solve 4 （A B E H）
rank 15/32
比赛链接：http://acm.csu.edu.cn:22080/cpcsys/contest/problemset?cid=1023
A题Sim Card：（通过）
签到题，且没什么可写的。
B题Bank Card Verifier：（通过）
签到题，跟着题目要求写就行了。
C题Border Wall：
E题Barareh on Fire：（通过）
题意：火焰每k秒蔓延一次，能否从s点最快走到t点。
思路：
直接搜索，主要是每k秒更新一下新地图便可。
可以直接预处理新地图，要省空间的话可以中途更新。
其余的就是普通的bfs过程了。
搜索题中比较考验码力的题，代码如下：
#include <cstdio> #include <algorithm> #include <queue> #include <iostream> using namespace std; struct node { int x,y; int step; node(int x=0,int y=0,int step=0):x(x),y(y),step(step) {} }; int mp[110][110][110],n,m,k; char ch[110]; int bfs(int x,int y,int sx,int sy) { int vis[110][110]= {}; queue<node> q; while(!q.empty()) q.pop(); q.push(node(x,y,0)); vis[x][y]=1; while(!q.empty()) { node nod = q.front(); if(nod.x==sx&&nod.y==sy) return nod.step; q.pop(); if(nod.x>0&&!vis[nod.x-1][nod.y]&&mp[(nod.step+1)/k][nod.x-1][nod.y]) { vis[nod.x-1][nod.y]=1; q.push(node(nod.x-1,nod.y,nod.step+1)); } if(nod.x<n-1&&!vis[nod.x+1][nod.y]&&mp[(nod.step+1)/k][nod.x+1][nod.y]) { vis[nod.x+1][nod.y]=1; q.push(node(nod.x+1,nod.y,nod.step+1)); } if(nod.y>0&&!vis[nod.x][nod.y-1]&&mp[(nod.step+1)/k][nod.x][nod.y-1]) { vis[nod.x][nod.y-1]=1; q.push(node(nod.x,nod.y-1,nod.step+1)); } if(nod.y<m-1&&!vis[nod.x][nod.y+1]&&mp[(nod.step+1)/k][nod.x][nod.y+1]) { vis[nod.x][nod.y+1]=1; q.push(node(nod.x,nod.y+1,nod.step+1)); } } return -1; } int main() { int flag=1; while(scanf("%d %d %d",&n,&m,&k)) { if(!n&&!m&&!k) break; int x,y,sx,sy; for(int i=0; i<n; i++) { scanf("%s",ch); for(int j=0; j<m; j++) { if(ch[j]=='s') { mp[0][i][j]=1; x=i; y=j; } else if(ch[j]=='t') { mp[0][i][j]=1; sx=i; sy=j; } else if(ch[j]=='f') { mp[0][i][j]=0; } else if(ch[j]=='-') { mp[0][i][j]=1; } } } for(int p=1; p<max(n,m); p++) { for(int i=0; i<n; i++) { for(int j=0;j<m;j++) { mp[p][i][j]=1; if(i>0&&j>0&&!mp[p-1][i-1][j-1]) mp[p][i][j]=0; if(i>0&&!mp[p-1][i-1][j]) mp[p][i][j]=0; if(j>0&&!mp[p-1][i][j-1]) mp[p][i][j]=0; if(i>0&&j<m-1&&!mp[p-1][i-1][j+1]) mp[p][i][j]=0; if(i<n-1&&j>0&&!mp[p-1][i+1][j-1]) mp[p][i][j]=0; if(i<n-1&&!mp[p-1][i+1][j]) mp[p][i][j]=0; if(j<m-1&&!mp[p-1][i][j+1]) mp[p][i][j]=0; if(i<n-1&&j<m-1&&!mp[p-1][i+1][j+1]) mp[p][i][j]=0; } } } int ans=bfs(x,y,sx,sy); if(ans==-1) printf("Impossible\n"); else printf("%d\n",ans); } return 0; } /********************************************************************** Problem: 1263 User: multi2018team024 Language: C++ Result: AC Time:164 ms Memory:7228 kb **********************************************************************/
H题Column Addition：（通过）
题意：给长度为n的加法计算式a+b=c，问最少删除多少列使得式子正确。
思路：
<错误的贪心策略（虽然不知道哪里错了）>
对于第pos位，如果(a[pos] + b[pos])%10==c[pos] 或者 (a[pos] + b[pos] +1)%10==c[pos]
pos位有可能留下，其余的一定要删掉（易证）。
那么把必须删掉的提前处理完，从而达到剪枝的目的。
<但是其实不需要贪心处理就可以ac这题>
<一个正确的策略>
由于数字最长只有1000位，我们不妨设dp[pos]，表示第pos位合法时，能够得到的最长的合法序列有多长。
（1）对于所有的pos：
if((a[pos]+b[pos])%10==c[pos]) dp[pos]=1;
（2）对于第pos位，能否跟第pos+x位连接起来的条件是：
int jinwei=(dp[pos+x])&&(a[pos+x]+b[pos+x]>c[pos+x]); if((a[pos]+b[pos]+jinwei)%10==c[pos]) dp[pos]=max(dp[pos],dp[pos+x]+1);
注意这里的变量 jinwei ，满足进位的条件当且仅当第pos+x位的a + b > c并且dp[pos+x]有值（如5+8=1这种式子是非法的，所以可以直接忽略掉，前面的贪心策略有处理掉这种非法式子）。
（3）如果第pos位本位不进位，那么这一位可以作为新式子的最高位，所以答案可以这样更新：
if((a[i]+b[i]<=c[i]))ans=min(ans,n-dp[i]);
最后贴上dzc巨巨的ac代码：
#include <cstdio> #include <algorithm> #include <queue> #include <iostream> #include <cstring> using namespace std; int n,ans=0; string s1,s2,s3; int a[1010],b[1010],c[1010],dp[1010]; int main() { while(scanf("%d",&n)!=EOF&&n){ ans=n; cin>>s1>>s2>>s3; for(int i=0;i<n;i++) { a[i]=s1[i]-'0'; b[i]=s2[i]-'0'; c[i]=s3[i]-'0'; } memset(dp,0,sizeof(dp)); for(int i=n-1;i>=0;i--) { if((a[i]+b[i])%10==c[i]) dp[i]=1; for(int j=i+1;j<n;j++) { int jinwei=(dp[j])&&(a[j]+b[j]>c[j]); if((a[i]+b[i]+jinwei)%10==c[i]) dp[i]=max(dp[i],dp[j]+1); } } for(int i=0;i<n;i++) { if((a[i]+b[i]<=c[i]))ans=min(ans,n-dp[i]); } printf("%d\n",ans); } return 0; } /********************************************************************** Problem: 1266 User: multi2018team024 Language: C++ Result: AC Time:160 ms Memory:2040 kb **********************************************************************/
I题Cafe Bazaar：
K题Mars：