搜索

2022NOIP A层联测33


发布时间: 2022-11-24 21:21:01    浏览次数:32 次

GCD

直接枚举\(\text {GCD}\),$\text {bitset} $维护。

CD

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<bitset>
#include<map>
#include<vector>
using namespace std;

#define Miuna printf ("dai suki...")
#define Mizuki signed 
#define love (1209 & 322 & 901)

namespace LRH
{
	template <typename Shiodome_miuna> inline void in (Shiodome_miuna &x)
	{
		x = 0;
		char f = 0, ch;
		while (!isdigit (ch = getchar ())) if (ch == '-') f = 1;
		do
		{
			x = (x << 1) + (x << 3) + (ch ^ 48);
		} while (isdigit (ch = getchar ()));
		if (f) x = -x;
	}
	int st[40], tp;
	template <typename Shiodome_miuna> inline void ot (Shiodome_miuna x, int f = 2)
	{
		if (x < 0) putchar ('-'), x = -x;
		do
		{
			st[++ tp] = x % 10;
			x /= 10;
		} while (x);
		while (tp) putchar (st[tp --] | 48);
		if (f == 1) putchar ('\n');
		if (!f) putchar (' ');
	}
}using namespace LRH;
const int maxn = 3e4 + 10;
int n, m, q;
int u[maxn], v[maxn], w[maxn];
bitset <30020> Q[maxn];
vector <int> a[100010];
pair<int, int> po[300010];
map <pair <int, int>, int> mp;
int gcd (int x, int y)
{
	while (y)
	{
		int t = x; x = y;
		y = t % x;
	}
	return x;
}
int fa[maxn];
int fd (int x)
{
	while (x != fa[x]) x = fa[x] = fa[fa[x]];
	return x;
}
void un (int x, int y)
{
	int fx = fd (x), fy = fd (y);
	if (fx != fy) fa[fx] = fy;
}
int main ()
{
	freopen ("gcd.in", "r", stdin);
	freopen ("gcd.out", "w", stdout);
	in (n), in (m), in (q);
	int g = 0, mx = 0;
	for (int i = 1; i <= m; ++ i)
	{
		in (u[i]), in (v[i]), in (w[i]);
		int z = sqrt (w[i]);
		if (!g) g = w[i];
		else g = gcd (w[i], g);
		mx = max (mx, w[i]);
		for (int J = 1; J <= z; ++ J) if (w[i] % J == 0)
		{
			a[J].push_back (i);
			if (J * J != w[i]) a[w[i] / J].push_back (i);
		}
	}
	for (int i = 1; i <= q; ++ i)
	{
		in (po[i].first), in (po[i].second);
		Q[po[i].first].set (po[i].second);
		mp[po[i]] = -1;
	}
	for (int i = 1; i <= n; ++ i) fa[i] = i;
	for (int i = mx; i >= 1; i -= g)
	{
		bitset <30020> s, g;
		for (auto J : a[i])
		{
			s.set (u[J]), s.set (v[J]);
			un (u[J], v[J]);
		}
		for (int x = s._Find_first (); x != 30020; x = s._Find_next (x))
		{
			g = s & Q[x];
			for (int y = g._Find_first (); y != 30020; y = g._Find_next (y)) if (fd (x) == fd (y)) mp[{x, y}] = i, Q[x].reset(y);
		}
		for (int x = s._Find_first (); x != 30020; x = s._Find_next (x)) fa[x] = x;
	}
	for (int i = 1; i <= q; ++ i) ot (mp[po[i]], 1);
	return love;
}

简单题

经典套路题,做过4次了,发现\(\varphi(1e6)\)最多操作\(20\)次就变成\(1\)了,非常\(\text J\),于是就可以线段树暴力单点修改了,上传一个\(y\)的最大值,如果整个区间最大值是\(1\)那么直接区间加\(1\)即可,否则继续递归修改
然而记得要驱魔

CD

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

#define Miuna printf ("dai suki...")
#define Mizuki signed 
#define love (1209 & 322 & 901)

namespace LRH
{
	template <typename Shiodome_miuna> inline void in (Shiodome_miuna &x)
	{
		x = 0;
		char f = 0, ch;
		while (!isdigit (ch = getchar ())) if (ch == '-') f = 1;
		do
		{
			x = (x << 1) + (x << 3) + (ch ^ 48);
		} while (isdigit (ch = getchar ()));
		if (f) x = -x;
	}
	int st[40], tp;
	template <typename Shiodome_miuna> inline void ot (Shiodome_miuna x, int f = 2)
	{
		if (x < 0) putchar ('-'), x = -x;
		do
		{
			st[++ tp] = x % 10;
			x /= 10;
		} while (x);
		while (tp) putchar (st[tp --] | 48);
		if (f == 1) putchar ('\n');
		if (!f) putchar (' ');
	}
}using namespace LRH;
typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 998244353;
int n, m;
int x[maxn], y[maxn];
int prime[maxn], phi[maxn], cnt;
bool v[maxn];
void shai ()
{
	phi[1] = 1;
	for (int i = 2; i <= 1e6; ++ i)
	{
		if (!v[i]) prime[++ cnt] = i, phi[i] = i - 1;
		for (int J = 1; J <= cnt; ++ J)
		{
			int k = i * prime[J];
			if (k > 1e6) break;
			v[k] = 1;
			if (i % prime[J] == 0)
			{
				phi[k] = phi[i] * prime[J];
				break;
			}
			phi[k] = phi[i] * (prime[J] - 1);
		}
	}
}
struct miuna 
{
	ll sumy, sumx, y, lz;
}t[maxn << 2];
inline void pushup (int k)
{
	t[k].sumx = t[k << 1].sumx + t[k << 1 | 1].sumx;
	t[k].sumy = t[k << 1].sumy + t[k << 1 | 1].sumy;
	t[k].y = max (t[k << 1].y, t[k << 1 | 1].y);
}
inline void pushdown (int k, int l, int r)
{
	int mid = l + r >> 1;
	(t[k << 1].sumx += t[k].lz * (mid - l + 1)) %= mod;
	(t[k << 1].lz += t[k].lz) %= mod;
	(t[k << 1 | 1].sumx += t[k].lz * (r - mid)) %= mod;
	(t[k << 1 | 1].lz += t[k].lz) %= mod;
	t[k].lz = 0;
}
void build (int k, int l, int r)
{
	if (l == r)
	{
		t[k].sumx = x[l], t[k].y = y[l], t[k].sumy = y[l];
		return;
	}
	int mid = l + r >> 1;
	build (k << 1, l, mid);
	build (k << 1 | 1, mid + 1, r);
	pushup (k);
}
void update (int k, int l, int r, int L, int R)
{
	if (L <= l && r <= R && t[k].y == 1)
	{
		(t[k].sumx += r - l + 1) %= mod;
		t[k].lz  ++;
		return;
	}
	if (l == r)
	{
		(t[k].sumx += t[k].y) %= mod;
		t[k].y = phi[t[k].y];
		t[k].sumy = t[k].y;
		return;
	}
	if (t[k].lz) pushdown (k, l, r);
	int mid = l + r >> 1;
	if (L <= mid) update (k << 1, l, mid, L, R);
	if (R > mid) update (k << 1 | 1, mid + 1, r, L, R);
	pushup (k);
}
ll query_x (int k, int l, int r, int L, int R)
{
	if (L <= l && r <= R) return t[k].sumx;
	int mid = l + r >> 1;
	if (t[k].lz) pushdown (k, l, r);
	ll res = 0;
	if (L <= mid) res = query_x (k << 1, l, mid, L, R);
	if (R > mid) (res += query_x (k << 1 | 1, mid + 1, r, L, R)) %= mod;
	return res;
}
ll query_y (int k, int l, int r, int L, int R)
{
	if (L <= l && r <= R) return t[k].sumy;
	int mid = l + r >> 1;
	if (t[k].lz) pushdown (k, l, r);
	ll res = 0;
	if (L <= mid) res = query_y (k << 1, l, mid, L, R);
	if (R > mid) (res += query_y (k << 1 | 1, mid + 1, r, L, R)) %= mod;
	return res;
}
int main ()
{
	freopen ("simple.in", "r", stdin);
	freopen ("simple.out", "w", stdout);
	shai ();
	in (n), in (m);
	for (int i = 1; i <= n; ++ i)
	{
		in (x[i]), in (y[i]);
	}
	build (1, 1, n);
	int op, l, r;
	for (int i = 1; i <= m; ++ i)
	{
		in (op), in (l), in (r);
		if (op == 1) update (1, 1, n, l, r);
		else 
		{
			ot (query_x (1, 1, n, l, r), 0);
			ot (query_y (1, 1, n, l, r), 1);
		}
	}
	return love;
}

建筑

\(max_{x, y, xx, yy}\)表示以\((x, y)\)为左上角,\((xx, yy)\)为左下角的矩形中的最大值
\(sum_{x, y, xx, yy}\)同上
要求\(\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}\sum\limits_{xx=x}^{n}\sum\limits_{yy=y}^{m}(xx - x + 1) \times (yy - y +1)\times max_{x ,y, xx, yy} - sum_{x, y, xx, yy}\)
先考虑后半部分,单独考虑每个点的贡献,发现点\((i, J)\)\(i \times j \times (n - i+ 1)\times(m - J + 1)\)个矩形包含,因此点\((i, J)\)被计算了\(i \times j \times (n - i+ 1)\times(m - J + 1)\)次,所以它的贡献是$$i \times j \times (n - i+ 1)\times(m - J + 1)\times a_{i,J}$$
可以\(O(nm)\)处理出来
然后考虑前半部分,可以把\((xx - x +1)\)提出来,于是变成了$$\sum\limits_{x=1}^{n} \sum\limits_{xx=x}^{n}(xx - x +1)\sum\limits_{y = 1}^{m}\sum\limits_{yy = y}^{m}(yy - y+ 1)\times max_{x, y, xx, yy} $$
然而没有什么卵用
然后就可以考虑把后面一部分优化,我们直接把一个矩形压缩成一个序列,这样就可以\(O(max(n,m))\)后面了
考虑怎么压缩,我们直接枚举矩形的高,然后直接把这几行压缩,每一列都取一个最大值作为序列的第\(i\)个元素
一个序列的情况就很简单了,直接单调栈处理出每个元素的最左端点和最右端点,然后就可以直接算每个元素的贡献了
怎么计算呢,当区间的左端点在\(i\)时,他的贡献是\(\sum\limits_{r = i}^{R_i}r \times a_i\),若左端点左移一位,那么贡献就会变成\(\sum\limits_{r=i}^{Ri}(r+1)\times a_i\),左移\(x\)位就是加\((r+x)\),发现每左移一位,就会比上次多计算一个\((r_i-i+1)\times a_i\),发现是等差数列,一共会左移\(L_i - 1\)次,于是当左端点左移到\(L_i\)时初始贡献就会被计算\(\frac{(i - L_i +1)\times (i - L_i)}{2}\)次,于是就可以直接算出来了,然后最后记得乘上矩形的高度,就没了
时间复杂度:由于\(n \times m \leq1e5\)所以\(n\)\(m\)中必有一个小于等于\(\sqrt {nm}\),令小的一个作为高,另一个作为宽,这样时间复杂度就是\(O(nm\sqrt{nm})\)了,读入\(n > m\)时翻转一下就可以

CD

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

#define Miuna printf ("dai suki...")
#define Mizuki signed 
#define love (1209 & 322 & 901)

namespace LRH
{
	template <typename Shiodome_miuna> inline void in (Shiodome_miuna &x)
	{
		x = 0;
		char f = 0, ch;
		while (!isdigit (ch = getchar ())) if (ch == '-') f = 1;
		do
		{
			x = (x << 1) + (x << 3) + (ch ^ 48);
		} while (isdigit (ch = getchar ()));
		if (f) x = -x;
	}
	int st[40], tp;
	template <typename Shiodome_miuna> inline void ot (Shiodome_miuna x, int f = 2)
	{
		if (x < 0) putchar ('-'), x = -x;
		do
		{
			st[++ tp] = x % 10;
			x /= 10;
		} while (x);
		while (tp) putchar (st[tp --] | 48);
		if (f == 1) putchar ('\n');
		if (!f) putchar (' ');
	}
}using namespace LRH;
typedef long long ll;
#define G (r[i] - i + 1)
#define F (i - l[i] + 1)
const int maxn = 1e5 + 10;
#define int ll
int n, m;
int mp[400][maxn];
int l[maxn], r[maxn];
int stk[maxn], top;
int a[maxn];
ll ans = 0;
ll solve ()
{
	for (int i = 1; i <= m; ++ i)
	{
		while (top && a[stk[top]] < a[i]) r[stk[top --]] = i - 1;
		l[i] = stk[top] + 1;
		stk[++ top] = i;
	}
	while (top) r[stk[top --]] = m;
	ll res = 0;
	for (int i = 1; i <= m; ++ i) res += (1ll * G * (G + 1) / 2 * (i - l[i] + 1) + F * (F - 1) / 2 * G) * a[i];
	return res;
}
Mizuki main ()
{
	freopen ("building.in", "r", stdin);
	freopen ("building.out", "w", stdout);
	in (n), in (m);
	ll ans = 0;
	if (n < m) for (int i = 1; i <= n; ++ i) for (int J = 1; J <= m; ++ J) in (mp[i][J]);
	else for (int i = 1; i <= n; ++ i) for (int J = 1; J <= m; ++ J) in (mp[J][i]);
	if (n > m) swap (n, m);
	for (int i = 1; i <= n; ++ i) for (int J = 1; J <= m; ++ J) ans -= 1ll * i * J * (n - i + 1) * (m - J + 1) * mp[i][J];
	for (int i = 1; i <= n; ++ i) 
	{
		for (int J = 1; J <= m; ++ J) a[J] = 0;
		for (int J = i; J <= n; ++ J)
		{
			for (int k = 1; k <= m; ++ k) a[k] = max (a[k], mp[J][k]);
			ans += solve () * (J - i + 1);
		}
	}
	ot (ans);
	return love;
}

树上前缀和

注意到给的是随机生成的树,所以直接跳\(father\)就行
直接树上前缀和,然后\(dis_i+dis_J-dis_{lca_{i,J}}-dis_{fa_{lca_{i,J}}}\)即可
然而你也可以像我这个J一样写线段树

CD

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

#define Miuna printf ("dai suki...")
#define Mizuki signed 
#define love (1209 & 322 & 901)

namespace LRH
{
	template <typename Shiodome_miuna> inline void in (Shiodome_miuna &x)
	{
		x = 0;
		char f = 0, ch;
		while (!isdigit (ch = getchar ())) if (ch == '-') f = 1;
		do
		{
			x = (x << 1) + (x << 3) + (ch ^ 48);
		} while (isdigit (ch = getchar ()));
		if (f) x = -x;
	}
	int st[40], tp;
	template <typename Shiodome_miuna> inline void ot (Shiodome_miuna x, int f = 2)
	{
		if (x < 0) putchar ('-'), x = -x;
		do
		{
			st[++ tp] = x % 10;
			x /= 10;
		} while (x);
		while (tp) putchar (st[tp --] | 48);
		if (f == 1) putchar ('\n');
		if (!f) putchar (' ');
	}
}using namespace LRH;
const int maxn = 1e5 + 10;
int n, m;
int a[maxn];
struct miuna 
{
	int v, nt;
}e[maxn << 1];
int tot, head[maxn];
inline void add (int x, int y)
{
	e[++ tot] = {y, head[x]};
	head[x] = tot;
}
int siz[maxn], top[maxn], num[maxn], fa[maxn], son[maxn], val[maxn], tim, dep[maxn];
void dfs1 (int x, int dad)
{
	fa[x] = dad;
	dep[x] = dep[fa[x]] + 1;
	siz[x] = 1;
	for (int i = head[x]; i; i = e[i].nt)
	{
		int y = e[i].v;
		if (y == dad) continue;
		dfs1 (y, x);
		siz[x] += siz[y];
		if (siz[y] > siz[son[x]]) son[x] = y;
	}
}
void dfs2 (int x, int tp)
{
	top[x] = tp;
	num[x] = ++ tim;
	val[tim] = a[x];
	if (son[x]) dfs2 (son[x], tp);
	for (int i = head[x]; i; i = e[i].nt)
	{
		int y = e[i].v;
		if (y == fa[x] || y == son[x]) continue;
		dfs2 (y, y);
	}
}
int t[maxn << 2];
inline void pushup (int k)
{
	t[k] = t[k << 1] + t[k << 1 | 1];
}
void build (int k, int l, int r)
{
	if (l == r) 
	{
		t[k] = val[l];
		return;
	}
	int mid = l + r >> 1;
	build (k << 1, l, mid);
	build (k << 1 | 1, mid + 1, r);
	pushup (k);
}
int query (int k, int l, int r, int L, int R)
{
	if (L <= l && r <= R) return t[k];
	int mid = l + r >> 1;
	int res = 0;
	if (L <= mid) res = query (k << 1, l, mid, L, R);
	if (R > mid) res += query (k << 1 | 1, mid + 1, r, L, R);
	return res;
}
int q_ (int x, int y)
{
	int ans = 0;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) swap (x, y);
		ans += query (1, 1, n, num[top[x]], num[x]);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap (x, y);
	ans += query (1, 1, n, num[x], num[y]);
	return ans;
}
int main ()
{
	freopen ("shuqianzhui.in", "r", stdin);
	freopen ("shuqianzhui.out", "w", stdout);
	in (n), in (m);
	for (int i = 1; i <= n; ++ i) in (a[i]);
	for (int i = 1, x, y; i < n; ++ i) 
	{
		in (x), in (y);
		add (x, y);
		add (y, x);
	}
	dfs1 (1, 1);
	dfs2 (1, 1);
	build (1, 1, n);
	for (int i = 1, x, y; i <= m; ++ i)
	{
		in (x), in (y);
		ot (q_ (x, y), 1);
	}
	return love;
}
免责声明 2022NOIP A层联测33,资源类别:文本, 浏览次数:32 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 09:21:01。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/mizukimiunal/p/16916184.html