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

Codeforces Round 892 (Div. 2)

时间：2023-08-13 21:11:24浏览次数：39  
标签：892 const int typedef long Codeforces Div include define

Preface

最接近橙名的一场，可惜给我一个小时也没想到E的关键点，后面徐神一点拨就懂了

虽然现在这个号已经到渡劫局了但因为之前有场比赛给了ztc一份代码然后他直接没咋改交上去了，估计下次roll Rating的时候这个号要掉200来分了

嘛不过也无所谓反正下次打另一个号冲分，而且像我这种永远写不来Div2 E的人纯靠手速打上2100真的有说服力吗

A. United We Stand

签到题，把最大的数都放在\(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<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],b[N],c[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]);
		bool flag=0; for (i=2;i<=n;++i) if (a[i]!=a[1]) flag=1;
		if (!flag) { puts("-1"); continue; }
		int nb=0,nc=0,mx=0; for (i=1;i<=n;++i) mx=max(mx,a[i]);
		for (i=1;i<=n;++i) if (a[i]!=mx) b[++nb]=a[i];
		for (i=1;i<=n;++i) if (a[i]==mx) c[++nc]=a[i];
		for (printf("%d %d\n",nb,nc),i=1;i<=nb;++i)
		printf("%d%c",b[i]," \n"[i==nb]);
		for (i=1;i<=nc;++i) printf("%d%c",c[i]," \n"[i==nc]);
	}
	return 0;
}

B. Olya and Game with Arrays

不难发现由于所有数的最小值一定会在某个序列中造成贡献，那么我们不妨把所有数组中的最小值都扔到一个数组中

维护每个数组的次小值然后找一个最小的减去即可

#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<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=25005;
int t,n,m,x,mi[N],smi[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",&n),i=1;i<=n;++i)
		{
			scanf("%d",&m); vector <int> num;
			for (j=1;j<=m;++j) scanf("%d",&x),num.push_back(x);
			sort(num.begin(),num.end());
			mi[i]=num[0]; smi[i]=num[1]; 
		}
		int allmi=mi[1],mismi=smi[1]; LL sum=0;
		for (i=1;i<=n;++i) allmi=min(allmi,mi[i]),mismi=min(mismi,smi[i]),sum+=smi[i];
		printf("%lld\n",allmi+sum-mismi);
	}
	return 0;
}

C. Another Permutation Problem

很有意思的一个题，首先由于数据范围很小我们可以直接暴力枚举\(\max_{j = 1}^{n} p_j \cdot j\)的值

然后贪心地从大到小考虑每个\(p_i\)，将它能匹配的数中最大的找出来和它匹配即可

我刚开始的时候用了个set实现，然后跑了手\(n=250\)发现要跑5s……

但直觉告诉我们\(\max_{j = 1}^{n} p_j \cdot j\)的值肯定不会太小，然后把\(n=250\)的输出来一看大概是\(57000+\)左右，所以就把枚举\(\max_{j = 1}^{n} p_j \cdot j\)的值调整成\([\max(n^2-15000,1),n^2]\)即可

后面问了下ztc发现其实可以把set那个地方用并查集维护，就是删去一个数的时候把它接到前面的数上，就可以用大致线性的复杂度来做了

但据说这题可以打表发现最优的答案就是把\(\{1,2,3,\cdots,n\}\)的某个后缀翻转，这样就可以枚举后缀然后做到总复杂度\(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<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=255;
int t,n;
inline int solve(CI x)
{
	set <int> s; RI i; int ret=0;
	for (i=1;i<=n;++i) s.insert(i);
	for (i=n;i>=1;--i)
	{
		auto it=s.upper_bound(x/i);
		if (it==s.begin()) return 0;
		--it; ret+=*it*i; s.erase(it);
	}
	return ret;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; int ans=0; for (scanf("%d",&n),i=max(1,n*n-15000);i<=n*n;++i)
		ans=max(ans,solve(i)-i); printf("%d\n",ans);
	}
	return 0;
}

D. Andrey and Escape from Capygrad

首先由于这题传送区间的性质，不难发现答案随着起点的增加是不减的，这就提醒我们可以从大到小递推答案

考虑用类似扫描线的思路维护出每个点被覆盖的区间，那么这些区间的\(f_{b_i}\)中的最大值就可以用来更新答案

离散化下标后用树状数组维护最值即可，总复杂度\(O(n\log 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<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;
struct ifo
{
	int x,id;
	inline ifo(CI X=0,CI ID=0)
	{
		x=X; id=ID;
	}
	friend inline bool operator < (const ifo& A,const ifo& B)
	{
		return A.x>B.x;
	}
}o[N]; int t,n,l[N],a[N],b[N],r[N],q,x[N],rst[N],cnt,tot,ans[N];
class Tree_Array
{
	private:
		int mx[N],lim;
	public:
		#define lowbit(x) (x&-x)
		inline void init(CI n)
		{
			lim=n; for (RI i=1;i<=lim;++i) mx[i]=0;
		}
		inline int get(RI x,int ret=0)
		{
			for (;x;x-=lowbit(x)) ret=max(ret,mx[x]); return ret;
		}
		inline void add(RI x,CI y)
		{
			for (;x<=lim;x+=lowbit(x)) mx[x]=max(mx[x],y);
		}
		#undef lowbit
}BIT;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),cnt=0,i=1;i<=n;++i)
		scanf("%d%d%d%d",&l[i],&r[i],&a[i],&b[i]),
		rst[++cnt]=l[i],rst[++cnt]=r[i],rst[++cnt]=a[i],rst[++cnt]=b[i];
		for (scanf("%d",&q),i=1;i<=q;++i) scanf("%d",&x[i]),rst[++cnt]=x[i];
		sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;
		auto find=[&](CI x)
		{
			return lower_bound(rst+1,rst+cnt+1,x)-rst;
		};
		for (tot=0,i=1;i<=n;++i)
		{
			l[i]=find(l[i]); r[i]=find(r[i]); a[i]=find(a[i]); b[i]=find(b[i]);
			o[++tot]=ifo(b[i],i);
		}
		for (i=1;i<=q;++i) x[i]=find(x[i]),o[++tot]=ifo(x[i],n+i);
		for (sort(o+1,o+tot+1),BIT.init(cnt),i=1;i<=tot;++i)
		{
			int tmp=max(rst[o[i].x],BIT.get(o[i].x));
			if (o[i].id<=n) BIT.add(l[o[i].id],tmp); else ans[o[i].id-n]=tmp;
		}
		for (i=1;i<=q;++i) printf("%d%c",ans[i]," \n"[i==q]);
	}
	return 0;
}

E. Maximum Monogonosity

首先看到绝对值的式子就考虑拆绝对值，我们分四种情况来转移，最后取\(\max\)后一定能得到正确的答案

考虑朴素的DP，\(f_{i,j}\)表示前\(i\)个数，选的区间长度为\(j\)的最大答案，则转移方程为：

\[f_{k,j}+|a_{k+1}-b_i|+|b_{k+1}-a_i|\to f_{i,j+(i-k)} \]

乍一看感觉因为第二个下标的缘故很难维护答案，其实稍作观察就会发现转移只能在\(i-j\)相同的\(f_{i,j}\)之间发生

因此我们对于所有\(i-j\)的值以及\(4\)种情况分别维护最大值即可\(O(1)\)转移了，复杂度\(O(nk)\)

#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<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=3005,INF=1e18,s1[4]={1,1,-1,-1},s2[4]={1,-1,1,-1};
int t,n,k,a[N],b[N],f[N][N],mx[N][4];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j,s; for (scanf("%lld%lld",&n,&k),i=1;i<=n;++i) scanf("%lld",&a[i]);
		for (i=1;i<=n;++i) scanf("%lld",&b[i]);
		for (f[0][0]=0,i=1;i<=k;++i) f[0][i]=-INF;
		for (i=1;i<=n;++i) for (j=1;j<=i;++j) f[i][j]=-INF;
		auto calc=[&](CI x,CI y,CI tp)
		{
			return f[x][x-y]+a[x+1]*s1[tp]+b[x+1]*s2[tp];
		};
		for (s=0;s<4;++s) for (mx[0][s]=calc(0,0,s),i=1;i<=n;++i) mx[i][s]=-INF;
		for (i=1;i<=n;++i)
		{
			for (j=0;j<=k;++j) f[i][j]=f[i-1][j];
			for (j=0;j<=min(i,k);++j)
			{
				int dlt=i-j; for (s=0;s<4;++s)
				f[i][j]=max(f[i][j],mx[dlt][s]-b[i]*s1[s]-a[i]*s2[s]);
				for (s=0;s<4;++s) mx[dlt][s]=max(mx[dlt][s],calc(i,dlt,s));
			}
		}
		printf("%lld\n",f[n][k]);
	}
	return 0;
}

Postscript

F题因为今天下午打百度之星所以没时间补了，而且看了一眼感觉不容易就先弃了

标签：892,const,int,typedef,long,Codeforces,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/17627282.html

相关文章

  • 2023年多校联训NOIP层测试7+【LGR-149-Div.3】洛谷基础赛 #2 & qw Round -1
    2023年多校联训NOIP层测试7，集训欢乐赛，绝对欢乐，童叟无欺赛时在回家的路上+睡觉，所以没打。\(T1\)近似ybtOJ2049：【例5.19】字符串判等本题少了对空格的判断，水题。PS：题面和题解中都写了文件输入输出，测评时没有文件输入输出是几个意思，艹。#include<bits/stdc++.h>usingname......
  • 【题解】Educational Codeforces Round 146（CF1814）
    而且怎么感觉E,F比D要简单很多，大概是因为比较套路吧[惊恐]A.Coins题目描述：本题一共有\(t\)组数据。每组数据包含两个整数\(n\)和\(k\)，如果存在两个非负整数\(x,y\)，满足\(2\timesx+k\timesy=n\)，输出YES，否则输出NO（yes,Yes,NO,nO均可）。题目分析：注意到\(y\)可......
  • Codeforces Round 892 (Div. 2)(vp)
    CodeforcesRound892(Div.2)AUnitedWeStand题意：给一个数组，让你把它分成两个数组，第二个数组里的数不能是第一个数组里的数的除数，先输出两个数组的长度，依次输出两个数组的数，如果无法分出来，输出-1思路：如果数的种类只有一种一定不行，反之一定行，对于可行的情况，我们把最大的......
  • Codeforces Round 892 (Div. 2)
    手速慢了，掉分C.AnotherPermutationProblemProblem-C-Codeforces题意给定一个正整数\(n\)，设序列\(p\)为\(n\)的排列，求\(\sum_{i=1}^{n}p_i\timesi-max_{j=1}^np_j\timesj\)的最大值。思路打表可知，答案的排列一定为翻转一部分后缀。暴力枚举要翻转的后缀即可。代码......
  • Codeforces Round 892 div2.C
    这C真的魔幻，官方题解完全和写的不一样，太玄学了，打表发现的规律这是打表代码:intmain(){cin>>n;vector<int>a(n+1);for(inti=1;i<=n;i++)a[i]=i;LLans=0;do{autob=a;LLsum=0,mx=0;......
  • Codeforces Round 892 (Div.2)
    A.UnitedWeStand题解赛时想复杂了题目要求我们保证数组\(c\)中的数不是数组\(b\)中任意一个数的因子我们考虑将最小值置于数组\(b\)即可constintN=2e5+10,M=4e5+10;intn;inta[N];voidsolve(){cin>>n;intmi=INF;for(inti......
  • Codeforces Round 874 G题解
    做不动那么多题了，来个GG就是问你一棵树能切成多少个大小为3的链，想了半天，想过dp啥的，但是后来发现这个贪心就好了，可以证明贪心找不到的，其他方法也找不到好久没复健了，这是第一次，感觉以后要多做题才可以#include<bits/stdc++.h>usingnamespacestd;constexprintlimit=(4e......
  • 【LGR-149-Div.3】洛谷基础赛 #2 & qw Round -1
    T1签到。T2送分题。T3大模拟，但是TLE两个点。#include<bits/stdc++.h>#definelllonglong#defineintlonglong#definereregisterusingnamespacestd;constintN=1e5+5,INF=0x3f3f3f3f;intn;queue<string>Q;map<string,int>zt;//0不在；1排队；2游玩；......
  • Codeforces Round 799 (Div. 4)(vp)
    CodeforcesRound799(Div.4)AMarathonvoidsolve(){vector<int>a(4);intgoal;cin>>goal;intans=0;for(inti=0;i<3;i++){intx;cin>>x;if(goal<x)ans++;}co......
  • Codeforces 1854E - Game Bundles
    都这么会乱搞的吗/xia随机生成若干\(<30\)的数直到它们当中和为\(60\)的子集个数\(>k\)为止。删去最后一个元素。然后考虑贪心确定\(>30\)的部分，具体方法是按照\(dp_{60-x}\)从大到小贪心选，如果剩余子集个数\(\gedp_{60-x}\)就在序列中加入\(x\)。如此随机化直到找......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99