线性鸡

#include<bits/stdc++.h>
using namespace std;
const int maxn = 55;
#define int long long
int n, b[maxn] = {0};
void insert(int p){
	for(int i = 51; i >= 0; i--){
		if((p >> i) & 1){
			if(!b[i]){
				b[i] = p;
				return;
			}
			else p ^= b[i];
		}
	}
}
signed main(){
	cin >> n;
	for(int i = 1, p; i <= n; i++){
		cin >> p;
		insert(p);
	}
//	for(int i = 51; i >= 0; i--) cout << b[i] << endl;
	int num = 0;
	for(int i = 51; i >= 0; i--){
		num = max(num, num ^ b[i]);
//		cout << i << " " << num << endl;
	}
	cout << num;
	return 0;
}

https://www.luogu.com.cn/paste/yzikg4q9

G. 着色方案

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod  = 1e9 + 7;
int k, A[6], dp[16][16][16][16][16][6];
bool vis[16][16][16][16][16][6];
int dfs(int a, int b, int c, int d, int e, int x){
   if(vis[a][b][c][d][e][x]) return dp[a][b][c][d][e][x];
   vis[a][b][c][d][e][x] = true;
   if(!a && !b && !c && !d && !e) return dp[a][b][c][d][e][x] = 1;
   int ans = 0;
   if(a) ans = (ans + (a - (x == 2)) * dfs(a - 1, b, c, d, e, 1)) % mod;
   if(b) ans = (ans + (b - (x == 3)) * dfs(a + 1, b - 1, c, d, e, 2)) % mod;
   if(c) ans = (ans + (c - (x == 4)) * dfs(a, b + 1, c - 1, d, e, 3)) % mod;
   if(d) ans = (ans + (d - (x == 5)) * dfs(a, b, c + 1, d - 1, e, 4)) % mod;
   if(e) ans = (ans + e * dfs(a, b, c, d + 1, e - 1, 5)) % mod;
   return dp[a][b][c][d][e][x] = ans;
}
signed main(){
   cin >> k;
   for(int i = 1, x; i <= k; i++){
   	cin >> x;
   	A[x] += 1;
   }
   dfs(A[1], A[2], A[3], A[4], A[5], 0);
   cout << dp[A[1]][A[2]][A[3]][A[4]][A[5]][0];
   return 0;
}

Bad Hair Day 乱发节

#include<bits/stdc++.h>
using namespace std;
const int maxn = 8e4 + 5;
int n, a[maxn];
long long ans = 0;
int s[maxn];
int top = 0;
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++){
		if(a[i] < s[top]){
			ans += top;
		}else{
			while(a[i] >= s[top] && top) top--;
			ans += top;
		}
		s[++top] = a[i];
	}
	cout << ans;
	return 0;
}

滑动窗口

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
struct node{
	int val, id;
};
int N, K;
int A[maxn];
int mx[maxn], mn[maxn];
node q[maxn];
int main(){
	cin >> N >> K;
	for(int i = 1; i <= N; i++){
		cin >> A[i];
	}
	int head = 1, tail = 0;
	for(int i = 1; i <= N; i++){
		while(head <= tail && q[tail].val >= A[i]) tail--;
		q[++tail] = (node){A[i], i};
		if(i >= K){
			while(head <= tail && q[head].id <= i - K) head++;
//			mn[i] = q[head].val;
			cout << q[head].val << " ";
		}
	}
	cout << endl;
	head = 1, tail = 0;
	for(int i = 1; i <= N; i++){
		while(head <= tail && q[tail].val <= A[i]) tail--;
		q[++tail] = (node){A[i], i};
		if(i >= K){
			while(head <= tail && q[head].id <= i - K) head++;
//			mx[i] = q[head].val;
			cout << q[head].val << " ";
		}
	}
	memset(q, 0, sizeof(q));
	return 0;
}

最大数

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 5;
int m, mod, t;
int st[2][maxn], top, cnt;
int q[maxn];
void add(int x){
	cnt += 1;
	while(x > st[1][top] && top) top -= 1;
	st[0][++top] = cnt;
	st[1][top] = x;
}
void query(int mx){
	int l = 1, r = top;
    while(l < r){
        int mid = (l + r) / 2;
        if(st[0][mid] < mx) l = mid + 1;
        else r=mid;
    }
	t = st[1][r];
    cout << t << endl;
}
signed main(){
	cin >> m >> mod;
    while(m--){
        char ch;
        cin >> ch;
        if(ch == 'A') {
        	int x;
        	cin >> x;
        	add((t + x) % mod);
		}
        else {
        	int x;
        	cin >> x;
			query(cnt - x + 1);
		}
    }
	return 0;
}

最大连续和

#include<bits/stdc++.h>
#define fo(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
const int maxn = 2e5 + 5;
int n, m, top, l = 1, r = 0, sum[maxn];
int ans = INT_MIN;
int a[maxn];
struct node{
	int sum, id;
};
node q[maxn];
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	q[++r] = (node){0, 0};
	fo(i, 1, n){
		while(l <= r && q[r].sum >= sum[i]) r -= 1;
		while(l <= r && q[l].id < i - m) l += 1;
		ans = max(ans, sum[i] - q[l].sum);
		q[++r] = (node){sum[i], i};
	}
	cout << ans;
	return 0;
} 

烽火传递

#include<bits/stdc++.h>
#define fo(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
struct node{
	int val, id;
};
const int maxn = 2e5 + 5;
int n, m, top, l = 0, r = 0, dp[maxn];
int ans = INT_MAX;
int a[maxn];
node q[maxn];
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	fo(i, 1, m) dp[i] = a[i];
	fo(i, 1, n){
		while(l <= r && q[l].id < i - m) l += 1;
		while(l < r && q[r].val >= a[i] + q[l].val) r -= 1;
		dp[i] = a[i] + q[l].val;
		q[++r] = (node){dp[i], i};
	}
	fo(i, n - m + 1, n){
		ans = min(ans, dp[i]);
	}
	cout << ans;
	return 0;
} 

游历

#include<bits/stdc++.h>
#define int long long
#define maxn 500005
using namespace std;
int n, m, a, dep[maxn], fa[maxn][45], now, nex, tot = 0;
int head[maxn];
long long ans = 0, val[maxn];
struct node{
	int to, nex, one, two;
} E[maxn << 1];
void add(int u, int v, int o, int t){
	E[++tot].to = v;
	E[tot].nex = head[u];
	E[tot].one = o;
	E[tot].two = t;
	head[u] = tot;
}
void dfs(int x, int f) {
    dep[x] = dep[f] + 1;
    fa[x][0] = f;
    for(register int i = 1; (1 << i) <= dep[x]; i++){
    	fa[x][i] = fa[fa[x][i - 1]][i - 1];
	}
	for(register int i = head[x]; i; i = E[i].nex){
		if(E[i].to != f){
			dfs(E[i].to, x);
		}
	}
}
int lca(int x, int y)
{
	if(dep[x] < dep[y]) x ^= y ^= x ^= y;
	for(register int i = 40; i >= 0; i--)
	{
		if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
		if(x == y) return y;
	}
	for(register int i = 40; i >= 0; i--)
		if(fa[x][i] != fa[y][i]) {x = fa[x][i]; y = fa[y][i];}
	return fa[x][0];
}
void solve(int x)
{
	int u;
	for(register int i = head[x]; i; i = E[i].nex){
		if(E[i].to != fa[x][0])
		{
			solve(E[i].to);
			val[x] += val[E[i].to];
		}
		else u = i;
	}
	if(E[u].one * val[x] < E[u].two) ans += E[u].one * val[x];
	else ans += E[u].two;
	return;
}
signed main(){
	scanf("%d", &n);
	for(register int i = 1, u, v, c1, c2; i < n; i++)
	{
		scanf("%d %d %d %d", &u, &v, &c1, &c2);
		add(u, v, c1, c2); add(v, u, c1, c2);
	}
	dfs(1, 0);
	for(register int i = 1; i < n; i++)
	{
		val[i]++; val[i + 1]++;
		val[lca(i, i + 1)] -= 2;
	}
	solve(1);
	printf("%lld", ans);
	return 0;
}