Codeforces Round #775 (Div. 2)
如果是 $1$ 就直接跳，可以使用一次魔法向后跳。显然只能在前后跳。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, w[N];
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> w[i];
int p = 1, q = n;
while (p + 1 <= n && w[p + 1] == 1)
p++;
while (q > 1 && w[q - 1] == 1)
q--;
cout << (p >= q ? 0 : q - p) << endl;
}
return 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>
using namespace std;
const int N = 1e5 + 10;
int n, w[N];
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n;
int mx = 0;
long long sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
w[i] > mx && (mx = w[i]);
sum += w[i];
}
if (sum == 0)
puts("0");
else if (mx > sum - mx)
printf("%lld\n", mx - (sum - mx));
else
puts("1");
}
return 0;
}
|
给定一个矩阵，对于其中任意两个相同的数 $w _ {x _ 1, y _ 1}, w _ {x _ 2, y _ 2}$ ，贡献代价 $\left | x _ 1 - x _ 2 \right | \left | y _ 1 - y _ 2 \right |$ 。求总代价。
将所有的数相同的数放在一起，将行和列分开计算。现在问题转化为一个序列，两两求绝对值差的和。可以将所有的排序了求，也可以树状数组求。
查看代码
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
| #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
x < 0 && (putchar('-'), x = ~x + 1);
x > 9 && (write(x / 10), 0);
putchar(x % 10 + '0');
}
const int N = 1e5 + 10;
int n, m, w[N];
vector<int> c[N], r[N];
LL calc(vector<int> &x)
{
sort(x.begin(), x.end());
LL d = 0, res = 0;
for (int i = 0; i < x.size(); i++)
{
res += (LL)i * x[i] - d;
d += x[i];
}
return res;
}
int main()
{
read(n), read(m);
vector<int> ws;
for (int i = 0; i < n * m; i++)
{
read(w[i]);
ws.push_back(w[i]);
}
sort(ws.begin(), ws.end());
int len = ws.erase(unique(ws.begin(), ws.end()), ws.end()) - ws.begin();
for (int i = 0; i < n * m; i++)
{
w[i] = lower_bound(ws.begin(), ws.end(), w[i]) - ws.begin();
c[w[i]].push_back(i / m);
r[w[i]].push_back(i % m);
}
LL res = 0;
for (int i = 0; i < len; i++)
res += calc(c[i]) + calc(r[i]);
write(res);
return 0;
}
|
一个序列合法当且仅当对于任意序列中的两个数 $x \ge y$ ，$\left \lfloor \frac x y \right \rfloor$ 也在序列中。考虑一个在序列中的数 $y$ ，对 $x \in [ky, ky + y)$ ，$\left \lfloor \frac x y \right \rfloor = k$ ，即如果 $[ky, ky + y)$ 有序列中的数，一定必须存在 $k$ 。这样对于每个数枚举 $k$ ，时间复杂度为 $O(n) + O(\frac n 2) +… + O(\frac n n) = O(n \ln n)$ 。可以通过。判断一段区间是否有一个数，可以在值域上做前缀和。
查看代码
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, c, w[N], s[N];
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> w[i], s[w[i]]++;
for (int i = 1; i <= c; i++)
s[i] += s[i - 1];
bool flag = s[1] > 0;
for (int i = 1; i <= c && flag; i++)
for (int j = 1; s[i] > s[i - 1] && j * i <= c && flag; j++)
(s[min(j * i + i - 1, c)] - s[j * i - 1]) && !(s[j] - s[j - 1]) && (flag = false);
puts(flag ? "Yes" : "No");
for (int i = 1; i <= c; i++)
s[i] = 0;
}
return 0;
}
|
类似数位 DP 的方式，对于每一位，考察选择小于当前的数和等于当前的数。
如果当前的位置选择小的数，那么后面的随便选。
在没有限制 $i$ 为前，可能的答案有：
$$
\frac {(n - i + 1) !}{cnt _ 1 ! cnt _ 2 ! … cnt _ m !}
$$
限制之后：
$$
\frac {(n - i) !}{cnt _ 1 ! cnt _ 2 ! … (cnt _ m - 1) !}
$$
乘上了 $\frac {cnt _ m}{n - i + 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
x < 0 && (putchar('-'), x = ~x + 1);
x > 9 && (write(x / 10), 0);
putchar(x % 10 + '0');
}
const int N = 2e5 + 10, mod = 998244353;
int inv[N], fact[N], ifact[N];
int n, m, L, A[N], B[N], cnt[N << 1], tr[N << 1];
void add(int x, int k)
{
for (; x <= L; x += x & -x)
tr[x] += k;
}
int query(int x)
{
int res = 0;
for (; x; x -= x & -x)
res += tr[x];
return res;
}
void init()
{
inv[1] = 1;
for (int i = 2; i < N; i++)
inv[i] = -(LL)(mod / i) * inv[mod % i] % mod;
fact[0] = ifact[0] = 1;
for (int i = 1; i < N; i++)
{
fact[i] = (LL)fact[i - 1] * i % mod;
ifact[i] = (LL)ifact[i - 1] * inv[i] % mod;
}
}
int main()
{
read(n), read(m);
init();
vector<int> ws;
for (int i = 1; i <= n; i++)
read(A[i]), ws.push_back(A[i]);
for (int i = 1; i <= m; i++)
read(B[i]), ws.push_back(B[i]);
sort(ws.begin(), ws.end());
L = ws.erase(unique(ws.begin(), ws.end()), ws.end()) - ws.begin();
for (int i = 1; i <= n; i++)
A[i] = lower_bound(ws.begin(), ws.end(), A[i]) - ws.begin() + 1;
for (int i = 1; i <= m; i++)
B[i] = lower_bound(ws.begin(), ws.end(), B[i]) - ws.begin() + 1;
int res = 0, cur = fact[n];
for (int i = 1; i <= n; i++)
cnt[A[i]]++;
for (int i = 1; i <= L; i++)
cur = (LL)cur * ifact[cnt[i]] % mod;
for (int i = 1; i <= L; i++)
add(i, cnt[i]);
bool flag = true;
for (int i = 1; i <= min(n, m); i++)
{
cur = (LL)cur * inv[n - i + 1] % mod;
(res += (LL)query(B[i] - 1) * cur % mod) %= mod;
if (!cnt[B[i]])
{
flag = false;
break;
}
add(B[i], -1);
cur = (LL)cur * (cnt[B[i]]--) % mod;
}
printf("%d", (res + (n < m && flag) + mod) % mod);
return 0;
}
|