首页 > 其他分享 >Educational Codeforces Round 156 (Rated for Div. 2)

Educational Codeforces Round 156 (Rated for Div. 2)

时间：2023-10-10 18:01:14浏览次数：38  
标签：Educational Rated 156 int typedef long fi include define

Preface

沉迷Galgame不打CF懒狗闪总出列！

这场在大物课上口胡了前四个题，回去写了也都很顺，然后E题本来做不来的，看了眼昨天校队群里的消息就会做了

F题什么东西直接弃

A. Sum of Three

当\(n\bmod 3\ne 0\)时，用\((1,2,z)\)来凑；否则当\(n\bmod 3=0\)时，用\((1,4,z)\)来凑

#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;
int t,n;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		if (scanf("%d",&n),n%3)
		{
			int left=n-1-2;
			if (left<=0||left==1||left==2) { puts("NO"); continue; }
			printf("YES\n1 2 %d\n",left);
		} else
		{
			int left=n-1-4;
			if (left<=0||left==1||left==4) { puts("NO"); continue; }
			printf("YES\n1 4 %d\n",left);
		}
	}
	return 0;
}

B. Fear of the Dark

简单讨论下会发现可能的走法只有四种，\(O\to A \to P;O\to B\to P;O\to A\to B\to P;O\to B\to A\to P\)，取最短的那个即可

#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 pi O=mp(0,0);
int t; pi P,A,B;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d%d%d%d",&P.fi,&P.se,&A.fi,&A.se,&B.fi,&B.se);
		auto dist=[&](const pi& A,const pi& B)
		{
			return sqrt((A.fi-B.fi)*(A.fi-B.fi)+(A.se-B.se)*(A.se-B.se));
		};
		double OA=dist(O,A),OB=dist(O,B),AP=dist(A,P),BP=dist(B,P),AB=dist(A,B);
		printf("%.10lf\n",min({max(OA,AP),max(OB,BP),max({OA,AB/2.0,BP}),max({OB,AB/2.0,AP})}));
	}
	return 0;
}

C. Decreasing String

首先考虑对于一个给定的字符串\(s\)，删去哪个字符能使得其字典序最小

简单手玩一下会发现其实就是第一个满足\(s_{i+1}<s_i\)的位置\(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 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=1e6+5;
int t,n,pos,vis[N],ers[N],stk[N],top,cnt; char s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; scanf("%s%lld",s+1,&pos); n=strlen(s+1);
		for (top=cnt=0,i=1;i<=n;++i)
		{
			while (top&&s[i]<s[stk[top]]) ers[++cnt]=stk[top--];
			stk[++top]=i;
		}
		while (top) ers[++cnt]=stk[top--];
		if (pos<=n) { putchar(s[pos]); continue; }
		int sum=n; for (i=1;i<=n;++i)
		if (pos<=sum+(n-i))
		{
			vis[ers[i]]=1; pos-=sum;
			for (j=1;j<=n;++j) if (!vis[j])
			if (!--pos) { putchar(s[j]); break; }
			break;
		} else sum+=(n-i),vis[ers[i]]=1;
		for (i=1;i<=n;++i) vis[i]=0;
	}
	return 0;
}

D. Monocarp and the Set

刚开始想了好多假算法，后面冷静思考发现原来是个丁真题

首先发现若\(s_1=?\)的话答案一定为\(0\)，否则对于这种排列计数我们有很经典的增量法

考虑已经处理了前\(i\)个数，我们可以把这些数之间的大小关系看作一个长为\(i\)的排列

此时考虑加入第\(i+1\)个数，不难发现如果此时的符号是\(<\)或\(>\)的话，新加入的数只有一种取法

否则这个数可以取中间任意一个位置的值，即有\(i+1-2=i-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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=300005,mod=998244353;
int n,m,x,ans=1,inv[N]; char s[N],opt[10];
inline void init(CI n)
{
	inv[1]=1; for (RI i=2;i<=n;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%s",&n,&m,s+1),init(n),i=2;i<n;++i) ans=1LL*ans*(s[i]=='?'?i-1:1)%mod;
	if (s[1]=='?') puts("0"); else printf("%d\n",ans);
	for (i=1;i<=m;++i)
	{
		if (scanf("%d%s",&x,opt),x!=1)
		{
			ans=1LL*ans*(s[x]=='?'?inv[x-1]:1)%mod;
			ans=1LL*ans*(opt[0]=='?'?x-1:1)%mod;
		}
		if (s[x]=opt[0],s[1]=='?') puts("0"); else printf("%d\n",ans);
	}
	return 0;
}

E. I Wanna be the Team Leader

这个题还是出的挺好的，虽然我是纯靠学长的点拨才会的

考虑如果我们把所有人按照\(a_i\)从大到小排序，考虑最后被拉去写程序的人一定是某段前缀

证明的话很简单，如果最后选的人不是前缀的话，我们总可以通过将区间向前平移来得到仍然满足要求的解

同时进一步挖掘一下性质会发现此时去做某个项目的一定是一段连续区间的人，因为此时做一个项目需要的人数仅由其中\(a_i\)最小的那个人决定，因此肯定连续地选是最优的

有了这几点后再结合题目中的\(m\le 20\)的限制，很容易想到用状压DP求解（实际上朴素的想法就是枚举长为\(m\)的排列，然后很容易发现这东西就跟哈密顿通路一样显然可以状压优化）

具体地，我们设\(f_{mask}\)表示以及处理了状态为\(mask\)的项目后，最少要用多少长的前缀

为了优化转移我们还需要求出对于每个项目，从某个位置开始向后最少要多少个数才能满足要求，这个可以通过双指针预处理出来

最后要输出方案就记录下每个状态的转移点即可，总复杂度\(O(nm+m\times 2^m)\)

#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=200005,M=20;
int n,m,a[N],b[M+5],id[N],nxt[M+5][N],f[(1<<M)+5],pre[(1<<M)+5]; vector <int> ans[M+5];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; if (scanf("%lld%lld",&n,&m),n<m) return puts("NO"),0;
	for (i=1;i<=n;++i) scanf("%lld",&a[i]),id[i]=i;
	for (i=0;i<m;++i) scanf("%lld",&b[i]);
	auto cmp=[&](CI x,CI y)
	{
		return a[x]>a[y];
	};
	for (sort(id+1,id+n+1,cmp),i=0;i<m;++i)
	{
		for (j=k=1;j<=n;++j)
		{
			while (k<=n&&b[i]>a[id[k]]*(k-j+1)) ++k;
			nxt[i][j]=k;
		}
	}
	for (i=1;i<(1<<m);++i) f[i]=n+1;
	for (i=0;i<(1<<m);++i) if (f[i]<n)
	{
		for (j=0;j<m;++j) if (!((i>>j)&1))
		if (nxt[j][f[i]+1]<f[i|(1<<j)])
		f[i|(1<<j)]=nxt[j][f[i]+1],pre[i|(1<<j)]=j;
	}
	if (f[(1<<m)-1]>n) return puts("NO"),0;
	for (int cur=(1<<m)-1;cur;)
	{
		int lst=cur^(1<<pre[cur]);
		for (i=f[lst]+1;i<=f[cur];++i) ans[pre[cur]].push_back(id[i]);
		cur=lst;
	}
	for (puts("YES"),i=0;i<m;++i)
	{
		printf("%d ",ans[i].size());
		for (auto x:ans[i]) printf("%d ",x); putchar('\n');
	}
	return 0;
}

Postscript

唉最近手头事情一大堆，桂林站和期中考试又一起临近了，感觉好忙碌的说

标签：Educational,Rated,156,int,typedef,long,fi,include,define
From： https://www.cnblogs.com/cjjsb/p/17755362.html

相关文章

  • April Fools Day Contest 2021 A. Is it rated - 2
    询问若干个问题，每个问题用一段字符串表示，存在空格。每个问题一行，对于每个回答，只需要输出\(NO\)。view1#include<bits/stdc++.h>chars[1000005];voidsolve(){ while(fgets(s,1000005,stdin)!=NULL){ std::cout<<"NO"<<std::endl;//fgets从流中读取，读取失......
  • Educational Codeforces Round 156 (Rated for Div. 2)
    EducationalCodeforcesRound156(RatedforDiv.2)A.SumofThree解题思路:如果\(n\leq6或n=9\),无解。若\(n\%3==0，t=\lfloor\frac{3}{n}\rfloor\):若\(t=0\)构造\(1,4,n-5\)否则，构造\(t-3,t,t+3\)若\(n\%3==1:构造1,2，n-3\)若\(n......
  • Educational Codeforces Round 152 (Div. 2) D. Array Painting（双指针）
    EducationalCodeforcesRound152(Div.2)D.ArrayPainting//思路：双指针找连续正数段//若段中出现2，则更新两头的0的情况，若为涂色则改为true//若无2，则优先更新左侧0，若左0已经为true，则更新右侧0//数组开头结尾特判#defineintlonglong#defineldlongdoubleusingnam......
  • 练习记录-cf-Educational Codeforces Round 156 (Rated for Div. 2)(A-C)
    好久没打了还是就出了三道不过还好没掉分A.SumofThree就是问能不能把一个数拆成三个不同的且都不能被三整除的数我的思路就是拆成1+2+一个大于等于4的数如果拆了后另一个数是%3==0那么我拆成1+4它肯定就不被整除然后判下相同#include<bits/stdc++.h>#defineclose......
  • This generated password is for development use only. Your security configuration
    问题描述在我加上spring-boot-starter-security的依赖之后，启动项目报出来这样的错误：问题解决在启动类的注解上，加上这么一段代码就ok啦！启动成功：......
  • SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
    Preface纯纯的智商场，只能说老外的出题风格和国内的比赛差异还是挺大的这场开局被签到题H反杀后灰溜溜地下机，结果后面的题出的都还挺顺的等到最后徐神把J过掉后我们都以为D是个大分类讨论（实际上机房里的学长们都是用分类讨论过的），就不想写了挂机到结束后面看题解发现确实是分类......
  • Educational Codeforces Round 155 (Rated for Div. 2)
    \(A.Rigged!\)直接取第一个人能举起的最大重量看他是否是冠军即可。voidsolve(){intn=read();intfx=read(),ft=read();intans=fx;for(inti=1;i<n;i++){intx=read(),t=read();if(x>=fx&&t>=ft)ans=-1;}cout<<ans<......
  • Educational Codeforces Round 112 (Rated for Div. 2) A. PizzaForces
    有三种披萨：\(6\)、\(8\)、\(10\)块披萨。制作时间分别需要：\(15\)、\(20\)、\(25\)分钟。现在有\(n\)个人，每人需要一块披萨。询问使所有人能获得披萨的最快时间。观察：发现三种披萨的性价比都一样。（否则按最优性价比贪心）需要让得到的披萨数量\(m\geqn\)。不妨让\(n\)对......
  • Educational Codeforces Round 155 (Rated for Div
    B.ChipsontheBoard题解：贪心显然我们可以把题意转化为：对于任意一个\((i,j)\)，我们可以花费\(a_{i,j}\)的代价占据第\(i\)行和第\(j\)列，求占据所有格子的最小代价考虑两种情况：在每一行选一个格子在每一列选一个格子贪心选即可intn,a[N],b[N];voidsolve......
  • Educational Codeforces Round 122 (Rated for Div. 2)
    A.Div.7#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,a,b,c;cin>>n;c=n%10,n/=10;b=n%10,n/=10;a=n%10,n/=10;intres,val=100;for(inti=0;i<=9......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99