T1:https://gmoj.net/senior/#main/show/6793
T2:https://gmoj.net/senior/#main/show/6794
这道题考场上只要稍稍懂点脑筋就能想到
只要把一般的最长不下降子序列dp改为二维的就好了,没什么难度
(最让我崩溃的是考场上文件输入输出打错了......)
重拼3遍:
missile!
missile!
missile!
#include<cstdio> #include<algorithm> #include<cctype> #define N 500010 using namespace std; int f[51][21],a[51],n,m,ans; inline char gc() { static char buf[N],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x) { char ch=0;x=0;int f=0; while (!isdigit(ch)) ch=gc(),f^=ch=='-'; while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc(); f&&(x=-x); } inline void write(int x) { if (x<0) putchar('-'),x=-x; if (x>9) write(x/10); putchar(x%10+48); } int main() { freopen("missile.in","r",stdin); freopen("missile.out","w",stdout); read(m),read(n); for (int i=1;i<=n;i++) read(a[i]); for (int i=1;i<=n;i++) { for (int j=0;j<=m;j++) f[i][j]=1; for (int j=1;j<=i-1;j++) { if (a[j]>=a[i]) { for (int k=0;k<=m;k++) f[i][k]=max(f[i][k],f[j][k]+1),ans=max(ans,f[i][k]); } else { for (int k=1;k<=m;k++) f[i][k-1]=max(f[i][k],f[j][k]+1),ans=max(ans,f[i][k-1]); } } } write(ans); return 0; }
T3:https://gmoj.net/senior/#main/show/6795
注意题目要求的是一条链,而不是一个连通块
在深搜的同时更新答案就好了
#include<cstdio> using namespace std; int p[31][31],fx[9][3],a[31][31],n,m,x,s,ans1,ans2; char ss[31]; inline void write(int x) { if (x<0) putchar('-'),x=-x; if (x>9) write(x/10); putchar(x%10+48); } inline void clear(int lsb,int wzh) { if (s>ans2) ans1=x,ans2=s; else if (s==ans2&&ans1>x) ans1=x; for (int i=1;i<=8;i++) { int bb=lsb+fx[i][1],jj=wzh+fx[i][2]; if (bb>0&&bb<=n&&jj>0&&jj<=m&&a[bb][jj]==a[lsb][wzh]&&!p[bb][jj]) { p[bb][jj]=1,s++; clear(bb,jj); p[bb][jj]=0,s--; } } } int main() { freopen("clear.in","r",stdin); freopen("clear.out","w",stdout); scanf("%d%d",&n,&m),fx[1][1]=1,fx[2][1]=-1,fx[3][2]=1,fx[4][2]=-1,fx[5][1]=-1,fx[5][2]=-1,fx[6][1]=-1,fx[6][2]=1,fx[7][1]=1,fx[7][2]=-1,fx[8][1]=1,fx[8][2]=1; for (int i=1;i<=n;i++) { scanf("%s",ss+1); for (int j=1;j<=m;j++) a[i][j]=ss[j]-'0'; } for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { if (p[i][j]) continue; p[i][j]=s=1,x=a[i][j],clear(i,j),p[i][j]=0; } } write(ans1),putchar(' '),write(ans2); return 0; }
T4:https://gmoj.net/senior/#main/show/6796
设f[i][j]表示第i个字符与第j个字符匹配时的总代价
那么就可以从上一个状态f[k][s]转移而来
易得dp方程式:f[i][j]=min(f[i][j],f[k][s]+abs(a[i]-b[j])+(i-k+j-s-2)*kk)
最后统计答案即可,细节要多注意
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int a[31],b[31],f[31][31],n,m,kk,ans=0x7f7f7f7f; char s1[31],s2[31]; inline void write(int x) { if (x<0) putchar('-'),x=-x; if (x>9) write(x/10); putchar(x%10+48); } int main() { freopen("distance.in","r",stdin); freopen("distance.out","w",stdout); scanf("%s%s%d",s1+1,s2+1,&kk),n=strlen(s1+1),m=strlen(s2+1); for (int i=1;i<=n;i++) a[i]=s1[i]-'a'; for (int i=1;i<=m;i++) b[i]=s2[i]-'a'; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { f[i][j]=abs(a[i]-b[j])+(i+j-2)*kk; for (int k=1;k<=i-1;k++) { for (int s=1;s<=j-1;s++) f[i][j]=min(f[i][j],f[k][s]+abs(a[i]-b[j])+(i-k+j-s-2)*kk); } ans=min(ans,f[i][j]+(n-i+m-j)*kk); } } write(ans); return 0; }
T5:https://gmoj.net/senior/#main/show/3601
总结:
估分:0+60+60+0+0=120
实际:0+0+60+0+0=60
原因已经在上面讲过了(心态大崩*@#¥%……&*)
第一次做B组,作为高一的同学被初一的吊打,我清晰地认识到了自己现在能力的极大不足。离正式比赛也不剩多少天,要珍惜每分每秒,查漏补缺
接下来目标:补学算法,做模板题