本文主要是介绍2018西电ACM新生赛网络赛民科题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
写了一些啰嗦的东西忘记保存了,懒得再啰嗦一遍了...直入正题!
代码可能有点丑,不要嫌弃...
A:
超级水题,这种题只可能存在于校内比赛的签到题,当然n的数据范围变大又是另外的题了。数组+循环,f[i]=f[i-1]+f[i-2]就完事了。唯一坑点在于不能递归,会超时。。。让人搞不明白的是非递归也很好写的情况下为啥要用递归,我开始以为是为了装X,滕dalao说是因为计导课这么教的。。。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 45;
int t,n,f[N];
void init(){f[0]=f[1]=1;for(int i=2;i<=40;i++){f[i]=f[i-1]+f[i-2];}
}
int main(){init(); cin>>t;while(t--){cin>>n;cout<<f[n]<<"\n";}return 0;
}
B:
出题人的说法是“逗你玩”,灵感来自于BZOJ XXXX(我忘了哪题...),原题是个非常可怕的题,但是这题还是很欢乐的。由于题目唬人,结论简单,所以出现了部分dalao觉得“这题好难啊”,反而我等莽夫觉得很签到的局面。这里直接说结论,选一个最大的区间,输出平方,注意使用long long,完事。。。
代码:
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=a;i<=b;i++)
int n,l,r,len;
int main(){scanf("%d",&n);For(i,1,n){scanf("%d %d",&l,&r);if(r-l+1>len) len=r-l+1;}cout<<len*1ll*len<<"\n";return 0;
}
C:
应红太阳的强烈要求,我第一个验了这道题,第一感觉并没有什么坑点,虽然因为某些地方n和m以及'<' 、'>'写反,错了好几发。。。首先肯定要用long long。假设a数组长度n,b数组长度m,那么可以O(m)得到是否存在b[i]!=b[i-1]+b[i-2],然后O(max(n,m))得到b是否为a的子序列,依次判断是否满足要求然后输出对应字符串。
代码:
#include<stdio.h>
const int N=1e3+5;
char str[][100]={"Wrong Answer - The participant's answer does not obey the recursion",
"Wrong Answer - The participant's answer is not a subsequence of input",
"Wrong Answer - The jury gets better answer than participant's",
"Accepted - Ok, ok",
"System Error - The participant gets better answer than jury's"};
int n,m,k;
long long a[N],b[N];int main(){while(~scanf("%d %d %d",&n,&m,&k)){for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=1;i<=m;i++) scanf("%lld",&b[i]);int ans=0;for(int i=3;i<=m;i++){if(b[i]!=b[i-1]+b[i-2]){ans=1;break;}}if(ans!=1){int j=1;for(int i=1;i<=n;i++){if(b[j]==a[i]) j++;if(j>m) break;}if(j>m){if(m<k) ans=3;else if(m==k) ans=4;else ans=5;}elseans=2;}printf("%s\n",str[ans-1]);}return 0;
}
D:
题目给的是个1到n的排列
首先考虑n=1,此时答案为1。
然后分别考虑pi=1、n、j(1<j<n):
(1) pi=1时,只可能为左子序列减,右子序列增,因此只需要确定左边有哪些数,整个序列就确定了,即对于位置i,有种方案。举例子:1在第一个位置时,从剩下的n-1个数里选0个数放在左边,有;1在第二个位置时,从剩下的n-1个数里选1个数放在左边,故有种方案。。。因此可能的总方案数有。
(2)pi=n时,只可能为左子序列增,右子序列减,同理可得总方案数有。这里需要注意,n在第一个位置的序列就是pi=1时1在最后一个位置的序列,同理,n在最后一个位置的序列就是pi=1时1在第一个位置的序列。故此处实际应为。
(3)pi=j(1<j<n)时,显然只能全部递增或递减,而这同样分别是pi=1时1在第一个位置和最后一个位置的序列,即不产生新的方案。
综上,总方案数为
由于本题n非常大,朴素做法写个循环时间复杂度O(n),肯定会超时。因此需要使用快速幂,时间复杂度为O(),注意到式子里还有减法,假设,且ans=1,那么(ans-2)%mod=-1,显然会答案错误,因此最后需要(ans-2+mod)%mod,保证为答案不为负数。
代码:
(其实这题最开始出题人变态的把模数范围放到了1e18,计算过程中会爆long long,需要用到O(1)快速乘或者int128。)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,a,b) for(int i=a;i<=b;i++)
int t,p;
ll n,ans;
ll qpow(ll a,ll b,ll p){ll res=1;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res;
}
int main(){scanf("%d",&t);For(cas,1,t){scanf("%lld %d",&n,&p);cout<<"Case #"<<cas<<": "; if(n==1ll) ans=1;else ans=(qpow(2,n,p)-2+p)%p;cout<<ans<<"\n";}return 0;
}
E:
只有这题是我出的。。。很欢乐对不对,要不要出个略微不那么常见的博弈套点其他东西作为现场赛的复仇?(嫌题目简单的是要气死我啊,你不会用难的做法做吗???开个玩笑QAQ)
大概三种做法:
(1)无脑找规律
这个不用多说吧,会找规律也是本事
(2)思维
分奇偶考虑(ls学长和岩佬两位聚聚差不多是这个思路)。
因为先手能取2的幂次个石子,既包含了奇数1,又包含了一些偶数,而后手只能取奇数个石子,那么只要先手保证留给后手的是偶数个石子,后手就一定取不完,故先手除了开始就遇到0个石子都必胜。
(3)动态规划
去掉思维和规律,这题显然可以用dp对吧,而且算是个很套路的博弈的dp。
首先,在两人都采取最优策略下,Greenty_Q二代每次面对同样的石子数时最后得到的结局应该是一样的,同理,wang9897二代每次面对同样的石子数时最后得到的结局也是一样的。
将结局定义为必胜态和必败态,则可知一方只要存在一种操作可以使得操作后达到对方的必败态,则该状态为己方的必胜态,否则为己方的必败态。
假定dp1[i]代表Greenty_Q二代面对i个石子的结局,dp2[i]代表wang9897二代面对i个石子的结局,0是双方的必败态。
则dp1[i]可以通过所有的dp2[i-2^k] (2^k<=i)来确定,dp2[i]可以通过所有的dp1[i-3^k] (3^k<=i)来确定,只需要保证i从小到大,则后面的状态都可由前面已知的状态得到。
显然k至多为,因此时间复杂度为O()。
下面只给出dp代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=18;
bool sg2[N],sg3[N];//先手sg2,后手sg3
int f2[20],f3[20];
void init(){f2[0]=f3[0]=1;for(int i=1;i<M;i++) f2[i]=f2[i-1]<<1,f3[i]=(f3[i-1]<<1)+f3[i-1];//预处理可能会用到的2^k和3^k次方 sg2[0]=sg3[0]=false;int tt;for(int i=1;i<N;i++){ for(int j=0;j<M&&f2[j]<=i;j++){//先手面对i时的可能取法 tt=i-f2[j];if(!sg3[tt]){//只要能到对方的必败,此时己方就必胜 sg2[i]=true;break;}}for(int j=0;j<M&&f3[j]<=i;j++){//后手面对i时的可能取法 tt=i-f3[j];if(!sg2[tt]){//同上 sg3[i]=true;break;}}}
}
int t,n;
int main(){init();scanf("%d",&t);while(t--){scanf("%d",&n);cout<<(sg2[n]?"Greenty_Q\n":"The wisdom tree master No.1\n");}return 0;
}
F:
实在没想到F题会过的人那么少。。。当然,因为我不会树dp,所以直接YY到分两组,然后dfs黑白染色,两组的点数乘起来就完了。。。
前置技能:dfs
dfs过程中,传个flag的参数,往后传的时候一直取反就好了,然后根据flag统计两组的数目即可。
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define p_b push_back
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=1e5+5;
int n,t,x,y,s1,s2;
vector<int> v[N];
bool vis[N];
void dfs(int now,bool flag){if(flag) s1++;//分别统计两组的数目else s2++;For(i,0,(int)v[now].size()-1){if(!vis[v[now][i]]){vis[v[now][i]]=true;dfs(v[now][i],!flag);}}
}
int main(){while(~scanf("%d",&n)){s1=s2=0;memset(vis,0,(n+5)*sizeof(bool));For(i,1,n-1){scanf("%d %d",&x,&y);v[x].p_b(y),v[y].p_b(x);}vis[1]=true;dfs(1,true);cout<<s1*1ll*s2<<"\n";//防止爆intFor(i,1,n) v[i].clear();}return 0;
}
G:
积性函数,一时半会儿我也讲不清楚。
但是,简单的积性函数有一种套路的解法——线性筛。
这里同样不多讲线性筛,只需要记住,线性筛先枚举i,同时维护1到i的素数表,枚举到每个i时又会从小到大枚举此时的素数表,筛除这些素数的i倍,并且当这个倍数同时也是某个素数的倍数时退出内层循环。
由题中式子我们可以知道,f(1)=1,x是质数的时候,f(x)=x。
当x与y互质的时候,f(x*y)=f(x)*f(y)/f(1)=f(x)*f(y),当x是y的倍数时,f(x*y)=f(x)*f(y)/f(y)=f(x)。
而素数筛的过程中可以很很完美的用到上述几个式子。
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
int t,n;
bool notprime[N];
int cnt,prime[N/10],f[N];
void init(){//线性筛notprime[1]=true;f[1]=1;//f(1)=1 for(int i=2;i<=N-5;i++){if(!notprime[i]) prime[cnt++]=i,f[i]=i;//f(prime)=prime; for(int j=0;j<cnt&&prime[j]*i<=N-5;j++){notprime[prime[j]*i]=true;//从小到大枚举素数并筛掉素数的i倍if(i%prime[j]==0){f[prime[j]*i]=f[i];//gcd(prime,i)==prime,f(prime*i)=f(i)break;}f[prime[j]*i]=f[prime[j]]*f[i];//gcd(prime,i)==1,f(prime*i)=f(prime)*f(i)}}
}int main(){init();while(~scanf("%d",&n)) cout<<f[n]<<"\n";return 0;
}
H:
做法很多,昨晚才知道这题可以直接两遍前缀和orz。。。
前缀和:
两层循环枚举i从n到1,j从m到1,一遍从上到下的前缀和;再来一遍,这回从右到左。完事。。。
我的做法是二维差分:
同样两层循环枚举i从n到1,j从m到1,但是算的过程中f(i,j)+=f(i-1,j)+f(i,j-1)-f(i-1,j-1),这样恰好可以使(i-1,j-1)右上的区域不被计算两次,而且可以直接递推,一遍完事。
至于其他的各种做法,略。。。
差分代码:
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N = 1e3+5;
int n,m,h;
int a[N][N],x,y;
int main(){scanf("%d %d %d",&n,&m,&h);For(i,1,h){scanf("%d %d",&x,&y);a[x][y]++;}for(int i=n;i>=1;i--){for(int j=m;j>=1;j--){a[i][j]+=a[i+1][j]+a[i][j+1]-a[i+1][j+1];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%d\n",a[i][j]);}}return 0;
}
I:
I题我的第一想法也是按题意模拟。。。第一发T了马上就想到,如果是一条链不就T成傻X了。然后手画了两三个序列,立马发现了规律:第i个数的父亲节点的值一定是第1个到第i-1个数中恰好比第i个数大的数或者恰好比第i个数小的数。
原因:二叉排序树中序遍历的序列是有序的。对于新加入的第i个数,它是没有子节点的,若它为父节点的左儿子节点,则它在有序序列中一定恰好处于父节点前一个位置,即父节点值恰好比它大;若它为父节点的右儿子节点,则它在有序序列中一定恰好处于父节点后一个位置,即父节点的值恰好比它小。
而且,这两个值(如果都存在)谁位置更靠后谁就是父节点(可以想一想为什么)。
现在问题的关键在于如何找到这两个值。
对于知道STL的人来说,显然就是set啊、map啊搞一搞就完事了。
代码:
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define m_p make_pair
const int N = 1e5+5;
int t,n;
map<int,int> mp;
int fa[N];
int main(){scanf("%d",&n);map<int,int>::iterator it;int pos1,pos2,num,num1,num2;For(i,1,n){scanf("%d",&t);if(i==1)fa[t]=0;else{it=mp.end();if(t<mp.begin()->first)fa[t]=mp.begin()->first;else if(t>(--it)->first)fa[t]=it->first;else{it=mp.lower_bound(t);pos2=it->second,num2=it->first;it--;pos1=it->second,num=num1=it->first;if(pos1<pos2)num=num2;fa[t]=num;}}mp.insert(m_p(t,i));}For(i,1,n){cout<<fa[i]<<(i==n?'\n':' ');}return 0;
}
J:
终于到了重头戏了。。。
这道题我觉得出的非常好,也是这十题里面真正的难题。
先放上一个链接:https://www.cnblogs.com/CQzhangyu/p/8456756.html
对于第一道题的式子,是不是和本题的式子有点相似?
这里,我演示一遍推导过程:
然后令
则有
又
因此有
至此得到了递推式,递推的时候k从前往后,j从后往前,注意一下j的范围,就可以O(k^2)的求解了。(因为本题O()也可以过,我在求解的过程中直接用的快速幂求q^(n-j-1),极其暴力2333)
边界
代码:
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N = 1e3;
const int mod=1e9+7;
inline int qpow(int a,int b){int res=1;while(b){if(b&1) res=res*1ll*a%mod;b>>=1;a=a*1ll*a%mod;}return res;
}
int n,k,p;
int inv=qpow(100,mod-2);
int dp[N+5][N+5],f[N+5][N+5];
void init(){For(j,0,N) f[0][j]=1;For(i,1,N){For(j,0,N){f[i][j]=f[i-1][j]*1ll*(1+j)%mod;}}
}
int main(){init();while(~scanf("%d %d %d",&n,&k,&p)){int q=(100-p)*1ll*inv%mod,m=min(n-1,k);p=p*1ll*inv%mod;For(j,0,m) dp[0][j]=qpow(p,j)*1ll*(1-qpow(q,n-j))%mod;//,cout<<dp[0][j]<<"\n";For(i,1,k){For(j,0,m){dp[i][j]=(j*1ll*dp[i-1][j]+(n-j)*1ll*f[i-1][j]%mod*qpow(p,1+j)%mod*qpow(q,n-1-j)%mod+(n-j)*1ll*dp[i-1][j+1]%mod)%mod;}}int ans=(dp[k][0]+mod)%mod;printf("%d\n",ans);}return 0;
}
预处理p和q的幂次后,时间复杂度为O(k^2),效率提高了十几倍。
代码:
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N = 1e3;
const int mod=1e9+7;
inline int qpow(int a,int b){int res=1;while(b){if(b&1) res=res*1ll*a%mod;b>>=1;a=a*1ll*a%mod;}return res;
}
int n,m,k,p,q;
int inv=qpow(100,mod-2);
int dp[N+5][N+5],f[N+5][N+5],qq[N+5],pp[N+5];
inline void init(){pp[0]=1; For(j,0,N) f[0][j]=1;For(i,1,N) For(j,0,N) f[i][j]=f[i-1][j]*1ll*(1+j)%mod;
}
int main(){init();while(~scanf("%d %d %d",&n,&k,&p)){q=(100-p)*1ll*inv%mod,m=min(n-1,k),p=p*1ll*inv%mod;qq[0]=qpow(q,n-m);if(m==n-1) qq[n]=1;for(int j=m-1;j>=0;j--) qq[m-j]=qq[m-j-1]*1ll*q%mod;For(j,0,m) pp[j+1]=pp[j]*1ll*p%mod,dp[0][j]=pp[j]*1ll*(1-qq[j])%mod;For(i,1,k){For(j,0,m){dp[i][j]=(j*1ll*dp[i-1][j]%mod+(n-j)*(f[i-1][j]*1ll*pp[1+j]%mod*qq[j+1]%mod+dp[i-1][j+1])%mod)%mod;}}int ans=(dp[k][0]+mod)%mod;printf("%d\n",ans);}return 0;
}
当然搞上斯特林数本题还可以有另一种O(k^2)甚至O()的做法,但是由于模数为1e9+7,O()的做法极其复杂,放到区域赛现场赛可能是金牌题了orz...
斯特林数做法之后再更新(不过我只推了公式,并没有写代码2333)
这篇关于2018西电ACM新生赛网络赛民科题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!