A - Automatic Judge

题意： 签到题。给定某选手ACM比赛时的数据，请你计算这名选手的通过数量及罚时。

解法： 直接模拟即可。

参考代码：

#include <cstdio> #include <cstring> const int MAXN=100+10; int done[MAXN]; int main(){ int t; scanf("%d",&t); while (t--){ memset(done,0,sizeof(done)); int n,m; scanf("%d%d",&n,&m); int cnt=0,tim=0,pan=0; for (int i=0;i<m;++i){ int prob,h,m,s; char stat[10]; scanf("%d %d:%d %s",&prob,&h,&m,stat); prob-=1000; if (done[prob]==-1) continue; if (stat[0]=='A'){ cnt++; tim+=h*60+m; pan+=done[prob]; done[prob]=-1; } else done[prob]++; } printf("%d %d\n",cnt,tim+pan*20); } return 0; }

B - Building Shops

此题未AC

题意： 一条线上有若干个给定点，第 $i$ 个点有一个坐标 $x_i$ 和一个花费 $c_i$ 。现给出一种计算总花费的方式：若点 $i$ 被选择，则贡献 $c_i$ 的花费，否则贡献数值相当于它到它左边第一个被选择的点的距离 $x_i-x_j$ 的花费。要保证任意一个不被选择的点必存在一个被选择的点在它左边。 给定所有的 $x_i$ 和 $c_i$ ，计算总花费的最小值。

题解见队友博客，点此查看。

C - Coprime Sequence

题解见队友博客，点此查看。

D - Deleting Edges

此题未AC

题意： 给定一个带权 $n$ 顶图，现欲删去其中一些边（或者不删），使得剩余的边数为 $n-1$ ，且从结点 $0$ 到任意其他结点都至少保留原图的一条最短路径。问删边的方法数。结果需要取模。

解法： 先求出所有结点间的最短距离，然后寻找从 $0$ 到各个结点的最短路径数量，相乘再取模即为答案。（比赛的时候写错了29-30行的那两句，直接用了dist[j][i]作为原图距离，然而dist数组前后会发生变化）

参考代码：

#include <cstdio> #include <algorithm> #define min std::min const int MOD=1e9+7; const int MAXN=50+10; const int INF=0x3f3f3f3f; char maze[MAXN][MAXN]; int dist[MAXN][MAXN]; int n; void floyd(){ for (int k=0;k<n;++k) for (int i=0;i<n;++i) for (int j=0;j<n;++j) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); } int main(){ while (~scanf("%d",&n)){ for (int i=0;i<n;++i) scanf("%s",maze[i]); for (int i=0;i<n;++i) for (int j=0;j<n;++j) dist[i][j]=(maze[i][j]=='0')?INF:maze[i][j]-'0'; floyd(); dist[0][0]=0; int res=1; for (int i=1;i<n;++i){ int cnt=0; for (int j=0;j<n;++j){ int tmp=(maze[j][i]=='0')?INF:(maze[j][i]-'0'); if (dist[0][j]+tmp==dist[0][i]) cnt++; } res=(int)((long long)res*cnt%MOD); } printf("%d\n",res); } return 0; }

E - Easy Summation

题意： 给定两个整数 $n$ ， $k$ ，求 $\sum _{i=1}^n{i}^k$ 。其中 $0⩽k⩽5$ ， $1⩽n⩽10^4$ 。结果模 $10^9+7$ 。

解法： 数据不大，快速幂暴力即可。

参考代码：

#include <cstdio> typedef long long ll; const int MOD=1e9+7; inline int multi_mod(int a,int b){ return (int)((ll)a*b%MOD); } inline int plus_mod(int a,int b){ return (int)(((ll)a+b)%MOD); } int qp(int n,int k){ int res=1; while (k){ if (k&1) res=multi_mod(res,n); n=multi_mod(n,n); k>>=1; } return res; } int solve(int n,int k){ int res=0; for (int i=1;i<=n;++i) res=plus_mod(res,qp(i,k)); return res; } int main(){ int t; scanf("%d",&t); while (t--){ int n,k; scanf("%d%d",&n,&k); printf("%d\n",solve(n,k)); } return 0; }

G - Graph Theory

题意： 对于一个 $n$ 顶图（从 $0$ 开始标号），给出 $n-1$ 个描述，每一个描述 $1⩽a_i⩽2$ 表示是否从顶点 $i$ 向它之前的所有点都连一条边。请你判断这个给定的图是否存在完美匹配。即，是否存在某些互不共点的边能覆盖图上的每个顶点。

解法： 此题有一定规律。 首先，由于一条边覆盖两个点，且边与边不共点，所以点的数量必须是偶数。 其次，最后一个顶点必须向前连边，否则没有点与它相连，一定不存在完美匹配。 当满足以上两点时，考虑从后向前的任意点。 如果这个点向前连边，则至少能保证它自己在匹配的点当中。否则，这个点需要它后面的某个点与它相连。现比较从它开始向后的所有点。假设这些点中连出边的有 ${\text{cnt}}_1$ 个点，未连出边的有 ${\text{cnt}}_2$ 个点，则此时必须有 ${\text{cnt}}_1⩾{\text{cnt}}_2$ （因为一个点只能被用一次）。

参考代码：

#include <cstdio> const int MAXN=1e5+10; int n,a[MAXN]; bool solve(){ if ((n&1)||a[n-1]==2) return false; int cnt1=0,cnt2=0; for (int i=n-1;i>0;--i){ if (a[i]==1) cnt1++; else{ cnt2++; if (cnt2>cnt1) return false; } } return true; } int main(){ int t; scanf("%d",&t); while (t--){ scanf("%d",&n); for (int i=1;i<n;++i) scanf("%d",&a[i]); printf(solve()?"Yes\n":"No\n"); } }

H - Happy Necklace

题意： 一条含有 $n$ 个结点的长链，欲给这些结点着色，只允许着红蓝两种颜色，并要求对于每一个素数长度的序列，红色的数量不少于蓝色，求共有多少染色方法。

题解: 见队友博客，点此查看。

剩余题目皆未AC，题解暂不给出。