前端之家收集整理的这篇文章主要介绍了
cf1234-div3，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
A
@H_
403_8@水题
B
@H_
403_8@直接看2，发现`unordered_map被卡了。。。`
@H_
403_8@乖乖离散化
C
@H_
403_8@有六种水管，可以任意的旋转，使得有一条从(1,0)到(2,n)的通路。
@H_
403_8@找规律，当时写D没来得及看
@H_
403_8@
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<queue>
6 #include<cmath>
7 #include<map>
8 #include<stack>
9 #include<set>
10 #include<bitset>
11
12 using namespace std;
13 typedef long long ll;
14 typedef unsigned long long ull;
15 typedef pair<int,int> pii;
16 #define pb(x) push_back(x)
17 #define cls(x,val) memset(x,val,sizeof(x))
18 #define fi first
19 #define se second
20 #define mp(x,y) make_pair(x,y)
21 #define inc(i,l,r) for(int i=l; i<=r; i++)
22 const int inf = 0x3f3f3f3f;
23 const int maxn = 2000+10;
24 int n;
25 string s[2];
26
27 int main(){
28 ios::sync_with_stdio(false);
29 int _;
30 cin>>_;
31 while(_--){
32 cin>>n;
33 cin>>s[0]>>s[1];
34 int row=0;
35 int pos = 0;
36 for(pos=0; pos<n; pos++){
37 if(s[row][pos]>=‘3‘){
38 if(s[row^1][pos]<‘3‘) break;
39 else {
40 row ^= 1;
41 }
42 }
43 //cout<<row<<" "<<pos<<endl;
44 }
45 //cout<<"lst "<<row<<" "<<pos<<endl;
46 if(row == 1&&pos == n){
47 cout<<"YES"<<endl;
48 }else cout<<"NO"<<endl;
49 }
50
51
52 return 0;
53 }
View Code
@H_
403_8@
D
@H_
403_8@很裸的线段树，第一次正式的比赛AC了线段树，虽然很裸。。。
@H_
403_8@
E
@H_
403_8@看起来很复杂的算式计算，不想补了。。
@H_
403_8@
F SOS dp
@H_
403_8@原题意：
@H_
403_8@给一个字符串，长度可达1e6,最多翻转一个子串，使得最后选择一个子串，使得该子串包含的不同的字母的个数最大。
@H_
403_8@题意转换：
@H_
403_8@找两个不想交的子串，使得不相同的子串的个数最多。
@H_
403_8@1. 计算所有的子串的最大个数
@H_
403_8@2. 更新所有的集合i中包含的不同字母的最大个数。（dp[i]表示i的子集中的最大不同字母个数）
@H_
403_8@3. $ans = max(ans,dp[i]+dp[i \quad xor \quad all])$
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<queue>
6 #include<cmath>
7 #include<map>
8 #include<stack>
9 #include<set>
10 #include<bitset>
11
12 using namespace std;
13 typedef long long ll;
14 typedef unsigned long long ull;
15 typedef pair<int,r) for(int i=l; i<=r; i++)
22 const int inf = 0x3f3f3f3f;
23 const int maxn = 1e6+10;
24
25
26 int n,m,k;
27
28 char s[maxn]; int dp[1<<20];
29
30 int main(){
31 while(~scanf("%s",s+1)){
32 n = strlen(s + 1);
33 for(int i=1;i<=n;i++) s[i] -= ‘a‘;
34
35 memset(dp,0,sizeof(dp));
36 for(int i=1;i<=n;i++){
37 int x = 0,c = 0;
38 for(int j=i;j<=n;j++){
39 if((x >> s[j]) & 1) break;
40 x |= (1 << s[j]); c++;
41 dp[x] = c;
42 }
43 }
44
45
46 for(int i=0;i<20;i++){
47 for(int mask=0;mask<(1<<20);mask++){
48 if((mask>>i)&1){
49 //原来是仅有的几个状态被覆盖到了，现在是全部有覆盖一遍。
50 //i表示的集合是i的子集。
51 dp[mask] = max(dp[mask],dp[mask^(1<<i)]);
52 }
53 }
54 }
55
56 int ans = 0,all = (1<<20) - 1;
57 for(int i=0;i<(1<<20);i++){
58 ans = max(ans,dp[i] + dp[all^i]);
59 }
60 printf("%d\n",ans);
61 }
62 return 0;
63 }
View Code
