CFR623

CFR623 div1

CF1314A Recommendations

请先思考后再展开
1
2
3
4
5
6
7
8
9
pii a[N];int n=qread();fo(i,1,n) a[i].FR=qread();fo(i,1,n) a[i].SE=qread();sort(a+1,a+n+1);
ll ans=0;priority_queue<int> q;ll sum=a[1].SE;q.push(a[1].SE);int cur=a[1].FR,ii=2;
while(1)
{
while(ii<=n and a[ii].FR==cur) q.push(a[ii].SE),sum+=a[ii].SE,ii++;
if(sz(q)) sum-=q.top(),q.pop(),cur++;
else if(ii<=n) cur=a[ii].FR; else break;
ans+=sum;
}write(ans);

CF1314B Double Elimination

题意:双败淘汰制,$2^n$参赛者中有k个关键人物,最大化有特殊关键参与的比赛总数,$n \le 17$

注意败者组每轮有两场比赛,两场中间是胜者组的一场比赛;参赛双方是根据可用编号排序后决定的

题解

CF1314C Au Pont Rouge

题意:给出一个长度为$n \le 1e3$的字符串S,有$C_{n-1}^{m-1}$种分为m段非空段的方案,以字典序最小的作为方案的关键字排序,输出关键字第$k \le 1e18$大的方案的关键字

请先思考后再展开

随便什么方法将所有子串排序(例如二分hash求出后缀两两的lcp从而快速判断两个子串的lcp),二分答案,于是就是求多少方案使得每段的字典序都不小于M,因为从每个位置开始的合法长度是一段后缀,可以从后往前后缀和优化dp,$O(n^2logn)$

CF1314D Tourism

题意:$n \le 80$点简单有向图,边带权,求一个从1开始的回路,经过恰$K \le 10$条边,且不含奇环,最小化权值和

请先思考后再展开

只加入路径上的边是个二分图,等概率随机每个点在哪一侧得出可用的边,跑个$kn^2$的dp求最小环

错误的概率为$O(\frac{2^k-1}{2^k})$,发现正确率能达到要求

CF1314E Strange Function

题意:定义一个从数组a到多重集的映射$f(a)=每种数出现次数$,求可以是任意长度不超过n的非空数组a时$f^k(a)$的结果种类数,$n,k \le 2020$

请先思考后再展开

最优展开(倒序排序,展开a1个1,a2个2……)发现这玩意似乎做$O(log(logn))$次就没有意义了,然而常数不小,还是能手玩出写7、8次的nb结果的,没法讨论咋办?

事实上这种时候应该把这种特别nb的结果搜出来看看是什么量级的,必要的时候还可以打表

1
2
3
4
5
6
7
8
9
10
11
void dfs(int num,int len)
{
if(!num) return;dfs(num-1,len);
a[len]=num;vc<int> aa(len),bb;fo(i,0,len-1) aa[i]=a[i+1];
fo(pp,1,K)
{
int sum=0;fo(t,1,sz(aa)) sum+=aa[t-1];if(sum>n) return;if(pp==K) break;
bb.resize(sum);for(int now=sum,t=1;t<=sz(aa);t++) while(aa[t-1]--) bb[--now]=t;aa.swap(bb);
}
ans++;dfs(num,len+1);
}//k=3是451945,如果你写得太随意可能会很慢

那么我们只需要会做k=1和2,可以讨论了

k=1就是$\sum a_i \le n$,k=2就是$\sum ai*i \le n$,从大到小dp每种数的出现次数,调和级数可知复杂度都为$O(n^2ln(n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll f[N][N],g[N][N];//f(sum,cnt)
void main()
{
n=qread(),K=qread();
if(K>=3) dfs(n,1),write(ans);
else if(K==2)
{
f[0][0]=1;
fd(i,n,1)
{
fo(sum,0,n) fo(cnt,0,n/i) if(f[sum][cnt])//实际上是根号级别
for(int ad=0;sum+(cnt*2+ad+1)*ad/2*i<=n;ad++)
add(g[sum+(cnt*2+ad+1)*ad/2*i][cnt+ad],f[sum][cnt]);
fo(sum,0,n) fo(cnt,0,n/i) f[sum][cnt]=g[sum][cnt],g[sum][cnt]=0;
}ll ans=0;fo(sum,0,n) fo(cnt,1,n) add(ans,f[sum][cnt]);write(ans);
}
else
{
f[n+1][0]=1;fd(i,n,1) fo(sum,0,n) fo(ad,0,n/i) if(sum+ad<=n) add(f[i][sum+ad*i],f[i+1][sum]);
ll ans=0;fo(sum,1,n) add(ans,f[1][sum]);write(ans);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/fcff1fe4.html
转载请注明出处,谢谢!