比较菜只有 A ~ E
原题面
使得所有的 \(1\) 连续也就是所有的 \(1\) 中间的 \(0\) 全部去掉，也就是可以理解为第一个 \(1\) 到最后一个 \(1\) 中间的 \(0\) 全部去掉，也就是它们之间 \(0\) 的个数，那么就顺序、逆序扫一遍就出来了。
#include<bits/stdc++.h>using namespace std;int main(){ int t; cin>>t; while(t--){ string s; cin>>s; int l = -1,r = -1; for(int i=0; i<s.size(); i++){ if(s[i] == '1'){ l = i; break; } } for(int i=s.size(); i>=0; i--){ if(s[i] == '1'){ r = i; break; } } if(l == -1){ printf("0\n"); continue; } int ans = 0; for(int i=l; i<=r; i++){ if(s[i] == '0'){ ans++; } } printf("%d\n",ans); } return 0;}原题面
题目要求是至少有一半是在好天气中修的，那么我们就考虑如果好天气都修那么修到哪一天可以满足这个条件。
我们可以将每 \(g\) 天视为一轮，那么总共就有 \(\lfloor\dfrac{\lceil \dfrac{n}{2} \rceil}{g}\rfloor\) 个完整的轮数，以及多出来的 \(\lceil \dfrac{n}{2} \rceil\% g\) 天。这一轮既有好天气也有坏天气，所以最后得到在哪一天可以满足条件时要算上坏天气的天数。如果多出来的天数不为 \(0\)，那么就意味着这么多轮坏天气都需要经过，而如果多出来的天数为 \(0\)，那么意味着经过坏天气的轮数是我们求出来的轮数减一，因为最后一轮不需要经过坏天气。
所以最后在哪一天可以满足条件的答案就是:（令 \(x = \lfloor\dfrac{\lceil \dfrac{n}{2} \rceil}{g}\rfloor\)）
#include<bits/stdc++.h>using namespace std;int main(){ long long t; cin>>t; while(t--){ long long n,g,b; cin>>n>>g>>b; long long x = (n+1)/2/g; if(((n+1)/2)%g == 0){ printf("%lld\n",max((x-1) * b + x * g,n)); } else{ printf("%lld\n",max(x * (g+b) + ((n+1)/2) % g,n)); } } return 0;}一个优美的技巧：\(\lceil \dfrac{n}{2} \rceil\) 可以写为： \(\lfloor \dfrac{n+1}{2} \rfloor\)
原题面
这种题很显然要先考虑转化为图上的问题。
很显然我们可以在 \(S\) 中相邻的两个字符之间连边，表示这两个字符必须相邻。
判断无解的条件也很明显了：
#include<bits/stdc++.h>using namespace std;const int MAXN = 50;int head[MAXN],cnt,du[MAXN],edge[MAXN][MAXN];bool vis[MAXN],flag,use[MAXN];void dfs(int now,int from){ vis[now] = true; for(int i=0; i<26; i++){ if(i == from || !edge[now][i] || now == i) continue; if(vis[i]){ flag = true; return; } dfs(i,now); }}void get_ans(int now,int from){ if(!vis[now]) cout<<char(now + 'a'); vis[now] = true; for(int i=0; i<26; i++){ if(vis[i] || i == from || !edge[now][i] || now == i) continue; get_ans(i,now); }}int main(){ int t; cin>>t; while(t--){ memset(edge,0,sizeof(edge)); memset(vis,false,sizeof(vis)); memset(use,false,sizeof(use)); memset(du,0,sizeof(du)); cnt = 0; flag = false; int mx = 0; string s; cin>>s; for(int i=0; i<s.size() - 1; i++){ if(!edge[s[i]-'a'][s[i+1]-'a']){ du[s[i]-'a']++; du[s[i+1]-'a']++; mx = max(mx,max(du[s[i]-'a'],du[s[i+1]-'a'])); } edge[s[i]-'a'][s[i+1]-'a'] = true; edge[s[i+1]-'a'][s[i]-'a'] = true; use[s[i] - 'a'] = true; use[s[i+1] - 'a'] = true; } for(int i=0; i<26; i++){ if(!vis[i]){ dfs(i,i); } if(flag) break; } if(flag || mx >= 3){ printf("NO\n"); } else{ printf("YES\n"); memset(vis,false,sizeof(vis)); for(int i=0; i<26; i++){ if(du[i] == 1) get_ans(i,i); } for(int i=0; i<26; i++){ if(!vis[i]) cout<<char(i + 'a'); } printf("\n"); } } return 0;}因为可能含有大量的重边而且点的数量很少所以可以考虑使用邻接矩阵。
输出的时候也要注意可能有的点没有出现那么就在最后输出这些没有出现的点。
所谓有大小大于等于三的环也可以理解为无向图上的有环，也就是如果从当前节点可以到达一个曾经访问过但不是其父亲的点那么就意味着有环。
原题面
考虑物品大小都是 \(2\) 的非负整数次幂也就可以联想到将 \(n\) 二进制拆分，因为这些物品的顺序不影响答案所以就考虑将他们存放到 \(cnt\) 数组中去。
考虑如果 \(n\) 的当前位我们数组中有那么直接减就好了，很显然这样做最优。而如果没有那么就要考虑是用比当前位小的那些数加和凑出这个位还是从比当前位更大的位拆。
那么这样就意味着我们要维护一个 \(sum\) 代表比当前位小的那些数的和，如果这个值大于当前位的值显然就扫一遍比它小的位然后减去这些位的值直到减为 \(0\) 就好。
而如果用比它小的数凑不出来当前位那么就找到比当前位大的最小的有值一位，然后从这一位一直拆，拆到当前位然后减掉就好了。
#include<bits/stdc++.h>using namespace std;const long long MAXN = 3e5+5;long long cnt[MAXN];int main(){ long long t; cin>>t; while(t--){ memset(cnt,0,sizeof(cnt)); long long flag = 0; long long n,m; long long mx = 0; cin>>n>>m; for(long long i=1; i<=m; i++){ long long a; cin>>a; cnt[int(log2(a))]++; mx = max(mx,a); flag += a; } if(flag < n){ printf("-1\n"); continue; } long long sum = 0; long long now = 0; long long ans = 0; while(n){ if(n & 1){ if(cnt[now]){ cnt[now]--; } else if(sum >= (1<<now)){ //用低位补 long long res = (1<<now); for(long long i=now-1; i>=0 && res; i--){ if(cnt[i] * (1<<i) <= res){ sum -= cnt[i] * (1<<i); res -= cnt[i] * (1<<i); cnt[i] = 0; } else{ while(cnt[i] && (1<<i) <= res){ res -= (1<<i); sum -= (1<<i); cnt[i]--; } } } } else{ //找到高位拆 for(long long j = now+1; j<=mx; j++){ if(cnt[j]){ for(long long k=j; k>now; k--){ cnt[k-1] += 2; cnt[k]--; ans++; } break; } } cnt[now]--; } } n>>=1; sum += cnt[now] * (1<<now); now++; } cout<<ans<<endl; } return 0;}注意一开始先判断有无解，也就是所有数加起来能不能大于等于 \(n\)，若能大于等于显然有解。
原题面
我们很明显可以想出来一步：枚举 \(t\) 在哪里拆开，然后将 \(t\) 转化为 \(t1+t2\)，再判断 \(s\) 中能不能拆出 \(t1,t2\) 就好了。
那么问题就转化为了 \(s\) 中能不能拆出来的问题了。发现可能需要 \(dp\) 求解。
很显然的状态是：\(dp[i][j][k]\) 表示 \(s\) 的前 \(i\) 位能不能拆出 \(t1\) 的前 \(j\) 位和 \(t2\) 的前 \(k\) 位，因为状态量过大我们就考虑优化这个状态。
也就是将状态改写为：\(dp[i][j]\) 表示 \(s\) 的前 \(i\) 位拆出 \(t1\) 的前 \(j\) 位最多再拆出 \(t2\) 的前多少位。这样当 \(dp[size_s][size_{t1}] = size_{t2}\) 时也就意味着可以拆出。
那么就考虑转移，转移也就是做决策，这里的决策显然就是 \(s\) 的当前位应该放到 \(t1\) 的后面还是 \(t2\) 的后面还是都不放，这样也能保证是不相交的子序列。
（1）当 \(s[i+1] = t1[j+1]\) 时，\(dp[i][j] \to dp[i+1][j+1]\)
（2）当 \(s[i+1] = t2[f[i][j] + 1]\) 时，\(dp[i][j] + 1 \to dp[i+1][j]\)
（3）任何情况下，\(dp[i][j] \to dp[i+1][j]\)，这个也十分显然
#include<bits/stdc++.h>using namespace std;const int MAXN = 805;int f[MAXN][MAXN];bool check(string s,string t1,string t2){ memset(f,-1,sizeof(f)); f[0][0] = 0; s = '0' + s; t1 = '0' + t1; t2 = '0' + t2; for(int i=0; i<s.size(); i++){ for(int j=0; j<t1.size(); j++){ if(f[i][j] == -1) continue; f[i+1][j] = max(f[i+1][j],f[i][j]); if(s[i+1] == t1[j+1]) f[i+1][j+1] = max(f[i+1][j+1],f[i][j]); if(s[i+1] == t2[f[i][j] + 1]) f[i+1][j] = max(f[i+1][j],f[i][j] + 1); } } if(f[s.size()-1][t1.size()-1] == t2.size()-1) return true; return false; }bool solve(string s,string t){ for(int i=0; i<=t.size(); i++){ string t1,t2; for(int j=0; j<i; j++){ t1 = t1 + t[j]; } for(int j=i; j<t.size(); j++){ t2 = t2 + t[j]; } if(check(s,t1,t2)) return true; } return false;}int main(){ int n; cin>>n; while(n--){ string s,t; cin>>s>>t; if(solve(s,t)){ printf("YES\n"); } else{ printf("NO\n"); } } return 0;}我们会发现对于 \(dp\) 的边界、初值不好设置，那么就将所有的字符串前面加上一位那就好转移了。