526互联

Codeforces Round 905 (Div. 2)

发布时间 2023-10-24 17:22:42作者: 空気力学の詩

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++吧