NOIP2015|NOIP2015 提高组合集 NOIP2015提高组合集

NOIP 2015 提高组合集
D1 T1 神奇的幻方
题目让你干啥你就干啥，让你咋走你就咋走就完事儿了

#include #include #include #include #define N 50 using namespace std; struct Node { int x,y; }a[N*N]; int ans[N][N]; int main() { int n; cin >> n ; a[1].x=1; a[1].y=n/2+1; ans[1][n/2+1]=1; for(int i=2; i<=n*n; i++) { if(a[i-1].x==1&&a[i-1].y!=n) { ans[n][a[i-1].y+1]=i; a[i].x=n; a[i].y=a[i-1].y+1; } else if(a[i-1].x!=1&&a[i-1].y==n) { ans[a[i-1].x-1][1]=i; a[i].x=a[i-1].x-1; a[i].y=1; } else if(a[i-1].x==1&&a[i-1].y==n) { ans[a[i-1].x+1][a[i-1].y]=i; a[i].x=a[i-1].x+1; a[i].y=a[i-1].y; } else { if(!ans[a[i-1].x-1][a[i-1].y+1]) { ans[a[i-1].x-1][a[i-1].y+1]=i; a[i].x=a[i-1].x-1; a[i].y=a[i-1].y+1; } else { ans[a[i-1].x+1][a[i-1].y]=i; a[i].x=a[i-1].x+1; a[i].y=a[i-1].y; } } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) printf("%d ",ans[i][j]); puts(""); } }

D1 T2 信息传递
由题目的描述，我们发现这是一个基环内向森林。题目中问的是最多进行多少局，等价于求基环内向森林中所有基环的最小值。模拟即可。

#include #include #include #include #define N 200001 using namespace std; int a[N],f[N],v[N]; inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x; } int main() { int n=rd(),p,t,ans=0x7f7f7f7f; for(int i=1; i<=n; i++) a[i]=rd(); for(int i=1; i<=n; i++) { v[i]=1,t=i,p=a[i]; while(f[p]!=i) { if(f[p]!=0&&f[p]v[t]+1-v[p]) ans=v[t]+1-v[p]; } printf("%d",ans); return 0; }

D1 T3 斗地主
挖坑代填
D2 T1 跳石头
二分答案，二分出最大可能值，然后暴力验证

#include #include #include #include using namespace std; int L,n,m,a[50010]; inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x; } int check(int dist) { int last=0,cnt=0; for(int i=1; i<=n; i++) { if(a[i]-last>1; if(check(mid))l=mid; else r=mid; } printf("%d\n",l); }

D2 T2 子串
动态规划
f[i][j][k]表示当前：A串枚举到了i，B串枚举到了j，已经找到了k个串切使用了a[i]的方案数。
g[i][j][k]................................不管使不使用a[i]的方案数。
然后因为空间问题，f[i][j][k]，i压滚动。
转移sb

#include #include #include #include #define mod 1000000007 #define N 210 using namespace std; int f[2][N][N],g[2][N][N]; char s1[10010],s2[10010]; int main() { int n,m,k; cin >> n >> m >> k ; scanf("%s%s",s1+1,s2+1); int pre=1; g[1][0][0]=1; for(int i=1; i<=n; i++) { // puts("Fuck"); pre^=1; g[pre][0][0]=1; for(int j=1; j<=m; j++) { for(int l=1; l<=k; l++) { if(s1[i]==s2[j]) (f[pre][j][l]=g[pre^1][j-1][l-1]+f[pre^1][j-1][l])%=mod; else f[pre][j][l]=0; (g[pre][j][l]=f[pre][j][l]+g[pre^1][j][l])%=mod; // if(f[pre][j][l]) printf("%d %d %d\n",i,j,l); } } } printf("%d\n",g[pre][m][k]); return 0; }

D2 T3 运输计划
一眼二分答案，关键是怎么验证。首先，我们对于每次询问，都记录出：这个询问在不建立虫洞的情况下的长度。
紧接着根据我们二分出的mid，对于一次距离大于mid的询问树上查分，记录每条边被多少询问累计过。
然后我们边权下放到点权，对于每条被所有大于mid的询问经过的边，我们判断：是不是长度最长的询问减去这条边对应的边权在mid内即可。

#include #include #include #include #define N 300010 #define M 300010 using namespace std; int n,m; inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=nc(); return x; } struct Line {int x,y,v,lca; }L[M]; inline bool cmp(const Line &x,const Line &y) {return x.v=dep[y]) x=f[x][i]; } if(x==y) return x; for(int i=25; ~i; i--) { if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; } return f[x][0]; } void dfs_check(int pos,int fa) { for(int i=head[pos]; i; i=nxt[i]) if(to[i]!=fa) { dfs_check(to[i],pos); o[pos]+=o[to[i]]; } } bool check(int x) { memset(o,0,sizeof o); int begin; for(int i=1; i<=m; i++) if(L[i].v>x) {begin=i; break; } // printf("%d\n",begin); for(int i=begin; i<=m; i++) { o[L[i].x]++; o[L[i].y]++; o[L[i].lca]-=2; } dfs_check(1,1); for(int i=2; i<=n; i++) { if(o[i]>=m-begin+1&&L[m].v-top[i]<=x) { // printf("%d %d %d %d\n",i,L[m].v,top[i],x); return true; } } return false; } void test() { puts("Fuck"); for(int i=1; i<=n; i++) printf("%d ",top[i]); puts(""); } void test1() { puts("Shit"); for(int i=1; i<=m; i++) printf("%d ",L[i].v); puts(""); } int main() { n=rd(),m=rd(); int x,y,z; for(int i=1; i>1; if(check(mid)) r=mid-1; else l=mid+1; } // if(m==1&&L[1]) for(int i=r-1; i<=L[m].v; i++) { if(!check(i)) continue; printf("%d\n",i); return 0; } puts("0"); } /* 6 3 1 2 3 1 6 4 3 1 7 4 3 6 3 5 5 3 6 2 5 4 5 */

【NOIP2015|NOIP2015 提高组合集】转载于:https://www.cnblogs.com/ShuraK/p/9601909.html