首页 > 其他分享 >think-cell Round 1

think-cell Round 1

时间：2024-02-24 14:00:13浏览次数：24  
标签：typedef int CI long Round cell include think define

Preface

这场一周前打的了，结果因为每天都有训练一直拖到今天才有时间补

前期虽然有点犯病但一直到D2出题都还算稳，然后看到E题经典数数题就走不动路了直接投降

后面请徐神来救场才堪堪会做，可惜最后推出优化的式子后比赛已经结束10min了

不够好在是手速够快没有掉分，感觉现在就是前面题出的巨快但总是后面题一个也做不来罚坐到结束

A. Maximise The Score

签到，排序后相邻的两个数一对地取即可

#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=105;
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),n<<=1,i=1;i<=n;++i) scanf("%d",&a[i]);
		int sum=0; for (sort(a+1,a+n+1),i=1;i<=n;i+=2) sum+=a[i];
		printf("%d\n",sum);
	}
	return 0;
}

B. Permutation Printing

不难发现所有\(>\frac{n}{2}\)的数都不存在倍数，因此将它们和\(\le \frac{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_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=100005;
int t,n;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		vector <int> ans; scanf("%d",&n);
		for (RI i=1,j=n;i<=j;)
		{
			if (i<=j) ans.push_back(i++);
			if (i<=j) ans.push_back(j--);
		}
		for (auto x:ans) printf("%d ",x); putchar('\n');
	}
	return 0;
}

C. Lexicographically Largest

感觉很典的一个题

首先如果所有\(a_i+i\)都不相同就很简单，从大到小取即可，否则考虑有若干个\(a_i+i\)的和都是\(x\)

我们总是先取最靠左的那个数，这样就可以一路得到\(x,x-1,x-2,\cdots\)

那么做法就很简单了，把所有\(a_i+i\)从大到小排序，对于当前的数\(x\)，找到\(\le x\)且还未被使用的数\(y\)，将\(y\)输出即可

然后因为之前做过和这个基本一样的东西，直接离散化后用并查集维护一下就好了

#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=600005;
int t,n,a[N],fa[N],idx,rst[N]; map <int,int> ID;
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
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]),a[i]+=i;
		idx=0; ID.clear(); vector <int> ans;
		for (sort(a+1,a+n+1,greater <int>()),i=1;i<=n;++i)
		{
			auto getID=[&](CI x)
			{
				if (ID.count(x)) return ID[x];
				ID[x]=++idx; fa[idx]=idx; rst[idx]=x; return ID[x];
			};
			int x=getID(a[i]),cur=rst[getfa(x)]; ans.push_back(cur); fa[getfa(x)]=getfa(getID(cur-1));
		}
		for (auto x:ans) printf("%d ",x); putchar('\n');
	}
	return 0;
}

D1. Sum over all Substrings (Easy Version)

经典Guess Force，直接无脑猜结论就行

D1因为数据范围很小，可以暴力枚举每个子串，现在的问题就是对于某个确定的01串求它的贡献

直觉告诉我们如果包含该点的大的区间\([L,R]\)内的众数为目标数字，那么被包含的较小的区间\([l,r]\in[L,R]\)中也必然存在合法区间，因此我们只需要考虑长度为\(2\)的区间即可

那么问题转化为，对于原01串的每个1，需要保证在与其距离\(\le 1\)的位置内至少存在一个1，这个显然可以直接从前往后贪心

因此这题就有了\(O(n^3)\)的做法，当然很容易优化到\(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_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=105;
int t,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; int ans=0; scanf("%d%s",&n,s+1);
		auto calc=[&](CI l,CI r)
		{
			int ret=0; static int tmp[N]; for (RI i=l;i<=r;++i) tmp[i]=-1;
			for (RI i=l;i<=r;++i)
			{
				if (tmp[i]!=-1) continue;
				if (s[i]=='1')
				{
					if (i-1>=l&&tmp[i-1]==1) { tmp[i]=0; continue; }
					tmp[i]=0; tmp[i+1]=1; ++ret;
				} else tmp[i]=0;
			}
			return ret;
		};
		for (i=1;i<=n;++i) for (j=i;j<=n;++j) ans+=calc(i,j);
		printf("%d\n",ans);
	}
	return 0;
}

D2. Sum over all Substrings (Hard Version)

考虑上面那个东西的本质，其实就是要拿出最少的长度为\(3\)的区间，使得用这些区间能覆盖原01串中的所有1

不妨考虑DP，设\(f_i\)表示所有以\(i\)为左端点的区间的答案之和，转移的时候考虑：

  • \(s_i=0\)，我们找到距离\(i\)最近的\(j(i<j)\)，满足\(s_j=1\)，显然第一个区间以\(j\)为左端点最优，因此\(f_i=f_j\)
  • \(s_i=1\)，那么显然第一个区间的左端点必然要放在\(i\)处，因此有\(f_i=f_{i+3}+(n-i+1)\)（因为以\(i\)为左端点的串共有\(n-i+1\)个）

直接从后往前递推处理即可，复杂度\(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 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,f[N]; char s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; int ans=0; scanf("%lld%s",&n,s+1);
		int nxt=n+1; for (f[n+1]=f[n+2]=f[n+3]=0,i=n;i>=1;--i)
		if (s[i]=='0') f[i]=f[nxt]; else f[i]=(n-i+1)+f[i+3],nxt=i;
		for (i=1;i<=n;++i) ans+=f[i]; printf("%lld\n",ans);
	}
	return 0;
}

E. 2..3...4.... Wonderful! Wonderful!

唉又被徐神救了，不然我真做不来一点Counting Problem

首先数据范围允许我们枚举\(k\)，然后大力枚举删除了\(d\)次，这里的复杂度是调和级数的

考虑用容斥，用选\(2dk\)个数删除的方案数\(C_n^{2dk}\)减去不合法的删除方案数，考虑后者有什么性质

根据徐神大力猜测的结论，一个删除序列合法当且仅当存在至少一个没被删除的位置，使得其左右都有至少\(k\)个数被删除

证明的话考虑如果某个局面不满足上面的限制，则显然无法倒推完成最后一次删除操作；否则因为可以任意地把\(2k\)个数还原回去，因此条件一定变宽松了

那么考虑怎么计算当前局面的方案数，不难发现此时删除位置的形态一定形如中间一段连续的删除位置，然后两边分散一些删除位置随便放

具体地，不妨设\(len=2dk-2(k-1)\)，则我们需要先选一段长度为\(len\)的区间全部钦定删除，然后在该区间的左右两侧各放上\(k-1\)个删除位置

因此不难想到枚举中间那段的起始位置然后暴力将两边的方案数乘起来，即下面代码中注释的部分，但这样显然会TLE飞因此还需要考虑优化

不妨从组合意义的角度出发，这个问题相当于在\(n-len\)个球中先放一个隔板，再左右各取\(k-1\)个球

不妨把隔板也看作一个球，这样相当于在\(n-len+1\)各球中取出\(2k-2+1=2k-1\)个球，因此最后方案数就是\(C_{n-len+1}^{2k-1}\)，就可以\(O(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=1e6+5,mod=998244353;
int t,n,fact[N],ifac[N];
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline void dec(int& x,CI y)
{
	if ((x-=y)<0) x+=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
	if (n<m||n<0||m<0) return 0;
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(1e6);t;--t)
	{
		RI i,d,k; for (scanf("%d",&n),k=1;k<=(n-1)/2;++k)
		{
			int ans=1; for (d=1;2*d*k<=n;++d)
			{
				inc(ans,C(n,2*d*k)); int len=2*d*k-(2*k-2);
				//for (i=k;n-(i+len-1)>=k-1;++i)
				//dec(ans,1LL*C(i-1,k-1)*C(n-(i+len-1),k-1)%mod);
				dec(ans,C(n-len+1,2*k-1));
			}	
			printf("%d ",ans);
		}
		putchar('\n');
	}
	return 0;
}

F. Maximize the Difference

这题其实本质不难，但就是要破除一定要用数据结构来优化的桎梏

首先\(\max [(x|z)-(y|z)]\)是一个很经典的问题，设其最大值为\(w\)，则一定满足\(w\)是\(x\)的子集，同时\(w\)也是\(y\)的补集的子集

证明的话也很简单，\(w\)是\(x\)的子集这点是由于若\(x\)某一位是\(0\)则\(w\)这一位上就不可能是\(1\)；同理若\(y\)某位上是\(1\)则\(w\)这一位上就必为\(0\)，因此\(w\)是\(y\)的补集的子集

因此不难想到一个暴力做法，开两个数组分别记录当前状态是否作为某个数的子集/补集的子集出现过，每加入一个数字的时候暴力枚举子集/补集的子集即可，这样复杂度是\(O(3^{22})\)的，无法通过

考虑我们只要算出最大值，因此如果已经确定一个数是合法的（其同时作为某个数的子集以及某个数补集的子集出现过），那么它的所有子集就没有必要再扩展了

因此可以用类似BFS的方法来按位扩展子集，一旦遇到以及扩展过的状态就不再重复扩展，最终复杂度就变成\(O(2^{22}\times 22)\)了

#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=(1<<22)+5;
int t,n,q,x,ans,vis[N][2];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d",&n,&q); ans=0;
		int m=0; while ((1<<m)<n) ++m;
		for (i=0;i<(1<<m);++i) for (j=0;j<2;++j) vis[i][j]=0;
		while (q--)
		{
			scanf("%d",&x); x=(x+ans)%n;
			for (i=0;i<2;++i)
			{
				int now=(i==0?x:x^((1<<m)-1));
				if (vis[now][i]) continue; vis[now][i]=1;
				queue <int> q; q.push(now); 
				while (!q.empty())
				{
					now=q.front(); q.pop();
					if (vis[now][i^1]) ans=max(ans,now);
					for (j=0;j<m;++j) if ((now>>j)&1)
					if (!vis[now^(1<<j)][i])
					vis[now^(1<<j)][i]=1,q.push(now^(1<<j));
				}
			}
			printf("%d ",ans);
		}
		putchar('\n');
	}
	return 0;
}

Postscript

唉马上就要开学力，事情多起来后训练的时间就要减少了

而且这个学期还有给新生暑假前集训出题、校赛、省赛、蓝桥杯、天梯赛等一堆事情，同时绩点和科研啥的也不能落下

借最近玩的《拔作岛》的经典台词与诸君共勉吧：

不畏人间苦，不惧世上难，万般皆磨炼，有志终逞愿。

标签：typedef,int,CI,long,Round,cell,include,think,define
From： https://www.cnblogs.com/cjjsb/p/18031005

相关文章

  • Educational Codeforces Round 162 [Rated for Div. 2]
    第二次，三道题，剩下的回学校再补，总结：还是需要多练习A：让数列里所有的1都挨在一起，可以看出，相邻1之间有多少个0就需要操作几次，特判：当只有一个1或者原本全是1就输出0；voidsolve(){cin>>n;inttop1=0,top2=0,cnt=0;memset(a,0,sizeof(a));memset(b,0,siz......
  • background-position详解
    原文链接：https://blog.csdn.net/weixin_30687587/article/details/98437498一.background-position:lefttop;背景图片的左上角和容器(container)的左上角对齐，超出的部分隐藏。等同于background-position:0,0;也等同于background-position:0%,0%;二.background-position:r......
  • 2024.2.22 LGJ Round
    A你需要求\(n\timesm\)格子里随机撒\(k\)个点，期望扫多少次使得相邻的格子没有同时有点。\(n\timesm\le80,k\le20\)。直接状压求出方案数即可。B你需要维护一个数组，支持区间求和或执行覆盖操作fori:=ltordoa[i]:=a[i-k]或区间回溯成一开始的数。可持久化平衡......
  • Codeforces Round 923 (Div. 3)
    A.MakeitWhite#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingi128=__int128;usingldb=longdouble;#defineinti64usingvi=vector<int>;usingpii=pair<int,int>;usingvii......
  • 2024.2.21 LGJ Round
    A你在平面上有\(n\)个点，你每次可以从一个点跳到其右下或左上任意的点，|对每个点\(i\)，求所有点到\(i\)至少跳多少次的和。点的坐标值域为\(M=2500\)。\(n\le2.5e5\).我们先考虑某个点，到所有点跳多少次。首先右下，左上都是跳一次即可。我们先考虑右上的点怎么办。我们一定......
  • Codeforces Round 928 (Div. 4)
    CodeforcesRound928(Div.4)比赛链接A.VladandtheBestofFive思路就是统计字符A和字符B的个数，将个数多的那个输出出来Code#include<bits/stdc++.h>usingnamespacestd;#defineall(x)x.begin()+1,x.end()#defineintlonglongvoidsolve(){strings;......
  • P2899 [USACO08JAN] Cell Phone Network G
    原题链接题解一开始我想的是每个节点要么建，要么不建，可是这样一来不好转移，因为有如下情况（黑色代表建站）于是我们换一个角度思考，我们发现一个点要能通网，有三种情况：1.自己建站2.儿子建站3.父亲建站Code#definelllonglong#include<bits/stdc++.h>usingnamespacestd;ve......
  • Codeforces Round 928（Div. 4）
    Dashboard-CodeforcesRound928(Div.4)-Codeforces第一次参加CF，最后一道题连题都没读，下次不会就跳，菜是原罪A：找字符串中A,B数量，遍历一下最后比较即可B：判断是三角形还是正方形，题目表示除了正方形就是三角形，所以直接判断是不是正方形，用ans数组记录每一行1的个数，然后从大......
  • Codeforces Round 900 (Div. 3)
    题目A.只要k出现过就是YES#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn,k;cin>>n>>k;map<int,int>mp;for(inti=0,x;i<n;i++){cin......
  • Codeforces Round 928 (Div. 4) (小白的复盘)
    A.VladandtheBestofFive思路:给你一个长度字符串只包含A和B输出最多的字符解法:按题意来Code:#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){strings;cin>>s;intcnt=0;fo......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99