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

Codeforces Round 951 (Div. 2)

时间：2024-07-06 19:30:11浏览次数：16  
标签：typedef 951 Codeforces long int Div include se define

Preface

这场由于下午四点约好了和祁神打乒乓球，因此两点开了一场VP，结果困得要死D题一个特判写挂了没看出来调了贼久

然后E题秒出正解，但因为一个极其傻逼的地方挂了又没调出来，鉴定为纯纯的飞舞

A. Guess the Maximum

签到，每次选的一定是相邻的两个

#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=50005;
int t,n,a[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]);
		int ans=max(a[1],a[2]); for (i=2;i<n;++i) ans=min(ans,max(a[i],a[i+1]));
		printf("%d\n",ans-1);
	}
	return 0;
}

B. XOR Sequences

手玩一下发现其实就是找 \(x,y\) 从低到高第一个不一样的位 \(h\)，答案就是 \(2^h\)

#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;
int t,x,y;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d",&x,&y);
		for (i=0;i<30;++i) if (((x>>i)&1)!=((y>>i)&1))
		{
			printf("%d\n",(1<<i)); break;
		}
	}
	return 0;
}

C. Earning on Bets

根据人类直觉不难发现让所有的 \(k_i\times a_i\) 都相等是最优的策略，如果这样都不合法说明 \(\sum \frac{1}{k_i}>1\)，此时不管怎么安排肯定都是无解的

构造答案的话令所有的 \(k_i\times a_i\) 都等于 \(\operatorname{lcm}(k_i)\) 即可

#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=55;
int t,n,a[N],b[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]);
		LL g=a[1]; for (i=2;i<=n;++i) g=g/__gcd(g,1LL*a[i])*a[i];
		LL sum=0; for (i=1;i<=n;++i) sum+=g/a[i];
		if (sum>=g) puts("-1"); else
		{
			for (i=1;i<=n;++i) printf("%d%c",g/a[i]," \n"[i==n]);
		}
	}
	return 0;
}

D. Fixing a Binary String

考虑枚举操作的前缀长度 \(p\) ，判断操作后是否合法需要满足哪些要求

首先此时序列的开头变成了 \(p+1\)，因此首先需要判断 \([p+1,n]\) 这一段能否作为一段合法的开头

然后就是要把 \([1,p]\) 这段翻转后接到后面去，就需要判断 \([p:1]\) 这一段能否作为一段合法的后缀

与此同时中间接合处的情况还需要讨论一下：

  • 若 \(k\mid p\)，此时需要满足 \(s_p\ne s_n\)，因为这种情况下 \(s_p\) 和 \(s_n\) 分属于不同的块；
  • 若 \(k\nmid p\)，此时需要满足 \(s_p=s_n\)，因为这种情况下 \(s_p\) 和 \(s_n\) 分属于同一个块；

前后缀的合法情况很容易写出递推的预处理式子，总复杂度 \(O(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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,k,pre[N],suf[N],pfx[N]; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d%s",&n,&k,s+1);
		auto check=[&](void)
		{
			for (RI i=2;i<=k;++i) if (s[i]!=s[1]) return 0;
			for (RI i=1;i<=n-k;++i) if (s[i]==s[i+k]) return 0;
			return 1;
		};
		if (check()) { printf("%d\n",n); continue; }
		for (i=1;i<=n;++i) pfx[i]=pfx[i-1]+(s[i]-'0');
		auto same=[&](CI l,CI r)
		{
			int tmp=pfx[r]-pfx[l-1];
			return tmp==0||tmp==r-l+1;
		};
		for (i=1;i<=k;++i) pre[i]=same(1,i);
		for (i=2;i<=n/k;++i)
		{
			for (j=(i-1)*k+1;j<=i*k;++j)
			pre[j]=(pre[(i-1)*k]&&same((i-1)*k+1,j)&&s[(i-1)*k]!=s[j]);
		}
		for (i=n;i>=n-k+1;--i) suf[i]=same(i,n);
		for (i=n-k;i>=1;--i) suf[i]=(same(i,i+k-1)&&suf[i+k]&&s[i]!=s[i+k]);
		//for (i=1;i<=n;++i) printf("%d%c",pre[i]," \n"[i==n]);
		//for (i=1;i<=n;++i) printf("%d%c",suf[i]," \n"[i==n]);
		bool flag=0; for (i=1;i<n;++i)
		if (pre[i]&&suf[i+1])
		{
			if ((i%k!=0&&s[i]==s[n])||(i%k==0&&s[i]!=s[n]))
			{
				printf("%d\n",i); flag=1; break;
			}
		}
		if (!flag) puts("-1");
	}
	return 0;
}

E. Manhattan Triangle

刚好打这场的前一天和队友聊到了曼哈顿距离转切比雪夫距离的trick，然后这个题就可以直接套

进行 \((x,y)\to (x+y,x-y)\) 的变换后，要找的三个点两两间切比雪夫距离均为 \(d\)

显然此时三个点的距离不能都在横坐标或者纵坐标上体现，因此分析后可以得到这三个点必为以下两种情况之一：

  • 两点横坐标均为 \(x\)，纵坐标 \(|y_1-y_2|=d\)，此时第三个点横坐标为 \(x\pm d\)，纵坐标 \(\in[y_1,y_2]\)；
  • 两点纵坐标均为 \(y\)，横坐标 \(|x_1-x_2|=d\)，此时第三个点纵坐标为 \(y\pm d\)，横坐标 \(\in[x_1,x_2]\)；

以前者为例，我们把所有横坐标相同的点存入一个 vector 中

枚举确定公共的 \(x\) 的值，用 two pointers 找出纵坐标之差符合要求的点对，然后在 \(x\pm d\) 对应的 vector 里二分找符合要求的点即可

后者只需要把横纵坐标交换后再做一遍即可，总复杂度 \(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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,S=600000;
int t,n,d,x[N],y[N]; vector <pi> p[2*S+5];
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,&d),i=1;i<=n;++i)
		{
			int a,b; scanf("%d%d",&a,&b);
			x[i]=a+b; y[i]=a-b;
		}
		auto solve=[&](void)
		{
			RI i,j; vector <int> X;
			for (i=1;i<=n;++i)
			{
				p[x[i]+S].push_back(pi(y[i],i));
				X.push_back(x[i]+S);
			}
			sort(X.begin(),X.end());
			X.erase(unique(X.begin(),X.end()),X.end());
			auto clear=[&](void)
			{
				for (auto x:X) p[x].clear();
			};
			for (auto x:X) sort(p[x].begin(),p[x].end());
			for (auto x:X)
			{
				for (j=0,i=1;i<p[x].size();++i)
				{
					while (p[x][i].fi-p[x][j].fi>d) ++j;
					int y_1=p[x][j].fi,y_2=p[x][i].fi;
					if (y_2-y_1!=d) continue;
					auto find=[&](vector <pi>& vec,CI y_1,CI y_2)
					{
						auto it=lower_bound(vec.begin(),vec.end(),pi(y_1,0));
						if (it==vec.end()||it->fi>y_2) return pi(-1,-1);
						return *it;
					};
					pi tmp=find(p[x-d],y_1,y_2);
					if (tmp.se!=-1)
					{
						printf("%d %d %d\n",p[x][i].se,p[x][j].se,tmp.se);
						clear(); return 1;
					}
					tmp=find(p[x+d],y_1,y_2);
					if (tmp.se!=-1)
					{
						printf("%d %d %d\n",p[x][i].se,p[x][j].se,tmp.se);
						clear(); return 1;
					}
				}
			}
			clear(); return 0;
		};
		if (solve()) continue;
		for (i=1;i<=n;++i) swap(x[i],y[i]);
		if (solve()) continue;
		puts("0 0 0");
	}
	return 0;
}

Postscript

这场F题感觉挺难的，想了下不太会做索性直接开摆

标签：typedef,951,Codeforces,long,int,Div,include,se,define
From： https://www.cnblogs.com/cjjsb/p/18287639

相关文章

  • 沪越联赛 - 2024年6月月赛Div2 题解
    问题A:替换题目描述小明每次注释的时候都写\(n\)个/。小红看了小明的程序，觉得太难看了，那么多/，所以决定把这些没用的/都去掉。小红定义了一个宏命令，每次可以将所有连续的\(m\)个/替换成空（注意不是空格）小明得知了小红的企图后非常着急，因为他知道光把/都去掉，那么原......
  • YOLOv8改进 | Conv篇 | 添加DiverseBranchBlock多元分支模块（有效涨点，重参数化模块高效
    鱼弦：公众号【红尘灯塔】，CSDN博客专家、内容合伙人、新星导师、全栈领域优质创作者、51CTO(Top红人+专家博主)、github开源爱好者（go-zero源码二次开发、游戏后端架构https://github.com/Peakchen）YOLOv8改进|Conv篇|添加DiverseBranchBlock多元分支模块（有效涨点，重参数......
  • HT-014 Div3 扫雷 题解 [ 绿 ] [ 二维差分 ]
    分析观察到是曼哈顿距离\(\ler\)的范围可以扫到，联想到如下图形：左边是\(r=1\)可以扫到的范围，右边是\(r=2\)可以扫到的范围。于是，我们只要对这样的图形在\(1000*1000\)的格子里差分一下就好了。但这样的复杂度是\(O(nm)\)的，会死的很惨。优化不难发现这个图形是一......
  • HT-014 Div3 跳棋 题解 [ 黄 ] [ 并查集 ] [ 树型结构 ]
    分析依旧是一个连通块题。观察题面不难发现两个重要性质：一个跳棋只能以它旁边的两个跳棋为中点跳跃，且满足跳跃路线中除中点以外没有其它跳棋阻挡。只有我们的跳棋可以移动。跳棋的操作具有可逆性/对称性。第三条性质可以这么理解，就是一个跳棋跳过去之后，它还可以跳回来。......
  • Codeforces Round 953 (Div. 2)
    CodeforcesRound953(Div.2)闲来无事水题解。A。B。C显然\(k\)是偶数。考虑\(k\)的上界，\(p_{1}=n,p_{n}=1\)，产生\(2n-2\)的贡献，同时递归到子问题。那么等价于有\(1\simn-1\)的物品可以有贡献，可以直接贪心构造。D好像做复杂了。\(i\)能赢有两种情况：没......
  • Codeforces Round 879 (Div. 2)
    vp的非常炸裂的一把。A喵了B卡住了，到最后都没做出来。其实思路已经有了，但是我觉得是错的，就难蚌。其实就是找第一位不一样的，后面就是0和9这样的最优的选择了。C其实推导一下就能够发现其实BOB的操作没什么意义，直接统计两个字符串不一样的地方有几个，然后反转一下再统计，这两个取......
  • Codeforces Round 953 (Div. 2)
    Preface经典30min写完前四题，然后E题大脑宕机想复杂，最后写了一坨很难调试的东西成功把自己送走趁着Div1的训练还没开始赶紧找回点状态吧，不然到时候保准天天坑队友的说A.AliceandBooks不难发现\(a_n\)一定会取，那么在剩下的里面找一个最大的自成一堆就行#include<cstdio......
  • Codeforces 19xx 合集
    CF1974A.PhoneDesktop每个手机只能填两个大的，先把大的填完，然后剩下的地方用小的补上，最后小的不够用了再拿新的手机。B.SymmetricEncoding直接模拟吧。C.BeautifulTriplePairs一个比较好写的做法，是先不管那个不同的，把所有存在两个相同的都加上，最后减去三遍三个......
  • Codeforces Round 941 (Div. 2) cf 941 div2 A~D
    每题都有AC代码在伸缩代码框请留意！！A.CardExchange-------------------------------------------题解----------------------------------选择任意K张相同的牌替换成k-1张任意的牌，也就是说只要有一组牌相同的数量大于k就可以获得最大k-1相同的其他牌，按照这个策略便可以替换掉......
  • CF950Div3 G. Yasya and the Mysterious Tree（01Trie）
    Problem题目地址Solution设\(s[u]\)是根到\(u\)路径上的异或和，树上任意两点\(u,v\)的路径异或和可表示为\(s[u]\opluss[v]\)。考虑查询操作?vx即求\(\max\{s[v]\opluss[u]\oplusx|\\1\leu\len,u\not=v\}\)，若把\(s[v]\oplusx\)看作一个整体......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99