*五道题眼镜都花了
T1：
【题意】给定一个字符串，删除后缀的ly,er,ing一次
【题解】。。。
T2
【题意】给定1g,2g,3g,5g,10g,20g的砝码若干个，总重量<=10^5，求能称出多少质量
【题解】。。。
T2
【题意】
【题解】
60分n^4暴力dp：
#define mod 1000000007 int n,m,k,map[777][777],f[777][777]; int main(){ FO(hopscotch); n=gi;m=gi;k=gi;FOR1(i,n)FOR1(j,m)map[i][j]=gi; f[1][1]=1; FOR1(i,n){ FOR1(j,m){ // printf("(%d,%d):",i,j); FOR0(l,i)FOR0(r,j)if(map[l][r]!=map[i][j]){ // if(l&&r)printf("(%d,%d) ",l,r); f[i][j]=(f[i][j]+f[l][r])%mod; } // puts(""); } } // FOR1(i,n){// // FOR1(j,m){ // printf("%d ",f[i][j]); // }puts(""); // } printf("%d",f[n][m]); return 0; }
正解
czyz的机房的格局，是和别处不同的….孔乙己显出极高兴的样子，将两个指头的长指甲敲着柜台，点头说，“对呀对呀！……这题有三样写法，你知道么？”
首先很显然二维线段树，动态的开点是可以做的
那么用平衡树维护也是可以得
正解其实是cdq分治，但是我不会cdq分治
T4
【题意】
给定一颗都是字母的树，问是否存在一条链等于给定字符串
【题解】
数据范围非常的有趣，考虑一个枚举起点bfs的暴力。分类讨论一下
对于 20% 的数据，N ≤ 1000。
对于另外 20% 的数据，N ≤ 10^4 ，且树上有且仅有一种字母。
期望复杂度O(n)
对于另外 30% 的数据，N ≤ 10^4 ，且树随机生成。
期望复杂度O(nlogn)
对于另外 30% 的数据，N ≤ 10^4 ，且树上的字母随机生成。
期望复杂度O(n^2/26/2)
然而其实最后这个挺虚的，所以我们看起点和终点的个数，哪个少从哪个开始bfs
然后就过了
struct edge{ int to,next; }e[23333];int cnt,last[10005]; char ch[10005],tgt[10005];int f[10005][20],dep[10005]; void link(int a,int b){ e[++cnt]=(edge){b,last[a]};last[a]=cnt; e[++cnt]=(edge){a,last[b]};last[b]=cnt; } struct data{ int a,fa,d; }; int n,m,_ds,_es,ds[10001],es[10001]; bool bfs(int s){ queue<data>q; q.push((data){s,-1,1}); while(!q.empty()){ data c=q.front();q.pop(); for(int i=last[c.a];i;i=e[i].next){ if(e[i].to!=c.fa){ // printf("from %d to %d ",c.a,e[i].to); if(ch[e[i].to]==tgt[c.d+1]){ q.push((data){e[i].to,c.a,c.d+1}); // dep[e[i].to]=dep[c.first]+1; if(c.d+1==m)return true; } } } } return false; } bool diff(char str[]){ int t=strlen(str+1); FOR1(i,t)if(i^1&&str[i]^str[i-1])return true; return false; } void bfs1(){ } void luangao(){ } int main(){ FO(alphabet); int T=gi; FOR1(_,T){ int n=gi;bool flag=false; memset(last,0,sizeof(last));cnt=0; FOR1(i,n-1){ int u,v;u=gi;v=gi; link(u,v); } // bfs(1); scanf("%s",ch+1); scanf("%s",tgt+1); n=strlen(ch+1),m=strlen(tgt+1); _ds=0;_es=0; // if(diff(tgt)){ FOR1(i,n){ if(ch[i]==tgt[1])ds[++_ds]=i; if(ch[i]==tgt[m])es[++_es]=i; } if(_ds<=_es){ FOR1(l,_ds){ // cout<<ds[l]<<endl; if(bfs(ds[l])){ flag=true; break; } } } else{ FOR1(i,m/2)swap(tgt[i],tgt[m-i+1]); FOR1(i,_es) // cout<<ds[l]<<endl; if(bfs(es[i])){ flag=true; break; } } printf("Case #%d: %s ",_,flag?"Find":"Impossible"); // puts("-------------"); // }else{ // luangao(); // . } } return 0; }
那两个空的函数啊。。是本来特判所有字符都一样的数据，不知道怎么没了
T5
【题意】给定一个n*m的非负矩阵，求左上角到右下角路径上值得方差*（n+m-1)最小
【题解】
考虑一个dp,表示(1,1)到(i,j)平均值为k最小的方差，然后挺好的转移的
但是空间不够优秀。
我们考虑要最小化的是这个式子
那么首先可以发现S是平均值的时候最小。
展开他
如果*（n+m-1)，可以枚举最后一项，dp前两项
然后就可以求出答案了
为什么可以枚举和呢？因为非法的和的答案不会比恰好是的小
int n,m,a[33][33],f[33][33],ans=0x7fffffff; int main(){ FO(route); n=gi;m=gi; FOR1(i,n)FOR1(j,m)a[i][j]=gi; FOR0(sum,(n+m-1)*30+1){ memset(f,0,sizeof(f)); FOR1(i,n)FOR1(j,m){ if(i==1)f[i][j]=f[i][j-1]; else if(j==1)f[i][j]=f[i-1][j]; else f[i][j]=min(f[i][j-1],f[i-1][j]); int x=a[i][j]; f[i][j]+=x*x*(n+m-1)-x*sum*2; } ans=min(ans,f[n][m]+sum*sum); } cout<<ans; return 0; }