Codeforces Round #802 (Div. 2)

[Link](Dashboard - Codeforces Round #802 (Div. 2) - Codeforces)

A. Optimal Path

The question

​ To give you one $(n,m)$ Matrix , The first $(i,j)$ The number of positions is $(i-1)\times m+j$, Ask you to go from the upper left corner to the lower right corner , You can only go right or left at a time , What is the minimum value of the sum of path numbers .

Ideas

• greedy

​ It's equivalent to every time $i+1$ or $j+1$, obviously $i$ This one's right is $m$ So first add $j$ better , Only when you can't do it can you add $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

The question

​ To give you one $n$ The number of positions $a$, Let you construct a without leading zeros $n$ Digit number $b$, And makes $a+b$ Is a palindrome number

Ideas

• violence

hypothesis $a+b=c$, So let's just find a palindrome number $c$, Give Way $c-a=b$, If $a$ The first place is not $9$, We can use $999...9$ To construct the , If it is $9$ because $b$ There can't be leading zeros , So choose $11111$ That's fine

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

The question

​ Give you a bit of length $n$ Array of $a$, Each operation can ：1. Select a prefix and subtract one 2. Choose a suffix minus one 3. Add one to the whole , Ask how many times you can make $a$ The array is $0$.

Ideas

• Difference , greedy

​ The interval problem wants to be different , set up $d$ by $a$ The difference fraction group of is $d_i=a_i-a_{i-1}$, Then our three operations are translated into $b$ Array 1. Subtract one from the first position and add one to the next position 2. Subtract one from a position 3. Add one to the first position , The goal is to transform $d$ Make the array all zeros

​ From $2$ Look at the first position if $i$ A place is $>0$ We can use operation two directly , If it is less than zero, we use the operation to affect the $1$ A place , Finally, use operation 3 to fix the first position

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

The question

​ Here you are. $n$ Put this bucket in a row , The first $i$ Each bucket has a capacity of $a_i$, You can pick any bucket and stick a pipe to start running down , Every second $1$ Of water , If the first $i$ When the bucket is full, the extra water will be given to the third party without delay $i+1$ Bucket water , Until the last bucket of water flows to the sea , Here you are. $q$ A asked , Give you one time at a time $t$, How many water pipes can you open at least $t$ Seconds later, all the barrels are full , If there is no solution output $-1$

Ideas

• greedy

​ First, we consider the case of no solution , set up $s$ by $a$ And , For the first $i$ A barrel we need in the worst case $t_i$ Time to fill it up , The former $i$ Every barrel has a water pipe and is in front of it $i-1$ A barrel flows into the $i$ A bucket of water plus its own water needs $\ge a_i$, That is to say $(t_i\times (i-1)-s_{i-1}+t_i\ge s_i-s_{i-1})$$\to t_i$$\times i\ge s_i\to t_i\ge \lceil \frac{s_i}{i}\rceil$, So we just need to count $\lceil \frac{s_i}{i}\rceil$ The maximum of $mx$ We can judge whether there is no solution

​ If $mx\ge t$ There must be a solution , Otherwise, I have no idea , From time to time, we record a front in $t$ How much can flow in time $v$, If $v\ge a_i$ Then there is no need for boiling water pipe at this position , Otherwise, you must , This greed is the best , But the complexity is too high

​ Continue to think about if for $i$ He had to open a pipe , At this time, we can drive the pipe to a certain position in the front , That's right $i$ It's the same thing . Before hypothesis $i-1$ Have been established and opened $k$ The second tube is for the $i$ For one thing $a_i-(t\times k-s_{i-1})$ Is it greater than $0$ It is to judge whether a pipe needs to be opened at present , Judgment $s_i-t\times k$ whether $0$, If it is less than zero, it can not be opened , Otherwise, you must open one , So we're going to let $i\in [1,n]$ All meet $s_i-t\times k\le 0$, That is, how many tubes can we open continuously from the first position to put all barrels in $t$ Fill up in seconds , namely $\lceil \frac{s_i}{t}\rceil$

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

The question

​ To give you one $n\times m$ Matrix , All the elements in the matrix belong to $[1,n\times m]$ And they are different , Every time you go from $1$ Start walking , You can only walk where you have walked , Or greater than the maximum you've ever walked $+1$ The location of , One operation can exchange the numbers of two positions at will , Ask if you can be in $0,1,\ge 2$ This matrix is completed in one operation ,$0$ Second operation output $0$,$\ge 2$ Second operation output $2$,$1$ How many different operation methods are there for each operation output .

Ideas

• thinking , violence

​ Our topic is equivalent to having an irregular circle , One point at a time , But it is hard to think of such a simulation

​ So let's change the angle , Consider each element , about $(i,j)$ The element of this position $k$ When will he have a solution , That is, there is a solution when the value of one position above, below, left and right is smaller than him , Note that the solution here means $[1,k-1]$ All the solutions have been solved $k$ When , If $[1,k-1]$ Don't even mention it $k$ 了 , because $[1,k-1]$ All of them are in a circle, so they must be able to move to $(i,j)$ Around this position smaller than him , So he must have a solution .

​ So we can count how many blocks have no solutions , Assuming that $bad$ There is no solution . We can swap two blocks at most $10$ In the case of two blocks, that is, the upper, lower, left and right of two blocks and the two blocks themselves , So if $bad>10$ Then you must $\ge 2$ operations , If $bad==0$ Then we can do $0$, about $1$ We can judge the operation violently , For a bad block, we can swap around it or swap it , Because a bad block must be fixed before it can be solved , So we enumerate the five positions of the first block to replace the entire matrix of violence , Every time we judge whether there are no bad blocks after changing, we can judge whether there is a solution at present , If we don't have a set of solutions after the final operation, it means that $\ge 2$ operations

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

The question

Here are two for you $2\times m$ individual $0/1$ matrix $a,b$, Each operation can exchange elements of adjacent positions , Ask how many times you can operate at least $b$ become $a$

Ideas

• greedy

​ We'll use a two-dimensional array $[0,1]toa,[2,3]tob$, From the past to the future, suppose we arrive at $i$ Column and front $i-1$ The columns are all the same in the best way ,$cnt[j]$： The first $j$ Before the line is finished $i$ List the rest $1$

​ First of all, we should put the former $i-1$ List the remaining $1$ Move over , Our operands $res$ To add $cnt[0\sim 3]$, Then we began to eliminate the same thing, namely $i$ Column $[0,1]$ and $[2,3]$ Whether or not the same , If there is $1$ Let's eliminate... In this column first , Next, let's see if we can move the column to eliminate $1$, Because the movement will only be operated once , If you don't eliminate the more in this column $1$ It must move back, so it can be eliminated , namely $(0,3),(1,2)$ Are there any $1$ If so, it will be eliminated and our $res$ To add operands , In this way, you can traverse from front to back , If $cnt[0\sim 3]$ Zero is our optimal solution , Otherwise, there is no solution

​ Since each step is optimal, the optimality must be established , It is the same to do from left to right or from right to left , Prove the following ：

​ For a pair of arbitrary Columns $(0,2)$ or $(1,3)$, There are the following centralized situations ：

1. It's the same , It is eliminated when the current column is operated , So it doesn't matter to do left or right
2. Itself is different , hypothesis $(0,2)$ The value of this pair is $(1,0)$, From left to right, there are the following centralized situations
   1. The first $2$ Line from the front $k$ Here comes a $1$ So in the current position it cancels out , Because of the offset, this will not be used in the subsequent right walk $1$, When we do it from right to left, this column $0$ All right $1$ Will go left to $k$, Because the relative position between them is unchanged, so $1$ The operational contribution of the does not change
   2. The first $0$ All right $1$ Move back to $k$ And with the first $2$ Yes $1$ Offset , Because of the offset, it will not be used later $k$ this $1$, So when we go from doing to right and left $k$ In this position $1$ Will move to the... Of the first column in the discussion $2$ Row merging and $0$ Yes $1$ offset , Since the relative position remains unchanged , So the contribution remains the same

To sum up, the left and right actions are the same

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;
}