首页 > 其他分享 >Codeforces Round 905 (Div. 2)

Codeforces Round 905 (Div. 2)

时间：2023-10-24 17:23:13浏览次数：36  
标签：typedef const 905 int Codeforces long Div include define

Preface

周日晚上Div1,2,3同乐，但我不想打Div1，同时第三个号由于只打了两场没够到Div2的门槛，因此刚好打不了Div2，遂玩了一晚上LOL

今天补了下这场题感觉难度偏低，E之前的题都比较签，F刚开始没想到转化成差分最小准备去写扫描线+线段树了，后面发现其实可以写的很简单

A. Chemistry

签，设出现次数为奇数的字符有\(odd\)种，则当且仅当\(odd-k>1\)时无解

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,k,c[30]; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d%s",&n,&k,s+1); memset(c,0,sizeof(c));
		for (i=1;i<=n;++i) ++c[s[i]-'a']; int odd=0;
		for (i=0;i<26;++i) if (c[i]&1) ++odd;
		puts(odd-k>1?"NO":"YES");
	}
	return 0;
}

B. Raspberries

签，先判掉不用改的trivial情形，不难发现对于\(k=2,3,5\)都是只改一个数最优

对于\(k=4\)的情况需要稍作讨论，不过也很简单的说

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,k,x,c[10];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d",&n,&k); memset(c,0,sizeof(c));
		for (i=1;i<=n;++i) scanf("%d",&x),++c[x%k];
		if (c[0]) { puts("0"); continue; }
		if (k!=4)
		{
			int cur=1e9; for (i=1;i<k;++i)
			if (c[i]) cur=min(cur,k-i);
			printf("%d\n",cur); continue;
		}
		if (c[2]>=2) { puts("0"); continue; }
		if (c[2]==1) { puts(n==1?"2":"1"); continue; }
		int cur=1e9; for (i=1;i<k;++i)
		if (c[i]) cur=min(cur,k-i);
		if (n>=2) cur=min(cur,2);
		printf("%d\n",cur);
	}
	return 0;
}

C. You Are So Beautiful

刚开始没想到关键地方还觉得有点难，后面发现是个丁真题

这题的关键就是要注意到判断一个区间\([l,r]\)合法的充要条件，当\(a_{1\sim l-1}\)中没有\(a_l\)，且\(a_{r+1\sim n}\)中没有\(a_r\)时该区间合法

手玩一下会发现这个结论是对的，因此我们就可以统计出每个位置作为左右端点是否合法了

用前缀和统计下合法的左端点数量，然后在合法的右端点处累加答案即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,a[N],L[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		set <int> s; for (i=1;i<=n;++i)
		{
			L[i]=L[i-1]; if (!s.count(a[i])) ++L[i]; s.insert(a[i]);
		}
		LL ans=0; for (s.clear(),i=n;i>=1;--i)
		{
			if (!s.count(a[i])) ans+=L[i]; s.insert(a[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

D1. Dances (Easy version)&&D2. Dances (Hard Version)

这题Easy version很容易，首先给两个数组都排序，考虑如果删\(k\)个数，则\(a\)中一定删最大的\(k\)个，\(b\)中一定删最小的\(k\)个，因此可以二分答案

考虑Hard version的做法，我们不妨先把\(a\)中确定的\(n-1\)个数假定放在下标为\(2\sim n\)的位置

同时不妨设\(a\)中第\(i\)个数在\(b\)中第一个大于它的位置为\(d_i\)，则不难发现答案为\(\max (d_i-i)\)

注意到上面的式子和每个数的下标密切相关，而考虑我们逐步增大\(a_1\)的取值时，其实就是一个个地把数往前移动一位的过程

但如果暴力地枚举\(m\)个数肯定不行，不难发现很多连续的数其实可以一起处理，稍加分析我们发现关键的位置就是所有\(a_i\)的值以及所有\(b_i-1\)的值，离散化后双指针扫一遍即可

最后还要用个可删除堆来维护式子的最大值，总复杂度\(O(n\log n)\)

PS：后面发现队友写的做法都比我的简单，貌似就是\(a_1=1\)和\(a_1=m\)的答案只会相差\(1\)，然后可以二分/直接计算出分界点的样子，但我没有挖掘太多性质直接上了

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,m,a[N],b[N],d[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; scanf("%lld%lld",&n,&m); vector <int> rst;
		for (i=2;i<=n;++i) if (scanf("%lld",&a[i]),a[i]<=m) rst.push_back(a[i]);
		for (i=1;i<=n;++i) if (scanf("%lld",&b[i]),b[i]-1>0&&b[i]-1<=m) rst.push_back(b[i]-1);
		sort(a+2,a+n+1); sort(b+1,b+n+1); rst.push_back(m);
		sort(rst.begin(),rst.end()); rst.erase(unique(rst.begin(),rst.end()),rst.end());
		multiset <int> hp; for (i=2,j=1;i<=n;++i)
		{
			while (j<=n&&a[i]>=b[j]) ++j;
			d[i]=j; hp.insert(d[i]-i);
		}
		int l=1,ans=0; i=2; j=1; for (auto r:rst)
		{
			while (i<=n&&l>a[i]) hp.erase(hp.find(d[i]-i)),hp.insert(d[i]-(i-1)),++i;
			while (j<=n&&l>=b[j]) ++j;
			ans+=(r-l+1)*max({0LL,*hp.rbegin(),j-(i-1)}); l=r+1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

E. Time Travel

近几场遇到的最简单的E了，看完题目就会做了

不难发现类似于Dijkstra的过程，我们设\(f_i\)表示走到图上\(i\)这个点时，在序列上最少要花多少天

考虑一条\(i\to j\)，出现在时代\(k\)的边，不难发现我们要找的就是在\(a\)序列中第\(i\)个位置以后出现的第一个\(k\)的位置，用这个去更新\(f_j\)

而求这个只需要把每个时代在序列中出现的下标存下来，直接二分找到转移的代价即可

总复杂度\(O(n\log^2 n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,t,m,x,y,k,a[N],dis[N],vis[N]; vector <int> pos[N]; vector <pi> v[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&t),i=1;i<=t;++i)
	for (scanf("%d",&m),j=1;j<=m;++j)
	scanf("%d%d",&x,&y),v[x].push_back(pi(y,i)),v[y].push_back(pi(x,i));
	for (scanf("%d",&k),i=1;i<=k;++i) scanf("%d",&x),pos[x].push_back(i);
	for (i=1;i<=n;++i) dis[i]=k+1; dis[1]=0;
	priority_queue <pi,vector <pi>,greater <pi>> hp; hp.push(pi(0,1));
	while (!hp.empty())
	{
		int now=hp.top().se; hp.pop();
		if (vis[now]) continue; vis[now]=1;
		for (auto [to,w]:v[now])
		{
			auto it=upper_bound(pos[w].begin(),pos[w].end(),dis[now]);
			if (it!=pos[w].end()&&dis[to]>*it) hp.push(pi(dis[to]=*it,to));
		}
	}
	return printf("%d",dis[n]!=k+1?dis[n]:-1),0;
}

F. Minimum Array

这题最关键的就是要发现数组的字典序最小等价于其差分数组的字典序最小

然后我们就可以把问题转化到差分数组上了，这样区间修改就变成了单点修改

考虑怎么比较两个版本\(x,y(x<y)\)的差分数组的字典序大小，考虑我们只进行\([x+1,y]\)这些修改操作，然后找到当前数组中第一个值不为\(0\)的元素

如果这个元素\(<0\)则说明\(y\)的字典序小于\(x\)；反之若这个元素\(>0\)则说明\(y\)的字典序大于\(x\)

因此我们可以直接拿一个map来维护从上一个字典序最小的版本到当前版本的差分数组，每次只要根据第一个非零元素的正负判断是否更新答案即可

总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005;
int t,n,a[N],q,l[N],r[N],x[N],s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
		map <int,int> d; int pos=0; for (scanf("%d",&q),i=1;i<=q;++i)
		{
			scanf("%lld%lld%lld",&l[i],&r[i],&x[i]);
			d[l[i]]+=x[i]; d[r[i]+1]-=x[i];
			while (!d.empty()&&d.begin()->se==0) d.erase(d.begin());
			while (!d.empty()&&d.begin()->se<0) pos=i,d.clear();
		}
		for (i=1;i<=n;++i) s[i]=0;
		for (i=1;i<=pos;++i) s[l[i]]+=x[i],s[r[i]+1]-=x[i];
		for (i=1;i<=n;++i) s[i]+=s[i-1];
		for (i=1;i<=n;++i) printf("%lld%c",a[i]+s[i]," \n"[i==n]);
	}
	return 0;
}

Postscript

马上就要出发去桂林了，接下来要整理下板子啥的，希望RP++吧

标签：typedef,const,905,int,Codeforces,long,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/17785334.html

相关文章

  • CodeForces 946F Fibonacci String Subsequences
    洛谷传送门CF传送门duel的时候差点不会2400了。套路地，考虑每个\(F(x)\)中与\(s\)相同的子序列的贡献。设这个子序列为\(F(x)_{p_1},F(x)_{p_2},F(x)_{p_3},\ldots,F(x)_{p_n}\)。我们想要它成为一个子序列的子串，那么\(F(x)_{[p_1,p_n]}\)中除了\(p_1\simp_......
  • Codeforces 1862G 题解
    传送门题解因为有这个操作：将序列\(a\)加上\(\{n,n-1,\cdots,1\}\)，考虑差分。那么显然每次操作会将差分数组中的每个元素减去\(1\)，如果差分数组中有\(0\)，就会把\(0\)删除。所以可以发现差分数组中剩下的一定是操作前的最大值。由于操作后最大值还是最大值，最小值仍......
  • Codeforces Round 886 (Div. 4) 题解
    link我为什么还要vpdiv4场。。。A直接找最大的两个判断一下。voidsolve(){ inta[3]; cin>>a[0]>>a[1]>>a[2]; sort(a,a+3); if(a[2]+a[1]>=10)cout<<"YES\n"; elsecout<<"NO\n";}B按照题目意思模拟。voidsolv......
  • Codeforces Round#905 解题报告
    由于是解题报告不是过题报告，所以理所当然的放弃了后三题代码的写。感觉这场Div1D是cyh的菜，E是gjk的菜。我负责菜。只写Div1题的题解。A双指针可以做\(m=1\)你发现随便换\(a_1\)答案最多减少\(1\)，而且\(a_1\)越趋向于减少，所以可以二分分割点B最短路，怎么dij......
  • Codeforces Round 905 (Div. 2) D1. Dances (Easy version)（贪心+二分）
    CodeforcesRound905(Div.2)D1.Dances(Easyversion)思路：对于\(a\)，它的头默认为\(1\)，则\(a_0\)=\(1\)对于排完序的\(a\)与\(b\)数组最优为从\(a\)的结尾删除，从\(b\)的开头删除二分保留位数，删去\(n-mid\)位,即\(a\)从\(0\)开始，\(b\)从\(k\)（\(k=n-......
  • 「解题报告」Codeforces Round 905 (Div. 3)
    A.MorningYouaregivenafour-digitpincodeconsistingofdigitsfrom\(0\)to\(9\)thatneedstobeentered.Initially,thecursorpointstothedigit\(1\).Inonesecond,youcanperformexactlyoneofthefollowingtwoactions:Pressthecu......
  • Codeforces Round 905 (Div. 2) C. You Are So Beautiful（数据结构）
    CodeforcesRound905(Div.2)C.YouAreSoBeautiful定义：设数组abcd子数组定义：从原数组砍去前面若干元素，后边若干元素，剩余的数组。如：bc、ab子序列定义：从原数组删除若干元素，剩余元素拼凑一起，组成的数组。如：ac、bd思路：作为结果的连续子数组，如果他为[\(a_l\)，……，\(a_......
  • Educational Codeforces Round 144（CF1796 D~E） 题解
    D.MaximumSubarray题目链接十分钟秒了一道*2000，非常爽，但是个人感觉确实非常简单。下面令\(b_i=a_{i}-x\)，\(b_i'=a_i+x\)。因为\(k<=20\)，因此考虑一个复杂度与\(k\)相关的做法。不妨dp：设\(f_{i,j,0/1}\)表示考虑了前\(i\)个数，对\(j\)个数加上了\(x\)，第\(i\)......
  • Codeforces Round 905 (Div. 2)
    目录写在前面ABCD1/D2E写在最后写在前面比赛地址：https://codeforces.com/contest/1884oonp这场div2怎么才2k5人打啊我草里面还不知道多少大神的小号，呃呃打了1k3掉了75分也是牛逼A考虑如何拼出一个长度为\(n-k\)的回文串，先一对一对地拼，再看需不需要再顶上去一个......
  • Codeforces Round 905 - div.3(A B C D E)
    目录CodeforcesRound905(Div.3)A.MorningB.ChemistryC.RaspberriesCodeforcesRound905(Div.3)A.Morning模拟光标移动即可voidsolve(){ stringss; cin>>ss; charch='1'; intans=0; for(autoc:ss){ if(c!=ch){ intx=c,y=c......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99