前言

运气真好AK了(╯‵□′)╯︵┻━┻

庆祝$E$题没看懂题找规律过了(╯‵□′)╯︵┻━┻

A

题意： 差不多就是说，在$1-10000$范围内，如果一个数字的每一位都是同一个数字，就叫无聊数字，然后会以$1,11,111,1111,2,22...$这样的顺序排列，然后问无聊数字$x$，以及其的排列前面的数字的位数之和是多少，例如：$11$，前面有$1$，然后位数之和为$2+1=3$。

暴力模拟啊。

#include<cstdio> #include<cstring> using namespace std; inline int solve(int x) { int type=x%10; int ans=(type-1)*10; int y=0; while(x) { x/=10; y++; ans+=y; } printf("%d\n",ans); } int main() { int T;scanf("%d",&T); for(int i=1;i<=T;i++) { int x;scanf("%d",&x); solve(x); } return 0; }

B

题意： 如果第$i$个位置有书为$1$，没书为$0$。 对于书架上连续的一段书$[l,r]$，如果$r+1$的位置没有位置，则可以把$[l,r]$的书右移到$[l+1,r+1]$，左移类似。 然后问把所有书变成连续的一段最小需要多少移动次数。

做法： 每次最多消掉一个间隔，不难发现，答案就是相邻每段书之间的间隔和。

#include<cstdio> #include<cstring> #define N 60 using namespace std; int a[N],n; void solve() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); bool bk=0;int ans=0,cnt=0; for(int i=1;i<=n;i++) { if(!a[i]) { if(bk)cnt++; } else { bk=1; ans+=cnt; cnt=0; } } printf("%d\n",ans); } int main() { int T;scanf("%d",&T); while(T--)solve(); return 0; }

C

题意： 差不多就是说，一条鱼$i$，如果$a[i-1]<a[i]$或者$a[i+1]<a[i]$，就可以吃掉$i-1$或者$i+1$的位置，然后$a[i]++$，如果一条鱼，假定全局只有它能吃别的鱼，并且在最后它能吃掉所有的鱼，那么称其为优势鱼，然后问存不存在优势鱼，存在，随便输其中一条优势鱼的编号。

首先考虑权值最大的情况，那如果权值最大的鱼吃掉了一条鱼，那么所有的鱼它随便吃，因此只要存在一只权值最大的鱼且左右两边有一条鱼比它小，它就是优势鱼。

当时这样一定能判定没有优势鱼的情况吗？不难发现，这种做法找到的优势鱼一定是正确的，且如果找不到当且仅当所有的鱼权值相同，此时确实是没有优势鱼的，所以这种做法是正确的。

#include<cstdio> #include<cstring> #define N 310000 using namespace std; int a[N],n; inline int mymax(int x,int y){return x>y?x:y;} void solve() { scanf("%d",&n); int mmax=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); mmax=mymax(a[i],mmax); } a[0]=a[1];a[n+1]=a[n]; for(int i=1;i<=n;i++) { if(a[i]==mmax && (a[i-1]!=a[i] || a[i+1]!=a[i])) { printf("%d\n",i); return ; } } printf("-1\n"); return ; } int main() { int T;scanf("%d",&T); while(T--)solve(); return 0; }

同机房奆佬还想了一个类似栈的做法，不再赘述。虽然刚开始思路错了，但是后来发现改一下就能规避问题了。

D

题意： 每个点都有一个权值，然后让你用$n-1$条边把$n$个点连成一棵树，且要求边两端的点权值不能相同。

记录第一个点的颜色，找到第一个和第一个点不同颜色的点，记为$id$，如果一个点和第一个点不同颜色，则连向第一个点，如果和第一个点相同，则连向$id$。

无解情况就是找不到$id$的情况。

#include<cstdio> #include<cstring> #define N 5100 using namespace std; int co[N],n; void solve() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&co[i]); } int shit=co[1]; int id=0; for(int i=2;i<=n;i++) { if(co[i]!=shit) { id=i; break; } } if(!id) { printf("NO\n"); return ; } printf("YES\n"); for(int i=2;i<=n;i++) { if(co[i]!=shit)printf("1 %d\n",i); else printf("%d %d\n",id,i); } } int main() { int T;scanf("%d",&T); while(T--)solve(); return 0; }

E

题意： 赛后才知道题意 首先，轮舞是什么？ 篝火晚宴见过吧，手拉着手一个圈跳舞就是轮舞，现在把$n(n是偶数)$个人（第$i$个人编号为$i$）等分成两个轮舞。 记为一种轮舞方案{$A,B$}。 两个轮舞$X,Y$相同，当且仅当选定某个点为开头时，从左往右形成的序列相同（也就是说$[1,2,3]$和$[3,2,1]$是不同的）。 轮舞方案{$A_1,B_1$}和{$A_2,B_2$}相同，当且仅当$A_1=A_2,B_1=B_2$或者$A_1=B_2,B_1=A_2$。 问有多少个不同的方案，答案保证在$long$ $long$范围内。

做法： 设$n=2m$，先选$m$个人组成左边的圈，即$C_n^m$，但是选出了$m$个人，不同的圈排列个数是多少呢？我们不妨像题目中所说的，固定一个人就是在一号位置，其余人全排列，那么就是$(n-1)!$，不难发现这样不会重复且可以找到所有的方案（显然正确因为每个人一定在圈上），然后就是$C_n^m\ast (m-1)!\ast (m-1)!$，但是发现一个圈方案左边右边都会被选上，所以还要除$2$（其实有规避的方法，假设编号为$1$的人一定被选上，那么就是$C_{n-1}^{m-1}$）。

化一下式子： $\frac{C_n^m\ast (m-1)!\ast (m-1)!}{2}=\frac{n!\ast (m-1)!\ast (m-1)!}{2\ast m!\ast m!}=\frac{2n!}{n^2}=\frac{2(n-1)!}{n}$

这个式子就简单了很多。这个就是我考场上发现的规律。

打开计算器，发现$19!$不会爆$long$ $long$，直接乱搞。

#include<cstdio> #include<cstring> using namespace std; int main() { int n;scanf("%d",&n); if(n==2)printf("1\n"); else { long long ans=1; for(int i=1;i<n;i++)ans*=i; ans/=n/2; printf("%lld\n",ans); } return 0; }

F

一个$n\ast m$的矩阵，每一行最多能选$\frac{m}{2}$个，然后要求选出来数的总和是$k$的倍数，问总和的最大值是多少。

设$f[i][j][k]$表示每一行的第$i$个数字，选了$j$个，余数为$k$的最大值，不难想到状态转移方程。

时间复杂度：$O(n^4)$

#include<cstdio> #include<cstring> #define N 90 using namespace std; inline int mymax(int x,int y){return x>y?x:y;} int a[N][N]; int f[2][N][N]; int n,m,K; void dp() { memset(f[0],-20,sizeof(f[0])); f[0][0][0]=0;int now=0,pre=1; int limit=m/2; for(int i=1;i<=n;i++) { now^=1;pre^=1; memset(f[now],-20,sizeof(f[now])); for(int j=0;j<=limit;j++) { for(int k=0;k<K;k++)f[now][0][k]=mymax(f[now][0][k],f[pre][j][k]); } for(int j=1;j<=m;j++) { now^=1;pre^=1; memset(f[now],-20,sizeof(f[now])); for(int k=1;k<=limit;k++) { for(int t=0;t<K;t++) { int shit=(t+a[i][j])%K; f[now][k][shit]=mymax(f[now][k][shit],f[pre][k-1][t]+a[i][j]); } } for(int k=0;k<=limit;k++) { for(int t=0;t<K;t++)f[now][k][t]=mymax(f[now][k][t],f[pre][k][t]); } } } now^=1;pre^=1; memset(f[now],-20,sizeof(f[now])); for(int j=0;j<=limit;j++) { for(int k=0;k<K;k++)f[now][0][k]=mymax(f[now][0][k],f[pre][j][k]); } printf("%d\n",f[now][0][0]); } int main() { scanf("%d%d%d",&n,&m,&K); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++)scanf("%d",&a[i][j]); } dp(); return 0; }

G

题意： 一个$n$个点$m$条边的无向图，有$k$个订单，每个订单是从$x$跑到$y$，定义每个订单的费用为$x$到$y$的最短路，总费用为每个订单的费用和。

你最多可以让一条边变成$0$，然后问你最小总费用是多少。

做法： 对每个点跑一遍最短路，因为是稀疏图，$SPFA$很快。为了不被hack，后面又打了一个Dij的版本

肯定用掉机会比不用最小费用更小一点（最多不变）。

枚举是哪条边变成了$0$，对于订单$x->y$，有两种操作，一种走原来的路，一种为了走$0$边而强行改变路线（可能没改），至于怎么让$x->y$强行走一条边，大家也是懂的啦，直接把$x$走到边的一端的费用再加上另一端走到$y$的费用即可。

Dij时间复杂度：$O(nm\log m+mk)$ SPFA：

#include<cstdio> #include<cstring> #define N 1100 #define M 2100 using namespace std; typedef long long LL; inline LL mymin(LL x,LL y){return x<y?x:y;} LL d[N][N]; int list[N],head,tail,n,m,k; bool v[N]; struct node { int y,next; LL c; }a[M];int len,last[N]; inline void ins(int x,int y,LL c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;} void SPFA(int st) { memset(d[st],20,sizeof(d[st]));d[st][st]=0; list[head=1]=st;tail=2;v[st]=1; while(head!=tail) { int x=list[head++];if(head==n+1)head=1; v[x]=0; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(d[st][x]+a[k].c<d[st][y]) { d[st][y]=d[st][x]+a[k].c; if(!v[y]) { v[y]=1; list[tail++]=y;if(tail==n+1)tail=1; } } } } } struct SHIT { int x,y; SHIT(int xx=0,int yy=0){x=xx;y=yy;} }zjj1[N],zjj2[N]; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { int x,y;LL c;scanf("%d%d%lld",&x,&y,&c); ins(x,y,c);ins(y,x,c); zjj2[i]=SHIT(x,y); } for(int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); zjj1[i]=SHIT(x,y); } for(int i=1;i<=n;i++)SPFA(i); LL ans=(LL)99999999999999; for(int i=1;i<=m;i++) { LL sum=0; int x=zjj2[i].x,y=zjj2[i].y; for(int j=1;j<=k;j++) { int ax=zjj1[j].x,ay=zjj1[j].y; sum+=mymin(mymin(d[ax][x]+d[y][ay],d[ax][y]+d[x][ay]),d[ax][ay]); } ans=mymin(ans,sum); } printf("%lld\n",ans); return 0; }

Dij：

#include<cstdio> #include<cstring> #include<queue> #define N 1100 #define M 2100 using namespace std; typedef long long LL; inline LL mymin(LL x,LL y){return x<y?x:y;} LL d[N][N]; int n,m,k; bool v[N]; struct node { int y,next; LL c; }a[M];int len,last[N]; inline void ins(int x,int y,LL c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;} priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > > fuck; void SPFA(int st) { memset(d[st],20,sizeof(d[st]));d[st][st]=0; memset(v,0,sizeof(v)); while(!fuck.empty())fuck.pop(); fuck.push(make_pair(0,st)); for(int i=1;i<=n;i++) { pair<LL,int> zwq=fuck.top();fuck.pop(); int x=zwq.second; while(v[x]) { zwq=fuck.top();fuck.pop(); x=zwq.second; } v[x]=1; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(!v[y] && zwq.first+a[k].c<d[st][y]) { d[st][y]=zwq.first+a[k].c; fuck.push(make_pair(d[st][y],y)); } } } } struct SHIT { int x,y; SHIT(int xx=0,int yy=0){x=xx;y=yy;} }zjj1[N],zjj2[N]; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { int x,y;LL c;scanf("%d%d%lld",&x,&y,&c); ins(x,y,c);ins(y,x,c); zjj2[i]=SHIT(x,y); } for(int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); zjj1[i]=SHIT(x,y); } for(int i=1;i<=n;i++)SPFA(i); LL ans=(LL)99999999999999; for(int i=1;i<=m;i++) { LL sum=0; int x=zjj2[i].x,y=zjj2[i].y; for(int j=1;j<=k;j++) { int ax=zjj1[j].x,ay=zjj1[j].y; sum+=mymin(mymin(d[ax][x]+d[y][ay],d[ax][y]+d[x][ay]),d[ax][ay]); } ans=mymin(ans,sum); } printf("%lld\n",ans); return 0; }