Codeforces Round #802 (Div. 2)
[Link](Dashboard - Codeforces Round #802 (Div. 2) - Codeforces)
A. Optimal Path
题意
? 给你一个
(
n
,
m
)
(n,m)
(n,m)的矩阵，第
(
i
,
j
)
(i,j)
(i,j)个位置的数字是
(
i
?
1
)
×
m
+
j
(i-1)\times m + j
(i?1)×m+j，问你从左上角向右下角走，每次只能向右或向左走，问你途径数字和的最小值是多少。
思路
? 相当于每次
i
+
1
i+1
i+1或
j
+
1
j+1
j+1，显然
i
i
i这一位的权是
m
m
m因此先加
j
j
j更优，没法的时候才能加
i
i
i
Code
#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T;
cin >> T;
while (T -- ) {
cin >> n >> m;
LL res = 0;
for (int i = 1; i <= m; i ++) res += i;
for (int i = 2; i <= n; i ++) res += (LL)(i - 1) * m + m;
cout << res << '\n';
}
return 0;
}
B. Palindromic Numbers
题意
? 给你一个
n
n
n位置的数字
a
a
a，让你构造一个不含前导零的
n
n
n位数字
b
b
b，并且使得
a
+
b
a+b
a+b是一个回文数字
思路
假设
a
+
b
=
c
a+b=c
a+b=c，那么我们直接找一个回文数字
c
c
c，让
c
?
a
=
b
c-a=b
c?a=b，如果
a
a
a的第一位不是
9
9
9，我们可以用
999...9
999...9
999...9来构造，如果是
9
9
9由于
b
b
b不能有前导零，因此选
11111
11111
11111这样的即可
Code
#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T;
cin >> T;
while (T -- ) {
cin >> n;
string str; cin >> str;
if (str[0] == '9') {
int t = 1;
string res = string(n + 1, '1'), b;
reverse(str.begin(), str.end());
int d = 0;
for (int i = 0; i < n; i ++) {
int t = res[i] - str[i] - d;
if (t < 0) {
d = 1;
t += 10;
}
else d = 0;
b += ('0' + t);
}
reverse(b.begin(), b.end());
cout << b << '\n';
}
else {
for (int i = 0; i < str.size(); i ++)
cout << 9 - (str[i] - '0');
cout << '\n';
}
}
return 0;
}
C. Helping the Nature
题意
? 给你一个长度位
n
n
n的数组
a
a
a，每次操作可以：1. 选择一个前缀都减一 2.选择一个后缀都减一 3.整体都加一，问你最少操作多少次可以使
a
a
a数组为
0
0
0。
思路
? 区间问题想差分，设
d
d
d为
a
a
a的差分数组即
d
i
=
a
i
?
a
i
?
1
d_i=a_i-a_{i-1}
di?=ai??ai?1?，那么我们的三个操作转化为对
b
b
b数组 1. 第一个位置减一后面后一个位置加一 2.某个位置减一 3.第一个位置加一，目标转化为将
d
d
d数组弄成全零
? 从第
2
2
2个位置看如果第
i
i
i个位置是
>
0
>0
>0的我们直接用操作二即可，如果是小于零的我们使用操作一并影响第
1
1
1个位置，最后在用操作三将第一个位置弄好即可
Code
#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
LL a[N], d[N];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T;
cin >> T;
while (T -- ) {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) d[i] = a[i] - a[i - 1];
LL res = 0;
for (int i = 2; i <= n; i ++)
if (d[i] < 0) {
res -= d[i];
d[1] += d[i];
}
else res += d[i];
res += abs(d[1]);
cout << res << '\n';
}
return 0;
}
D. River Locks
题意
? 给你
n
n
n个连续放这个水桶，第
i
i
i个水桶容量为
a
i
a_i
ai?，你可以任选一些水桶上卡一个水管开始往下流水，每秒流下
1
1
1的水，如果第
i
i
i桶水满了会无延迟的将多的给第
i
+
1
i+1
i+1桶水，一直到最后一桶水流向大海，给你
q
q
q个询问，每次给你一个时间
t
t
t，问你最少开多少个水管可以在
t
t
t秒后所有的桶都是满的，如果无解输出
?
1
-1
?1
思路
? 首先我们考虑无解的情况，设
s
s
s为
a
a
a的前缀和，对于第
i
i
i个桶我们最坏的情况下需要
t
i
t_i
ti?的时间能将其灌满，即前
i
i
i个桶都开水管且前
i
?
1
i-1
i?1个桶流入第
i
i
i个桶的水加上其本身的水要
≥
a
i
\ge a_i
≥ai?，也就是
(
t
i
×
(
i
?
1
)
?
s
i
?
1
+
t
i
≥
s
i
?
s
i
?
1
)
( t_i \times (i-1) - s_{i-1}+t_i\ge s_i-s_{i-1})
(ti?×(i?1)?si?1?+ti?≥si??si?1?)
→
t
i
\to t_i
→ti?
×
i
≥
s
i
→
t
i
≥
?
s
i
i
?
\times i\ge s_i \to t_i\ge \lceil \frac{s_i}{i}\rceil
×i≥si?→ti?≥?isi???，因此我们只需要统计
?
s
i
i
?
\lceil \frac{s_i}{i}\rceil
?isi???的最大值
m
x
mx
mx即可判断是否无解
? 如果
m
x
≥
t
mx\ge t
mx≥t 则一定有解，否则的话无脑想一下，从前往后我们记录一个前面在
t
t
t时间内可以流过来多少
v
v
v，如果
v
≥
a
i
v\ge a_i
v≥ai?则这个位置不需要开水管，否则一定需要，这样贪心最优，但是复杂度太高了
? 在继续往下想如果对于
i
i
i来说他不得不开一个管子，这个时候我们就可以把这个管子开到前面的某一个位置，这样对
i
i
i的作用是一样的。假设前
i
?
1
i-1
i?1都成立了且开了
k
k
k个管子则对于第
i
i
i个来说
a
i
?
(
t
×
k
?
s
i
?
1
)
a_i-(t\times k-s_{i-1})
ai??(t×k?si?1?)是否大于
0
0
0就是判断当前这个是否需要开一个管子，即判断
s
i
?
t
×
k
s_i-t\times k
si??t×k是否
0
0
0，如果小于零可以不开，否则一定开一个，因此我们要让
i
∈
[
1
,
n
]
i\in [1,n]
i∈[1,n]均满足
s
i
?
t
×
k
≤
0
s_i-t\times k\le 0
si??t×k≤0，即我们从第一个位置开始连续开多少个管子可以将所有的桶在
t
t
t秒内灌满，即
?
s
i
t
?
\lceil \frac{s_i}{t}\rceil
?tsi???
Code
#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
LL s[N];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i], s[i] = s[i - 1] + a[i];
LL mx = -1e20;
for (int i = 1; i <= n; i ++)
mx = max(mx, (s[i] + i - 1) / i);
cin >> m;
while (m --) {
LL t; cin >> t;
if (t < mx) cout << -1 << '\n';
else cout << (s[n] + t - 1) / t << '\n';
}
return 0;
}
E. Serega the Pirate
题意
? 给你一个
n
×
m
n\times m
n×m的矩阵，矩阵中的元素均属于
[
1
,
n
×
m
]
[1,n\times m]
[1,n×m]且各不相同，每次你从
1
1
1开始走，你只能走你走过的位置，或者大于你当前走过的最大值
+
1
+1
+1的位置，一次操作可以任意交换两个位置的数字，问你是否能在
0
,
1
,
≥
2
0,1,\ge 2
0,1,≥2次操作走完这个矩阵，
0
0
0次操作输出
0
0
0，
≥
2
\ge2
≥2次操作输出
2
2
2，
1
1
1次操作输出有多少种不同的操作方法。
思路
? 我们的题意等价于有一个不规则的圈，每次要往外吞一个点，但是这样模拟的去想是很难想的
? 因此我们换个角度，考虑每个元素，对于
(
i
,
j
)
(i,j)
(i,j)这个位置的元素
k
k
k来说什么时候他有解呢，即当他的上下左右有一个位置的值比他小的时候有解，注意这里的有解是指
[
1
,
k
?
1
]
[1,k-1]
[1,k?1]均有解了来推
k
k
k的时候，如果
[
1
,
k
?
1
]
[1,k-1]
[1,k?1]都没解跟别提
k
k
k了，由于
[
1
,
k
?
1
]
[1,k-1]
[1,k?1]均有解他们在一个圈内因此一定可以通过圈内的移动走到
(
i
,
j
)
(i,j)
(i,j)周围比他小的这个位置，因此他一定有解。
? 所以我们可以统计一下有多少个块无解，假设为
b
a
d
bad
bad个无解。我们任意交换两个块最多改变
10
10
10个块的情况即两个块的上下左右和两个块本身，因此如果
b
a
d
>
10
bad>10
bad>10则一定需要
≥
2
\ge 2
≥2次操作，如果
b
a
d
=
=
0
bad==0
bad==0则操作为
0
0
0，对于
1
1
1次操作的我们可以暴力的来判断，对于一个坏块我们可以交换它周围的或者交换它，由于一个坏的块一定要被弄好才有解，因此我们枚举第一个块的五个位置暴力的整个矩阵去换，每次判断是否换完以后没有坏的块了来判断当前是否有解，如果最后操作完我们都没有一组解则说明需要
≥
2
\ge 2
≥2次操作
Code
#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0, 0}, dy[] = {0, 1, 0, -1, 0};
int n, m, k;
vector<vector<int> > a;
vector<vector<bool> > st, tag;
bool bound(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
bool check(int x, int y) {
if (a[x][y] == 1) return false;
bool ok = true;
for (int i = 0; i < 4; i ++) {
int xx = x + dx[i], yy = y + dy[i];
if (bound(xx, yy) && a[xx][yy] < a[x][y])
ok = false;
}
return ok;
}
vector<PII> bad;
bool check(int x1, int y1, int x2, int y2) {
swap(a[x1][y1], a[x2][y2]);
int cnt = 0;
for (int i = 0; i < 5; i ++) {
int xx = x1 + dx[i], yy = y1 + dy[i];
if (bound(xx, yy) && !st[xx][yy]) {
cnt += (tag[xx][yy] - check(xx, yy));
st[xx][yy] = true;
}
}
for (int i = 0; i < 5; i ++) {
int xx = x2 + dx[i], yy = y2 + dy[i];
if (bound(xx, yy) && !st[xx][yy]) {
cnt += (tag[xx][yy] - check(xx, yy));
st[xx][yy] = true;
}
}
for (int i = 0; i < 5; i ++) {
int xx = x1 + dx[i], yy = y1 + dy[i];
if (bound(xx, yy)) st[xx][yy] = false;
xx = x2 + dx[i], yy = y2 + dy[i];
if (bound(xx, yy)) st[xx][yy] = false;
}
swap(a[x1][y1], a[x2][y2]);
return cnt == bad.size();
}
struct Node {
int x1, y1, x2, y2;
bool operator<(Node t)const {
if (t.x1 != x1) return t.x1 < x1;
else if (t.x2 != x2) return t.x2 < x2;
else if (t.y1 != y1) return t.y1 < y1;
return t.y2 < y2;
}
};
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
a.resize(n + 1), tag.resize(n + 1), st.resize(n + 1);
for (int i = 1; i <= n; i ++) {
a[i].resize(m + 1), tag[i].resize(m + 1), st[i].resize(m + 1);
for (int j = 1; j <= m; j ++)
cin >> a[i][j];
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
if (check(i, j))
bad.push_back({i, j}), tag[i][j] = 1;
map<Node, bool> mp;
if (!bad.size()) return cout << 0 << '\n', 0;
else if (bad.size() > 10) return cout << 2 << '\n', 0;
int res = 0;
int cnt = 0;
for (int k = 0; k < 5; k ++) {
int xx = bad[0].x + dx[k], yy = bad[0].y + dy[k];
if (bound(xx, yy)) {
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
if (check(i, j, xx, yy) && !mp[{i, j, xx, yy}] && !mp[{xx, yy, i, j}]) res ++, mp[{xx, yy, i, j}] = true, mp[{i, j, xx, yy}] = true;
}
}
if (!res) cout << 2 << '\n';
else cout << 1 << ' ' << res << '\n';
return 0;
}
F. Puzzle
题意
给你两个
2
×
m
2\times m
2×m个
0
/
1
0/1
0/1矩阵
a
,
b
a,b
a,b，每次操作可以交换连个相邻位置的元素，问你至少操作多少次可以将
b
b
b变成
a
a
a
思路
? 我们将二维数组
[
0
,
1
]
给
a
,
[
2
,
3
]
给
b
[0,1]给a,[2,3]给b
[0,1]给a,[2,3]给b，从前往后考虑假设我们到了第
i
i
i列且前
i
?
1
i-1
i?1列都用最优的方法弄得一样了，
c
n
t
[
j
]
cnt[j]
cnt[j]：第
j
j
j行弄完前
i
i
i列剩下的
1
1
1
? 首先我们要将前
i
?
1
i-1
i?1列剩的
1
1
1都挪过来，即我们的操作数
r
e
s
res
res要加上
c
n
t
[
0
～
3
]
cnt[0\sim 3]
cnt[0～3]，然后我们开始消除一样的即第
i
i
i列的
[
0
,
1
]
[0,1]
[0,1]和
[
2
,
3
]
[2,3]
[2,3]是否一样，如果有
1
1
1我们优先在这一列消除掉，其次我们再看是否可以在这一列通过移动消除
1
1
1，由于移动只会操作一次，如果不在这一列消除掉后边这个多的
1
1
1一定会后移因此能消就消，即
(
0
,
3
)
,
(
1
,
2
)
(0,3),(1,2)
(0,3),(1,2)是否均有
1
1
1有的话就消除并且我们的
r
e
s
res
res要加上操作数，这样从前往后遍历完，如果
c
n
t
[
0
～
3
]
cnt[0\sim 3]
cnt[0～3]均为零就是我们的最优解，否则无解
? 由于每一步都是最优的因此最优性肯定成立，对于从左往右做或从右往左做是一样的，证明如下：
? 对于任意一列的一对
(
0
,
2
)
(0,2)
(0,2)或
(
1
,
3
)
(1,3)
(1,3)，有以下集中情况：
- 本身就一样，则在操作当前列的时候就消除掉了，因此左右做无所谓
- 本身不一样，假设
(
0
,
2
)
(0,2)
(0,2)这一对的值为
(
1
,
0
)
(1,0)
(1,0)，则从左往右做有以下集中情况
- 第
2
2
2行从前面
k
k
k这个位置过来了个
1
1
1因此在当前位置抵消了，由于抵消了因此后续往右走不会用到这个
1
1
1，我们从右往左做的时候这一列
0
0
0行这个
1
1
1会向左走到
k
k
k，由于它们之间的相对位置不变因此
1
1
1的操作贡献不变
- 第
0
0
0行这个
1
1
1往后移动到
k
k
k并且和那的第
2
2
2行的
1
1
1抵消了，由于抵消了后面不会用到
k
k
k这
1
1
1，因此我们从做往右走左做的时候
k
k
k这个位置的
1
1
1会移到讨论的中一列的第
2
2
2行并和
0
0
0行的
1
1
1抵消，由于相对位置不变，因此贡献不变
综上左右做是一样的
Code
#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> m;
vector<vector<int>> a(4, vector<int>(m));
for (int i = 0; i < 4; i ++)
for (int j = 0; j < m; j ++)
cin >> a[i][j];
vector<int> cnt(4);
LL res = 0;
for (int j = 0; j < m; j ++) {
for (int i = 0; i < 4; i ++) {
res += cnt[i];
if (a[i][j]) cnt[i] ++;
}
for (int i = 0; i < 2; i ++)
if (cnt[i] && cnt[i + 2])
cnt[i] --, cnt[i + 2] --;
for (int i = 0; i < 2; i ++)
if (cnt[i] && cnt[3 - i])
res ++, cnt[i] --, cnt[3 - i] --;
}
for (int i = 0; i < 4; i ++)
if (cnt[i])
return cout << -1 << '\n', 0;
cout << res << '\n';
return 0;
}
|