初赛

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;
}

说点什么
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...