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

Codeforces Round 961 (Div. 2)

时间：2024-07-28 20:40:12浏览次数：7  
标签：typedef 961 int Codeforces long pair Div include define

Preface

菜的批爆，B2 一直 WA 道心破碎了直接白兰去了，鉴定为纯纯的飞舞

本来想着周末补题的然后又摆了一天，E1 和 E2 都没时间补了，鉴定为纯纯的懒狗

A. Diagonals

签到，贪心枚举即可

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

B1. Bouquet (Easy Version)

当时 B2 先写了发三分发现 WA 了，就赶紧滚回来把 B1 写了，这题就直接双指针扫一遍就能过

#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m,a[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%lld",&n,&m),i=1;i<=n;++i)
		scanf("%lld",&a[i]); sort(a+1,a+n+1);
		int ans=0,sum=a[1]; for (i=j=1;i<=n;++i)
		{
			while (j<=n&&a[j]-a[i]<=1&&sum<=m) sum+=a[++j];
			sum-=a[j--]; if (sum<=m) ans=max(ans,sum); sum-=a[i];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

B2. Bouquet (Hard Version)

Div.2 B 题战俘闪总出列

这题有个很简单的讨论方式，即对于一组 \((a,a+1)\)，我们假设先全部买 \(a\)，然后把剩下的钱拿来买 \(a+1\)

这样如果还有剩余的钱，可以考虑将一些刚开始买的 \(a\) 替换成 \(a+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 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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m,a[N],b[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld%lld",&n,&m),i=1;i<=n;++i)
		scanf("%lld",&a[i]); map <int,int> rst;
		for (i=1;i<=n;++i) scanf("%lld",&b[i]),rst[a[i]]=b[i];
		int ans=0;
		for (auto [a,x]:rst)
		{
			int c1=min(x,m/a),sum=c1*a,rem=m-c1*a;
			if (!rst.count(a+1)) { ans=max(ans,sum); continue; }
			int c2=min(rst[a+1],rem/(a+1));
			sum+=c2*(a+1); rem-=c2*(a+1);
			sum+=min(c1,min(rem,rst[a+1]-c2));
			ans=max(ans,sum);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C. Squaring

神秘题，感觉精度要爆炸但交上去就是过了，很神秘

首先这题的策略很简单，即从前往后贪心，每个位置操作到比前一个位置大了就停手一定最优

现在的难点就在于怎么比较两个数的大小，假设前一个数 \(a_{i-1}\) 操作了 \(x\) 次，考虑快速计算当前数 \(a_{i}\) 操作的次数 \(y\)

原来要比较 \(a_{i-1}^{2^x}\) 和 \(a_i^{2^y}\) 的大小；两边取 \(\ln\) 后变为比较 \(2^x\times \ln a_{i-1}\) 和 \(2^y\times \ln a_{i}\) 的大小

两边再做商得 \(2^{x-y}\times \frac{\ln a_{i-1}}{\ln a_i}\)，因此可以直接再取 \(\log_2\) 快速解出 \(y\) 的值，注意要对 \(0\) 取 \(\max\)

#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m,a[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]);
		int ans=0,lst=0; bool flag=1;
		for (i=2;i<=n;++i)
		{
			if (a[i]==1&&a[i-1]!=1) { flag=0; break; }
			lst=max(0LL,(int)ceil(log2(1.0L*log(a[i-1])/log(a[i]))+lst));
			ans+=lst;
		}
		if (!flag) { puts("-1"); continue; }
		printf("%lld\n",ans);
	}
	return 0;
}

D. Cases

考虑原题的限制相当于对于任意连续的 \(k\) 个字符，其中必须至少有一个是终止字符

反过来思考下，这就等价于对于连续的 \(k\) 个字符组成的状压状态 \(T\) 不能为所有不是终止字符的字符构造的集合 \(S\) 的子集

因此把所有连续的 \(k\) 个字符对应的状态标记为不合法（注意最后一个字符要特判），然后把它们的超集也标记成不合法即可

最后用枚举子集或者 sosdp 即可 \(O(3^{c})\) 或 \(O(2^{c}\times c)\) 通过此题

#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=(1<<18)+5;
int t,n,c,k,f[N],bkt[20]; char s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d%d%s",&n,&c,&k,s+1);
		for (i=0;i<(1<<c);++i) f[i]=0; f[1<<(s[n]-'A')]=1;
		int mask=0; for (i=0;i<c;++i) bkt[i]=0;
		auto add=[&](CI x)
		{
			if (++bkt[x]==1) mask^=(1<<x);
		};
		auto del=[&](CI x)
		{
			if (--bkt[x]==0) mask^=(1<<x);
		};
		for (i=1;i<=k;++i) add(s[i]-'A'); f[mask]=1;
		for (i=k+1;i<=n;++i) del(s[i-k]-'A'),add(s[i]-'A'),f[mask]=1;
		for (i=0;i<c;++i) for (j=0;j<(1<<c);++j)
		if ((j>>i)&1) f[j]|=f[j^(1<<i)];
		int ans=c; for (i=0;i<(1<<c);++i)
		if (!f[i]) ans=min(ans,__builtin_popcount(((1<<c)-1)^i));
		printf("%d\n",ans);
	}
	return 0;
}

Postscript

感觉再这么菜下去要被新一届 Div2 薄纱了

标签：typedef,961,int,Codeforces,long,pair,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/18328832

相关文章

  • SMU Summer 2024 div2 3rd
    文章目录TheThirdWeek一、前言二、算法1.KMP算法2.线性DP<1>（最长上升子序列II）3.背包DP<1>（「木」迷雾森林）4.其它<1>（Ubiquity）三、总结TheThirdWeek战略上藐视敌人，战术上重视敌人————毛泽东主席一、前言周六打了场cf，只过了俩题而且比较慢，给我的id上......
  • Solution - Atcoder ARC114F Permutation Division
    令\(a\)为题目中的\(P\)。首先考虑后手的重排策略是什么。因为\(a\)是个排列，元素互不相同，那么肯定就是按照每一段的第一个数的大小，越大的放在越前面。那么当\(a_1\lek\)的时候，显然先手会把以\(1\simk\)开头来划分段。因为否则存在一个开头\(>k\)的段，后手把其放......
  • CodeForces 1883G1 Dances (Easy version)
    题目链接：CodeForces1883G1【Dances(Easyversion)】思路    为了使得数组a，b中的每个对应元素满足a[i]<b[i]，所以将数组a，b按从小到大依次排列，优先删除数组a中较大的元素和数组b中较小的元素，由于删去的元素个数具有单调性，所以使用二分优化，计算最少要删去几个元素。......
  • CodeForces 1883F You Are So Beautiful
    题目链接：CodeForces1883F【YouAreSoBeautiful】思路    要找出一个子数组使得在数组中只能找出一个子序列和当前子数组相等，则只需要找出首元素的数字必须为当前元素值第一次出现，尾元素的数字必须为当前元素值最后一次出现，则只能找出唯一的子序列和当前子数组相等。......
  • codeforces 1209E1 Rotate Columns (easy version)
    codeforces1209E1RotateColumns(easyversion)题目传送门：codeforcces，luogu思路贪心，暴力搜索贪心对于所有列，只有列中最大值在所有列的最大值中前\(n\)大才可能对答案有贡献。证明：若有非前\(n\)大的列对某行最大值产生了贡献，则用没有被取的前\(n\)大的列代替该行......
  • Codeforces Round 962 (Div. 3) 题解 A-F
    A.LegsProblem-A-Codeforces1.1翻译农夫约翰的农场又迎来了美好的一天。农夫约翰来到农场后，数了数n条腿。众所周知，农场里只住着鸡和牛，一只鸡有2条腿，而一头牛有4条腿。假设约翰农场主数清了所有动物的腿，那么他的农场里最少有多少动物？1.2思路求最少有几只动物......
  • Codeforces Round 962 (Div. 3)
    题目链接：CodeforcesRound962(Div.3)总结：ABC秒过，D有点难评了，E优化很妙。A.Legstag：签到voidsolve(){cin>>n;inta=n/4,b=n%4;a+=b/2;cout<<a<<endl;}B.Scaletag：模拟voidsolve(){cin>>n>>k;......
  • CodeForces 1883E Look Back
    题目链接：CodeForces1883E【LookBack】思路    若直接对每个元素进行操作累乘至大于相邻的前一个元素时，可能最后会数据溢出，而且乘的2个数可能会很多，会时间超限。所以可以对每两个相邻的元素进行判断，判断他们之间差了2的多少次方。cnt记录的是当前元素和上个元素之间差......
  • CodeForces 1883D In Love
    题目链接：CodeForces1883D【InLove】思路    求能否找出两个区间不相交，所以将得到的区间先按区间左端点的大小从小到大排列，再按区间右端点的大小从小到大排列，此时取出最小的右端点和最大的左端点，若右端点在左端点左侧，则存在两个不相交的区间。由于需要动态操作增加减......
  • CodeForces 1883C Raspberries
    题目链接：CodeForces1883C【Raspberries】思路    依次枚举，特判k=4的情况，因为k=4可以由2个2拼凑起来，这2个2可以不在同一个元素上，如K=4时，数组a可以为2,3,2,5,7,9，此时数组中所有的元素乘积可以被4整除。若k=4时，此时数组中元素没有可以拆分出2的情况时，所有的......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99