标签：958 typedef int Codeforces long pair Div include define

Preface

周末补题计划的最后一场，这场由于是最古早的所以有些题题意都记不太清了

赛时经典发病，前四题一题 WA 一发，然后把时间打没了 E 题经典没写完（中间还抽空写了个假做法），邮电部诗人了属于是

A. Split the Multiset

刚开始还感觉无从下手，写了个记搜交上去还 WA 了，后面发现每次分裂出 \(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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1005;
int t,n,k;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	scanf("%d%d",&n,&k),printf("%d\n",(n-1+k-2)/(k-1));
	return 0;
}

B. Make Majority

上来经典乱猜结论先挂一发后才能好好想题

不难发现操作一段区间如果得到的结果为 \(1\)，则并不会使得 \(0,1\) 的个数差发生变化（如 \(101\to 1\)，个数差保持在 \(1\) 个）

而唯一能减少个数差的操作只有把连续的一段 \(0\) 变成单独一个，因此先这样收缩完后比较 \(0,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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,pfx[N]; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%s",&n,s+1); int c[2]={0,0};
		for (i=1;i<=n;++i)
		if (s[i]=='1') ++c[1]; else
		if (s[i-1]!='0') ++c[0];
		puts(c[1]>c[0]?"Yes":"No");
	}
	return 0;
}

C. Increasing Sequence with Fixed OR

经典对着样例猜结论，通过观察发现序列长度最大为 \(n\) 在二进制下 \(1\) 的个数 \(+1\)

构造方案也很简单，从高到低将为 \(1\) 的位依次消去即可，最后补上 \(n\) 本身

由于不能出现 \(0\)，因此要特判形如 \(2^k\) 的数，当然关于这个为什么是最优的建议去看 Tutorial

#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; LL n;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%lld",&n);
		vector <LL> ans;
		for (RI i=60;i>=0;--i)
		if (((n>>i)&1)&&(n^(1LL<<i))!=0) ans.push_back(n^(1LL<<i));
		ans.push_back(n);
		printf("%d\n",ans.size());
		for (auto x:ans) printf("%lld ",x); putchar('\n');
	}
	return 0;
}

D. The Omnipotent Monster Killer

经典先乱搞一发 WA 了再猜结论，我愿称之为红温做题法

刚开始一波观察样例认为只需要两轮就能删完，因此就是跑一个树上最大权独立集，然后写完交上去就似了

后面手玩出了一组需要三轮操作的样例，本来准备把两轮改成三轮冲了，但后面还是冷静想了想感觉会有更多轮的情况

但直觉告诉我们这个轮数一定不会很多，对着一个链的情况画一画会感觉大概就是 \(\log\) 级别的轮数，实现时就直接取 \(20\) 了

因此此时把问题转化为，给树上的每个点赋一个权值 \(c_i\in [1,20]\)，在满足任意两个相邻的点权值不同的情况下，最小化 \(\sum_{i=1}^n a_i\times c_i\)

很容易想到 DP，令 \(f_{i,j}\) 表示处理了 \(i\) 的子树，且 \(c_i=j\) 时子树内最小权值和，朴素的转移是 \(O(n\times 20^2)\) 的，但预处理下每个点的最大/次大值可以很容易做到 \(O(n\times 20)\) 的复杂度

#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=300005;
int t,n,a[N],x,y,f[N][20],mn[N],smn[N]; vector <int> v[N];
inline void DP(CI now=1,CI fa=0)
{
	RI i; for (i=1;i<20;++i) f[now][i]=a[now]*i;
	for (auto to:v[now]) if (to!=fa)
	{
		for (DP(to,now),i=1;i<20;++i)
		if (mn[to]==f[to][i]) f[now][i]+=smn[to];
		else f[now][i]+=mn[to];
	}
	mn[now]=f[now][1]; smn[now]=f[now][2];
	if (mn[now]>smn[now]) swap(mn[now],smn[now]);
	for (i=3;i<20;++i)
	if (f[now][i]<mn[now]) smn[now]=mn[now],mn[now]=f[now][i];
	else if (f[now][i]<smn[now]) smn[now]=f[now][i];
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; int sum=0; for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%lld",&a[i]),v[i].clear(),sum+=a[i];
		for (i=1;i<n;++i)
		scanf("%lld%lld",&x,&y),v[x].push_back(y),v[y].push_back(x);
		DP(); printf("%lld\n",mn[1]);
	}
	return 0;
}

E. Range Minimum Sum

比赛的时候抽风了一个弯没绕过了，然后就释怀地似了

没有删除元素的时候做法很多，大致思路都是一致的，即找到每个位置左边/右边第一个小于该元素的位置 \(l_i/r_i\)，实现时可以用单调栈（笛卡尔树）或 set 处理

先计算出起始时的答案，并考虑修改一个位置 \(a_p\) 带来的影响：

最小值为 \(a_p\) 的区间没了，这个贡献初始时就已经计算过了；
对于一些 \(a_i<a_p\) 的位置，以 \(i<p\) 为例，若 \([i+1,p-1]\) 中没有 \(<a_i\) 的元素，则最小值为 \(a_i\) 的区间会少去一部分贡献，这部分实际上是个区间加，可以差分解决；
对于一些 \(a_i>a_p\) 的位置，以 \(i<p\) 为例，当 \(a_p\) 被删掉后 \(a_i\) 为最小值的区间反而增加了；这类贡献在 \(a_i\) 处统计比较方便，即我们找到 \(>i\) 的第一个 \(<a_i\) 的位置 \(p\)，并找出 \(>p\) 的第一个 \(<a_i\) 的位置 \(q\)，那么 \(a_p\) 被删除时最小值为 \(a_i\) 的区间就会增多 \((q-p-1)\times (i-l_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<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=500005;
int t,n,a[N],d[N],pos[N],dlt[N],val[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld",&n),i=1;i<=n;++i)
		scanf("%lld",&a[i]),pos[a[i]]=i,d[i]=dlt[i]=0;
		set <int> s; s.insert(0); s.insert(n+1);
		int sum=0; for (i=1;i<=n;++i)
		{
			int p=pos[i],L=*(--s.lower_bound(p)),R=*s.upper_bound(p);
			val[p]=i*(p-L)*(R-p); sum+=val[p];
			auto upt=[&](CI l,CI r,CI mv)
			{
				d[l]+=mv; d[r+1]-=mv;
			};
			if (L+1<=p-1) upt(L+1,p-1,-i*(R-p));
			if (p+1<=R-1) upt(p+1,R-1,-i*(p-L));
			auto it=s.lower_bound(p);
			if (it!=s.begin())
			{
				if (--it!=s.begin())
				{
					auto pre=it; --pre;
					dlt[*it]+=i*(*it-*pre-1)*(R-p);
				}
			}
			it=s.upper_bound(p);
			if (it!=s.end())
			{
				auto nxt=it; ++nxt;
				if (nxt!=s.end())
				{
					dlt[*it]+=i*(*nxt-*it-1)*(p-L);
				}
			}
			s.insert(p);
		}
		for (i=1;i<=n;++i) d[i]+=d[i-1];
		for (i=1;i<=n;++i) printf("%lld%c",sum-val[i]+d[i]+dlt[i]," \n"[i==n]);
	}
	return 0;
}

Postscript

感觉最近的训练强度有点大了，好多题都没来得及补就要开始新一周的训练了，不过还是很充实的说

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

Codeforces Round 958 (Div. 2)