大三第十一周学习笔记

周一

赛前最后的努力了，加油！！

前几天疯狂写作业，现在还有三场比赛的题没补，加油！

L. Buy Figurines（堆+线段树）

这题的关键在于只有n个人，怎么利用这个保证复杂度

考虑维护这n个人的离开时间，用一个优先队列维护

那么对于当前状态，可以处理处当前每个队的人数，怎么快速求最值呢

这个其实就是一个可以修改的堆，可以用set或者线段树实现

#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;
 
typedef long long ll;
typedef pair<ll, int> pii;
const int N = 2e5 + 10;
pair<int, int> b[N];
int t[N << 2], n, m;
ll last[N];
 
void up(int k)
{
	t[k] = min(t[l(k)], t[r(k)]);
}
 
void clear(int k, int l, int r)
{
	t[k] = 0;
	if(l == r) return;
	int m = l + r >> 1;
	clear(l(k), l, m);
	clear(r(k), m + 1, r);
}
 
void modify(int k, int l, int r, int x, int p)
{
	if(l == r)
	{
		t[k] += p;
		return;
	}
	int m = l + r >> 1;
	if(x <= m) modify(l(k), l, m, x, p);
	else modify(r(k), m + 1, r, x, p);
	up(k);
}
 
int ask(int k, int l, int r)
{
	if(l == r) return l;
	int m = l + r >> 1;
	if(t[l(k)] <= t[r(k)]) return ask(l(k), l, m);
	else return ask(r(k), m + 1, r);
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d", &n, &m);
		_for(i, 1, n) scanf("%d%d", &b[i].first, &b[i].second);
		sort(b + 1, b + n + 1);
		
		_for(i, 1, m) last[i] = 0;
		clear(1, 1, m);
 
		ll ans = 0;
		priority_queue<pii, vector<pii>, greater<pii>> q;
		_for(i, 1, n)
		{
			auto [a, s] = b[i];
			while(!q.empty() && a >= q.top().first)
			{
				modify(1, 1, m, q.top().second, -1);
				q.pop();
			}
 
			int cur = ask(1, 1, m);
			if(a >= last[cur]) last[cur] = a + s;
			else last[cur] += s;
			ans = max(ans, last[cur]);
			modify(1, 1, m, cur, 1);
			q.push({last[cur], cur});
		}
		printf("%lld\n", ans);
	}
 
	return 0; 
} 

C. Slipper（建图+最短路）

每一层加一个点，这一层连到它，然后它连向d+k层的所有点，然后跑最短路即可

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;
 
typedef long long ll;
const int N = 2e6 + 10;
ll d[N];
struct node
{
	int v; ll w;
	bool operator < (const node& rhs) const
	{
		return w > rhs.w;
	}
};
vector<pair<int, int>> g[N];
vector<int> ve[N];
int n, k, p, s, t, cnt;
 
void dfs(int u, int fa, int dep)
{
	ve[dep].push_back(u);
	for(auto [v, w]: g[u])
	{
		if(v == fa) continue;
		dfs(v, u, dep + 1);
	}
}
 
void solve()
{
	_for(i, 1, 2 * n) d[i] = 1e18;
	d[s] = 0;
	priority_queue<node> q;
	q.push({s, d[s]});
 
	while(!q.empty())
	{
		node x = q.top(); q.pop();
		int u = x.v;
		if(d[u] != x.w) continue;
 
		for(auto [v, w]: g[u])
			if(d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				q.push({v, d[v]});
			}
	}
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		_for(i, 1, 2 * n) g[i].clear(), ve[i].clear();
		_for(i, 1, n - 1)
		{
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			g[u].push_back({v, w});
			g[v].push_back({u, w});
		}
		scanf("%d%d%d%d", &k, &p, &s, &t);
 
		dfs(1, 0, 1);
 
		cnt = n;
		_for(i, 1, n)
		{
			if(!ve[i].size()) break;
			cnt++;
			for(int x: ve[i]) g[x].push_back({cnt, 0}); 
			for(int x: ve[i + k]) g[cnt].push_back({x, p});
			if(i - k >= 1) for(int x: ve[i - k]) g[cnt].push_back({x, p});
		}
 
		solve();
		printf("%lld\n", d[t]);
	}
 
	return 0; 
} 

J. Eat, Sleep, Repeat（博弈）

这是一类博弈题，就是说操作次数其实是一定的，直接算操作次数的奇偶即可，关键是怎么算。

对于这题，可以发现限制为0把数分成了很多段。

每一段内，每个数尽可能的小，从最小的数开始往上。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 1e5 + 10;
map<int, int> mp;
int n, k;
ll a[N];
 
ll cal(vector<int> ve, int st)   //函数这里不要忘记开long long
{
	if(!ve.size()) return 0;
 
	ll sum = 0;
	for(auto x: ve) sum += x - st;
 
	int pos = st - 1;
	while(mp.count(pos + 1) && mp[pos + 1]) pos++;
	if(pos == st - 1) return sum;
 
	ll res = 0, num = ve.size();
	_for(i, st, pos) 
	{
		if(num <= mp[i])
		{
			res += 1LL * (i - st) * num;   //相乘的时候注意开1LL
			num = 0;
			break;
		}
		else
		{
			res += 1LL * (i - st) * mp[i];
			num -= mp[i];
		}
	}
	res += num * (pos + 1 - st);
 
	return sum - res;
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		mp.clear();
		scanf("%d%d", &n, &k);
		_for(i, 1, n) scanf("%lld", &a[i]);
		sort(a + 1, a + n + 1);
		
		vector<int> ve;
		while(k--)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			mp[x] = y;
			if(!y) ve.push_back(x);
		}
		ve.push_back(-1);
		ve.push_back(2e9);
		sort(ve.begin(), ve.end());
 
		ll ans = 0;
		rep(i, 0, ve.size() - 1)
		{
			int l = lower_bound(a + 1, a + n + 1, ve[i]) - a;
			int r = lower_bound(a + 1, a + n + 1, ve[i + 1]) - a - 1;
			vector<int> v;
			_for(j, l, r) v.push_back(a[j]);
			ans += cal(v, ve[i] + 1);
		}
		puts(ans % 2 == 1 ? "Pico" : "FuuFuu");
	}
 
	return 0;
}

G. Grade 2（打表/异或）

比赛时是推出结论的

其实如果打表找一下规律，能出的更快

首先异或与加法联系紧密

对于A^x对A的改变为正负x

可以这么理解，异或的作用就是为1的地方取反，那么最多就是全部把0变1，也就是加x，相反最小就是减x。

范围宽放一点话就是二进制位

那么kx^x=kx+a

gcd(kx ^ x, x) = gcd(kx + a, x) = gcd(a, x)

也就是说其实gcd取决于异或后改变了多少

那么题目给的x是1e6,这个非常关键，意味着不会改变太多

再考虑二进制位，会发现如果k的范围可以遍历二进制位的所有数，那么一定会有重复，那么重复就可以想到循环节

考虑t为大于x的最小的二次幂数

那么kx = (k + t) x  (mod t)

因为改变的就是低位的二进制，所以只用看低位二进制的，那么发现t是循环 节

也就是说，gcd(kx ^ x, x)以t为循环节

那么l和r转化为前缀和

对于当前，看有几个t，多出来的部分用前缀和

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 2e6 + 10;
ll s[N], mod;
 
ll gcd(ll a, ll b) { return !b ? a: gcd(b, a % b); }
 
ll cal(ll r)
{
	ll k = r / mod;
	return k * s[mod] + s[r - k * mod];
}
 
int main()
{
	ll x, n;
	scanf("%lld%lld", &x, &n);
	
	ll t = 1;
	while(t <= x) t <<= 1;
	
	mod = t;
	_for(i, 1, mod) s[i] = s[i - 1] + (gcd(i * x ^ x, x) == 1);
 
	while(n--)
	{
		ll l, r;
		scanf("%lld%lld", &l, &r);
		printf("%lld\n", cal(r) - cal(l - 1));
	}
 
	return 0;
}

I. Dragon Bloodline（二分答案+贪心）

这题的重点是贪心

首先有一个结论，就是对于当前最高的2次幂，如果把它分配给大于等于它的，那么一定不会更差。因为在一个合法解里面，可以进行替换。

那么2的次幂从高到低遍历，首先把大于等于它的都分配给它，如果用完了就下一个，否则把多出来的给前cnt大的，这样肯定是浪费最少的。

二分答案的上界需要思考一下，要小心check的时候爆long long

分母部分为b的和，分子部分为maxa，这是上界。这样子check的时候不会爆long long

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 5e4 + 10;
int a[N], b[25], cnt[25], n, k;
ll c[N];
 
bool check(ll key)
{
	_for(i, 1, n) c[i] = a[i] * key;
	_for(i, 1, k) cnt[i] = b[i];
	
	for(int j = k; j >= 1; j--)
	{
		_for(i, 1, n)
		{
			ll cur = min(c[i] / (1 << (j - 1)), (ll)cnt[j]);
			cnt[j] -= cur;
			c[i] -= cur * (1 << (j - 1));
			if(!cnt[j]) break;
		}
 
		if(cnt[j])
		{
			cnt[j] = min(cnt[j], n);
			nth_element(c + 1, c + cnt[j], c + n + 1, greater<ll>());
			_for(i, 1, cnt[j]) c[i] = 0;
		}
	}
	
	_for(i, 1, n)
		if(c[i])
			return false;
	return true;
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d", &n, &k);
		_for(i, 1, n) scanf("%d", &a[i]);
		_for(i, 1, k) scanf("%d", &b[i]);
		
		int mx = 0;
		_for(i, 1, n) mx = max(mx, a[i]);
		
		ll l = 0, r = 2e15 / mx;
		while(l + 1 < r)
		{
			ll m = l + r >> 1;
			if(check(m)) l = m;
			else r = m;
		}
		printf("%lld\n", l);
	} 
	
	return 0;
}

C. Magic（差分约束）

推一下三个不等式即可

注意每个位置非负有Si - Si-1 >= 0

这道题是求一个变量的最值，那么建立一个超级源点，对所有点连边权为0的边，然后从这个点开始spfa。注意不要漏掉0

养成好习惯，打完代码后不急着编译，从头肉眼查错，重点看有没有变量名打错

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e4 + 10;
int d[N], vis[N], cnt[N], S, n, k;
vector<pair<int, int>> g[N];
bool spfa()
{
	_for(i, 0, n + 1) d[i] = -1e9, vis[i] = cnt[i] = 0;  //最长路，有负权边，初始化为负无穷
	d[S] = 0;
	deque<int> q;
	q.push_back(S);
 
	while(!q.empty())
	{
		int u = q.front(); q.pop_front();
		vis[u] = 0;
		for(auto [v, w]: g[u])
			if(d[v] < d[u] + w)   //注意这里是最长路
			{
				d[v] = d[u] + w;
				if(!vis[v])
				{
					if(!q.empty() && d[v] > d[q.front()]) q.push_front(v);  //注意判空
					else q.push_back(v);
					vis[v] = 1;
					if(++cnt[v] > n) return false;
				}
			}
	}
	return true;
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d", &n, &k);
		_for(i, 0, n + 1) g[i].clear();
		S = n + 1;
		_for(i, 1, n)
		{
			int p; scanf("%d", &p);
			g[max(i - k, 0)].push_back({min(i + k - 1, n), p});
			g[i - 1].push_back({i, 0});
		}
		_for(i, 0, n) g[S].push_back({i, 0});
 
		int q; scanf("%d", &q);
		_for(i, 1, q)
		{
			int l, r, b;
			scanf("%d%d%d", &l, &r, &b);
			g[r].push_back({l - 1, -b});
		}
 
		if(!spfa()) puts("-1");
		else printf("%d\n", d[n]);
	} 
	
	return 0;
}

Link with Level Editor II（矩阵+线段树）

首先图比较小，可以用矩阵乘法。两个矩阵相乘就是恰好就是计算方案数，于是可以用矩阵来维护。

容易发现可以双指针求，关键是如何迅速求一段的值

可以直接用线段树求，但是会T

因为只关心1到m的答案，所以可以用一个向量不断右乘矩阵，这也可以优化掉一个m

继续养成习惯，写完检查一遍，防止变量。

#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 5e3 + 10;
struct martix 
{ 
	ll s[25][25]; 
	martix() { memset(s, 0, sizeof s); }
}t[N << 2];
int n, m, k;
ll v[25];
 
martix mul(martix A, martix B)
{
	martix C;
	_for(i, 1, m)
		_for(j, 1, m)
			_for(k, 1, m)
				C.s[i][j] += A.s[i][k] * B.s[k][j];
	return C;
}
 
void mul(martix A)
{
	ll res[25] = {0};
	_for(i, 1, m)
		_for(j, 1, m)
			res[i] += v[j] * A.s[j][i];
	_for(i, 1, m) v[i] = res[i];
}
 
void up(int k)
{
	t[k] = mul(t[l(k)], t[r(k)]);
}
 
void build(int k, int l, int r)
{
	if(l == r)
	{
		int l; scanf("%d", &l);
		memset(t[k].s, 0, sizeof t[k].s);
		_for(i, 1, m) t[k].s[i][i] = 1;
		while(l--)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			t[k].s[u][v] = 1;
		}
		return;
	}
	
	int m = l + r >> 1;
	build(l(k), l, m);
	build(r(k), m + 1, r);
	up(k);
}
 
void ask(int k, int l, int r, int L, int R)
{
	if(L <= l && r <= R)
	{
		mul(t[k]);
		return;
	}
	int m = l + r >> 1;
	if(L <= m) ask(l(k), l, m, L, R);
	if(R > m) ask(r(k), m + 1, r, L, R);
}
 
bool check(int l, int r)
{
	_for(i, 1, m) v[i] = 0;
	v[1] = 1;
 
	ask(1, 1, n, l, r);
	return v[m] <= k;
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d%d", &n, &m, &k);
		build(1, 1, n);
 
		int r = 0, ans = 0;
		_for(l, 1, n)
		{
			while(r + 1 <= n && check(l, r + 1)) r++;
			ans = max(ans, r - l + 1);
		}
		printf("%d\n", ans);
	} 
	
	return 0;
}

还有一种骚操作可以避免删除。

在l和r中加一个mid，每次计算拆成[l, mid] 乘上 [mid + 1, r]

右半部分r拓展的时候维护

左半部分用一个bi维护i到mid的值

当l超过mid的时候，mid=r，然后计算bi。

这样依然是O(n)的，同时避免了删除操作

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 5e3 + 10;
struct martix 
{ 
	ll s[25][25]; 
	martix() { memset(s, 0, sizeof s); }
}a[N], b[N];
int n, m, k;
 
martix mul(martix A, martix B)
{
	martix C;
	_for(i, 1, m)
		_for(j, 1, m)
			_for(k, 1, m)
				C.s[i][j] += A.s[i][k] * B.s[k][j];
	return C;
}
 
void init(martix& A)  //初始化为单位矩阵 注意引用
{
	memset(A.s, 0, sizeof A.s);
	_for(i, 1, m) A.s[i][i] = 1;
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d%d", &n, &m, &k);
		_for(i, 1, n)
		{
			init(a[i]);
			int l; scanf("%d", &l);
			while(l--)
			{
				int u, v;
				scanf("%d%d", &u, &v);
				a[i].s[u][v] = 1;
			}
		}
 
		int l = 1, mid = 1, r = 1, ans = 0;
		martix cur; init(cur);
		b[1] = a[1];
 
		_for(l, 1, n)
		{
			if(l > mid)
			{
				mid = r;
				init(cur);
				martix t; init(t);
				for(int i = mid; i >= l; i--)
				{
					t = mul(a[i], t);
					b[i] = t;
				}
			}
			while(r + 1 <= n && mul(b[l], mul(cur, a[r + 1])).s[1][m] <= k) cur = mul(cur, a[++r]);
			ans = max(ans, r - l + 1);
		}
		printf("%d\n", ans);
	} 
	
	return 0;
}

周二

Map(数学)

由边成比例写出两个圆的方程，相减得到过两个交点的直线，然后直线和圆联立得到一元二次方程，然后求根公式，得到两个解，判断一下交点是否在矩形内即可。

需要推一些公式，比较复杂

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const double EPS = 1e-8;
 
struct Point {
	double x, y;
	Point (double x = 0, double y = 0) : x(x), y(y) {}
};
int sgn(double x) {
	return (x < -EPS) ? -1 : (x > EPS);
}
 
double Cross(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}
double Cross(Point a, Point b, Point c) {
	return Cross(Point(b.x - a.x, b.y - a.y), Point(c.x - a.x, c.y - b.y));
}
 
double x[10], y[10];
 
bool Judge(Point p, Point a, Point b, Point c, Point d) {
	return sgn(Cross(Point(b.x - a.x, b.y - a.y), Point(p.x - a.x, p.y - a.y)) * Cross(Point(d.x - c.x, d.y - c.y), Point(p.x - c.x, p.y - c.y))) == -1;
}
 
bool check(double x1, double y1)
{
	return (Judge(Point(x1, y1), Point(x[5], y[5]), Point(x[6], y[6]), Point(x[8], y[8]), Point(x[7], y[7])) &&
		Judge(Point(x1, y1), Point(x[5], y[5]), Point(x[8], y[8]), Point(x[6], y[6]), Point(x[7], y[7])));
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		_for(i, 1, 8) scanf("%lf%lf", &x[i], &y[i]);
 
		//计算k
		double k = (pow(x[1] - x[2], 2) + pow(y[1] - y[2], 2)) / (pow(x[5] - x[6], 2) + pow(y[5] - y[6], 2));
 
		//直线方程
		double A = 2 * (k * x[5] - k * x[6] - x[1] + x[2]);
		double B = 2 * (k * y[5] - k * y[6] - y[1] + y[2]);
		double C = (x[1] * x[1] + y[1] * y[1] - x[2] * x[2] - y[2] * y[2] - k * (x[5] * x[5] + y[5] * y[5] - x[6] * x[6] - y[6] * y[6]));
 
		//圆方程
		double a = 1 - k;
		double b = 2 * (k * x[5] - x[1]);
		double c = 1 - k;
		double d = 2 * (k * y[5] - y[1]);
		double e = x[1] * x[1] + y[1] * y[1] - k * x[5] * x[5] - k * y[5] * y[5];
 
		//一元二次方程
		if(sgn(B))
		{
			double D = -A / B;
			double E = -C / B;
			double ta = a + c * D * D;
			double tb = b + 2 * c * D * E + d * D;
			double tc = c * E * E + d * E + e;
 
			//解方程
			double x1 = (-tb + sqrt(tb * tb - 4 * ta * tc)) / (2 * ta);
			double y1 = D * x1 + E;
			double x2 = (-tb - sqrt(tb * tb - 4 * ta * tc)) / (2 * ta);
			double y2 = D * x2 + E;
 
			if(check(x1, y1)) printf("%.10lf %.10lf\n", x1, y1);
			else printf("%.10lf %.10lf\n", x2, y2);
		}
		else
		{
			double X = -C / A;
			e += a * X * X + b * X;
			double ta = c, tb = d, tc = e;
			double y1 = (-tb + sqrt(tb * tb - 4 * ta * tc)) / (2 * ta);
			double y2 = (-tb - sqrt(tb * tb - 4 * ta * tc)) / (2 * ta);
 
			if(check(X, y1)) printf("%.10lf %.10lf\n", X, y1);
			else printf("%.10lf %.10lf\n", X, y2);
		}
	}
	
	return 0;
}

Maex（树形dp）

0是一个很重要的点，如果当前子树没有0，那么值就是全0

设dp[u]为以u为根子树中bi的最大和，也就是说以u为根的子树时的答案

那么u的b值为siz[u]，对于它的儿子v，只有一个儿子的子树是有0的，其他都没有0

没有0的子树答案是0,所以要选一个答案最大的子树

即dp[u] = siz[u] + max(dp[v])

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 5e5 + 10;
vector<int> g[N];
int siz[N], n;
ll dp[N];
 
void dfs(int u, int fa)
{
	siz[u] = 1;
	ll mx = 0;
	for(int v: g[u])
	{
		if(v == fa) continue;
		dfs(v, u);
		siz[u] += siz[v];
		mx = max(mx, dp[v]);
	}
	dp[u] = siz[u] + mx;
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		_for(i, 1, n) g[i].clear();
		_for(i, 1, n - 1)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
 
		dfs(1, 0);
		printf("%lld\n", dp[1]);
	}
	
	return 0;
}

Loop(思维)

贪心考虑每一次操作

把第一个大于前一个数的位置找出，为i

然后把ai-1提出来，插到后面去，插到第一个比它小的数前面

考虑如何快速求

可以一次性处理，把所有提出来的数放一起，由于插是随意的，所以排个序，然后把这些数和原来剩下的数做一个归并即可

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 3e5 + 10;
int st[N], top, n, k;
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		top = 0;
		scanf("%d%d", &n, &k);
 
		priority_queue<int> q;
		_for(i, 1, n)
		{
			int x; scanf("%d", &x);
			while(k && top && x > st[top])
			{
				k--;
				q.push(st[top--]);
			}
			st[++top] = x;
		}
 
		_for(i, 1, top)
		{
			while(!q.empty() && q.top() > st[i])
			{
				printf("%d ", q.top());
				q.pop();
			}
			printf("%d ", st[i]);
		}
		while(!q.empty()) 
		{
			printf("%d ", q.top());
			q.pop();
		}
		puts("");
	}
	
	return 0;
}

周三

Black Magic（思维）

考虑合并的次数最多

那就全黑放一起，左边放一个右黑，右边放要给左黑，然后左黑和右黑两两配对

注意要特判没有全黑的情况，要单独处理，因为这个WA了一发

考虑合并的次数最少

全黑和全白交替放，然后左边放右白，右边放左白

多余的黑只能放一起

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		 int E, L, R, B, sum;;
		 scanf("%d%d%d%d", &E, &L, &R, &B);
		 sum = E + L + R + B;
 
		 if(B)
		 {
			int ans = B - 1;
			if(L) ans++, L--;
			if(R) ans++, R--;
			ans += min(L, R);
			printf("%d ", sum - ans);
		 }
		 else printf("%d ", sum - min(L, R));
 
		 int t = max(0, B - (E + 1));
		 printf("%d\n", sum - t);
	}
 
	return 0;
}

Independent Feedback Vertex Set（思维）

很容易发现一个点如果选到了第一个集合，那么剩下的点都确定了。

而一个环要有一个点在第一个集合，所以选一个环枚举三种情况即可

选集合的写法很重要，赛时写的很复杂，实际上按照读入顺序即可，当前点连了两个点，如果其中第一个点是第一个集合，那么当前点必然是第二个集合，如果两个点都是第二个集合，那么当前点是第一个集合

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 1e5 + 10;
int a[N], u[N], v[N], c[N], n;
 
ll solve(int t)
{
	_for(i, 1, n) c[i] = 0;
	c[t] = 1;
 
	_for(i, 4, n)
	{
		if(c[u[i]] || c[v[i]]) c[i] = 0;
		else c[i] = 1;
	}
 
	ll res = 0;
	_for(i, 1, n)
		if(c[i])
			res += a[i];
	return res;
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		_for(i, 1, n) scanf("%d", &a[i]);
		_for(i, 4, n) scanf("%d%d", &u[i], &v[i]);
 
		ll ans = 0;
		_for(i, 1, 3)
			ans = max(ans, solve(i));
		printf("%lld\n", ans);
	}
 
	return 0;
}

Counting Stickmen（树形dp+组合数学）

这题赛时队友想出了一种奇妙的状压dp做法，很骚

一个火柴人有四个部分，一个头，两个手臂，一个身体带两条腿

那么现在就是凑成这个四个部分有多少种方案，那么我们用一个四位二进制代表已经有当前部分的时候的方案数是什么

dp[i][S]表示对于当前点，遍历前i个邻居，构成状态S的方案数

从高到低分别是头，两条腿，身体

对于一个新的点，作为头的话就是把最高位为0的变为1，身体的话就是最低位的0变为1

对于腿，用00表示没有腿，10表示有一条腿，11表示两点腿，每次可以加一条腿

记住还有不构成新部分的答案

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 5e5 + 10;
const int mod = 998244353;
ll dp[N][1 << 4], ans;
vector<int> g[N];
int n, cnt;
 
void add(ll num)
{
	cnt++;
 
	//什么都不干
	rep(S, 0, 1 << 4)
		dp[cnt][S] = dp[cnt - 1][S];
 
	//头
	rep(S, 0, 1 << 4)
		if(S & (1 << 3))
			(dp[cnt][S] += dp[cnt - 1][S ^ (1 << 3)]) %= mod;
	
	//腿
	rep(S, 0, 1 << 4)
	{
		if(((S >> 2) & 1) && ((S >> 1) & 1))
			(dp[cnt][S] += dp[cnt - 1][S ^ (1 << 2)] * num) %= mod;
		if(!((S >> 2) & 1) && ((S >> 1) & 1))
			(dp[cnt][S] += dp[cnt - 1][S ^ (1 << 1)] * num) %= mod;
	}
 
	//身体
	rep(S, 0, 1 << 4)
		if(S & 1)
			(dp[cnt][S] += dp[cnt - 1][S ^ 1] * ((num * (num - 1) / 2) % mod)) %= mod;
}
 
void dfs(int u, int fa)
{
	cnt = 0;
	dp[0][0] = 1;
	for(int v: g[u]) add(g[v].size() - 1);
	(ans += dp[cnt][(1 << 4) - 1]) %= mod;
 
	_for(i, 0, cnt)
		rep(S, 0, 1 << 4)
			dp[i][S] = 0;
	
	for(int v: g[u]) 
	{
		if(v == fa) continue;
		dfs(v, u);
	}
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		_for(i, 1, n) g[i].clear();
		_for(i, 1, n - 1)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		
		ans = 0;
		dfs(1, 0);
		printf("%lld\n", ans);
	}
 
	return 0;
}

另一种做法，就是比较组合数学了，就枚举哪一个邻居作为身体，然后剩下的部分组合数学算

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 5e5 + 10;
const int mod = 998244353;
ll ans, inv2 = 499122177;
vector<int> g[N];
int n;
 
void dfs(int u, int fa)
{
	if(g[u].size() <= 3)
	{
		for(int v: g[u])
		{
			if(v == fa) continue;
			dfs(v, u);
		}
		return;
	}
 
	vector<ll> ve;
	for(int v: g[u])
		ve.push_back(g[v].size() - 1);
	
	ll sum1 = 0, sum2 = 0;
	for(auto x: ve) 
	{
		sum1 = (sum1 + x) % mod;
		sum2 = (sum2 + x * x % mod) % mod;
	}
 
	ll t = (sum1 * sum1 % mod - sum2 + mod) * inv2 % mod;
	for(auto x: ve)
	{
		ll res = (x * (x - 1) / 2) % mod;
		res = res * (t - (sum1 - x) * x % mod + mod) % mod;
		res = res * (g[u].size() - 3) % mod;
		ans = (ans + res) % mod;
	}
 
	for(int v: g[u])
	{
		if(v == fa) continue;
		dfs(v, u);
	}
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		_for(i, 1, n) g[i].clear();
		_for(i, 1, n - 1)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		
		ans = 0;
		dfs(1, 0);
		printf("%lld\n", ans);
	}
 
	return 0;
}

Weighted Beautiful Tree（树形dp）

可以发现点要不不变，要不取边权。

那么对于每个点，维护一下取某个边权的答案，求一下前缀最小值，后缀最小值

那么对于边u，v，分类讨论

v小于边权，此时u可以大于等于边权

v大于边权，u可以小于等于边权

v等于边权，u任取

注意要小心v等于边权的情况，不然会算重

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 1e5 + 10;
int c[N], a[N], n;
vector<ll> val[N], dp[N], pre[N], suf[N];
unordered_map<int, int> mp[N];
vector<pair<int, int>> g[N];
void dfs(int u, int fa)
{
	dp[u].resize(val[u].size() + 1);
 
	for(auto [v, w]: g[u])
	{
		if(v == fa) continue;
		dfs(v, u);
 
		int pv = mp[v][w];
		ll cur = pre[v][pv];
 
		int pu = mp[u][w];
		dp[u][pu + 1] += cur;
 
		cur = suf[v][pv];
		dp[u][0] += cur;
		dp[u][pu] -= cur;
 
		dp[u][pu] += pre[v][val[v].size() - 1];
		dp[u][pu + 1] -= pre[v][val[v].size() - 1];
	}
 
	rep(i, 1, val[u].size()) dp[u][i] += dp[u][i - 1];
	rep(i, 0, val[u].size()) dp[u][i] += 1LL * c[u] * abs(val[u][i] - a[u]);
 
	pre[u].resize(val[u].size());
	suf[u].resize(val[u].size());
	pre[u][0] = dp[u][0];
	rep(i, 1, val[u].size()) pre[u][i] = min(dp[u][i], pre[u][i - 1]);
 
	suf[u][val[u].size() - 1] = dp[u][val[u].size() - 1];
	for(int i = val[u].size() - 2; i >= 0; i--)
	 	suf[u][i] = min(dp[u][i], suf[u][i + 1]);
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		_for(i, 1, n) scanf("%d", &c[i]), g[i].clear(), val[i].clear(), mp[i].clear(), dp[i].clear(), pre[i].clear(), suf[i].clear();
		_for(i, 1, n) scanf("%d", &a[i]), val[i].push_back(a[i]);
		_for(i, 1, n - 1)
		{
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			g[u].push_back({v, w});
			g[v].push_back({u, w});
			val[u].push_back(w);
			val[v].push_back(w);
		}
 
		_for(i, 1, n) 
		{
			sort(val[i].begin(), val[i].end());
			rep(j, 0, val[i].size()) mp[i][val[i][j]] = j;
		}
 
		dfs(1, 0);
 
		ll ans = 1e18;
		rep(i, 0, dp[1].size() - 1)
			ans = min(ans, dp[1][i]);
		printf("%lld\n", ans);
	}
	
	return 0;
}

Triangle Game（博弈论）

打了个表，没看出来啥，然后队友说-1后的异或和为0

这个游戏有点像nim游戏，这类游戏就要往异或和的方向想。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		 int a, b, c;
		 scanf("%d%d%d", &a, &b, &c);
		 a--; b--; c--;
		 if((a ^ b ^ c)== 0) puts("Lose");
		 else puts("Win");
	}
 
	return 0;
}

周四

D. ConstructOR（思维）

这题关键是想出一种巧妙的构造方法

首先因为x | a和x | b都要被d整除，那不如设结果都是x

即x | a = x, x | b = x

这样设后会不会漏掉解，不会，因为在这种情况下一定可以构造出来

满足x | a = x, x | b = x时，那么在a | b的某一位为1，x的这一位必须为1，其他地方可能为1可能为0

然后考虑d的倍数，x = d * t，把t看成二进制，那么x就是d多次左移相加

那么枚举二进制位从小到大，如果当前的x这一位必须为1(也就是a|b的这一位为1)，那么就把d左移，把最低位为1的位移到这，加上，这样是一定可以构造出来的

注意，当a|b的最低为1的位小于d时，是无解的

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
ll a, b, d;
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%lld%lld%lld", &a, &b, &d);
 
		int k = 0;
		while(!(d >> k & 1)) k++;
		ll x = 0;
		_for(j, 0, 30)
		{
			if(((a | b) >> j & 1) && !(x >> j & 1))
			{
				if(j < k) { x = -1; break; }
				else x += d << j - k;
			}
		}
		printf("%lld\n", x);
	}
	
	return 0;
}

周五

Stormwind（数据范围）

这题的关键在于数据范围，发现nT的数据范围是可以过的，我一开始还在想O(1)的做法，没注意到这个。

这个数据范围可以过，那直接枚举小矩阵的一条边即可，注意两个边的边长都不能超过大矩形的边长。

注意数据范围，尤其是一些数值非1e9的

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		int n, m, k;
		scanf("%d%d%d", &n, &m, &k);
 
		int ans = 0;
		_for(i, 1, min(k, n))
		{
			int j = (k + i - 1) / i;
			if(j > m) continue;
			ans = max(ans, n / i + m / j - 2);
		}
		printf("%d\n", ans);
	}
 
	return 0;
}

Darnassus（根号数据范围）

这题不太好想到

5e4这个奇妙的数据范围，n方不能通过，nlogn又冗余了些

所以应该是bitset优化或者n根号n的算法

根号的话可以想到两两不同，莫队，分块，枚举因数

首先考虑连i到i-1，发现每条边都是小于等于n-1
那么这样的话答案的最小生成树肯定是每条边都小于等于n-1，因为是从小到大贪心选的

那么|i-j|*|pi-pj| <= n-1,必然有一个小于等于根号n-1

那么可以n根号n的求出所有这些权值小于等于根号n-1的边，然后跑krusal即可

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 5e4 + 10;
int p[N], a[N], f[N], n;
struct Edge { int u, v, w; };
vector<Edge> e;
 
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
 
bool cmp(Edge x, Edge y)
{
	return x.w < y.w;
}
 
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		e.clear();
		scanf("%d", &n);
		_for(i, 1, n) scanf("%d", &p[i]), a[p[i]] = i, f[i] = i;
 
		int t = sqrt(n);
		_for(i, 1, n)
		{
			_for(j, i + 1, n)
			{
				if(j - i > t) break;
				ll cur = 1LL * abs(i - j) * abs(p[i] - p[j]);
				if(cur <= n - 1) e.push_back({i, j, cur});
			}
			
			_for(j, p[i] + 1, n)
			{
				if(j - p[i] > t) break;
				ll cur = 1LL * abs(i - a[j]) * abs(p[i] - j);
				if(cur <= n - 1) e.push_back({i, a[j], cur});
			}
		}
 
		ll ans = 0;
		sort(e.begin(), e.end(), cmp);
		for(auto [u, v, w]: e)
		{
			int fu = find(u), fv = find(v);
			if(fu != fv)
			{
				f[fu] = fv;
				ans += w;
			}
		}
		printf("%lld\n", ans);
	}
 
	return 0;
}