首页 > 其他分享 >Pinely Round 4 (Div. 1 + Div. 2)

Pinely Round 4 (Div. 1 + Div. 2)

时间：2024-07-29 20:17:17浏览次数：10  
标签：typedef const int Pinely long Div include Round define

Preface

难得地有直觉的一场，50min 过了前 5 题后形式大好，然后 F 也一眼看出了有个斐波那契的上界

结果写了个暴力判断交上去一直挂，前面一直以为是一定有解的阈值设错了，没想到挂了好几发后发现暴力漏了一种 Case，真是唐完了

A. Maximize the Last Element

不难发现只有奇数位置上的数可以保留下来

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

B. AND Reconstruction

对于每一位分别考虑，若 \(b_i\) 该位为 \(1\)，则 \(a_i\) 和 \(a_{i+1}\) 的这一位都必须是 \(1\)；然后默认其余的都为 \(0\) 最后检验下是否合法即可

#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,a[N],b[N],c[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<n;++i) scanf("%d",&b[i]);
		for (i=1;i<=n;++i) a[i]=0; bool flag=1;
		for (j=0;j<30&&flag;++j)
		{
			for (i=1;i<=n;++i) c[i]=0;
			for (i=1;i<n;++i)
			if ((b[i]>>j)&1) c[i]=c[i+1]=1;
			for (i=1;i<n;++i)
			if (!((b[i]>>j)&1)&&c[i]&&c[i+1]) { flag=0; break; }
			for (i=1;i<=n;++i) if (c[i]) a[i]|=(1<<j);
		}
		if (!flag) { puts("-1"); continue; }
		for (i=1;i<n;++i) assert((a[i]&a[i+1])==b[i]);
		for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
	}
	return 0;
}

C. Absolute Zero

神秘构造题，看完题面就感觉是个那一堆 \(2\) 的幂次来构造，还在想怎么会有无解的情况

后面仔细一想发现如果初始序列中又有奇数又有偶数，则每次操作后序列仍然是有奇有偶的，因此永远不可能全为 \(0\)

否则手玩一波后会发现对于偶数就用形如 \(2^{29},2^{28},\dots,2^1,1,1\) 这样的构造方式；奇数就用形如 \(2^{29},2^{28},\dots,2^1,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 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)
	{
		RI i; int c[2]={0,0};
		for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),++c[a[i]&1];
		if (c[0]>0&&c[1]>0) { puts("-1"); continue; }
		if (c[0]>0)
		{
			puts("31");
			for (i=29;i>=0;--i) printf("%d ",1<<i);
			puts("1");
		} else
		{
			puts("30");
			for (i=29;i>=0;--i) printf("%d%c",1<<i," \n"[i==0]);
		}
	}
	return 0;
}

D. Prime XOR Coloring

很需要直觉的一个题，不然可能想半天想不出来

由于自然数中最小的不是质数的数是 \(4\)，因此考虑让同色的数之间的异或值都是 \(4\) 的倍数就可以构造一种符号要求的做法

显然将所有数按照它们模 \(4\) 的余数分组，同组数染一种颜色即可，这样组内任意两数异或值都是 \(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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d",&n);
		if (n==1) puts("1\n1"); else
		if (n==2) puts("2\n1 2"); else
		if (n==3) puts("2\n1 2 2"); else
		if (n==4) puts("3\n1 2 2 3"); else
		if (n==5) puts("3\n1 2 2 3 3"); else
		{
			puts("4");
			for (RI i=1;i<=n;++i) printf("%d%c",i%4+1," \n"[i==n]);
		}
	}
	return 0;
}

E. Coloring Game

思路很简单的一个题，感觉只有正常的 Div.2 D 的难度

首先考虑来个黑白染色，如果给出的图不是二分图那么选先手，保证每次都给 1 2 两种颜色，此时一定必胜

否则如果给出的图是二分图就选后手，不妨设原图中的黑点对应颜色 \(1\)，白点对应颜色 \(2\)

对于交互器每次给出的两种颜色，如果存在颜色 \(1/2\) 且它们对应的点还没有被染色，那么就直接对应地染色

否则如果不存在上述情况，则必然存在一种颜色已经把对应的点涂完了，那剩下没涂完的点都用颜色 \(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=10005;
int t,n,m,x,y,col[N]; bool flag; vector <int> v[N],c[2];
inline void DFS(CI now)
{
	for (auto to:v[now])
	if (col[to]==-1) col[to]=col[now]^1,DFS(to);
	else if (col[to]==col[now]) flag=0;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d",&n,&m);
		for (i=1;i<=n;++i) v[i].clear(),col[i]=-1;
		for (i=1;i<=m;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
		flag=1; c[0].clear(); c[1].clear();
		for (i=1;i<=n;++i) if (col[i]==-1) col[i]=0,DFS(i);
		if (!flag)
		{
			printf("Alice\n"); fflush(stdout);
			for (i=1;i<=n;++i)
			{
				printf("1 2\n"); fflush(stdout);
				int x,y; scanf("%d%d",&x,&y);
			}
		} else
		{
			printf("Bob\n"); fflush(stdout);
			for (i=1;i<=n;++i) c[col[i]].push_back(i);
			for (i=1;i<=n;++i)
			{
				int x,y; scanf("%d%d",&x,&y);
				if ((x==1||y==1)&&!c[0].empty())
				{
					printf("%d 1\n",c[0].back());
					c[0].pop_back(); fflush(stdout); continue;
				}
				if ((x==2||y==2)&&!c[1].empty())
				{
					printf("%d 2\n",c[1].back());
					c[1].pop_back(); fflush(stdout); continue;
				}
				if (!c[0].empty())
				{
					printf("%d 3\n",c[0].back());
					c[0].pop_back(); fflush(stdout);
				} else
				{
					printf("%d 3\n",c[1].back());
					c[1].pop_back(); fflush(stdout);
				}
			}
		}
	}
	return 0;
}

F. Triangle Formation

神秘观察题，发现一定有解的下界后就很简单了

考虑如果在一堆棍子里找一个三角形，那么排序之后找相邻的三个一定最优

因此如果要构造一个三角形都找不到的数据，则木棍的长度一定形如斐波那契数列

简单计算发现第 \(44\) 个斐波那契数大于 \(10^9\)，然后就说明当区间长度 \(>50\) 时一定有解

现在考虑怎样快速判断能否找到两个三角形，不妨先给所有数从小到大排序，并钦定第一个三角形的最长边小于等于第二个三角形的最长边

枚举第一个三角形的最长边，分以下三种情况讨论：

  • 第二个三角形三条边都在当前这条边后面，这个可以预处理每个后缀的信息
  • 第二个三角形较长的两条边都在当前这条边后面，这个只需要求出后缀中差值最小的两条边，然后每次在前面找一个是否大于这个差值的边
  • 第二个三角形最长的一条边在当前这条边后面，此时需要找到前面还没被用的最长的两条边，和之后的最短的边比较下即可

那么我们再枚举第一个三角形的次长边，然后用一个 two pointers 扫一下即可，单组询问复杂度 \(\min^2(50,r-l+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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005,INF=1e9;
int n,q,a[N],l,r;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&q),i=1;i<=n;++i) scanf("%d",&a[i]);
	while (q--)
	{
		scanf("%d%d",&l,&r);
		if (r-l+1>50) { puts("YES"); continue; }
		vector <int> vec;
		for (i=l;i<=r;++i) vec.push_back(a[i]);
		sort(vec.begin(),vec.end());
		vector <int> suf(vec.size(),0),d(vec.size(),INF);
		int mnp=INF,mxp=-INF;
		for (i=0;i+2<vec.size();++i)
		if (vec[i]+vec[i+1]>vec[i+2])
		suf[i]=1,mnp=min(mnp,i),mxp=max(mxp,i);
		if (mxp-mnp>=3) { puts("YES"); continue; }
		for (i=vec.size()-1;i>=1;--i) suf[i-1]|=suf[i];
		for (i=vec.size()-2;i>=0;--i)
		d[i]=min(d[i+1],vec[i+1]-vec[i]);
		bool flag=0;
		for (i=2;i+1<vec.size()&&!flag;++i)
		{
			for (RI j=i-1,k=0;k<j;--j)
			{
				while (k<j&&vec[k]+vec[j]<=vec[i]) ++k;
				if (k>=j) continue;
				if (suf[i+1]) { flag=1; break; }
				int mxp=i-1;
				while (mxp==j||mxp==k) --mxp;
				if (mxp>=0&&vec[mxp]>d[i+1]) { flag=1; break; }
				if (mxp<=0) continue;
				int smxp=mxp-1;
				while (smxp==j||smxp==k) --smxp;
				if (smxp>=0&&vec[smxp]+vec[mxp]>vec[i+1]) { flag=1; break; }
			}
		}
		puts(flag?"YES":"NO");
	}
	return 0;
}

Postscript

后面的题银牌✌比赛时快 2h 都没做出来，说明肯定不是我能做的了，直接白兰

标签：typedef,const,int,Pinely,long,Div,include,Round,define
From： https://www.cnblogs.com/cjjsb/p/18330970

相关文章

  • 易优CMS模板标签uibackground背景图片在模板文件index.htm中调用uibackground标签，实现
    【基础用法】标签：uibackground描述：背景图片上传标签，使用时结合html一起才能完成可视化布局，只针对具有可视化功能的模板。用法：<divclass="eyou-edit"e-id="文件模板里唯一的数字ID"e-page='文件模板名'e-type="background"style="background-image:url({eyou:uibackgrounde......
  • Pinely Round 4 (Div. 1 + Div. 2)(A - F)
    PinelyRound4(Div.1+Div.2)(A-F)A-MaximizetheLastElement解题思路:只有奇数位置能选。偶数位置前后都有奇数个数字，无法删完。代码：#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#define......
  • Codeforces Round 961 (Div. 2) 复盘
    第一次打div2的总结div2难度明显比div3要难一些，其实也不是很难前面的签到题，但是给了我一种每道题都可以直接暴力但是就是会超时的感觉，不知道是不是提前就在告诉你要考虑greedythinking。T11995A-Diagonals这道题说实话就是存粹的模拟，除了最长的一个对角线同长度只有一列，其......
  • CF Div3 962补题 E-F
    CFDiv3962补题E-FE.Decode链接:Problem-E-Codeforces简要题意:给你一个长度为\(n\)的二进制字符串\(s\)。对于每一对整数\((l,r)\)\((1\leql\leqr\leqn)\)中，数出\((x,y)\)\((l\leqx\leqy\leqr)\)这样的整数对的个数。\((l\leqx\leqy\leq......
  • NSSRound#4 Team
    [NSSRound#4SWPU]1zweb考察：phar的反序列化1.打开环境，审计代码1.非预期解直接用file伪协议读取flag,或直接读取flagfile:///flag/flag2.正常解法用读取文件读取index.php,upload.php的源码 index.php:<?phpclassLoveNss{public$ljt;public$dky;......
  • Pinely Round 4 (Div. 1 + Div. 2) 复盘总结
    PinelyRound4(Div.1+Div.2)发挥到极致了，写出了两题A.MaximizetheLastElement对于每个满足他左边的数的个数和他后面的数的个数都是奇数的数，取最大值即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;//#defineintlonglong#defi......
  • Pinely Round 4 (Div. 1 + Div. 2)
    打的挺惨的，也算是活该吧。。总是沉浸在自己的舒适圈里，不肯跳出来，最近的总结和复盘也没认真做，回寝室明明应该做事情，但是就一直打游戏。。要是少打点游戏，也不至于最近这么长时间一场cf都没有vp过，手感这么差了。不过这次的题目也确实是我的漏洞。B因为初值的原因爆炸了，到最后都不知......
  • Pinely Round 4 (Div. 1 + Div. 2) 补题记录（A~F）
    打成乐子A容易证明下标为奇数的地方可以取到，下标为偶数的地方不可以取到。直接模拟时间复杂度为\(O(n)\)。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1000100;inta[N];signedmain(){intT;scanf("%lld",&T);......
  • Codeforces Round 961 (Div. 2)
    Preface菜的批爆，B2一直WA道心破碎了直接白兰去了，鉴定为纯纯的飞舞本来想着周末补题的然后又摆了一天，E1和E2都没时间补了，鉴定为纯纯的懒狗A.Diagonals签到，贪心枚举即可#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#in......
  • SMU Summer 2024 div2 3rd
    文章目录TheThirdWeek一、前言二、算法1.KMP算法2.线性DP<1>（最长上升子序列II）3.背包DP<1>（「木」迷雾森林）4.其它<1>（Ubiquity）三、总结TheThirdWeek战略上藐视敌人，战术上重视敌人————毛泽东主席一、前言周六打了场cf，只过了俩题而且比较慢，给我的id上......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99