陷入了一种每场比赛打完都不想改题的虚无状态，不能这样，改题改题改题。

昨晚只写了三道题意即题解的题…感觉意识模糊，看了看是unrated就睡了

CF已经连续三场unrated了qwq，我一共就没打过几场

A. Diplomas and Certificates

题意：拿到

certificate的人数将会是拿到diploma人数的k倍，但拿到他们的总人数不能超过n/2

把n/2向下取底分成k+1分

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long LL;LL n,k;int main(){    scanf("%I64d%I64d",&n,&k);    LL t1=n/2/(k+1),t2=t1*k;    printf("%I64d %I64d %I64d\n",t1,t2,n-t1-t2);    return 0;}
        
       
      
     

B. Permutation Game

题意：给出一个排列a

₁...a

_n，进行m轮游戏，首先选定一个leader作为l[1]，l[i+1]=a[l[i]]+l[i]

a[l[i]]+l[i]=l[i+1] 所以 a[l[i]]=l[i+1]-l[i]

如果遇到有冲突的情况特判一下输出-1（一个以上的位置是同一个数或同一个位置几次得到的结果不一样）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,m,l[105],a[105];int num[105];vector
           
            v;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&l[i]); for(int i=1;i
            
             1){printf("-1\n");return 0;} else if(!num[i])v.push_back(i); for(int i=1;i<=n;i++) { if(!a[i])a[i]=v.back(),v.pop_back(); printf("%d ",a[i]); } return 0;}
            
           
          
         
        
       
      

C. Sofa Thief

题意：有d个沙发，每个沙发占据相邻两个格子，定义一个沙发A在另一个沙发B左边为：存在沙发A的格子a和沙发B的格子b使得x

_a<x

_b，求出一个沙发满足给出的cnt

_l,cnt

_r,cnt

_t,cnt

_b

m和n都不超过1e5，直接处理出前缀和，O(n)可求

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;struct data{    int x1,y1,x2,y2;}sofa[100005];int d,n,m,cntl,cntr,cntt,cntb,xl[100005],yl[100005],xr[100005],yr[100005];int main(){    scanf("%d%d%d",&d,&n,&m);    for(int i=1;i<=d;i++)    {            scanf("%d%d%d%d",&sofa[i].x1,&sofa[i].y1,&sofa[i].x2,&sofa[i].y2);        xl[min(sofa[i].x1,sofa[i].x2)]++;        yl[min(sofa[i].y1,sofa[i].y2)]++;        xr[max(sofa[i].x1,sofa[i].x2)]++;        yr[max(sofa[i].y1,sofa[i].y2)]++;    }    scanf("%d%d%d%d",&cntl,&cntr,&cntt,&cntb);    for(int i=1;i<=n;i++)xl[i]+=xl[i-1];    for(int i=1;i<=m;i++)yl[i]+=yl[i-1];    for(int i=n;i;i--)xr[i]+=xr[i+1];    for(int i=m;i;i--)yr[i]+=yr[i+1];     for(int i=1;i<=d;i++)    {        int l=xl[max(sofa[i].x1,sofa[i].x2)-1];        int r=xr[min(sofa[i].x1,sofa[i].x2)+1];        if(sofa[i].x1!=sofa[i].x2)l--,r--;        int t=yl[max(sofa[i].y1,sofa[i].y2)-1];        int b=yr[min(sofa[i].y1,sofa[i].y2)+1];        if(sofa[i].y1!=sofa[i].y2)t--,b--;        if(l==cntl&&r==cntr&&t==cntt&&b==cntb)        {printf("%d\n",i);return 0;}    }    printf("-1\n");    return 0;}
            
           
          
         
        

D. Multicolored Cars

题意：有n辆车依次驶过，给定对方选择的一个颜色a，请你选择一个颜色b使得在任一时刻cnt

_b>=cnt

_a

感觉也没什么好说的，线性扫一遍即可，细节的话还是看代码

(Update:发现被hack了，因为答案不能超出1000000…已改。)

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int n,a,b,num[1000005],x[1000005];bool f[1000005];int main(){    scanf("%d%d",&n,&a);    for(int i=1;i<=n;i++)    {        scanf("%d",&x[i]);        if(a!=x[i]&&num[x[i]]
           
          
         
        
       

E. Card Game Again

题意：有多少连续的a

_i...a

_j的乘积是k的倍数

将k分解质因数，处理出序列每个质因数个数的前缀和，对于每个左端点通过二分来得到最小的能使乘积为k的倍数的右端点

#include
        
         #include
         
          #include
          
           #include
           
            typedef long long LL;using namespace std;LL n,k,a[100005],cnt=0,num[50],sum[50][100005],res=0;LL read(){    LL x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
      if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}bool check(int x,int y){    for(int i=1;i<=cnt;i++)    if(x!=1&&sum[i][y]-sum[i][x-1]
            
             1)num[++cnt]=t,sum[cnt][0]++;    for(int i=1;i<=n;i++)    {        a[i]=read();        int t=a[i];        for(int j=1;j<=cnt;j++)        {            if(t%num[j]==0)            {                while(t%num[j]==0)                t/=num[j],sum[j][i]++;            }        }    }    for(int i=1;i<=cnt;i++)    for(int j=1;j<=n;j++)    if(j!=1)sum[i][j]+=sum[i][j-1];    for(int i=1;i<=n;i++)    {        int l=i,r=n,ans=-1;        while(l<=r)        {            int mid=(l+r)>>1;            if(check(i,mid))r=mid-1,ans=mid;            else l=mid+1;        }        if(ans!=-1)res+=n-ans+1;    }    printf("%I64d\n",res);    return 0;}
            
           
          
         
        

F. Level Generation

题意：n个点的图，桥的个数要求不小于边数的一半，问边数的最大值

n个点中k个点两两相连有k*(k-1)/2条边，其余的点顺次相连为桥n-k条边，当k*(k-1)/2<=n-k时才符合要求

可以发现f(k)=n-k+min(n-k,k*(k-1)/2)是一个单峰函数，于是三分得到答案

#include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long LL;LL q,n,ans;LL check(LL x){    if(x*(x-1)/2<=n-x){ans=max(ans,x*(x-1)/2+n-x);return x*(x-1)/2+n-x;}    ans=max(ans,(n-x)*2);return (n-x)*2;}int main(){    scanf("%I64d",&q);    for(int i=1;i<=q;i++)    {        scanf("%I64d",&n);        LL l=1,r=n;        ans=n-1;        while(l+2
             
            
           
          

G. Four Melodies

题意：给出序列a

₁...a

_n，找出四个不可重复的子序列使得子序列里相邻元素相差1或在模7意义下相等，最大化这四个子序列的长度和

费用流。拆点建图还是比较容易的，然而边太多了需要优化…

发现只需要找出4个子序列，所以模数相同时最多只需要向后连最近的4条边即可，对结果不会有影响

#include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define INF 0x3f3f3f3fusing namespace std;int n,ss,s,t,a[6005],head[6005],cnt=0,vis[100005],f[6005],dis[6005],pre[6005];bool inq[6005];struct Node{    int next,to,cap,w;}Edges[10000005];int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}void addedge(int u,int v,int c,int w){    Edges[cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v;    Edges[cnt].cap=c;    Edges[cnt++].w=w;}void insert(int u,int v,int c,int w){    addedge(u,v,c,w);    addedge(v,u,0,-w);}queue
                
                 q;int MCMF(){ int flow=0,cost=0; while(1) { memset(dis,-1,sizeof(dis)); q.push(ss); inq[ss]=1,dis[ss]=0,f[ss]=INF,pre[ss]=-1; while(!q.empty()) { int u=q.front(); q.pop(),inq[u]=0; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(dis[v]
                 
                  0) { dis[v]=dis[u]+Edges[i].w; f[v]=min(f[u],Edges[i].cap); pre[v]=i; if(!inq[v])inq[v]=1,q.push(v); } } } if(dis[t]==-1)break; flow+=f[t]; cost+=dis[t]*f[t]; int p=t; while(pre[p]!=-1) { Edges[pre[p]].cap-=f[t]; Edges[pre[p]^1].cap+=f[t]; p=Edges[pre[p]^1].to; } } return cost;}int main(){ memset(head,-1,sizeof(head)); n=read(),ss=2*n+2,s=0,t=2*n+1; insert(ss,s,4,0); for(int i=1;i<=n;i++) { a[i]=read(),insert(i,i+n,1,1); insert(s,i,1,0),insert(i+n,t,1,0); } for(int i=1;i<=n;i++) { int have=0; for(int j=i+1;j<=n;j++) { if(abs(a[i]-a[j])==1&&vis[a[j]]!=i) insert(i+n,j,1,0),vis[a[j]]=i; else if(have<4&&vis[a[j]]!=i&&a[i]%7==a[j]%7) insert(i+n,j,1,0),have++,vis[a[j]]!=i; } } printf("%d\n",MCMF()); return 0;}