2018西电ACM新生赛网络赛民科题解

2019-04-13 13:25发布

站内文章 / 模拟电子
15580 0 1010
写了一些啰嗦的东西忘记保存了，懒得再啰嗦一遍了...直入正题！
代码可能有点丑，不要嫌弃... A：
超级水题，这种题只可能存在于校内比赛的签到题，当然n的数据范围变大又是另外的题了。数组+循环，f[i]=f[i-1]+f[i-2]就完事了。唯一坑点在于不能递归，会超时。。。让人搞不明白的是非递归也很好写的情况下为啥要用递归，我开始以为是为了装X，滕dalao说是因为计导课这么教的。。。
代码：
  #include 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< B：
出题人的说法是“逗你玩”，灵感来自于BZOJ XXXX（我忘了哪题...），原题是个非常可怕的题，但是这题还是很欢乐的。由于题目唬人，结论简单，所以出现了部分dalao觉得“这题好难啊”，反而我等莽夫觉得很签到的局面。这里直接说结论，选一个最大的区间，输出平方，注意使用long long，完事。。。
代码：
  #include 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< 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 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 D:
题目给的是个1到n的排列 首先考虑n=1，此时答案为1。 然后分别考虑pi=1、n、j（1 (1) pi=1时，只可能为左子序列减，右子序列增，因此只需要确定左边有哪些数，整个序列就确定了，即对于位置i，有C_{n-1}^{i-1}种方案。举例子：1在第一个位置时，从剩下的n-1个数里选0个数放在左边，有C_{n-1}^{0}；1在第二个位置时，从剩下的n-1个数里选1个数放在左边，故有C_{n-1}^{1}种方案。。。因此可能的总方案数有sum_{i=0}^{n-1}C_{n-1}^{i}=2^{n-1}。
(2)pi=n时，只可能为左子序列增，右子序列减，同理可得总方案数有sum_{i=0}^{n-1}C_{n-1}^{i}=2^{n-1}。这里需要注意，n在第一个位置的序列就是pi=1时1在最后一个位置的序列，同理，n在最后一个位置的序列就是pi=1时1在第一个位置的序列。故此处实际应为sum_{i=0}^{n-1}C_{n-1}^{i} - C_{n-1}^{0}-C_{n-1}^{n-1}=2^{n-1}-2。
(3)pi=j(1 由于本题n非常大，朴素做法写个循环时间复杂度O(n)，肯定会超时。因此需要使用快速幂，时间复杂度为O(log_{2}n)，注意到式子里还有减法，假设ans=2^{n}\%mod，且ans=1，那么（ans-2)%mod=-1，显然会答案错误，因此最后需要(ans-2+mod)%mod，保证为答案不为负数。 代码：
(其实这题最开始出题人变态的把模数范围放到了1e18，计算过程中会爆long long，需要用到O(1)快速乘或者int128。) #include 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 #"< 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至多为log_{2}n，因此时间复杂度为O(nlog_{2}n)。
下面只给出dp代码：
  #include 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 F:
实在没想到F题会过的人那么少。。。当然，因为我不会树dp，所以直接YY到分两组，然后dfs黑白染 {MOD}，两组的点数乘起来就完了。。。
前置技能：dfs
dfs过程中，传个flag的参数，往后传的时候一直取反就好了，然后根据flag统计两组的数目即可。
代码：
  #include 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 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< 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 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 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 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 ",a[i][j]); } } return 0; } I:
I题我的第一想法也是按题意模拟。。。第一发T了马上就想到，如果是一条链不就T成傻X了。然后手画了两三个序列，立马发现了规律：第i个数的父亲节点的值一定是第1个到第i-1个数中恰好比第i个数大的数或者恰好比第i个数小的数。 原因：二叉排序树中序遍历的序列是有序的。对于新加入的第i个数，它是没有子节点的，若它为父节点的左儿子节点，则它在有序序列中一定恰好处于父节点前一个位置，即父节点值恰好比它大；若它为父节点的右儿子节点，则它在有序序列中一定恰好处于父节点后一个位置，即父节点的值恰好比它小。
而且，这两个值（如果都存在）谁位置更靠后谁就是父节点（可以想一想为什么）。
现在问题的关键在于如何找到这两个值。
对于知道STL的人来说，显然就是set啊、map啊搞一搞就完事了。 代码：
  #include 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 mp; int fa[N]; int main(){ scanf("%d",&n); map::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(tfirst)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 J：
终于到了重头戏了。。。
这道题我觉得出的非常好，也是这十题里面真正的难题。
先放上一个链接：https://www.cnblogs.com/CQzhangyu/p/8456756.html
对于第一道题的式子，是不是和本题的式子有点相似？
这里，我演示一遍推导过程：
sum_{i=0}^{n}C_{n}^{i}*q^{n-i}*p^{i}*i^{k}\ =sum_{i=1}^{n}C_{n}^{i}*q^{n-i}*p^{i}*i^{k}\ =sum_{i=1}^{n}C_{n}^{i}*q^{n-i}*p^{i}*i*i^{k-1}\ =sum_{i=1}^{n}frac{n}{i}*C_{n-1}^{i-1}*q^{n-i}*p^{i}*i*i^{k-1}\ =n*sum_{i=1}^{n}C_{n-1}^{i-1}*q^{n-i}*p^{i}*i^{k-1}\ =n*sum_{i=0}^{n-1}C_{n-1}^{i}*q^{n-i-1}*p^{i+1}*(i+1)^{k-1}\ =n*q^{n-1}*p+n*sum_{i=1}^{n-1}C_{n-1}^{i}*q^{n-i-1}*p^{i+1}*(i+1)^{k-1} 然后令 f[k][j]=sum_{i=1}^{n-j}C_{n-j}^{i}*(i+j)^{k}*q^{n-i-j}*p^{i+j} 则有 f[k][j]=sum_{i=1}^{n-j}C_{n-j}^{i}*(i+j)^{k}*q^{n-i-j}*p^{i+j}\ =sum_{i=1}^{n-j}C_{n-j}^{i}*(i+j)*(i+j)^{k-1}*q^{n-i-j}*p^{i+j}\ =sum_{i=1}^{n-j}C_{n-j}^{i}*j*(i+j)^{k-1}*q^{n-i-j}*p^{i+j}+sum_{i=1}^{n-j}C_{n-j}^{i}*i*(i+j)^{k-1}*q^{n-i-j}*p^{i+j}\ =j*sum_{i=1}^{n-j}C_{n-j}^{i}*(i+j)^{k-1}*q^{n-i-j}*p^{i+j}+(n-j)*sum_{i=1}^{n-j}C_{n-j-1}^{i-1}*(i+j)^{k-1}*q^{n-i-j}*p^{i+j}\ =j*f[k-1][j]+(n-j)*sum_{i=0}^{n-j-1}C_{n-j-1}^{i}*(i+j+1)^{k-1}*q^{n-i-j-1}*p^{i+j+1} 又     (n-j)*sum_{i=0}^{n-j-1}C_{n-j-1}^{i}*(i+j+1)^{k-1}*q^{n-i-j-1}*p^{i+j+1}\ =(n-j)*(1+j)^{k-1}*q^{n-j-1}*p^{j+1}+(n-j)*sum_{i=1}^{n-j-1}C_{n-j-1}^{i}*(i+j+1)^{k-1}*q^{n-i-j-1}*p^{i+j+1}\ =(n-j)*(1+j)^{k-1}*q^{n-j-1}*p^{j+1}+(n-j)*f[k-1][j+1] 因此有 small f[k][j]=j*f[k-1][j]+(n-j)*f[k-1][j+1]+(n-j)*(1+j)^{k-1}*q^{n-j-1}*p^{j+1} 至此得到了递推式，递推的时候k从前往后，j从后往前，注意一下j的范围，就可以O(k^2)的求解了。（因为本题O(small k^{2}log_{2}n)也可以过，我在求解的过程中直接用的快速幂求q^(n-j-1)，极其暴力2333） 边界
f[0][j]\ =sum_{i=1}^{n-j}C_{n-j}^{i}*(i+j)^{0}*q^{n-i-j}*p^{i+j}\ =sum_{i=1}^{n-j}C_{n-j}^{i}*q^{n-i-j}*p^{i+j}\ =sum_{i=0}^{n-j}C_{n-j}^{i}*q^{n-i-j}*p^{i+j}-q^{n-j}*p^{j}\ =p^{j}*sum_{i=0}^{n-j}C_{n-j}^{i}*q^{n-i-j}*p^{i}-q^{n-j}*p^{j}\ =p^{j}*(q+p)^{n-j}-q^{n-j}*p^{j}\ =p^{j}*1-p^{j}*q^{n-j}\ =p^{j}*(1-q^{n-j}) 代码： #include 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< 预处理p和q的幂次后，时间复杂度为O(k^2)，效率提高了十几倍。
代码： #include 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 ",ans); } return 0; } 当然搞上斯特林数本题还可以有另一种O(k^2)甚至O(small k*log_{2}k)的做法，但是由于模数为1e9+7，O(small k*log_{2}k)的做法极其复杂，放到区域赛现场赛可能是金牌题了orz... 斯特林数做法之后再更新（不过我只推了公式，并没有写代码2333）

热门文章