CF #636 (Div. 3) 对应题号CF1343

unrated 选手悠闲做题，然后只做出四个滚蛋了
符合 div3 一贯风格，没啥难算法
E最后就要调出来了，但还是赛后才A的

CF1343A Candies

传送门
找到一个 (x)，使得存在一个正整数 (k>1)，满足 (sum_{i=0}^{k-1}2^i x=n)
给定 (n)

[sum_{i=0}^{k-1}2^i x=nRightarrow 2^k-1=frac{n}{x} ]

那么我们只要枚举 (xin[1,sqrt n])，如果 (xmid n)，那么就进行计算：
从 (1) 枚举 (k)，看看有没有一个 (k) 使得 (2^k-1=x) 或 (2^k-1=frac{n}{x})
直到 (2^k-1>max(x,frac{n}{x}))

复杂度 (O(sqrt nlogsqrt n))，应该是这样

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
int main(){int T=read();while(T--){
	LL n=read();
	for(reg LL i=1;i*i<=n;i++)if(!(n%i)){
		LL tmp=n/i;
		for(reg LL k=2,s=4;;k++,s<<=1){
			if(s-1==i){
				std::printf("%d
",tmp);goto YES;
			}
			if(s-1==tmp){
				std::printf("%d
",i);goto YES;
			}
			if(s-1>i&&s-1>tmp) break;
		}
	}
	YES:;
}
	return 0;
}

CF1343B Balanced Array

传送门
给定偶数 (n)，求一个数列，数列的前半段都是偶数，后半段都是奇数，前半段后半段的和相等

对于前 (n-1) 位，构造数列：(2,4,6,8,cdots,1,3,5,7,cdots)
也就是对于前半段，(a_i=2i)，对于后半段，(a_i=2(i-frac{n}{2})-1,i e n)
那么这 (frac{n}{2}) 位后半段都比前半段少 (1)，就要通过最后一位补回来，所以第 (n) 位是 (2(n-frac{n}{2})-1+frac{n}{2}=n-1+frac{n}{2})
如果这个数是奇数，则有解，是偶数则无解（因为后半段规定要是奇数）

至于这样无解怎么严格证明很简单，可是我懒得证了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
int main(){int T=read();while(T--){
	int n=read();
	if(n%4) std::puts("NO");
	else{
		std::puts("YES");
		for(reg int i=1;i<=n/2;i++) std::printf("%d ",i*2);
		for(reg int i=1;i<n/2;i++) std::printf("%d ",i*2-1);
		std::printf("%d
",n-1+n/2);
	}
}
	return 0;
}

CF1343C Alternating Subsequence

传送门
给定一个长度为 (n,2mid n,a_i e 0) 的数列，定义“交替数列”为：每两个相邻数正负性不同的数列
问给定数列的子数列中，最长的“交替数列”，的最大和是多少
就是说长度最大的“交替数列”有很多，求其中每个元素和最大的数列，的这个最大的和是多少

首先，把给定数列分成若干段，每段的正负性相同，相邻段的正负性不同
就是从左到右遍历数列，一旦正负性发生变化，就加一个新的段
比如数列：(1,7,5,-1,-6,4,-7,-8)
当中，(1,7,5) 是一段，(-1,-6) 是一段，(4) 是一段，(-7,-8) 是一段
那么长度最大的“交替数列”，就一定是在每一段中，分别取一个数

那么我们只要分别记录每一段数的最大值，加起来就行了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
int main(){int T=read();while(T--){
	int n=read();
	if(n==1){
		std::printf("%d
",read());
		continue;
	}
	reg LL is_posi,x,max=read();x=max;
	if(x>0) is_posi=1;
	else is_posi=0;
	reg LL ans=0;
	for(reg int i=2;i<=n;i++){
		x=read();
		if(x>0){
			if(is_posi) max=std::max(max,x);
			else ans+=max,max=x,is_posi=1;
		}
		else{
			if(!is_posi) max=std::max(max,x);
			else ans+=max,max=x,is_posi=0;
		}
	}
	std::printf("%lld
",ans+max);
}
	return 0;
}

CF1343D Constant Palindrome Sum

传送门
给定长度为 (n,2mid n,a_iin [1,k]) 的数列，其中 (k) 是定值
可以对每个数进行修改，让它变为 (x,xin [1,k])
求最小的修改次数，使得 (forall iin[1,frac{n}{2}],a_i=a_{n-i+1})

我们把每个 (a_i,a_{n-i+1}) 看作“一对数”
然后开个桶记录 (t_x) 表示有几个 (a_i+a_{n-i+1}=x)
然后枚举 (x)，分别确定有几对数是两个都要修改，有几对是只用修改其中一个，有几对是一个不用修改（最后这个就是 (t_x) 对）

那么如何确定有几对数是两个都要修改？
要用线段树或是差分，我这里用的线段树
下面讨论的是修改使得 (forall iin[1,frac{n}{2}],a_i+a_{n-i+1}=x) 的情况，其中 (xin[1,2k])（这点 (x) 的限制很显然）

  1. 记录有几对数它们的最小值大于等于 (x)，如果最小值大于等于 (x)，就说明肯定是两个都要修改
  2. 再记录有几对数的最大值加 (k) 小于 (x)，如果大的那个数加 (k)（就是把小的那个数修改成了 (k)）仍然比 (x) 小，也说明必须修改两个

剩下的只改一个就行

所以就是预处理每对数，用线段树区间修改和单点查询，开两个树：(segmax,segmin)

  1. 对于每对数，(segmax) 中 ([1,min(a_i,a_{n-i+1})]) 都加一，这点是对应刚才的
  2. (segmin) 中，([max(a_i,a_{n-i+1}),2k]) 都减一，对应刚才的
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
int t[400006],a[200006];
struct segment_tree{
	struct tr{
		tr *ls,*rs;
		int x,tag;
	}dizhi[800006],*root=&dizhi[0];
	int tot=0;
	inline void pushup(tr *tree){tree->x=tree->ls->x+tree->rs->x;}
	inline void pushdown(tr *tree){
		if(!tree->tag) return;
		tree->ls->x+=tree->tag;tree->rs->x+=tree->tag;
		tree->ls->tag+=tree->tag;tree->rs->tag+=tree->tag;
		tree->tag=0;
	}
	void build(tr *tree,int l,int r){
		if(l==r) return tree->x=tree->tag=0,void();
		int mid=(l+r)>>1;
		tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
		build(tree->ls,l,mid);build(tree->rs,mid+1,r);
		tree->ls->x=tree->ls->tag=tree->rs->x=tree->rs->tag=0;
	}
	int get(tr *tree,int l,int r,int pos){
		if(l==r) return tree->x;
		int mid=(l+r)>>1;pushdown(tree);
		if(pos<=mid) return get(tree->ls,l,mid,pos);
		else return get(tree->rs,mid+1,r,pos);
	}
	void change(tr *tree,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr) return tree->x+=(r-l+1),tree->tag++,void();
		int mid=(l+r)>>1;pushdown(tree);
		if(ql<=mid) change(tree->ls,l,mid,ql,qr);
		if(qr>mid) change(tree->rs,mid+1,r,ql,qr);
		pushup(tree);
	}
}segmin,segmax;
int main(){int T=read();while(T--){
	int n=read(),k=read()*2;
	for(reg int i=1;i<=n;i++) a[i]=read();
	segmin.tot=0;segmin.build(segmin.root,1,k);
	segmax.tot=0;segmax.build(segmax.root,1,k);
	for(reg int i=1;i<=(n>>1);i++){
		t[a[i]+a[n-i+1]]++;
		segmax.change(segmax.root,1,k,1,std::min(a[i],a[n-i+1]));
		int max=std::max(a[i],a[n-i+1])+(k>>1)+1;
		if(max>k) continue;
		segmin.change(segmin.root,1,k,max,k);
	}
	int ans=1e9;
	for(reg int i=1;i<=k;i++){
		int num=segmin.get(segmin.root,1,k,i)+segmax.get(segmax.root,1,k,i);
		ans=std::min(ans,num*2+((n-num*2-t[i]*2)>>1));
	}
	std::printf("%d
",ans);
	for(reg int i=1;i<=n;i++) t[a[i]+a[n-i+1]]=0;
}
	return 0;
}

CF1343E Weights Distributing

传送门
给出一个无向图，给出边权数列 (p_1,p_2,cdots,p_m)，用这个边权数列可以给每条边指定边权
问如何指定边权，能使得 (a ightarrow b ightarrow c) 能找到一条最小花费的路径，求这个最下花费

首先枚举每个点（(u)），让它走的过程是 (a ightarrow u ightarrow b ightarrow u ightarrow c)
显然不论怎么走，都会存在这样的一个 (u) 点
那么可以发现，(u,b) 间的路要走两遍，那肯定把最小的几个边权分给这些点，其次小的分给 (u,a) 和 (u,c) 之间的路

那么就先 bfs 出每个点到 (a,b,c) 分别的距离是多少，为 (p) 数列排序后记一个前缀和 (sum)，然后枚举这个 (u)，计算方式就是：

[2sum(disb(u))+(sum(disa(u)+disb(u)+disc(u))-sum(disb(u))) ]

就得到答案了，记得清空数组的时候，CF 是多测，别用 memset

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
#define N 200006
#define M 400006
int n,m,a,b,c;
int fir[N],nex[M],to[M],tot;
int vis[N];
LL p[M],sum[M];
LL disa[N],disb[N],disc[N];
inline int cmp(int x,int y){return x<y;}
inline void add(int u,int v){
	to[++tot]=v;
	nex[tot]=fir[u];fir[u]=tot;
}
std::queue<int>q;
inline void bfsa(){
	q.push(a);q.push(0);vis[a]=1;
	reg int u,v;
	while(!q.empty()){
		u=q.front();q.pop();
		disa[u]=q.front();q.pop();
		for(reg int i=fir[u];i;i=nex[i]){
			v=to[i];
			if(!vis[v]) q.push(v),q.push(disa[u]+1),vis[v]=1;
		}
	}
}
inline void bfsb(){
	q.push(b);q.push(0);vis[b]=1;
	reg int u,v;
	while(!q.empty()){
		u=q.front();q.pop();
		disb[u]=q.front();q.pop();
		for(reg int i=fir[u];i;i=nex[i]){
			v=to[i];
			if(!vis[v]) q.push(v),q.push(disb[u]+1),vis[v]=1;
		}
	}
}
inline void bfsc(){
	q.push(c);q.push(0);vis[c]=1;
	reg int u,v;
	while(!q.empty()){
		u=q.front();q.pop();
		disc[u]=q.front();q.pop();
		for(reg int i=fir[u];i;i=nex[i]){
			v=to[i];
			if(!vis[v]) q.push(v),q.push(disc[u]+1),vis[v]=1;
		}
	}
}
inline void clear(){
	for(reg int i=1;i<=m;i++) sum[i]=0;
	tot=0;
	for(reg int i=1;i<=n;i++){
		for(reg int j=fir[i];j;){
			to[j]=0;
			int tmp=nex[j];nex[j]=0;
			j=tmp;
		}
		fir[i]=0;
	}
}
int main(){int T=read();while(T--){
	n=read();m=read();a=read();b=read();c=read();
	for(reg int i=1;i<=m;i++) p[i]=read();
	std::sort(p+1,p+1+m,cmp);
	for(reg int i=1;i<=m;i++) sum[i]=sum[i-1]+p[i];
	for(reg int u,v,i=1;i<=m;i++){
		u=read();v=read();
		add(u,v);add(v,u);
	}
	bfsa();for(reg int i=1;i<=n;i++) vis[i]=0;
	bfsb();for(reg int i=1;i<=n;i++) vis[i]=0;
	bfsc();for(reg int i=1;i<=n;i++) vis[i]=0;
	reg LL ans=1e18;
	for(reg int i=1;i<=n;i++){
		if(disa[i]+disb[i]+disc[i]>m) continue;
		ans=std::min(ans,sum[disb[i]]*2+(sum[disb[i]+disa[i]+disc[i]]-sum[disb[i]]));
	}
	std::printf("%lld
",ans);
	clear(); 
}
	return 0;
}

CF1343F Restore the Permutation by Sorted Segments

传送门
比较锻炼思维的一题
要求一个长度为 (n) 的排列：
(forall rin[2,n])，会有一个 (l<r)，给出 (p_l,p_{l+1},cdots,p_r) 的排序后的形式，注意是 ([2,n]) 中每个数都对应一个唯一的 (r)
但并不按照顺序给出，即我们并不知道这些排序后的数列分别是对应哪个 (r)
(p_1,p_2,cdots,p_n) 即为我们要求的排列
数据保证有解，(nle 200)

(n) 特别小，所以这大概是一个 (n^3) 算法，事实上，是 (O(n^3log n)) 的
首先，如果我们知道这些数列分别对应哪个 (r)，那么，对于每个给定的数列 ([l,r+1])，这个 (l) 是啥并不重要，但是我们可以在 ([l,r+1]) 这个数列中找到一个与前 (r) 个数都不相同的数，他就是 (p_{r+1})
此时，对于大部分情况，有一种数学归纳的感觉，如果已经知道了前 (r,r>1) 个数分别是啥（其实想知道第一个数是啥也很简单，(r=1) 时数列包含 (p_1,p_2)，再从后面找到一个只包含 (p_2) 不包含 (p_1) 的数列就能确定了），那也就能推知第 (r+1) 个，这个过程是唯一的，所以我们的答案也必将是唯一的
刚才说对于大部分情况，是因为如果没有一个条件，能让我们区分出前两个数（就是所有区间要么都包含前两个数，要么都不包含），那么答案其实有两种

到此，可以发现，第一个数是啥，是如何求答案的一个较为重要的东西，枚举它，设为 (i)
在把所以给定的数列看作一个集合，对于每个含有 (i) 的集合都把 (i) 删去
然后我们对以下过程重复 (n-1) 次：

  • 设我们当前在重复第 (j-1) 次，也就是现在要确定 (p_j)
  • 如果仅含有一个元素的集合有且只有一个，那么 (p_j) 就是当前这个集合中的那个唯一元素，此时要再把所有含有 (p_j) 的集合删掉 (p_j)
  • 否则，对于当前枚举的 (i)，无解，原因是：
    考虑那个等于 (j) 的 (r) （这句话咋这么别扭），当它前面的，所有的可能出现在这个数列 ([l,r-1]) 中的数都被删掉（这里不包括 (r)，因为他还没开始删），它必然只剩一个
    而对于大于 (j) 的 (r)，它的集合肯定还剩不止一个元素，小于 (j) 的 (r)更好理解，肯定就是已经删光了，不用管
    而如果此时有多个集合只有一个元素，也就是有多个对应的 (r)，那么显然不对（因为题目里说了，([2,n]) 中每个数都对应一个唯一的 (r)），说明出了问题，也就是无解

现在，我们只是构造出了一种可能的答案
还要检验一遍，因为，如果某个集合内元素删除不是连续的（就是说刚才重复 (n-1) 次那些操作的时候，不是连续几次把某个集合所有元素删光），就会出现问题
比如这样一组数据：

7
3 1 2 6
4 1 3 5 6
2 1 2
3 4 5 7
6 1 2 3 4 5 6
3 1 3 6

如果不检验，会输出

1 2 6 3 5 4 7

显然不对
具体的检验方法，我是维护了一个 (index_x) 表示 (x) 这个数在答案排列的第几个，见 check 函数
代码中上文说的集合显然要用 set 维护，总复杂度 (O(n^3log n))

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<set>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
std::set<int>set[206],now[206];
int n;
int ans[206],index[206];//ans 即答案数列，index 是 ans 数列中每个数的索引 
inline void del(int x){
	for(reg int i=1;i<n;i++)
		if(now[i].count(x)) now[i].erase(x);
}
inline int find(){
	int ret=0;
	for(reg int i=1;i<n;i++)if(now[i].size()==1){
		if(ret) return 0;//有多个
		ret=*now[i].begin(); 
	}
	return ret;
}
inline int check(){
//		return 1;
	int tmp[206];
	for(reg int i=1;i<n;i++){
		tmp[0]=0;
		for(reg int j=1;j<=n;j++)if(set[i].count(j)) tmp[++tmp[0]]=index[j];
		std::sort(tmp+1,tmp+1+tmp[0]);
		for(reg int j=2;j<=tmp[0];j++) if(tmp[j]!=tmp[j-1]+1) return 0; 
	}
	return 1;
}
int main(){int T=read();while(T--){
	n=read();
	for(reg int i=1;i<=n;i++) set[i].clear();
	for(reg int i=1,len;i<n;i++){
		len=read();
		while(len--) set[i].insert(read());
	}
	for(reg int i=1;i<=n;i++){//i 枚举的是排列的第一个数 
		for(reg int j=1;j<n;j++) now[j]=set[j];
		del(i);
		ans[1]=i;index[i]=1;
		for(reg int j=2;j<=n;j++){
			int tmp=find();
			if(!tmp) goto FAIL;
			ans[j]=tmp;index[tmp]=j;
			del(tmp);
		}
		if(check()){
//			std::printf("ans:   ");
			for(reg int j=1;j<=n;j++) std::printf("%d ",ans[j]);
			EN;
			break;
		}
		FAIL:;
	}
}
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/suxxsfe/p/12749744.html