qbxtD7 && NOIP提高组考前刷题冲刺班（第七场）

n^15

写的搜索

n²m那种

容斥

ljh:

是7的倍数,减去是2/3/5的倍数,+是6/10/15的倍数,-是30的倍数

my:

至少是2,3,5,7的倍数-至少是2,3,5的倍数

于是我们就可以写一个ljh的容斥,然后相减

最小化?/yun

我们可以维护一个矩阵,行表示a选什么列表示b选什么

然后我们就有某一个数是a,b都选之后这个矩阵只有一个矩阵下三角是满足的

然后相当于我们一个边就代表这里面一个点

把这个[ab]矩阵变成一个点,边变成一个矩阵

那么我们相当于给一个矩阵加1

然后要找一个点使得被最小的矩阵覆盖

可以进行扫描线

my:

额没有那么妙

就是考虑增量,对于一个右端点,用线段树维护所有左端点处答案

然后一路增量过去即可.....就是枚举新点的所有边然后区间修改

注意我们一条边再被经过时要改两次,就是左边被改一次右边被改一次....

时间复杂度都是O(nlogn)

code:


//tsx线段树
//关门弟子
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 4e5 + 7;
int n, m, ccnt;
int home[MAXN], nxt[MAXN], to[MAXN];

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

struct rec {
	int adt;
	ll Mx;
	rec(int ADT = 0, ll Mix = 0): adt(ADT), Mx(Mix) {};
} tr[MAXN];

rec operator+(const rec &x, const rec &y) {
	rec nw = rec();
	nw.adt = x.adt + y.adt;
	nw.Mx = x.Mx + y.adt;
	return nw;
}

inline void calc(int k, int v) {
	tr[k].Mx += v;
	tr[k].adt += v;
	return;
}

inline void update(int k) {
	tr[k].Mx = min(tr[k << 1].Mx, tr[k << 1 | 1].Mx);
	return;
}

inline void pushdown(int k) {
	if(tr[k].adt) {
		calc(k << 1, tr[k].adt);
		calc(k << 1 | 1, tr[k].adt);
		tr[k].adt = 0;
	}
}

///jk
inline void add(int k, int l, int r, int L, int R, rec jk) {
	// printf("add : %d %d %d %d %d %lld V is %d\n", k, l, r, L, R, tr[k].Mx, jk.adt);
	if(L <= l && r <= R) {
		calc(k, jk.adt);
		return ;
	}
	pushdown(k);
	int mid = (l + r) >> 1;
	if(L <= mid)add(k << 1, l, mid, L, R, jk);
	if(R > mid)add(k << 1 | 1, mid + 1, r, L, R, jk);
	update(k);
	return;
}

inline int qry(int k, int l, int r, int L, int R) {
	if(L <= l && r <= R) {
		// printf("qry  : %d %d %lld\n", l, r, tr[k].Mx);
		return tr[k].Mx;
	}
	pushdown(k);
	int mid = (l + r) >> 1;
	if(R <= mid)return qry(k << 1, l, mid, L, R);
	else if(L > mid)return qry(k << 1 | 1, mid + 1, r, L, R);
	else return min(qry(k << 1, l, mid, L, R), qry(k << 1 | 1, mid + 1, r, L, R));
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	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);
	}
	int ans = 1e9;
	for(int u = 2; u < n; ++u) {
		// printf("now is :%lld \n", u);
		for(int i = home[u]; i; i = nxt[i]) {
			int v = to[i];
			// printf("vis is %d\n", v);
			if(v > u || v == 1) {
				add(1, 1, n, 2, u, rec(1, 0));
			} else {
				add(1, 1, n, v + 1, u, rec(1, 0));
				add(1, 1, n, 2, v, rec(-1, 0));
			}//如果包括了他们俩,就-1
			//显然左端点1不能成为答案吧
		}
		// printf("%d ?\n", qry(1, 1, n, 2, u));
		ans = min(ans, qry(1, 1, n, 2, u));//查询区间答案???
	}
	printf("%d\n", ans);
	return 0;
}

首先直接dp要记录这个轮数

妈的不要

所以说我们发现这个转移矩阵是个循环矩阵

所以说我们就可以循环矩阵快速幂( $O(n^2log)$ ,qc的做法)

但是写出转移式子就发现可以倍增做这个事情

$f_{i,j}$ 表示2^i步,走j步的方案数

然后,,,,,我们就能 $O(n^2logn)$ 了...

code:


//考虑f_{i,j}表示前2^i轮,最后0号在j的方案数(走了j步)
//转移考虑两个拼起来的时候,对于位置x,我们有一个类似卷积的东西
//就是类似于走了y步,再去走k步,满足(x+k)%(n-1)==x
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 2000;
const int MAXlog = 40;
int n, m, t, d;
int a[MAXN];
int f[MAXlog][MAXN], g[MAXN], dp[MAXN];

inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
}

inline void solve() {
	for(int i = 1; i <= m; ++i)f[0][a[i]] = 1;
	for(int i = 1; i <= 30; ++i) {
		for(int j = 0; j < n; ++j) {
			for(int k = 0; k < n; ++k) {
				add(f[i][(j + k) % n], 1ll * f[i - 1][k]*f[i - 1][j] % P);
			}
		}
	}
	//走0步,一步都不算
	g[0] = 1;
	for(int i = 0; i <= 30; ++i) {
		if(t >> i & 1) {
			// printf("%d ?\n", i);
			for(int j = 0; j < n; ++j) {
				for(int k = 0; k < n; ++k) {
					// printf("%d %d %d %d\n", j, k, f[i][k], g[j]);
					add(dp[(j + k) % n], 1ll * g[j]*f[i][k] % P);
				}
			}
			for(int j = 0; j < n; ++j)g[j] = dp[j], dp[j] = 0;
		}
	}
	int ans = 0;
	// for(int i = 0; i < n; ++i)printf("%d ", g[i]);
	for(int i = 0; i < n; i += d)add(ans, g[i]);
	printf("%d\n", ans);
	return ;
}

int main() {
	scanf("%d%d%d%d", &n, &m, &t, &d);
	for(int i = 1; i <= m; ++i)scanf("%d", &a[i]);
	solve();
	return 0;
}
/*

9 10 96318817 5
29086
14551
3546
12089
18582
10244
23380
4102
31676
31273


*/

全局最小割

钦定一个s,t

$a_1$ 是随便一个

然后选一个点i,然后使得i和前面的所有点连的边数最大

然后会发现这样能构造出一个序列

最后删掉 $a_n$ 所有连边即可

但是还没有考虑两个点是合并的

也很简单,我们把两个点merge成一个点,然后再做上述过程

随后我们接着随便选,把剩下n-1个点合乘一个,所有过程答案求最小值即可

对于一个图,随机logn棵生成树,这log棵生成树不能有共同的边

随机G'有 $nlog^2n$ 条边

然后这些生成树中有一个生成树

最小的分割方案是会分成三份

所以说我们可以选两条边断掉,然后枚举其中一条用数据结构优化另一条的枚举

$mlog^3n$

区间的代价为这一段的出现数字种类的平方

然后问总划分方案使得划分代价最小

首先都分成一段是可能优的答案为n

然后你会发现这个东西啊naive

因为平方上升,所以说我们直接枚举i前根号个不同的数字即可..... $f_i=f_j+cst(i,j)$

这个预处理可以动脑子

平面最近点对

随便按横坐标劈开

然后分治左右得到答案d

然后中间合并的话.....

你会发现答案一定在x-d和x+d之间的范围内

然后把那些点找出来,按照纵坐标排序

考虑其中某一个点,向前后枚举几个点纵坐标距离差就已经超过d了...就停止

会发现这里我们只需要枚举几次就能超越d

然后又会发现这个三角形咋办啊

枚举一个,剩下的都在附近??

从中间分开,算左右答案

现在我们只需要看x-d和x+d的

纵坐标排序

剩下两个点只能在y+d范围

然后感觉一下,这个点不会很多

我们先枚举第一个,再枚举第二个并用第一个第二个距离再减第三个的纵坐标范围

n个点,m条边的有向图

然后在i点选操作j有得分 $c_{i,j}$

下一秒所在的点可能在这个点指出去的某个点

有 $p_{i,j,k}$ 表示i这个点做操作j到点k的概率

保证和为1

最小化t=0时的得分期望

1e-6误差

$f_{i}$ 表示t=0在i的最小得分

初始化....f=0, $f^{(k)}_{i}$ 表示第k次计算是 $f_i$ 的值

每一步

f^{(k)}_{i}=min_a{C_{i,a}+\frac 1 2*\sum_j {p_{i,a,j}*f^{(k-1)}_j}}

然后多算几轮,知道快超时就输出,使得误差很小

(差不多三四十次就好了....)

然后这里老师数学分析了一下,证明这个误差确实不会很大

牛顿迭代

找到某个点,然后搞一个直线(导数)

从直线出发求交点横坐标然后带入再求导

再求那个导数的交点横坐标......

一直迭代直到找到0点

$loglogn$

P4055 [JSOI2009]游戏

显然是二分图染色后跑最大匹配,非必须点就是可行的答案

然后我们可以从不在最大匹配的(一定是非匹配点)点集中向最大匹配点走沿着匹配边,和i同一侧的点都是非必须的

因为至少有一种方案是选上i

SP11469 SUBSET - Balanced Cow Subsets

先除半,然后左边有10个点,右边有10个

我们左边的和为a,右边的和为b,左边另一堆数和为c,右边另一堆数和为d

a+b=c+d

a-c=d-b

相当于我们左边枚举子集得到所有可能的差

然后右边也一样做做

利用map来匹配一下!

复杂度 $O(3^{\frac n 2})$

夏晓光(loveJY)的博客

qbxtD7 && NOIP提高组考前刷题冲刺班（第七场）

P4049 [JSOI2007]合金