526互联

2023-12-23训练总结

发布时间 2023-12-23 16:47:11作者: ZnPdCo

T1 计数

Problem Description

img

Input

img

Output

img

Sample Input Copy

2 10

Sample Output Copy

90

Data Constraint

img

忘记初始化了调了半个小时。

维护 \(f_{i,0/1}\) 表示长度为 \(i\)，最高位为 \(0\) / 不为 \(0\) 的合法方案数。

明显有：

\[f_{i,0}\gets f_{i-1,1} \\ f_{i,1}\gets (f_{i-1,0}+f_{i-1,1})\times(k-1) \]

然后滚动数组就可以直接搞过了。

/**
 * @file 计数.cpp 
 * @tag: #GMOJ #dp
 * @author: ZnPdCo
 * @date: 2023-12-23 16:00:01
 * @problem: https://gmoj.net/senior/#main/show/4630
 **/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
#define N 1810
ll n, k;
struct node {
	ll a[N], len;
	node(ll l = 1) {memset(a, 0, sizeof(a));len = l;}
	friend node operator+(const node &x, const node &y) {
		node z(max(x.len, y.len));
		for(ll i = 1; i <= z.len; i++) {
			z.a[i] += x.a[i] + y.a[i];
			if(z.a[i] >= 10) {
				z.a[i+1] += z.a[i] / 10;
				z.a[i] %= 10;
				if(i+1 > z.len) z.len++;
			}
		}
		return z;
	} 
	friend node operator*(const node &x, const ll &y) {
		node z(x.len);
		for(ll i = 1; i <= z.len; i++) {
			z.a[i] += x.a[i] * y;
			if(z.a[i] >= 10) {
				z.a[i+1] += z.a[i] / 10;
				z.a[i] %= 10;
				if(i+1 > z.len) z.len++;
			}
		}
		return z;
	} 
	void put() {
		bool flag = false;
		for(ll i = len; i >= 1; i--) {
			if(a[i] || flag) {
				flag = true;
				printf("%lld", a[i]);
			}
		}
	}
} f[2][2], ans;
// f[i][0] 最高位为0，f[i][1] 最高位不为0
int main() {
	scanf("%lld %lld", &n, &k);
	f[1][0].a[1] = 1;
	f[1][1].a[1] = k-1;
	for(ll i = 2; i <= n; i++) {
		memset(f[i%2][0].a, 0, sizeof(f[i%2][0].a));
		f[i%2][0].len = 1;
		memset(f[i%2][1].a, 0, sizeof(f[i%2][1].a));
		f[i%2][1].len = 1;
		
		f[i%2][0] = f[(i-1)%2][1];
		f[i%2][1] = (f[(i-1)%2][0] + f[(i-1)%2][1]) * (k-1ll);
	}
	ans = f[n%2][1];
	ans.put();
}

T2 跳楼机

Problem Description

DJL为了避免成为一只咸鱼，来找srwudi学习压代码的技巧。
Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi改造了一个跳楼机，使得访客可以更方便的上楼。
经过改造，srwudi的跳楼机可以采用以下四种方式移动：
1、向上移动x层；
2、向上移动y层；
3、向上移动z层；
4、回到第一层。
一个月黑风高的大中午，DJL来到了srwudi的家，现在他在srwudi家的第一层，碰巧跳楼机也在第一层。DJL想知道，他可以乘坐跳楼机前往的楼层数。

Input

第一行一个整数h，表示摩天大楼的层数。
第二行三个正整数，分别表示题目中的x, y, z。

Output

一行一个整数，表示DJL可以到达的楼层数。

Sample Input Copy

15
4 7 9

Sample Output Copy

9
样例解释
可以到达的楼层有：1,5,8,9,10,12,13,14,15

Data Constraint

对于20%的数据，1≤h, x, y, z≤100；
对于40%的数据，1≤h, x, y, z≤10^5；
对于100%的数据，1≤h≤10^18，1≤x, y, z≤10^5。

在做这题前连同余最短路都不知道。

维护 \(d_i\) 表示只用操作 2、3 满足 \(a \bmod x = i\) 的最小的 \(a\)。

明显有 \(d_{(i+y)\bmod x}\gets d_i+y\)，\(d_{(i+z)\bmod x}\gets d_i+z\)，最后的答案就是 \(\lfloor\frac{h-d_i}{x}\rfloor+1\)，可以看作是直接在 \(d_i\) 开跑，然后合法的有 \(d_i,d_i+x,d_i+2x,\cdots\)。

该多补补了。

/**
 * @file 跳楼机.cpp 
 * @tag: #GMOJ #同余最短路
 * @author: ZnPdCo
 * @date: 2023-12-23 16:03:06
 * @problem: https://gmoj.net/senior/#main/show/4722
 **/
#include <cstdio>
#include <queue>
#define ll long long
using namespace std;
ll h, x, y, z, ans;
ll f[100010];

ll head[100010];
ll nxt[200010];
ll cost[200010];
ll to[200010], cnt;
void addEdge(ll u, ll v, ll w) {
	cnt++;
	to[cnt] = v;
	cost[cnt] = w;
	nxt[cnt] = head[u];
	head[u] = cnt;
}
ll dis[100010];
ll vis[100010];
priority_queue<pair<ll,ll> > que;
void dij() {
	for(ll i = 0; i < x; i++) dis[i] = h+1;
	dis[0] = 0;
	que.push(make_pair(0, 0));
	while(!que.empty()) {
		ll u = que.top().second;
		que.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(ll i = head[u]; i; i = nxt[i]) {
			ll v = to[i];
			if(!vis[v]) {
				if(dis[v] > dis[u] + cost[i]) {
					dis[v] = dis[u] + cost[i];
					que.push(make_pair(-dis[v], v));
				}
			}
		}
	}
}
int main() {
	scanf("%lld%lld%lld%lld", &h, &x, &y, &z);
	h--;
	for(ll i = 0; i < x; i++) {
		addEdge(i, (i+y)%x, y);
		addEdge(i, (i+z)%x, z);
	}
	dij();
	for(ll i = 0; i < x; i++) {
		if(dis[i] <= h) ans += (h - dis[i]) / x + 1;
	}
	printf("%lld", ans);
}

T3 立方体

Problem Description

img

Input

img

Output

img

Sample Input Copy

e2 e3 0 8 1 2 1 1

Sample Output Copy

5

Data Constraint

img

难道这就是 T3 大模拟定律？

这题锻炼的是折纸能力，考场上一定要动手。

发现一个立方体摆放情况只需要相邻的两个面的编号（共 \(24\) 种情况），共然后再预处理出 \(24\) 种情况向上向下向左向右滚变成的情况（共 \(24\times4=96\) 种情况），然后对于国际象棋棋盘的每个点的每种情况共 \(8\times8\times24=\text{不超过一万}\)，再向上向下向左向右连边，代价就是转过去之后最下面的价值，然后跑迪杰斯特拉就好了。

/**
 * @file 立方体.cpp 
 * @tag: #GMOJ #大模拟 #最短路
 * @author: ZnPdCo
 * @date: 2023-12-23 16:02:14
 * @problem: https://gmoj.net/senior/#main/show/4628
 **/
#include <cstdio>
#include <queue>
#define ll long long
#define F 1
#define B 2
#define U 3
#define D 4
#define L 5
#define R 6
#define FU 1
#define FD 2
#define FL 3
#define FR 4
#define BU 5
#define BD 6
#define BL 7
#define BR 8
#define UF 9
#define UB 10
#define UL 11
#define UR 12
#define DF 13
#define DB 14
#define DL 15
#define DR 16
#define LF 17
#define LB 18
#define LU 19
#define LD 20
#define RF 21
#define RB 22
#define RU 23
#define RD 24
using namespace std;

struct node {
	ll up;
	ll down;
	ll left;
	ll right;
	ll me;
	bool flag;
	node(ll u=0, ll d=0, ll l=0, ll r=0, ll m=0) {
		up = u;
		down = d;
		left = l;
		right = r;
		me = m;
		flag = true;
	}
} a[10][10];

ll num[10];





char st[10], ed[10];

ll stx, sty, edx, edy; // 定义，x、i是行，y、j是列

ll zip(ll x, ll y, ll s) {
	return s * 100 + y * 10 + x;
}


ll head[100000];
ll nxt[200000];
ll cost[200000];
ll to[200000], cnt;

ll dis[200000];
ll vis[200000];

void addEdge(ll u, ll v, ll w) {
	++cnt;
	to[cnt] = v;
	cost[cnt] = w;
	nxt[cnt] = head[u];
	head[u] = cnt;
}
void unzip(ll s) {
//	printf("x : %lld ; y : %lld ; s : %lld ; dis : %lld\n", s % 10, s % 100 / 10, s / 100, dis[s]);
}

ll fun(ll x) {
	switch (x) {
	case FU:
	case BU:
	case LU:
	case RU:
		return U;
		break;
	case FD:
	case BD:
	case LD:
	case RD:
		return D;
		break;
	case UF:
	case DF:
	case LF:
	case RF:
		return F;
		break;
	case UB:
	case DB:
	case LB:
	case RB:
		return B;
		break;
	case UL:
	case DL:
	case FL:
	case BL:
		return L;
		break;
	case UR:
	case DR:
	case FR:
	case BR:
		return R;
		break;
	}
}
priority_queue<pair<ll, ll> > que;
int main() {
	scanf("%s %s", st, ed);
	stx = st[1]-'1';
	sty = st[0]-'a';
	edx = ed[1]-'1';
	edy = ed[0]-'a';
	scanf("%lld", &num[F]);
	scanf("%lld", &num[B]);
	scanf("%lld", &num[U]);
	scanf("%lld", &num[R]);
	scanf("%lld", &num[D]);
	scanf("%lld", &num[L]);
	for(ll i = 1; i <= 6; i++) {
		for(ll j = 1; j <= 6; j++) {
			a[i][j].flag = false;
		}
	}
	
	// wdf??!
	a[F][U] = node(UB, DF, FR, FL, FU);
	a[F][D] = node(DB, UF, FL, FR, FD);
	a[F][L] = node(LB, RF, FU, FD, FL);
	a[F][R] = node(RB, LF, FD, FU, FR);
	
	a[B][U] = node(UF, DB, BL, BR, BU);
	a[B][D] = node(DF, UB, BR, BL, BD);
	a[B][L] = node(LF, RB, BD, BU, BL);
	a[B][R] = node(RF, LB, BU, BD, BR);
	
	a[U][F] = node(FD, BU, UL, UR, UF);
	a[U][B] = node(BD, FU, UR, UL, UB);
	a[U][L] = node(LD, RU, UB, UF, UL);
	a[U][R] = node(RD, LU, UF, UB, UR);
	
	a[D][F] = node(FU, BD, DR, DL, DF);
	a[D][B] = node(BU, FD, DL, DR, DB);
	a[D][L] = node(LU, RD, DF, DB, DL);
	a[D][R] = node(RU, LD, DB, DF, DR);
	
	a[L][F] = node(FR, BL, LD, LU, LF);
	a[L][B] = node(BR, FL, LU, LD, LB);
	a[L][U] = node(UR, DL, LF, LB, LU);
	a[L][D] = node(DR, UL, LB, LF, LD);
	
	a[R][F] = node(FL, BR, RU, RD, RF);
	a[R][B] = node(BL, FR, RD, RU, RB);
	a[R][U] = node(UL, DR, RB, RF, RU);
	a[R][D] = node(DL, UR, RF, RB, RD);
	
	for(ll i = 0; i < 8; i++) {
		for(ll j = 0; j < 8; j++) {
			for(ll d = 1; d <= 6; d++) {	// 前面颜色
				for(ll k = 1; k <= 6; k++) {	// 底面颜色
					if(a[d][k].flag) {
						if(i+1 < 8) addEdge(zip(i, j, a[d][k].me), zip(i+1, j, a[d][k].up), num[fun(a[d][k].up)]);
						if(i-1 >= 0) addEdge(zip(i, j, a[d][k].me), zip(i-1, j, a[d][k].down), num[fun(a[d][k].down)]);
						if(j+1 < 8) addEdge(zip(i, j, a[d][k].me), zip(i, j+1, a[d][k].right), num[fun(a[d][k].right)]);
						if(j-1 >= 0) addEdge(zip(i, j, a[d][k].me), zip(i, j-1, a[d][k].left), num[fun(a[d][k].left)]);
					}
				}
			}
		}
	}
	
	for(ll i = 0; i <= 200000; i++) dis[i] = 1e15;
	dis[zip(stx, sty, FD)] = num[D];
	que.push(make_pair(-num[D], zip(stx, sty, FD)));
	while(!que.empty()) {
		ll u = que.top().second;
		unzip(u);
		que.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(ll i = head[u]; i; i = nxt[i]) {
			ll v = to[i];
			if(!vis[v]) {
				if(dis[v] > dis[u] + cost[i]) {
					dis[v] = dis[u] + cost[i];
					unzip(v);
					que.push(make_pair(-dis[v], v));
				}
			}
		}
	}
	ll ans = 1e15;
	for(ll i = 1; i <= 24; i++) {
		if(dis[zip(edx, edy, i)] < ans) {
			ans = dis[zip(edx, edy, i)];
		}
	}
	printf("%lld", ans);
}

T4 颜料大乱斗

Problem Description

画师傅又要开始画画了，这次他花了三天三夜将一堵墙涂成了白色。

但是画师傅有个顽劣的弟子小花，小花讨厌画师傅对Ta始乱终弃，所以趁画师傅不在用不同的颜料将墙涂来涂去。

然而画师傅为了保护他的大作，设置了一个监控机制A。A每隔一段时间会查询某一段墙上的颜料的种类数，并将其记录下来。

现在画师傅回来了，看到五颜六色色彩斑斓灯火阑珊金碧辉煌的【哗】墙，一口气没换上来，卒。

作为画师傅的好友杀小姐的你，为了追查画师傅的死因，于是调用了墙的监控机制A的记录。于是，你看到了怎样的记录呢？

Input

Output

Sample Input Copy

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

Sample Output Copy

2
1

Data Constraint

Hint

提示：

  1. 1就是白色。
  2. x 可能大于 y

刚开始维护了 \(30\) 棵线段树，被卡常于是得了 \(30\) 分。

显然每种颜色出现次数并不重要，所以可以直接用 bool 存。

既然都用 bool 存了，那么可以状态压缩。

都状态压缩了，常数就小了，就过了。

/**
 * @file 颜料大乱斗.cpp 
 * @tag: #GMOJ #线段树
 * @author: ZnPdCo
 * @date: 2023-12-23 16:03:45
 * @problem: https://gmoj.net/senior/#main/show/4603
 **/
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define N 100010
using namespace std;
ll n, c, m;
struct node {
	ll val;
	ll lazy;
	node() {val = 0, lazy = 0;}
} t[N*4];
inline void pushdown(ll l, ll r, ll pos) {
	t[ls(pos)].lazy = t[rs(pos)].lazy = t[pos].lazy;
	t[ls(pos)].val = t[rs(pos)].val = 1 << (t[pos].lazy-1);
	t[pos].lazy = 0;
}
void build(ll l, ll r, ll pos) {
	if(l == r) {
		t[pos].val = 1;
		return;
	}
	ll mid = (l + r) >> 1;
	build(l, mid, ls(pos));
	build(mid+1, r, rs(pos));
	t[pos].val = t[ls(pos)].val | t[rs(pos)].val;
}
void update(ll nl, ll nr, ll l, ll r, ll pos, ll k) {
	if(nl <= l && r <= nr) {
		t[pos].val = 1 << (k-1);
		t[pos].lazy = k;
		return;
	}
	if(t[pos].lazy) {
		pushdown(l, r, pos);
	}
	ll mid = (l + r) >> 1;
	if(nl <= mid)
		update(nl, nr, l, mid, ls(pos), k);
	if(mid < nr)
		update(nl, nr, mid+1, r, rs(pos), k);
	t[pos].val = t[ls(pos)].val | t[rs(pos)].val;
}
ll query(ll nl, ll nr, ll l, ll r, ll pos) {
	if(nl <= l && r <= nr) {
		return t[pos].val;
	}
	if(t[pos].lazy) {
		pushdown(l, r, pos);
	}
	ll mid = (l + r) >> 1;
	ll res = 0;
	if(nl <= mid)
		res = res | query(nl, nr, l, mid, ls(pos));
	if(mid < nr)
		res = res | query(nl, nr, mid+1, r, rs(pos));
	return res;
}
int main() {
	scanf("%lld %lld %lld", &n, &c, &m);
	build(1, n, 1);
	for(ll i = 1; i <= m; i++) {
		char op[10];
		scanf("%s", op);
		if(op[0] == 'P') {
			ll l, r;
			scanf("%lld %lld", &l, &r);
			if(l > r) swap(l, r);
			printf("%lld\n", __builtin_popcountll(query(l, r, 1, n, 1)));
		} else {
			ll l, r, t;
			scanf("%lld %lld %lld", &l, &r, &t);
			if(l > r) swap(l, r);
			update(l, r, 1, n, 1, t);
		}
	}
}