“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛数据结构与算法yhyxzywl的博客-

A 张老师和菜哭武的游戏
题目中有描述“当且仅当集合存在y和z，满足x等于y+z或者y-z”
所以考虑y-z，很容易想到辗转相减法，所以最小项是最大公约数
然后题目就迎刃而解了

#include <bits/stdc++.h> using namespace std; int n,a,b; int gcd(int a,int b){ if(a==b)return a; return a>b?gcd(a-b,b):gcd(b-a,a); } int main(){ int t;     cin>>t; while(t--){         cin>>n>>a>>b; int temp=gcd(a,b); int ans=n/temp; if(ans%2==1) printf("Yesn"); else printf("Non"); } return 0; } 

B 伤害计算
看了题解，觉得还是用atoi更加简单；
atoi主要用来将数字字符串转变为对应的整型数字，具体用法网上教程很多；
数学期望的计算公式是用各项权值乘以概率，常数的数学期望就是常数，公式推导还是挺简单的；
注意题目中小数只有.5，所以方便计算，可以将各项结果先乘以2，最后除2，看余数决定是否输出.5；
ps:字符串题目多用函数可以减少很多时间；

#include <bits/stdc++.h> using namespace std; const int MAXL=6000; char strfuc[MAXL]; int ans; void opera(char *str){ char *D=strchr(str,'d'); if(D==NULL){ int c=atoi(str);         ans+=2*c; //cout<<c<<endl; }else{ *D=''; int n=atoi(str); int x=atoi(D+1);         ans+=n*(x+1); //cout<<n<<" "<<x<<endl; } } int main(){ while(cin>>strfuc){         ans=0; char* str=strfuc; while(1){ char* ps=strchr(str,'+'); if(ps==NULL){ opera(str); break; }else{ *ps=''; opera(str);                 str=ps+1; } }         cout<<ans/2; if(ans%2) cout<<".5"<<endl; else cout<<endl; } return 0; } 

C 张老师的旅行
直觉上感觉可以用贪心去做；
结果wa了；
仔细想想还是不行，跟任务分配问题还是有区别的；
这道题dp还是比较难想的；
通俗的讲：
比如你在起点位置，你左边有i个景点，右边有j个景点，问题就是问你浏览完所有景点的最小时间；
首先你不管以什么顺序浏览，你要么最后停在i点，要么最后停在j点；
所以要分两种情况来讨论；
以最后停在i点为例；
这个问题的子问题，比如浏览完左边的i-1个景点，右边的j个景点的最短时间已经求得；
那么对于子问题两种情况的可行解（一种停在i-1点，一种停在j点），你都要回到i点，那么加上对应的路程就可以了（想象你从i-1出发走到i,或从j出发走到i）；
然后问题的解就是两种情况的最小的那一个；
然后ac的代码；

#include <bits/stdc++.h> using namespace std; const int INF=0x3f3f3f; struct point{ int deadline; int coordinate; }; point mp[1100]; point leftpointSet[1100]; point rightpointSet[1100]; int dp[1100][1100][2]; bool cmp(point a,point b){ return a.coordinate<b.coordinate; } int main(){ int n;     cin>>n; int my_coordinate; for(int i=1;i<=n;i++){         cin>>mp[i].coordinate; } for(int i=1;i<=n;i++){         cin>>mp[i].deadline; if(mp[i].deadline==0) my_coordinate=i; } sort(mp+1,mp+1+n,cmp); memset(dp,INF,sizeof(dp));     dp[0][0][1]=0;     dp[0][0][0]=0; int cnt_left=0,cnt_right=0; for(int i=my_coordinate-1;i>0;i--){         cnt_left++;         leftpointSet[cnt_left].coordinate=abs(mp[i].coordinate-mp[my_coordinate].coordinate);         leftpointSet[cnt_left].deadline=mp[i].deadline; } for(int i=my_coordinate+1;i<=n;i++){         cnt_right++;         rightpointSet[cnt_right].coordinate=abs(mp[i].coordinate-mp[my_coordinate].coordinate);         rightpointSet[cnt_right].deadline=mp[i].deadline; } /*     cout<<my_coordinate<<endl;     for(int i=1;i<=cnt_left;i++) cout<<leftpointSet[i].coordinate<<" ";     cout<<endl;     for(int j=1;j<=cnt_right;j++) cout<<rightpointSet[j].coordinate<<" ";     cout<<endl;     */ for(int i=0;i<=cnt_left;i++){ for(int j=0;j<=cnt_right;j++){ if(i){                 dp[i][j][0]=min(dp[i-1][j][0]-leftpointSet[i-1].coordinate+leftpointSet[i].coordinate,dp[i-1][j][1]+rightpointSet[j].coordinate+leftpointSet[i].coordinate); } if(j){                 dp[i][j][1]=min(dp[i][j-1][1]-rightpointSet[j-1].coordinate+rightpointSet[j].coordinate,dp[i][j-1][0]+leftpointSet[i].coordinate+rightpointSet[j].coordinate); } if(dp[i][j][0]>leftpointSet[i].deadline && dp[i][j][1]>rightpointSet[j].deadline){                 cout<<-1<<endl; return 0; } if(dp[i][j][0]>leftpointSet[i].deadline) dp[i][j][0]=INF; if(dp[i][j][1]>rightpointSet[j].deadline) dp[i][j][1]=INF; } }      cout<<min(dp[cnt_left][cnt_right][0],dp[cnt_left][cnt_right][1])<<endl; return 0; } 

D 车辆调度
注意车一次可以走到头，同时不止一辆车，也不止一个终点；
这样就要考虑车不仅会在遇到障碍物的情况下停下，也有可能在遇到车的时候停下，这时候仅仅把车的位置作为bfs时的结点就不行了；
其实这种问题，非常像一种叫华容道的传统游戏；
因为此时你上一步操作会影响下一步操作，这种情况下，一般可以将图作为bfs的结点，这样每一个节点都是起点图可能到达的一种情况，然后去找符合题目要求的图就可以了；
因为图有可能重复，可以用一个set来去掉重复的图（剪枝），同时因为k已经给了，所以如果操作步骤超过了k，就可以输出no,不需要再操作了；
ps:给出一道类似的题：Rush Hour Puzzle 有兴趣可以做一下
代码中的注释去掉，可以浏览所有结点；
ac代码：

#include <bits/stdc++.h> #define P pair<int,int> using namespace std; int h,w; int k; struct mp{ char p[15][15]; bool friend operator<(const mp &a,const mp &b){ for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ if(a.p[i][j]!=b.p[i][j]) return a.p[i][j]<b.p[i][j]; } } return false; } }; struct node{     P car[8];     P goal[100]; int cnt;     mp p; }c;  set <mp> st; queue <node> q; bool ans=false; bool move(node &res,int id,int de){     mp &p=res.p;     P &car=res.car[id]; int h1,w1;     h1=car.first;     w1=car.second; if(de==1){ int temp=w; if(car.second==w) return false; for(int i=w1+1;i<=w;i++){ if(p.p[h1][i]=='R' || p.p[h1][i]=='X'){                 temp=i-1; break; } }         p.p[car.first][car.second]='.';         car.first=h1;         car.second=temp;         p.p[car.first][car.second]='R'; } if(de==2){ int temp=1; if(car.second==1) return false; for(int i=w1-1;i>=1;i--){ if(p.p[h1][i]=='R' || p.p[h1][i]=='X'){                 temp=i+1; break; } }         p.p[car.first][car.second]='.';         car.first=h1;         car.second=temp;         p.p[car.first][car.second]='R'; } if(de==3){ int temp=h; if(car.first==h) return false; for(int i=h1+1;i<=h;i++){ if(p.p[i][w1]=='R' || p.p[i][w1]=='X'){                 temp=i-1; break; } }         p.p[car.first][car.second]='.';         car.first=temp;         car.second=w1;         p.p[car.first][car.second]='R'; } if(de==4){ int temp=1; if(car.first==1) return false; for(int i=h1-1;i>=1;i--){ if(p.p[i][w1]=='R' || p.p[i][w1]=='X'){                 temp=i+1; break; } }         p.p[car.first][car.second]='.';         car.first=temp;         car.second=w1;         p.p[car.first][car.second]='R'; } /*     cout<<res.cnt<<endl;     for(int i=1;i<=h;i++){         for(int j=1;j<=w;j++){             cout<<res.p.p[i][j]<<" ";         }         cout<<endl;     }     cout<<endl;     */ return true; } int main(){ int test; int cnt1=0; int cnt2=0;     cin>>w>>h>>k; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ char m;             cin>>m; if(m=='R') c.car[cnt1++]={i,j}; if(m=='D') c.goal[cnt2++]={i,j};             c.p.p[i][j]=m; } }     st.insert(c.p);     q.push(c); while(!q.empty()){         c=q.front();         q.pop(); for(int i=0;i<cnt2;i++){ int t1=c.goal[i].first; int t2=c.goal[i].second; if(c.p.p[t1][t2]=='R'){                 ans=true;                 test=c.cnt; break; } } if(ans) break; if(c.cnt>=k) continue; for(int i=0;i<cnt1;i++){ for(int j=1;j<=4;j++){                 node res=c;                 res.cnt++; if(move(res,i,j)){ if(st.count(res.p)) continue; else st.insert(res.p),q.push(res); } } } } if(ans) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }