当前位置:   article > 正文

Codeforces Round #742 Div.2 (A~E)题解_codeforces round #743 (div. 2)

codeforces round #743 (div. 2)

比赛链接:点击这里传送

官方题解链接:点击这里传送


Codeforces 1567A 题目链接:点击这里传送

在这里插入图片描述
题意:
给出n个1 × \times × 2大小的多米诺骨牌组成2 × \times ×n的矩形。现输入第一行的多米诺骨牌的方向,根据上图的格式输出排列方法。
思路:
上下左右四个方向都取其对立面输出就行。

#include<bits/stdc++.h>
using namespace std;
int t, n;
string s;
string ans;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--)
	{
		ans = "";
		cin >> n;
		cin >> s;
		int i = 0;
		while (i < s.length())
		{
			if (s[i] == 'L')
			{
				ans += 'L';
			}
			else if (s[i] == 'R')
			{
				ans += 'R';
			}
			else if (s[i] == 'D')
			{
				ans += 'U';
			}
			else if (s[i] == 'U')
			{
				ans += 'D';
			}
			i++;
		}
		cout << ans << 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
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

Codeforces 1567B 题目链接:点击这里传送

在这里插入图片描述
题意:
给出两个数a和b,要求你构造出一个数组并使其长度尽可能短,使得这个数组的最小未出现过的数字为a,数组中所有元素的异或为b。输出这个数组的长度。
思路:
先把MEX构造出来,然后求出这些数的异或和。打个表列出规律可得

  • 偶数%4=0 为本身
  • 偶数%4!=0 本身+1
  • 奇数%4=3 0
  • 奇数%4=1 1

设这个异或和为temp,当temp ⨁ \bigoplus b=b时,只需要n个数;当temp ⨁ \bigoplus a=b时,需要n+2个数,其他情况需要n+1个数。(找一x使得temp ⨁ \bigoplus x=b,x可以为除a外的任意数)


```cpp
#include<bits/stdc++.h>
using namespace std;
int t, n, a, b;
//偶数%4==0 为本身
//偶数%4!=0 本身+1
//奇数%4==3 0
//奇数%4==1 1
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> a >> b;
		//1 1 temp^x=b temp^b=x 当且仅当x=a时,不成立,需要再加一个数
		n = a;//为了满足MEX
		a--;
		int temp = 0;	
		if (a % 4 == 0) temp = a;
		if (a % 4 == 2) temp = a + 1;
		if (a % 4 == 1) temp = 1;
		if (a % 4 == 3) temp = 0;
		if (temp == b) cout << n << endl;
		else if ((temp^b)!=n) cout << n + 1 << endl;
		else cout << n + 2 << 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
  • 29
  • 30
  • 31

Codeforces 1567C 题目链接:点击这里传送

在这里插入图片描述
题意:
Alice学加法的时候进位不是进大一位的,而是进大两位的。现在给出一个数,其由两个正数a和b通过Alice的加法得到,现在问a和b有几种取法。
思路:
分析题意可得,奇数位进奇数位,偶数位进偶数位。把奇数位的数字和偶数位的数分别提出来组成两个数。此时只需要找出有多少种方法组成x,有多少种方法组成y,然后将他们相乘。显而易见是(x+1) × \times ×(y+1)。这个答案还得减去2,因为题意要求为正数,有两种情况会使两个数中的某一个数奇偶位全为0.
例如12345这个数,奇数提出来为135,偶数提出来为24.135=90+45,24=15+9
1 9 5 0 和 4 9 5 加起来就是12345
上面看懂了0的两种特例应该也能很好理解。

#include<bits/stdc++.h>
using namespace std;
int t;
string s;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> s;
		string even; string odd;
		for (int i = 0; i < s.length(); i++)
		{
			if (i % 2) even += s[i];
			else odd += s[i];
		}
		long long a; 
		if (even.size() == 0) a = 0;
		else a = stol(even);
		long long b = stol(odd); 
		cout << (a + 1) * (b + 1) - 2 << 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

Codeforces 1567D 题目链接:点击这里传送

在这里插入图片描述
题意:
给出一个数,要求你将其分成n个数,然后将这n个数看做十一进制求和。求出最后这个和的最大值(十进制)
思路:
不知道这题是怎么放到D题的,应该是测试数据不够?思路也很简单,最大的数让其位数尽可能大(1开头),次大的也尽可能大。当然要保证后面的数得大于0。就这样一直到最后一个数。

#include<bits/stdc++.h>
using namespace std;
int t, n, m;
int get_length(int x)
{
	return to_string(x).size();
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		for (int i = 1; i < m; i++)
		{
			int j = pow(10, (int)log10(n - (m - i)));
			n = n - j;
			cout << j <<" ";
		}
		cout << n << 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

Codeforces 1567E 题目链接:点击这里传送

在这里插入图片描述
题意:
给出n个数,有两个操作。一:改变某个元素的值 二:求某个区间非递减序列的个数(单个元素也算)
思路:
线段树+区间修改。好好复习 (预习)一下这个知识点
先给出本人线段树的码风

struct segtreenode
{
	int l, r,len;
	long long sum, lm, rm;//连续递增区间的个数,左子树递增区间长度最大值,右子树递增区间长度最大值
}tree[MAXN<<2];
  • 1
  • 2
  • 3
  • 4
  • 5

我们将某个区间分为左区间和右区间。先不考虑区间合并的情况,一个区间的递增区间个数等于左右两边加起来,一个区间左边递增区间长度最大值等于左子树的最大值,右边递增区间长度最大值等于右子树的最大值,就有了如下代码。

	tree[rt].lm = tree[rt << 1].lm; tree[rt].rm = tree[rt << 1 | 1].rm;
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
  • 1
  • 2

现在考虑区间合并的情况。如果左边一整个区间都是递增区间,那么lm就可以加上右子树的lm;如果右边一整个区间都是递增区间,那么rm就可以加上左子树的rm。sum就会中间多出来一部分。
a + b + c + d + e + . . . + i , j , k , l ∣ 分 割 线 ∣ m , o ⏟ n + m + . . . + u + w + x + y + z ⏞ \overbrace{a+b+c+d+e+...+\underbrace{i,j,k,l|分割线|m,o}_{n+m}+...+u+w+x+y+z}^{} a+b+c+d+e+...+n+m i,j,k,l线m,o+...+u+w+x+y+z
设左区间的rm为n,右区间的lm为m,多出来的总数就为m*n。
综上,完成了区间合并也就是pushup的处理

void pushup(int rt)
{
	tree[rt].lm = tree[rt << 1].lm; tree[rt].rm = tree[rt << 1 | 1].rm;
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
	if (a[tree[rt << 1].r] <= a[tree[rt << 1 | 1].l])//左右区间可以合并
	{
		if (tree[rt << 1].lm == tree[rt << 1].len)//如果左区间都是递增区间
		{
			tree[rt ].lm += tree[rt << 1 | 1].lm;
		}
		if (tree[rt << 1 | 1].rm == tree[rt << 1 | 1].len)//如果右区间都是递增区间
		{
			tree[rt ].rm += tree[rt << 1].rm;
		}
		tree[rt].sum += tree[rt << 1].rm * tree[rt << 1 | 1].lm;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

由于查询时不一定是整个区间,所以查询里面重新加了一段区间合并的代码。需要注意的是区间查询不是一整个区间时,得写两行代码划好左区间rm的上限和右区间lm的上限。

	long long lsum = min(tree[rt << 1].rm,mid-l+1);
	long long rsum = min(tree[rt << 1 | 1].lm,(r-(mid+1)+1));
  • 1
  • 2

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
int a[MAXN];
int n, m;
struct segtreenode
{
	int l, r,len;
	long long sum, lm, rm;//连续递增区间的个数,左子树递增区间长度最大值,右子树递增区间长度最大值
}tree[MAXN<<2];
void pushup(int rt)
{
	tree[rt].lm = tree[rt << 1].lm; tree[rt].rm = tree[rt << 1 | 1].rm;
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
	if (a[tree[rt << 1].r] <= a[tree[rt << 1 | 1].l])//左右区间可以合并
	{
		if (tree[rt << 1].lm == tree[rt << 1].len)//如果左区间都是递增区间
		{
			tree[rt ].lm += tree[rt << 1 | 1].lm;
		}
		if (tree[rt << 1 | 1].rm == tree[rt << 1 | 1].len)//如果右区间都是递增区间
		{
			tree[rt ].rm += tree[rt << 1].rm;
		}
		tree[rt].sum += tree[rt << 1].rm * tree[rt << 1 | 1].lm;
	}
}
void build(int rt, int l, int r)
{
	tree[rt].l = l; tree[rt].r = r; tree[rt].len = r - l + 1;
	if (l == r)
	{
		tree[rt].lm = 1;
		tree[rt].rm = 1;
		tree[rt].sum = 1;
		return;
	}
	int mid = (l + r) / 2;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	pushup(rt);
}
void update(int rt, int k, int x)//将下标为k的值修改为x
{
	if (tree[rt].l > k || tree[rt].r < k) return;
	if (tree[rt].l == tree[rt].r)
	{
		a[k] = x;
		return;
	}
	
	
	update(rt << 1, k, x);
	update(rt << 1 | 1, k, x);
	pushup(rt);
}
long long query(int rt, int l, int r)
{
	if (tree[rt].l > r || tree[rt].r < l) return 0;
	if (tree[rt].l >= l && tree[rt].r <= r) return tree[rt].sum;
	long long ans = 0;
	long long mid = (tree[rt].l + tree[rt].r) / 2;
	if (mid >= l) ans += query(rt << 1, l, r);
	if (mid < r) ans += query(rt << 1 | 1, l, r);
	if (a[tree[rt << 1].r] <= a[tree[rt << 1 | 1].l])//如果可以合并
	{
		long long lsum = min(tree[rt << 1].rm,mid-l+1);
		long long rsum = min(tree[rt << 1 | 1].lm,(r-(mid+1)+1));
		if (lsum > 0 && rsum > 0)
		{
			ans += lsum * rsum;
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	int f;
	while (m--)
	{
		cin >> f;
		if (f == 1)//修改
		{
			int k, x;
			cin >> k >> x;
			update(1, k, x);
		}
		else//查询
		{
			int x, y;
			cin >> x >> y;
			cout << query(1, x, y)<<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
  • 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
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/1003935
推荐阅读
相关标签
  

闽ICP备14008679号