首页 Tests

期望：100 + 0 + 0 + 50
实际：0 + 0 + 0 + 35
能冲: 100 + 100 + 100 + 0

输光了

主要输在 T2 想复杂了以及 T1FST 了

T2 胡了个线段树优化建图但点数爆炸就没写，实际上简单地上前缀优化建图即可。

T1FST 的奇奇怪怪的，还是要自己好好想想。

T4 看错题了，但还有 35 (?) ，但它自动姬一点的做法是真的玄妙，但好像作为原题出现过两次（我都没考）

# Solutions

# A

你在 ss 要去 tt ，有个杀手要干你，初始在 kk ，求你和他速度最小比使得你不会被干。

n≤5e5n\le 5e5

值得注意的是，你只知道杀手初始在哪里，但不能动态知道它每一步在哪里，所以你不是博弈类似的它走一步你走一步，也不能直接硬上最短路。

那我们把杀手到每个点的最短路求出来，然后你二分答案 xx ，再跑 dijdij ，当你到某个点时 dis2v>x×dis1vdis2_v > x\times dis1_v 那你走就会被鲨，于是不能走，这样就能 checkcheck 了

# B

nn 个怪，mm 种魔法 (a,b,c)(a,b,c) 表示把一个 aa 血量的怪变成 bb 血量花费 cc 法力，你也可以直接打花 11 法力扣 11 血量，求把每个怪打成 11 血所花费的最少法力

n≤1e6n\le 1e6

线段树优化建图？

直接排序离散化建图！

我是什么石锤了

# C

nn 个路口，两两距离为 did_i ，每 G+RG+R 时间中 GG 时间绿灯，RR 时间红灯，你只有在绿灯才能通过路口，qq 次询问从时刻 tt 出发啥时候能到 nn 号路口。

n≤2×105n\le 2\times 10^5

考虑你在时刻 k≥Rk\ge R 时间到了一个路口，你必然会等到下一个绿灯区间才会往后走。

这启发我们预处理每个路口从绿灯区间出发到 nn 号路口的答案。

你考虑，从后往前，类似 dpdp 的，ii 号路口的答案一定会由后面第一个红灯的 jj 号路口答案转移过来。

我们可以列出不等式 :$$G\le sum_j-sum_i < G+R$$.
在你做 ii 时， sumisum_i 是个定值，于是你可以直接在值域线段树上查 jj

查询时，只需类似的判断后面第一个红灯在哪里，就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/* ==============================
 *  Author : Odalys 
 *
 *  Blog : Odalys.xyz
 *
 *  Mail : minyuenu@gmail.com
 * =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 2e5 + 10;
#define LL long long 
struct SGT {
	struct Node { int val, l, r; };
	int tot, rt;
	vector < Node > tr;
	SGT (int siz) : tot(0), rt(0), tr(siz, Node{-1, 0, 0}) {}
	#define ls tr[x].l
	#define rs tr[x].r
		
	inline void put (int &x, int v) {
		if (!x) x = ++tot;
		tr[x].val = v;
	}
	void pushdown (int x) {
		if (~tr[x].val) put(ls, tr[x].val), put(rs, tr[x].val), tr[x].val = -1;
	}
	void update (int &x, int l, int r, int ll, int rr, int v) {
		if (ll <= l && r <= rr) return put(x, v), void();
		pushdown(x);
		int mid = (l + r) / 2;
		if (ll < mid) update (ls, l, mid, ll, rr, v);
		if (rr > mid) update (rs, mid, r, ll, rr, v); 
	}
	int query (int x, int l, int r, int p) {
		if (~tr[x].val) return tr[x].val;
		pushdown(x);
		int mid = (l + r) / 2;
		if (p < mid) return query (ls, l, mid, p);
		return query (rs, mid, r, p); 
	}
} ;
int n, G, R;
LL a[N], pre[N];
LL Ans[N];
int main() {
	read(n); read(G); read(R);
	For (i, 0, n) read(a[i]), pre[i] = pre[i - 1] + a[i];
	SGT tr (n * 100); R += G;
	tr.update(tr.rt, 0, R, 0, R, n);
	foR (i, n - 1, 0) {
		int j = tr.query (tr.rt, 0, R, (R - pre[i] % R) % R);
		Ans[i] = Ans[j] + pre[j] - pre[i];
		if (j < n) Ans[i] += (R - (pre[j] - pre[i]) % R);
		int l = (R + G - pre[i] % R) % R;
		int r = (R - pre[i] % R) % R; 
		if (l < r) 
			tr.update (tr.rt, 0, R, l, r, i);
		else {
			tr.update (tr.rt, 0, R, l, R, i);
			if (r)
			tr.update (tr.rt, 0, R, 0, r, i);
		}
	}
	int q;	read(q);
	LL tmp = 0;
	while (q--) {
		int t; read(t); t = t xor (tmp % 2147483647); 
		int i = tr.query (tr.rt, 0, R, t % R);
	tmp = Ans[i] + pre[i] + t;
		if (i < n) tmp += R - (pre[i] + t) % R;
		printf ("%lld\n", tmp);
	}
	return 0;
}

# d

this

考虑设计一个 DFA ，每个状态为一个等价类，即满足 f(x)=f(y)f(x) = f(y) 且 f(x+S)=f(y+S)f(x+S) = f(y+S) 其中 SS 为任意 01 串

可以证明，这样的等价类不超过 200 个 草！

然后考虑判断两个串是否在同一等价类中，可以证明，只要在这两个串后面随意加长度不超过 77 的函数值还 TM 相等，就在同一等价类中。 草！

然后暴力建出自动姬在上面 DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int>
#define pii pair<int, int>
#define vi vector<int>
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 1e5 + 10;
const int Mod = 1e9 + 7;
struct Node {
	int siz, a[20];
} dot[222];

int f[10];

int get ( vi a ) {
	while (a.size() > 1) {
		int xx = 0;
		For (i, 0, 2) xx = xx * 2 + a.back(), a.pop_back();
		xx = f[xx]; a.pb(xx);
	}
	return a[0];
}

int to[N][2], tot;
bool tag[30][2];
pii sol ( Node x ) {
	memset (tag, 0, sizeof tag);
	tag[1][x.a[1]] = 1;
	for (int i = 3; i <= x.siz; i += 2)
		for (int j = 1; j < i; j += 2)
			For (k, 0, 1)
				if (tag[j][k]) {
					vi tmp; tmp.pb(k);
					For (o, j + 1, i) tmp.pb(x.a[o]);
					tag[i][get(tmp)] = 1;
				}
	return mp (tag[x.siz][0], tag[x.siz][1]);
}

bool ck ( Node x, Node y ) {
	if ( (x.siz & 1) != (y.siz & 1) ) return false;
	For (len, 0, 7)
		if ( (x.siz + len) & 1 ) {
			For (s, 0, (1 << len) - 1) {
				Node c = x, d = y;
				For (i, 1, len) {
					c.a[++c.siz] = (s >> i - 1) & 1;
					d.a[++d.siz] = (s >> i - 1) & 1;
				}
				if (sol(c) != sol(d)) return false;
			}
		}
	return true;
}

void build () {
	static queue <int> q; while (!q.empty()) q.pop();
	q.push(1);
	tot = 1;
	while (!q.empty()) {
		int id = q.front(); q.pop();
		Node u = dot[id];
		For (i, 0, 1) {
			Node v = u; v.a[++v.siz] = i;
			bool flag = false;
			For (j, 1, tot) if (ck(dot[j], v)) { to[id][i] = j; flag = 1; break; }
			if (!flag) {
				dot[to[id][i] = ++tot] = v;
				q.push(tot);
			}
		}
	}
}
int dp[N][333];
char ch[N];
int main() {
	int cases; read(cases);
	while (cases--) {
		memset (to, 0, sizeof to);
		For (i, 0, 7) scanf ("%1d", &f[i]);
		build ();
		memset (dp, 0, sizeof dp);
		scanf ("%s", ch + 1);
		int n = strlen(ch + 1);
		dp[0][1] = 1;
		For (i, 1, n) For (j, 1, tot) {
			if (dp[i - 1][j]) {
				if (ch[i] == '?')
					For (o, 0, 1) (dp[i][to[j][o]] += dp[i - 1][j]) %= Mod;
				else
					(dp[i][to[j][ch[i] - '0']] += dp[i - 1][j]) %= Mod;
			}
		}
		int Ans = 0;
		For (i, 1, tot) if (sol(dot[i]).se == 1) (Ans += dp[n][i]) %= Mod;
		printf ("%d\n", Ans);
	}
}