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

Codeforces Round 908 (Div. 2)

时间：2023-11-20 15:25:29浏览次数：40  
标签：typedef const int 908 Codeforces long Div include define

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一场，就明后天再说吧

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

相关文章

  • Selenium4+python被单独定义＜div＞的动态输入框和二级下拉框要怎么定位?
    今天在做练习题的时候,发现几个问题捣鼓了好久,写下这篇来记录问题一:有层级的复选框无法定位到二级目录 对于这种拥有二级框的选项无法定位,也不是<select>属性.我们查看下HTML,发现它是被单独封装在body内拥有动态属性的独立<div>,当窗口点击的时候才会触发. 解......
  • Codeforces Round 910 (Div. 2)
    CodeforcesRound910(Div.2)基本情况做A题的速度比之前快多了，大概20分钟搞定。B题想了一个贪心错解，想用链表实现，但是不熟练，实现太慢，而且还被hack了。但是自己hack掉了，造数据上进步。B.MilenaandAdmirer贪心思路发现一个大于下一个的数，直接对半分，如果不能对半就小的在......
  • Codeforces Round 909 (Div. 3)
    CodeforcesRound909(Div.3)基本情况第一次在CF上AC了超过一道题。（毕竟是Div3）B题卡住了很久。D没有深入思考。[B.250ThousandTonsofTNT](Problem-B-Codeforces)一开始死活过不了的代码：#include<iostream>#include<cstdio>#include<cstring>#inc......
  • CF909 div3
    CF909div3A.GamewithIntegers题意两人博弈，给出一个数字，每人每次可以选择令该数字+1或者-1。如果在10步以内可以令数字为3的倍数，先手胜。否则后手胜。数据范围多组数据，\(1<=T<=100,1<=n<=1000\)题解后手可以恢复现场，所以先手最多只能有效操作1次。若+1或者-1......
  • Educational Codeforces Round 13 E
    tilian最开始看错了以为是可以任意选择两人or选择一人胜出但题意是可以选择下一个擂主是谁考虑dp的话我们显然需要记录一个state以及当前擂主是谁转移就是dp[state][i]=max(dp[state][i],dp[state(1<<j)][j]*a[i][j]+dp[state(1<<i)]*a[j][i])意义是我们枚举他后一个交......
  • Codeforces Round 909 (Div. 3) A-E
    CodeforcesRound909(Div.3)A.GamewithIntegers题意：两人轮流操作，可以加一或减一，若结果能被3整除则输出First，否则输出Second思路：若n不能被3整除，则第一个人可以直接通过加一或减一使结果被3整除，反之则一定不能代码：#include<bits/stdc++.h>usingnamespacestd;cons......
  • cf1864C. Divisor Chain
    https://codeforces.com/contest/1864/problem/C思维越来越僵化了假如\(n=2^k\)，直接每次/2就行。否则，我们可以考虑如何转化成上面的情况令\(n=2^kx\)，那么我们显然可以转移到\(n=2^k(x-1)\)，因为x是奇数，所以2的次幂会加一，最后变成\(2^k\)次方的时候，每个数最多出现两次，正好符合......
  • 一个可以拖拽缩放的div？
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"/><metahttp-equiv="X-UA-Compatible"content="IE=edge"/><metaname="viewport"content="width=de......
  • C++ signal(SIGFPE,handler) ignore division by 0 exception
    #include<stdexcept>#include<chrono>#include<csetjmp>#include<ctime>#include<fstream>#include<iostream>#include<iomanip>#include<signal.h>#include<sstream>#include<thread>#incl......
  • 【LGR-166-Div.4】洛谷入门赛17
    【LGR-166-Div.4】洛谷入门赛#17比赛地址这次是div4的难度，整体不算是很难，很适合小白玩家[10月入门赛-A]食堂题目描述为了给师生提供良好的用餐体验，洛谷小学的食堂坚持现炒、现做每一道菜肴。洛谷小学一共有\(a\)名老师和\(b\)名学生。食堂的营养师为每位师生的用餐进......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99