首页 > 代码库 > 华中农业大学第五届程序设计大赛网络同步赛解题报告2（转）
华中农业大学第五届程序设计大赛网络同步赛解题报告2（转）
今天实在累了，还有的题晚点补。。。。
题目链接：http://acm.hzau.edu.cn/problemset.php?page=3
题目：acm.hzau.edu.cn/5th.pdf
A：Little Red Riding Hood
题意：给你n朵花，每朵花有个权值，然后每次取花最少要间隔k朵，求权值最大；
思路：简单dp；
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<stack> 9 #include<cstring>10 #include<vector>11 #include<list>12 #include<set>13 #include<map>14 using namespace std;15 #define ll long long16 #define pi (4*atan(1.0))17 #define eps 1e-418 #define bug(x) cout<<"bug"<<x<<endl;19 const int N=1e6+10,M=1e6+10,inf=2147483647;20 const ll INF=1e18+10,mod=2147493647;21 ///数组大小22 int a[N];23 ll dp[N];24 int main()25 {26 int n,k;27 int T;28 scanf("%d",&T);29 while(T--)30 {31 memset(dp,0,sizeof(dp));32 scanf("%d%d",&n,&k);33 for(int i=1;i<=n;i++)34 scanf("%d",&a[i]);35 for(int i=1;i<=n;i++)36 if(i<=k)dp[i]=max(dp[i-1],1LL*a[i]);37 else dp[i]=max(dp[i-1],dp[i-k-1]+a[i]);38 printf("%lld\n",dp[n]);39 }40 return 0;41 }
D：gcd
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<stack> 9 #include<cstring>10 #include<vector>11 #include<list>12 #include<set>13 #include<map>14 using namespace std;15 #define ll long long16 #define pi (4*atan(1.0))17 #define eps 1e-418 #define bug(x) cout<<"bug"<<x<<endl;19 const int N=1e6+10,M=1e6+10,inf=2147483647;20 const ll INF=1e18+10,mod=2147493647;21 22 ///数组大小23 ll MOD;24 struct Matrix25 {26 ll a[2][2];27 Matrix()28 {29 memset(a,0,sizeof(a));30 }31 void init()32 {33 for(int i=0;i<2;i++)34 for(int j=0;j<2;j++)35 a[i][j]=(i==j);36 }37 Matrix operator + (const Matrix &B)const38 {39 Matrix C;40 for(int i=0;i<2;i++)41 for(int j=0;j<2;j++)42 C.a[i][j]=(a[i][j]+B.a[i][j])%MOD;43 return C;44 }45 Matrix operator * (const Matrix &B)const46 {47 Matrix C;48 for(int i=0;i<2;i++)49 for(int k=0;k<2;k++)50 for(int j=0;j<2;j++)51 C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j])%MOD;52 return C;53 }54 Matrix operator ^ (const ll &t)const55 {56 Matrix A=(*this),res;57 res.init();58 ll p=t;59 while(p)60 {61 if(p&1)res=res*A;62 A=A*A;63 p>>=1;64 }65 return res;66 }67 };68 int main()69 {70 Matrix base;71 base.a[0][0]=1;base.a[0][1]=1;72 base.a[1][0]=1;base.a[1][1]=0;73 int T;74 scanf("%d",&T);75 while(T--)76 {77 int n,m,p;78 scanf("%d%d%d",&n,&m,&p);79 int x=__gcd(n+2,m+2);80 MOD=p;81 if(x<=2)82 printf("%d\n",1%p);83 else84 {85 Matrix ans=base^(x-2);86 printf("%lld\n",(ans.a[0][0]+ans.a[0][1])%MOD);87 }88 }89 return 0;90 }
E：One Stroke
题意：给你一棵二叉树，点有点权，每次往左或者往右走，求最长走的路，并且点权和小于k；
思路：官方题解，尺取，我的写法，树上二分，
对于一条链，枚举每个点为终点，vector存该点到根节点的前缀和，二分一下即可；
详见代码；
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<stack> 9 #include<cstring>10 #include<vector>11 #include<list>12 #include<set>13 #include<map>14 using namespace std;15 #define ll long long16 #define pi (4*atan(1.0))17 #define eps 1e-418 #define bug(x) cout<<"bug"<<x<<endl;19 const int N=1e6+10,M=1e6+10,inf=2147483647;20 const ll INF=1e18+10,mod=2147493647;21 22 ///数组大小23 int n,ans,k,a[N];24 vector<int>v;25 void dfs(int x)26 {27 int s=0,t=v.size()-1;28 int e=v.size()-1,ansq=-1;29 while(s<=e)30 {31 int mid=(s+e)>>1;32 if(v[t]-v[mid]<=k)33 {34 ansq=mid;35 e=mid-1;36 }37 else s=mid+1;38 }39 if(v[t]<=k)ans=max(ans,t+1);40 else ans=max(ans,t-ansq);41 int z=v[v.size()-1];42 if(x*2<=n)43 {44 v.push_back(z+a[x<<1]);45 dfs(x<<1);46 v.pop_back();47 }48 if(x*2+1<=n)49 {50 v.push_back(z+a[x<<1|1]);51 dfs(x<<1|1);52 v.pop_back();53 }54 }55 int main()56 {57 int T;58 scanf("%d",&T);59 while(T--)60 {61 ans=0;62 v.clear();63 scanf("%d%d",&n,&k);64 for(int i=1;i<=n;i++)65 scanf("%d",&a[i]);66 v.push_back(a[1]);67 dfs(1);68 if(ans)printf("%d\n",ans);69 else printf("-1\n");70 }71 return 0;72 }
G:Sequence Number
题意：找出最远的i<=j&&a[i]<=a[j]的长度；
思路：这是一道排序可以过的题，也可以rmq+二分 最快的写法可以用单调栈做到O(n)
我是求后面的最大值后缀，二分后缀；
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<stack> 9 #include<cstring>10 #include<vector>11 #include<list>12 #include<set>13 #include<map>14 using namespace std;15 #define ll long long16 #define pi (4*atan(1.0))17 #define eps 1e-418 #define bug(x) cout<<"bug"<<x<<endl;19 const int N=1e5+10,M=1e6+10,inf=2147483647;20 const ll INF=1e18+10,mod=2147493647;21 22 int a[N],nex[N];23 int main()24 {25 int n;26 while(~scanf("%d",&n))27 {28 memset(nex,0,sizeof(nex));29 for(int i=1;i<=n;i++)30 scanf("%d",&a[i]);31 for(int j=n;j>=1;j--)32 nex[j]=max(a[j],nex[j+1]);33 int ans=0;34 for(int i=1;i<=n;i++)35 {36 int s=i,e=n,pos=-1;37 while(s<=e)38 {39 int mid=(s+e)>>1;40 if(nex[mid]>=a[i])41 pos=mid,s=mid+1;42 else e=mid-1;43 }44 ans=max(ans,pos-i);45 }46 printf("%d\n",ans);47 }48 return 0;49 }
J：Color Circle
题意：对于一个点，找长度大于4，相同字母，并且回到原点；
思路：暴力搜索；
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<stack> 9 #include<cstring>10 #include<vector>11 #include<list>12 #include<set>13 #include<map>14 using namespace std;15 #define ll long long16 #define pi (4*atan(1.0))17 #define eps 1e-418 #define bug(x) cout<<"bug"<<x<<endl;19 const int N=1e2+10,M=1e6+10,inf=2147483647;20 const ll INF=1e18+10,mod=2147493647;21 22 ///数组大小23 24 char a[N][N],vis[N][N];25 int n,m,ans;26 int xx[4]={0,1,0,-1};27 int yy[4]={1,0,-1,0};28 int check(int x,int y)29 {30 if(x<=0||x>n||y<=0||y>m)31 return 0;32 return 1;33 }34 void dfs(int x,int y,int dep)35 {36 if(ans)return;37 for(int i=0;i<4;i++)38 {39 int xxx=x+xx[i];40 int yyy=y+yy[i];41 if(check(xxx,yyy)&&a[xxx][yyy]==a[x][y])42 {43 if(vis[xxx][yyy]&&dep-vis[xxx][yyy]+1>=4)44 {45 ans=1;46 }47 else if(!vis[xxx][yyy])48 {49 vis[xxx][yyy]=dep;50 dfs(xxx,yyy,dep+1);51 vis[xxx][yyy]=0;52 }53 }54 }55 }56 int main()57 {58 while(~scanf("%d%d",&n,&m))59 {60 memset(vis,0,sizeof(vis));61 ans=0;62 for(int i=1;i<=n;i++)63 scanf("%s",a[i]+1);64 for(int i=1;i<=n;i++)65 {66 for(int j=1;j<=m;j++)67 {68 dfs(i,j,1);69 if(ans)break;70 }71 if(ans)break;72 }73 if(ans)printf("Yes\n");74 else printf("No\n");75 }76 return 0;77 }
K：Deadline
题意：给你n个bug，每个bug最晚修复时间，一个程序猿需要一天修复一个bug，问需要多少个程序猿才能修复成功；
思路：开始sort一下，遍历过去超时；
后面想想发现>=n的数根本没有必要，一个程序员总是够的，所以遍历，标记小于n的就是；
这题只要想到思路还是很简单的，假设所有工程师每天都在修复bug，那么对天数记录bug的前缀和，O(n)得到答案max(pre[i]+i-1)/i)
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<stack> 9 #include<cstring>10 #include<vector>11 #include<list>12 #include<set>13 #include<map>14 using namespace std;15 #define ll long long16 #define pi (4*atan(1.0))17 #define eps 1e-418 #define bug(x) cout<<"bug"<<x<<endl;19 const int N=1e6+10,M=1e6+10,inf=2147483647;20 const ll INF=1e18+10,mod=2147493647;21 ///数组大小22 int a[N],pre[N];23 int main()24 {25 int n;26 while(~scanf("%d",&n))27 {28 memset(pre,0,sizeof(pre));29 for(int i=1;i<=n;i++)30 {31 scanf("%d",&a[i]);32 if(a[i]>=N-5)continue;33 pre[a[i]]++;34 }35 int ans=1;36 for(int i=1;i<=1000000;i++)37 {38 pre[i]=pre[i]+pre[i-1];39 ans=max(ans,pre[i]/i+(pre[i]%i?1:0));40 }41 printf("%d\n",ans);42 }43 return 0;44 }
L：Happiness
思路：找AB即可；
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<stack> 9 #include<cstring>10 #include<vector>11 #include<list>12 #include<set>13 #include<map>14 using namespace std;15 #define ll long long16 #define pi (4*atan(1.0))17 #define eps 1e-418 #define bug(x) cout<<"bug"<<x<<endl;19 const int N=3e3+10,M=1e6+10,inf=2147483647;20 const ll INF=1e18+10,mod=2147493647;21 22 char a[M];23 int main()24 {25 int T,cas=1;26 scanf("%d",&T);27 while(T--)28 {29 scanf("%s",a+1);30 int n=strlen(a+1);31 int ans=0;32 for(int i=1;i<=n;i++)33 if(a[i]==‘A‘&&a[i+1]==‘B‘)34 ans++;35 printf("Case #%d:\n%d\n",cas++,ans);36 }37 return 0;38 }
from:http://www.cnblogs.com/jhz033/p/6754712.html
华中农业大学第五届程序设计大赛网络同步赛解题报告2（转）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。