首页 > 代码库 > noip2014总结
noip2014总结
noip总结
经过七周的停课，我们终于迎来了期盼已久的noip考试。在这一次的noip考试中，我们经历了很多，也收获了很多。当然这一次考试中也有很多值得总结的地方，特写此总结。
这一次考试考得还不错，其实有一部分运气的存在，bird本来应该只有30分的，莫名其妙的拿了60分。但不要在意这些细节。
第一天，第一二题都还是比较水，也很快的做了出来。第三题先写了一个正确的70分暴力，然后第二题的对拍，没拍出错就交了。第一题真心不会写对拍。然后开始写第三题的错误的30分正解。比较naive。
第二天，第一题二维前缀和正解，没发现暴力也能过，拍了很久发现datamaker写错了，第二题水水的bfs，没什么好说的。第三题，考的是骗分选手的自我修养，第一次写20hash，→_→，70分在意料之中。
总体来说，530也算是发挥了自己应有的水平。如果bird不写错，当然就更好了。和第一名，省选差了20分啊→_→，还是可以接受的，吧。
后附代码。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int N,Na,Nb; 6 int xx[10][10]; 7 int a[2010],b[2010]; 8 int ans1,ans2; 9 int main()10 {11 freopen("rps.in","r",stdin);12 freopen("rps.out","w",stdout);13 xx[0][0]=0;14 xx[0][1]=0;15 xx[0][2]=1;16 xx[0][3]=1;17 xx[0][4]=0;18 xx[1][0]=1;19 xx[1][1]=0;20 xx[1][2]=0;21 xx[1][3]=1;22 xx[1][4]=0;23 xx[2][0]=0;24 xx[2][1]=1;25 xx[2][2]=0;26 xx[2][3]=0;27 xx[2][4]=1;28 xx[3][0]=0;29 xx[3][1]=0;30 xx[3][2]=1;31 xx[3][3]=0;32 xx[3][4]=1;33 xx[4][0]=1;34 xx[4][1]=1;35 xx[4][2]=0;36 xx[4][3]=0;37 xx[4][4]=0;38 scanf("%d%d%d",&N,&Na,&Nb);39 for(int i=0;i<Na;i++)40 scanf("%d",&a[i]);41 for(int i=0;i<Nb;i++)42 scanf("%d",&b[i]);43 for(int i=0;i<N;i++)44 {45 ans1+=xx[a[i%Na]][b[i%Nb]];46 ans2+=xx[b[i%Nb]][a[i%Na]];47 }48 printf("%d %d\n",ans1,ans2);49 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 struct JackSlowFuck 7 { 8 int from,to,next; 9 }Fu[1000010];10 int head[400010];11 struct node12 {13 int w,mx,sum,pfs,ans;14 }nd[400010];15 int nn;16 void addedge(int f,int t)17 {18 ++nn;19 Fu[nn].from=f;20 Fu[nn].to=t;21 Fu[nn].next=head[f];22 head[f]=nn;23 }24 priority_queue <int> Q;25 void dfs(int now,int from)26 {27 28 while(!Q.empty()) Q.pop();29 for(int k=head[now];k;k=Fu[k].next)30 if(Fu[k].to!=from)31 dfs(Fu[k].to,now);32 while(!Q.empty()) Q.pop();33 Q.push(0);34 Q.push(0);35 Q.push(nd[from].w);36 nd[now].sum=(nd[now].sum+nd[from].w)%10007;37 nd[now].pfs=(nd[now].pfs+(nd[from].w*nd[from].w)%10007)%10007;38 for(int k=head[now];k;k=Fu[k].next)39 if(Fu[k].to!=from)40 {41 Q.push(nd[Fu[k].to].w); 42 nd[now].sum=(nd[now].sum+nd[Fu[k].to].w)%10007;43 nd[now].pfs=(nd[now].pfs+(nd[Fu[k].to].w*nd[Fu[k].to].w)%10007)%10007;44 nd[now].ans=(nd[now].ans+nd[Fu[k].to].ans)%10007;45 }46 nd[now].mx=Q.top();47 Q.pop();48 nd[now].mx*=Q.top();49 nd[now].ans=(nd[now].ans+((nd[now].sum*nd[now].sum)%10007-nd[now].pfs%10007+10007)%10007)%10007;50 while(!Q.empty()) Q.pop();51 }52 int N;53 int f,t;54 int maxx;55 int main()56 {57 freopen("link.in","r",stdin);58 freopen("link.out","w",stdout);59 scanf("%d",&N);60 for(int i=1;i<N;i++)61 {62 scanf("%d%d",&f,&t);63 addedge(f,t);64 addedge(t,f);65 }66 nd[0].w=0;67 for(int i=1;i<=N;i++)68 scanf("%d",&nd[i].w);69 dfs(1,0);70 maxx=nd[1].mx;71 for(int i=1;i<=N;i++)72 maxx=max(maxx,nd[i].mx);73 printf("%d %d\n",maxx,nd[1].ans);74 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 long long dp[2][20010]; 7 int mx=0; 8 int N,M,K; 9 struct JackSlowFuck10 {11 int X,Y;12 }nd[200010];13 struct line14 {15 int P,L,H;16 }ln[200010];17 bool cmp(line a,line b)18 {19 return a.P<b.P;20 }21 long long ans;22 int L,H;23 int l,r;24 int nn,k;25 #ifdef WIN3226 #define LL "%I64d"27 #else28 #define LL "%lld"29 #endif30 int main()31 {32 freopen("bird.in","r",stdin);33 freopen("bird.out","w",stdout);34 memset(dp,-1,sizeof(dp));35 scanf("%d%d%d",&N,&M,&K);36 for(int i=1;i<=M;i++)37 dp[0][i]=0;38 for(int i=0;i<N;i++)39 scanf("%d%d",&nd[i].X,&nd[i].Y);40 for(int i=0;i<K;i++)41 scanf("%d%d%d",&ln[i].P,&ln[i].L,&ln[i].H);42 sort(ln,ln+K,cmp);43 for(int i=0;i<N;i++)44 { 45 L=0,H=M;46 l=1,r=M;47 while(nn<K&&ln[nn].P<i+1) nn++;48 if(ln[nn].P==i+1) L=ln[nn].L,H=ln[nn].H;49 if(nn>0&&ln[nn-1].P==i) l=ln[nn-1].L+1,r=ln[nn-1].H-1;50 for(int j=l;j<=r;j++)51 if(~dp[i&1][j])52 {53 mx=max(mx,nn);54 k=1;55 if(j-nd[i].Y>L)56 if(dp[(i+1)&1][j-nd[i].Y]==-1||dp[(i+1)&1][j-nd[i].Y]>dp[i&1][j])57 dp[(i+1)&1][j-nd[i].Y]=dp[i&1][j];58 while(k*nd[i].X+j<L) k++;59 while(k*nd[i].X+j<H)60 {61 if(dp[(i+1)&1][k*nd[i].X+j]==-1||dp[(i+1)&1][k*nd[i].X+j]>dp[i&1][j]+k)62 dp[(i+1)&1][k*nd[i].X+j]=dp[i&1][j]+k;63 else64 break;65 k++;66 }67 68 if(k*nd[i].X+j>=M&&ln[nn].P!=i+1&&(dp[(i+1)&1][M]==-1||dp[(i+1)&1][M]>dp[i&1][j]+k))69 dp[(i+1)&1][M]=dp[i&1][j]+k;70 dp[i&1][j]=-1;71 }72 }73 int flags=0;74 ans=1000000000000000000LL;75 for(int i=1;i<=M;i++)76 if(~dp[N&1][i])77 {78 flags=1;79 ans=min(ans,dp[N&1][i]);80 }81 if(flags)82 printf("%d\n" LL "\n",flags,ans);83 else84 printf("%d\n%d\n",flags,mx);85 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int dp[1010][1010]; 6 int a[1010][1010]; 7 int d,N; 8 int x,y,k; 9 int ans,mx;10 int main()11 {12 freopen("wireless.in","r",stdin);13 freopen("wireless.out","w",stdout);14 memset(a,0,sizeof(a));15 memset(dp,0,sizeof(dp));16 scanf("%d%d",&d,&N);17 for(int i=1;i<=N;i++)18 {19 scanf("%d%d%d",&x,&y,&k);20 a[x+1][y+1]+=k;21 }22 for(int i=1;i<=129;i++)23 for(int j=1;j<=129;j++)24 dp[i][j]=a[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];25 ans=0;26 mx=0;27 for(int i=1;i<=129;i++)28 for(int j=1;j<=129;j++)29 {30 if(dp[min(i+d,129)][min(j+d,129)]-dp[max(i-d-1,0)][min(j+d,129)]-dp[min(i+d,129)][max(j-d-1,0)]+dp[max(i-d-1,0)][max(j-d-1,0)]>mx)31 mx=dp[min(i+d,129)][min(j+d,129)]-dp[max(i-d-1,0)][min(j+d,129)]-dp[min(i+d,129)][max(j-d-1,0)]+dp[max(i-d-1,0)][max(j-d-1,0)];32 33 }34 35 for(int i=1;i<=129;i++)36 for(int j=1;j<=129;j++)37 {38 if(dp[min(i+d,129)][min(j+d,129)]-dp[max(i-d-1,0)][min(j+d,129)]-dp[min(i+d,129)][max(j-d-1,0)]+dp[max(i-d-1,0)][max(j-d-1,0)]==mx)39 ans++;40 }41 printf("%d %d\n",ans,mx);42 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 int N,M; 8 const int INF=0x3f3f3f3f; 9 struct JackSlowFuck10 {11 int from,to,len,next;12 }Fu[1000010];13 int head[100010],nn;14 int dis[100010];15 bool in[100010];16 queue <int> Q;17 void spfa(int s)18 {19 while(!Q.empty()) Q.pop();20 memset(dis,0x3f,sizeof(dis));21 dis[s]=0;22 Q.push(s);23 in[s]=true;24 while(!Q.empty())25 {26 int now=Q.front();27 in[now]=false;28 Q.pop();29 for(int k=head[now];k;k=Fu[k].next)30 if(dis[Fu[k].to]>dis[now]+Fu[k].len)31 {32 dis[Fu[k].to]=dis[now]+Fu[k].len;33 if(!in[Fu[k].to])34 Q.push(Fu[k].to),in[Fu[k].to]=true;35 }36 }37 }38 void addedge(int f,int t)39 {40 ++nn;41 Fu[nn].next=head[f];42 head[f]=nn;43 Fu[nn].len=1;44 Fu[nn].from=f;45 Fu[nn].to=t;46 }47 int t,f;48 int s,e;49 int main()50 {51 freopen("road.in","r",stdin);52 freopen("road.out","w",stdout);53 scanf("%d%d",&N,&M);54 for(int i=1;i<=M;i++)55 {56 scanf("%d%d",&t,&f);57 addedge(f,t);58 }59 scanf("%d%d",&s,&e);60 memset(in,0,sizeof(in));61 spfa(e);62 if(dis[s]==INF)63 {64 printf("-1\n");65 return 0;66 }67 else68 {69 memset(in,0,sizeof(in));70 for(int i=1;i<=N;i++)71 if(dis[i]==INF)72 {73 for(int k=head[i];k;k=Fu[k].next)74 in[Fu[k].to]=true;75 }76 if(in[s])77 {78 printf("-1\n");79 return 0;80 }81 spfa(e);82 if(dis[s]==INF)83 {84 printf("-1\n");85 return 0;86 }87 else88 {89 printf("%d\n",dis[s]);90 }91 92 }93 }
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int MOD[21]={1000000011,1000000009,1000000008,1000000007,1000000003,1000000001,1000000013,1000000017,1000000019,1000000117,1000000119,2000000011,2000000009,2000000008,2000000007,2000000003,2000000001,2000000013,2000000017,2000000019,2000000117}; 6 long long N,M; 7 long long a[21][110]; 8 char x[20010]; 9 int len;10 bool flags;11 long long now=0;12 long long ans=0;13 int b[1500010],nn;14 int main()15 {16 freopen("equation.in","r",stdin);17 freopen("equation.out","w",stdout);18 cin>>N>>M;19 for(int i=0;i<=N;i++)20 {21 scanf("%s",x+1);22 len=strlen(x+1);23 flags=false;24 if(x[1]==‘-‘)25 flags=true;26 for(int j=1+flags;j<=len;j++)27 {28 for(int t=0;t<=20;t++)29 a[t][i]=(a[t][i]*10)%MOD[t]+x[j]-‘0‘;30 }31 if(flags)32 {33 for(int t=0;t<=20;t++)34 a[t][i]=-a[t][i];35 }36 }37 for(int i=1;i<=M;i++)38 {39 for(int t=0;t<=20;t++)40 { 41 flags=false;42 now=1;43 ans=a[t][0];44 for(int j=1;j<=N;j++)45 {46 now=(now*i)%MOD[t];47 ans=(ans+(a[t][j]*now)%MOD[t])%MOD[t];48 }49 if(ans)50 {51 flags=true;52 break;53 }54 }55 if(!flags)56 b[++nn]=i;57 }58 printf("%d\n",nn);59 for(int i=1;i<=nn;i++)60 printf("%d\n",b[i]);61 }
noip2014总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。