codeforces 906C
A. Shockers
introduction
这道题要充分理解题意和输入的意思。
method
可以用集合的思想的做
集合\(A\)表示可行的字母，初始是\(26\)个字母
集合\(B\)表示每一句操作的字符的集合
集合\(C\)表示猜过的字符的集合
每读入一个动作，
如果\(|A|>1\)我们做如下操作:
\[ A= \begin{cases} A\cap B, & \text{if $op$ is !} \\ A\setminus B, & \text{if $op$ is .}\\ update \ C, A\setminus C,&\text{if $op$ is ?} \end{cases}\\ op \in \{!, . , ?\} \]
如果\(|A|=1\):
统计多余的次数
tips
- set的初始化方法
- set_intersection和set_difference的用法
- 关闭cin和stdio的同步
- cin接受行末的\n
Q&A
conclusion
做这道题学到了很多新的知识，尝试使用STL中的set来解决问题。
如果WA是因为思路有问题，那么可以查看别人AC的代码的测试数据，可以作为判断问题的依据。为codeforces打call。
reference
https://ask.csdn.net/questions/63825
https://blog.csdn.net/kalilili/article/details/42177279
http://c.biancheng.net/view/537.html
code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<istream>
#include<cassert>
#include<set>
#include<iterator>
#define DEBUG(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int MAXN=1e5+10;
typedef long long ll;
vector<string>input;
set<char>cndt;
set<char>ask;
void fillcndt()
{for(int i=0;i<26 ;i++ ){cndt.insert('a'+i);}
}
int main()
{
// freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);fillcndt();int n;(cin>>n).get();for(int ii=0;ii<n ;ii++ ){string t;getline(cin,t);input.push_back(t);}char ltr=input[n-1][2];int ans=0;for(int ii=0;ii<n-1 ;ii++ ){set<char>tmp;set<char>strst{input[ii].begin()+2,input[ii].end()};char &c=input[ii][0];if(cndt.size()>1){if(c=='!')set_intersection(cndt.begin(),cndt.end(),strst.begin(),strst.end(),inserter(tmp,tmp.begin()));else if(c=='.')set_difference(cndt.begin(),cndt.end(),strst.begin(),strst.end(),inserter(tmp,tmp.begin()));else if(c=='?'){ask.insert(input[ii][2]);set_difference(cndt.begin(),cndt.end(),ask.begin(),ask.end(),inserter(tmp,tmp.begin()));}cndt=tmp;}else if(c=='!'||c=='?'){assert(cndt.size()!=0);ans++;}}cout<<ans;
}