初赛
A
题目大意：给定一段元素，分为相等的两部分，使剩下的元素尽量少
看了看题解发现是个DP(虽然第一反应是DP，当时不知怎么一直在往费用流的方向想QAQ)
代码回头补
B
签到题
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#define N 110
using namespace std;
int n,m,a,b,c,T,i,ans;
int e[N],p[N];
inline void Ready(){
for (int i=1;i<=100;i++) e[i+1]=(i*a+b)%c;
}
inline bool Check(int x){
int i=0,s=0;
for (i=1;i<=x;i++) p[i]=e[i];
sort(p+1,p+1+x);
for (i=1;i<=x-n;i++) s+=p[i];
return (s<=m)?1:0;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
Ready(); ans=1;
for (i=1;i<=100;i++) if (Check(i)) ans=i; else break;
printf("%d\n",ans);
}
return 0;
}
C
没有题解+并不会做
D
签到题
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 1010
using namespace std;
int n,T,i,cnt,eps=0,ans=0;
int a[N],b[N];
inline int Max(int a,int b){return (a>b)?a:b;}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
ans=0; cnt=0; eps=0;
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) scanf("%d",&b[i]);
if (n==1){
printf("%d\n",a[1]);
continue;
}
ans=cnt=a[1];
for (i=2;i<=n;i++){
cnt+=b[i]; ans+=cnt;
if (cnt<a[i]) eps=Max(eps,a[i]-cnt);
}
printf("%d\n",ans+n*eps);
}
return 0;
}
E
题目大意：给定N个点，构造一个最大生成树，边权的定义为两点点权的gcd
做法：类比于Kruskal算法，从大到小枚举gcd的值，然后连边即可，拿并查集维护。
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 100010
#define LL long long
using namespace std;
int T,i,x,flag,p,q,n,m;
int f[N],b[N];
LL Ans=0;
inline int Max(int a,int b){return (a>b)?a:b;}
inline int Find(int x){return (x==f[x])?x:f[x]=Find(f[x]);}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n); Ans=0;
memset(b,0,sizeof(b)); memset(f,0,sizeof(f));
for (i=1;i<=n;i++){
scanf("%d",&x);
if (x==1) {
Ans+=1; continue;
}
f[x]=x; (!b[x])?b[x]=1:Ans+=x;
m=Max(m,x);
}
for (i=(m/2)+1;i;i--){
x=i; flag=0; p=0; q=0;
while (x<=m){
if (!b[x]) goto END;
q=Find(f[x]);
if (flag==0){
flag=q; p=x;
} else {
if (flag==q) goto END;
f[q]=flag; Ans+=(LL)i;
}
END:
x+=i;
}
}
printf("%lld\n",Ans);
}
return 0;
}
F
题目大意：求n个同余方程
（i+1）^{i+1}\equiv (i+1)^{i} (mod\ m)
的解的个数。(1<=i<=n)
解法：不难发现，求解的个数可以转化为求
i*(i+1)^{i}
的因子数。
前一项可以线性筛，后一项可以通过枚举质数算贡献。算完直接乘起来，再预处理好前缀和就行了。
被边界条件和内存卡了无数次
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 10000011
#define MOD 998244353
#define LL long long
using namespace std;
int T,n,i;
bool flag[N];
int p[700000];
int Ans[N],d[N];
LL e[N];
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Ready(){
LL i=0,x=0,cnt=0,j=0,l=0;
for (i=2;i<=N-10;i++){
if (!flag[i]) p[++p[0]]=i;
for (x=i+i;x<=N-10;x+=i) flag[x]=1;
}
d[1]=1;
for (i=2;i<=N-10;i++){
if (!flag[i]){
d[i]=2; e[i]=1;
}
for (j=1;j<=p[0];j++){
if (i*p[j]>N-10) break;
if ((i%p[j])!=0){
d[i*p[j]]=d[i]*2; e[i*p[j]]=1;
} else {
d[i*p[j]]=d[i]/(e[i]+1)*(e[i]+2);
e[i*p[j]]=e[i]+1;
break;
}
}
}
for (i=1;i<+N-10;i++) e[i]=1;
for (i=1;i<=p[0];i++){
l=(N-10)/p[i];
for (j=1;j<=l;j++){
if ((j%p[i])==0) continue;
if (j*p[i]>N-10) break;
for (cnt=1,x=j*p[i];x<=N-10;x*=p[i],cnt++)
e[x]=((LL)e[x]*(1+cnt*(x-1)))%MOD;
}
}
for (i=1;i<=N-10;i++) Ans[i]=((LL)d[i]*e[i+1])%MOD;
for (i=2;i<=N-10;i++) Ans[i]=(Ans[i]+Ans[i-1])%MOD;
}
int main(){
Ready(); T=read();
while (T--){
n=read(); printf("%d\n",Ans[n]);
}
for (i=1;i<=100;i++) printf("%lld\n",e[i]);
return 0;
}
G
有待填坑
H
题目大意:德州扑克规则，已知可以组成顺子，已知桌面上五张牌，求手上牌的方案数
解法：枚举。还是签到题
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,i,j,Ans;
int s[50],a[50],t[50];
char c[110];
inline void Ready(){
int i=0;
memset(s,0,sizeof(s)); memset(a,0,sizeof(a));
for (i=0;i<=4;i++){
if (c[i]>='2'&&c[i]<='9') s[c[i]-48]++;
if (c[i]=='A') s[1]++;
if (c[i]=='T') s[10]++;
if (c[i]=='J') s[11]++;
if (c[i]=='Q') s[12]++;
if (c[i]=='K') s[13]++;
}
}
inline bool Check(int x){
int i=0;
for (i=x;i<=x+4;i++)
if (!a[i]) return 0;
return 1;
}
inline void Work(int x,int y){
int i=0;
for (i=1;i<=13;i++) a[i]=s[i];
a[x]++; a[y]++; a[14]=a[1];
for (i=1;i<=10;i++){
if (Check(i)) goto END;
}
return;
END:
if (x!=y) Ans+=(4-s[x])*(4-s[y]);
else Ans+=t[4-a[x]+2];
}
int main(){
scanf("%d",&n);
t[2]=1; t[3]=3; t[4]=6;
while (n--){
scanf("%s",&c); Ready();
for (i=1;i<=13;i++)
for (j=i;j<=13;j++){
if (i==j&&s[i]+2>4) continue;
if ((s[i]==4)||(s[j]==4)) continue;
Work(i,j);
}
printf("%d\n",Ans); Ans=0;
}
return 0;
}
I
题目大意：定义了四种矩阵，给出一个矩阵列，每一位上的矩阵为四种矩阵之一，定义每次操作后得到的新矩阵列为
b_{i}=a_{i}*a_{i\ mod \ n+1}
求k次操作后的矩阵列。
解法：题解的意思是这其实是一个Klein 群的矩阵表示，利用其性质用异或来做。
然而并不会Klein 群，所以经过分析，不难发现每个矩阵平方后可以得到一个单位阵，而经过数学归纳法，n次操作后得到的矩阵列中，每个位置上的矩阵可以表示成n个矩阵的次幂相乘的形式，而幂指数即为二项展开式系数。
考虑到一个矩阵的偶数次次方为单位阵，对结果不影响，再利用C_{n}^{k}在n为2的次幂时恒为偶数(除去两端)，通过快速幂的思想，每次对矩阵列进行2的次幂次操作，每一次操作后，每一位上的结果可以仅通过两个矩阵相乘得到(中间的矩阵次幂为偶数，计算得到的是单位阵，可以不考虑，只有首尾项不是偶数)。总时间复杂度为
O(T*nlog{k})
中间还被卡常了QAQ
话说这道题通过的人挺多的，大部分人应该都不是标程的解法吧毕竟这算法很冷门
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 1000010
using namespace std;
int i,j,T,n,k;
char c[N],e[N];
int p[50];
char f[150][150];
inline void Ready(){
int i=0;
for (p[0]=1,i=1;i<=30;i++) p[i]=p[i-1]<<1;
f[65][65]='A'; f[65][71]='G'; f[65][67]='C'; f[65][84]='T';
f[71][65]='G'; f[71][71]='A'; f[71][67]='T'; f[71][84]='C';
f[67][65]='C'; f[67][71]='T'; f[67][67]='A'; f[67][84]='G';
f[84][65]='T'; f[84][71]='C'; f[84][67]='G'; f[84][84]='A';
}
inline void Work(){
int i=0,j=0;
for (i=0;i<=30;i++){
if ((p[i]&k)==0) continue;
for (j=0;j<n;j++){
e[j]=f[(int)c[j]][(int)c[(j+p[i])%n]];
}
memcpy(c,e,sizeof(e));
}
printf("%s\n",c);
}
int main(){
scanf("%d",&T);
Ready();
while (T--){
memset(c,0,sizeof(c)); memset(e,0,sizeof(e));
scanf("%d%d",&n,&k); scanf("%s",&c);
Work();
}
return 0;
}
J
有待填坑
K
题目大意： 给定一个序列，每次求一段区间中的非零最小值和区间和，对区间进行取模运算(模数为查询得到的最小值)，然后再次求区间和
解法：
维护一棵线段树，因为每次取模运算后，一个非零数的值至多为之前的一半，所以每个元素至多被取模log次。线段树的节点维护区间的和，非零最小值。每次取模运算的时候暴力维护即可。
标算是并查集，线段树貌似可以被特殊数据卡
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define l(x) x<<1
#define r(x) (x<<1)+1
#define N 100010
#define LL long long
using namespace std;
int n,i,l,r,T,q;
LL s;
LL a[N];
struct Tree{
int l,r; LL p,d;
}t[8*N];
inline LL Min(LL a,LL b){
if (a==0) return b;
if (b==0) return a;
return min(a,b);
}
inline LL read(){
LL p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Maketree(int x,int low,int high){
int mid=(low+high)>>1;
t[x].l=low; t[x].r=high;
if (low==high) {
t[x].d=t[x].p=a[low]; return;
}
Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
t[x].d+=t[l(x)].d+t[r(x)].d;
t[x].p=Min(t[l(x)].p,t[r(x)].p);
}
inline LL Query(int x,int low,int high){
int mid=(t[x].l+t[x].r)>>1;
if (t[x].l==low&&t[x].r==high) return t[x].d;
if (high<=mid) return Query(l(x),low,high);
if (low>mid) return Query(r(x),low,high);
else return Query(l(x),low,mid)+Query(r(x),mid+1,high);
}
inline LL Get(int x,int low,int high){
int mid=(t[x].l+t[x].r)>>1;
if (low==t[x].l&&high==t[x].r) return t[x].p;
if (high<=mid) return Get(l(x),low,high);
if (low>mid) return Get(r(x),low,high);
else return Min(Get(l(x),low,mid),Get(r(x),mid+1,high));
}
inline void Mod(int x,int low,int high){
int mid=(t[x].l+t[x].r)>>1;
if (t[x].l==t[x].r){
t[x].d%=s; t[x].p%=s; return;
}
if (t[x].p==0) return;
if (high<=mid) Mod(l(x),low,high); else
if (low>mid) Mod(r(x),low,high); else{
Mod(l(x),low,mid); Mod(r(x),mid+1,high);
}
t[x].d=t[l(x)].d+t[r(x)].d;
t[x].p=Min(t[l(x)].p,t[r(x)].p);
}
int main(){
T=read();
while (T--){
n=read(); q=read();
for (i=1;i<=n;i++) a[i]=read();
memset(t,0,sizeof(t));
Maketree(1,1,n);
while (q--){
l=read(); r=read();
printf("%lld ",Query(1,l,r));
s=Get(1,l,r);
if (s==0){
printf("%lld\n",Query(1,l,r));
continue;
} Mod(1,l,r);
printf("%lld\n",Query(1,l,r));
}
}
return 0;
}
L
题目大意：给定一个商品清单和初始钱数，每回合会更新可以买到的商品，回合结束时会获得当前钱数带来的利息。求最快几回合买够清单上的商品。
解法：显然，答案单调。二分答案+贪心，尽量晚点买。
决赛
比赛经历
今天阳光明媚风大，是个打比赛爆零的好日子。
机房在S7六楼，Win7系统，用起来并不卡顿。桌上有一瓶水+小零食*n，比赛环境还是很可以的。
到点后迟迟不开赛，结果得到通知推迟15min，然后在大约开赛半小时的时候才看到题，中间服务器又崩溃了老长时间，结果5点结束的比赛硬是延长到了6点……(其实相比而言还是能接受的，毕竟初赛咕了半年)
喝水看题。
点开A，看完后又看了一遍，确认是签到题，迅速码完一遍AC。
B题是求一个序列的第k小非空子序列，一眼望去不可做，直接过。C题是给定一个序列，从中抽取出不重合的几段，每一段的元素和大于给定的数m，使抽取的段数最多。这不是很经典的DP问题么。。。不过数据给的很奇怪，首先m可能为负，其次数据由给定的随机数生成器给出，输入数据提供随机种子，自己生成数据。自己造随机数据给我一种很奇怪的感觉，担心有坑点，先放一放。
抬头看了一眼榜，I题有人做出来了，立刻跳到I。题面是很经典的击鼓传花游戏，我记得这个好像是有公式的，但是我没背QAQ。仔细看了一眼后发现被选中的人并不会从游戏中出去，然后只需要判定第一个人会不会被选中就行了。立刻开始推式子，推了半天发现要判断整除关系，几次迭代下来怎么有了辗转相除的感觉。。。对式子一波变形，得到一个二元不定方程，发现直接上裴蜀定理，算一个gcd就行了。。。
写完提交的时候发现服务器崩了，没法交题也没法看榜，只能接着做别的题了。
回到C，思考了一下可以对m为负的情况拿贪心特判，别的情况直接套DP做，数据随机就随机吧，应该和解法没有关系。码完开D，经典的区间询问，不过需要在给定的区间内再找一个区间，然后最小化一个奇怪的分式，还要求按最简分式输出。貌似仍然不可做，直接跳过。。。E题是把字符串扔到了一个树上，树的中序遍历为原串，可以对树上的节点进行翻转操作，判断可不可以通过一个字符串生成另一个。感觉后缀那一套在这行不通，有Splay的感觉，不过本着先看完题的原则，继续选择跳过。
F是几何题，输出一个有n个点的坐标图，使任意两点间的中垂线上有别的点。手画了一下从3到7的情况，再往下就画不出来了，第一直觉是7以上无解？因为担心罚时，所以暂时没有动F，打算最后没题做了再碰碰运气。
继续往下看。H还是数学题，和lcm有关。目测是质因数分解套组合数计算。可能会有容斥在里面。G题题面最长，读完后发现是树上的问题，大意是树上每个节点都有一个权值v，v互不相同，每条边有边权。有m次询问，每次给定一个数d，求权值为d的倍数的点两两之间的路径长度和。第一反应是树剖+LCA，但是暴力计算两点路径明显会T。思考了一会后发现可以计算每个边对答案的贡献，对于每次特定的询问，处理好需要被计算的点的个数，和每个点子树下有多少个点需要计算。然后算每条边的贡献。不难发现需要被计算的d的数目是有限的，可以先全部读入进来统一处理。
码完之后反应过来时间复杂度算错了，不是O(n\sqrt{n}),是O(n^2)，根本过不去。。。观察了一会后又发现每次被计算的点的数目也是有限的，可以把这些点抽出来，对树重构，利用之前的思想算边权的贡献。重构过程中需要不断的求LCA，还需要维护区间边权和，于是又码了树剖和线段树上去，代码长度直奔200心态逐渐崩溃QAQ
中间服务器恢复了，立刻把存好的两道题交上去，全是1A。信心++。G题也码完了进入调试阶段。然而调试过程中突然发现求LCA重构树的过程有Bug，我不可能在\frac{n}{d}*logn的时间内重构树，而且手边没有现成的方法来做这个过程，时间复杂度从O(n*(logn)^2)跳到O(玄学)。。。望着200行的代码心灰意冷。。。
这个时候发现时间只剩一个半小时了，想了想可以去F题碰碰运气。找规律，打了一个从1到7的表，提交，WA，一气呵成。。。看来这道题确实是有正经解法的。。。犹豫了一下觉得自己不适合计算几何的题目，还是掉头去想G题了，毕竟自认为比较擅长树上的问题。剩下的时间在G题上一点点磨了过去，手边的零食越来越少，思绪越来越乱，到最后20min的时候开始一阵阵犯困，基本上无法正常思考了，长时间的脑力劳动已经到了极限。慢慢撑到比赛结束，瞥了一眼总榜，前14名全是外校的，里面还有4个高中生。。。最后总排名29，校排名第8，貌似能拿个二等奖吧。多亏了手速比较快，以及在F题胡乱提交WA之后没敢再交题，罚时上很沾光。
考完后和出题人交流，G题其实是一个裸的虚树问题，F的构造也很简单，先点一个点，画一个圆，圆上两点的中垂线都过圆心。考虑到等边三角形和菱形是符合题意的，那么每次按这种方式往圆上放点就可以了。要是想到了F就是一等奖了QAQ。最后拿着(大家基本都有的)三个气球结束了校赛之旅。
整场比赛的区分度很不好，一直到80多名都是三道题起步，最高的只做开了5道题，很多题根本就没人去交。但是一些题目的思维强度还是不错的(比如F)。初赛+决赛下来感觉ACM更偏向于思维能力，出题方式和CF比较接近。
题目代码
A
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x,Ans,i,j,k;
int t[1100],f[1100];
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) scanf("%d",&t[i]);
for (i=1;i<=n;i++){
scanf("%d",&k);
for (j=1;j<=k;j++){
scanf("%d",&x); f[x]=1;
}
}
for (i=1;i<=m;i++){
if (!f[i]) continue;
Ans+=t[i];
}
printf("%d\n",Ans);
return 0;
}
C
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 10000010
#define LL long long
using namespace std;
int n,m,l,u,r,i,T,Ans;
int a[N];
LL f[N];
struct RNG {
int u, l, r;
};
inline int Max(int a,int b){return(a>b)?a:b;}
int RNGNextInt ( struct RNG *r) {
r->u ^= (r->u >> 3) & 0x7fffffff ;
r->u ^= (r->u << 5) & 0x7fffffff ;
r->u ^= (r->u >> 1) & 0x7fffffff ;
return (r->u % (r->r - r->l + 1) ) + r->l;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d%d%d%d%d",&n,&m,&u,&l,&r);
Ans=0; memset(f,0,sizeof(f));
struct RNG rng = {.u = u , .l = l , .r = r};
for (i=1;i<=n;i++) a[i]=RNGNextInt (& rng);
if (m<=0){
for (i=1;i<=n;i++)
if (a[i]>m) Ans++;
printf("%d\n",Ans); continue;
}
f[0]=0;
for (i=1;i<=n;i++){
f[i]=Max(f[i],f[i-1]+a[i]);
if (f[i]>m) Ans++,f[i]=0;
}
printf("%d\n",Ans);
}
return 0;
}
I
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x,y,t;
inline int gcd(int x,int y){return (y==0)?x:gcd(y,x%y);}
int main(){
scanf("%d",&m);
while (m--){
scanf("%d%d%d",&n,&x,&t);
t=gcd(n,t);
if ((x-1)%t!=0) printf("NO\n");
else printf("YES\n");
}
return 0;
}
