夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

多省省选联考全真模拟考试3

2020-05-03 11 min read # 比赛题 # 线段树合并 # AC自动机 # 矩阵乘法

http://csp.ac/contest/11

最重要的是对998244353取模

加上这个取模就200了qwq

T1

所有区间第k大和

考虑排序之后从小到大删除,然后对于一个数,他能当第k大当且仅当他在删完后的序列中有一个区间包括他同时也正好包括k个点

然后这个过程可以用一个链表维护删除,暴力去维护包括k个点的区间

注意当前删除序列和实际序列的差别,是计数标准

复杂度是O(nk+nlogn)的,跑了最快

T3

51nod原题...带边权联通分量计数

先考虑每个边的贡献,然后补集转换

考虑对于一条边两边的子树,如果一个区间不包括这个边那么一定在某子树有编号连续的一段

所以我们对于一条边,把一边的子树全部标记,就是这个样子的

--------__-----

每一段都用len∗(len+1)/2len*(len+1)/2作为代价求个和就能做完了

但是我们还需要知道怎么快速求这个和以及怎么知道子树标记

裸的线段树合并啊qwq

T2

考场上就看了一眼的题,因为直接想到AC自动机+矩乘,不太可做qwq

第一问建出AC自动机直接搜索就好了,和最短不公共子串一个样

第二问...dp[i][j][S]表示我长度为i,然后走到自动机j号点,然后经过状态为S,并且没有经过那些爆炸点

所以转移直接枚举下一个放什么就好了

然后第一维要是想矩乘的话那不能有三维啊

所以我们要容斥掉第三维qwq怎么容呢

考虑强制硬点走过几个,比如走过一个,我们第二维就到那个点的终止点

然后∑Sg(S)∣S∣\sum_Sg(S)^|S|其中g(S)表示S集合都强制走过一遍方案数

而且我们转移矩阵是G[i][j]表示从i->j号点一步的方案数

如果j是个坏点就设置为0即可

复杂度只有T3lognT^3logn?

完结散花!

code

T1:


//好像有点难写?
//From Dawn light
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
#define ll long long
const int P = 998244353;
const int MAXN = 3e6 + 7;
int n, k;
ll ans;
int nxt[MAXN], pre[MAXN];
int a[MAXN];
struct rec {
	int a, pos;
	bool operator<(const rec &x)const {
		return a < x.a;
	}
} b[MAXN];

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;
inline void init() {
	for(int i = 1; i <= n; ++i) {
		nxt[i] = i + 1;
		pre[i] = i - 1;
	}
	sort(b + 1, b + n + 1);
	//qwq
}

inline void del(int x) {
	pre[nxt[x]] = pre[x];
	nxt[pre[x]] = nxt[x];
}

inline void chuli(int u, int l, int r) {//尺取即可
	for(; l != nxt[u]; l = nxt[l], r = nxt[r]) {
		if(r == n + 1)break;
		ans = (ans + 1ll * (nxt[r] - r) * (l - pre[l]) % P * a[u] % P) % P;
	}
	return ;
}

inline void solve() {
	for(int i = 1; i <= n; ++i) {
		int u = b[i].pos;
		int l = u, r = u;
		int cnt = 0;
		for(cnt = 2; cnt <= k ; ++cnt) {
			// printf("%d %d?\n", l, pre[l]);
			if(pre[l] != 0)l = pre[l];
			else break;
		}
		for(; cnt <= k; ++cnt) {
			if(nxt[r] != n + 1)r = nxt[r];
			else break;
		}
		// printf("%d %d %d? ", cnt, l, r);
		if(cnt > k)chuli(u, l, r);
		// printf("%d! \n", ans);
		del(u);
	}
	// printf("%lld\n", ans);
	return;
}

inline void solve2() {
	for(int i = n; i >= 1; --i) {
		int u = b[i].pos;
		int l = u, r = u;
		int cnt = 0;
		for(cnt = 2; cnt <= k ; ++cnt) {
			// printf("%d %d?\n", l, pre[l]);
			if(pre[l] != 0)l = pre[l];
			else break;
		}
		for(; cnt <= k; ++cnt) {
			if(nxt[r] != n + 1)r = nxt[r];
			else break;
		}
		// printf("%d %d %d? ", cnt, l, r);
		if(cnt > k)chuli(u, l, r);
		// printf("%d! \n", ans);
		del(u);
	}
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("T1.out", "w", stdout);
	n = read();
	k = read();
	for(int i = 1; i <= n; ++i) {
		// scanf("%d", &a[i]);
		a[i] = read();
		b[i].a = a[i];
		b[i].pos = i;
	}
	init();
	solve();
	init();
	solve2();
	// ans = ((ans % P + P) % P);
	printf("%lld\n", ans);
	return 0;
}

T3

#pragma GCC optimize(2)
#pragma G++ optimize(2)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
#define CT const int&
const int MAXN = 2e5 + 7;
const int P = 998244353;
namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;
int ccnt, n;
int home[MAXN], nxt[MAXN], to[MAXN], len[MAXN], dis[MAXN];
inline void ct(CT x, CT y, CT z) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	len[ccnt] = z;
}
ll SUM, ans;
struct rec {
	int l1, r1, l2, r2;
	//记录0/1
	ll s;
	rec(): l1(0), r1(0), l2(0), r2(0), s(0) {}
} tr[MAXN << 4];
namespace seg {
#define mid ((x+y)>>1)
	int ls[MAXN << 4], rs[MAXN << 4], root[MAXN << 4], T;
	inline ll getval(ll x) {
		return x * (x + 1) / 2;//不会爆
	}
	inline rec pushup(rec x, rec y, int lenl, int lenr) { //恶心...
		rec nw;
		// printf("lson %d %d %d %d %d rson %d %d %d %d %d merge \n", x.s, x.l1, x.r1, x.l2, x.r2, y.s, y.l1, y.r1, y.l2, y.r2);
		nw.s = x.s + y.s;
		nw.l1 = x.l1;
		nw.l2 = x.l2;
		nw.r1 = y.r1;
		nw.r2 = y.r2;
		if(x.r1 && y.l1) {
			nw.s -= getval(y.l1) + getval(x.r1);
			nw.s += getval(x.r1 + y.l1);
		}
		if(y.l2 && x.r2) {
			nw.s -= getval(y.l2) + getval(x.r2);
			nw.s += getval(x.r2 + y.l2);
		}
		if(x.l1 == lenl) {
			// puts("QWQ");
			nw.l1 += y.l1;
		}
		if(x.l2 == lenl) {
			nw.l2 += y.l2;
		}
		if(y.r1 == lenr) {
			nw.r1 += x.r1;
		}
		if(y.r2 == lenr) {
			nw.r2 += x.r2;
		}
		// printf("is %d %d %d %d %d\n", nw.s, nw.l1, nw.r1, nw.l2, nw.r2);
		return nw;
	}
	inline void modify(int &k, int x, int y, int pos) {
		if(!k)k = ++T;
		if(x == y) {
			tr[k].l1 = tr[k].r1 = 1;
			tr[k].r2 = tr[k].l2 = 0;
			tr[k].s = 1;
			return ;
		}
		if(pos <= mid)modify(ls[k], x, mid, pos);
		else modify(rs[k], mid + 1, y, pos);
		//单独处理
		if(!ls[k]) {
			ls[k] = ++T;
			tr[T].l2 = tr[T].r2 = mid - x + 1;
			tr[T].s = getval(mid - x + 1);
		}
		if(!rs[k]) {
			rs[k] = ++T;
			tr[T].l2 = tr[T].r2 = y - mid;
			tr[T].s = getval(y - mid);
		}
		// printf("%d %d %d %d :\n", k, x, y, pos);
		tr[k] = pushup(tr[ls[k]], tr[rs[k]], mid - x + 1, y - mid);
	}
#undef mid
#define mid ((l+r)>>1)
	//...
	inline int merge(int x, int y, int l, int r) {
		if(!x || !y)return x + y;
		if(tr[x].l2 == r - l + 1)return y;
		if(tr[y].l2 == r - l + 1)return x;
		// printf("%d %d %d %d %d\n", x, y, l, r, mid);

		ls[x] = merge(ls[x], ls[y], l, mid);
		rs[x] = merge(rs[x], rs[y], mid + 1, r);
		if(!ls[x]) {
			ls[x] = ++T;
			tr[T].l2 = tr[T].r2 = mid - l + 1;
			tr[T].s = getval(mid - l + 1);
		}
		if(!rs[x]) {
			rs[x] = ++T;
			tr[T].l2 = tr[T].r2 = r - mid;
			tr[T].s = getval(r - mid);
		}

		tr[x] = pushup(tr[ls[x]], tr[rs[x]], mid - l + 1, r - mid);
		return x;
	}
}


inline void dfs(int u, int F) {
	// printf("%d %d?\n",  u, F);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v != F) {
			dis[v] = len[i];//每个点考虑父亲的边
			dfs(v, u);
			// printf("?????%d %d? ", u, v);
			seg::root[u] = seg::merge(seg::root[u], seg::root[v], 1, n); //线段树合并
			// printf("???%d\n", seg::root[u]);
		}
	}
	seg::modify(seg::root[u], 1, n, u);
	// printf("%d %d %lld!\n", u, seg::root[u], tr[seg::root[u]].s);
	ans = (ans + (((SUM - tr[seg::root[u]].s) % P + P) % P) * dis[u] % P) % P;
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("T3.out", "w", stdout);
	n = read();
	for(int i = 1, x, y, z; i < n; ++i) {
		x = read();
		y = read();
		z = read();
		// printf("%d %d %d*\n", x, y, z);
		ct(x, y, z);
		ct(y, x, z);
	}
	SUM = 1ll * n * (n + 1) / 2;
	dfs(1, 0);
	printf("%lld\n", ans);
	return 0;
}
Powered by Gridea RSS