首页 > 代码库 > NOIP2015D2总结
NOIP2015D2总结
今天居然考了一套题。NOIP2015D2。
这是当年的战绩：
360的一等奖线。好强啊！
之前做过2015的D1，但我确实不会做landlord……今天曾祥瑞学长和林可学姐都来了，他们说，朱昶宇AK，看见landlord时蒙了便按照自己平时的套路来打程序，看见transport时蒙了便暴力乱搞……
我不想说，经过了不懈的努力，我才让transport成了95，而他轻轻松松暴力乱搞过了最后那个防AK点。我不想说，当时全省只有他一个人A了这道题。
太强了！
好的，现在我们该静一静了。
第一题，stone，典型的二分答案例题（套贪心），但是二分策略确实很伤人头脑。
1 #define PN "stone" 2 #include <cstdio> 3 int l, n, m, d[50010]; 4 int main() { 5 freopen(PN".in","r",stdin); 6 freopen(PN".out","w",stdout); 7 scanf("%d%d%d",&l,&n,&m); 8 d[0]=0;for( int i = 1; i <= n; i++ ) scanf("%d",&d[i]);d[n+1]=l; 9 int lf=1,rg=l;10 while(lf<=rg) {11 int mid=(lf+rg)>>1, pos=0, num=0;12 for( int i = 1; i <= n+1; i++ ) if(d[i]-d[pos]>=mid) pos=i;else num++;13 if(num<=m) lf=mid+1;14 else rg=mid-1;//?15 }16 printf("%d\n",rg);17 return 0;18 }
第二题，那啥，很明显是可以套路化的，不知道难在哪里。
1 #define PN "substring" 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 int n, m, p, f[2][210][210]; 6 char A[1010], B[210]; 7 inline int add(int a,int b) {static int MOD=1e9+7;if(a-MOD+b>0) return a-MOD+b;return a+b;} 8 int main() { 9 freopen(PN".in","r",stdin);10 freopen(PN".out","w",stdout);11 scanf("%d%d%d%s%s",&n,&m,&p,A,B);12 memset(f,0,sizeof(f));f[0][0][0]=1;13 for( int i = 1; i <= n; i++ ) for( int j = std::min(i,m); j >= 0; j-- ) for( int k = std::min(i,p); k >= 0; k-- ) {14 f[0][j][k]=add(f[1][j][k],f[0][j][k]);15 if(j!=0&&A[i-1]==B[j-1]) f[1][j][k]=add(add(f[1][j-1][k],f[1][j-1][k-1]),f[0][j-1][k-1]);16 else f[1][j][k]=0;17 }18 printf("%d\n",add(f[0][m][p],f[1][m][p]));19 return 0;20 }
第三题，transport，这道题理论上需要先处理处每个方案的LCA，以及这一段的距离。然后，我们就可以愉快的二分答案。找出那些超了限额的方案，看他们所共有的线路。最值减最值，与mid比较一番，就可以愉快的得出结果了。但是n,m<=300000伤不起啊。
好的，不多说了。最后一题挂个代码吧。
1 #define PN "transport" 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 template<class T>inline void readin(T &res) { 7 static char ch;while((ch=getchar())<‘0‘||ch>‘9‘); 8 res=ch-48;while((ch=getchar())>=‘0‘&&ch<=‘9‘)res=(res<<1)+(res<<3)+ch-48; 9 }10 11 const int N = 300000+10;12 const int M = 300000+10;13 struct EDGE {int v, upre, w;}g[N];14 int head[N], ne=0;15 inline void adde(int u,int v,int w) {g[++ne]=(EDGE){v,head[u],w},head[u]=ne;}16 17 int n, m, u, v, w, s, t;18 19 const int S = 19;20 int dep[N], anc[N][S+1], dis[N], edg[N], A[M], B[M], C[M], LEN[M];21 void DFS(int u,int fa) {22 anc[u][0]=fa;23 for( int j = 1; j <= S; j++ ) anc[u][j]=anc[anc[u][j-1]][j-1];24 for( int i = head[u]; i; i = g[i].upre ) {25 int v=g[i].v;26 if(v==fa) continue;27 edg[v]=g[i].w;dep[v]=dep[u]+1;dis[v]=dis[u]+g[i].w;DFS(v,u);28 }29 }30 31 int lca(int u,int v) {32 if(dep[u]<dep[v]) swap(u,v);33 for( int t=dep[u]-dep[v],p=0; t; t>>=1,p++ ) if(t&1) u=anc[u][p];34 if(u==v) return u;35 for( int p = S; anc[u][0]!=anc[v][0]; p-- ) if(anc[u][p]!=anc[v][p]) u=anc[u][p], v=anc[v][p];36 return anc[u][0];37 }38 39 int counter, maxl=0, flag[N], ans;40 void DFS1(int u,int fa) {41 for( int i = head[u]; i; i = g[i].upre ) {42 int v = g[i].v;43 if(v==fa) continue;44 DFS1(v,u);45 flag[u]+=flag[v];46 }47 if(flag[u]==counter) ans=max(ans,edg[u]);48 }49 bool check(int limit) {50 ans=0;counter=0;memset(flag,0,sizeof(flag));for( int i = 1; i <= m; i++ ) if(LEN[i]>limit) counter++, flag[A[i]]++, flag[B[i]]++, flag[C[i]]-=2;51 DFS1(1,1);return maxl-ans<=limit;52 }53 54 int main() {55 freopen(PN".in","r",stdin);56 freopen(PN".out","w",stdout);57 readin(n);readin(m);for( int i = 1; i < n; i++ ) {readin(u);readin(v);readin(w);adde(u,v,w);adde(v,u,w);}58 DFS(1,1);59 for( int i = 1; i <= m; i++ ) {60 readin(A[i]);readin(B[i]);C[i]=lca(A[i],B[i]);61 LEN[i]=dis[A[i]]+dis[B[i]]-dis[C[i]]*2;maxl=max(maxl,LEN[i]);62 }63 int lf=0, rg=maxl-1;64 while(lf<=rg) {65 int mid=(lf+rg)>>1;66 if(check(mid)) rg=mid-1;67 else lf=mid+1;68 }69 printf("%d\n",rg+1);70 return 0;71 }
NOIP2015D2总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。