acm暑期集训_2020.07.04

任务清单

1、ZUCC蓝桥杯热身赛-2 中 C、D、F题 2、参加晚10：30的cf

C题------ZUCC-2247 最小的01串(易）

题目链接：http://acm.zucc.edu.cn/problem.php?id=2247 题目输入格式：

输入第一行包含两个整数依序为N(1<N<10^6) 和K(1<K<N^2 )，依序代表字符串的长度和最 多可以进行的操作次数。

错题反思：注意了输入用long long 读入，而输出没有用 long long 类型，导致有些点被卡了，少A一题真难过。写代码时要注意读入和输出类型要与题目要求一致！

D题------ZUCC-2248 乘积求和(中）

题目链接：http://acm.zucc.edu.cn/problem.php?id=2248 算法：裸dp 解法：

当 k = 1 时可知 ans=sum(a[i]) 当 k = 2 时可知 tot=sum(a[i]); 累加（tot-=a[i]；ans=(ans+(a[i]*(tot%mod))%mod)%mod;）i的范围0~n; 比赛时我就推到这里，然后就没思路了，看了题解才知道是道dp，是我太笨，没看出来，以下是归纳后的结论： k=1 时，f[i]=f[i-1]+a[i] //f[i]即表示到i这个点时当前的乘积和 k=2 时，g[i]=g[i-1]+f[i-1]*a[i];//其实可以看到这里的g[i]就是我之前推的每个过程的ans,f[i-1]就是tot-=a[i],练得太少看不出啊 k=3 时，h[i]=h[i-1]+g[i-1]*a[i]; 由此可以推出一个式子 k=10,dp[maxn][11] dp[i][j]=(dp[i-1][j]+(dp[i-1][j-1]*a[i]) //当前的的j(即k)需要从上一层转移而来

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1000000007; const int maxn=1000007; int n,k; ll a[maxn]; ll dp[maxn][11]; int main(){ scanf("%d%d",&n,&k); for(int i=0;i<n;i++){ scanf("%lld",&a[i]); dp[i][0]=1; } dp[0][1]=a[0]; for(int i=1;i<n;i++){ for(int j=1;j<=k;j++){ dp[i][j]=(dp[i-1][j]+(dp[i-1][j-1]*a[i])%mod)%mod; } } printf("%lld\n",dp[n-1][k]); }

D题------ZUCC-2250 假赛大师(中）

题目链接：http://acm.zucc.edu.cn/problem.php?id=2250 算法：优先队列

#include<bits/stdc++.h> using namespace std; typedef long long ll; int n; ll ans; int w[1100007]; priority_queue<int,vector<int>,greater<int>> que; int main(){ scanf("%d",&n); int inx=0; for(int i=1;i<=n;i++){ scanf("%d",&w[i]); if(w[i]==-1){ inx=i; } } ans=0; while(n>inx){//若n<=inx说明当前轮不需要贿赂，他自己就可以打败对手晋级 que.push(w[n]); ans+=que.top();//选择当前轮花费最小的，以保证晋级 que.pop(); for(int i=n/2+1;i<n;i++){ //(n/2+1)~(n-1)都是可以被n以后的对手打败的 que.push(w[i]); } n/=2; } printf("%lld\n",ans); }