本文共 3610 字，大约阅读时间需要 12 分钟。

好！

T1

暴力模拟，比较水
所以不多讲
$100pts$

$ACCode$

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int a[1000010],b[1000010];int n,x,c,ans;int main(){       freopen("card.in","r",stdin);    freopen("card.out","w",stdout);    cin>>n;    for(int i=1; i<=n; i++)     {        	cin>>x;     	a[x]=x;      //桶     }    for(int i=1; i<=n*2; i++)     {        	if(a[i]==0)     	  b[++c]=i;    //记录奶牛Bessie的纸牌     }    c=1;    sort(a+1,a+1+n*2);    for(int i=1; i<=n; i++)    //暴力比较     {        	while(a[c]==0)     	  c++;     	if(b[i]>a[c])     	  ans++,c++;     }    cout<<ans;    return 0;}

T2

二分
我们记录每种音节的位置，然后二分范围。

$100pts$

$ACCode$

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int n,q,fw,x,l,r,mid;struct node{       int l,r;}a[100010];int main(){   	freopen("mnotes.in","r",stdin);    freopen("mnotes.out","w",stdout);	scanf("%d%d",&n,&q);    for(int i=1; i<=n; i++)     {           scanf("%d",&x);        a[i].l=fw;     //记录位置		fw+=x;		a[i].r=fw-1;     }    for(int i=1; i<=q; i++)     {           scanf("%d",&x);        l=1,r=n;        while(1)         {               mid=(l+r)/2;            if(a[mid].l<=x&&a[mid].r>=x)    //二分范围			 {   			   printf("%d\n",mid);			   break;			 }            else if(a[mid].l>x)			  r=mid;            else 			  l=mid+1;         }     }    return 0;}

T3

一道DP
刚开题的时候发现有点眼熟，
然后发现可以对每种游戏平台里的游戏做01背包
就过了

$ACCode$

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int f[1000010],ans[1000010];int n,v,pt,yxs,w,c;int main(){   	freopen("vidgame.in","r",stdin);    freopen("vidgame.out","w",stdout);	cin>>n>>v;	for(int i=1; i<=n; i++)	 {   	 	cin>>pt>>yxs;	 	for(int j=pt; j<=v; j++)  //减去当前平台价值	 	   f[j]=ans[j-pt];	 	for(int j=1; j<=yxs; j++)	 	 {   	 	 	cin>>w>>c;	 	 	for(int k=v-w; k>=pt; k--)   //做01背包	 	 	   f[k+w]=max(f[k+w],f[k]+c);	 	 }	 	for(int j=pt; j<=v; j++)	 	   ans[j]=max(ans[j],f[j]);	 }  	cout<<ans[v];    return 0;}

T4

明显就是一个最短路，
但问题就是我不会处理点权，
只能输出样例，得了10分。

正解:巧妙的Floyd
我们先把点权排序，这样就能符合Floyd的性质，我们就可以直接一边跑Floyd一边比较点权求最大了。

$ACCode$

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int f[1010][1010],w[1010],bq[1010][1010];int n,m,q,ax,ay,x,y,z;struct node{     int c,id;}d[1010];bool cmp(node a,node b){       return a.c==b.c?a.id<b.id:a.c<b.c;}int main(){   	freopen("toll.in","r",stdin);    freopen("toll.out","w",stdout);	cin>>n>>m>>q;    for(int i=1; i<=n; i++)     {   	   scanf("%lld",&d[i].c);	   d[i].id=i;     }    sort(d+1,d+1+n,cmp);    for(int i=1; i<=n; i++)	   w[d[i].id]=i;	for(int i=1; i<=n; i++)	 for(int j=1; j<=n; j++)	  f[i][j]=bq[i][j]=1e9;    for(int i=1; i<=n; i++)	   bq[i][i]=0;	for(int i=1; i<=n; i++)	 for(int j=1; j<=f[i]; j++)	 if(bq[i][j]==w[i])	   f[i][j]=bq[i][j]+w[i];    for(int i=1; i<=m; i++)     {           scanf("%lld%lld%lld",&x,&y,&z);        x=w[x];		y=w[y];        bq[x][y]=min(bq[x][y],z);   //预处理边权		bq[y][x]=bq[x][y];     }    for(int k=1; k<=n; k++)     for(int i=1; i<=n; i++)      for(int j=1; j<=n; j++)       {             bq[i][j]=min(bq[i][j],bq[i][k]+bq[k][j]);  //Floyd          f[i][j]=min(bq[i][j]+max(d[i].c,max(d[j].c,d[k].c)),f[i][j]);  //点权比较       }    for(int i=1; i<=q; i++)     {           scanf("%lld%lld",&ax,&ay);        ax=w[ax];		ay=w[ay];	    cout<<f[ax][ay]<<endl;     }    return 0;}

总分

$100+100+100+10=310pts$

再接再厉！