A 除500和对500取模即可，但是这个余数是1-500的，并不是0-499，所以直接取模会在边界情况出错，需要特判一下 void solve(){ cin>>n; int x=n/500; char c='A'+x; int y=n%500; if(y){ cout<<c; string s=to_string(y); while(s.size()<3)s='0'+s; cout<<s; } else{ c--; cout<<c<<"500"; } }  B 模拟，吧目标串的字符放到一个集合里，然后看猜的串...

A 每次可以选一个子区间，复制其中所有元素，那其实我们可以用这个操作把初始元素变成任意多个，但是我们不能凭空变出来一个元素。那么给出操作后的数组，其中每一段连续相同元素，一定是初始数组中至少一个该种元素操作得来的。因此把每一段连续相同元素缩成一个该种元素，就是最小的初始数组 void solve(){ cin>>n; vi a(n+1); rep(i,1,n)cin>>a[i]; int ans=1; rep(i,2,n){ if(a[i]!=a[i-1]){ ans++; } } cout<<ans<<'\n'; }  B 经典子序列+状态机d...

G 求n模i的余数的前k大的和，其中i属于。 首先是一个和整除，求和有关的东西，先想想数论分块。实际上 n模i=n-floor(n/i)*i 然后在整除分块的一个块里是一样的，所以在一个块里，余数是一个等差数列。然后我们要求前k大的余数的和，可以找到第k大的的余数的值，然后对于大于这个值的余数，直接求和，对于等于这个值的余数，取一定个数的求和，直到求和元素总个数等于k 那么我们首先需要找到第k大余数的值，这可以二分第k大实现，我们每次check就遍历一遍所有块，把大于mid的值的个数求和，如果总数小于，就缩小mid，反之增大mid。计算一个块大于mid的余数个数时，我们可以先算出这个等差数列的...

A 签到 判断一个数列是否由给定元素构成，由于反例很少，可以从反例入手，写的更短 #include<bits/stdc++.h> using namespace std; int main(){ int f=0; for(int i=0;i<7;i++){ int x; cin>>x; if(x==4||x==7)f=1; } if(f)cout<<"NO"; else cout<<"YES"; }  B 签到 找到至少比一半元素小的最大元素，先排序然后找中位数前面那个数就行 #include<bits/stdc++.h> us...

A 找到一个数和数组中任何一个数都不互为倍数，注意到数组中数字不超过1e9，但我们找的这个数可以1e18，那显然找一个比1e9打的质数就行了。但是注意任何数都是1的倍数，所以出现1就无解 #include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; int cnt=0; for(int i=0;i<n;i++){ int x; cin>>x; if(x==1)cnt++; } if(cnt)cout<...

周赛77 B 注意力 注意到我们要求每个长度为9的子数组都出现1-9，那么实际上构造方式只能是选择一个1-9的排列然后一直循环，最后剩下的不到9个也可以利用前面的组成长度为9的排列。 但是注意到这样是不行的，也就是只有剩余不到9个的数里没有重复的才行。这个条件也可以转化为，所有数字中最大出现次数-最小出现次数不能超过1 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int cnt[10]={0}; for(int i=0;i<n;i++){ int t; cin&gt...

B 可以把一个区间的数字都变成出现次数较多的元素，问把整个数组变成相同元素，最少操作几次。 首先可以注意到只有01两种元素，那么长度为奇数的数组，01个数一定不等，也就是01一定有一个比另一个更多，可以执行操作变成同一个，因此长度为奇数答案至多为1 长度为偶数时，如果01个数不同，也是一次操作。如果01个数相同，我们可以取长度为n-1的子数组，它的长度是奇数，一定能通过一次操作变成一样的。这样的子数组一共有四个，我们看这四个情况，变完之后剩下的那一个元素和变完的元素是否相同，如果相同就是一次操作。如果不同还需要一次把剩下的拿一个元素变了，就是两次操作 当然需要注意初始全都相同就不用操作 voi...

周赛round36 E 构造一张图，让左上角到右下角的最短路不是把所有点都走一遍，也不是长度为n+m-2（一直向下或向右），并且不存在绝对众数（某个字母出现次数大于总数一半） 由于是构造题，不止一种思路。我开始想的是一种比较麻烦的，不过最后也过了。就是类似样例里的那种走法，先一直往下，再一直往右，直到(n,m-1)，往上拐一个小圈到达(n,m)，这样路径长度为n+m。为了保证只有这一种走法，把这条路径的边上都用封住。剩余格子只要保证别出现绝对众数就可以了，那么可以每次都放出现次数最小的。 ">using namespace std; const int N=1e3+10; int a[N][N...

B 博弈 虽然不难但是很有教育意义。很大一类博弈问题的思路都是：某一个量每轮都可以变化某一固定值，当这个量达到某一阈值时游戏结束。那么不管怎么操作，游戏的胜负在开始时都已经注定了，唯一的影响就是先后手，只要判断下奇偶就行了。 对这题来说，每轮都变化的固定值是每轮数字个数都会减一，阈值是结束时数字一定是奇偶交替排列，奇偶数量相等，也就是总数一定是偶数。那么就很简单了，开始时数字个数如果是奇数，先手必胜，反之先手必败。 不过考场上并没有做出来，因为没看到数字是在一个环上的，所以说一定要认真读题…… GH 枚举 只有三个元素，完全可以把他们所有的大小关系全枚举出来，然后看是否存在一种满足题目给出的约...

寒假营4 D 数论，特判！！ 每次可以把一个数减一，零一个数加一，问最终整个序列有多少种可能的gcd。一个数是整个数组的gcd，他首先一定是每个元素的约数，也就是说所有元素的和是这个数的倍数。 我们现在得到了一个判断的必要条件，但它实际上也是一个充分条件，可以通过构造证明：我们可以把一个数减一，零一个数加一，那么我们实际上就可以把sigma(a(i))的值随意分配到n个位置上。那么如果sigma(a(i))是一个数x的倍数，我们可以把一个元素变成x，剩下的元素都变成kx，k>=1。此时整个序列的gcd就是x了。 前面的比赛时都想到了，但是没考虑到元素个数为1的特判，我以为都说gcd了，肯...

寒假营第五场 B 思维 可以删任意个数的字符串，但是不能删连续两个，每种删除方案的得分是"mygo"出现的次数，问全部方案的总分。 首先一个重要的观察是，由于不能删连续字符，删除后能出现"mygo"的字符串实际上只有八种，具体来说就是"mygo"中间的三个空都可以插入一个其他字符。对于这八种字符串，都有唯一的删除方式使删完出现一个"mygo"。 另一个重要的观察是，既然遍历所有删除方式，分别计算贡献很麻烦，那么我们可以分开计算每一个"mygo"对答案的贡献。对于每一个"mygo"，得到他的删除方式再mygo内部是唯一的，而外部可以随意删。我们需要外部随意删有多少种方案，这些方案的贡献都是1，也...

周赛round32 D 树形dp 每个节点有0或1的权值，设f(i)为从i节点出发，向叶子节点走，可以中途停下，所形成的数字中奇数的个数，求所有f(i)。奇数显然就是最后一位为1，所以这实际上就是要求每个节点所在子树权值为1叶结点个数。但又特殊规定：单独的叶节点不能形成一个数，因此叶节点虽然对祖先的f(i)有贡献，但对自己的f(i)无贡献。 所以这个dfs不能写成无返回值，f(i)初始化为当前节点权值，每次都把儿子节点的f(i)加进当前节点f(i)中的形式从，这样会把叶节点的f(i)也算成1。而应该写成有返回值，f(i)初始化为0，f(i)加上子节点递归返回值，返回f(i)加当前节点权值的形式...

寒假训练营2 C 字典树 求升序子序列个数，其中最大值和最小值的异或小于等于d。如果确定了最小值最大值分别为a[i]，a[j]，，那么中间的数都可选可不选，这组maxmin对总方案数的贡献就是2^(j-i-1)。 直接二重循环枚举minmax显然是不行的，只能枚举一个，然后logn查询另一个。但这个查询是要查询抑或上一个数不超过d的元素个数，此时用字典树才能达到logn。 字典树用叶子节点表示一个元素，从根节点到叶结点的路径则是这个元素的二进制表示，0为左，1为右。查询时，由于异或的结果不大于d，如果d某一位是1，那么minmax在这一位可以一样，也可以不一样，如果不一样，接着往下走，直到达到...

寒假训练营1 E dfs 被骗了，名字叫贪心，实际上是dfs。 注意到比赛场数只有10场，每场只有3种结果，爆搜复杂度也只有3^10，果断dfs。教训是数据小到能爆搜，就直接爆搜。  if(x==m+1){//比完了 int p0=p[0]; sort(p.begin(),p.end(),cmp); // rep(i,0,p.size()-1)cout<<p[i]<<' '; // cout<<'\n'; rep(i,0,p.size()-1){//计算排名 if(p[i]==p0){ ans=min(ans,i+1); return; } } } vect...