B 模拟 相邻的反转 注意反斜杠需要转义 int a[200][200]; void solve() { int n, m; cin >> n >> m; rep(i, 1, n) { rep(j, 1, m) { if (j == 1) { if (i == 1) { a[i][j] = 1; } else { a[i][j] = a[i - 1][j] ^ 1; } } else { a[i][j] = a[i][j - 1] ^ 1; } } } rep(i, 1, n) { rep(j, 1, m) { if (a[i][j]) { cout << ...

A 模拟 注意是出来自己之外有80% int a[N]; void solve() { int n; cin >> n; rep(i, 1, n) { cin >> a[i]; } int ans = 0; rep(i, 1, n) { int cnt = 0; rep(j, 1, n) { if (a[j] <= a[i]) { cnt++; } } if (cnt * 10 >= 8 * n) { ans += a[i]; } } cout << ans << '\n'; }  B 前缀和 前缀和维护每个人开始的第一年 int t...

A 数学 问一个数能否表示成。如果能，则，检查这个即可 void solve() { int n; cin >> n; int t = sqrt(n); if (t * (t + 1) == n) { cout << "YES"; } else { cout << "NO"; } }  B 概率 数论 找出一对，保证数据是随机生成的。这种问题，先考虑偶数，然后就会发现，由于是随机生成，所以较大时全是奇数的概率很低，可以忽略不计。所以设定一个阈值，大于这个阈值，认为一定存在至少两个偶数，有解；小于这个阈值，暴力枚举全部个数对，检查 void solve() {...

A 思维 三种东西，构造一个序列，让连续三个元素都不同。 每次选三个东西接到序列末尾，每次的三个东西的排列都相同，最后一轮可以不满三个。这样则受限于，如果差距过大，一个用完了，另一个还有超过一个，就不行。 void solve() { vi a(3); for (int &x : a) { cin >> x; } sort(a.begin(), a.end()); if(a[1]-a[0]>1||a[2]-a[0]>1){ cout<<"NO\n"; } else{ cout<<"YES\n"; } }  B 思维 博弈 思维太难。。。个...

A 概率 模拟 八个一样的显示器，都是七段数码管，每个灯管都有一个通电后亮不亮的概率。一次尝试点亮每一个灯管。上下各四个，问上下形成的数字和为给定数字的概率。 七个灯管之间是独立的，用每个灯管亮灭的概率能组合出显示0-9的数字的概率，进一步可以算出四个灯管组成不同数字的概率。然后枚举上面的灯管，上下和一定，可以确定下面的灯管的值和概率，相乘就是上下加起来等于c的一种情况的概率，累加就是答案 计算0-9的数字的概率这块写起来有点难受，可能有状压的写法更快，以及可以用自动取模的modint类来省去取模 复杂度，瓶颈在预处理四位数的概率，可以压到 void solve() { int c; cin ...

A 最小表示法 字符串匹配 长得像的字母和数字被认为是一样的，问两个串是否相同。 比较简单的写法是类似最小表示法的思想。规定每一组相似字符，都变成其中某一个字符，然后看是否严格相等即可 void solve() { int n; cin >> n; string s1, s2; cin >> s1 >> s2; for (auto &c : s1) { if (c == 'O') { c = '0'; } if (c == 'l' || c == 'I') { c = '1'; } } for (auto &c : s2) { if (c =...

D 二分 贪心 删掉个元素，剩下每个连续段，元素求和，取为答案，问答案最大值？ 首先这个最大化最小值就是在暗示二分，然后里，是要我们把这个序列拆成多段，约束是要删掉个来实现拆分。 这个的思路也比较显然，拆分数组，每一段需要满足一定限制才能拆出来，约束是拆的次数，那么一般就贪心的拆，然后看操作次数能否满足约束。具体来说就是我们二分出来最小值，那么每一段元素和不小于这个最小值了，就可以拆出来。然后有一个贪心是，如果拆出来段数大于要求，肯定也是可以的，因为我们可以把两段合并，减小段数到，而合并了元素和只会变大（元素全是正数），肯定依然满足不小于最小值的约束，所以贪心地能拆就拆。 然后一个观察是，开头...

C 思维 每个人都给出除了自己以外，人数最多的颜色有多少人。问能否判断有人说谎 如果只有一组人数最多的颜色，有人，没人撒谎的情况肯定是，这组内人报告，这组外其他人报告 如果有多组人数最多的颜色，都有人，那么所有人都报告。因为至少有两组，所以总人数不少于。 还一种可能是个人颜色都一样，所有人都报告，也是可以的 其它都不合法 void solve(){ int n; cin>>n; vi a(n+1); rep(i,1,n)cin>>a[i]; set<int>s; map<int,int>mp; rep(i,1,n){ s.insert(a[i])...

A 模拟 检查字母按字典序升序，出现次数是否是一个公差为1的数列 void solve(){ int n; cin>>n; string s; cin>>s; map<char,int>mp; for(char c:s){ mp[c]++; } bool ok=1; int pre=-1; for(auto &[k,v]:mp){ if(v!=pre+1&&pre!=-1){ ok=0; } pre=v; } if(ok)cout<<"YES\n"; else cout<<"NO\n"; }  B 枚举 检查是...

A 模拟 问能否删除一些字符后重新排列，能组成给定的字符串。 可以排列，所以只要传力每种字符的出现次数，都比目标串更多即可，这可以统计，然后枚举目标串的 void solve(){ int n; cin>>n; string s="Kato_Shoko"; string t; cin>>t; map<char,int>mp1,mp2; for(char c:s)mp1[c]++; for(char c:t)mp2[c]++; bool ok=1; for(auto &[k,v]:mp1){ if(mp2[k]<v)ok=0; } if(ok){...

B 逆序对 循环移位 给一个排列，问每次循环移位一个区间后，序列逆序对奇偶性 交经典结论，换两个相邻元素，保证元素不同，逆序对奇偶反转。循环移位这个区间，相当于把移动到左边，其他不变，也就是交换次。根据的奇偶，即可知道操作完，整个序列逆序对的奇偶。 F 状压 枚举 二分  不大，保留灯管的所有情况最多也不多。考虑枚举所有保留的灯管集合，对每个集合去检查能否区分种数字。检查时直接保存mask&a_i，看结果是否有种，这可以unordered_map实现。但常数有点大，也可以记录每种结果的出现次数，手动维护结果种类数。每次枚举都要清空，值域显然不能暴力清空，考虑用时间戳思想。 这样复杂度还...

C 贪心 每次可以选一个子序列，全部减一。问最少多少次操作可以变成不减。 只能减不能加，那么贪心的想，最后一个元素一定不能减，否则它变小了，可能需要前面的元素减更多次才能保证序列不减。 所以处理完一个后缀之后,一定比后缀里的所有都要小，也就是比小。如果初始，需要减小到，如果本来就比小则不用操作。 最后我们每次可以操作一个子序列，也就是同时操作多个。所以操作次数上界取决于需要操作次数最多的那个元素。 #include <bits/stdc++.h> #define int long long using namespace std; using ll = long long; usi...

F 双指针 扫描线 线段树 确定两个指针把数组分成三段，求一个方案使得三个集合的交集最大 有两个指针的位置需要确定，显然考虑枚举，然后对每个确定三个集合交集最大的的位置 对于每种元素，想要这个元素出现在交集里，也就是三个集合都有这个元素，如果确定，设这个元素在里最左出现位置是，最右出现是，那么想让三个区间里都有这个元素，可以位于这区间。 也就是对于每个元素都有个可以位于的区间，然后对于一个位置，的话，交集的大小，就是覆盖这个的区间个数。 那么这就是一个区间加，球单点最值，线段树维护即可。 具体就是，用一个数组维护左侧这个集合的元素，枚举，扫描整个原序列，如果的位置是一个左侧集合未出现的元素，我...

A 树形dp 观察 可以删点，加点，问把一个二叉树变成avl的最少操作次数？ avl的要求就是左右子树都是avl树，且左右子树高度差不超过1. 注意到这是个递归定义，可以考虑树形dp，计算出一个点的两个子树变成avl树的最小代价，然后再用这两个一个变成avl的子树，和当前点拼起来，就能计算当前点为根的子树变成avl的最小代价 但是，想让当前点为根的子树是avl，不仅需要两个子树都是avl，还需要知道两个子树的高度，然后看他们满不满足子树高度差不超过1的这个约束。而子树高度可以是任意取值，所以考虑把子树高度也放在dp状态里 也就是表示以为根的子树，变成高度为的avl树，的最小代价。那么我们转移时...