https://ac.nowcoder.com/acm/contest/4137

C. 酒馆战棋

 

签到

题意：有圣盾，嘲讽，剧毒三种属性，只有我方剧毒随从能击杀敌方，我方打，只打一轮，问最多，最少击杀敌方多少人。

直接模拟

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int T, n;
int a1, b1, c1, d1, a, b, c, d;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
		a1 = a, b1 = b, c1 = c, d1 = d;
		int ans = 0, ans1 = 0;
		for (int i = 1; i <= n; i++) {
			char ch;
			scanf(" %c", &ch);
			if (ch == '1') {
				if (c)c--, ans++;
				else if (d)d--, c++;
				else if (a)a--, ans++;
				else if (b)b--, a++;

				if (d1)d1--, c1++;
				else if (c1)c1--, ans1++;
				else if (b1)b1--, a1++;
				else if (a1)a1--, ans1++;
			}
			else {
				if (d)d--, c++;
				else if (c);
				else if (b)b--, a++;
				else if (a);

				if (c1);
				else if (d1)d1--, c1++;
				else if (a1);
				else if (b1)b1--, a1++;
			}
		}
		printf("%d %d\n", ans, ans1);
	}
	return 0;
}

 

F. 图与三角形

 

题意：给定一个无向完全图，每条边有黑/白，当两端点满足 (A(i+j)2+B(i−j)2+C) mod P>D(A(i+j)^2+B(i−j)^2+C) \bmod P>D 时，这条边是黑色。问三条边同色的三角形个数。

直接算复杂度不够，考虑从总的里减去异色三角形，由于三角形比较简单，可以直接枚举顶点，计算它作为三角形中两条异色边的顶点的三角形数，由于和这个点异色的点的集合不会有交集，所以可以直接用两种集合的个数相乘，最后由于重复计算，所以除2。至于总的三角形就是 Cn3C_n^3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
ll n;
ll A, B, C, P, D;
ll cnt[maxn][2];
int main() {
	scanf("%lld", &n);
	scanf("%lld%lld%lld%lld%lld", &A, &B, &C, &P, &D);
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= n; j++) {
			if (i == j)continue;
			if ((A*(i + j)*(i + j) + B * (i - j)*(i - j) + C) % P > D)cnt[i][1]++;
			else cnt[i][0]++;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++)ans += cnt[i][0] * cnt[i][1];
	cout << n * (n - 1)*(n - 2) / 6 - ans / 2 << endl;
	return 0;
}

 

K. 最大权值排列

 

签到

题意：对于一个长度为 n 的数列 A，定义它的权值 f(A)为每一个区间平均数的和 ，给定排列，使得 f 最大。

题解里说把大的尽量往中间放。现场上我就是看样例隔着2递增，再递减，就照着做，没想到就A了，也不会理论证明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i += 2)printf("%d ", i);
	for (int i = n - (n & 1); i > 0; i -= 2)printf("%d ", i);
	puts("");
	return 0;
}

 

L. 你吓到我的马了.jpg

 

签到

题意：给定网格，中国象棋里马的走法，问到每一格最少步数。

BFS

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int sx, sy, n, m;
char mz[110][110];
int d[110][110];
typedef pair<int, pii> ppii;
int dx[]{ -2,-2,-1,1,-1,1,2,2 };
int dy[]{ 1,-1,2,2,-2,-2,1,-1 };
bool leg(int i, int x, int y) {
	int nx = x + dx[i], ny = y + dy[i];
	if (nx<1 || nx>n || ny<1 || ny>m || mz[nx][ny] == 'X')return false;
	if (i == 0 || i == 1) {
		if (mz[x - 1][y] == 'X')return false;
	}
	else if (i == 2 || i == 3) {
		if (mz[x][y + 1] == 'X')return false;
	}
	else if (i == 4 || i == 5) {
		if (mz[x][y - 1] == 'X')return false;
	}
	else {
		if (mz[x + 1][y] == 'X')return false;
	}
	return true;
}
void bfs() {
	priority_queue<ppii, vector<ppii>, greater<ppii> >que;
	memset(d, 0x3f, sizeof(d));
	d[sx][sy] = 0;
	que.push(ppii(0, pii(sx, sy)));
	while (!que.empty()) {
		ppii tp = que.top(); que.pop();
		int x = tp.second.first, y = tp.second.second, dis = tp.first;
		if (dis > d[x][y])continue;
		for (int i = 0; i < 8; i++) {
			if (leg(i, x, y)) {
				int nx = x + dx[i], ny = y + dy[i];
				if (d[nx][ny] > d[x][y] + 1) {
					d[nx][ny] = d[x][y] + 1;
					que.push(ppii(d[nx][ny], pii(nx, ny)));
				}
			}
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf(" %c", &mz[i][j]);
			if (mz[i][j] == 'M')sx = i, sy = j;
		}
	}
	bfs();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			printf("%d%s", d[i][j] >= INF ? -1 : d[i][j], j == m ? "\n" : " ");
		}
	}
	return 0;
}

 

M. 自闭

 

签到

题意：模拟赛场上提交情况，问每个选手的自闭程度。

直接模拟

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m, W;
int renAc[110], tiAc[20], renti[110][20], renSub[110];
vector<int>vc[110][20];
int ans[110], cnt[5010];
int main() {
	scanf("%d%d%d", &n, &m, &W);
	for (int i = 0; i < W; i++) {
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		vc[x][y].push_back(c);
		renSub[x]++; 
		if (c == 1) {
			if (!renti[x][y]) {
				renAc[x] ++;
				tiAc[y] ++;
				renti[x][y] = 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (renSub[i] == 0) { ans[i] = 998244353; continue; }
		if (renAc[i] == 0) { ans[i] = 1000000; continue; }
		if (renAc[i] == m) { ans[i] = 0; continue; }
		for (int j = 1; j <= m; j++) {
			if (tiAc[j] > 0 && renti[i][j] == 0)ans[i] += 20;
			if (tiAc[j] >= n / 2 && renti[i][j] == 0)ans[i] += 10;
			memset(cnt, 0, sizeof(cnt));
			int K = 0;
			for (int k = 1; k <= (int)vc[i][j].size(); k++) {
				if (vc[i][j][k - 1] == 1)cnt[k] = 0;
				else cnt[k] = cnt[k - 1] + 1;
				K = max(K, cnt[k]);
			}
			ans[i] += K * K;
			if (!renti[i][j])ans[i] += K * K;
		}
	}
	for (int i = 1; i <= n; i++)cout << ans[i] << endl;
	return 0;
}

 

N. 合并！

 

题意：石子合并，合并相邻两堆收益为两堆石子数乘积。求最大收益。

貌似直接从左到右合并就一定是答案。

场上用了区间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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2020;
int n;
ll dp[maxn][maxn], a[maxn], sum[maxn];
int rela[maxn][maxn];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i], rela[i][i] = i;
    for (int len = 1; len <= n; len++) {
        for (int j = 1; j + len <= n + 1; j++) {
            int ends = j + len - 1;
            for (int k = rela[j][ends - 1]; k <= rela[j + 1][ends]; k++) {
                if (dp[j][ends] < dp[j][k] + dp[k + 1][ends] + (sum[k] - sum[j - 1])*(sum[ends] - sum[k])) {
                    dp[j][ends] = dp[j][k] + dp[k + 1][ends] + (sum[k] - sum[j - 1])*(sum[ends] - sum[k]);
                    rela[j][ends] = k;
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

 

G. 单调栈

 

题意：有一个排列，每个数都有一个 ff 值，为这个数前面最大的比他小的数的 ff 值+1.现在给出一个一些数的 ff 值，要求构造出一个符合条件的排列。

构造

首先肯定要把小的放到前面，并且要先把f为1的都安排好。因为前面的1一定大于后面的1，而2一定大于前面某个1，所以2一定大于它后面的所有1，那么要让2最小，就必须让所有的1都小，所以要先安排好1再安排2.以此类推。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 3e5 + 10;
const int INF = 0x3f3f3f3f;
int T, n;
int a[maxn];
int S[maxn], tp;
int ans[maxn];
int main() {
	scanf("%d", &T);
	while (T--) {
		int mx = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			if (a[i] == -1)a[i] = mx + 1;
			mx = max(mx, a[i]);
		}
		int r = 1;
		for (int i = 1; i <= n; i++) {
			tp = 0;
			for (int j = 1; j <= n; j++) {
				if (a[j] == i)S[tp++] = j;
			}
			while (tp)ans[S[--tp]] = r++;
		}
		for (int i = 1; i <= n; i++)printf("%d%s", ans[i], i == n ? "\n" : " ");
	}
	return 0;
}

 

H. 异或询问

 

题意：给定一个序列 a1...na_{1...n}，定义 f(x)f(x) 为有几个 aia_i 小于等于 xx，现在有 QQ 次询问，每次给定 l,r,xl,r,x，你需要求 ∑i=lrf(i⨁x)2\sum _{i=l}^r f(i\bigoplus x)^2。

连续区间可以用前缀和，但是异或之后就不一定连续了。但是有一个重要的结论， [0,n][0,n] 异或 xx 后的区间段数一定是 log⁡n\log n 的，可以对这 log⁡n\log n 个区间前缀和。

至于怎么得到这些连续区间，还是摘抄一下大佬博客orz。

转自： https://www.cnblogs.com/mollnn/p/12367026.html

自己试一下应该可以看懂。

所以总的思路就是：先把查询的区间分成两个前缀和，对于每个前缀和，即 [0,R][0,R] 上的询问可以得到 log⁡n\log n 个连续区间，对每个区间分别求解，求解时再用前缀和得到这个区间上的 ∑f(x)2\sum f(x)^2。

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;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const ll mod = 998244353;
int n, Q, N;
ll a[maxn], b[maxn], sum[maxn];
inline int Add(int x, int y) {
    x += y;
    return x % mod;
}
inline int Sub(int x, int y) {
    x -= y;
    while (x < 0)x += mod;
    return x % mod;
}
inline int Mul(int x, int y) {
    return 1ll * x*y%mod;
}
ll ask(ll x) {
    int pos = upper_bound(b + 1, b + N + 1, x) - b;
    if (pos == 1)return 0;
    pos--;
    ll res = sum[pos - 1];
    ll k = upper_bound(a + 1, a + n + 1, b[pos]) - a - 1;
    res = Add(res , Mul(Mul(1ll * (x - b[pos] + 1), k), k));
    return res;
}
ll ask(ll l, ll r) {
    return Sub(ask(r) , ask(l - 1));
}
ll qry(ll t, ll x) {
    if (t < 0)return 0;
    ll cur = 0;
    ll res = 0;
    for (int i = 30; i >= 0; i--) {
        int u = ((x >> i) & 1);
        if ((t >> i) & 1) {
            res = Add(res, ask(cur | (u << i), (cur | (u << i)) + (1 << i) - 1));
            cur |= ((u << i) ^ (1 << i));
        }
        else {
            cur |= (u << i);
        }
    }
    res = Add(res, ask(cur, cur));
    return res;
}
int main() {
    scanf("%d%d", &n, &Q);
    for (int i = 1; i <= n; i++)scanf("%lld", &a[i]), b[i] = a[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    N = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i < N; i++) {
        int p = upper_bound(a + 1, a + n + 1, b[i]) - a - 1;
        sum[i] = Add(sum[i - 1], Mul(b[i + 1] - b[i], Mul(p, p)));
    }
    while (Q--) {
        ll l, r, x;
        scanf("%lld%lld%lld", &l, &r, &x);
        ll ans = Sub(qry(r, x) , qry(l - 1, x));
        printf("%lld\n", ans);
    }
    return 0;
}