B. super_log

 

递推式求解，转化为求aaa⋯n个aa^{a^a{\cdots}n个a}，则欧拉降幂套公式。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
ll a, b, m;
ll Mod(ll x, ll m) {
	return x < m ? x : (x % m + m);
}
ll q_pow(ll a, ll b, ll mod) {
	ll ans = 1;
	while (b) {
		if (b & 1)ans = Mod((ans*a),mod);
		a = Mod(a*a, mod);
		b >>= 1;
	}
	return ans;
}
ll euler_phi(ll n)
{
	ll m = (ll)sqrt(n + 0.5);
	ll ans = n;
	for (ll i = 2; i <= m; i++)
	{
		if (n % i == 0)
		{
			ans = ans / i * (i - 1);
			while (n % i == 0)  n /= i;        //除尽
		}
	}
	if (n > 1)  ans = ans / n * (n - 1);    //剩下的不为1,也是素数
	return ans;
}

ll solve(ll a, ll b, ll p) {
	if (b == 0)return Mod(1, p);
	if (p == 1)return Mod(a, p);
	ll phip = euler_phi(p);
	return q_pow(a, solve(a, b - 1, phip), p);
}
int main() {
	cin.sync_with_stdio(false);
	cin >> t;
	while (t--) {
		cin >> a >> b >> m;
		cout << (solve(a, b, m) % m) << endl;
	}
	return 0;
}

 

F. Greedy Sequence

 

又是一道权值线段树，先找右子树

维护两棵权值线段树，一棵记录下标最小值，一棵记录下标最大值，当区间长为1时，判断是否满足条件。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,((rt<<1)|1)
const int maxn = 1e5 + 5;
int t, n, k;
int pos[maxn], a[maxn];
int tremax[maxn << 2], tremin[maxn << 2];
int nxt[maxn], ans[maxn];
bool flg;
void pushup(int rt) {
	tremax[rt] = max(tremax[rt << 1], tremax[(rt << 1) | 1]);
	tremin[rt] = min(tremin[rt << 1], tremin[(rt << 1) | 1]);
}
void build(int l, int r, int rt) {
	if (l == r) {
		tremax[rt] = tremin[rt] = pos[l];
		return;
	}
	build(lson);
	build(rson);
	pushup(rt);
}
int u;
void query(int i,int ql, int qr, int l, int r, int rt) {
	if (l == r) {
		if (l<a[i]&&pos[l] <= min(n, i + k) && pos[l] >= max(1, i - k)) {
			flg = 1;
			u = l;
		}
		return;
	}
	if ((!flg)&&(qr > mid) && 
		(tremax[(rt << 1) | 1] >=max(1,i-k) || tremin[(rt << 1) | 1] >= min(n,i+k)))query(i, ql, qr, rson);
	if ((!flg)&&(ql<=mid))query(i, ql, qr, lson);
}
int main() {
	cin.sync_with_stdio(false);
	cin >> t;
	while (t--) {
		cin >> n >> k;
		nxt[1] = ans[0] = 0;
		for (int i = 1; i <= n; i++) {
			int u;
			cin >> u;
			pos[u] = i;
			a[i] = u;
		}
		build(1, n, 1);
		for (int i = 1; i <= n; i++) {
			flg = 0;
			query(i, 1, a[i] - 1, 1, n, 1);
			if (flg == 0)nxt[a[i]] = 0;
			else nxt[a[i]] = u;
		}
		for (int i = 1; i <= n; ++i) ans[i] = ans[nxt[i]] + 1;
		for (int i = 1; i <= n; ++i) {
			if (i != 1) printf(" ");
			printf("%d", ans[i]);
		}
		printf("\n");
	}
	return 0;
}

 

H. Holy Grail

 

问题可转化为找到图中的最短路，并不断向图中加边，有负边。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 2e9;
typedef pair<ll, int>pii;
int t, n, m, x, y, w;
ll G[305][305];
ll d[305];
void Dij(int s) {
	fill(d, d + n, INF);
	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 v = p.second;
		if (d[v] < p.first)continue;
		for (int i = 0; i < n; i++) {
			if (G[v][i] < INF) {
				if (d[i] > d[v] + G[v][i]) {
					d[i] = d[v] + G[v][i];
					q.push(pii(d[i], i));
				}
			}
		}
	}
}
int main() {
	cin.sync_with_stdio(false);
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				G[i][j] = INF;
			}
		}
		for (int i = 0; i < m; i++) {
			cin >> x >> y >> w;
			G[x][y] = w;
		}
		for (int i = 0; i < 6; i++) {
			int s, t;
			cin >> s >> t;
			Dij(t);
			int D = d[s];
			G[s][t] = -D;
			cout << -D << endl;
		}
	}
	return 0;
}