Kvar_ispw17's blog
0%

Posted on In

题目链接：HDU 3085 Nightmare Ⅱ

题目大意

​ 给一个地图，有些地方不能走。二明和他的女朋友被两个鬼追，所以他们二人希望尽快团聚。每个单位时间，二明可以走 \(3\) 步，女朋友可以走 \(1\) 步，人类不能穿墙。每一个单位时间鬼可以分裂，并占据当前状态向外拓展 \(2\) 步的所有地点覆盖。问二人幸福美满快乐地团聚所需的最小时间。

题解

  1. 如何判断当前位置是否有鬼？

    由于鬼可以穿墙，我们发现利用两点之间的折线距离——即曼哈顿距离 \(\text{dis} = |x_1-x_2|+|y_1-y_2|\) 可以直接判断：设当前时刻为 \(t\)，如果该点到某一个鬼的位置折线距离 \(\text{dis} \leq 2t\)，说明该点被鬼的分身已经占据。

  2. 怎么在一个单位时间让两人走不同的步数？

    注意到，在传统 \(\text{bfs}\) 中，我们每次取队首，得到新的合法位置，然后就直接把新的位置放到了队尾，从而没法考虑步数的问题。 现在我们在传统 \(\text{bfs}\) 中再加入一个临时队列 \(\text{tmp}\)，并且每次取当前队列 \(q\) 得到下一步的所有位置，并把下一步的所有位置加入临时队列 \(\text{tmp}\)，以保证每次只考虑走一步，最后再 \(q = \text{tmp}\)，重复该过程 \(k\) 次，就代表一共连续考虑了 \(k\) 步。

  3. 其他小细节？

    开一个数组 \(\text{d}[4][2]\) 存坐标的变化：\(\{0,1,0,-1,1,0,-1,1\}\)，使拓展新坐标时代码简洁。 当二人存当前状态的队列均为空时退出，设一个布尔变量判断是否相遇并输出当前的时刻（由于步长相同，所以该时刻满足一定是最短时间）。 （最开始样例的第三组数据总是 \(\text{WA}\) ，结果发现一个大 \(\text{bug}\)：当前队列里的点可能在上一个点还没有鬼占据，但是这一个时刻可能已经非法了！于是我又写了一个 \(\text{check_ghost()}\) 专门判断是不是有鬼占据……）

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>
// #include <cstdlib>
// #include <windows.h>
using namespace std;

typedef long long ll;

const int N = 800 + 5;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
    for(c = getchar(); !isdigit(c); c = getchar());
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int T, m, n;
char a[N][N];

struct pos {
    int x, y;
    pos() {}
    pos(int _x, int _y): x(_x), y(_y) {}
}; // 管学长说写struct更好~

int d[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
vector<pos> Z; // Ghosts !

bool check(const pos &p, int op, int t) {
    int x = p.x;
    int y = p.y;
    if(op == 0 && a[x][y] == 'M') return false;
    if(op == 1 && a[x][y] == 'G') return false;
    if(a[x][y] == 'X') return false;
    if(x < 1 || x > n || y < 1 || y > m) return false;
    for(int i = 0; i < 2; i++) {
        pos &Zp = Z[i];
        int _x = Zp.x;
        int _y = Zp.y;
        int dis = abs(x - _x) + abs(y - _y);
        if(dis <= 2 * t) return false;
    }
    return true;
}

bool check_ghost(const pos &p, int op, int t) {
    int x = p.x;
    int y = p.y;
    for(int i = 0; i < 2; i++) {
        pos &Zp = Z[i];
        int _x = Zp.x;
        int _y = Zp.y;
        int dis = abs(x - _x) + abs(y - _y);
        if(dis <= 2 * t) return false;
    }
    return true;
}

void print_map() {
    // system("cls");
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            printf("%c", a[i][j]);
        }
        puts("");
    }
    // Sleep(100);
}

bool bfs(queue<pos> &q, int op, int s, int t) {
    queue<pos> tmp;
    for(int i = 1; i <= s; i++) {
        // printf("step = %d\n", i);
        while(!q.empty()) {
            pos p = q.front();
            q.pop();
            if(!check_ghost(p, op, t)) {
                continue;
            }
            for(int j = 0; j < 4; j++) {
                pos np;
                np.x = p.x + d[j][0];
                np.y = p.y + d[j][1];
                if(check(np, op, t)) {
                    if(op == 0) {
                        if(a[np.x][np.y] == 'G') {
                            // printf("FOUND G at (%d, %d)\n", np.x, np.y);
                            return true;
                        }
                        else a[np.x][np.y] = 'M';
                    }
                    if(op == 1) {
                        if(a[np.x][np.y] == 'M') {
                            // printf("FOUND M at (%d, %d)\n", np.x, np.y);
                            return true;
                        }
                        else a[np.x][np.y] = 'G';
                    }
                    tmp.push(np);
                    // printf("\tGOT (%d, %d)\n", np.x, np.y);
                }
            }
        }
        q = tmp;
        while(!tmp.empty()) tmp.pop();
    }
    return false;
}

void init() {
    Z.clear();
    memset(a, 0, sizeof a);
}

char str[N];

int main() {
    // freopen("t5.in", "r", stdin);
    read(T);
    while(T--) {
        init();
        queue<pos> M, G;
        read(n), read(m);
        for(int i = 1; i <= n; i++) {
            scanf("%s", str + 1);
            for(int j = 1; j <= m; j++) {
                char c = str[j];
                a[i][j] = c;
                if(c == 'M') M.push(pos(i, j));
                if(c == 'G') G.push(pos(i, j));
                if(c == 'Z') Z.push_back(pos(i, j));
            }
        }
        int t = 0;
        bool f = 0;
        while(!(M.empty() && G.empty())) {
            t++;
            if(bfs(M, 0, 3, t)) { 
                // printf("M found G!\n");
                f = 1; 
                break;
            }
            if(bfs(G, 1, 1, t)) {
                // printf("G found M!\n");
                f = 1;
                break;
            }
            // printf("t = %d [%d][%d]\n", t, M.size(), G.size());
        }
        // print_map();
        printf("%d\n", f ? t : -1);
    }
    return 0;   
}

Posted on In

题目链接： Codeforces 176B Word Cut

题目大意

给两个字符串 \(s\)，\(e\) \((\text{len} \leq 1000)\)，和数字 \(k\) \((k\leq 10^5)\)， 定义一次操作为：从当前字符串中任取一个间隔拆开字符串并交换左右部分得到新字符串，问从 \(s\to e\) 且恰好操作了 \(k\) 次的不同方案数。

题解

  1. 我们把字符串复制一份放到后面接上，设为 \(t=s+s\) ，则每一次操作实际上是取字符串 \(t\) 的一个长为 \(n\) 的子串得到新串，所以我们可以直接得到在所有的 \(n\) 个循环串（设为集合 \(T\)）中哪些是最终状态 \(e\)，并记录满足条件的位置（记为 \(O\)）个数为 \(\text{ok}\)，则不能达到的状态位置个数 \(\text{nok}=n-\text{ok}\).

  2. 注意到每考虑一次该操作，即代表一个从 \(T\to T\) 的映射，我们发现当前操作中达到某一个 \(e\) 位置的方案可以由上一次操作转移，由于转移中可能用到中间过渡的非终点串，于是设 \(\text{dp}[0][i]\) 表示进行了 \(i\) 次操作后达到 \(O\) 的方案数，\(\text{dp}[1][i]\) 为 进行了 \(i\) 次操作后达到 \(T-O\) 的方案数，

    则有：\[\text{dp}[0][i] = \text{dp}[0][i-1]\times(\text{ok}-1)+\text{dp}[1][i-1]\times(\text{ok}) \\\text{dp}[1][i]=\text{dp}[0][i-1]\times (\text{nok}) +\text{dp}[1][i-1]\times (\text{nok} - 1)\]

    该转移表示，当前的到达终点串的方案一方面来自上次状态的到达终点的方案转移到新的终点串，由于每次转移不能转移到自己，故为 \(\text{ok}-1\)，而另一部分为上一个状态中不能到达终点串的方案再利用所有终点串转移到当前状态，故直接为 \(\text{ok}\)。当前状态的非终点串方案同理。

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
    for (c = getchar(); !isdigit(c); c = getchar());
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e3 + 5;
const int K = 1e5 + 5;
const int MOD = 1e9 + 7;

int n, k;
string s, e;
ll ok, nok, dp[2][K];

int main() {
    // freopen("t5.in", "r", stdin);
    cin >> s >> e >> k;
    n = s.length();
    string t = s + s;
    for(int i = 0; i < n; i++) {
        string _t = t.substr(i, n);
        if(_t == e) ok++;
        else nok++; 
    }
    // cout << ok << endl;
    if(s == e) dp[0][0] = 1;
    else dp[1][0] = 1;
    for(int i = 1; i <= k; i++) {
        dp[0][i] = (dp[1][i - 1] * ok % MOD + dp[0][i - 1] * (ok - 1) % MOD) % MOD;
        dp[1][i] = (dp[1][i - 1] * (nok - 1) % MOD + dp[0][i - 1] * nok % MOD) % MOD;
    }
    cout << dp[0][k] << endl;
    return 0;
}

Posted on

题目链接：LibreOJ #6343. Sally Face 与地牢

做过 [Heoi 2014]林中路径 的同学应该対本题感到十分亲切，而在本题目，询问由平方和变为任意 \(r_i\) 次方和。

边无向和自环其实和边有向的情况完全相同，注意特判即可，关键问题为维护 \(r\) 次方和。

定义非负整数集合 \(S\) 用来存储路径长度，定义矩阵 $A_{[p]S}(0pr) $，表示从 \(i\) 点到 \(j\) 点，路径长度 \(k\in S\) 的路径长度的 \(p\) 次方和。

设 \(u\rightarrow k\) 有 \(a\) 条路径，长度为 \(c_1,c_2,\dots,c_{a}(c_i\in S_1)\) ， 设 \(k\rightarrow v\) 有 \(b\) 条路径，长度为 \(d_1,d_2,\dots,d_{b}(d_i\in S_2)\) ，我们有以下式子： \[ \begin{aligned} A_{[p]S_1\times S_2}[u][v] &= \sum_{i=1}^{a}\sum_{j=1}^{b}(c_i+d_j)^p\\ &=\sum_{i=1}^a\sum_{j=1}^b\sum_{t=0}^{p}\binom{p}{t}c_i^{p-t}d_j^{t}\\ &=\sum_{t=0}^{p}\binom{p}{t}\sum_{i=1}^a\sum_{j=1}^bA_{[p-t]S_1}[u][k]\cdot A_{[t]S_2}[k][v]\\ \end{aligned} \] 其中 $ S_1S_2 $ 表示一个集合 \(S'\)， 设\(S_1, S_2\) 进行笛卡尔积后为集合 \(\{(a_i,b_i)\}\)，则 $ S'={a_i+b_i} $。上面的形式符合矩阵乘法的运算法则，所以有： \[ A_{[p]S_1\times S_2}=\sum_{t=0}^p\binom{p}{t}A_{[p-t]S_1}\times A_{[t]S_2} \]

开始读入路径的长度都为 $ 1 $，直接读入 $ A_{[p]{1}}[i][j] $ ，运用刚才定义的矩阵运算计算，可得 $ A^i $ 为恰好走 \(i\) 步的答案，则 \(\sum_{i=1}^kA_{[p]}^i\) 即为最多走 $ k $ 步的答案 。对于 \(k\leq 10^{13}\) ，我们运用快速幂的思想加速计算，具体细节参考下面代码中的 \(\text{procedure()}\) 函数，时间复杂度为 \(O(n^3r^2logk+q)\) 。

注意到由于 \(r^2\) 的存在，这个复杂度无法通过此题，我们考虑在具体实现中把 $ i $ 次方和作为 $ (r+1)$ 元组放在一个矩阵中的每个位置，则每次做元组乘法时实际上是： \[ \begin{align} &(a_0,a_1,a_2,\dots,a_r)\\ &(b_0,\,b_1,\,b_2,\dots,b_r) \end{align} \] 其中下标表示路径长度的 $ i $ 次方和，则实际上上下两个式子做了一个卷积，且卷积每次相乘附带了一个二项式系数。设 \(c_i\) 为卷积后的第 $ i $ 次方和的答案，则： \[ \begin{align} c_i&=\sum_{j=0}^ia_j\cdot b_{i-j}\cdot \binom{i}{j}\\ &=\sum_{j=0}^ia_j\cdot b_{i-j}\cdot \frac{i!}{j!(i-j)!}\\ &=i!\sum_{j=0}^i\frac{a_j}{j!}\cdot \frac{b_{i-j}}{(i-j)!} \end{align} \] 用原数除下标的阶乘代替原数做快速傅立叶变换，之后乘以 \(i!\) 就是新的值，预处理阶乘及阶乘逆元即可。

至此问题解决，复杂度为 \(O(n^3r\text{log}r\cdot \text{log}k+q)\) 。

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;
typedef long long ll;

const int mod = 1004535809;
const int N = 10 + 5;
const int R = 5000 + 5;
const int g = 3;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int n, m, r, q;
ll rev[R], inv_n, r_n, k;
ll fac_inv[R], fac[R];

ll q_pow(ll a, ll b, ll ret = 1) {
	while (b) { if (b & 1) ret = ret * a % mod; a = a * a % mod; b >>= 1; }
	return ret;
}

void init() {
	r_n = 1 << (ll)ceil(log2(r + 1));
	r_n <<= 1;
	inv_n = q_pow(r_n, mod - 2);
	for (int i = 0; i < r_n; i++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << ((ll)log2(r_n) - 1));
	fac[0] = 1;
	for (int i = 1; i <= r; i++) fac[i] = (fac[i - 1] * i) % mod;
	fac_inv[r] = q_pow(fac[r], mod - 2);
	for (int i = r - 1; i >= 0; i--) fac_inv[i] = fac_inv[i + 1] * (i + 1) % mod;
}

void NTT(ll F[], ll _n_, int op) {
	for (int i = 0; i < _n_; i++) if (rev[i] > i) swap(F[i], F[rev[i]]);
	for (int i = 2; i <= _n_; i <<= 1) {
		ll wi = q_pow(g, op == 1 ? (mod - 1) / i : mod - 1 - (mod - 1) / i);
		for (int j = 0; j < _n_; j += i) {
			ll w = 1;
			for (int k = j, h = i >> 1; k < j + h; k++) {
				ll t = w * F[k + h], u = F[k];
				F[k] = (u + t) % mod;
				F[k + h] = ((u - t) % mod + mod) % mod;
				w = w * wi % mod;
			}
		}
	}
	if (op == -1) for (int i = 0; i < _n_; i++) F[i] = F[i] * inv_n % mod;
}

ll ta[R], tb[R];

void FFT(ll c[], const ll a[], const ll b[]) {
	memset(ta, 0, sizeof ta);
	memset(tb, 0, sizeof tb);
	for (int i = 0; i <= r; i++) {
		ta[i] = a[i] * fac_inv[i] % mod;
		tb[i] = b[i] * fac_inv[i] % mod;
	}
	NTT(ta, r_n, 1);
	NTT(tb, r_n, 1);
	for (int i = 0; i < r_n; i++) c[i] = ta[i] * tb[i] % mod;
	NTT(c, r_n, -1);
	for (int i = 0; i < r_n; i++) c[i] = c[i] * fac[i] % mod;
}

struct M {
	ll a[R];
	M() {}
	M operator + (const M &x) const {
		M ret;
		for (int i = 0; i <= r; i++) ret.a[i] = (a[i] + x.a[i]) % mod;
		return ret;
	}
	M operator * (const M &x) const {
		M ret;
		FFT(ret.a, a, x.a);
		for (int i = 0; i <= r; i++) ret.a[i] = ret.a[i] % mod;
		for (int i = r + 1; i < r_n; i++) ret.a[i] = 0;
		return ret;
	}
};

M A[N][N], t[N][N], o[N][N], a[N][N], b[N][N];

void mul(M t1[N][N], M t2[N][N]) {
	memset(t, 0, sizeof t);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++) t[i][j] = t[i][j] + t1[i][k] * t2[k][j];
	memcpy(t1, t, sizeof t);
}

void add(M t1[N][N], M t2[N][N]) {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) t1[i][j] = t1[i][j] + t2[i][j];
}

void procedure(ll k) {
	if (k == 1) return;
	procedure(k >> 1), memcpy(b, A, sizeof A), mul(A, a), mul(a, a), add(A, b);
	if (k & 1) mul(A, o), mul(a, o), add(A, o);
}

int main() {
	read(n), read(m), read(r), read(k), read(q), init();
	for (int i = 1; i <= m; i++) {
		int x, y; read(x), read(y);
		for (int j = 0; j <= r; j++) {
			A[x][y].a[j]++, A[y][x].a[j]++;
			if (x == y) A[x][y].a[j]--;
		}
	}
	memcpy(o, A, sizeof A);
	memcpy(a, A, sizeof A);
	procedure(k);
	while (q--) {
		int x, y, z; read(x), read(y), read(z);
		printf("%lld\n", A[x][y].a[z]);
	}
	return 0;
}

（\(n\) 年前某天在机房里出的题，结果std被同学们暴打，顶锅盖，逃……）

Posted on Edited on In

题目链接：Luogu P4155 [SCOI2015]国旗计划

T5 - Luogu 4155 [SCOI2015] 国旗计划 题解

第7组

题目大意

选出尽量少的区间完全覆盖一个环，输出每个区间强制选的答案，\(n\leq 2\times10^5,M\leq 10^9\).

题解

  1. 把所有战士从 \([1,m]\) 复制到 \([1,2m]\)，对应端点加 \(m\)，把 \(n\) 个节点都复制一遍.
  2. 由于区间不包含，则我们可以把所有区间按左端点排序，则右端点也会同时有序增加，此时可以利用双指针 \(O(n)\) 得到每个区间 \(i\) 的范围 \([l_i,r_i]\) 内，之后的区间中左端点 \(\leq r_i\) 的最靠右的区间 \(j\)，利用该区间贪心取尽量长的覆盖长度，设为 \(\text{nxt}[i] =j\).
  3. 倍增法：构造数组 \(f[i][j]\) 表示从 \(i\) 开始，利用刚才的 \(\text{nxt}\) 关系向后跳 \(2^j\) 步，所达到的区间编号.
  4. 利用数组 \(f[i][j]\) 倍增快速跳到刚好不能覆盖环长 \(m\) 的最右编号，之后再跳一次即可将环完全覆盖. 记录倍增时跳过的 \(2^k\) 累加为答案，并加上该区间自己.

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2 * (2e5 + 5);

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int n, m, _n, _m;

class seg {
  public:
	int l, r, nxt, id;
	seg() {}
	seg(int _l, int _r, int _id) {
		l = _l;
		r = _r;
		nxt = -1;
		id = _id;
	}
	void print() {
		printf("[%d, %d] -> %d\n", l, r, nxt);
	}
	bool operator < (const seg &o) const {
		return l < o.l;
	}
	~seg() {}
};

seg a[N];

int f[N][20], pz[N];

void print() {
	for (int i = 1; i <= n; i++) {
		a[i].print();
	}
}

#define DEBUG

int main() {
	// freopen("t5.in", "r", stdin);
	read(n), read(m);
	_n = n * 2;
	_m = m * 2;
	for (int i = 1; i <= n; i++) {
		int l, r;
		read(l), read(r);
		if (r < l) r += m;
		a[i] = seg(l, r, i);
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		a[i + n] = a[i];
		a[i + n].l = a[i].l + m;
		a[i + n].r = a[i].r + m;
	}
	int p1 = 1, p2 = 1;
	while (p1 <= _n) {
		int cr = a[p1].r;
		while (a[p2].l <= cr && p2 <= _n) {
			p2++;
		}
		a[p1].nxt = p2 - 1;
		f[p1][0] = p2 - 1;
		p1++;
	}
	for (int j = 1; j < 20; j++) {
		for (int i = 1; i <= _n; i++) {
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		seg &u = a[i], v = a[i];
		int p = i;
		int ans = 1;
		for (int j = 19; j >= 0; j--) {
			int to = f[p][j];
			if (to) {
				v = a[to];
				if (v.r < u.l + m) {
					p = to;
					ans += 1 << j;
				}
			}
		}
		pz[a[i].id] = ans + 1;
	}
	for (int i = 1; i <= n; i++) {
		printf("%d ", pz[i]);
	}
	puts("");
	return 0;
}

Posted on In

题目链接：Codeforces 1451E1 Bitwise Queries (Easy Version)

第五题 Bitwise Queries (Easy Version) 题解

第 7 组 - 2020 年 4 月 28 日

题目大意

题目有一个长度为 \(n\,(n\leq 2 ^ {16})\) 的隐藏数组，每次可以向题目询问任意两个位置 \(i\) 和 \(j\) （但 \(i\neq j\) ）的两个数的位与、位或和异或，最多问 \(n+2\) 次。

题解

自然的思路一定是尽可能确定下一个数 \(a\) ，假设已经确定了 \(a\) ，则其他的数都可以通过一次异或询问得到：\(a \text{ ^ } (a \text{ ^ } b) = b\) .

在此有补充的公式：\[a+b=a \text{ ^ } b + 2\times(a \text{ & } b)\]

于是我们实际上可以得到其中任意三个数的值：

  1. 询问 \(a \text{ & } b\)，\(b \text{ & } c\)，\(a \text{ & } c\)
  2. 询问 \(a \text{ ^ } b\)，\(b \text{ ^ } c\)，然后本地计算得到 \(a \text{ ^ } c\)
  3. 利用上面的公式得到 \(a+b\)，\(b+c\)，\(a+c\)，之后得到 \(a+b+c\)，自然可以得到每个数的值

得到这三个数的值后，便可由异或询问得到所有值了，一共询问了\(n+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
#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 16) + 5;

int n, _xor[N], A[N];
int a, b, c;
int ab, bc, ac;
int xab, xbc, xac;
int _ab, _bc, _ac;

int main() {
	scanf("%d", &n);
	printf("AND 1 2\n"), fflush(stdout), scanf("%d", &_ab);
	printf("AND 2 3\n"), fflush(stdout), scanf("%d", &_bc);
	printf("AND 1 3\n"), fflush(stdout), scanf("%d", &_ac);
	printf("XOR 1 2\n"), fflush(stdout), scanf("%d", &xab);
	printf("XOR 2 3\n"), fflush(stdout), scanf("%d", &xbc);
	xac = xab ^ xbc;
	ab = xab + (_ab << 1);
	bc = xbc + (_bc << 1);
	ac = xac + (_ac << 1);
	int s = (ab + bc + ac) / 2;
	a = s - bc,  b = s - ac, c = s - ab;
	A[1] = a, A[2] = b, A[3] = c;
	for (int i = 4; i <= n; i++) {
		printf("XOR 1 %d\n", i), fflush(stdout), scanf("%d", &_xor[i]);
		A[i] = _xor[i] ^ a;
	}
	printf("! ");
	for (int i = 1; i <= n; i++) printf("%d ", A[i]);
	printf("\n"), fflush(stdout);
	return 0;
}

Posted on Edited on In

题目链接： CodeForces 670C Cinema

第五题 Cinema 题解

Author: 第7组

2021.4.19

题目概述

有\(n\) 个人，各自会说一种语言，他们去看电影，每个电影\(q_i\)有音频语言\(a_i\)和字幕语言\(s_i\)，如果一个人能听懂，则非常开心,如果只能看懂字幕则不是非常开心但也能凑合，如果两个都不懂，他会非常愤怒。

现在要找一个电影，可以让非常开心的人最多，如果有多个方案，要求不是非常开心的最多。

题解

语言的范围是\(10^9\)，但是人数仅有\(2\times 10^5\)，于是第一步就是离散化（sort加unique）.

将语言离散化后，可以开一个数组\(e[i]\)存每个语言\(i\)有多少人会说，然后建立一个结构体存下电影的下标\(idx\)、能听懂的人数\(au\)和能看懂的人数\(su\)，然后重载小于号进行排序，分别以\(au\)和\(su\)作为第一和第二关键字即可。

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 2e5 + 5;
const int M = 2e5 + 5;

int n, m;
int a[N], b[M], c[M];
int _a[N], tot;
int e[N];
map<int, int> t;
map<int, int> rt;

// #define DEBUG

class _data {
  public:
	int idx, au, su;
	_data() {}
	_data(int _idx, int _au, int _su) : idx(_idx), au(_au), su(_su) {}
	bool operator < (const _data &o) const {
		return au ==  o.au ? su < o.su : au < o.au;
	}
	~_data() {}
} q[M];

int main() {
#ifdef DEBUG
	freopen("C.in", "r", stdin);
#endif
	read(n);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		_a[i] = a[i];
	}
	sort(_a + 1, _a + n + 1);
	tot = unique(_a + 1, _a + n + 1) - (_a + 1);
	// printf("tot = %d\n", tot);
	for (int i = 1; i <= tot; i++) {
		t[_a[i]] = i;
		rt[i] = _a[i];
	}
	for (int i = 1; i <= n; i++) {
		a[i] = t[a[i]];
		e[a[i]]++;
	}
	read(m);
	for (int i = 1; i <= m; i++) {
		read(b[i]);
		b[i] = t[b[i]];
	}
	for (int i = 1; i <= m; i++) {
		read(c[i]);
		c[i] = t[c[i]];
	}
	for (int i = 1; i <= m; i++) {
		q[i] = _data(i, e[b[i]], e[c[i]]);
	}
	sort(q + 1, q + m + 1);
	printf("%d\n", q[m].idx);
	return 0;
}

Posted on Edited on In

题目链接: https://vjudge.net/contest/418600

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e4 + 5;
int co[N];
int L, M;

int main() {
	read(L);
	read(M);
	while (M--) {
		int l, r;
		read(l);
		read(r);
		for (int i = l; i <= r; i++) {
			co[i]++;
		}
	}
	int cnt = 0;
	for (int i = 0; i <= L; i++) {
		if (!co[i]) cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}

B 铺地毯

从后往前遍历地毯，找到的第一个即为答案。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e7 + 5;

class carpet {
  public:
	int id, a, b, x, y;
	carpet(int _id, int _a, int _b, int _x, int _y) {
		id = _id;
		a = _a;
		b = _b;
		x = _x;
		y = _y;
	}
};

vector<carpet> c;

int n;

int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		int a, b, x, y;
		read(a), read(b), read(x), read(y);
		c.push_back(carpet(i, a, b, x, y));
	}
	int X, Y;
	read(X), read(Y);
	vector<carpet>::reverse_iterator it;
	for (it = c.rbegin(); it != c.rend(); it++) {
		carpet o = *it;
		// printf("GET %d %d %d %d\n", o.a, o.b, o.x, o.y);
		if (X >= o.a && X <= o.a + o.x && Y >= o.b && Y <= o.b + o.y) {
			printf("%d\n", o.id);
			return 0;
		}
	}
	puts("-1");
	return 0;
}

C 低买高卖

维护一个小根堆，每一个元素表示前 \(i-1\) 天中可以和当前第 \(i\) 天进行一次购买售出操作的股票。设 \(a[i]\) 表示股票价格，当堆顶小于当前价格时，贪心使用堆顶的股票低买高卖；若堆顶大于当前价格，则把今日的股票插入堆中两次。为什么要放两次？因为实际上在某一天什么都不做，相当于买入一股又立马卖出一股，其不会改变收入，但买入和卖出的股票由于不存在标识，完全可以认为是不同的股票。刚才插入的两股，第一股如果在未来被使用，则可认为其做了一次“中间股票”；第二股则是传统意义上的，该股票在未来的某一天被对应卖出。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 200000 + 5;
int a[N], n;

priority_queue<int, vector<int>, greater<int>> p;

int main() {
	read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	p.push(a[1]);
	int ans = 0;
	for (int i = 2; i <= n; i++) {
		int x = a[i];
		if (x < p.top()) {
			p.push(x);
		} else {
			ans += x - p.top();
			p.pop();
			p.push(x);
			p.push(x);
		}
	}
	printf("%d\n", ans);
	return 0;
}

D IP地址转换

使用位运算模拟即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int main() {
	char c = 0;
	int a = 0;
	while (c != '-') {
		c = getchar();
		if (c == '.') {
			// printf("PRINT a = %d\n", a);
			for (int i = 7; i >= 0; i--) {
				int b = (a >> i) & 1;
				printf("%d", b);
			}
			a = 0;
			continue;
		}
		if (c == '\n') {
			for (int i = 7; i >= 0; i--) {
				int b = (a >> i) & 1;
				printf("%d", b);
			}
			a = 0;
			printf("\n");
			continue;
		}
		a = a * 10 + c - '0';
	}
	return 0;
}

E 明明的随机数

sort()与unique()函数。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 100 + 5;

int n, a[N];

int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
	}
	sort(a + 1, a + n + 1);
	int m = unique(a + 1, a + n + 1) - (a + 1);
	printf("%d\n", m);
	for (int i = 1; i <= m; i++) {
		printf("%d ", a[i]);
	}
	puts("");
	return 0;
}

F 拼数

观察了一下样例，发现这不就是字典序嘛，果断WA了。后来发现 \(432\) 字典序比 \(43\) 大，但是实际上却应该是 \(43432\) ，把字典序比较换成了 \(a+b\lt b+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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

string s[2500];
int n;

bool cmp(string a, string b) {
	return a + b > b + a;
}

int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	sort(s + 1, s + n + 1, cmp);
	for (int i = 1; i < n; i++) {
		string a = s[i];
		string b = s[i + 1];
	}
	for (int i = 1; i <= n; i++) {
		cout << s[i];
	}
	puts("");
	return 0;
}

G 今年暑假不AC

把线段按左端点排序，然后从右往左遍历排好的线段，贪心取不重叠的线段即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

class segment {
  public:
	int l, r;
	segment(int _l = 0, int _r = 0) {
		l = _l, r = _r;
	}
	bool operator < (const segment o) const {
		return l < o.l;
	}
};

int n;
segment a[105];

void init() {
	memset(a, 0, sizeof a);
}

int main() {
	while (scanf("%d", &n)) {
		if (n == 0) break;
		init();
		for (int i = 1; i <= n; i++) {
			int l, r;
			read(l), read(r);
			a[i] = segment(l, r);
		}
		sort(a + 1, a + n + 1);
#ifdef DEBUG
		for (int i = 1; i <= n; i++) {
			printf("[%d, %d]\n", a[i].l, a[i].r);
		}
#endif
		int ans = 1;
		segment x = a[n];
		for (int i = n - 1; i >= 1; i--) {
			if (a[i].r <= x.l) {
				ans++;
				x = a[i];
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

H 排座椅

取桌子之间的间隙建立新网格，对行和列贪心取“串”起来最多的即可。(OOP大法好！)

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void r(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int _N_ = 1000 + 5;
const int _D_ = 2000 + 5;

int a[_N_], b[_N_];
int M, N, K, L, D;

class data {
  public:
	int id, cnt;
	data() {
		id = cnt = -1;
	}
	data(int _id, int _cnt) {
		id = _id, cnt = _cnt;
	}
	bool operator < (const data o) const {
		return cnt > o.cnt;
	}
};

data A[_N_], B[_N_];

int main() {
	r(M), r(N), r(K), r(L), r(D);
	for (int i = 1; i <= D; i++) {
		int x1, y1, x2, y2;
		r(x1), r(y1), r(x2), r(y2);
		if (y1 == y2) {
			int x = min(x1, x2);
			a[x]++;
		}
		if (x1 == x2) {
			int y = min(y1, y2);
			b[y]++;
		}
	}
	int tot_A = 0, tot_B = 0;
	for (int i = 1; i < M; i++) {
		if (a[i]) {
			A[++tot_A] = data(i, a[i]);
		}
	}
	for (int i = 1; i < N; i++) {
		if (b[i]) {
			B[++tot_B] = data(i, b[i]);
		}
	}
	sort(A + 1, A + tot_A + 1);
	sort(B + 1, B + tot_B + 1);
	vector<int> v, _v;
	vector<int>::iterator it;
	for (int i = 1; i <= K; i++) {
		v.push_back(A[i].id);
	}
	sort(v.begin(), v.end());
	for (it = v.begin(); it != v.end(); it++) {
		int x = *it;
		printf("%d ", x);
	}
	puts("");
	for (int i = 1; i <= L; i++) {
		_v.push_back(B[i].id);
	}
	sort(_v.begin(), _v.end());
	for (it = _v.begin(); it != _v.end(); it++) {
		int x = *it;
		printf("%d ", x);
	}
	puts("");
	return 0;
}

I 回文日期

强行手写一个日期类，然后枚举判断即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void r(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

class date {
  public:
	int y, m, d;
	date(string s) {
		int _y = atoi(s.substr(0, 4).c_str());
		int _m = atoi(s.substr(4, 2).c_str());
		int _d = atoi(s.substr(6, 2).c_str());
		y = _y, m = _m, d = _d;
	}
	bool operator == (const date A) const {
		return A.y == y && A.m == m && A.d == d;
	}
	void print() {
		printf("YEAR=%d MONTH=%d DAY=%d\n", y, m, d);
	}
	string sprint() {
		char s[10];
		sprintf(s, "%d%02d%02d\n", y, m, d);
		string str = s;
		return str;
	}
	void update() {
		if (m == 1 ||
		        m == 3 ||
		        m == 5 ||
		        m == 7 ||
		        m == 8 ||
		        m == 10
		   ) {
			if (d == 31) {
				d = 1;
				m++;
			} else {
				d++;
			}
		} else if (m == 12) {
			if (d == 31) {
				d  = 1;
				m = 1;
				y++;
			} else {
				d++;
			}
		} else if (m == 2) {
			if ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) {
				if (d == 29) {
					d = 1;
					m++;
				} else {
					d++;
				}
			} else {
				if (d == 28) {
					d = 1;
					m++;
				} else {
					d++;
				}
			}
		} else {
			if (d == 30) {
				d = 1;
				m++;
			} else {
				d++;
			}
		}
	}
};

string A, B;

bool good(string str) {
	// printf("\t---COMPARING");
	int len = 8;
	for (int i = 0; i < len / 2 + 1; i++) {
		int j = len - i - 1;
		// printf(" j = %d   %c <-> %c  \n", j, str[i], str[j]);
		if (str[i] != str[j]) return false;
	}
	return true;
}

int main() {
	cin >> A >> B;
	date a(A), b(B);
	b.update();
	int cnt = 0;
	for (date t = a; !(t == b); t.update()) {
		// printf("NOW AT DATE -> ");
		// cout << t.sprint();
		if (good(t.sprint())) cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}

J Claris and XOR

（这题真是要了老命）

贪心从高到低构造 \(1\) ，考虑当前是第 \(i\) 位，若 \(x\) 和 \(y\) 在这一位的取法均为任意，则后面所有位一定都可以任意取，这时直接把答案的后面全取为 \(1\) 。如果两个数在这一位的取法受限，则贪心构造出答案 \(1\) 。如果贪心也不行则只能填上 \(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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

ll a, b, c, d;
int T;

void print(ll x) {
	for (int i = 63; i >= 0; i--) {
		int p = x >> i & 1;
		printf("%d", p);
	}
}

int main() {
	read(T);
	while (T--) {
		read(a), read(b), read(c), read(d);
		ll ans = 0;
		ll ta, tb, tc, td;
		ta = a;
		tb = b;
		tc = c;
		td = d;
		for (int i = 62; i >= 0; i--) {
			ll t = 1LL << (i + 1);
			ll _t = 1LL << i;
			// printf("i = %d \t_t =\n", i); print(_t); puts(""), puts("---");
			int x0, x1, y0, y1;
			x0 = x1 = y0 = y1 = 0;
			if (ta <= _t - 1) x0 = 1;
			if (tb >= _t) x1 = 1;
			if (tc <= _t - 1) y0 = 1;
			if (td >= _t) y1 = 1;
			// printf("x0=%d  x1=%d  y0=%d  y1=%d\n", x0, x1, y0, y1);
			if (x0 && x1 && y0 && y1) {
				ans += t - 1;
				break;
			}
			if (x0 && y1) {
				ans += _t;
				tc -= _t;
				td -= _t;
				continue;
			}
			if (x1 && y0) {
				ans += _t;
				ta -= _t;
				tb -= _t;
				continue;
			}
			if ((!x0) && (!y0)) {
				ta -= _t;
				tb -= _t;
				tc -= _t;
				td -= _t;
			}
			// print(td), puts("");
			// print(tc), puts("");
			// print(tb), puts("");
			// print(ta), puts("");
			// puts("------------");
		}
		printf("%lld\n", ans);
	}
	return 0;
}

K Flip Game

注意到，翻片儿的顺序不会产生影响，则同一个地方最多翻一次即可，直接进行DFS记忆化搜索。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void r(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int a[5][5];
int G1, G2, st[100000];

void print(int x[][5]) {
	puts("------\nPRINT\n------");
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			printf("%d", x[i][j]);
		}
		puts("");
	}
	puts("------\nEND PRINT\n------");
}

int trans(int x[][5]) {
	int ret = 0;
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			ret = (ret << 1) | x[i][j];
		}
	}
	return ret;
}

int g1[5][5], g2[5][5];
bool vis[5][5];

void dfs(int x[][5], int cnt) {
	int sta = trans(x);
	if (st[sta] <= cnt) {
		return;
	}
	st[sta] = cnt;
	// printf("CURRENTLY AT -> cnt = %d\n", cnt);
	// print(x);
	if (sta == G1 || sta == G2) {
		return;
	}
	int t[5][5];
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			t[i][j] = x[i][j];
		}
	}
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (!vis[i][j]) {
				t[i][j] ^= 1;
				if (i - 1 >= 1) t[i - 1][j] ^= 1;
				if (i + 1 <= 4) t[i + 1][j] ^= 1;
				if (j - 1 >= 1) t[i][j - 1] ^= 1;
				if (j + 1 <= 4) t[i][j + 1] ^= 1;

				vis[i][j] = true;
				dfs(t, cnt + 1);
				vis[i][j] = false;

				t[i][j] ^= 1;
				if (i - 1 >= 1) t[i - 1][j] ^= 1;
				if (i + 1 <= 4) t[i + 1][j] ^= 1;
				if (j - 1 >= 1) t[i][j - 1] ^= 1;
				if (j + 1 <= 4) t[i][j + 1] ^= 1;
			}
		}
	}
}

int main() {
	memset(st, 0x7f7f7f7f, sizeof st);
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			g1[i][j] = 0;
			g2[i][j] = 1;
		}
	}
	G1 = trans(g1);
	G2 = trans(g2);
	for (int i = 1; i <= 4; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < 4; j++) {
			if (str[j] == 'b') {
				a[i][j + 1] = 1;
			} else {
				a[i][j + 1] = 0;
			}
		}
	}
	// print(a);
	// printf("G1 = %d, G2 = %d\n", G1, G2);
	dfs(a, 0);
	int ans  = min(st[G1], st[G2]);
	if (ans >= 0x7f7f7f7f) puts("Impossible");
	else printf("%d\n", ans);
	return 0;
}

M Unique Snowflakes

滑动窗口型问题，我好像写了一个st表加二分的方法……（离谱）。

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;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e6 + 5;
const int logN = 30;
int a[N], lst[N], f[N][logN];
int T, n;

map<int, int> c;

void init() {
	c.clear();
	memset(a, 0, sizeof a);
	memset(lst, 0, sizeof a);
	memset(f, 0, sizeof f);
}

int ask(int L, int R) {
	int k = log2(R - L + 1);
	return max(f[L][k], f[R - (1 << k) + 1][k]);
}

int main() {
	read(T);
	while (T--) {
		init();
		read(n);
		for (int i = 1; i <= n; i++) {
			read(a[i]);
			if (!c[a[i]]) {
				c[a[i]] = i;
			} else {
				lst[i] = c[a[i]];
				c[a[i]] = i;
			}
			f[i][0] = lst[i];
		}
		for (int j = 1; j <= 21; j++) {
			for (int i = 1; i + (1 << j) - 1 <= n; i++) {
				f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
			}
		}
		int ans = -1;
		for (int i = 1; i <= n; i++) {
			int L = i, R = n, mid;
			while (L <= R) {
				mid = (L + R) / 2;
				int mx = ask(i, mid);
				if (mx < i) L = mid + 1;
				else R = mid - 1;
			}
			int tmp = L - i;
			ans = max(ans, tmp);
		}
		printf("%d\n", ans);
	}
	return 0;
}

N Hero

一开始写了一个奇怪的贪心给WA了，实际上直接利用 \(\displaystyle\frac{\text{HP}_i}{\text{DPS}_i}\) 越小越好的贪心就可以了。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

#define INF 0x3f3f3f3f

class hero {
  public:
	int HP, DPS;
	hero(int _HP = -1, int _DPS = -1) {
		HP = _HP, DPS = _DPS;
	}
	bool operator < (const hero o) const {
		return HP * o.DPS < DPS * o.HP;
	}
};

hero a[25];
int n;
int sum_HP, sum_DPS;
bool vis[25];

void init() {
	sum_DPS = sum_HP = 0;
	memset(a, -1, sizeof a);
	memset(vis, 0, sizeof vis);
}

int main() {
	while (~scanf("%d", &n)) {
		init();
		int dps, hp;
		for (int i = 1; i <= n; i++) {
			read(dps), read(hp);
			a[i] = hero(hp, dps);
			sum_HP += hp;
			sum_DPS += dps;
		}
		int ans = 0;

#if 1
		sort(a + 1, a + n + 1);
		int ts = 0;
		for (int i = 1; i <= n; i++) {
			ans += a[i].HP * (sum_DPS - ts);
			ts += a[i].DPS;
		}
		printf("%d\n", ans);

#endif

#if 0

		for (int j = 1; j <= n; j++) {
			int good = -1, td = -INF;
			int tmp_s = 0;
			for (int i = 1; i <= n; i++) {
				if (!vis[i]) {
					tmp_s += a[i].DPS;
				}
			}
			for (int i = 1; i <= n; i++) {
				if (!vis[i]) {
					int st = a[i].HP * (tmp_s - a[i].DPS);
					if (st > td) {
						td = st;
						good = i;
					}
				}
			}
			// printf("j = %d  good = %d  td = %d\n", j, good, td);
			vis[good] = true;
			ans += td;
		}
		int oth = sum_HP * sum_DPS;
		ans = oth - ans;
		printf("%d\n", ans);

#endif

	}
	return 0;
}