526互联

Codeforces Round 908 (Div. 2)

发布时间 2023-11-20 15:17:09作者: 空気力学の詩

Preface

补一下之前期中考落下的CF

yysy因为这学期又开始断电了，所以除了周五周六晚上的CF可能都不一定会去打，都会以后面补题为主

A. Secret Sport

由于题目保证给出的状态合法，因此直接输出最后一个字符即可

#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=25;
int t,n; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	scanf("%d%s",&n,s+1),putchar(s[n]),putchar('\n');
	return 0;
}

B. Two Out of Three

设\(c_x\)表示数\(x\)出现的次数，则有解的充要条件就是\((\sum [c_i\ge 2])\ge 2\)，构造的话就随便搞一下就行了

#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=105;
int t,n,a[N],ans[N]; vector <int> v[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (i=1;i<=100;++i) v[i].clear();
		for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d",&a[i]),v[a[i]].push_back(i);
		int ret=0; for (i=1;i<=100;++i) ret+=(v[i].size()>=2);
		if (ret<2) { puts("-1"); continue; }
		int cur=0; for (i=1;i<=100;++i)
		{
			if (v[i].size()<2)
			{
				for (auto x:v[i]) ans[x]=1; continue;
			}
			if (cur==0)
			{
				++cur; ans[v[i][0]]=1;
				for (j=1;j<v[i].size();++j) ans[v[i][j]]=2;
			} else if (cur==1)
			{
				++cur; ans[v[i][0]]=1;
				for (j=1;j<v[i].size();++j) ans[v[i][j]]=3;
			} else
			{
				for (auto x:v[i]) ans[x]=1;
			}
		}
		for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

C. Anonymous Informant

观察到当我们选择一个fix point\(a_x\)时，下一步这个数一定会被换到\(n\)这个位置上

因此我们反过来从后往前推，\(n\)位置上的数就代表我们需要向右循环位移多少位来复原上一次操作

因此很容易发现无解的情况就是遇到大于\(n\)的数了，然后如果模拟\(k\)次或者发现成环后就可以直接退出了

#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 t,n,k,b[N],vis[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)
		scanf("%d",&b[i]),vis[i]=0;
		bool flag=1; int cur=n; for (i=1;i<=k;++i)
		{
			if (vis[cur]) break;
			if (b[cur]>n) { flag=0; break; }
			vis[cur]=1; cur=(cur-b[cur]-1+n)%n+1;
		}
		puts(flag?"Yes":"No");
	}
	return 0;
}

D. Neutral Tonality

首先不难发现\(\{b_m\}\)中的元素一定是先降序排列后再插入的，同时答案有一个下界就是\(\{a_n\}\)的LIS长度

考虑构造一种方案使得最后的LIS保持不变，我们可以先用树状数组求出\(f_i\)，表示以\(i\)开头向后能得到的LIS长度

然后我们找到所有\(f_i\)的最大值出现的位置\(i_1,i_2,\cdots,i_k\)，不难发现它们之间一定满足\(a_{i_1}\ge a_{i_2}\ge\cdots\ge a_{i_k}\)，然后我们用如下方式构造：

  • 将\(\{b_m\}\)中在\([a_{i_1},\infty)\)的元素降序放在\(a_{i_1}\)的前面
  • 将\(\{b_m\}\)中在\([a_{i_2},a_{i_1})\)的元素降序放在\(a_{i_2}\)的前面
  • 依次类推，最后将\(\{b_m\}\)中\(<a_{i_k}\)的元素降序放在\(a_{i_k}\)的后面即可

手玩一下会发现这样满足我们的要求，总复杂度\(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 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 t,n,m,a[N],b[N],f[N],rst[N],cnt;
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&-x)
		inline void init(CI n)
		{
			for (RI i=1;i<=n;++i) bit[i]=0;
		}
		inline int get(RI x,int ret=0)
		{
			for (;x<=cnt;x+=lowbit(x)) ret=max(ret,bit[x]); return ret;
		}
		inline void add(RI x,CI y)
		{
			for (;x;x-=lowbit(x)) bit[x]=max(bit[x],y);
		}
		#undef lowbit
}BIT;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
		scanf("%d",&a[i]),rst[i]=a[i];
		for (i=1;i<=m;++i) scanf("%d",&b[i]);
		sort(rst+1,rst+n+1); cnt=unique(rst+1,rst+n+1)-rst-1;
		for (i=1;i<=n;++i) a[i]=lower_bound(rst+1,rst+cnt+1,a[i])-rst;
		for (BIT.init(cnt),i=n;i>=1;--i)
		f[i]=BIT.get(a[i]+1)+1,BIT.add(a[i],f[i]);
		int mxf=*max_element(f+1,f+n+1); vector <int> pos;
		for (i=1;i<=n;++i) if (f[i]==mxf) pos.push_back(i);
		sort(b+1,b+m+1,greater <int>()); vector <int> ans;
		RI j=0,k=1; for (i=1;i<=n;++i)
		{
			if (j<pos.size()&&pos[j]==i)
			{
				while (k<=m&&b[k]>=rst[a[i]]) ans.push_back(b[k++]);
				ans.push_back(rst[a[i]]); ++j;
			} else ans.push_back(rst[a[i]]);
		}
		while (k<=m) ans.push_back(b[k++]);
		for (auto x:ans) printf("%d ",x); putchar('\n');
	}
	return 0;
}

E. Freedom of Choice

感觉比D题简单的说，首先令\(L=\sum_{i=1}^m l_i,R=\sum_{i=1}^m r_i\)，则最后选出的数个数一定在\([L,R]\)中

首先考虑判掉答案为\(0\)的情况，其实就是看\([L,R]\)中是否所有的数都出现过

不难发现因为出现的数的种类数\(\le 10^5\)，因此我们可以暴枚来判断，同时也说明了若最后答案不为\(0\)，\(R-L\)也是\(10^5\)级别的

因此我们还是可以直接枚举最后选了几个数，然后贪心地判断下最少的答案即可，这部分细节可以看代码

#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,m,n,l[N],r[N],a[N],c[N],sum[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; map <int,vector <pi>> rst; int all=0,L=0,R=0;
		for (scanf("%lld",&m),i=1;i<=m;++i)
		{
			scanf("%lld%lld%lld",&n,&l[i],&r[i]); L+=l[i]; R+=r[i];
			for (j=1;j<=n;++j) scanf("%lld",&a[j]); sum[i]=0;
			for (j=1;j<=n;++j) scanf("%lld",&c[j]),sum[i]+=c[j];
			for (j=1;j<=n;++j) rst[a[j]].push_back(pi(c[j],i));
		}
		bool flag=0; for (i=L;i<=R;++i)
		if (!rst.count(i)) { flag=1; break; }
		if (flag) { puts("0"); continue; }
		int ans=1e18; for (i=L;i<=R;++i)
		{
			int tot=R,ret=0;
			for (auto [c,id]:rst[i])
			{
				tot-=r[id]; int token=sum[id]-c;
				if (l[id]<=token&&token<=r[id]) { tot+=token; continue; }
				if (token<l[id]) ret+=l[id]-token,tot+=l[id]; else tot+=r[id];
			}
			if (tot<i) ret+=i-tot; ans=min(ans,ret);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

1D. Colorful Constructive

很奇怪这场Div2只有5个题，然后跑去看了眼Div1的D怎么过了这么多，后面随便猜了个结论发现就是对的

这题的思路其实很简单，就是从前往后加入颜色，我们每次都选择一个不和这个架子之前填的颜色发生冲突的颜色中，剩余数量最多的

感性理解下这个东西看起来就很对，实现的话用个堆模拟一下即可，复杂度\(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 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 t,n,m,x,s[N],d[N]; vector <int> ans[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; map <int,int> c; priority_queue <pi> hp;
		for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&x),++c[x];
		for (auto [x,y]:c) hp.push(pi(y,x));
		for (i=1;i<=m;++i) scanf("%d",&s[i]),ans[i].resize(s[i]+1);
		for (i=1;i<=m;++i) scanf("%d",&d[i]);
		bool flag=1; for (i=1;i<=m;++i)
		{
			for (j=1;j<=s[i];++j)
			{
				if (hp.empty()) { flag=0; break; }
				auto [x,y]=hp.top(); hp.pop();
				--c[y]; ans[i][j]=y;
				if (j>=d[i]&&c[ans[i][j-d[i]+1]]>0)
				hp.push(pi(c[ans[i][j-d[i]+1]],ans[i][j-d[i]+1]));
			}
			if (!flag) break;
			for (j=s[i]-d[i]+2;j<=s[i];++j) if (c[ans[i][j]]>0)
			hp.push(pi(c[ans[i][j]],ans[i][j]));
		}
		if (!flag) { puts("-1"); continue; }
		for (i=1;i<=m;++i)
		for (j=1;j<=s[i];++j) printf("%d%c",ans[i][j]," \n"[j==s[i]]);
	}
	return 0;
}

Postscript

还有昨天晚上的CF要补，不过由于今天晚上还要VP一场，就明后天再说吧