首页 > 代码库 > 【63测试20161111】【BFS】【DP】【字符串】
【63测试20161111】【BFS】【DP】【字符串】
第一题： tractor
题目描述
农场上有N(1 <= N <= 50,000)堆草，放在不同的地点上。FJ有一辆拖拉机，也在农场上。拖拉机和草堆都表示为二维平面上的整数坐标，坐标值在1..1000的范围内。拖拉机的初始位置与所有草堆不同。
FJ开拖拉机时，只能平行于坐标轴（即东、南、西、北四个方向），而且每次开动的一段必须是整数长度。
例如，他可以向北开2个单位长度，然后向东开3个单位长度。拖拉机不能开到草堆的位置。
请帮助FJ计算出最少要移动多少个草堆，他才能将拖拉机开回坐标原点。
拖拉机可以开到1..1000之外的地方去。
输入
第1行: 3个整数，即N 和拖拉机的初始位置 (x,y)
第2..1+N行: 每行2个整数，表示一堆草的位置 (x,y)
输出
第1行: FJ必须移动的最少的草堆的数量
样例输入
7 6 3
6 2
5 2
4 3
2 1
7 3
5 4
6 4
样例输出
1
这道题：可以用BFS,DFS,SPFA，我选择了BFS。但是，我居然把BFS 的模板写错了。于是就死循环 了。就是vis数组的位置，一定要注意。然后剪枝很重要，我基本上能用到最优的剪枝：if (now.w>=ans) continue;
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define maxn 1005 7 using namespace std; 8 const int zl[2][4]={{0,0,1,-1},{1,-1,0,0}}; 9 int n,xi,yi,ans=12345678;10 bool mp[maxn][maxn],vis[maxn][maxn];11 struct pp{12 int x,y;13 int w;14 };15 pp s;16 queue < pp > q;17 void bfs(int stx,int sty)18 {19 s.x=stx;20 s.y=sty;21 s.w=0;22 vis[stx][sty]=true;//vis 的位置，bfs 模板....未掌握 23 q.push(s);24 while (!q.empty())25 {26 pp cur=q.front();27 //vis[cur.x][cur.y]=true;//注意在哪里加vis 28 q.pop();29 for (int i=0;i<=3;i++)30 { 31 int a=cur.x+zl[0][i],b=cur.y+zl[1][i];32 if (vis[a][b]) continue;//否则死循环 33 pp now;34 now.x=a;now.y=b;now.w=cur.w;35 if (a<1||b<1||a>1000||b>1000){//到边界随便走 36 if (cur.w<ans) ans=cur.w;37 continue;38 }39 if (a==0&&b==0){//到原点40 if (mp[a][b]) cur.w++; 41 if (cur.w<ans) ans=cur.w;42 continue;43 }44 if (mp[a][b]) now.w++;45 if (now.w>=ans) continue;//剪枝46 vis[a][b]=true; //********47 q.push(now);48 }49 }50 }51 int main()52 {53 freopen("tractor.in","r",stdin);54 freopen("tractor.out","w",stdout);55 cin>>n>>xi>>yi;56 for (int i=1;i<=n;i++)57 {58 int x,y;59 scanf("%d%d",&x,&y);60 mp[x][y]=true;61 }62 bfs(xi,yi);63 printf("%d",ans);64 return 0;65 }
第二题：Landscaping
题目描述
N(1 <= N <= 100)个数排成一行，值分别为A_i，现在希望把每个数对应地改成B_i。(A_i,B_i的值均在0..10之间)。改变的方式有3种：
(1)把A_i增加到B_i，每增加1，花费$X
(2)把A_i减少到B_i，每减少1，花费$Y
(3)把第i个数的值转移到第j个数，每转移1，花费为$Z*|i-j|
问：最小的花费是多少。
输入
第1行：4个整数 N, X, Y, Z (0 <= X, Y, Z <= 1000).
第2..1+N行: 每行2个整数 A_i 和 B_i.
输出
第1行：1个整数，表示最小的花费。
样例输入
4 100 200 1
1 4
2 3
3 2
4 0
样例输出
210
解：
考试的时候用的贪心，过了50分剩下的T了，好像大家感到很惊讶。这个贪心，有点神奇。记录最近的方向（即是需要+，还是-）相同和方向相反的点，方向相同的是方便传递。然后转移最近的。最后剩的就是自己+，-了。
然后这道题是一道DP题。类似于均分纸牌。f[i][j]表示前 i 个数交换 j 个1 的最小花费。
具体的解释在代码里了。这道DP的思想很重要。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 105 6 using namespace std; 7 int n,x,y,z,base=1000,v; 8 int cha[maxn],dp[maxn][2005]; 9 int main()10 {11 freopen("landscaping.in","r",stdin);12 freopen("landscaping.out","w",stdout);13 cin>>n>>x>>y>>z;14 for (int i=1;i<=n;i++)15 {16 int a,b;17 scanf("%d%d",&a,&b);18 cha[i]=b-a;//need how much:b-a not a-b19 v+=abs(cha[i]);//abs20 }21 memset(dp,0x3f,sizeof(dp));//赋初值 22 dp[0][base]=0;23 for (int i=0;i<n;i++)24 {25 for (int j=-v;j<=v;j++)//所有状态 26 dp[i+1][base+j+cha[i+1]]=min(dp[i+1][base+j+cha[i+1]],dp[i][base+j]+z*abs(j));//abs(j)27 //前i个人需要j个，所以用i+1给i j个，i+1就需要 j+cha[i+1]个 28 //从最后一个人考虑，则刚好前n-1 个人需要的j个 与cha[n]抵消，(类似于均分纸牌) 29 if (cha[i+1]>0){//自己加 30 for (int j=v;j>=1;j--)31 dp[i+1][base+j-1]=min(dp[i+1][base+j-1],dp[i+1][base+j]+x);32 }33 else {//自己减 34 for (int j=-v;j<=-1;j++)35 dp[i+1][base+j+1]=min(dp[i+1][base+j+1],dp[i+1][base+j]+y);36 }37 }38 printf("%d",dp[n][base]);39 return 0;40 }
第三题“：equal
【问题描述】
明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？
这个选择题中的每个表达式都满足下面的性质：
1． 表达式只可能包含一个变量‘a’。
2． 表达式中出现的数都是正整数，而且都小于10000。
3． 表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后 是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）
4． 幂指数只可能是1到10之间的正整数（包括1和10）。
5． 表达式内部，头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子：
((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9……
这道题是noip的某第三道题。由于把多项式展开太复杂，所以我们用类似于多项式计算的方式，把a替代为一个很大的素数，并且计算时mod上一个素数，然后看选项计算的值是否与第一个表达式相同。
表达式的计算，这个模板还需要练。乘方的优先级是最高的需要注意它的判断。乘方用快速幂写。
还有读入：因为要舍去空格，所以建议一个一个的读入。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<map> 6 #define maxn 55 7 #define ll long long 8 using namespace std; 9 const ll P[]={10003,10007,56971},Q[]={2,73217,33233}; 10 int n; 11 ll ans[5]; 12 char s[maxn],symbol[maxn]; 13 ll num[maxn]; 14 int topn,topf; 15 void read_string() 16 { 17 int l=0; 18 char c=getchar(); 19 while (c==‘ ‘||c==‘\n‘) c=getchar(); 20 while (c!=‘\n‘&&c!=EOF) 21 { 22 if (c!=‘ ‘) s[++l]=c; 23 c=getchar(); 24 } 25 s[0]=‘(‘;s[++l]=‘)‘; 26 } 27 ll ksm(ll a,ll b,ll modd) 28 { 29 ll t=1,tmp=a; 30 while (b>0) 31 { 32 if (b%2) t=(tmp*t)%modd; 33 b=b>>1; 34 tmp=(tmp*tmp)%modd; 35 } 36 return t; 37 } 38 void pop(ll modd) 39 { 40 switch(symbol[topf]) 41 { 42 case‘+‘:num[topn-1]=(num[topn]+num[topn-1])%modd;topn--;break; 43 case‘-‘:num[topn-1]=((num[topn-1]-num[topn])%modd+modd)%modd;topn--;break; 44 case‘*‘:num[topn-1]=(num[topn-1]*num[topn])%modd;topn--;break; 45 case‘^‘:num[topn-1]=ksm(num[topn-1],num[topn],modd)%modd;topn--;break; 46 } 47 topf--; 48 } 49 bool pd(int i) 50 { 51 if ((s[i]==‘+‘||s[i]==‘-‘)&&symbol[topf]!=‘(‘) return true; 52 if (symbol[topf]==‘^‘) return true;//^的优先级最高 53 if ((s[i]==‘*‘&&symbol[topf]==‘*‘)) return true; 54 return false; 55 } 56 ll js(int tt) 57 { 58 int i=0,len=strlen(s); 59 while (i<len) 60 { 61 while (s[i]==‘(‘) { 62 symbol[++topf]=s[i]; 63 i++; 64 } 65 ll x=0; 66 if (s[i]==‘a‘){ 67 x=Q[tt];i++; 68 } 69 else { 70 while (s[i]>=‘0‘&&s[i]<=‘9‘) 71 x=x*10+s[i++]-‘0‘; 72 } 73 num[++topn]=x; 74 do{ 75 if (s[i]==‘)‘){ 76 while (symbol[topf]!=‘(‘) pop(P[tt]); 77 topf--;//删括号 ******* 78 } 79 else{ 80 while (pd(i)) pop(P[tt]); 81 symbol[++topf]=s[i]; 82 } 83 i++; 84 }while (i<strlen(s)&&s[i-1]==‘)‘); 85 } 86 return num[1]; 87 } 88 int main() 89 { 90 freopen("equal.in","r",stdin); 91 freopen("equal.out","w",stdout); 92 read_string();//gets 的使用 93 for (int i=0;i<=2;i++) 94 { 95 memset(symbol,0,sizeof(symbol)); 96 memset(num,0,sizeof(num)); 97 topn=0;topf=0; 98 ans[i]=js(i); 99 }100 cin>>n;101 getchar();//getchar102 for (int i=1;i<=n;i++)103 {104 memset(s,0,sizeof(s));105 read_string();106 bool b=false;107 for (int j=0;j<=2;j++)108 {109 memset(symbol,0,sizeof(symbol));110 memset(num,0,sizeof(num));111 topn=0;topf=0;112 ll cur=js(j);113 if (cur!=ans[j]) {114 b=true;115 break; 116 }117 }118 if (b) continue;119 char oo=‘A‘+i-1;120 printf("%c",oo);121 }122 return 0;123 }
【63测试20161111】【BFS】【DP】【字符串】