首页 > 其他分享 >Codeforces Round 890 (Div. 2) supported by Constructor Institute

Codeforces Round 890 (Div. 2) supported by Constructor Institute

时间：2023-08-06 22:12:28浏览次数：35  
标签：890 sz typedef Institute supported long int include define

Preface

现在开始严格按照双号上分法来打CF了，大致就是每次比赛都拿两个号中分较少的那个打，这样可以保证两个号的最高分不降

然后昨天打完就后悔了，没有拿hl666那个号打导致没抓住难得的上分机会，本来可以打到橙名渡劫局的但分全加在Kusanagi_Misuzu那个号上了

不过昨天这场其实可以打的更好的，前面被C搞了导致后面时间不够宽裕了，最后写完E1还有25min其实完全可以搏一搏E2的，但就是下意识地以为自己写不来就没想了

后面一看题解妈的就是我前两天和ztc说的多重背包在总体积较小时的优化，血妈亏

A. Tales of a Sort

签到题，不难发现如果\(a_i> a_{i+1}\)，则我们只要要操作\(a_i\)次来把这两个数都变成\(0\)，因此取最大值输出即可

#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>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=55;
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),i=1;i<=n;++i) scanf("%d",&a[i]);
		int ans=0; for (i=1;i<n;++i) if (a[i]>a[i+1]) ans=max(ans,a[i]);
		printf("%d\n",ans);
	}
	return 0;
}

B. Good Arrays

刚开始秒出了一个假算法WA了一发，后面冷静下来才发现我是傻逼

首先特判\(n=1\)时无解，否则我们不妨令原序列所有\(a_i\ne1\)的位置都有\(b_i=1\)，而\(a_i=1\)的位置都有\(b_i=2\)

做完之后求出\(\sum_{i=1}^n b_i\)和\(\sum_{i=1}^n a_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>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=100005;
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; LL sum=0; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
		if (n==1) { puts("NO"); continue; }
		LL ret=0; for (i=1;i<=n;++i) ret+=(a[i]!=1?1:2);
		puts(ret<=sum?"YES":"NO");
	}
	return 0;
}

C. To Become Max

这题就是很容易想一些假算法，刚开始写了个样例都过不去，后面重新想了下才过

考虑枚举最后最大值出现的位置，刚开始想着是模拟加数的过程，但十分难写

后面发现其实大可以二分最后变成的值，然后转化成判定性问题后就很好办了

假设当前变成的最大值为\(x\)，则最后这一段数一定形如\(x,x-1,x-2\cdots\)，只要中间存在某个位置大于等于目标值既可以中止了

注意特判处理到最后一个数的情况，具体实现可以看代码，复杂度\(O(n^2\log a_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>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=1005,INF=1e9;
int t,n,k,a[N];
inline bool check(CI tar)
{
	for (RI i=1,j;i<=n;++i)
	{
		int ret=0; for (j=i;j<=n;++j)
		{
			if (tar-(j-i)<=a[j]) break;
			ret+=tar-(j-i)-a[j];
			if (j==n) ret+=INF;
		}
		if (ret<=k) return 1;
	}
	return 0;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; int mx=0; for (scanf("%lld%lld",&n,&k),i=1;i<=n;++i) scanf("%lld",&a[i]),mx=max(mx,a[i]);
		int l=mx,r=mx+k,mid,ret; while (l<=r)
		if (check(mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
		printf("%lld\n",ret);
	}
	return 0;
}

D. More Wrong

比赛时过的人不多但我感觉是个很一眼的题

首先考虑一种保证正确性的做法，假设我们已经知道了\([1,i]\)中最大值的位置\(x\)

那么考虑加入\(i+1\)后最大值无非两种情况，保留\(x\)或者变成\(i+1\)

而我们只需要比较\([1,i]\)的逆序对数量是否和\([1,i+1]\)的逆序对数量相同即可

若相同则说明\(i+1\)比\([1,i]\)中的所有数都大，自然是\([1,i+1]\)的最大值，否则则说明\([1,i]\)中有至少一个数大于\(a_{i+1}\)，则说明最大值仍为\(x\)

然后要优化的话是显然的，我们用分治法每次先递归求出子区间的最大值位置，再合并即可

稍微列出最坏情况下的式子的代价算一下可以得到：

\[2\times n^2+4\times (\frac{n}{2})^2+8\times (\frac{n}{4})^2+\cdots\\ =(2+1+\frac{1}{2}+\frac{1}{4}+\cdots)\times n^2<4n^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>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
int t,n;
inline LL ask(CI l,CI r)
{
	printf("? %d %d\n",l,r); fflush(stdout);
	LL x; scanf("%lld",&x); return x;
}
inline int solve(CI l=1,CI r=n)
{
	if (l==r) return l;
	int mid=l+r>>1,lpos=solve(l,mid),rpos=solve(mid+1,r);
	if (lpos+1==rpos)
	{
		LL res=ask(lpos,rpos);
		if (res==1) return lpos; return rpos;
	}
	LL res1=ask(lpos,rpos),res2=ask(lpos,rpos-1);
	if (res1==res2) return rpos; return lpos;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t) scanf("%d",&n),printf("! %d\n",solve()),fflush(stdout);
	return 0;
}

E1. PermuTree (easy version)

首先有个很显然的性质就是每个子树内的数一定是一段连续的区间，正确性显然

因此我们考虑统计某个点的答案时，只要将它的子树划分为两类，一类是最后填的数小于它本身的，一类是大于它本身的，不难发现两类集合的大小之积就是贡献

那么问题其实可以转化为一个0/1背包问题，直接暴力做就可以通过E1了

#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_set>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=5005;
int n,x,sz[N]; vector <int> v[N]; LL ans;
inline void DFS(CI now=1)
{
	sz[now]=1; for (int to:v[now]) DFS(to),sz[now]+=sz[to];
	unordered_set <int> s; s.insert(0);
	for (int to:v[now])
	{
		unordered_set <int> t=s;
		for (int x:s) t.insert(x+sz[to]);
		s=t;
	}
	LL ret=0; for (int x:s) ret=max(ret,1LL*x*(sz[now]-1-x));
	ans+=ret;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=2;i<=n;++i) scanf("%d",&x),v[x].push_back(i);
	return DFS(),printf("%lld",ans),0;
}

E2. PermuTree (hard version)

曾记得某天ztc问过我和这个一模一样的东西，当时我秒出了做法但现在我TMD的想都懒得想了可海星

考虑这个0/1背包的一大特点就是总体积和也是\(O(n)\)级别的，利用类似于根号分治的思想我们知道不同类的物品的个数很少

因此可以把它转化成多重背包来做，为了优化可以再加一个二进制分组上去，当然再极限一点的话再套个bitset也不是不行

同时有一个很有用的剪枝就是当存在某个子树的大小大于其它所有子树大小之和时可以直接计算贡献，实测发现这个剪枝非常有效

总复杂度不太好写表达式，总之大概跑1s左右

#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_set>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=1e6+5;
int n,x,sz[N],f[N]; vector <int> v[N]; LL ans;
inline void DFS(CI now=1)
{
	sz[now]=1; int mx=0; for (int to:v[now])
	DFS(to),sz[now]+=sz[to],mx=max(mx,sz[to]);
	if (mx*2>=sz[now]-1) return (void)(ans+=1LL*mx*(sz[now]-1-mx));
	int lim=(sz[now]-1)/2; map <int,int> rst;
	RI i,j; for (f[0]=1,i=1;i<=lim;++i) f[i]=0;
	for (int to:v[now]) ++rst[sz[to]];
	int ret=0; for (auto [x,y]:rst)
	{
		for (int k=1;y>=k;y-=k,k<<=1)
		{
			int v=k*x; for (j=lim;j>=v;--j)
			if (f[j-v]) f[j]=1,ret=max(ret,j);
		}
		if (y)
		{
			int v=y*x; for (j=lim;j>=v;--j)
			if (f[j-v]) f[j]=1,ret=max(ret,j);
		}
	}
	ans+=1LL*ret*(sz[now]-1-ret);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=2;i<=n;++i) scanf("%d",&x),v[x].push_back(i);
	return DFS(),printf("%lld",ans),0;
}

Postscript

现在两个号都是2000+了，感觉有望趁状态好冲一波橙名了

标签：890,sz,typedef,Institute,supported,long,int,include,define
From： https://www.cnblogs.com/cjjsb/p/17610170.html

相关文章

  • 【题解】Codeforces Round 890（CF1856）
    赛时过了A-E1，rk195可惜是E2傻逼了不会背包优化了，直接连普及组水平都不到了。A.TalesofaSort题目描述：给定长度为\(n\)的序列\(a\)，每次操作为对于所有\(i\)将\(a_i\)变为\(\max(a_i-1,0)\)，询问最少多少次操作之后可以让序列\(a\)单调不降。题目分析：唯一能改变......
  • Codeforces Round 890 (Div. 2)
    TalesofaSort题解找到最大的能够产生逆序对的数即可暴力\(O(n^2)\)枚举即可constintN=2e5+10,M=4e5+10;intn;inta[N];voidsolve(){cin>>n;intans=0;for(inti=1;i<=n;++i){cin>>a[i];}fo......
  • Codeforces Round 890 (Div. 2) supported by Constructor Institute ————C - T
    关于这场div2，只能说一言难尽C题可以二分的，赛时看到n<=1000,直接往\(O(n^2)\)考虑，想了一会贪心的话能写出来，但是，细节太多没调出来，G掉打分。\(O(n^2)\)做法：思路：每次让i为起点，往前贪心枚举，并且当前位置如果满足，也要枚举当前区间，细节就是要注意上下限，赛时，漏了一种上界小于下届的情......
  • Codeforces Round 890 (Div. 2) supported by Constructor Institute 题解
    A.TalesofaSort关键就是找逆序对记一组逆序对下标为\(l,r\)，则求出最大的\(a_l\)即可B.GoodArrays记要构造的GoodArray为\(b\)前置：\(\forall1\lei\len,b_i=1\)然后\(O(n)\)扫一遍看一下有没有重复，有重复就\(b_i\leftarrowb_i+1\)扫完之后，记\(sum=\sum_......
  • msm8909_wk2124_SPI转串口485
    项目使用的是高通的msm8909平台，采用广和通SC806开发板，开发环境采用Ubuntu18.04。SC806默认有两路串口，对项目来说不够使用，需要进行转接，所以采用了wk2124将一路SPI转换为4路串口，然后再加485芯片，转换为4路485接口。接下来详细看看整个配置过程。概述说明：本文档会将为开提供的官方文......
  • 漏洞复现报告:CVE-2019-2890 反序列化漏洞
    OracleWebLogicServer漏洞研究报告一、漏洞信息搜集1.1漏洞信息表漏洞名称OracleWebLogicServer反序列化漏洞发布时间2019年10月16日漏洞编号CVE-2019-2890威胁类型反序列化漏洞危害级别高危影响版本OracleWebLogicServer10.3.6.0.0、12.1.3.0.0、12.2.1.3.0、12.2.1.4.0......
  • msm8909_Setting中添加永不休眠功能
    项目中需要让Android板开机就进入桌面并且永不休眠。项目使用的是广和通的SC806Android开发板，msm8909平台。配置永不休眠diffdiff文件放前面，可以直接apply进去！diff--gita/frameworks/base/packages/SettingsProvider/res/values/defaults.xmlb/frameworks/base/packages/Se......
  • msm8909_MIPI转HDMI调试记录
    项目中需要把开发板的MIPI输出信号转换为HDMI和LVDS输出，使用龙迅的LT8912B进行转换。龙迅的FAE提供的资料相对来说还是比较少的。先简单的看一下吧：厂商资料寄存器配置该文件提供了对LT8912B初始化的寄存器配置。对于我们来说需要做的就是，写一个驱动，在开机的时候调用相关的函数，......
  • Ubuntu16 编译源码出错 unsupported reloc 43
      错误如下prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.11-4.6//x86_64-linux/include/c++/4.6/bits/basic_string.h:270:error:unsupportedreloc43prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.11-4.6//x86_64-linux/include/c++/4.6/bits/basic_string.h:270......
  • Python报错 | xlrd.biffh.XLRDError Excel xlsx file; not supported
    报错信息Python加载xlsx文件时，遇到：xlrd.biffh.XLRDErrorExcelxlsxfile;notsupported错误原因报错翻译过来是：xlrd.biffh.xlrd错误：Excelxlsx文件；不受支持解决方案方法1：安装指定低版本的xlrd，执行下面的pip安装命令即可：pipinstallxlrd==1.2.0方法2：Excel另存为......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99