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

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

时间：2023-09-02 19:36:03浏览次数：44  
标签：typedef const int Pinely long Div include Round define

Preface

唉懒狗了这把比赛的时候突然不想打了跑去看AIR了，所以就没打了，后面补题的时候发现前面题挺合我口味的如果打了大概率能上橙

不过这种第二天早上有早八的时间还是很难打的，苦路西苦路西

A. Channel

统计当存在某个时刻在线人数为\(n\)时就是YES

否则把所有的+加起来看看是否大于等于\(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_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,q; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d%d%s",&n,&a,&q,s+1);
		bool flag=a==n; int b=a;
		for (i=1;i<=q;++i)
		{
			if (s[i]=='+') ++a,++b; else --a; flag|=a==n;
		}
		if (flag) { puts("YES"); continue; }
		if (b>=n) puts("MAYBE"); else puts("NO");
	}
	return 0;
}

B. Split Sort

考虑按序进行\(2\sim n\)这些操作一定能将整个序列排序，考虑什么时候能节省下一些操作

手玩下发现对于每对\(i,i+1\)，若\(pos(i+1)>pos(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_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=100005;
int t,n,a[N],pos[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]),pos[a[i]]=i;
		int ans=n-1; for (i=1;i<n;++i) ans-=(pos[i+1]>pos[i]);
		printf("%d\n",ans);
	}
	return 0;
}

C. MEX Repetition

手玩找下规律会发现每次操作就是在开头补上缺少的那个数，然后删除序列末尾的元素

发现操作\(n+1\)次后序列会复原，因此把\(k\)向\(n+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_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=100005;
int t,n,k,x,w,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=0;i<=n;++i) vis[i]=0;
		deque <int> q; for (i=1;i<=n;++i) scanf("%d",&x),vis[x]=1,q.push_back(x);
		for (i=0;i<=n;++i) if (!vis[i]) { w=i; break; }
		for (k%=n+1,i=1;i<=k;++i) q.push_front(w),w=q.back(),q.pop_back();
		for (auto x:q) printf("%d ",x); putchar('\n');
	}
	return 0;
}

D. Two-Colored Dominoes

好简单的D题啊

考虑横着的这种牌，不难发现它对行没有影响，只要考虑它对列的影响即可

统计出每列牌的数量，如果是奇数就显然无解，否则我们按列的顺序随便染即可，不难发现这样总有解

处理完后考虑竖着的牌即可，做法是相同的

#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_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=505;
int t,n,m,col[N][N],wr[N],wc[N]; char s[N][N]; vector <int> R[N],C[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%s",s[i]+1);
		for (i=1;i<=n;++i) R[i].clear(),wr[i]=0;
		for (i=1;i<=m;++i) C[i].clear(),wc[i]=0;
		for (i=1;i<=n;++i) for (j=1;j<=m;++j)
		{
			col[i][j]=-1;
			if (s[i][j]=='L') C[j].push_back(i),C[j+1].push_back(i);
			if (s[i][j]=='U') R[i].push_back(j),R[i+1].push_back(j);
		}
		bool flag=1; for (i=1;i<=n&&flag;++i)
		{
			if (R[i].size()&1) flag=0;
			for (auto j:R[i])
			{
				if (~col[i][j]) continue;
				int c=wr[i]*2<R[i].size(); col[i][j]=c; wr[i]+=c;
				if (s[i][j]=='U') col[i+1][j]=c^1,wr[i+1]+=c^1;
			}
		}
		for (j=1;j<=m&&flag;++j)
		{
			if (C[j].size()&1) flag=0;
			for (auto i:C[j])
			{
				if (~col[i][j]) continue;
				int c=wc[j]*2<C[j].size(); col[i][j]=c; wc[j]+=c;
				if (s[i][j]=='L') col[i][j+1]=c^1,wc[j+1]+=c^1;
			}
		}
		if (!flag) { puts("-1"); continue; }
		for (i=1;i<=n;++i,putchar('\n')) for (j=1;j<=m;++j)
		if (s[i][j]=='.') putchar('.'); else putchar(col[i][j]?'W':'B');
	}
	return 0;
}

E. Speedrun

首先考虑答案的计算形式，我们需要确定起始时刻，然后跑一个拓扑排序就能得到结束时刻了

因此一个很自然的想法就是给DAG的零入度点排序，然后按顺序枚举某个作为起始时刻，不难发现其实就是不断地把前一个起始时刻加上\(k\)的过程

考虑修改某个点的值后会影响它后面的点的值，乍一看复杂度很爆炸，但仔细一想最后至多每个数都比原来大\(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_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=200005;
int t,n,m,k,h[N],x,y,deg[N],f[N],mx[N],ret; vector <int> v[N];
inline int calc(CI x,CI y)
{
	int d=x/k,r=x%k; return (d+(y<r))*k+y;
}
inline void reset(CI now)
{
	if (calc(mx[now],h[now])<=f[now]) return;
	ret=max(ret,f[now]=calc(mx[now],h[now]));
	for (auto to:v[now]) mx[to]=max(mx[to],f[now]),reset(to);
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld%lld%lld",&n,&m,&k),i=1;i<=n;++i)
		mx[i]=deg[i]=0,v[i].clear(),scanf("%d",&h[i]);
		for (i=1;i<=m;++i) scanf("%lld%lld",&x,&y),v[x].push_back(y),++deg[y];
		queue <int> q; vector <pi> st;
		for (i=1;i<=n;++i) if (!deg[i]) mx[i]=h[i],q.push(i),st.push_back(pi(h[i],i));
		sort(st.begin(),st.end()); ret=0; while (!q.empty())
		{
			int now=q.front(); q.pop(); ret=max(ret,f[now]=calc(mx[now],h[now]));
			for (auto to:v[now])
			{
				mx[to]=max(mx[to],f[now]); if (!--deg[to]) q.push(to);
			}
		}
		int ans=ret-st[0].fi; for (i=0;i<st.size()-1;++i)
		mx[st[i].se]+=k,reset(st[i].se),ans=min(ans,ret-st[i+1].fi);
		printf("%lld\n",ans);
	}
	return 0;
}

F. Divide, XOR, and Conquer

妙妙题

考虑对于某个能得到区间\([l,r]\)，记\(s=\bigoplus_{i=l}^r a_i\)，考虑若\(s=0\)则对于其任意一个前缀或者后缀区间都可以得到

否则若\(s\ne 0\)，则对于每个前缀\([l,k]\)，记\(x=\bigoplus_{i=l}^k a_i\)，显然当且仅当\(s\)的最高位和\(x\)的最高位相同时，区间\([l,k]\)可以被表示

直接利用这个性质做有很多种做法，但都是\(O(n^2\log a_i)\)的复杂度，由于\(n=10000\)无法通过

考虑怎么把状态的转移做到\(O(1)\)，可以利用状压，用\(sl_i,sr_i\)表示以\(i\)为左端点/右端点时，区间最高位的集合（状压）

那么考虑若当前区间\([l',r']\)，其\(s'=\bigoplus_{i=l'}^{r'} a_i\)，则如果\(s'\and sl_{l'}>0\)或者\(s'\and sr_{r'}>0\)这个区间就可以得到，这样就可以\(O(1)\)转移了

注意下当\(s=0\)时需要给\(sl_l,sr_r\)赋上全\(1\)的值，总复杂度\(O(n^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_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=10005,S=(1LL<<61)-1;
int t,n,a[N],pfx[N],sl[N],sr[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; for (scanf("%lld",&n),i=1;i<=n;++i)
		scanf("%lld",&a[i]),pfx[i]=pfx[i-1]^a[i],sl[i]=sr[i]=0;
		auto high=[&](CI x)
		{
			if (!x) return S; return 1LL<<(63-__builtin_clzll(x));
		};
		for (i=1;i<=n;++i) for (j=n;j>=i;--j)
		{
			int flag=(i==1&&j==n),s=pfx[j]^pfx[i-1];
			flag|=(sl[i]&s)>0||(sr[j]&s)>0;
			if (sl[i]==S||sr[j]==S) flag=1;
			if (flag) sl[i]|=high(s),sr[j]|=high(s);
			if (i==j) putchar(flag?'1':'0');
		}
		putchar('\n');
	}
	return 0;
}

Postscript

最近训练态度很不积极啊感觉，马上要第一次出战区域赛了得赶紧加训加训

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

相关文章

  • Educational Codeforces Round 23 A - F
    EducationalCodeforcesRound23目录EducationalCodeforcesRound23A-TreasureHuntB-MakesAndTheProductC-ReallyBigNumbersD-ImbalancedArrayE-ChoosingTheCommanderF-MEXQueriesA-TreasureHunt往四个方向走，每次操作会变动横坐标和纵坐标，横纵坐标......
  • Educational Codeforces Round 154 (Rated for Div. 2)（A—C）
    A.PrimeDeletion思路：从1到9，每个数后面都可以加一个数构成一个含有两个数的质数，只需要从s[1]~s[9]中找到一个数与s[0]构成质数即可代码实现/*******************************|Author:CHC|Problem:A.PrimeDeletion|Contest:Codeforces-EducationalCodeforcesR......
  • 【题解】Educational Codeforces Round 153（CF1860）
    每次打都想感叹一句，Educational名不虚传。A.NotaSubstring题目描述：有\(t\)组数据，对于每一组数据，你需要判断能否构造一个只由左右括号组成且长度为已经给定字符串的\(2\)倍且已经给定的字符串不是子串的合法字符串。注：合法的字符串是左右括号能完全匹配的字符串。如果能，......
  • Educational Codeforces Round 113
    稳定发挥4题A题文件输出没去掉WA了一发B题特殊情况没判到，WA了好几发，中间还交到D题去了C题简单判断一下无解，然后组合数求一下就行D题其实也挺简单的，考虑严格夹在两条竖线之间的点（不包括边界），如果它们不是在同一水平线上，则必然大于Manhattan距离，而且两个点对之间要么是x方向走多......
  • Educational Codeforces Round 154 (Rated for Div. 2)
    感觉edu的题目都比较有新意；A.PrimeDeletion题意：给定长度为9的数，且1-9每个数字出现一次，求按照原定顺序选几个数组成的质数（起码选择两个）；下意识写了一个dfs，过了；1#include<bits/stdc++.h>2usingnamespacestd;3intread(){4charch=getchar();intx=0,f=1;5......
  • Educational Codeforces Round 123
    A.DoorsandKeys#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){strings;cin>>s;map<char,int>pos;for(inti=0;i<6;i++)pos[s[i]]=i;if(pos['r&......
  • Educational Codeforces Round 15 A - E
    EducationalCodeforcesRound15目录EducationalCodeforcesRound15A-MaximumIncreaseB-PowersofTwoC-CellularNetworkD-RoadtoPostOfficeE.AnalysisofPathesinFunctionalGraphA-MaximumIncrease一段上升子数组\([l,r]\)最大化\(r-l+1\)，我们......
  • Educational Codeforces Round 5 A-E
    EducationalCodeforcesRound5垫底咯，中间老师找我去聊了下新学期的机房借用和训练，但出去前就只有我没出E目录EducationalCodeforcesRound5AComparingTwoLongIntegersBDinnerwithEmmaCTheLabyrinthDLongestk-GoodSegmentE-SumofRemaindersAComparingTwo......
  • Pinely Round 2 (Div. 1 + Div. 2)
    PinelyRound2(Div.1+Div.2)比赛链接因为第二天早上满课，所以这个比赛没有打，但是补题还是要有的。A题ChannelA题链接你是一个博主，有n个订阅者，当你发表了一篇博客时，会被订阅者看到，一开始有a名订阅者在线，随后给你q个指令，“+”代表有一个订阅者上线，“-”代表有一个订阅者下......
  • Educational Codeforces Round 148 (Rated for Div. 2)E. Combinatorics Problem（组合
    题目链接：https://codeforces.com/contest/1832/problem/E 题意：  当然这是化简后的题意，原题面和这个差距还是有点大的； 分析： 因为组合数有公式：  所以：   嗯，然后就没有了； 时间复杂度：O（n*k）； 代码： #include<bits/stdc++.h>#defineintlonglong......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99