0%

CF Round 1305

$\text{C}$

看到 $m \leq 1000$,就会收到一个很明显的提示,即可以直接枚举答案。

枚举差之后计算一下个数,快速幂一下就行了。

当然如果你脑回路正常,会意识到根据鸽巢原理,当 $n > m$ 的时候答案一定是 $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
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
int read() {
int f = 1, x = 0; 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 f * x;
}
int mod;
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }
inline int add (int a, int b) { return a + b >= (mod - 1) ? a + b - (mod - 1) : a + b; }
inline int circ (int x) { while (x >= mod) x -= mod; return x; }
const int N = 202000;
int n, a[N], pric[N];
unordered_map <int, int> p;
int main() {
n = read(), mod = read();
if (n > mod) return puts("0"), 0;
for (int i = 1; i <= n; ++i) a[i] = read();
ll ans = 1;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
ans = ans * abs(a[i] - a[j]) % mod;
cout << ans << '\n';
return 0;
}

$\text{D}$

很好的一道构造题。

对于每步询问,我们都去询问两个度数为 $1$ 的点。这样有一个好处:如果他们两个的 $\text{LCA}$ 就是其一,那么是 $\text{LCA}$ 的那个点就是根(这个性质画图显然),否则我们就可以直接把这两个叶子删掉,牵出新的叶子。

这样如果每次没找到答案,最后一定至少没了两个点,所以最后一定能找到解。

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
#include <bits/stdc++.h>
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
int read() {
int f = 1, x = 0; 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 f * x;
}
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }

const int N = 100010;
int n, r, x[N], y[N], d[N], banned[N];
vector <int> g[N];
int main() {
n = read();
rep (i, 1, n - 1) {
x[i] = read(), y[i] = read();
d[x[i]]++, d[y[i]]++;
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
set <int> st;
rep (i, 1, n) st.insert(i);
while (true) {
if (st.size() == 1) return cout << "! " << *(st.begin()) << endl, 0;
vector <int> v;
rep (i, 1, n) if (d[i] == 1) v.push_back(i);
assert(v.size());
if (v.size() < 2) return cout << "! " << v[0] << endl, 0;
cout << "? " << v[0] << " " << v[1] << endl;
int lca = read();
if (lca == v[0] || lca == v[1]) return cout << "! " << lca, 0;
else {
st.erase(v[0]), st.erase(v[1]);
rep (i, 1, n - 1) if (x[i] == v[0] || x[i] == v[1] || y[i] == v[0] || y[i] == v[1]) {
if (!banned[i]) banned[i] = 1, --d[x[i]], --d[y[i]];
}
}
}
return 0;
}

$\text{E}$

挺神仙的

考虑如果我们要构造尽可能多的答案该如何去构造:直接构造 $1, 2, 3…x$ 即可。

但是如果这样构造到一个地方多了怎么办呢?令当前和为 $cnt$,那我们让当前这个数加上 $2\times (cnt - 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
#include <bits/stdc++.h>
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
int read() {
int f = 1, x = 0; 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 f * x;
}
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }

const int N = 5050;
int n, m, a[N], answer[N];
int main() {
cin >> n >> m;
int now = 0;
for (int i = 1; i <= n; ++i) {
now += (i - 1) / 2;
answer[i] = i;
if (now >= m) {
int dt = now - m;
answer[i] += 2 * dt;
for (int j = n, num = 1e9; j > i; j--, num -= answer[i] + 1)
answer[j] = num;
rep (j, 1, n) printf("%d ", answer[j]);
return 0;
}
}
puts("-1");
return 0;
}