首页 > 其他分享 >Codeforces Round 889 (Div. 2) A-E

Codeforces Round 889 (Div. 2) A-E

时间:2023-08-02 17:36:56浏览次数:51  
标签:return int 889 Codeforces ans Div 正数 dp mod

传送门,不用谢。
A
给出排列每次可以交换两个数字,求最少多少次使得排列为错排。

考虑在原位的数字个数为\(cnt\)

则答案显然为\((cnt+1)>>1\)

B
求一个最大区间满足其中说有数字被\(n\)整除

极其有趣,注意到样例解释具有迷惑性。

考虑一个序列\([l,r]\)为答案 那么从中可以看出\(1|n,2|n,3|n,...r-l+1|n\)

由此可知\([1,r-l+1]\)也是答案。

那么做法就有了。

C1
给出一个长为\(n\)的序列\(-20\le a_i\le 20\)

每次可以使得\(a_i\)加上\(a_j\),\(i,j\)可以相等。让不超过\(50\)次使得整个序列是不降的。

随便做就行,考虑花\(5\)次培养一个极大值或者极小值。

然后对每个数挨个加譬如用极大值来做给当前\(a_i\)加上两次极大值或者加上一次极大值一次\(a_{i-1}\)。

这样最多\(45\)次。可以通过。

C2
考虑操作被压缩到了\(31\)次。这个界非常的紧。

想了\(1h\)之后发现先将所有数字都变得\(\le 0\)或者\(\ge 0\)再通过一次前缀和或后缀和即可。

前缀和要\(19\)次也就是说通过\(12\)次操作使得整个序列变成上述那样。

考虑正数负数一半一半且正数有最大值,这显然可以完成。

只需要考虑正数比较少且正数有最大值比如正数\(7\)个负数\(13\)个

负数至少是有一个\(-1\)的否则可以认为整个序列已经全部\(\ge 0\)了。

此时利用\(5\)次培养一个极小的负值来让正数全部\(\le 0\)即可。

恰好卡到了\(31\)次。

D
容易想到如果最终结束点是\(i\)那么所得到的价值可以直接知道\((\sum a_i)-(i-1)\)

考虑枚举所有的结束点,问题的关键是当前结束点是否可以到达。

就变成了一个可达性问题,设\(f_{i,j}\)表示用了前\(i\)个数,对于j是否可达。

转移就是普通的背包,这个经典问题可以利用bitset来优化。复杂度\(\frac{n^2}{w}\)

E
这就更有意思了。题意不再赘述。

将问题模型想成数轴上的点,每个点可以往前走。

和前面那个点相遇这个点就消失。

这样由期望的线性性我们假想一个点和前面那个点要么相遇要么不相遇。

每个点如果不和前面点相遇期望步数为\(m+1-a_i\)

那么只需要减去相遇步数即可利用\(f_{x,y}\)表示两点位置的期望要减去步数dp即可。

int n,k,m,T,cnt,lim,B;
int f[MAXN][MAXN];
int ans;
inline int dp(int x,int y)
{
	if(x==y)return m-x+1;
	if(y==m+1)return 0;
	if(f[x][y])return f[x][y];
	f[x][y]=((ll)dp(x+1,y)*G+(ll)dp(x,y+1)*G)%mod;
	return f[x][y];
}
signed main()
{
	freopen("1.in","r",stdin);
	sc(n);sc(m);
	int x=0,y;
	rep(1,n,i)
	{
		sc(y);
		ans=(ans+(m-y+1))%mod;
		if(x)ans=(ans+mod-dp(x,y))%mod;
		x=y;
	}
	put(ans);
	return 0;
}

标签:return,int,889,Codeforces,ans,Div,正数,dp,mod
From: https://www.cnblogs.com/chdy/p/17601287.html

相关文章

  • 1853 Round 887 (Div. 2)
    Desorting定义一次操作为选定一个\(i\),令\(a_{1\simi}\)自增,\(a_{i+1\simn}\),自减,求使得整个序列无序的最小操作次数若序列一开始就无序,输出\(0\)否则找到相邻两数差值最小的位置,在这个位置不断使用操作,可以证明这是最优方案#include<bits/stdc++.h>usingna......
  • 1851 Round 888 (Div. 3)
    EscalatorConversations判断两人台阶是否为\(k\)的倍数且在\((0,m)\)内即可#include<bits/stdc++.h>usingnamespacestd;signedmain(){ intT; scanf("%d",&T); for(intn,m,k,H;T;--T){ scanf("%d%d%d%d",&n,&m,&a......
  • 1848 Round 885 (Div. 2)
    VikaandHerFriends给定一张网格图,Vika在\((x,y)\)处,她的\(k\)个朋友分别在\((x_{1\simk},y_{1\simk})\)处,每次所有人都必须移动到相邻各格子,询问Vika能否永远逃离她烦人的朋友考虑对格子进行黑白染色,每次移动一定会变换格子颜色,那么只有相同颜色的人才会碰......
  • 1855 Round 889 (Div. 2)
    DaltontheTeacher给定序列\(a_{1\simn}\),定义一次操作为交换序列中的某两个数,求使得\(\foralli,a_i\not=i\)的最少操作次数对于所有数据,\(n\leq10^5\)计算出\(a_i=i\)的位置数量\(sum\),若\(sum\)为偶数,则让其两两配对交换即可;否则会剩下一个数,在其他......
  • Educational Codeforces Round 152 (Rated for Div. 2)
    Preface经典秒完SB题然后开始坐牢1h,写了个E的假算法T在24个点就不管了打lol去了妈的怎么稍微难点的题就是想不到呢A.MorningSandwich签到#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>......
  • Codeforces Round 889 (Div. 2)
    CodeforcesRound889(Div.2)T1​ 思路:我们将\(i\nep_i\)的数量记下来,再判断这个数的奇偶性,如果为偶,那么答案就为这个数/2,如果为奇,那么就是这个数/2+1。T2​ 思路:我们枚举\(1\simn\),我们记录连续是\(n\)的因数的个数,如果不连续了就\(break\),答案就是个数......
  • Codeforces Round 885 (Div. 2)
    CodeforcesRound885(Div.2)A.VikaandHerFriends题目大意太长了click思路可以手动模拟一下,可以发现当两个人的\(x+y\)值就行相同的就能抓到了#include<bits/stdc++.h>usingnamespacestd;intmain(){intT;cin>>T;while(T--){......
  • Codeforces Round 887 (Div. 2)
    CodeforcesRound887(Div.2)A.Desorting题目大意给出一个长度为\(n\)的数组\(a\),可以执行这个操作任意次。选择一下标\(i\),使得\(a_{1...i}\)加上\(1\),\(a_{i+1...n}\)减少\(1\)。问最少几次操作使得数组\(a\)无序。思路首先如果\(a\)原本就无序的......
  • Codeforces Round 885 (Div. 2) 题解
    A.VikaandHerFriends看一下样例就可以发现,Vika以及她的朋友都不能走对角线,在这种情况下Vika和朋友的距离为偶数,且朋友一定追不上Vika所以直接判断Vika和朋友的距离是否都为偶数即可B.VikaandtheBridge显然贪心,枚举颜色,找到相邻距离最大的两块木板,记该距离为\(......
  • Practice on Codeforces and Atcoder in May
    CF补题题解2023.5说明:CF题直接去luogu看翻译,AT题会附上简要题意CF1821E先考虑如何高速计算权值一个显而易见的贪心是尽量在右边取括号消除,设右括号为1,左括号为-1那么我们每一次消除的括号\(i,i+1\)都满足了\(i+1\)的右边剩下的全部是右括号,代价就是往右数的个数更进一......