吼吼~第一次rank1的比赛！
第一题直接最短路，存名字用map即可。
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <algorithm>#include <map>#include <queue>#define inf 0x3f3f3f3fusing namespace std;map<string,int> mp;string s[15],s1,s2;int p,q,d[1000],l[1000],inq[1000],pre[1000],tot,cnt,r,h[100];struct Reco{int p,v;}re[10000];struct edge{int y,v,ne;}e[10000];void Addedge(int x,int y,int v){e[++tot].y=y;e[tot].v=v;e[tot].ne=h[x];h[x]=tot;}void Ask(int from,int to){for (int i=1;i<=p;i++)d[i]=inf,inq[i]=0,pre[i]=0;queue<int> q;q.push(from);d[from]=0,inq[from]=1;while (!q.empty()){int x=q.front();q.pop();inq[x]=0;for (int i=h[x];i;i=e[i].ne){int y=e[i].y;if (d[y]>d[x]+e[i].v){d[y]=d[x]+e[i].v;pre[y]=x;l[y]=e[i].v;if (!inq[y]) q.push(y),inq[y]=1;}}}int u=to;cnt=0;while (u!=from){re[++cnt].p=u;re[cnt].v=l[u];u=pre[u];}cout<<s[from];for (int i=cnt;i;i–){printf("->(%d)->",re[i].v);cout<<s[re[i].p];}cout<<endl;}int main(){scanf("%d",&p);for (int i=1;i<=p;i++){cin>>s[i];mp[s[i]]=i;}int qq;scanf("%d",&qq);for (int i=1;i<=qq;i++){int v;cin>>s1;cin>>s2;cin>>v;Addedge(mp[s1],mp[s2],v);Addedge(mp[s2],mp[s1],v);}scanf("%d",&r);for (int i=1;i<=r;i++){cin>>s1;cin>>s2;Ask(mp[s1],mp[s2]);}return 0;}
第二题类似于博弈：
分两种情况：
1.如果一共有偶数个数字，那先手必胜：
因为偶数个数字除去1这个数字后还有奇数个，那么分布在1的左右两侧的数字一定是一奇一偶的，所以先手取完之后一定可以保证1两侧都有奇数个数字；
这样到最后，1左侧一个数字，右侧一个数字，那么先手必胜直接输出1/1
2.如果一共有奇数个数字，只有1在最左侧或最右侧先手必胜：
为什么1在别的地方先手必败？因为先手取走一个后，就后手的情况就变成了第一种情况中先手的状态，所以后手必胜，直接输出2/n（注意n=1的情况要特判）
<span style="font-size:18px;">#include <iostream>#include <cstdio>#include <algorithm>#include <cstdlib>#include <cstring>#include <cmath>#define LL long longusing namespace std;LL n;int main(){cin>>n;if (n&1LL){if (n==1LL) cout<<"1/1"<<endl;else cout<<"2/"<<n<<endl;}else{cout<<"1/1"<<endl;}return 0;}</span>
T3当时没看懂题，其实就是一个网络流，建图方法是：
每个点拆成两个x,x’，从s向每个x连流量为1，费用为0的边；x’向t连流量为1，费用为0的边；
从x向比他线密度大的y’连流量为1费用为第一个公式的边（任何点不向1’连，n不向任何点连）；
对于扭曲平面的情况，可以发现他的费用之和目的地有关，所以建立一个附加源s’，s和s’连流量为m费用为0的边，s’向每个x’连流量为1费用为第二个公式的边。
求费用流即可。
（没有写= =）
第四题正解是插头dp，，我用spfa水了47分：
对于只有一对的直接spfa求就可以；
有两对的枚举三种配对情况，对于要求不能有重复路径：在到达终点后把当前路径走过的地方标记，再另一对的最小值更新答案（非常暴力）
<span style="font-size:18px;">#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <queue>#define inf 0x3f3f3f3f#define M 10000using namespace std;int nx,from,to,p[1000],ny,size,ans,pre[M],d2[M],pre2[M],inq2[M],inq[M],tot,d[M],h[M],r,c,fx[10][10];char a[100][100],Ans[100][100];struct edge{int y,ne;}e[M];int C(int x,int y){return (x-1)*c+y;}void Addedge(int x,int y){e[++tot].y=y;e[tot].ne=h[x];h[x]=tot;}void Buildgragh(){for (int i=1;i<=r;i++)for (int j=1;j<=c;j++){for (int k=1;k<=4;k++){int x=i+fx[k][1],y=j+fx[k][2];if (x>0&&y>0&&x<=r&&y<=c&&(a[x][y]==' '||a[x][y]=='X'))Addedge(C(i,j),C(x,y));}}}void Get(int x){nx=0,ny=0;nx=x/c+(x%c==0?0:1);ny=x-c*(nx-1);}void spfa(){for (int i=1;i<=r*c;i++)d[i]=inf,inq[i]=0;d[from]=0;queue<int> q;q.push(from);inq[from]=1;while (!q.empty()){int x=q.front();q.pop();inq[x]=0;for (int i=h[x];i;i=e[i].ne){int y=e[i].y;if (d[y]>d[x]+1){d[y]=d[x]+1;pre[y]=x;if (!inq[y]) q.push(y),inq[y]=1;}}}cout<<d[to]<<endl;int u=to;while (pre[u]!=from){u=pre[u];Get(u);a[nx][ny]='.';}for (int i=1;i<=r;i++){for (int j=1;j<=c;j++)cout<<a[i][j];cout<<endl;}}void Paint1(int from,int to){int u=to;while (pre[u]!=from){u=pre[u];Get(u);if (a[nx][ny]==' ') a[nx][ny]='.';else a[nx][ny]=' ';}}void Paint2(int from,int to){int u=to;while (pre2[u]!=from){u=pre2[u];Get(u);if (a[nx][ny]==' ') a[nx][ny]='.';else a[nx][ny]=' ';}}int Calc(int from,int to){for (int i=1;i<=size;i++)d2[i]=inf,inq2[i]=0;queue<int> q2;q2.push(from);inq2[from]=1,d2[from]=0;while (!q2.empty()){int x=q2.front();q2.pop();inq2[x]=0;for (int i=h[x];i;i=e[i].ne){int y=e[i].y;Get(y);if (a[nx][ny]=='.'||(a[nx][ny]=='X'&&y!=to)) continue;if (d2[y]<=d2[x]+1) continue;d2[y]=d2[x]+1;pre2[y]=x;if (!inq2[y]) q2.push(y),inq2[y]=1;}}return d2[to];}void spfa2(int from,int to,int from2,int to2){for (int i=1;i<=size;i++)d[i]=inf,inq[i]=0;queue<int> q;q.push(from);inq[from]=1,d[from]=0;while (!q.empty()){int x=q.front();q.pop();inq[x]=0;for (int i=h[x];i;i=e[i].ne){int y=e[i].y;Get(y);if (a[nx][ny]=='X'&&y!=to) continue;if (d[y]<=d[x]+1) continue;d[y]=d[x]+1;pre[y]=x;if (!inq[y]) q.push(y),inq[y]=1;if (y==to){Paint1(from,to);int o=Calc(from2,to2);if (d[y]+o<ans){ans=d[y]+o;Paint2(from2,to2);for (int j=1;j<=r;j++)for (int k=1;k<=c;k++)Ans[j][k]=a[j][k];Paint2(from2,to2);}Paint1(from,to);}}}}int main(){fx[1][1]=1,fx[1][2]=0,fx[2][1]=-1,fx[2][2]=0;fx[3][1]=0,fx[3][2]=1,fx[4][1]=0,fx[4][2]=-1;scanf("%d%d",&r,&c);size=r*c;int cnt=0;for (int i=1;i<=r;i++){char ch=getchar();while (ch!='+'&&ch!='|')ch=getchar();a[i][1]=ch;for (int j=2;j<=c;j++){ch=getchar();a[i][j]=ch;if (a[i][j]=='X'){cnt++;p[cnt]=C(i,j);if (cnt==1) from=C(i,j);else to=C(i,j);}}}if (cnt==0){for (int i=1;i<=r;i++){for (int j=1;j<=c;j++)cout<<a[i][j];cout<<endl;}}Buildgragh();if (cnt==2){spfa();}if (cnt==4){ans=inf;for (int i=1;i<=r;i++)for (int j=1;j<=c;j++)Ans[i][j]=a[i][j];spfa2(p[1],p[2],p[3],p[4]);spfa2(p[1],p[3],p[2],p[4]);spfa2(p[1],p[4],p[2],p[3]);cout<<ans<<endl;for (int i=1;i<=r;i++){for (int j=1;j<=c;j++)cout<<Ans[i][j];cout<<endl;}}return 0;}</span>
每天告诉自己一次，『我真的很不错』
