2020/10/21最近几天做的题qwq

那些在我记忆里留不下印象的

ARC105B

给定 $n$ 个数 $ai$ ，然后执行以下操作：

令 $X$ 表示其中的最大值， $x$ 表示其中的最小值。

如果 $X=x$ ，那么终止操作，否则将所有 $ai=X$ 的 $ai$ 替换为 $X−x$

输出终止操作时 $a1$ 的权值。

这个操作其实就是辗转相减。。。而且是所有数一起做。。。。

所以求个n个数的gcd即可

ARC105C

有 $n$
只骆驼要过桥，第 $i$ 只骆驼重量为 $wi$
。

桥分为 $m$
个部分，每个部分长度为 $li$ 容重为 $vi$

。

你需要规定骆驼过桥的顺序和相邻两头骆驼之间的距离，使得桥不倒塌的情况下最小化第一只骆驼和最后一只骆驼之间的距离。

2≤n≤8,1≤m≤105,1≤wi,li,vi≤108

n很小可以考虑阶乘枚举，然后快速 $check$ 答案

考虑传递闭包，一个桥长为l,称重为w，对于区间 $[l,r]$ 如果他们的和大于 $w$ ,那么彼此间长度就要大于 $l$

而且同样的，我们可以对于一段区间，用数据结构找到限制最严格的那个l

所以从l,r连一下这样的n条边

最后求一个1，n的最长路就能得到答案qwq

ARC105D

给定 $N$ 个背包，第 $i$ 个背包有 $ai$ 个硬币。初始有 $N$ 个空盘子。

当至少有一个背包不为空的时候，你可以将一个背包的所有硬币移动到一个盘子上。

当所有背包都为空的时候，你可以选择一个非空盘子，然后将其中至少一个硬币移走。

无法操作者输， $T$ 组数据，判定每组数据先手和后手谁必胜。

T≤10^5,N≤10^5,1≤ai≤10^9,∑N≤2×10^5

嗯嗯嗯可以nim游戏第二部分

然后第一部分我自闭了

ljh：只要能有一个数大于sum/2我就一定赢了

所以我们可以发现，如果我是后手而且有奇数个背包，就是后手一定能使一个数大于sum/2

因为先手有n/2+1个，后手有n/2-1个数操作

先手放下一个数后，后手选当前最大的n/2-1个数在那个数上面就好了

最后一定能凑出一个n/2+1个数的和的盘子

对于偶数，后手想要等于0

那么仔细想想这个过程，n=4先手可以决定第2,4大的数，后手可以决定第1,3大的数

那么如果1=2且2=4时就好了qwq后手一定可以等价操作

如果排序后奇数rank=偶数rank则先手必败，否则必胜

做完了

CF643G Choosing Ads

国家集训队作业试题

摩尔投票法拓展！

因为这个方法求绝对正数空间复杂度O1

当 $p>50$ 时就是绝对众数，是摩尔投票

$p<50$ 考虑如果我们要求多个众数(前k大，我们就都记录下来！假设p=20

然后如果允许暴力，做法就是记录5个数，然后如果有这五个数中的一个就加入其中某个数hp+1，如果五个数没满就放入其中，否则就让所有数的hp-1，如果这样hp减为0了就清掉这个位置

$major[1,5],cnt[1,5]$ 表示1,5最多的出现的数以及他们剩余数量

然后考虑合并区间

如果有相同的数，直接merge
剩下的数我们选取出现最多的那5个，(注意是两边求和后)然后剩下的就成为牺牲品让他们去hp--,注意如果我们最小值被剃掉了也要去做一次

keycode:

	inline Node operator + (const Node &o) const {
		Node res = o;
		for(Rint i = 0;i < num;i ++){
			bool flag = false;
			for(Rint j = 0;j < res.num && !flag;j ++)
				if(a[i] == res.a[j]){
					res.b[j] += b[i];
					flag = true;
				}
			if(flag) continue;
			if(res.num < p){res.a[res.num] = a[i]; res.b[res.num] = b[i]; ++ res.num; continue;}
			int k = 0;
			for(Rint j = 1;j < res.num;j ++)
				if(res.b[j] < res.b[k]) k = j;
			if(b[i] < res.b[k])
				for(Rint j = 0;j < res.num;j ++) res.b[j] -= b[i];
			else {
				int tmp = res.b[k];
				res.a[k] = a[i]; res.b[k] = b[i];
				for(Rint j = 0;j < res.num;j ++) res.b[j] -= tmp;
			}
		}
		return res;
	}

CF679E Bear and Bad Powers of 42

考虑用线段树记录每个数和最近比他大的42次幂的差值，是个负值

然后怎么维护呢？其实可以发现，不管怎么样一个数最多进位 $log_{42}V$
次

这个数很小，所以会发现如果我们区间加使得最大值大于0就重构其中某个区间

实现的时候不能重构一整颗树，只能递归那些最大值大于0的！！

复杂度是合法的，因为每个数最多重构log次，所以是 $O(nlog^2)$

还有一个区间推平。。。ODT一波吧。。。没办法啊

好像ODT写法还有些问题我去爬爬爬一下？

做法就是考虑这题时间本质是什么

E(T)=[t_2<t_1]+[t_3<t_1]...+[t_n<t_1]+1

然后期望的线性性

$E([t_2<t_1])$

这个东西就是考虑2什么时候在1前面，为 $\frac{a_2}{a_1+a_2}$

否则贡献为0, $...*0$ 就不写了

那么答案也就显然了

P3232 [HNOI2013]游走

也很显然吧。。。因为有绿豆蛙的归宿那道题

考虑算一个点的期望经过次数，这个可能推起来要一点脑子

因为我们一旦经过一个这个点邻居之后就有一定概率走回这个点

f_1=\sum_j{f_j * 1/degree(j)}+1

f_i=\sum_j{f_j*1/degree(j)}

是 $degree(j)....$

然后高斯消元求出所有期望经过次数

那么一条边期望经过次数就是起点 $*1/degree$ +终点 $*1/degree$

这个最大的分配最小的

code:


#include<bits/stdc++.h>
#define db double
using namespace std;
const int MAXN=505;
const int MAXM=3e5+7;
struct EDGE {
	int x,y;
	db ex;
	bool operator<(const EDGE &xx)const {
		return ex<xx.ex;
	}
} e[MAXM];
int n,m;
int ccnt,home[MAXN],nxt[MAXM],to[MAXM],in[MAXN];
inline void ct(int x,int y) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
	in[y]++;
}
const db eps=1e-7;
struct MAT {
	db a[MAXN][MAXN];
	inline void gauss() {
		for(int i=1; i<=n; ++i) {
			if(fabs(a[i][i])<eps) {
				for(int j=1; j<=n; ++j) {
					if(fabs(a[j][i])>eps) {
						for(int k=1; k<=n+1; ++k) {
							swap(a[i][k],a[j][k]);
						}
						break;
					}
				}
			}//交换得到合法矩阵！
			db k=a[i][i];
			for(int j=1; j<=n+1; ++j) {
				a[i][j]/=k;
			}//同时除以下？
			for(int j=1; j<=n; ++j) {
				if(i==j)continue;
				db kk=a[j][i];//考虑我们要减去几倍qwq
				for(int k=1; k<=n+1; ++k) {
					a[j][k]-=kk*a[i][k];///kk
				}
			}
		}
	}
} mt;

inline void output() {
	puts("Here is output matric!");
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n+1; ++j) {
			printf("%lf ",mt.a[i][j]);
		}
		puts("");
	}
	puts("");
}

inline void init() {

	for(int u=1; u<n; ++u) {
		for(int i=home[u]; i; i=nxt[i]) {
			int v=to[i];
			mt.a[u][v]=1.0/in[v];
		}
		mt.a[u][u]=-1;
	}
	mt.a[1][n+1]=-1;
	mt.a[n][n]=1;
	mt.a[n][n+1]=0;
//	output();
}



int main() {
	scanf("%d%d",&n,&m);
	for(int i=1,x,y; i<=m; ++i) {
		scanf("%d%d",&x,&y);
		ct(x,y);
		ct(y,x);
		e[i].x=x;
		e[i].y=y;
	}
	init();
	mt.gauss();
//	output();
	for(int i=1; i<=m; ++i) {
		e[i].ex=mt.a[e[i].x][n+1]*1.0/in[e[i].x] + mt.a[e[i].y][n+1]*1.0/in[e[i].y];
//		printf("%d %d %lf\n",e[i].x,e[i].y,e[i].ex);
	}
	sort(e+1,e+m+1);
	db ans=0;
	for(int i=1; i<=m; ++i) {
		ans+=e[i].ex*(m-i+1);
	}
	printf("%.3lf\n",ans);
	return 0;
}

CF1369E DeadLee

一种构造思路吧。。。

一开始我想的是选择值最小的当值相同的时候我们选择上面人数最大的菜开始吃，因为这样能尽可能减少吃两道菜的人？？

但是正着构造显然不对吧

反着构造！！

首先一定存在一个菜是不用担心可以随便吃的，也就是所有喜欢的人都选了这个菜还能吃不完，把这个菜加入队列

然后我们取出队头，可以发现，既然这个菜已经是吃不完的了，那么对于一个人，他喜欢的另一道菜就可以尽可能的少吃了，让另一道菜的剩余含量++，然后把这个人排到队列尾端即可

此时可能又会有新菜剩余含量大于等于0，再把它加入队列循环做即可

code：


#include<iostream>
using namespace std;
const int MAXN=4e5+7;
int n,m,a[MAXN],ccnt,que[MAXN],vis[MAXN],vvis[MAXN],ans[MAXN],tot;
int nxt[MAXN],home[MAXN],to[MAXN],id[MAXN];
inline void ct(int x,int y,int z) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
	id[ccnt]=z;
	return ;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i) {
		scanf("%d",&a[i]);
	}
	for(int i=1,x,y; i<=m; ++i) {
		scanf("%d%d",&x,&y);
		a[x]--;
		a[y]--;
		ct(x,y,i);
		ct(y,x,i);
	}
	int h=0,t=0;
	for(int i=1; i<=n; ++i) {
		if(a[i]>=0) {
			que[++t]=i;
			vis[i]++;
		}
	}
	while(h<=t) {
		int u=que[h];
		++h;
		for(int i=home[u]; i; i=nxt[i]) {
			int v=to[i];
			a[v]++;
			if(!vvis[id[i]]) {
				ans[++tot]=id[i];
				vvis[id[i]]=1;
			}
			if(a[v]>=0 && !vis[v]) {
				que[++t]=v;
				vis[v]=1;
			}
		}
	}
	if(tot==m) {
		puts("ALIVE");
		for(int i=tot; i>=1; --i) {
			printf("%d ",ans[i]);
		}
	} else {
		puts("DEAD");
	}
	return 0;
}

P3643 [APIO2016]划艇

计数计数计数计数计数计数计数计数计数计数计数

首先我们可以考虑离散化，然后得到 $f_{i,j}$ 表示考虑了前i个数第i个数分在第j段的方案数

然后转移就是枚举一个 $p,k$ ，表示我们把一些数分到第i段

f_{i,j} = \sum_{p<j,k<i}{f_{k,j}\binom{l+m-1}{m}}

m是有多少人，l是值域大小

至于正确性。。其实就是插板法。。。

Lemma. 从区间 $[0,L]$ 中取 $n$ 个数，要求所有非零数严格递增，则方案数为 $\binom{L+n}{n}$ 。

所以这个计数是正确的。。。

而直接做其实复杂度时 $O(n^4)$

所以要预处理组合数已经前缀和优化一下第二维。。。

有一道势能函数期望题。。。单独分一片出来吧？

http://acm.hdu.edu.cn/showproblem.php?pid=5036

先建图

其实不太显然的是这个题是和树上没太多区别的，要考虑每个点的期望贡献次数

就是看有多少个点到达他

那么我们就是可以做一个传递闭包，得到每个点有多少点可达，然后直接搞就好了。。。

如果缩点会不会有问题呢？。。。可能这个E？？？

P4550 收集邮票

这能不会我也是服了

首先期望dp有一个很不错的套路：反向设状态

$f_i$ 表示已经有了i种数，然后凑齐i到n期望次数是什么

$g_i$ 表示已经有了i种数，然后凑齐i到n期望花费是什么

那么我们就能直接dp了。。。

f_i=\frac i n f_i + 1 + \frac {n-i} n f_{i+1}

有了这个期望次数，会发现这个花费其实和次数是相关的。。。

也就是说我们可以用f更新g

g_i=\frac i n (g_i + f_i + 1) + \frac {n-i} n (g_{i+1} + f_{i+1} +1)

可能因为显然的是我们不知道 $1~i$ 的期望花费怎么推到i+1的，这个和csp的那道题相似吧qwq

嗯嗯额这个好像在图上高斯消元的时候也有用到

另外这个分开设的好像很妙啊！就是设一个期望花费一个期望次数然后相互贡献！

夏晓光(loveJY)的博客

CF1373F Network Coverage