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

Codeforces Round 963 (Div. 2)

时间：2024-08-11 20:05:17浏览次数：18  
标签：typedef 963 int Codeforces long Div include RI define

Preface

有懒狗上周日的比赛拖到这周日才写博客，我不说是谁

这场比赛的时候因为 C 数组没开两倍卡了 1h 最后写对拍才看出来，直接心态爆炸导致 D 没写完掉大分

A. Question Marks

签到

#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=405;
int t,n; char s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%s",&n,s+1);
		int c[4]={0,0,0,0},ans=0;
		for (RI i=1;i<=4*n;++i)
		if (s[i]!='?') ++c[s[i]-'A'];
		for (RI i=0;i<4;++i) ans+=min(c[i],n);
		printf("%d\n",ans);
	}
	return 0;
}

B. Parity and Sum

注意到偶数与奇数的和依然为奇数，因此我们的策略总是把所有偶数变成奇数

拿出最大的奇数，从小到大和所有偶数比较，能操作就吸收这个偶数得到更大的奇数；否则直接找一个奇数和最大的偶数操作后得到一个最大的数，这个数一定可以和所有偶数进行操作

#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d",&n); vector <int> odd,even;
		for (RI i=1;i<=n;++i)
		{
			scanf("%d",&a[i]);
			if (a[i]%2==1) odd.push_back(a[i]); else even.push_back(a[i]);
		}
		if (odd.empty()||even.empty()) { puts("0"); continue; }
		sort(odd.begin(),odd.end());
		sort(even.begin(),even.end());
		int flag=0; LL cur=odd.back();
		for (auto x:even) if (cur<x) { flag=1; break; } else cur+=x;
		printf("%d\n",(int)even.size()+flag);
	}
	return 0;
}

C. Light Switches

不难发现灯的状态以 \(2k\) 为周期变化，因此很容易想到把所有 \(t_i\) 投射到 \([0,2k-1]\) 的数组上

此时我们需要找到一个长为 \(k\) 的区间 \([l,r]\) 使得其包含所有的数，注意这个区间是在模意义下的可以跨过末尾

最后答案为最小的 \(T\equiv r\pmod {2k}\)，且所有的 \(t_i\le T\)，简单枚举即可

#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,k,a[N],c[N*2];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&n,&k);
		for (RI i=0;i<2*k;++i) c[i]=-1;
		for (RI i=1;i<=n;++i)
		scanf("%d",&a[i]),c[a[i]%(2*k)]=max(c[a[i]%(2*k)],a[i]);
		vector <int> pos;
		for (RI i=0;i<2*k;++i)
		if (c[i]!=-1) pos.push_back(i);
		if (pos.size()==1) { printf("%d\n",c[pos[0]]); continue; }
		bool flag=0;
		for (RI i=0;i<pos.size()-1;++i)
		{
			int l=pos[i+1],r=2*k+pos[i];
			if (r-l<k)
			{
				int ans=0; for (auto x:pos)
				if (x>=l) ans=max(ans,c[x]+r-x); else ans=max(ans,c[x]+r-2*k-x);
				printf("%d\n",ans); flag=1; break;
			}
		}
		if (!flag)
		{
			int l=pos[0],r=pos.back();
			if (r-l<k)
			{
				int ans=0; for (auto x:pos)
				ans=max(ans,c[x]+r-x);
				printf("%d\n",ans); flag=1;
			}
		}
		if (!flag) puts("-1");
	}
	return 0;
}

D. Med-imize

中位数的处理套路就是二分答案 \(x\)，然后将 \(\ge x\) 的数置为 \(1\)，\(<x\) 的数置为 \(0\)（置为 \(-1\) 也行），最后就是要使得留下的数的和大于某个定值

假设最后留下了 \(R\) 个数，观察这些数需要满足什么限制，手玩后发现它们下标对 \(k\) 取模的值从左到右一定为 \(1,2,\dots,k\)

因此很容易想到 DP，令 \(f_{i}\) 表示处理了前 \(i\) 个数，且最后选的数下标模 \(k\) 的值和 \(i\bmod 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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005;
int t,n,k,rem,a[N],f[N];
inline int calc(CI lim)
{
	int ret=0; for (RI i=1;i<=n;++i)
	{
		if ((i-1)%k+1>rem) { f[i]=0; continue; }
		if ((i-1)%k==0)
		{
			f[i]=(a[i]>=lim);
			if (i>=k) f[i]=max(f[i],f[i-k]);
		}else
		{
			f[i]=f[i-1]+(a[i]>=lim);
			if (i>=k) f[i]=max(f[i],f[i-k]);
		}
		ret=max(ret,f[i]);
	}
	return ret;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&n,&k);
		for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
		if (n<=k)
		{
			sort(a+1,a+n+1);
			printf("%d\n",a[(n+1)/2]);
			continue;
		}
		rem=n%k; if (rem==0) rem+=k;
		int l=1,r=1e9,mid,ret;
		while (l<=r) if (calc(mid=l+r>>1)>=rem/2+1) ret=mid,l=mid+1; else r=mid-1;
		printf("%d\n",ret);
	}
	return 0;
}

E. Xor-Grid Problem

观察到核心性质后就不难的一个题

不妨给矩形多扩展一行一列，其中最后一行的数字代表这列所有数字的异或和；最后列的数字代表这行所有数字的异或和

此时不难发现每个操作等价于交换某一行和最后一行，以及交换某一列和最后一列

但我们最后计算答案时不考虑多出的这一行一列，因此需要在选出某行某列删去后，将剩下的行列任意排布得到答案

不难发现行和列的贡献可以分开计算，以行为例，任意两行相邻排布的贡献就是它们对应列（去掉被删除的列后）上元素差的绝对值和

这形成了一个类似哈密顿路径的问题，可以简单状压 DP 解决，最后将删去某行某列的答案合并即可

认为 \(n,m\) 同阶，总复杂度 \(O(2^n\times n^3)\)

#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=16,INF=1e9;
int t,n,m,a[N][N],dr[N][N],dc[N][N],R[N][N],C[N][N],f[1<<N][N];
inline void solve(int d[N][N],CI n)
{
	for (RI i=0;i<(1<<n+1);++i)
	for (RI j=0;j<=n;++j) f[i][j]=INF;
	for (RI i=0;i<=n;++i) f[1<<i][i]=0;
	for (RI mask=0;mask<(1<<n+1);++mask)
	for (RI i=0;i<=n;++i) if ((mask>>i)&1)
	for (RI j=0;j<=n;++j) if (!((mask>>j)&1))
	f[mask|(1<<j)][j]=min(f[mask|(1<<j)][j],f[mask][i]+d[i][j]);
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&n,&m);
		for (RI i=0;i<=n;++i) a[i][m]=0;
		for (RI j=0;j<=m;++j) a[n][j]=0;
		for (RI i=0;i<n;++i) for (RI j=0;j<m;++j)
		scanf("%d",&a[i][j]),a[i][m]^=a[i][j],a[n][j]^=a[i][j];
		for (RI i=0;i<n;++i) a[n][m]^=a[i][m];
		for (RI rmv_c=0;rmv_c<=m;++rmv_c)
		{
			for (RI i=0;i<=n;++i) for (RI j=0;j<=n;++j)
			{
				if (i==j) continue; dr[i][j]=0;
				for (RI k=0;k<=m;++k)
				if (k!=rmv_c) dr[i][j]+=abs(a[i][k]-a[j][k]);
			}
			solve(dr,n);
			for (RI i=0;i<=n;++i)
			{
				R[i][rmv_c]=INF; int mask=((1<<n+1)-1)^(1<<i);
				for (RI j=0;j<=n;++j)
				if ((mask>>j)&1) R[i][rmv_c]=min(R[i][rmv_c],f[mask][j]);
			}
		}
		for (RI rmv_r=0;rmv_r<=n;++rmv_r)
		{
			for (RI i=0;i<=m;++i) for (RI j=0;j<=m;++j)
			{
				if (i==j) continue; dc[i][j]=0;
				for (RI k=0;k<=n;++k)
				if (k!=rmv_r) dc[i][j]+=abs(a[k][i]-a[k][j]);
			}
			solve(dc,m);
			for (RI i=0;i<=m;++i)
			{
				C[rmv_r][i]=INF; int mask=((1<<m+1)-1)^(1<<i);
				for (RI j=0;j<=m;++j)
				if ((mask>>j)&1) C[rmv_r][i]=min(C[rmv_r][i],f[mask][j]);
			}
		}
		int ans=INF; for (RI i=0;i<=n;++i) for (RI j=0;j<=m;++j)
		ans=min(ans,R[i][j]+C[i][j]); printf("%d\n",ans);
	}
	return 0;
}

F1. Dyn-scripted Robot (Easy Version)

感觉比 D,E 都简单，算是个经典套路题

对于这类反射类问题一个经典的处理就是不改变机器人的移动方向，而是将整个外框镜像一下，这样就不涉及修改操作序列了

手玩下会发现当机器人走到 \((x,y)\) 时，在原矩形中的位置相当于 \((x\bmod 2w,y\bmod 2h)\)

因此这题很容易求解，我们先求出进行一整个序列的操作后坐标的偏移量 \(\Delta x,\Delta y\)，然后枚举之前进行了 \(i\in[0,k-1]\) 次完整的操作

要回到 \((0,0)\) 等价于在某个位置的偏移量为 \((-i\times \Delta x,-i\times \Delta y)\)（模意义下），用 map 统计下即可

#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5;
int t,n,k,w,h; char s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d%d%s",&n,&k,&w,&h,s+1);
		map <pi,int> rst; int x=0,y=0;
		for (RI i=1;i<=n;++i)
		{
			switch (s[i])
			{
				case 'U': ++y; break;
				case 'D': --y; break;
				case 'R': ++x; break;
				case 'L': --x; break;
			}
			x=(x%(2*w)+2*w)%(2*w);
			y=(y%(2*h)+2*h)%(2*h);
			++rst[{x,y}];
		}
		LL ans=0; for (RI i=0;i<k;++i)
		{
			int dx=(-1LL*i*x%(2*w)+2*w)%(2*w);
			int dy=(-1LL*i*y%(2*h)+2*h)%(2*h);
			ans+=rst[{dx,dy}];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Postscript

感觉最近不管什么比赛只要不顺心就容易红温犯病，明明已经算是老登了心态还是一如既往的烂

今晚还有 Div1+2，周末还要去北京打百度之星的决赛，希望别暴毙地太难看了吧

标签：typedef,963,int,Codeforces,long,Div,include,RI,define
From： https://www.cnblogs.com/cjjsb/p/18353827

相关文章

  • CF1998 div2 & abc366
    1CF1.1B被诈骗了。我们的构造要向“每个区间只有1个数不一样考虑”。1.2C比较难。但是出的好。注意到如果我们不删除中位数这个位置的数，那么那个数是一定的。所以我们可以把\(k\)加到最大的可以加的数上，统计答案就在这个数，然后二分算中位数即可。其它策略？我们可不......
  • Codeforces Round 965 (Div. 2) 题解
    个人难度顺序：A<D<B<C<E。A.FindKDistinctPointswithFixedCenter如果\(k\)是偶数，构造\((x_c+i,yc+i)\)，其中\(-\frac{k}{2}\lei\le\frac{k}{2}\)。对于\(k\)是奇数，先加一个点\((xc,yc)\)，然后就变成偶数的情况了。B.MinimizeEqualSumSubarr......
  • Codeforces Round 965 (Div. 2) 补题记录（A,B,D,E1）
    speedforcesagain~A<E1<<B<D<<CA若\(k\equiv1(\bmod2)\)，则构造\((x,y)\)，\((x-1,y)\)，\((x+1,y)\)，\((x-2,y)\)，\((x+2,y)\)，\(\ldots\)。否则构造\((x-1,y)\)，\((x+1,y)\)，\((x-2,y)\)，\((x+2,y)\)，\(\ldots\)。#pra......
  • Codeforces Round 964 (Div. 4)
    这场的题不错,就是一直在inqueue......
  • div-固定在页面中间，不被其他元素覆盖
    最开始设置的子元素D是text-align:center，子元素C的内容过长的时候，会发现子元素D不在页面正中了所以需要把子元素D设置成固定中间，把子元素D设置成固定中间后，发现元素B把子元素D给覆盖了一部分，所以需要在父元素A和元素B之间加一个空的div，给div设置高度后，父元素A和元素B之间的距离......
  • Codeforces 165E Compatible Numbers 题解
    思路高维前缀和高维前缀和把数的二进制看成一个集合，二进制的每一位为\(1\)为全集\(V\)。根据题目描述，若两数\(a,b\)相容，则\(a\operatorname{and}b=0\)，容易发现，\(b\in\complement_{V}a\)，所以我们只需要用高维前缀和处理出\(\complement_{V}a\)的一个元素即可。......
  • Codeforces Round 964 (Div. 4)
    知识点1.对于两个数字，一个乘n，一个除以n，可以理解为n进制下的这个数乘10和除10。比如E题用这个知识点就可以很快的解决问题。题解A.A+BAgain?#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;voidsolve(){ strings; cin>>s; cout<<s[0]-'0'+s[1]-......
  • Codeforces Round 964 (Div. 4)
    CodeforcesRound964(Div.4)A送分B大意:两个人两张牌随机翻求a翻出来的牌比b大的可能#include<cstdio>#include<cmath>#include<algorithm>#include<iostream>#include<cstring>#include<vector>#defineepemplace_backusingnamespace......
  • Codeforces Round 964 (Div. 4) D. Slavic's Exam
    题目链接:https://codeforces.com/contest/1999/problem/D题目描述Slavic的考试非常难，需要您的帮助才能通过。以下是他正在努力解决的问题：存在一个字符串s，它由小写英文字母和可能零个或多个“？”组成。Slavic被要求将每个“？”更改为小写英文字母，使得字符串t成为字符串s的......
  • Codeforces Round 962 (Div. 3)
    A.Legs-------------------------------------题解------------------------------经典鸡兔同笼，数据范围不大，跑暴力就行点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){intn;cin>......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99