DAY1
T1根据题目描述模拟就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 100 using namespace std; int ai[maxm][maxm]={0}; int main(){ freopen("magic.in","r",stdin); freopen("magic.out","w",stdout); int n,i,j,x,y,up; scanf("%d",&n); up=n*n;ai[1][n/2+1]=1; x=1;y=n/2+1; for (i=2;i<=up;++i){ if (x==1&&y!=n){ x=n;++y;ai[x][y]=i;continue; }if (y==n&&x!=1){ --x;y=1;ai[x][y]=i;continue; }if (x==1&&y==n){ ++x;ai[x][y]=i;continue; }if (!ai[x-1][y+1]){ --x;++y;ai[x][y]=i;continue; }++x;ai[x][y]=i; }for (i=1;i<=n;++i){ for (j=1;j<=n;++j) printf("%d ",ai[i][j]); printf(" "); } fclose(stdin); fclose(stdout); }
T2tarjan or dfs or spfa
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 400005 using namespace std; int point[maxm]={0},next[maxm]={0},en[maxm]={0},scnt=0,zh[maxm]={0},pre[maxm]={0},low[maxm]={0},ti=0, siz[maxm]={0},sccno[maxm]={0},tot=0; void add(int u,int v){next[++tot]=point[u];point[u]=tot;en[tot]=v;} void tarj(int u){ int i,j,v;zh[++zh[0]]=u; pre[u]=low[u]=++ti; for (i=point[u];i;i=next[i]){ if (!pre[v=en[i]]){ tarj(v);low[u]=min(low[u],low[v]); }else{ if (!sccno[v]) low[u]=min(low[u],pre[v]); } }if (pre[u]==low[u]){ ++scnt; while(zh[0]>0){ v=zh[zh[0]--]; sccno[v]=scnt;++siz[scnt]; if (v==u) break; } } } int main(){ freopen("message.in","r",stdin); freopen("message.out","w",stdout); int n,i,j,v,ans;scanf("%d",&n); for (i=1;i<=n;++i){scanf("%d",&v);add(i,v);} for (i=1;i<=n;++i) if (!pre[i]) tarj(i); ans=n; for (i=1;i<=scnt;++i) if (siz[i]>1) ans=min(ans,siz[i]); printf("%d ",ans); fclose(stdin); fclose(stdout); }
T3 landlords
题目大意：给定一副牌，求最少出牌次数。
思路：dfs搜顺子的情况，然后再dp，fi[a][b][c][d]表示有1张的a种、2张的b种、3张的c种、4张的d种的最少次数。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define up 15 using namespace std; int cnt[up],fi[up][up][up][up],ans; int idx(int x,int y){ if (!x) return 14; if (x==1||x==2) return x+11; return x-2; } void dfs(int dep,int ci){ int i,j,k; if (ci>=ans) return; if (dep==1){//三顺 for (i=1;i<=12;++i){ if (cnt[i]<3) continue; j=i;while(j<12&&cnt[j+1]>=3) ++j; if (j-i+1>=2){ for (k=j;k>=i;--k) cnt[k]-=3; k=3*(j-i+1); while(j-i+1>=2){ dfs(1,ci+1);k-=3; cnt[j]+=3;--j; }for (k=j;k>=i;--k) cnt[k]+=3; } }dfs(2,ci);return; }if (dep==2){//双顺 for (i=1;i<=12;++i){ if (cnt[i]<2) continue; j=i;while(j<12&&cnt[j+1]>=2) ++j; if (j-i+1>=3){ for (k=j;k>=i;--k) cnt[k]-=2; k=2*(j-i+1); while(j-i+1>=3){ dfs(2,ci+1);k-=2; cnt[j]+=2;--j; }for (k=j;k>=i;--k) cnt[k]+=2; } }dfs(3,ci);return; }if (dep==3){//单顺 for (i=1;i<=12;++i){ if (!cnt[i]) continue; j=i;while(j<12&&cnt[j+1]) ++j; if (j-i+1>=5){ for (k=j;k>=i;--k) cnt[k]-=1; k=j-i+1; while(j-i+1>=5){ dfs(3,ci+1);k-=1; cnt[j]+=1;--j; }for (k=j;k>=i;--k) cnt[k]+=1; } }dfs(4,ci);return; }int a,b,c,d,t;a=b=c=d=0;//dp memset(fi,127/3,sizeof(fi)); for (i=1;i<up;++i){ if (cnt[i]==4) ++d; if (cnt[i]==3) ++c; if (cnt[i]==2) ++b; if (cnt[i]==1) ++a; }fi[0][0][0][0]=0; for (i=0;i<=a;++i) for (j=0;j<=b;++j) for (k=0;k<=c;++k) for (t=0;t<=d;++t){ if (t){ fi[i][j][k][t]=min(fi[i][j][k][t],fi[i][j][k][t-1]+1); if (j) fi[i][j][k][t]=min(fi[i][j][k][t],fi[i][j-1][k][t-1]+1); if (j>=2) fi[i][j][k][t]=min(fi[i][j][k][t],fi[i][j-2][k][t-1]+1); if (t>=2) fi[i][j][k][t]=min(fi[i][j][k][t],fi[i][j][k][t-2]+1); if (i>=2) fi[i][j][k][t]=min(fi[i][j][k][t],fi[i-2][j][k][t-1]+1); }if (k){ fi[i][j][k][t]=min(fi[i][j][k][t],fi[i][j][k-1][t]+1); if (i) fi[i][j][k][t]=min(fi[i][j][k][t],fi[i-1][j][k-1][t]+1); if (j) fi[i][j][k][t]=min(fi[i][j][k][t],fi[i][j-1][k-1][t]+1); }if (j) fi[i][j][k][t]=min(fi[i][j][k][t],fi[i][j-1][k][t]+1); if (i) fi[i][j][k][t]=min(fi[i][j][k][t],fi[i-1][j][k][t]+1); } ans=min(ans,ci+fi[a][b][c][d]); } int main(){ int t,n,i,x,y;scanf("%d%d",&t,&n); while(t--){ memset(cnt,0,sizeof(cnt)); for (i=1;i<=n;++i){ scanf("%d%d",&x,&y); ++cnt[idx(x,y)]; }ans=n;dfs(1,0); printf("%d ",ans); } }
DAY2
T1二分+贪心判断。（考场上还是耗了一些时间，考场上和平时的思路还是有差距）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 50005 using namespace std; int di[maxm]={0},n,m,l; bool judge(int x){ int i,j,la=0,cnt=0; for (i=1;i<=n+1;++i){ if (di[i]-di[la]<x) ++cnt; else la=i; }return (cnt<=m); } int main(){ freopen("stone.in","r",stdin); freopen("stone.out","w",stdout); int i,j,ll,rr,mid,ans; scanf("%d%d%d",&l,&n,&m); for (i=1;i<=n;++i) scanf("%d",&di[i]); di[n+1]=l;ll=0;rr=l; while(ll<=rr){ mid=(ll+rr)/2; if (judge(mid)){ans=mid;ll=mid+1;} else rr=mid-1; }printf("%d ",ans); fclose(stdin); fclose(stdout); }
T2dp+前缀和优化。（考场上只写了一个裸的dp，想到可以前缀和优化了，但是下标的问题没有调出来）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 1005 #define maxx 205 #define p 1000000007 using namespace std; int fi[2][maxm][maxx]={0},pre[maxm][maxm]={0},gi[2][maxm][maxx]={0}; char s1[maxm],s2[maxm]; char in(){ char ch=getchar(); while(ch<'a'||ch>'z') ch=getchar(); return ch; } int main(){ int i,j,t,n,m,k,cur=0,a; scanf("%d%d%d",&n,&m,&k); for (i=1;i<=n;++i) s1[i]=in(); for (i=1;i<=m;++i) s2[i]=in(); for (i=1;i<=n;++i) for (j=1;j<=m;++j) if (s1[i]==s2[j]) pre[i][j]=max(pre[i][j],pre[i-1][j-1]+1); for(cur=i=0;i<=n;++i) fi[cur][i][0]=1; for (i=0;i<=n;++i) for (j=0;j<=m;++j) gi[cur][i][j]=(gi[cur][i-1][j-1]+fi[cur][i][j])%p; for (t=1;t<=k;++t){ cur^=1;memset(fi[cur],0,sizeof(fi[cur])); for (i=1;i<=n;++i) for (j=1;j<=m;++j){ if (j>i) break; fi[cur][i][j]=((gi[cur^1][i-1][j-1]-gi[cur^1][i-pre[i][j]-1][j-pre[i][j]-1]+ fi[cur][i-1][j])%p+p)%p; } for (i=0;i<=n;++i) for (j=0;j<=m;++j) gi[cur][i][j]=(gi[cur][i-1][j-1]+fi[cur][i][j])%p; }printf("%d ",fi[cur][n][m]); }
T3 transport
题目大意：给定一棵树和一些链，可以改动一条边为0，求所有链上边权和的最大值最小是多少。
思路：考场上只写了nm的暴力，60分。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 600005 using namespace std; int point[maxm]={0},next[maxm]={0},en[maxm]={0},va[maxm]={0},tot,v1[maxm]={0},v2[maxm]={0}, dep[maxm]={0},ed[maxm]={0},fa[maxm]={0},du[maxm]={0}; bool vi[maxm]={false}; void add(int u,int v,int vv){ next[++tot]=point[u];point[u]=tot;en[tot]=v;va[tot]=vv; next[++tot]=point[v];point[v]=tot;en[tot]=u;va[tot]=vv; } void dfs(int u,int ff){ int i,j,v;dep[u]=dep[ff]+1;fa[u]=ff; for (i=point[u];i;i=next[i]) if ((v=en[i])!=ff){dfs(v,u);ed[v]=i;} } int work(int u,int v){ int i,j,sum=0;if (dep[u]<dep[v]) swap(u,v); while(dep[u]>dep[v]){ vi[ed[u]]=vi[ed[u]^1]=true; sum+=va[ed[u]];u=fa[u]; }while(u!=v){ vi[ed[u]]=vi[ed[u]^1]=vi[ed[v]]=vi[ed[v]^1]=true; sum+=va[ed[u]]+va[ed[v]]; u=fa[u];v=fa[v]; }return sum; } int main(){ freopen("transport.in","r",stdin); freopen("transport.out","w",stdout); int n,m,i,j,u,v,vv,ans,ci=0;tot=1; scanf("%d%d",&n,&m);ans=2100000000; for (i=1;i<n;++i){ scanf("%d%d%d",&u,&v,&vv);add(u,v,vv); }dfs(1,0); for (i=1;i<=m;++i){ scanf("%d%d",&u,&v); for (j=2;j<=tot;++j) vi[j]=false; vv=work(u,v); for (j=2;j<=tot;++j){ if (!vi[j]) v2[j]=max(v2[j],vv); else v1[j]=max(v1[j],vv); } }for (i=2;i<=tot;++i) ans=min(ans,max(v1[i]-va[i],v2[i])); printf("%d ",ans); fclose(stdin); fclose(stdout); }
其实看到最大值最小还是首先想二分，但是不会判断。后来听了ta爷的讲解，才明白。其实二分完了之后，我们就是判断一下能否把所有超过二分答案的链的某一条公共边改为0之后使得这些链都不超过答案，可以首先记录有多少这样的链，然后利用差分的思想在树上记录一下，然后前缀和的话就可以考虑到每一条边能否被所有边覆盖了，对于能覆盖的边就可以取一个max，最后判断能否满足条件。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 300005 #define maxe 600005 #define up 20 using namespace std; struct use{ int u,v,lc,di; }ask[maxm]={0}; int point[maxm]={0},en[maxe],va[maxe],next[maxe]={0},tot=0,fa[maxm][up]={0},dep[maxm]={0}, gi[maxm]={0},ma=0,mi=0,cc[maxm]={0},cnt=0; int cmp(const use&x,const use&y){return x.di>y.di;} void add(int u,int v,int vv){ next[++tot]=point[u];point[u]=tot;en[tot]=v;va[tot]=vv; next[++tot]=point[v];point[v]=tot;en[tot]=u;va[tot]=vv; } void pre(int u,int ff,int vv){ int i,j,v;fa[u][0]=ff; gi[u]=gi[ff]+vv;dep[u]=dep[ff]+1; for (i=1;i<up;++i) fa[u][i]=fa[fa[u][i-1]][i-1]; for (i=point[u];i;i=next[i]){ if ((v=en[i])==ff) continue; pre(v,u,va[i]); } } int lca(int u,int v){ int i;if (dep[u]<dep[v]) swap(u,v); for (i=up-1;i>=0;--i) if (dep[fa[u][i]]>=dep[v]) u=fa[u][i]; if (u==v) return u; for (i=up-1;i>=0;--i) if (fa[u][i]!=fa[v][i]){ u=fa[u][i];v=fa[v][i]; }return fa[u][0]; } int dfs(int u,int ff){ int i,j,v,sum;sum=cc[u];cc[u]=0; for (i=point[u];i;i=next[i]){ if ((v=en[i])==ff) continue; sum+=dfs(v,u); }if (sum==cnt) mi=max(mi,gi[u]-gi[fa[u][0]]); return sum; } int main(){ int n,m,i,j,u,v,vv,l,r,mid; scanf("%d%d",&n,&m); for (i=1;i<n;++i){scanf("%d%d%d",&u,&v,&vv);add(u,v,vv);} pre(1,0,0); for (i=1;i<=m;++i){ scanf("%d%d",&u,&v); ask[i].u=u;ask[i].v=v;ask[i].lc=lca(u,v); ask[i].di=gi[ask[i].u]-gi[ask[i].lc]+gi[ask[i].v]-gi[ask[i].lc]; ma=max(ma,ask[i].di); }l=0;r=ma;sort(ask+1,ask+m+1,cmp); while(l<r){ mid=l+r>>1;cnt=mi=i=0; while(ask[++i].di>mid&&i<=m){ ++cc[ask[i].u];++cc[ask[i].v]; cc[ask[i].lc]-=2;++cnt; }dfs(1,0); if (ma-mi<=mid) r=mid; else l=mid+1; }printf("%d ",l); }
这样可以做到nlogn，但是会被卡常数。听说网上有一种n的做法。（LL内的排序可以做到n，基数排序思想。）
总的来说，noip2015比2014进步了很多，没有出现实现上的失误，但是有一些想到的没有实现出来，失去了一些分数，还是有些可惜；还有一些思路上的失误；对于时间的把控还应加强。