当前位置：网站首页>2022.7.27 Selected lectures on good topics

2022.7.27 Selected lectures on good topics

2022-08-01 05:31:00 【lAWTYl】

T1 数学计算

传送门：[TJOI2018]数学计算

$t a g$ ：Line segment tree maintenance sequence of operations

分析

It didn't seem that difficult at first.,Can't you just simulate it directly?,Why is blue？

仔细一想,哇塞,这数据范围,Are you going to go high-end?.To work it out,哇塞,Directly simulating the high-precision space will explode..So it's unrealistic to count it directly..

再想想,How about taking the model while calculating?,哇塞,There is a division to calculate the inverse element.looking at the data,哇塞,Modulus is not a prime number.Then it becomes quite troublesome to calculate the inverse（And also special judgment）.

Then we obviously can't be directly simulate the positive solutions,So we consider a more violent simulation.We maintain a sequence of operations,then if the operation $1$ I'll always go on.Every time an operation is encountered $2$ ,just delete the number in the previous sequence of operations,Then do the prefix product again from scratch.

啊,这样一来,Let's consider how we can optimize this practice..Think about the violence just now,肯定有很多重复计算,那么怎么避免呢.save the previous count？Still a lot of useless,再想想,维护一个数列,需要两个操作,The first is to change one of the numbers to $1$ （is the operation in the title $2$ ）,Another is to add a number at the end（操作 $1$ ）.Also need to check the prefix product from beginning to end,再抽象一点：支持单点修改,区间查询：线段树.

那么这样,We can maintain a sequence of operations using the segment tree,每当操作 $1$ is added at the end of the sequence with a $m$ ,每当操作 $2$ 的时候就把 $p os$ The number of the location is changed to $1$ ,In this way, the output prefix product is completed after each operation.

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
#define MAXN 100100
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int T = 0;
int q = 0; int M = 0;
int a[MAXN] = {
     0 };
struct Tnode{
    
	int dat;
	int l, r;
}t[MAXN << 5];

inline void up(int p) {
     t[p].dat = (t[ls(p)].dat * t[rs(p)].dat % M) % M; }

void build(int p, int l, int r){
    
	t[p].l = l, t[p].r = r;
	if(l == r) {
     t[p].dat = 1; return; }
	int mid = (l + r) >> 1;
	build(ls(p), l, mid); build(rs(p), mid + 1, r);
	up(p);
}

void update(int p, int idx, int val){
    
	if(t[p].l == t[p].r) {
     t[p].dat = val; return; }
	int mid = (t[p].l + t[p].r) >> 1;
	if(idx <= mid) update(ls(p), idx, val);
	else update(rs(p), idx, val);
	up(p);
}

int query(int p, int l, int r){
    
	if(l <= t[p].l and t[p].r <= r) return t[p].dat;
	up(p);
	int mid = (t[p].l + t[p].r) >> 1, ans = 0;
	if(l <= mid) ans = (ans * query(ls(p), l, r) % M) % M;
	if(r > mid)  ans = (ans * query(rs(p), l, r) % M) % M;
	return ans;
}

signed main(){
    
	T = in;
	while(T--){
    
		q = in, M = in; build(1, 1, q);
		for(int i = 1; i <= q; i++){
    
			int op = in; a[i] = in;
			if(op == 1){
    
				update(1, i, a[i]);
				cout << query(1, 1, q) << '\n';
			}
			else{
    
				update(1, a[i], 1);
				cout << query(1, 1, q) << '\n';
			}
		}
	}
	return 0;
}

T2 跑步

[NOI Online #1 入门组] 跑步

$t a g$ ：mysterious block？？根号分治？？~~or 数学？？？~~

分析

The problem is simply that let us use a non-strictly monotonically decreasing sequence to split $n$ ,问有多少种分法.

The first thing I saw was a backpack（完全背包）, $O(n^2)$ ,看看,已经 $70 pt s$ 了,~~feel left 30pts Price so low,why don't you do itqwq~~.记前 $i$ 种数和为 $j$ The plan is $f_{i, j}$ ,那么：

$f_{i, j} = f_{i, j - 1} + f_{i - 1, j }$

初始化 $f_{0, 0} = 1$ .Scroll the numbers again,甚至可以拿 $80 pt s$ .

#include<bits/stdc++.h>
using namespace std;
#define MAXN 101

int f[MAXN] = {
     0 };
int n = 0; int p = 0;

int main(){
    
	cin >> n >> p;
	f[0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = i; j <= n; j++)
			f[j] = (f[j - i] + f[j]) % p;
	cout << f[n] << '\n';
	return 0;
}

But we still need to the pursuit of truth,So I think about optimization.

优化这个 $d p$ Obviously it can't start with the transfer,已经是 $O (1)$ It's optimized for loneliness.So I can only count from state.This brings us to the point of the question,That is, divide and conquer by root sign.

We divide all numbers into two parts,part is numeric $\sqrt n$ 的,另一部分是 $\geq \sqrt n$ 的.Then we consider calculating the two parts separately and then merging them together.

数值 $\sqrt n$ 的部分,Figures on the number of species is here $\sqrt n$ ,So if you follow the violent approach above $d p$ 的话 $i$ The enumeration scope becomes $\sim \sqrt n$ ,This is an acceptable range,复杂度就是 $O(n\sqrt n)$ .
数值 $\geq \sqrt n$ 的部分,This part number clearly the number of optional number to $\leq \sqrt n$ ,Because this part of all values $\geq \sqrt n$ ,If the number is also $\sqrt n$ ,Then it must add up to more than $n$ 了.So if we want to reduce the number of states as in the previous case we have to do it another way $d p$ 了.
我们令 $g_{i, j}$ 表示选了 $i$ 个数,和为 $j$ 的方案数,In this way, it is possible to use a number not greater than $\sqrt n$ this nature $d p$ 了.
Now it's time to think about how to do this $d p$ 了,We consider how to construct such a sequence.We consider two operations,The first is to add a $\sqrt n$ （add min）,The other is to add all the numbers already in the sequence $1$ .These two operations are performed alternately（Of course, you can also perform an operation many times in a row.）,Will be able to create a non strictly monotone increasing and the minimum is $\sqrt n$ 的数列,于是我们就用 $d p$ to perform these two operations：
$\begin{aligned} 加入 \sqrt n ： & g_{i, j} +=g_{i - 1, j - \sqrt n} \\ 所有数加1 ： & g_{i, j} += g_{i, j - i} \end{aligned}$
这样一来,This completes the transfer we need.

In the end, it's a relatively simple backpack merger..

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100100
#define MAXM 505

int n = 0; int p = 0;
int f[MAXN] = {
     0 };
int g[MAXM][MAXN] = {
     0 };

int main(){
    
	cin >> n >> p; int ans = 0;
	int m = sqrt(n) + 1;
	f[0] = 1;
	for(int i = 1; i < m; i++)
		for(int j = i; j <= n; j++)
			f[j] = (f[j - i] + f[j]) % p;
	g[0][0] = 1;
	for(int i = 1; i <= m; i++)
		for(int j = i; j <= n; j++){
    
			g[i][j] = (g[i][j] + g[i][j - i]) % p;
			if(j >= m) g[i][j] = (g[i][j] + g[i - 1][j - m]) % p;
		}
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++)
			g[0][j] = (g[0][j] + g[i][j]) % p;
	for(int i = 0; i <= n; i++)
		ans = (ans + 1ll * g[0][i] * f[n - i] % p) % p;
	cout << ans << '\n';
	return 0;
}

T3 表达式求值

传送门：P7324 [WC2021] 表达式求值

I feel like I don't really understand…

T4 Poor Turkeys

传送门：AT2389 [AGC016E] Poor Turkeys

$t a g$ ：时光倒流？？？

分析

If you are doing it, you need to meet a bunch of constraints to judge $(i, j)$ 合不合法,This looks very difficult to do,So we consider the reverse.On the other hand, it is only necessary to satisfy $(i, j)$ Judging whether the previous pile of things is legal or not under the condition that they all survive,It will look simpler.

So we consider if only let $i$ What are the conditions for survival.We trace back from the last instruction,If an instruction is encountered and $i$ 无关,比如一个 $(x, y)$ ,Then these two chickens can be killed casually,Because the life and death of the two of them will not affect $i$ .But if you encounter an instruction that is $(i, j)$ ,Here, we can't kill $i$ ,只能杀 $j$ .但是 $j$ It may have been sent at some previous step,So we're not only going to click away at this step $j$ ,Also make sure that in the previous instruction $j$ won't get snapped.Then it is equivalent to requiring in the previous instruction $i, j$ to survive.

So we can think of maintaining a “protection set” $S_i$ ,To make the $i$ 最终存活下来,In the first several steps need to be protected in the collection of chicken,我们注意到,protect except $i$ The chickens outside are all there to kill it at some point,So the elements in the set can be divided into $i$ 和除了 $i$ Elements of two parts.

同理,我们从 $j$ Going up can also maintain a “protection set” $S_j$ ,如果我们要 $(i, j)$ 都存活,那么我们就要求 $S_i\bigcap S_j = \Phi$ .

这样一来,我们就能 $O (nm)$ deal with all the chickens “protection set”,然后 $O(n^2)$ ,枚举所有点对,Then each point of intersection judgment once done.

代码

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 404
#define MAXM 100100

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	} 
	return x;
}

int n = 0; int m = 0;
struct Trequ{
    
	int x, y;
}req[MAXM];
bitset<MAXN> s[MAXN];
bool flag[MAXN] = {
     0 };

int main(){
    
	n = in; m = in;
	for(int i = 1; i <= m; i++) req[i].x = in, req[i].y = in;
	for(int i = 1; i <= n; i++) s[i][i] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = m; j >= 1; j--){
    
			int x = req[j].x, y = req[j].y;
			if(s[i][x] && s[i][y]) {
     flag[i] = 1; break; }
			if(s[i][x] || s[i][y]) s[i][x] = s[i][y] = 1;
		}
	int ans = 0;
	for(int i = 1; i <= n; i++){
    
		if(flag[i]) continue;
		for(int j = i + 1; j <= n; j++){
    
			if(flag[j]) continue;
			if((s[i] & s[j]).count() == 0) ans++;
		}
	}
	cout << ans << '\n'; 
	return 0;
}

T5 Both Sides Merger

传送门：AT3944 [ARC092C] Both Sides Merger

$t a g$ ：Consider the source of the answer

分析

Don't panic if encounter this kind of operation,Play with a few examples to find the pattern.这里就不举例子了,我们可以发现,在这些点中,Contributing to the answer issubsequence on odd or even bits. that is either on odd bits,or on even digits,It is impossible to contribute to the answer in both odd and even positions at the same time.

这样一来,We turn the problem into a maximum subsequence problem,Run it once for odd and even bits,然后再取 $ma x$ 就做完了.

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
#define MAXN 1010
#define INFI 0x3f3f3f3f

inline int read(){
    
	int x = 0; int f = 1; char c = getchar();
	while(c < '0' or c > '9'){
    
		if(c == '-') f = -1; c = getchar();
	}
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	} 
	return f * x;
}

int a[MAXN] = {
     0 };
int n = 0; int m = 0;
int ans1 = 0, ans2 = 0;
int us1[MAXN], us2[MAXN];

int tot = 0;
int c[MAXN] = {
     0 };
int from[MAXN] = {
     0 };
void solve(int cnt, int us[]){
    
// for(int i = 1; i <= n; i++) cout << us[i] << ' '; puts("");
	int temp = 0;
	for(int i = 1; i <= n; i++)
		if(us[i]) from[i] = temp, temp = i;
// for(int i = 1; i <= n; i++) cout << from[i] << ' '; puts("");
	int l = 1, r = cnt;
	for(int i = 1; i <= n; i++) 
		if(!us[i]) c[++tot] = 1, cnt--, l++;
		else break;
	for(int i = n; i >= 1; i--)
		if(!us[i]) c[++tot] = cnt, cnt--, r--;
		else break;
// for(int i = 1; i <= tot; i++) cout << c[i] << ' '; puts("");
	int ll = l, rr = r;
	for(int i = l; i <= r; i++){
    
// printf("i = %d\n", i);
		if(!from[i]) continue;
// puts(" in");
		int x = i - ll + 1, y = from[i] - ll + 1;
// printf(" x = %d y = %d\n", x, y);
		while(x != y){
    
			int mid = (x + y) >> 1;
			c[++tot] = mid; x -= 2, ll += 2;
// printf("mid = %d\n", mid);
		}
	}
	cout << tot << '\n';
	for(int i = 1; i <= tot; i++) cout << c[i] << '\n';
}

signed main(){
    
	n = in; int ans = -INFI, f = 0, all = 1;
	for(int i = 1; i <= n; i++) {
     a[i] = in; if(a[i] > 0) all = 0; }
	if(all == 1){
    
		int ff = 0;
		ans1 = -INFI, ans2 = -INFI;
		for(int i = 1; i <= n; i += 2)
			if(a[i] > ans1) ans1 = a[i], ff = i;
		us1[ff] = 1;
		for(int i = 2; i <= n; i += 2)
			if(a[i] > ans2) ans2 = a[i], ff = i;
		us2[ff] = 1;
	}
	else{
    
		ans1 = 0, ans2 = 0;
		for(int i = 1; i <= n; i += 2)
			if(a[i] > 0) ans1 += a[i], us1[i] = 1;
		for(int i = 2; i <= n; i += 2)
			if(a[i] > 0) ans2 += a[i], us2[i] = 1;
	}
	if(ans1 > ans2) ans = ans1, f = 1;
	else ans = ans2, f = 2;
	cout << ans << '\n';
	if(f == 1) solve(n, us1);
	else if(f == 2) solve(n, us2);
	return 0;
}