补题 Codeforces Round #791 (Div. 2) A、B

补题

A题

思路
这题写的时候没想清楚，其实就是解4x + 6y = n
一开始没想清楚输出-1的情况，导致后面wa了一堆，还以为是题目问题
输出-1的情况就是n为奇数，或者n小于4的情况
若不输出-1，则最大是n/4辆，最小按理说是n/6辆，但是因为不能没有，所以\(（n + 4）/6\),保证在n==4的时候最少也有一辆车

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  
using namespace std;

typedef long long LL;
typedef pair PII;
const int N = 200010, M = 60, INF = 1e9; 
int a[N], b[N];
char g[M][M];

bool cmp(int a, int b)
{
	return a > b;
}

int check(char s)
{
	if(s >= 'a' && s <= 'z')
		return s - 'a' + 10;
	else return s - '0';
}

void solve()
{
	LL n;
	cin >> n;
	if(n & 1 || n < 4) puts("-1");
	else cout << (n + 4) / 6 << ' ' << n / 4 << endl;
}


int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	
	return 0;
}

B题

思路：只用输出和的结果，在最开始全加起来，然后进行加或者减就好了。
唯一困难的是当全部数字被替换之后怎么去给数组中所有元素换成x ，否则下次进行单个元素替换的时候就不对
解决方案就是用map或数组等 + last标识当前数组是否被全部替换，如果被全部替换，那么更新sum之前会将当前数更新成被整体替换的值

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#define int long long
using namespace std;

typedef long long LL;
typedef pair PII;
const int N = 200010, M = 60, INF = 1e9; 
int a[N], b[N];
char g[M][M];

bool cmp(int a, int b)
{
	return a > b;
}

int check(char s)
{
	if(s >= 'a' && s <= 'z')
		return s - 'a' + 10;
	else return s - '0';
}

void solve()  //核心代码
{
	int n, q;
	cin >> n >> q;
	map m;
	int last = 0, sum = 0;
	for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
	while(q--)
	{
		int tt, x, idx;
		cin >> tt;
		if(tt == 1)
		{
			cin >> idx >> x;
			if(!m[idx] && last)  //如果这个数没出现过且数组整体被更新过了
			{
				m[idx] = 1;
				a[idx] = last;
			}
			sum += x - a[idx];
			a[idx] = x;
		}
		else{
			cin >> x;
			sum = n * x;
			last = x;
                        m.clear();
		}
		cout << sum << endl;
	}
}


int main()
{
	int t;
	//cin >> t;
//	while(t--)
//	{
		solve();
//	}
	
	return 0;
}

相关

标签