首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛11

多校A层冲刺NOIP2024模拟赛11

时间：2024-10-22 17:00:13浏览次数：1  
标签：11 pp int 多校 Add mi1 mi2 NOIP2024 first

多校A层冲刺NOIP2024模拟赛11

\(T1\) A. 冒泡排序 \(100pts/100pts/100pts\)

  • 将循环 \(j\) 提到外面，本质上是对 \(a_{j},a_{j+k},a_{j+2k}, \dots ,a_{j+xk}\) 进行排序迭代的过程。

  • 按下标模 \(k\) 的余数分别排序即可。

    点击查看代码 
    int a[1000010];
vector<int>b[1000010];
int main()
{
  freopen("bubble.in","r",stdin);
  freopen("bubble.out","w",stdout);
  int n,k,i,j;
  scanf("%d%d",&n,&k);
  for(i=0;i<=n-1;i++)
  {
    scanf("%d",&a[i]);
    b[i%k].push_back(a[i]);
  }
  for(i=0;i<=k-1;i++)
  {
    sort(b[i].begin(),b[i].end());
    for(j=0;j<b[i].size();j++)
    {
      a[j*k+i]=b[i][j];
    }
  }
  for(i=0;i<=n-1;i++)
  {
    printf("%d ",a[i]);
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

\(T2\) B. 染色 \(0pts/0pts/0pts\)

  • 难以保证最终得到的序列 \(\{ c' \}\) 本质不同，考虑正难则反，判断 \(\{ c' \}\) 能否被 \(\{ c \}\) 通过一系列操作得到。

  • 一个比较显然的结论是对于 \(\{ c' \}\) ，将同一个颜色段内的数都缩成一个数，设得到的序列为 \(\{ d \}\) ，那么 \(\{ c' \}\) 能被 \(\{ c \}\) 通过一系列操作得到当且仅当 \(\{ d \}\) 是 \(\{ c \}\) 的子序列。

    • 虽然赛时没想到。

  • 考虑统计 \(\{ c \}\) 满足相邻两项不能相同的本质不同子序列数量。设 \(F(i)\) 表示相邻两项不能相同的长度为 \(i\) 的本质不同子序列数量，由插板法有 \(\sum\limits_{i=1}^{n}\dbinom{n-1}{i-1}F(i)\) 即为所求。组合数判奇偶同 luogu P1869 愚蠢的组合数 ，难点在于如何求 \(F(i)\) 。

  • 设 \(f_{i,j,k}\) 表示前 \(i\) 个数中末尾元素为 \(j\) 且长度为 \(k\) 的相邻两项不能相同的的本质不同子序列数量，状态转移方程为 \(f_{i,j,k}=\begin{cases} [k=1]+\sum\limits_{h=1}^{m}f_{i-1,h,k-1} & c_{i}=j \\ f_{i-1,j,k} & c_{i} \ne j \end{cases}\) 。在使用 bitset 和前缀和优化后时间复杂度仍为 \(O(\frac{n^{2}m}{w})\) ，需要进一步优化。

  • 滚掉 \(i\) 这一维，有 \(f_{j,k}\) 表示表示末尾元素为 \(j\) 且长度为 \(k\) 的相邻两项不能相同的的本质不同子序列数量。

  • 在转移过程中发现有很多冗余转移（指 \(c_{i} \ne j\) 时），考虑对于每种元素单独考虑。具体地，对于 \(F(k)=\sum\limits_{j=1}^{m}f_{j,k}\) 记录一个总和 \(sum=\sum\limits_{k=1}^{n}F(k)\) 然后进行优化。

  • 而在二进制表示下， \(f_{j,k}=[k=1]+\sum\limits_{h=1}^{m}f_{h,k-1}\) 本质上是一个整体偏移的过程，使用 bitset 优化这一过程即可。

    点击查看代码 
    int c[200010];
bitset<100010>f[20010],tmp,sum;
int C(int n,int m)
{
	return (n&m)==m;
}
int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	int t,n,m,ans,i,j;
	scanf("%d",&t);
	for(j=1;j<=t;j++)
	{
		scanf("%d%d",&n,&m);	
		ans=0;
		for(i=1;i<=m;i++)
		{
			f[i].reset();
		}
		sum.reset();
		for(i=1;i<=n;i++)
		{
			scanf("%d",&c[i]);
		}
		for(i=1;i<=n;i++)
		{
			tmp=sum^f[c[i]];
			f[c[i]]=tmp<<1;
			f[c[i]][1]=1;
			sum=tmp^f[c[i]];
		}
		for(i=1;i<=n;i++)
		{
			ans^=C(n-1,i-1)*sum[i];
		}
		printf("%d",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

\(T3\) C. 图 \(5pts/5pts/5pts\)

  • 部分分

    • 子任务 \(1\) ：暴力建边求最小生成树。

  • 正解

    • 抽象题目，直接挂官方题解了。

    点击查看不屑于封装的 std 代码 
    #include <cstdio>
#include <map>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
#include <random>
#include <cstring>
#include <ctime>
#include <cmath>
#include <assert.h>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define LL long long
#define pp pair<LL, LL>
#define mp make_pair
#define ull unsigned long long
namespace IO {
const int sz = 1 << 22;
char a[sz + 5], b[sz + 5], *p1 = a, *p2 = a, *t = b, p[105];
inline char gc() {
	//	return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
	return getchar();
}
template <class T>
void gi(T& x) {
	x = 0;
	int f = 1;
	char c = gc();
	if (c == '-')
		f = -1;
	for (; c < '0' || c > '9'; c = gc())
		if (c == '-')
			f = -1;
	for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
	x = x * f;
}
inline void flush() { fwrite(b, 1, t - b, stdout), t = b; }
inline void pc(char x) {
	*t++ = x;
	if (t - b == sz)
		flush();
}
template <class T>
void pi(T x, char c = '\n') {
	if (x < 0)
		pc('-'), x = -x;
	if (x == 0)
		pc('0');
	int t = 0;
	for (; x; x /= 10) p[++t] = x % 10 + '0';
	for (; t; --t) pc(p[t]);
	pc(c);
}
struct F {
	~F() { flush(); }
} f;
}  // namespace IO
using IO::gi;
using IO::pc;
using IO::pi;
const int mod = 1e9 + 7;
inline int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int dec(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int qkpow(int a, int b) {
	if (b < 0)
		return 0;
	int ans = 1, base = a % mod;
	while (b) {
		if (b & 1)
			ans = 1ll * ans * base % mod;
		base = 1ll * base * base % mod;
		b >>= 1;
	}
	return ans;
}
int fac[1000005], inv[1000005], Invn[600005];
inline int binom(int n, int m) {
	if (n < m || m < 0)
		return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void init_C(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[0] = 1;
	inv[n] = qkpow(fac[n], mod - 2);
	for (int i = n - 1; i >= 1; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
	Invn[0] = Invn[1] = 1;
	for (int i = 1; i <= 200000; i++) Invn[i] = (LL)(mod - mod / i) * Invn[mod % i] % mod;
}
const LL INF = 1e18;
struct node3 {
	pp mi1, mi2;
	inline void init() { mi1 = mi2 = pp(INF, 0); }
} g1[100005], g2[100005], wg1[100005], wg2[100005];
inline void Add(node3& w1, pp w2) {
	if (!w2.second)
		return;
	if (w1.mi1.second == w2.second)
		w1.mi1.first = min(w1.mi1.first, w2.first);
	else if (w1.mi2.second == w2.second) {
		w1.mi2.first = min(w1.mi2.first, w2.first);
		if (w1.mi1.first > w1.mi2.first)
			swap(w1.mi1, w1.mi2);
	} else {
		if (w2.first < w1.mi1.first)
			w1.mi2 = w1.mi1, w1.mi1 = w2;
		else if (w2.first < w1.mi2.first)
			w1.mi2 = w2;
	}
}
int Log[100005];
struct ST_min {
	node3 f[100005][21];
	inline node3 query(int l, int r) {
		node3 res;
		res.init();
		if (l > r)
			return res;
		int k = Log[r - l + 1];
		res = f[r - (1 << k) + 1][k];
		Add(res, f[l][k].mi1);
		Add(res, f[l][k].mi2);
		return res;
	}
	inline void init(int N) {
		for (int j = 1; (1 << j) <= N; j++)
			for (int i = 1; i + (1 << j) - 1 <= N; i++) {
				f[i][j] = f[i + (1 << (j - 1))][j - 1];
				Add(f[i][j], f[i][j - 1].mi1);
				Add(f[i][j], f[i][j - 1].mi2);
			}
	}
} T1[2], T2[2];
int son1[100005], son2[100005], dep11[100005], dep22[100005], seg1[100005], seg2[100005], rev11[100005],
	rev22[100005];
int top1[100005], top2[100005];
int n, fa[200005], id1[100005], id2[100005], cnt1, cnt2, dfn1[100005], dfn2[100005];
int rev1[100005], rev2[100005], f2[100005][21], sz1[100005], sz2[100005], f1[100005][21];
int st1[100005][21], st2[100005][21];
LL jp1[100005][21], jp2[100005][21];
LL dep1[100005], dep2[100005];
pp mn[200005];
struct node {
	int to, w;
};
vector<node> G1[100005], G2[100005];
inline int findSet(int u) { return fa[u] == u ? u : fa[u] = findSet(fa[u]); }
inline int Min1(int u, int v) { return dfn1[u] < dfn1[v] ? u : v; }
inline int Min2(int u, int v) { return dfn2[u] < dfn2[v] ? u : v; }
inline int LCA1(int u, int v) {
	if (u == v)
		return u;
	if ((u = dfn1[u]) > (v = dfn1[v]))
		swap(u, v);
	int k = Log[v - u++];
	return Min1(f1[u][k], f1[v - (1 << k) + 1][k]);
}
inline int LCA2(int u, int v) {
	if (u == v)
		return u;
	if ((u = dfn2[u]) > (v = dfn2[v]))
		swap(u, v);
	int k = Log[v - u++];
	return Min2(f2[u][k], f2[v - (1 << k) + 1][k]);
}
inline LL getdis(int op, int u, int v) {
	if (op == 1)
		return dep1[u] + dep1[v] - 2 * dep1[LCA1(u, v)];
	else
		return dep2[u] + dep2[v] - 2 * dep2[LCA2(u, v)];
}
inline void dfs1(int u, int ff) {
	dep11[u] = dep11[ff] + 1;
	f1[dfn1[u] = ++cnt1][0] = ff;
	rev1[cnt1] = u;
	sz1[u] = 1;
	for (int i = 1; i <= 20; i++)
		st1[u][i] = st1[st1[u][i - 1]][i - 1], jp1[u][i] = jp1[u][i - 1] + jp1[st1[u][i - 1]][i - 1];
	for (auto to : G1[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		dep1[v] = dep1[u] + w;
		st1[v][0] = u, jp1[v][0] = w;
		dfs1(v, u);
		sz1[u] += sz1[v];
		if (sz1[v] > sz1[son1[u]])
			son1[u] = v;
	}
}
inline void dfs11(int u, int ff) {
	if (son1[u]) {
		seg1[son1[u]] = ++seg1[0];
		top1[son1[u]] = top1[u];
		rev11[seg1[0]] = son1[u];
		dfs11(son1[u], u);
	}
	for (auto to : G1[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		if (!top1[v]) {
			seg1[v] = ++seg1[0];
			top1[v] = v;
			rev11[seg1[0]] = v;
			dfs11(v, u);
		}
	}
}
inline void dfs2(int u, int ff) {
	dep22[u] = dep22[ff] + 1;
	f2[dfn2[u] = ++cnt2][0] = ff;
	rev2[cnt2] = u;
	sz2[u] = 1;
	for (int i = 1; i <= 20; i++)
		st2[u][i] = st2[st2[u][i - 1]][i - 1], jp2[u][i] = jp2[u][i - 1] + jp2[st2[u][i - 1]][i - 1];
	for (auto to : G2[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		dep2[v] = dep2[u] + w;
		st2[v][0] = u, jp2[v][0] = w;
		dfs2(v, u);
		sz2[u] += sz2[v];
		if (sz2[v] > sz2[son2[u]])
			son2[u] = v;
	}
}
inline void dfs22(int u, int ff) {
	if (son2[u]) {
		seg2[son2[u]] = ++seg2[0];
		top2[son2[u]] = top2[u];
		rev22[seg2[0]] = son2[u];
		dfs22(son2[u], u);
	}
	for (auto to : G2[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		if (!top2[v]) {
			seg2[v] = ++seg2[0];
			top2[v] = v;
			rev22[seg2[0]] = v;
			dfs22(v, u);
		}
	}
}
struct node2 {
	pp u, v;
} t[400005], po1[100005], po2[100005];
LL tag[400005];
#define ls(u) u << 1
#define rs(u) u << 1 | 1
inline node2 merge(int op, node2 A, node2 B) {
	node2 tmp;
	LL res = -1;
	LL d1 =
		(A.u.first == A.v.first ? A.u.second : A.u.second + A.v.second) + getdis(op, A.u.first, A.v.first);
	LL d2 =
		(B.u.first == B.v.first ? B.u.second : B.u.second + B.v.second) + getdis(op, B.u.first, B.v.first);
	LL d3 =
		(A.u.first == B.v.first ? A.u.second : A.u.second + B.v.second) + getdis(op, A.u.first, B.v.first);
	LL d4 =
		(B.u.first == A.v.first ? B.u.second : B.u.second + A.v.second) + getdis(op, B.u.first, A.v.first);
	LL d5 =
		(A.u.first == B.u.first ? A.u.second : A.u.second + B.u.second) + getdis(op, A.u.first, B.u.first);
	LL d6 =
		(A.v.first == B.v.first ? A.v.second : A.v.second + B.v.second) + getdis(op, A.v.first, B.v.first);
	res = max(d1, d2), res = max(res, max(d3, d4)), res = max(res, max(d5, d6));
	if (d1 == res)
		tmp = node2{ A.u, A.v };
	if (d2 == res)
		tmp = node2{ B.u, B.v };
	if (d3 == res)
		tmp = node2{ A.u, B.v };
	if (d4 == res)
		tmp = node2{ B.u, A.v };
	if (d5 == res)
		tmp = node2{ A.u, B.u };
	if (d6 == res)
		tmp = node2{ A.v, B.v };
	return tmp;
}
inline void push_down(int u) {
	if (tag[u]) {
		tag[ls(u)] += tag[u];
		tag[rs(u)] += tag[u];
		t[ls(u)].u.second += tag[u];
		t[ls(u)].v.second += tag[u];
		t[rs(u)].u.second += tag[u];
		t[rs(u)].v.second += tag[u];
		tag[u] = 0;
	}
}
inline void updata(int op, int p, int l, int r, int L, int R, int w) {
	if (L > R)
		return;
	if (L <= l && r <= R) {
		tag[p] += w;
		t[p].u.second += w;
		t[p].v.second += w;
		return;
	}
	push_down(p);
	int mid = (l + r) >> 1;
	if (L <= mid)
		updata(op, ls(p), l, mid, L, R, w);
	if (mid + 1 <= R)
		updata(op, rs(p), mid + 1, r, L, R, w);
	t[p] = merge(op, t[ls(p)], t[rs(p)]);
}
inline void build(int op, int p, int l, int r) {
	tag[p] = 0;
	if (l == r) {
		if (op == 2)
			t[p].u = t[p].v = pp(rev1[l], dep1[rev1[l]]);
		else
			t[p].u = t[p].v = pp(rev2[l], dep2[rev2[l]]);
		return;
	}
	int mid = (l + r) >> 1;
	build(op, ls(p), l, mid);
	build(op, rs(p), mid + 1, r);
	t[p] = merge(op, t[ls(p)], t[rs(p)]);
}
inline void redfs1(int u, int ff) {
	po1[u] = t[1];
	for (auto to : G1[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		updata(2, 1, 1, n, dfn1[v], dfn1[v] + sz1[v] - 1, -w);
		updata(2, 1, 1, n, 1, dfn1[v] - 1, w);
		updata(2, 1, 1, n, dfn1[v] + sz1[v], n, w);
		redfs1(v, u);
		updata(2, 1, 1, n, dfn1[v], dfn1[v] + sz1[v] - 1, w);
		updata(2, 1, 1, n, 1, dfn1[v] - 1, -w);
		updata(2, 1, 1, n, dfn1[v] + sz1[v], n, -w);
	}
}
inline void redfs2(int u, int ff) {
	po2[u] = t[1];
	for (auto to : G2[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		updata(1, 1, 1, n, dfn2[v], dfn2[v] + sz2[v] - 1, -w);
		updata(1, 1, 1, n, 1, dfn2[v] - 1, w);
		updata(1, 1, 1, n, dfn2[v] + sz2[v], n, w);
		redfs2(v, u);
		updata(1, 1, 1, n, dfn2[v], dfn2[v] + sz2[v] - 1, w);
		updata(1, 1, 1, n, 1, dfn2[v] - 1, -w);
		updata(1, 1, 1, n, dfn2[v] + sz2[v], n, -w);
	}
}
inline void dfss1(int u, int ff) {
	g1[u].init();
	wg1[u].init();
	Add(g1[u], pp(0, id1[u]));
	for (auto to : G1[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		dfss1(v, u);
		Add(g1[u], pp(g1[v].mi1.first + w, g1[v].mi1.second));
		Add(g1[u], pp(g1[v].mi2.first + w, g1[v].mi2.second));
	}
}
inline void redfss1(int u, int ff) {
	node3 pre;
	pre.init();
	Add(wg1[u], pp(0, id1[u]));
	for (auto to : G1[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		Add(wg1[v], pp(wg1[u].mi1.first + w, wg1[u].mi1.second));
		Add(wg1[v], pp(wg1[u].mi2.first + w, wg1[u].mi2.second));
		Add(wg1[v], pp(pre.mi1.first + w, pre.mi1.second));
		Add(wg1[v], pp(pre.mi2.first + w, pre.mi2.second));
		Add(pre, pp(g1[v].mi1.first + w, g1[v].mi1.second));
		Add(pre, pp(g1[v].mi2.first + w, g1[v].mi2.second));
	}
	reverse(G1[u].begin(), G1[u].end());
	pre.init();
	for (auto to : G1[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		Add(wg1[v], pp(pre.mi1.first + w, pre.mi1.second));
		Add(wg1[v], pp(pre.mi2.first + w, pre.mi2.second));
		Add(pre, pp(g1[v].mi1.first + w, g1[v].mi1.second));
		Add(pre, pp(g1[v].mi2.first + w, g1[v].mi2.second));
	}
	reverse(G1[u].begin(), G1[u].end());
	for (auto to : G1[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		redfss1(v, u);
	}
}
inline void dfss2(int u, int ff) {
	g2[u].init();
	wg2[u].init();
	Add(g2[u], pp(0, id2[u]));
	for (auto to : G2[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		dfss2(v, u);
		Add(g2[u], pp(g2[v].mi1.first + w, g2[v].mi1.second));
		Add(g2[u], pp(g2[v].mi2.first + w, g2[v].mi2.second));
	}
}
inline void redfss2(int u, int ff) {
	node3 pre;
	pre.init();
	Add(wg2[u], pp(0, id2[u]));
	for (auto to : G2[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		Add(wg2[v], pp(wg2[u].mi1.first + w, wg2[u].mi1.second));
		Add(wg2[v], pp(wg2[u].mi2.first + w, wg2[u].mi2.second));
		Add(wg2[v], pp(pre.mi1.first + w, pre.mi1.second));
		Add(wg2[v], pp(pre.mi2.first + w, pre.mi2.second));
		Add(pre, pp(g2[v].mi1.first + w, g2[v].mi1.second));
		Add(pre, pp(g2[v].mi2.first + w, g2[v].mi2.second));
	}
	reverse(G2[u].begin(), G2[u].end());
	pre.init();
	for (auto to : G2[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		Add(wg2[v], pp(pre.mi1.first + w, pre.mi1.second));
		Add(wg2[v], pp(pre.mi2.first + w, pre.mi2.second));
		Add(pre, pp(g2[v].mi1.first + w, g2[v].mi1.second));
		Add(pre, pp(g2[v].mi2.first + w, g2[v].mi2.second));
	}
	reverse(G2[u].begin(), G2[u].end());
	for (auto to : G2[u]) {
		int v = to.to, w = to.w;
		if (v == ff)
			continue;
		redfss2(v, u);
	}
}
inline node3 query22(int op, int u, int v, LL ex) {
	int fu = top2[u], fv = top2[v];
	node3 res;
	res.init();
	while (fu != fv) {
		if (dep22[fu] >= dep22[fv]) {
			node3 tmp = T2[op].query(seg2[fu], seg2[u]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
			u = st2[fu][0];
		} else {
			node3 tmp = T2[op].query(seg2[fv], seg2[v]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
			v = st2[fv][0];
		}
		fu = top2[u], fv = top2[v];
	}
	if (dep22[u] > dep22[v])
		swap(u, v);
	node3 tmp = T2[op].query(seg2[u], seg2[v]);
	Add(res, tmp.mi1), Add(res, tmp.mi2);
	return node3{ pp(res.mi1.first + ex, res.mi1.second), pp(res.mi2.first + ex, res.mi2.second) };
}
inline pp query2(int u, int v, LL w1, LL w2, int c) {  //��ɫ������ c
	int lca = LCA2(u, v);
	//	if(lca!=1)cerr<<lca<<" "<<"FUCK"<<endl;
	int to = u;
	LL sum = w1, tot = getdis(2, u, v) + w1 + w2;
	node3 res, tmp;
	res.init();
	LL ex = max(getdis(2, u, lca) + w1, getdis(2, v, lca) + w2);
	Add(res, pp(wg2[lca].mi1.first + ex, wg2[lca].mi1.second));
	Add(res, pp(wg2[lca].mi2.first + ex, wg2[lca].mi2.second));
	if (w1 >= tot - w1) {
		node3 tmp;
		tmp = query22(1, u, lca, w1 + dep2[u]);
		Add(res, tmp.mi1), Add(res, tmp.mi2);
	} else {
		for (int i = 20; i >= 0; i--) {
			if (sum + jp2[to][i] <= tot - sum - jp2[to][i]) {
				sum += jp2[to][i];
				to = st2[to][i];
			}
		}
		node3 tmp;
		if (dep22[to] <= dep22[lca]) {  //ȫ���� v ��
			tmp = query22(0, u, lca, w2 + dep2[v] - 2 * dep2[lca]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
		} else {
			tmp = query22(0, u, to, w2 + dep2[v] - 2 * dep2[lca]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
			tmp = query22(1, st2[to][0], lca, w1 + dep2[u]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
		}
	}
	to = v;
	sum = w2;
	if (w2 >= tot - w2) {
		tmp = query22(1, v, lca, w2 + dep2[v]);
		Add(res, tmp.mi1), Add(res, tmp.mi2);
	} else {
		for (int i = 20; i >= 0; i--) {
			if (sum + jp2[to][i] <= tot - sum - jp2[to][i]) {
				sum += jp2[to][i];
				to = st2[to][i];
			}
		}
		if (dep22[to] <= dep22[lca]) {  //ȫ���� u ��
			tmp = query22(0, v, lca, w1 + dep2[u] - 2 * dep2[lca]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
		} else {
			tmp = query22(0, v, to, w1 + dep2[u] - 2 * dep2[lca]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
			tmp = query22(1, st2[to][0], lca, w2 + dep2[v]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
		}
	}
	if (res.mi1.second == c)
		return res.mi2;
	return res.mi1;
}
inline node3 query11(int op, int u, int v, LL ex) {
	int fu = top1[u], fv = top1[v];
	node3 res;
	res.init();
	while (fu != fv) {
		if (dep11[fu] >= dep11[fv]) {
			node3 tmp = T1[op].query(seg1[fu], seg1[u]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
			u = st1[fu][0];
		} else {
			node3 tmp = T1[op].query(seg1[fv], seg1[v]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
			v = st1[fv][0];
		}
		fu = top1[u], fv = top1[v];
	}
	if (dep11[u] > dep11[v])
		swap(u, v);
	node3 tmp = T1[op].query(seg1[u], seg1[v]);
	Add(res, tmp.mi1), Add(res, tmp.mi2);
	return node3{ pp(res.mi1.first + ex, res.mi1.second), pp(res.mi2.first + ex, res.mi2.second) };
}
inline pp query1(int u, int v, LL w1, LL w2, int c) {  //��ɫ������ c
	int lca = LCA1(u, v);
	//	if(lca!=1)cerr<<lca<<" "<<"FUCK"<<endl;
	int to = u;
	LL sum = w1, tot = getdis(1, u, v) + w1 + w2;
	node3 res, tmp;
	res.init();
	LL ex = max(getdis(1, u, lca) + w1, getdis(1, v, lca) + w2);
	Add(res, pp(wg1[lca].mi1.first + ex, wg1[lca].mi1.second));
	Add(res, pp(wg1[lca].mi2.first + ex, wg1[lca].mi2.second));
	if (w1 >= tot - w1) {
		tmp = query11(1, u, lca, w1 + dep1[u]);
		Add(res, tmp.mi1), Add(res, tmp.mi2);
	} else {
		for (int i = 20; i >= 0; i--) {
			if (sum + jp1[to][i] <= tot - sum - jp1[to][i]) {
				sum += jp1[to][i];
				to = st1[to][i];
			}
		}
		node3 tmp;
		if (dep11[to] <= dep11[lca]) {  //ȫ���� v ��
			tmp = query11(0, u, lca, w2 + dep1[v] - 2 * dep1[lca]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
		} else {
			tmp = query11(0, u, to, w2 + dep1[v] - 2 * dep1[lca]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
			tmp = query11(1, st1[to][0], lca, w1 + dep1[u]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
		}
	}
	to = v;
	sum = w2;
	if (w2 >= tot - w2) {
		node3 tmp;
		tmp = query11(1, v, lca, w2 + dep1[v]);
		Add(res, tmp.mi1), Add(res, tmp.mi2);
	} else {
		for (int i = 20; i >= 0; i--) {
			if (sum + jp1[to][i] <= tot - sum - jp1[to][i]) {
				sum += jp1[to][i];
				to = st1[to][i];
			}
		}
		if (dep11[to] <= dep11[lca]) {  //ȫ���� u ��
			tmp = query11(0, v, lca, w1 + dep1[u] - 2 * dep1[lca]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
		} else {
			tmp = query11(0, v, to, w1 + dep1[u] - 2 * dep1[lca]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
			tmp = query11(1, st1[to][0], lca, w2 + dep1[v]);
			Add(res, tmp.mi1), Add(res, tmp.mi2);
		}
	}
	if (res.mi1.second == c)
		return res.mi2;
	return res.mi1;
}
inline void solve() {
	for (int i = 2; i <= 100000; i++) Log[i] = Log[i >> 1] + 1;
	gi(n);
	for (int i = 1; i < n; i++) {
		int u, v, w;
		gi(u), gi(v), gi(w);
		G1[u].push_back(node{ v, w });
		G1[v].push_back(node{ u, w });
	}
	for (int i = 1; i < n; i++) {
		int u, v, w;
		gi(u), gi(v), gi(w);
		G2[u].push_back(node{ v, w });
		G2[v].push_back(node{ u, w });
	}
	seg1[0] = seg1[1] = top1[1] = rev11[1] = 1;
	seg2[0] = seg2[1] = top2[1] = rev22[1] = 1;
	dfs1(1, 0), dfs2(1, 0), dfs11(1, 0), dfs22(1, 0);
	for (int j = 1; (1 << j) <= cnt1; j++)
		for (int i = 1; i + (1 << j) - 1 <= cnt1; i++)
			f1[i][j] = Min1(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
	for (int j = 1; (1 << j) <= cnt2; j++)
		for (int i = 1; i + (1 << j) - 1 <= cnt2; i++)
			f2[i][j] = Min2(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
	build(2, 1, 1, n);
	redfs1(1, 0);
	build(1, 1, 1, n);
	redfs2(1, 0);
	for (int i = 1; i <= 2 * n; i++) fa[i] = i;
	int cnt = 2 * n;
	LL ans = 0;
	while (cnt > 1) {
		for (int i = 1; i <= n; i++) id1[i] = findSet(i), mn[i] = pp(INF, 0);
		for (int i = 1; i <= n; i++) id2[i] = findSet(i + n), mn[i + n] = pp(INF, 0);
		dfss1(1, 0), dfss2(1, 0);
		redfss1(1, 0), redfss2(1, 0);
		for (int i = 1; i <= n; i++) {
			int u = rev11[i], v = rev22[i];
			T1[0].f[i][0].mi1 = pp(g1[u].mi1.first + dep1[u], g1[u].mi1.second);
			T1[0].f[i][0].mi2 = pp(g1[u].mi2.first + dep1[u], g1[u].mi2.second);
			T1[1].f[i][0].mi1 = pp(g1[u].mi1.first - dep1[u], g1[u].mi1.second);
			T1[1].f[i][0].mi2 = pp(g1[u].mi2.first - dep1[u], g1[u].mi2.second);

			T2[0].f[i][0].mi1 = pp(g2[v].mi1.first + dep2[v], g2[v].mi1.second);
			T2[0].f[i][0].mi2 = pp(g2[v].mi2.first + dep2[v], g2[v].mi2.second);
			T2[1].f[i][0].mi1 = pp(g2[v].mi1.first - dep2[v], g2[v].mi1.second);
			T2[1].f[i][0].mi2 = pp(g2[v].mi2.first - dep2[v], g2[v].mi2.second);
		}
		T1[0].init(n), T2[0].init(n), T1[1].init(n), T2[1].init(n);
		for (int i = 1; i <= n; i++) {
			int u = po1[i].u.first, v = po1[i].v.first;
			LL w1 = po1[i].u.second, w2 = po1[i].v.second;
			mn[id1[i]] = min(mn[id1[i]], query2(u, v, w1, w2, id1[i]));
		}
		for (int i = 1; i <= n; i++) {
			int u = po2[i].u.first, v = po2[i].v.first;
			LL w1 = po2[i].u.second, w2 = po2[i].v.second;
			mn[id2[i]] = min(mn[id2[i]], query1(u, v, w1, w2, id2[i]));
		}
		for (int i = 1; i <= 2 * n; i++) {
			if (mn[i].second) {
				int u = i, v = mn[i].second;
				u = findSet(u), v = findSet(v);
				if (u != v) {
					fa[v] = u;
					ans += mn[i].first;
					cnt--;
				}
			}
		}
		//	cerr<<cnt<<endl;
	}
	pi(ans);
}
/*
Ҫһ������
*/
signed main() {
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	srand(time(0));
	solve();
	return 0;
}
/*
*/

\(T4\) D. 山峦 \(40pts/40pts/35pts\)

  • 部分分

    • 测试点 \(1,2,3,10,11,12\) ：爆搜。

      点击查看代码 
      const ll p=998244353;
ll h[15][15],c[15],ans[310];
void dfs(ll x,ll y,ll n,ll m,ll sum)
{
	if(x>n)
	{
		return;
	}
	if(x==n&&y==c[x])
	{
		if(y==1)
		{
			h[x][y]=c[x];
			if(sum+h[x][y]<=m)
			{
				ans[sum+h[x][y]]=(ans[sum+h[x][y]]+1)%p;	
			}
		}
		else
		{
			for(ll i=1;i<=min(h[x-1][y],h[x][y-1])&&sum+i<=m;i++)
			{
				h[x][y]=i;
				ans[sum+i]=(ans[sum+i]+1)%p;
			}
		}
	}
	else
	{
		if(y==1)
		{
			h[x][y]=c[x];
			if(sum+h[x][y]<=m)
			{
				if(y==c[x])
				{
					dfs(x+1,1,n,m,sum+h[x][y]);
				}
				else
				{
					dfs(x,y+1,n,m,sum+h[x][y]);
				}
			}
		}
		else
		{
			for(ll i=1;i<=min(h[x-1][y],h[x][y-1])&&sum+i<=m;i++)
			{
				h[x][y]=i;
				if(y==c[x])
				{
					dfs(x+1,1,n,m,sum+h[x][y]);
				}
				else
				{
					dfs(x,y+1,n,m,sum+h[x][y]);
				}
			}
		}
	}
}
int main()
{
	freopen("mountain.in","r",stdin);
	freopen("mountain.out","w",stdout);
	ll n,m,i;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&c[i]);
	}
	memset(h[0],0x3f,sizeof(h[0]));
	dfs(1,1,n,m,0);
	for(i=1;i<=m;i++)
	{
		printf("%lld ",ans[i]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

  • 正解

    • 不会高维前缀和，先咕了。

    点击查看代码 
    #include <cstdio>
#include <map>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
#include <stack>
#include <cstring>
#include <ctime>
#include <cmath>
#include <assert.h>
using namespace std;
#define LL long long
#define pp pair<int, int>
#define mp make_pair
#define ull unsigned long long
namespace IO {
const int sz = 1 << 22;
char a[sz + 5], b[sz + 5], *p1 = a, *p2 = a, *t = b, p[105];
inline char gc() {
	//	return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
	return getchar();
}
template <class T>
void gi(T& x) {
	x = 0;
	int f = 1;
	char c = gc();
	if (c == '-')
		f = -1;
	for (; c < '0' || c > '9'; c = gc())
		if (c == '-')
			f = -1;
	for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
	x = x * f;
}
inline void flush() { fwrite(b, 1, t - b, stdout), t = b; }
inline void pc(char x) {
	*t++ = x;
	if (t - b == sz)
		flush();
}
template <class T>
void pi(T x, char c = '\n') {
	if (x < 0)
		pc('-'), x = -x;
	if (x == 0)
		pc('0');
	int t = 0;
	for (; x; x /= 10) p[++t] = x % 10 + '0';
	for (; t; --t) pc(p[t]);
	pc(c);
}
struct F {
	~F() { flush(); }
} f;
}  // namespace IO
using IO::gi;
using IO::pc;
using IO::pi;
const int mod = 998244353;
inline int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int dec(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int qkpow(int a, LL b) {
	if (b < 0)
		return 0;
	int ans = 1, base = a % mod;
	while (b) {
		if (b & 1)
			ans = 1ll * ans * base % mod;
		base = 1ll * base * base % mod;
		b >>= 1;
	}
	return ans;
}
int fac[1000005], inv[1000005], Invn[600005];
inline int C(int n, int m) {
	if (n < m || m < 0)
		return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void init_C(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[0] = 1;
	inv[n] = qkpow(fac[n], mod - 2);
	for (int i = n - 1; i >= 1; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
	Invn[0] = Invn[1] = 1;
	for (int i = 1; i <= 200000; i++) Invn[i] = (LL)(mod - mod / i) * Invn[mod % i] % mod;
}
int n, h, l[15], b[25], Len[15], res;
LL pw[15];
int dp[11][60005][305], pre[60005][305];
map<LL, int> Id[15];
struct node {
	int id;
	int w, b[15];
} a[11][60005];
vector<pp> G[15][15][15];
inline void dfs(int lim, int y, int tot, int lst) {
	if (tot > n)
		return;
	if (y == 0) {
		Len[lim]++;
		a[lim][Len[lim]].w = tot;
		LL S = 0;
		for (int i = 2; i <= lim; i++) S += 1ll * pw[i - 2] * (b[i] - 1);
		a[lim][Len[lim]].id = S;
		for (int i = 2; i <= lim; i++) a[lim][Len[lim]].b[i] = b[i] - 1;
		Id[lim][S] = Len[lim];
		return;
	}
	if (y == 1)
		b[y] = lim, dfs(lim, y - 1, tot, 1);
	else {
		for (int i = lst; i <= lim; i++) {
			b[y] = i;
			dfs(lim, y - 1, tot + i, i);
		}
	}
}
signed main() {
	freopen("mountain.in", "r", stdin);
	freopen("mountain.out", "w", stdout);
	pw[0] = 1;
	for (int i = 1; i <= 10; i++) pw[i] = 1ll * pw[i - 1] * 9;
	gi(h), gi(n);
	int ex = 0;
	for (int i = 1; i <= h; i++) gi(l[i]), ex += l[i];
	if (ex > n) {
		for (int i = 1; i <= n; i++) pi(0, ' ');
		return 0;
	}
	n -= ex;
	for (int i = 1; i <= 10; i++) {
		dfs(i, i, 0, 1);
		for (int j = 2; j <= i; j++) {
			for (int k = 1; k <= Len[i]; k++) {
				int x = a[i][k].b[j];
				LL nS = 0;
				if (x == i - 1)
					continue;
				for (int p = 2; p <= i; p++) {
					if (p < j)
						nS += 1ll * pw[p - 2] * max(a[i][k].b[p], x + 1);
					else if (p == j)
						nS += 1ll * pw[p - 2] * (x + 1);
					else
						nS += 1ll * pw[p - 2] * a[i][k].b[p];
				}
				if (Id[i].find(nS) != Id[i].end())
					G[i][j][x].push_back(pp(k, Id[i][nS]));
			}
		}
	}
	for (int i = 1; i <= h; i++) {
		if (i == 1) {
			for (int j = 1; j <= Len[l[i]]; j++) dp[i][j][a[l[i]][j].w]++;
		} else {
			for (int j = 1; j <= Len[l[i]]; j++)
				for (int k = 0; k <= n; k++) pre[j][k] = 0;
			for (int j = 1; j <= Len[l[i - 1]]; j++) {
				LL S = 0;
				for (int k = 2; k <= l[i]; k++) S += 1ll * pw[k - 2] * min(a[l[i - 1]][j].b[k], l[i] - 1);
				S = Id[l[i]][S];
				for (int k = 0; k <= n; k++) pre[S][k] = add(pre[S][k], dp[i - 1][j][k]);
			}
			for (int j = 2; j <= l[i]; j++) {
				for (int k = l[i] - 1; k >= 0; k--) {
					for (int p = 0; p < G[l[i]][j][k].size(); p++) {
						int id1 = G[l[i]][j][k][p].first;
						int id2 = G[l[i]][j][k][p].second;
						for (int p2 = 0; p2 <= n; p2++) pre[id1][p2] = add(pre[id1][p2], pre[id2][p2]);
					}
				}
			}
			for (int j = 1; j <= Len[l[i]]; j++) {
				int w = a[l[i]][j].w;
				for (int k = 0; k <= n - w; k++) {
					dp[i][j][k + w] = add(dp[i][j][k + w], pre[j][k]);
				}
			}
		}
	}
	for (int i = 1; i < ex; i++) pi(0, ' ');
	for (int p = 0; p <= n; p++) {
		res = 0;
		for (int i = 1; i <= Len[l[h]]; i++) res = add(res, dp[h][i][p]);
		pi(res, ' ');
	}
	return 0;
}
/*
2 2
2 2
*/

总结

  • \(T2\) 想到正难则反，但没发现重要结论，不会设状态。
  • \(T3\) 测 \(n \le 2000\) 的数据时，将树剖求 \(\operatorname{LCA}\) 换成了 \(DFS\) 序求 \(\operatorname{LCA}\) ，但优化不明显（下发的样例仅快了 \(2s\)） 。

标签：11,pp,int,多校,Add,mi1,mi2,NOIP2024,first
From： https://www.cnblogs.com/The-Shadow-Dragon/p/18493299

相关文章

  • YOLOv11模型改进-注意力-引入简单无参数注意力模块SimAM 提升小目标和遮挡检测
                本篇文章将介绍一个新的改进机制——卷积和注意力融合模块SimAM ，并阐述如何将其应用于YOLOv11中，显著提升模型性能。首先，SimAM是一种用于卷积神经网络的简单且无参数的注意力模块，它基于神经科学理论定义能量函数来计算3-D注意力权重，能有效提升网络......
  • 2024牛客暑期多校训练营9 - VP记录
    A.ImageScaling签到题，找出举行宽高以后直接除以它们的\(\gcd\)使它们互质即可。（这道题居然会有人又WA又RE，我不说是谁）点击查看代码#include<cstdio>#include<cstring>usingnamespacestd;constintN=505;intn,m,x1,y1,x2,y2;charg[N][N];intgcd(intx,int......
  • 多校A层冲刺NOIP2024模拟赛11
    又双叒叕垫底了。rank11，T190，T212，T35，T435。accdoer上rank44，T1100，T20，T35，T435。难度难评，T1签，剩下的不可做？死磕T3了，猜一个结论假一个，打完暴力遗憾离场。好像两个题库都挂了几分，不管了，赛前挂分RP就++。慢报：5k_sync_closer成功地取得了NFLS模拟赛第一名的好成绩。冒泡......
  • Docker 部署 JDK11 图文并茂简单易懂
    部署JDK11(Docker)[Step1]:下载JDK11-JDK11|Oracle甲骨文官网[Step2]:jdk11上传服务器/root/jdk11可自行创建文件夹进入目录/root/jdk11解压文件tar-zxvfjdk-11.0.22_linux-x64_bin.tar.gz解压后进入/root/jdk11/jdk-11.0.22创建jre文件......
  • 2024淘宝双十一红包口令大全，双11满300减多少？
    2024年双十一淘宝红包活动已经于10月14日晚上20点正式启动。朋友们都在寻找2024年双十一淘宝领红包的口令。那么，这个神秘的超级红包口令到底是什么呢？让我们一起加入这场购物的盛宴吧！那么，2024最新的的淘宝双十一红包口令到底是什么呢？2024淘宝双十一红包口令是【￥CZ00017DEM3N......
  • 11-案例：多线程版用户聊天程序
    1.多线程版用户群聊程序的_多用户聊天运行结果２.多线程版用户群聊程序的_服务端代码３.多线程版用户群聊程序的_客户端代码４.多线程版用户群聊程序的_双用户聊天运行结果５.多线程版用户群聊程序的_双用户聊天运行服务端代码６.多线程版用户群聊程序的_双用户聊天运行客户端代码......
  • Win11安装WSL2，自定WSL2安装位置，安装到其他磁盘(非C盘)
    参考：【Linux】自定义WSL2安装位置，安装到其他磁盘(非C盘)_wsl2指定安装路径-CSDN博客超详细Windows10/Windows11子系统（WSL2）安装Ubuntu20.04（带桌面环境）_wsl安装ubuntu20.04-CSDN博客旧版WSL的手动安装步骤|MicrosoftLearn【安装笔记-20240520-Windows-自定义WSL2安装......
  • 物理学基础精解【115】
    这里写目录标题统计物理学点估计定义性质数学原理公式计算例子例题区间估计（IntervalEstimation）定义性质数学原理公式计算例子例题在统计学中，估计量1.无偏性2.有效性3.一致性4.其他性质总结无偏估计和有偏估计无偏估计定义性质数学原理公式计算例子例题有偏估计......
  • 物理学基础精解【117】
    文章目录微积分无穷级数无穷级数的定义无穷级数的原理无穷级数的性质无穷级数的数学公式无穷级数的计算无穷级数的例子无穷级数的例题柯西判敛法基本原理应用于数列应用于函数序列应用于无穷级数局限性重要性判断级数是否收敛无穷级数收敛与发散无穷级数收敛与发散的定......
  • .netframework3.5安装被拒绝。Win1011系统Windows Update无法启动拒绝访问怎么办？【解
    原文链接：https://blog.csdn.net/qq_44905692/article/details/140434164安装.netframework3.5的时候，提示拒绝。查了下，windows更新服务是需要启动的,根本就找不到启动两个字，设置为自动也提示拒绝。用以下办法，显示了启动两个字，点击又显示1053报错，目前还没解决。打开注册表：1、通......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99