上紫啦！

E题1:59压哨提交成功翻盘

（1:00就做完了调了一个小时，还好意思说出来？ （逃））

 

题面太长就不复制了，但是配图很可爱所以要贴过来

九条可怜酱好可爱呀

 

询问从当前时刻过多久，时间会形成回文串的形式。

暴力呀暴力

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 int read(){ 8     int x=0,f=1;char ch=getchar(); 9     while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}10     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}11     return x*f;12 }13 int a,b;14 int test(){15     if(a/10 == b%10 && a%10==b/10)return 1;16     return 0;17 }18 int main(){19     a=read();b=read();20     for(int i=0;i>=0;i++){21         if(test()){22             printf("%d\n",i);23             return 0;24         }25         b++;26         if(b>59)b=0,a++;27         if(a>23)a=0;28     }29     return 0;30 }
          
         
        
       
      

 

 

扫描 前缀和

询问区间内有多少数出现次数超过K次

显然可以差分+前缀和

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int mxn=210005; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}11     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}12     return x*f;13 }14 int smm[mxn];15 int f[mxn];16 int n,K,Q;17 int main(){18     int i,j,a,b;19     n=read();K=read();Q=read();20     for(i=1;i<=n;i++){21         a=read();b=read();22         smm[a]++;23         smm[b+1]--;24     }25     for(i=1;i<=200000;i++){26         f[i]=f[i-1];27         smm[i]+=smm[i-1];28         if(smm[i]>=K)f[i]++;29     }30     while(Q--){31         a=read();b=read();32         int ans=f[b]-f[a-1];33         printf("%d\n",ans);34     }35     return 0;36 }
          
         
        
       
      

 

 

贪心

可以贪心删。如果行更长就先删行再删列，否则先删列再删行。

如果删不光就是无解。

好多人没有判删顺序，全部先删行，hack了四个，233

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int mxn=5000050; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}11     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}12     return x*f;13 }14 int stH[mxn],top1=0,stL[mxn],top2=0;15 int mp[201][201];16 int n,m;17 void getH(){18     int i,j;19     for(i=1;i<=n;i++){20         int tmp=0x3f3f3f3f;21         for(j=1;j<=m;j++){22             tmp=min(tmp,mp[i][j]);23         }24         for(j=1;j<=m;j++){25             mp[i][j]-=tmp;26         }27         while(tmp){28             stH[++top1]=i;tmp--;29         }30     }31     return;32 }33 void getL(){34     int i,j;35     for(i=1;i<=m;i++){36         int tmp=0x3f3f3f3f;37         for(j=1;j<=n;j++){38             tmp=min(tmp,mp[j][i]);39         }40         for(j=1;j<=n;j++){41             mp[j][i]-=tmp;42         }43         while(tmp){44             stL[++top2]=i;tmp--;45         }46     }47     return;48 }49 void check(){50     for(int i=1;i<=n;i++){51         for(int j=1;j<=m;j++){52             if(mp[i][j]>0){53                 printf("-1\n");54                 exit(0);55             }56         }57     }58     return;59 }60 int main(){61     int i,j;62     n=read();m=read();63     for(i=1;i<=n;i++){64         for(j=1;j<=m;j++){65             mp[i][j]=read();66         }67     }68     if(n<=m){69         getH();getL();70     }71     else{72         getL();getH();73     }74     check();75     printf("%d\n",top1+top2);76     while(top1){77         printf("row %d\n",stH[top1--]);78     }79     while(top2){80         printf("col %d\n",stL[top2--]);81     }82     return 0;83 }
          
         
        
       
      

 

数学问题 找规律 组合数

手列一个表看一下，可以发现神奇的规律。

倒数第二行肯定是$k_1*a_1+k_3*a_3+k_5*a_5+..$ 和 $ k_2*a_2 + k_4 * a_4 + k_6 * a_6+..$ 的形式。

k的值和二项式系数有关

如果n%4==2，答案是前者加后者，如果n%4==0，答案是前者减后者，如果n是奇数，就先算一行，把n变成偶数。

 

比赛的时候没做出来，时候补题因为阶乘没加LL，WA得飞起

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define LL long long 7 using namespace std; 8 const int mxn=200010; 9 const int mod=1e9+7;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}13     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}14     return x*f;15 }16 int n;17 int a[mxn];18 int fac[mxn],inv[mxn];19 void init(){20     fac[0]=fac[1]=inv[0]=inv[1]=1;21     for(int i=2;i
           
            >1;50 for(i=1;i<=ed;i++){51 tmp1=((LL)tmp1+(LL)C(ed-1,i-1)*a[i*2-1])%mod;52 tmp2=((LL)tmp2+(LL)C(ed-1,i-1)*a[i*2])%mod;53 }54 // printf("%d %d\n",tmp1,tmp2);55 if(n%4==0)tmp1=((LL)(tmp1-tmp2)%mod+mod)%mod;56 else tmp1=((LL)tmp1+tmp2)%mod;57 printf("%d\n",tmp1);58 return 0;59 }
           
          
         
        
       
      

 

 

动态规划 树形DP

$f[u][j]$表示在u结点，子树中共选了j件物品，有打折商品的最小花费

$g[u][j]$表示在u结点，子树中共选了j件物品，没有打折商品的最小花费

转移的时候，f可以加g，g不能加f，分别计算一下就可以了。

 

不到一个小时的时候就写完了，自信提交发现TLE。

原因是DP的时候，先加上了子树size再O(n^2)转移。

↑然而这样复杂度并不是O(n^2)的，在链数据上会被卡得超慢

　　↑然而一直以为是常数大，尝试了各种优化，提交了一串，无限TLE

　　　　↑在最后十几分钟冷静下来思考，终于察觉到了问题，改成先转移再加子树size，在1:59压哨提交PP

　　　　　　↑真™刺激

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #define LL long long 8 using namespace std; 9 const int mxn=100010;10 const int INF=0x3f3f3f3f;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}14 while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();}15 return x*f;16 }17 struct edge{18 int v,nxt;19 }e[mxn<<1];20 int hd[mxn],mct=0;21 void add_edge(int u,int v){22 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;23 }24 int n,B;25 int w[mxn],c[mxn],fa[mxn],sz[mxn];26 int f[5005][5005];27 int g[5005][5005];28 vector
           
            ve[5005];29 int cmp(int a,int b){30 return sz[a]
            
             =0;j--){47 // int ed=min(sz[v],j);48 if(j>0){49 for(int k=1;k<=sz[v];k++){50 if(f[v][k]>B && g[v][k]>B)break;51 if(f[v][k]<=B)f[u][j+k]=min(f[u][j+k],f[u][j]+f[v][k]);52 if(g[v][k]<=B)f[u][j+k]=min(f[u][j+k],f[u][j]+g[v][k]);53 }54 }55 for(int k=0;k<=sz[v];k++){56 if(g[v][k]>B)break;57 g[u][j+k]=min(g[u][j+k],g[u][j]+g[v][k]);58 }59 // ed=min(sz[v],j-1);60 61 }62 sz[u]+=sz[v];63 }64 return;65 }66 int main(){67 int i,j;68 n=read();B=read();69 for(i=1;i<=n;i++){70 w[i]=read();c[i]=read();71 if(i>1){72 fa[i]=read();73 add_edge(fa[i],i);74 }75 }76 // memset(f,0x3f,sizeof f);77 // memset(g,0x3f,sizeof g);78 DFS(1);79 int mx=0;80 for(i=1;i<=n;i++){81 if(f[1][i]<=B || g[1][i]<=B)mx=i;82 else break;83 }84 printf("%d\n",mx);85 /* for(i=1;i<=sz[1];i++){86 printf("%d %d\n",f[1][i],g[1][i]);87 }*/88 return 0;89 }