Codeforces Round #791 (Div. 2)解题报告(Codeforces round #791 (Div. 2) problem solving Report)

A. AvtoBus

题意:有两种车,一种车4轮,另一种6轮,给你轮子的数量,猜出能恰好组成的车辆数量的最大和最小,如果凑不出就输出-1
分析: 显而易见奇数个轮子肯定不恰好能凑成若干车辆,再考虑偶数情况,将6看作两个2加一个2,4看作两个2,那么所有大于4的偶数都可以看作是若干个2组成的,那么所有的偶数都可以由4和6组成
故输出-1的条件为x < 4 || x & 1,最大的计算:肯定能组成的话,先尽量组成4轮的,如果有剩余,肯定剩2,随便找一个4轮的安成6轮的,所以maxv = x / 4,最小的计算:先尽量组成6轮的,如果有剩余那么剩下的不是2就是4,拉出一辆6轮的组成俩4轮或一4一6,车辆数 + 1,所以minv = x / 6 + (x % 6 != 0);
ac 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
set<int> r;
set<int> co;

int main()
{
	ios;
	int t;
	cin >> t;
	while(t --)
	{
		LL x;
		cin >> x;
		if(x < 4 || x & 1) cout << -1 << endl;
		else 
		{
			LL maxv = x / 4, minv = x / 6 + (x % 6 != 0);
			cout << minv << " " << maxv << endl;
		}
	}
	return 0;
}

B. Stone Age Problem

题意:给你一个数组,定义以下两个操作:
1.令a[pos] = x;
2.令所有数变成x
每次操作都要输出当前数组的总和
分析:模拟
ac代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 2000010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,k;
int a[N];
string s,p;
LL sum = 0,last = 0;
bool flag = false,st[N];
int main()
{
	ios;
	cin >> n >> k;
	
	for(int i = 1;i <= n;i ++) cin >> a[i],sum += a[i];

	while(k --)
	{
		int t,pos,x;
		cin >> t;
		if(t == 1)
		{
			cin >> pos >> x;
			if(!flag)
			{
				sum -= a[pos];
				a[pos] = x;
				sum +=  a[pos];
			}
			else
			{
				if(!st[pos])
				{
					sum -= last - x;
					a[pos] = x;
					st[pos] = true;
				}
				else 
				{
					sum -= a[pos] - x;
					a[pos] = x;
				}
				

			}
			cout << sum << endl;

		}
		else
		{
			flag = true;
			memset(st,0,sizeof(bool) * (n + 4));
			cin >> x;
			sum = 1LL * x * n;
			last = x;
			cout << sum << endl;
		}
	}
	return 0;
}

C. Rooks Defenders

题意:给定一个\(n * n\) 的棋盘,定义以下三个操作:
1.在(x,y)处放一个棋子
2.在(x,y)处取走棋子
3.问 以\((x_1,y_1)\)为左上角\((x_2,y_2)\)为右下角的区域是否每个格子都被攻击
攻击条件:一个格子所在行或所在列有棋子就被攻击
在进行操作3后,需回答
分析:维护空行和空列两个有序集合,

version 1

采用二叉搜索树来维护,每次询问对有序行集合进行查找大于x1的最小元素,对有序列集合进行查找大于y1的最小元素,如果行大于x2,或列大于y2,说明整个区域都被攻击,
ac代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
set<int> r;
set<int> co;
int main()
{
	ios;
	cin >> n >> k;
	for(int i = 1;i <= n;i ++) co.insert(i),r.insert(i);

	while(k --)
	{
		int t,a,b,c,d;
		cin >> t;
		if(t == 1)
		{
			cin >> a >> b;
			row[a] ++,col[b] ++;
			
			if(row[a] == 1) r.erase(a);
			if(col[b] == 1) co.erase(b);
		}
		else if(t == 2)
		{
			cin >> a >> b;
			row[a] -- , col[b] --;
			if(!row[a]) r.insert(a);
			if(!col[b]) co.insert(b);
		}
		else
		{
			cin >> a >> b >> c >> d;
			set<int>::iterator A = r.lower_bound(a),B = co.lower_bound(b);
			if(A == r.end() || B == co.end()) cout << "YES" << endl;
			else if(* A > c || * B > d) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
	}
	return 0;
}

version 2

用两个树状数组维护行与列的空行
ac代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
int tr1[N],tr2[N];

int lowbit(int x)
{
	return x & -x;
}

void add(int tr[],int x,int v)
{
	for(int i = x;i < N;i += lowbit(i)) tr[i] += v;
}

int query(int tr[],int x)
{
	int res = 0;
	for(int i = x;i;i -= lowbit(i)) res += tr[i];
	return res;
}

int main()
{
	ios;
	cin >> n >> k;
	while(k --)
	{
		int t,a,b,c,d;
		cin >> t;
		if(t == 1) 
		{
			cin >> a >> b;
			row[a] ++, col[b] ++;
			if(row[a] == 1) add(tr1,a,1);
			if(col[b] == 1) add(tr2,b,1);
		}
		else if(t == 2)
		{
			cin >> a >> b;
			row[a] --,col[b] --;
			if(row[a] == 0) add(tr1,a,-1);
			if(col[b] == 0) add(tr2,b,-1);
		}
		else
		{	
			cin >> a >> b >> c >> d;
			x = query(tr1,c) - query(tr1,a - 1);
			y = query(tr2,d) - query(tr2,b - 1);
			if(x >= c - a + 1 || y >= d - b + 1) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
	}
	return 0;
}
————————

A. AvtoBus

There are two kinds of cars, one with four wheels and the other with six wheels. Give you the number of wheels and guess the maximum and minimum number of vehicles that can be exactly composed. If you can’t figure it out, output – 1
Analysis: it is obvious that the odd number of wheels can’t exactly make up several vehicles. Considering the even number, take 6 as two 2 plus one 2, and 4 as two 2, then all even numbers greater than 4 can be regarded as composed of several 2, and all even numbers can be composed of 4 and 6
Therefore, the condition of output – 1 is X & lt; 4 || x & 1. Maximum calculation: if it can be formed, try to form 4 wheels first. If there is a surplus, there must be 2 left. Arbitrarily find a 4-wheel into a 6-wheel, so maxv = x / 4. Minimum calculation: try to form 6 wheels first. If there is a surplus, then the rest is either 2 or 4. Pull out a 6-wheel into two 4 wheels or a 4-6, and the number of vehicles + 1, so minv = x / 6 + (x% 6! = 0);
AC code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
set<int> r;
set<int> co;

int main()
{
	ios;
	int t;
	cin >> t;
	while(t --)
	{
		LL x;
		cin >> x;
		if(x < 4 || x & 1) cout << -1 << endl;
		else 
		{
			LL maxv = x / 4, minv = x / 6 + (x % 6 != 0);
			cout << minv << " " << maxv << endl;
		}
	}
	return 0;
}

B. Stone Age Problem

Give you an array to define the following two operations:
1. Make a [POS] = x;
2. Make all numbers X
Each operation outputs the sum of the current array
Analysis: simulation
AC code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 2000010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,k;
int a[N];
string s,p;
LL sum = 0,last = 0;
bool flag = false,st[N];
int main()
{
	ios;
	cin >> n >> k;
	
	for(int i = 1;i <= n;i ++) cin >> a[i],sum += a[i];

	while(k --)
	{
		int t,pos,x;
		cin >> t;
		if(t == 1)
		{
			cin >> pos >> x;
			if(!flag)
			{
				sum -= a[pos];
				a[pos] = x;
				sum +=  a[pos];
			}
			else
			{
				if(!st[pos])
				{
					sum -= last - x;
					a[pos] = x;
					st[pos] = true;
				}
				else 
				{
					sum -= a[pos] - x;
					a[pos] = x;
				}
				

			}
			cout << sum << endl;

		}
		else
		{
			flag = true;
			memset(st,0,sizeof(bool) * (n + 4));
			cin >> x;
			sum = 1LL * x * n;
			last = x;
			cout << sum << endl;
		}
	}
	return 0;
}

C. Rooks Defenders

Meaning: given a \ (n * n \) chessboard, define the following three operations:
1. Place a piece at (x, y)
2. Remove the chess pieces at (x, y)
3. Ask whether each grid in the area with \ ((x_1, y_1) \) as the upper left corner and \ ((x_2, y_2) \) as the lower right corner is attacked
Attack condition: if there are pieces in the row or column of a grid, it will be attacked
After operation 3, answer
Analysis: maintain two ordered sets of empty rows and empty columns,

version 1

The binary search tree is used to maintain. Each query finds the smallest element greater than X1 for the ordered row set, and the smallest element greater than Y1 for the sequential set. If the row is greater than x2 or the column is greater than Y2, the whole region is attacked,
AC code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
set<int> r;
set<int> co;
int main()
{
	ios;
	cin >> n >> k;
	for(int i = 1;i <= n;i ++) co.insert(i),r.insert(i);

	while(k --)
	{
		int t,a,b,c,d;
		cin >> t;
		if(t == 1)
		{
			cin >> a >> b;
			row[a] ++,col[b] ++;
			
			if(row[a] == 1) r.erase(a);
			if(col[b] == 1) co.erase(b);
		}
		else if(t == 2)
		{
			cin >> a >> b;
			row[a] -- , col[b] --;
			if(!row[a]) r.insert(a);
			if(!col[b]) co.insert(b);
		}
		else
		{
			cin >> a >> b >> c >> d;
			set<int>::iterator A = r.lower_bound(a),B = co.lower_bound(b);
			if(A == r.end() || B == co.end()) cout << "YES" << endl;
			else if(* A > c || * B > d) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
	}
	return 0;
}

version 2

Maintain empty rows of rows and columns with two tree arrays
AC code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
int tr1[N],tr2[N];

int lowbit(int x)
{
	return x & -x;
}

void add(int tr[],int x,int v)
{
	for(int i = x;i < N;i += lowbit(i)) tr[i] += v;
}

int query(int tr[],int x)
{
	int res = 0;
	for(int i = x;i;i -= lowbit(i)) res += tr[i];
	return res;
}

int main()
{
	ios;
	cin >> n >> k;
	while(k --)
	{
		int t,a,b,c,d;
		cin >> t;
		if(t == 1) 
		{
			cin >> a >> b;
			row[a] ++, col[b] ++;
			if(row[a] == 1) add(tr1,a,1);
			if(col[b] == 1) add(tr2,b,1);
		}
		else if(t == 2)
		{
			cin >> a >> b;
			row[a] --,col[b] --;
			if(row[a] == 0) add(tr1,a,-1);
			if(col[b] == 0) add(tr2,b,-1);
		}
		else
		{	
			cin >> a >> b >> c >> d;
			x = query(tr1,c) - query(tr1,a - 1);
			y = query(tr2,d) - query(tr2,b - 1);
			if(x >= c - a + 1 || y >= d - b + 1) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
	}
	return 0;
}