B. Fire-Fighting Hero

 

很垃圾的英文表述，题意是有一个无向图，图上有几个点是救火站，从这几个救火站同时出发，求出到图上所有点的最短路，也就是说，这几个救火站距离为0，bfs。还有一个救火hero，他从给定点出发，求所有点最短路。

求完图上的最短路后，对救火队找出最短路长度最长的点，对救火hero，同样如此，两个最大值比较。

bfs以消防队为源点求最短路时可以先把所有消防队都压入队列中，也可以给所有消防队加一个距离为0的源点，以新的源点为起点求最短路。

题中可能会多次给出同一条边，要取最小值作为该边长度。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1005;
const int INF = 0x3f3f3f3f;
int G[maxn][maxn];
int t, V, E, S, K, C;
vector<int>team;
int anst, ansh;
int d[maxn];
void bfs(int s) {
	memset(d, 0x3f, sizeof(d));
	priority_queue<pii, vector<pii>, greater<pii> >q;
	q.push(pii(0, s));
	d[s] = 0;
	while (!q.empty()) {
		pii p = q.top(); q.pop();
		int u = p.second;
		if (d[u] < p.first)continue;
		for (int v = 1; v <= V; v++) {
			if (G[u][v] == INF)continue;
			if (d[v] > d[u] + G[u][v]) {
				d[v] = d[u] + G[u][v];
				q.push(pii(d[v], v));
			}
		}
	}
}
int main() {
	cin.sync_with_stdio(false);
	cin >> t;
	while (t--) {
		anst = ansh = 0;;
		memset(G, 0x3f, sizeof(G));
		team.clear();
		cin >> V >> E >> S >> K >> C;
		for (int i = 1; i <= K; i++) {
			int u;
			cin >> u;
			team.push_back(u);
		}
		for (int i = 0; i < E; i++) {
			int u, v, L;
			cin >> u >> v >> L;
			G[u][v] = G[v][u] = min(G[u][v], L);
		}
		for (auto v : team) {
			G[0][v] = G[v][0] = 0;
		}
		bfs(0);
		for (int i = 1; i <= V; i++) {
			anst = max(d[i], anst);
		}
		bfs(S);
		for (int i = 1; i <= V; i++) {
			ansh = max(ansh, d[i]);
		}
		if (ansh<=anst*C) {
			cout << ansh << endl;
		}
		else {
			cout << anst << endl;
		}
	}
	return 0;
}

 

E. Magic Master

 

直接用队列模拟 拿牌，放到最底下，那最顶上的牌，明明是到签到题，却没敢这么做。。

用结构体+链表模拟会超时，用两个数组记录就不会，不过时间很紧，用双端队列push，pop只要一半时间。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
int t, n, m, q, k;
const int maxn = 4e7 + 1;
deque<int>que;
int ans[maxn];
int main() {
	cin.sync_with_stdio(false);
	cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			que.push_back(i);
		}
		for (int i = 1; i <= n; i++) {
			ans[que.front()] = i;
			que.pop_front();
			if (que.empty())break;
			for (int j = 1; j <= m; j++) {
				que.push_back(que.front());
				que.pop_front();
			}
		}
		cin >> q;
		for (int i = 0; i < q; i++) {
			cin >> k;
			cout << ans[k] << endl;
		}
	}
	return 0;
}

 

F. Megumi With String

 

后缀自动机

对于一个长度为i的，已知确定的字串，它对T的value的贡献为G(i)，而它出现的概率为len(T)−i+126i\frac{len(T)-i+1}{26^i}，所以期望为value=len(T)−i+126i⋅G(i)value=\frac{len(T)-i+1}{26^i} \cdot G(i)，而每一个长度相同，都为i的字串的value都是相同的，都等于上述value。

所以我们现在只需要统计T中长度从0到min(len(S)+m,len(T))的包含于S中字串的个数，注意，由于我们不知道T串，所以我们现在只需要找到S中长度从0到min(len(S)+m,len(T))的子串个数，就可以假设它在T中，并计算期望值。

后缀自动机中每一个节点代表了长度位于某一区间的子串，且每种长度的子串在同一个节点中只出现一次，而若直接枚举必定超时，因此自然想到区间（尾-头），即前缀和，记录长度从0到i的子串的期望值之和。

接下来需要考虑的就是向S串中加字符，由于后缀自动机的性质，向图中加入一个字符时：

  • 若原图中没有代表该状态的节点，则已有节点的endpos不会改变，故只需要向答案添加新增加的节点的信息。
  • 若原图中有代表该状态的节点，则该结点所有子串对答案都应该增加一次贡献，这就相当于把该结点所代表的区间的期望值再加一遍。同样是只要向答案中添加加入的字符所在的节点信息。

所以ans=ans+新加入的字符所在的节点代表的的长度区间的期待值。

由于有多个case，所以每次记得清空。

用getchar()读入插入的字符会有段错误，用char c[2]读入，再insert(c[0])。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 500016;
const int mod = 998244353;
char s[maxn];
ll p[64], sum[maxn];
int t, l, k, n, m;
ll ans = 0;
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
	while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
ll power(ll a, ll x) {
	ll ans = 1;
	while (x) {
		if (x & 1)ans = (ans*a) % mod;
		a = (a*a) % mod;
		x >>= 1;
	}
	return ans;
}
struct SAM {
	int last, cnt;
	int ch[maxn][26], fa[maxn], len[maxn];
	void init() {
		last = cnt = 1;
		memset(ch[1], 0, sizeof(ch[1]));
		len[1] = fa[1] = 0;
	}
	int ins(int c) {
		int p = last, np = ++cnt;
		memset(ch[np], 0, sizeof(ch[np]));
		last = np;
		len[np] = len[p] + 1;
		for (; p && !ch[p][c]; p = fa[p])
			ch[p][c] = np;
		if (!p)fa[np] = 1;
		else {
			int q = ch[p][c];
			if (len[p] + 1 == len[q])fa[np] = q;
			else {
				int nq = ++cnt; len[nq] = len[p] + 1;
				memcpy(ch[nq], ch[q], sizeof(ch[q]));
				fa[nq] = fa[q]; fa[q] = fa[np] = nq;
				for (; ch[p][c] == q; p = fa[p])ch[p][c] = nq;
			}
		}
		return last;
	}
	int build(const char* s) {
		int len = strlen(s);
		last = cnt = 1;
		for (int i = 0; i < len; i++)ins(s[i] - 'a');
		return cnt;
	}
}sam;
ll inv(ll a) {
	return power(a, mod - 2);
}
int main() {
	t = read();
	while (t--) {
		sam.init();
		ans = 0;
		l = read(); k = read(); n = read(); m = read();
		scanf("%s", s);
		for (int i = 0; i <= k; i++) {
			p[i] = read();
		}
		sum[0] = p[0];
		for (int i = 1; i <= min(l + m, n); i++) {
			ll now = 0, b = 1;
			for (int j = 0; j <= k; j++) {
				now = (now + b * p[j]) % mod;
				b = b * i%mod;
			}
			now = now * (n - i + 1) % mod;
			now = now * inv(power(26, i)) % mod;
			sum[i] = (sum[i - 1] + now) % mod;
		}
		int tot = sam.build(s);
		for (int i = 2; i <= tot; i++) {
			int L = sam.len[sam.fa[i]] + 1, R = min(n, sam.len[i]);
			ans = (ans + sum[R] - sum[L - 1] + mod) % mod;
		}
		printf("%lld\n", ans);
		for (int i = 0; i < m; i++) {
            char c[2];
			scanf("%s",c);
			int now = sam.ins(c[0] - 'a');
			int L = sam.len[sam.fa[now]] + 1, R = min(n, sam.len[now]);
			ans = (ans + sum[R] - sum[L - 1] + mod) % mod;
			printf("%lld\n", ans);
		}
	}
	return 0;
}

 

G. Pangu Separates Heaven and Earth

 

很直接的签到题，就看谁敢跳过题干。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<iostream>
using namespace std;
int T;
long long n;
int main()
{
    cin >> T;
    while (T--) {
        cin >> n;
        if (n == 1) cout << 18000 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

 

H. The Nth Item

 

队友写的，听说用矩阵快速幂，题解上说用快速幂预处理，然后推导出通项公式。

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
#include<set>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const LL maxn = 2e5+5, mod = 998244353;
struct matrix
{
    LL a[2][2];
    matrix(LL b11=0, LL b12=0, LL b21=0, LL b22=0) {
        a[0][0]=b11; a[0][1]=b12; a[1][0]=b21; a[1][1]=b22;
    }
    matrix operator * (const matrix& rhs) const {
        matrix tmp;
        for (int i : {0, 1}) for (int j : {0, 1}) for (int k : {0, 1})
            tmp.a[i][j] = (tmp.a[i][j] + a[i][k] * rhs.a[k][j]) % mod;
        return tmp;
    }
    matrix pow_mod(LL i) {
        matrix A = *this, ret = matrix(1,0,0,1);
        for (; i; i >>= 1, A = A * A)
            if (i & 1) ret = ret * A;
        return ret;
    }
};
LL n, q, ans, xors, mark1, mark2, rst;
matrix m(3, 2, 1, 0);
bool flag, temp;

int main()
{
    cin >> q >> n;
    xors = 0;
    ans = 0;
    while (q--) {
        n ^= ans * ans;
        if (n <= 1) ans = n;
        else ans = m.pow_mod(n-1).a[0][0];
        xors ^= ans;
        if (xors == mark1) {
            if (q % 2) cout << mark2 << endl;
            else cout << mark1 << endl;
            break;
        }
        flag = !flag;
        if (flag) mark1 = xors;
        else mark2 = xors;
    }
    if (q == -1) cout << xors << endl;
    return 0;
}