【蒟蒻】NOIP的各种
好久不见,那啥在做一些可能很**的联赛题哎。。。怪我?
(重新拉到首页,Timeline有些错乱,轻拍)
UPDATE 20161114: 增加了NOIP2015&NOIP2013华容道&NOIP2011mayan游戏&更改部分格式
之前的链接:http://lujiaxin.is-programmer.com/posts/181542.html
NOIP2015:http://lujiaxin.is-programmer.com/posts/187893.html
广告时间~%%%xmc:http://scarlet.is-programmer.com/posts/207004.html
NOIP2015 DAY1 T1 神奇的幻方
暴力模拟
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #define LL long long #define D double using namespace std; struct REC { int x,y; }; int n; REC a[2500]; int ans[50][50]; int main() { freopen("magic.in","r",stdin); freopen("magic.out","w",stdout); scanf("%d",&n); memset(a,0,sizeof(a)); memset(ans,0,sizeof(ans)); a[1].x=1; a[1].y=(n+1)>>1; ans[a[1].x][a[1].y]=1; for (int i=2;i<=n*n;++i) { if (a[i-1].x==1 && a[i-1].y!=n) { a[i].x=n; a[i].y=a[i-1].y+1; ans[a[i].x][a[i].y]=i; continue; } else if (a[i-1].y==n && a[i-1].x!=1) { a[i].x=a[i-1].x-1; a[i].y=1; ans[a[i].x][a[i].y]=i; continue; } else if (a[i-1].x==1 && a[i-1].y==n) { a[i].x=a[i-1].x+1; a[i].y=a[i-1].y; ans[a[i].x][a[i].y]=i; continue; } else { if (ans[a[i-1].x-1][a[i-1].y+1]==0) { a[i].x=a[i-1].x-1; a[i].y=a[i-1].y+1; ans[a[i].x][a[i].y]=i; continue; } else { a[i].x=a[i-1].x+1; a[i].y=a[i-1].y; ans[a[i].x][a[i].y]=i; continue; } } } for (int i=1;i<=n;++i) { for (int j=1;j<n;++j) printf("%d ",ans[i][j]); printf("%d\n",ans[i][n]); } fclose(stdin); fclose(stdout); return 0; }
NOIP2015 DAY1 T2 信息传递
大力BFS
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <ctime> #define LL long long #define D double #define NN 200020 using namespace std; struct REC { int p,fa; }; int num[NN],ne[NN<<1],head[NN],v[NN<<1]; int n,x,tot,minn,tott; int vis[NN]; queue<REC> que; REC tmp; void Build(int xx,int yy) { ne[++tot]=head[xx]; v[tot]=yy; head[xx]=tot; } void BFS(int xx) { while (!que.empty()) que.pop(); vis[xx]=tott; num[xx]=1; tmp.p=xx; tmp.fa=0; que.push(tmp); while (!que.empty()) { REC h=que.front(); que.pop(); for (int i=head[h.p];i;i=ne[i]) { if (vis[v[i]]==tott) { minn=min(minn,num[h.p]+1-num[v[i]]); continue; } else if (!vis[v[i]]) { vis[v[i]]=tott; tmp.p=v[i]; tmp.fa=h.p; num[v[i]]=num[h.p]+1; que.push(tmp); } } } return; } int main() { freopen("message.in","r",stdin); freopen("message.out","w",stdout); scanf("%d",&n); tot=0; minn=0x7fffffff; memset(ne,0,sizeof(ne)); memset(head,0,sizeof(head)); memset(v,0,sizeof(v)); for (int i=1;i<=n;++i) { scanf("%d",&x); Build(i,x); } memset(vis,0,sizeof(vis)); tott=0; for (int i=1;i<=n;++i) if (!vis[i]) { tott++; BFS(i); } printf("%d\n",minn); fclose(stdin); fclose(stdout); return 0; }
NOIP2015 DAY1 T3 斗地主
考场上大暴力爆炸,难过
据说可以DP,蒟蒻只能DFS辣
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #define LL long long #define D double using namespace std; struct REC { int num,ne,cs; }; REC sum[50]; bool f[50],huojian; int x,y,tot,T,n,a[50],minn,one,two,three,four,maxx3,maxx4,checker[10]; void DFS(int pr,int tot) { if (tot-maxx3>minn) return; if (pr>17) { int ans=tot; checker[1]=one,checker[2]=two,checker[3]=three,checker[4]=four; //去4 带走尽量多的2个对子 若不足带走两个单牌 for (int w=1;w<=checker[4];++w) { if (checker[2]>=2) ans++,checker[2]-=2; else if (checker[1]>=2) ans++,checker[1]-=2; else if (checker[2]==1) ans++,checker[2]-=1; else ans++; } //去3 先带光对子,然后带光单牌 for (int w=1;w<=checker[3];++w) { if (checker[2]>0) ans++,checker[2]--; else if (checker[1]>0) ans++,checker[1]--; else ans++; } if (checker[1]>=2&&huojian) ans++,checker[1]-=2; ans+=checker[1]+checker[2]; minn=min(ans,minn); return; } if (a[pr]==0) {DFS(pr+1,tot); return;} if (pr<=14) { bool flag; int t; if (pr+4<=14) { flag=1,t=0; for (int w=pr;w<=pr+4;++w) if (a[w]<1) {flag=0; break;} if (flag) { for (int w=pr;w<=pr+3;++w) a[w]--; for (int w=pr+4;w<=14;++w) if (a[w]>=1) { a[w]--; t=w; DFS(pr,tot+1); } else break; for (int w=pr;w<=t;++w) a[w]++; } } //单顺子 if (pr+2<=14) { flag=1,t=0; for (int w=pr;w<=pr+2;++w) if (a[w]<2) { flag=0; break;} if (flag) { for (int w=pr;w<=pr+1;++w) a[w]-=2; for (int w=pr+2;w<=14;++w) if (a[w]>=2) { a[w]-=2; t=w; DFS(pr,tot+1); } else break; for (int w=pr;w<=t;++w) a[w]+=2; } } //双顺子 if (pr+1<=14) { flag=1,t=0; for (int w=pr;w<=pr+2;++w) if (a[w]<3) { flag=0; break;} if (flag) { a[pr]-=3; for (int w=pr+1;w<=14;++w) if (a[w]>=3) { a[w]-=3; t=w; DFS(pr,tot+1); } else break; for (int w=pr;w<=t;++w) a[w]+=3; } } //三顺子 } if (a[pr]>=4) { ++four; a[pr]-=4; DFS(pr,tot); --four; a[pr]+=4; }//4 if (a[pr]>=3) { ++three; a[pr]-=3; DFS(pr,tot); --three; a[pr]+=3;}//3 if (a[pr]>=2) { ++two; a[pr]-=2; DFS(pr,tot); --two; a[pr]+=2; }//2 if (a[pr]>=1) { ++one; a[pr]-=1; DFS(pr,tot); --one; a[pr]+=1; }//1 return; } int main() { freopen("landlords.in","r",stdin); freopen("landlords.out","w",stdout); scanf("%d%d",&T,&n); while (T--) { memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); minn=0x7fffffff; for (int i=1;i<=n;++i) { scanf("%d%d",&x,&y); if (x>=3) a[x]++; else { if (x==0) { if (y==1) a[16]++; else a[17]++;} else a[x+13]++; } } for (int i=3;i<=17;++i) { if (a[i]>=3) ++maxx3; if (a[i]>=4) ++maxx4; } maxx3+=maxx4*2; one=two=three=four=0; if (a[16]==1 && a[17]==1) huojian=1; else huojian=0; DFS(3,0); printf("%d\n",minn); } fclose(stdin); fclose(stdout); return 0; }
NOIP2015 DAY2 T1 跳石头
二分+$O(n)$贪心判断
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <queue> #include <set> #define NN 50010 using namespace std; int tot,l,r,len,n,m,a[NN],g[NN],ans; bool Check(int xx) { tot=0; int i=0; while (i<n+1) { i++; int sum=g[i]; while (sum<xx) { sum+=g[++i],tot++; if (tot>m) return 0; if (i>n+1) return 1; } } return 1; } int main() { freopen("stone.in","r",stdin); freopen("stone.out","w",stdout); scanf("%d%d%d",&len,&n,&m); a[0]=0; a[n+1]=len; for (int i=1;i<=n;++i) scanf("%d",&a[i]); for (int i=1;i<=n+1;++i) g[i]=a[i]-a[i-1]; l=0; r=len; ans=0; while (l<=r) { int mid=(l+r)>>1; if (Check(mid)) l=mid+1,ans=mid; else r=mid-1; } printf("%d\n",ans); fclose(stdin); fclose(stdout); return 0; }
NOIP2015 DAY2 T2 子串
DP,但是要加滚动数组防MLE
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #define mod 1000000007 #define LL long long using namespace std; LL f[3][1010][210],ans[3][1010][210]; int t,n,m,k; char a[1010],b[210]; int main() { freopen("substring.in","r",stdin); freopen("substring.out","w",stdout); scanf("%d%d%d",&n,&m,&k); scanf("%s",a+1); scanf("%s",b+1); t=0; for (int i=0;i<=n;++i) ans[0][i][0]=1; for (int w=1;w<=k;++w) { t^=1; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (a[i]==b[j]) { f[t][i][j]=(f[t][i-1][j-1]+ans[t^1][i-1][j-1])%mod; ans[t][i][j]=(f[t][i][j]+ans[t][i-1][j])%mod; } else f[t][i][j]=0,ans[t][i][j]=ans[t][i-1][j]; for (int i=0;i<=n;++i) ans[t^1][i][0]=0; } printf("%lld\n",ans[t][n][m]); fclose(stdin); fclose(stdout); return 0; }
NOIP2015 DAY2 T3 运输计划
树上乱搞+二分答案判断
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <queue> #define LL long long #define INF 0x3f3f3f3f using namespace std; #define NN 300100 int read() { int xx=0,ff=1; char ch; for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch == '-') ff=-1; for (;ch>='0';ch=getchar()) xx=xx*10+ch-'0'; xx*=ff; return xx; } int sz=0, fa[NN][20], deep[NN], pos[NN], dis[NN], tot=0, head[NN], n, m; int sum=0, x[NN], y[NN], z[NN], l, r, ans, maxx2=0, val[NN]; struct E { int v,w,ne; }e[NN<<1]; struct S { int u,v,d,lca; }s[NN]; void Build(int xx,int yy,int zz) { e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz; e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].w=zz; } void DFS(int xx) { pos[++sz]=xx; for (int i=1;i<=17;++i) if ((1<<i)<=deep[xx]) fa[xx][i]=fa[fa[xx][i-1]][i-1]; for (int i=head[xx];i;i=e[i].ne) if (e[i].v != fa[xx][0]) { deep[e[i].v] = deep[xx]+1, fa[e[i].v][0] = xx, dis[e[i].v] = dis[xx] + e[i].w, val[e[i].v] = e[i].w; DFS(e[i].v); } } int LCA(int xx,int yy) { if (deep[xx]<deep[yy]) swap(xx,yy); int tmp=deep[xx]-deep[yy]; for (int i=0;i<=17;++i) if (tmp>>i&1) xx=fa[xx][i]; for (int i=17;i>=0;--i) if (fa[xx][i] != fa[yy][i]) xx=fa[xx][i], yy=fa[yy][i]; return xx==yy?xx:fa[xx][0]; } int tmp[NN]; bool Check(int xx) { int cnt=0, lim=0; memset(tmp,0,sizeof(tmp)); for (int i=1;i<=m;++i) if (s[i].d > xx) { ++tmp[s[i].u], ++tmp[s[i].v], tmp[s[i].lca]-=2; lim = max(s[i].d-xx, lim); cnt++; } if (!cnt) return 1; for (int i=n;i>1;--i) tmp[fa[pos[i]][0]]+=tmp[pos[i]]; for (int i=2;i<=n;++i) if (val[i] >= lim && tmp[i]==cnt) return 1; return 0; } int main() { n=read(), m=read(); for (int i=1;i<n;++i) { x[i]=read(), y[i]=read(), z[i]=read(), sum+=z[i]; Build(x[i],y[i],z[i]); } dis[1]=0, deep[1]=1, fa[1][0]=0; DFS(1); for (int i=1;i<=m;++i) { s[i].u=read(), s[i].v=read(); s[i].lca=LCA(s[i].u, s[i].v); s[i].d=dis[s[i].u] + dis[s[i].v] - 2*dis[s[i].lca]; } l=0, r=sum; while (l<=r) { int mid=(l+r)>>1; if (Check(mid)) ans=mid, r=mid-1; else l=mid+1; } printf("%d\n", ans); return 0; }
NOIP2014 DAY1 T3 飞扬的小鸟
唔,其实比赛的时候想到了标算,但至今不知道当时怎么死在了75分
然而重新写一遍就A了是smg!!!(咆哮
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> #define INF 0x7fffffff #define NN 10010 #define MM 1010 using namespace std; int n,m,k,tot,ans,p; int x[NN],y[NN],l[NN],r[NN],dp[NN][MM]; bool f[NN][MM],ff,fl[NN]; int main() { scanf("%d%d%d",&n,&m,&k); memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); memset(fl,0,sizeof(fl)); for (int i=1;i<=n;++i) { scanf("%d%d",&x[i],&y[i]); } for (int i=1;i<=k;++i) { scanf("%d",&p); scanf("%d%d",&l[p],&r[p]); fl[p]=1; } memset(f,0,sizeof(f)); memset(dp,0x3f,sizeof(dp)); tot=0; for (int i=1;i<=m;++i) f[0][i]=1,dp[0][i]=0; for (int i=1;i<=n;++i) { for (int j=x[i]+1;j<=m;++j) if (f[i-1][j-x[i]]) f[i][j]=1,dp[i][j]=min(dp[i][j],dp[i-1][j-x[i]]+1); for (int j=x[i]+1;j<=m;++j) if (f[i][j-x[i]]) f[i][j]=1,dp[i][j]=min(dp[i][j],dp[i][j-x[i]]+1); for (int j=1;j<=m-y[i];++j) if (f[i-1][j+y[i]]) f[i][j]=1,dp[i][j]=min(dp[i][j],dp[i-1][j+y[i]]); for (int j=m-x[i]+1;j<=m;++j) { if (f[i-1][j]) dp[i][m]=min(dp[i][m],dp[i-1][j]+1),f[i][m]=1; if (f[i][j]) dp[i][m]=min(dp[i][m],dp[i][j]+1),f[i][m]=1; } if (fl[i]) { for (int j=1;j<=l[i];++j) f[i][j]=0; for (int j=r[i];j<=m;++j) f[i][j]=0; } ff=0; for (int j=1;j<=m;++j) if (f[i][j]) { ff=1; break;} if (!ff) { puts("0"); printf("%d\n",tot); return 0; } else if (fl[i]) tot++; } ans=INF; for (int i=1;i<=m;++i) if (f[n][i]) ans=min(ans,dp[n][i]); puts("1"); printf("%d\n",ans); return 0; }
NOIP2013 DAY1 T3 货车运输
冰茶几+LCA+DFS+乱搞什么的肯定能做出
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; struct REC {int x,y,v;}; REC a[50010]; int head[20010],ne[20010],u[20010],w[20010],father[20010],fa[10010][20],dis[10010][20],deep[10010]; bool used[10010]; int n,m,xx,yy,total,tot,q,qx,qy; void Insert(int xx,int yy,int zz) { ne[++total]=head[xx]; head[xx]=total; u[total]=yy; w[total]=zz; ne[++total]=head[yy]; head[yy]=total; u[total]=xx; w[total]=zz; } int find_father(int xx) { return father[xx]==xx?xx:father[xx]=find_father(father[xx]); } bool cmp(const REC xx,const REC yy) { return xx.v>yy.v; } void DFS(int xx) { used[xx]=1; for (int i=1;i<=16;++i) { if (deep[xx]<(1<<i)) break; fa[xx][i]=fa[fa[xx][i-1]][i-1]; dis[xx][i]=min(dis[xx][i-1],dis[fa[xx][i-1]][i-1]); } for (int i=head[xx];i;i=ne[i]) { if (used[u[i]]) continue; fa[u[i]][0]=xx; dis[u[i]][0]=w[i]; deep[u[i]]=deep[xx]+1; DFS(u[i]); } return; } int LCA(int xx,int yy) { if (deep[xx]<deep[yy]) swap(xx,yy); int tmp=deep[xx]-deep[yy]; for (int i=0;i<=16;++i) if ((1<<i)&tmp) xx=fa[xx][i]; for (int i=16;i>=0;--i) if (fa[xx][i]!=fa[yy][i]) { xx=fa[xx][i]; yy=fa[yy][i]; } if (xx==yy) return xx; return fa[xx][0]; } int ASK(int xx,int yy) { int minn=0x7fffffff; int tmp=deep[xx]-deep[yy]; for (int i=0;i<=16;++i) { if (tmp&(1<<i)) { minn=min(minn,dis[xx][i]); xx=fa[xx][i]; } } return minn; } int main() { memset(dis,127/3,sizeof(dis)); scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) father[i]=i; for (int i=1;i<=m;++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v); sort(a+1,a+1+m,cmp); total=0; for (int i=1;i<=m;++i) { int xx=find_father(a[i].x),yy=find_father(a[i].y); if (xx!=yy) { father[xx]=yy; Insert(a[i].x,a[i].y,a[i].v); ++tot; if (tot==n-1) break; } } for (int i=1;i<=n;++i) if (!used[i]) DFS(i); scanf("%d",&q); for (int i=1;i<=q;++i) { scanf("%d%d",&qx,&qy); if (find_father(qx)!=find_father(qy)) puts("-1"); else { int tmp=LCA(qx,qy); printf("%d\n",min(ASK(qx,tmp),ASK(qy,tmp))); } } return 0; }
NOIP2013 DAY2 T1 同余方程
数学题,%%%Scarlet数论大神
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #define LL long long using namespace std; LL a,b,x,y,ans; LL GCD(LL a,LL b,LL &xx,LL &yy) { if (!b) { xx=1; yy=0; return a; } else { LL sum=GCD(b,a%b,xx,yy); LL tmp=xx; xx=yy; yy=tmp-(a/b)*yy; return sum; } } int main() { scanf("%lld%lld",&a,&b); LL tmp=GCD(a,b,x,y); ans=x%b; while (x<0) x+=b; printf("%lld\n",x); return 0; }
NOIP2013 DAY2 T2 花匠
DP一眼题,然后想着把O(n^2)弄到O(n)就可以了
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #define NN 100100 using namespace std; int f[NN][3],a[NN]; int n; int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]); f[1][0]=f[1][1]=1; for (int i=1;i<n;++i) { if (a[i]>a[i+1]) { f[i+1][0]=f[i][0]; f[i+1][1]=max(f[i][1],f[i][0]+1); } else if (a[i]<a[i+1]) { f[i+1][1]=f[i][1]; f[i+1][0]=max(f[i][1]+1,f[i][0]); } else { f[i+1][1]=f[i][1]; f[i+1][0]=f[i][0]; } } printf("%d\n",max(f[n][1],f[n][0])); return 0; }
NOIP2013 DAY2 T3 华容道
大力BFS
#include <bits/stdc++.h> using namespace std; const int NN = 40, INF = 0x3f3f3f3f; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; struct STK { int x,y,d; }stk[15]; struct P { int x,y; }; queue <P> que; queue <STK> QUE; int n,m,EX,EY,SX,SY,TX,TY,Q,stk_n; int mp[NN][NN],dis[NN][NN],st[NN][NN][5][5],dp[NN][NN][5]; bool vis[NN][NN][5]; void Pre(int sx,int sy) { stk_n=0; for (int i=0;i<4;++i) { int tx=sx+dx[i],ty=sy+dy[i]; if (tx>0 && ty>0 && tx<=n && ty<=m && mp[tx][ty]) stk[++stk_n].x=tx, stk[stk_n].y=ty, stk[stk_n].d=i; } for (int _=stk_n;_;--_) { while(!que.empty()) que.pop(); memset(dis,0x3f,sizeof(dis)); int ttx=stk[_].x,tty=stk[_].y,ttd=stk[_].d; dis[ttx][tty] = 0; que.push((P){ttx,tty}); while (!que.empty()) { int tx=que.front().x,ty=que.front().y; que.pop(); for (int i=0;i<4;++i) { int xx=tx+dx[i],yy=ty+dy[i]; if (xx>0 && yy>0 && xx<=n && yy<=m) if (mp[xx][yy] && (xx!=sx||yy!=sy) && dis[xx][yy] == INF) { dis[xx][yy] = dis[tx][ty] + 1; que.push((P){xx,yy}); } } } for (int i=0;i<4;++i) { int xx = sx+dx[i], yy = sy+dy[i]; if (xx>0 && yy>0 && xx<=n && yy<=m) if (mp[xx][yy] && (xx!=ttx||yy!=tty) && dis[xx][yy] != INF) st[sx][sy][ttd][i] = dis[xx][yy]; } } } void Pre_BFS() { memset(dis,0x3f,sizeof(dis)); while (!que.empty()) que.pop(); dis[EX][EY] = 0; que.push((P){EX,EY}); while (!que.empty()) { int tx = que.front().x, ty = que.front().y; que.pop(); for (int i=0;i<4;++i) { int xx = tx+dx[i], yy = ty+dy[i]; if (xx>0 && yy>0 && xx<=n && yy<=m && (xx!=SX || yy!=SY)) if (mp[xx][yy] && dis[xx][yy] == INF) { dis[xx][yy] = dis[tx][ty] + 1; que.push((P){xx,yy}); } } } } int BFS() { int ans = 0; if (TX==SX && TY==SY) return 0; Pre_BFS(); memset(dp,0x3f,sizeof(dp)); while (!QUE.empty()) QUE.pop(); for (int i=0;i<4;++i) { int xx = SX+dx[i], yy = SY+dy[i]; if (xx>0 && yy>0 && xx<=n && yy<=m && mp[xx][yy] && dis[xx][yy] != INF) { dp[SX][SY][i] = dis[xx][yy]; QUE.push((STK){SX,SY,i}); vis[SX][SY][i] = 1; } } while (!QUE.empty()) { int tx=QUE.front().x, ty=QUE.front().y, td=QUE.front().d; QUE.pop(); vis[tx][ty][td] = 0; int xx=tx+dx[td], yy=ty+dy[td]; if (dp[xx][yy][(td+2)%4] > dp[tx][ty][td] + 1) { dp[xx][yy][(td+2)%4] = dp[tx][ty][td] + 1; if (!vis[xx][yy][(td+2)%4]) { vis[xx][yy][(td+2)%4] = 1; QUE.push((STK){xx,yy,(td+2)%4}); } } for (int i=0;i<4;++i) { xx=tx+dx[i],yy=ty+dy[i]; if (i!=td && xx>0 && yy>0 && xx<=n && yy<=m && mp[xx][yy] && st[tx][ty][td][i] != INF) if (dp[tx][ty][i] > dp[tx][ty][td] + st[tx][ty][td][i]) { dp[tx][ty][i] = dp[tx][ty][td] + st[tx][ty][td][i]; if (!vis[tx][ty][i]) vis[tx][ty][i] = 1, QUE.push((STK){tx,ty,i}); } } } ans = INF; for (int i=0;i<4;++i) ans = min(ans,dp[TX][TY][i]); return (ans == INF)?-1:ans; } int main() { scanf("%d%d%d",&n,&m,&Q); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) scanf("%d",&mp[i][j]); memset(st,0x3f,sizeof(st)); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (mp[i][j]) Pre(i,j); while (Q--) { scanf("%d%d%d%d%d%d",&EX,&EY,&SX,&SY,&TX,&TY); printf("%d\n",BFS()); } return 0; }
NOIP2012 DAY1 T3 开车旅行
嗯,就是倍增
先用set预处理出每个城市的最近与次近
然后令g[i][j]为从i点走2^j个轮回(注意是轮回,不是步)后的位置,f[i][j][0]为从i点走2^j个轮回后A走过的距离,f[i][j][1]为从i点走2^j个轮回后B走过的距离。
那么很容易推出:
g[i][j]=g[g[i][j-1]][j-1];
f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];
f[i][j][1]=f[i][j-1][0]+f[g[i][j-1]][j-1][1];
然后我会告诉你这样就好了哒?
#include <iostream> #include <cstdio> #include <set> #include <cstring> #include <cstdlib> #include <cmath> #define LL long long #define NN 100010 using namespace std; struct REC { int h,num; bool operator <(const REC xx) const{ return h<xx.h; } }; REC a[NN]; set <REC> s; set <REC> ::iterator it; LL f[NN][21][2]; int ne[NN][2],dis[NN][2],g[NN][21]; int n,m,x0,s0,ans=0; void Update(REC xx, REC yy) { if (!ne[xx.num][0]) { ne[xx.num][0]=yy.num; dis[xx.num][0]=abs(xx.h-yy.h); } else if (abs(xx.h-yy.h)<dis[xx.num][0] || (abs(xx.h-yy.h)==dis[xx.num][0] && yy.h<a[ne[xx.num][0]].h)) { ne[xx.num][1]=ne[xx.num][0]; dis[xx.num][1]=dis[xx.num][0]; ne[xx.num][0]=yy.num; dis[xx.num][0]=abs(xx.h-yy.h); } else if (abs(xx.h-yy.h)<dis[xx.num][1] || (abs(xx.h-yy.h)==dis[xx.num][1] && yy.h<a[ne[xx.num][1]].h)) ne[xx.num][1]=yy.num,dis[xx.num][1]=abs(xx.h-yy.h); else if (!ne[xx.num][1]) ne[xx.num][1]=yy.num,dis[xx.num][1]=abs(xx.h-yy.h); return ; } void Query(int ss,int xx,LL &disa,LL &disb) { for (int j=20;j>=0;--j) { if (f[ss][j][0]+f[ss][j][1]<=xx && g[ss][j]) { disa+=f[ss][j][0]; disb+=f[ss][j][1]; xx-=(f[ss][j][0]+f[ss][j][1]); ss=g[ss][j]; } } if (ne[ss][1] && dis[ss][1]<=xx) disa+=dis[ss][1]; } int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i].h),a[i].num=i; for (int i=n;i>=1;i--) { s.insert(a[i]); it=s.find(a[i]); if (it!=s.begin()) { it--; Update(a[i],*it); if (it!=s.begin()) { it--; Update(a[i],*it); it++; } it++; } if ((++it)!=s.end()) { Update(a[i],*it); it++; if (it!=s.end()) Update(a[i],*it); it--; } it--; } for (int i=1;i<=n;++i) { g[i][0]=ne[ne[i][1]][0]; f[i][0][0]=dis[i][1]; f[i][0][1]=dis[ne[i][1]][0]; } for (int j=1;j<=20;++j) for (int i=1;i<=n;++i) { g[i][j]=g[g[i][j-1]][j-1]; f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0]; f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1]; } scanf("%d",&x0); LL ansa=1e15,ansb=0; for (int i=1;i<=n;++i) { LL disa=0,disb=0; Query(i,x0,disa,disb); if (disb&&(!ans||ansa*disb>ansb*disa)) { ans=i; ansa=disa,ansb=disb; } } printf("%d\n",ans); scanf("%d",&m); while (m--) { scanf("%d%d",&s0,&x0); LL disa=0,disb=0; Query(s0,x0,disa,disb); printf("%lld %lld\n",disa,disb); } return 0; }
NOIP2012 DAY2 T2 借教室
鬼畜用了二分答案,其实还是8错滴~~~感觉比线段树好写一点哎
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #define NN 1000100 using namespace std; int n,m,l,r,sum; int rr[NN],d[NN],s[NN],t[NN],a[NN]; bool f,ff; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&rr[i]); for (int i=1;i<=m;++i) scanf("%d%d%d",&d[i],&s[i],&t[i]); l=1; r=m+1; f=1; while (l<r) { ff=0; int mid=(l+r)>>1; for (int i=l;i<=mid;++i) { a[s[i]]+=d[i]; a[t[i]+1]-=d[i]; } sum=0; for (int i=1;i<=n;++i) { sum+=a[i]; if (sum>rr[i]) { f=0; ff=1; break; } } if (ff) { r=mid; for (int i=l;i<=mid;++i) { a[s[i]]-=d[i]; a[t[i]+1]+=d[i]; } } else l=mid+1; } if (f) puts("0"); else { puts("-1"); printf("%d\n",l); } return 0; }
NOIP2012 DAY2 T3 疫情控制
呀,noip膜你赛竟然考真·noip题,不过不然不会这么早去做它了QAQ
二分+贪心判断
先向上移动到首都下一层的几个点,然后某个点有好几个军队的话,就要考虑到首都下一层可能有几个点还是空着的,就是要通过首都移动过去,排序贪心什么的
(↑_↑上面的好混乱)
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #define NN 50010 #define LL long long using namespace std; int head[NN*2],ne[NN*2],u[NN*2],w[NN*2]; bool leaf[NN],tmpp[NN],used[NN]; LL times[NN],diss[NN],dis[NN]; int mark[NN],army[NN],ances[NN],n,m,fa[NN],Q[NN],tmp1[NN],tmp2[NN]; int x,y,z,t,hh,tott; LL r,tot,l; void Build(int x,int y,int z) { ne[++tott] = head[x]; head[x] = tott; u[tott] = y; w[tott] = z; ne[++tott] = head[y]; head[y] = tott; u[tott] = x; w[tott] = z; } bool cmp1(const int xx,const int yy) { return diss[xx]<diss[yy]; } bool cmp2(const int xx,const int yy) { return dis[army[xx]]>dis[army[yy]]; } bool Check(LL mid) { memset(times,-1,sizeof(times)); memset(used,0,sizeof(used)); memcpy(tmpp,leaf,sizeof(tmpp)); for (int i=n;i>=1;--i) { int h=Q[i]; if (mark[h]&&dis[h]>mid) times[h]=mid; times[fa[h]]=max(times[fa[h]],times[h]-diss[h]); if (times[h]>=0) tmpp[h]=1; if (!tmpp[h]) tmpp[fa[h]]=0; } for (int i=1;i<=m;++i) if (dis[army[i]]<=mid) used[i]=1; tmp1[0]=tmp2[0]=0; for (int i=head[1];i;i=ne[i]) if (!tmpp[u[i]]) tmp1[++tmp1[0]]=u[i]; for (int i=1;i<=m;++i) if (used[i]) tmp2[++tmp2[0]]=i; sort(tmp1+1,tmp1+1+tmp1[0],cmp1); sort(tmp2+1,tmp2+1+tmp2[0],cmp2); int jj=1; for (int i=1;i<=tmp2[0];++i) { if (!tmpp[ances[army[tmp2[i]]]]) tmpp[ances[army[tmp2[i]]]]=1; else if (diss[tmp1[jj]]+dis[army[tmp2[i]]]<=mid) tmpp[tmp1[jj]]=1; while (jj<=tmp1[0] && tmpp[tmp1[jj]]) jj++; if (jj>tmp1[0]) return 1; } return 0; } queue <int> que; void BFS(int xx) { hh=1; t=0; Q[++t]=xx; while (hh<=t) { int h=Q[hh++]; leaf[h]=0; for (int i=head[h];i;i=ne[i]) { int v=u[i]; if (v==fa[h]) continue; fa[v]=h; dis[v]=dis[h]+w[i]; diss[v]=w[i]; if (h!=xx) ances[v]=ances[h]; else ances[v]=v; leaf[h]=1; Q[++t]=v; } } } int main() { scanf("%d",&n); tott = 0; tot=1; for (int i=1;i<n;++i) { scanf("%d%d%d",&x,&y,&z); Build(x,y,z); tot+=(LL)z; } scanf("%d",&m); memset(mark,0,sizeof(mark)); for (int i=1;i<=m;++i) scanf("%d",&army[i]),mark[army[i]]=1; BFS(1); l=0; r=tot; while (l<r-1) { LL mid=(l+r)>>1; if (Check(mid)) r=mid; else l=mid; } if (r==tot) puts("-1"); else printf("%lld\n",r); return 0; }
NOIP2011 DAY1 T2 选择客栈
这真是斯波题啊,O(nk)乱搞表示毫无压力
就是倒着处理一遍,然后正着摞一遍
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #define NN 200010 using namespace std; int n,k,p; int a[NN],b[NN],po[NN],f[NN][55]; long long ans; int main() { scanf("%d%d%d",&n,&k,&p); for (int i=1;i<=n;++i) scanf("%d%d",&a[i],&b[i]); memset(f,0,sizeof(f)); po[n+1]=n+1; for (int i=n;i>=1;--i) { if (b[i]<=p) po[i]=i; else po[i]=po[i+1]; for (int j=0;j<k;++j) f[i][j]=f[i+1][j]; f[i][a[i]]++; } ans=0; for (int i=1;i<=n;++i) { if (po[i]!=i) { ans+=f[po[i]][a[i]]; } if (po[i]==i) { ans+=f[i+1][a[i]]; } } printf("%lld\n",ans); return 0; }
NOIP2011 DAY1 T3 Mayan游戏
DFS
注意Fall 和 Remove两个函数就可以了
NOIP竟然还给了-1两个点,自己还是too young,一开始都不看好题目
#include <bits/stdc++.h> using namespace std; const int NN = 10; int C[NN][NN],cnt[15],n,lin[NN][5]; bool FLAG=0; bool Remove(int c[][NN]) { bool pos[10][10]={0},flag = 0; for (int i=1;i<=5;++i) for (int j=1;j<=7;++j) if (c[i][j]) { if (i<=3 && c[i][j] == c[i+1][j] && c[i][j] == c[i+2][j]) pos[i][j] = pos[i+1][j] = pos[i+2][j] = 1; if (j<=5 && c[i][j] == c[i][j+1] && c[i][j] == c[i][j+2]) pos[i][j] = pos[i][j+1] = pos[i][j+2] = 1; } for (int i=1;i<=5;++i) for (int j=1;j<=7;++j) if (pos[i][j]) c[i][j] = 0, flag = 1; return flag; } void Fall(int c[][NN]) { int k,tmp; for (int i=1;i<=5;++i) { k=0; for (int j=1;j<=7;++j) { tmp=c[i][j], c[i][j] = 0; if (tmp) c[i][++k] = tmp; } } } bool Check(int c[][NN]) { for (int i=1;i<=5;++i) for (int j=1;j<=7;++j) if (c[i][j]) return 0; return 1; } void DFS(int k,int c[][NN]) { if (k>n) { if (Check(c)) { for (int i=1;i<=n;++i) { if (lin[i][2]) printf("%d %d -1\n",lin[i][0],lin[i][1]-1); else printf("%d %d 1\n",lin[i][0]-1,lin[i][1]-1); } FLAG = 1; } return; } int tmp[10][10]={0}; memset(cnt,0,sizeof cnt); for (int i=1;i<=5;++i) for (int j=1;j<=7;++j) ++ cnt[c[i][j]]; for (int i=1;i<=10;++i) if (cnt[i] == 1 || cnt[i] == 2) return; for (int i=1;i<5;++i) for (int j=1;j<=7;++j) { if (c[i][j] != c[i+1][j]) { memcpy(tmp,c,sizeof(tmp)); lin[k][0]=i, lin[k][1]=j, lin[k][2]=!c[i][j]; swap(tmp[i][j],tmp[i+1][j]); Fall(tmp); while (Remove(tmp)) Fall(tmp); DFS(k+1,tmp); if (FLAG) return; } } } int main() { scanf("%d",&n); for (int i=1;i<=5;++i) for (int j=1;;++j) { scanf("%d",&C[i][j]); if (!C[i][j]) break; } DFS(1,C); if (!FLAG) puts("-1"); return 0; }
NOIP2011 DAY2 T1 计算系数
其实就是C(k,n)*a^n*b*m就好了
然后求C(k,n)的时候其实挺简单的啊。。。(逆元其实挺好玩的辣)
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #define mod 10007 using namespace std; long long ans; int a,b,k,n,m; long long ny[1010]; long long ksm(int xx,int yy) { long long tmp=1,x=xx; while (yy) { if (yy&1) tmp=tmp*x%mod; yy>>=1; x=x*x%mod; } return tmp; } int main() { scanf("%d%d%d%d%d",&a,&b,&k,&n,&m); ans=1; for (int i=1;i<=k;++i) ny[i]=ksm(i,mod-2); for (int i=k;i>=(k-n+1);--i) ans=(ans*i)%mod; for (int i=1;i<=n;++i) ans=(ans*ny[i])%mod; ans=(ans*ksm(a,n)%mod)*ksm(b,m)%mod; printf("%lld\n",ans); return 0; }
NOIP2010 T3 关押罪犯
并查集水题
排序的时候n和m打反了,调了老久都没调出,感觉可以自爆了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define NN 20010 #define MM 100010 using namespace std; struct REC { int x,y,w; }; int father[NN],e[NN]; REC a[MM]; int n,m; bool cmp(const REC xx,const REC yy) { return xx.w>yy.w; } int find_father(int xx) { if (father[xx]==xx) return xx; int fx=father[xx]; father[xx]=find_father(fx); return father[xx]; } void doing(int xx,int yy) { int xa=find_father(xx),ya=find_father(yy); father[xa]=ya; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w); for (int i=1;i<=n;++i) father[i]=i; memset(e,0,sizeof(e)); sort(a+1,a+1+m,cmp); for (int i=1;i<=m;++i) { int xa=find_father(a[i].x),ya=find_father(a[i].y); if (xa==ya) { printf("%d\n",a[i].w); return 0; } if (e[a[i].x]==0 && e[a[i].y]==0){ e[a[i].x]=a[i].y; e[a[i].y]=a[i].x; continue;} if (e[a[i].x]==0) e[a[i].x]=a[i].y; if (e[a[i].y]==0) e[a[i].y]=a[i].x; doing(e[a[i].x],a[i].y); doing(e[a[i].y],a[i].x); } puts("0"); return 0; }
NOIP2008 T4 双栈排序
DFS染色一下什么的,然后就乱搞
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <stack> #define NN 1010 using namespace std; stack<int> stacka,stackb; bool ff; int f[NN],a[NN],colour[NN]; bool e[NN][NN]; int n,k; void work(int xx,int yy) { colour[xx]=yy; for (int i=1;i<=n;++i) if (e[xx][i]) { if (yy==colour[i]) { ff=1; return; } if (colour[i]==0) work(i,3-yy); if (ff) return; } } int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]); f[n+1]=0x7fffffff; for (int i=n;i>=1;--i) f[i]=min(a[i],f[i+1]); for (int i=1;i<=n;++i) for (int j=i+1;j<=n;++j) { if (a[i]<a[j] && f[j+1]<a[i]) e[i][j]=e[j][i]=1; } memset(colour,0,sizeof(colour)); ff=0; for (int i=1;i<=n;++i) if (colour[i]==0) work(i,1); if (ff) { puts("0"); return 0; } k=1; for (int i=1;i<=n;++i) { if (colour[i]==1) { stacka.push(a[i]); printf("a "); } else { stackb.push(a[i]); printf("c "); } while (((!stacka.empty())&&stacka.top()==k) || ((!stackb.empty())&&stackb.top()==k)) { if ((!stacka.empty())&&stacka.top()==k) { printf("b "); stacka.pop(); } else { printf("d "); stackb.pop(); } k++; } } puts(""); return 0; }
(感觉好像未完待续。。。)
2022年9月08日 21:41
The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student, and the economics subject paper-1 AP 1st Inter Economics Model Paper and paper-2 important questions with suggestions are available through AP Jr and Sr inter Economics Model Paper 2023 Pdf with guess paper.