主页
Featured image of post ACM比赛总结——Codeforces #682 (Div. 2)……

ACM比赛总结——Codeforces #682 (Div. 2)……

2020.11.13 —— Codeforces #682 (Div. 2)……

文章字数:5507
预计阅读时长: 分钟

比赛链接

总结范围

  • A
  • B
  • C
  • D
  • E
  • F

A. Specific Tastes of Andre

比赛状态:AC

题目大意

问题描述

定义一个“好数组”:该数组的元素和能被其长度整除。

例子:

$[2,3,1]$是“好数组”——其元素和$6$能被长度$3$整除。
$[1,1,2,3]$不是“好数组”——其元素和$7$不能被长度$4$整除。

读入格式

$T$组数据,每组读入一个长度$n$。

输出格式

输出任意一个长度为$n$的“好数组”。

分析

多试试就能知道$[1,1,1,…]$,
全1数组为好数组。

直接输出即可。

代码

代码
#include <bits/stdc++.h>
#define MAX 100
using namespace std;
int main()
{
	int T,n;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n;i++)
			printf("%d ", 1);
		printf("\n");
	}
}

B. Valerii Against Everyone

比赛状态:AC

题目大意

问题描述

原数组$b_{i}$,令数组$a$,其中$a_{i}=2^{b_{i}}$。
问:是否存在$l_{1},r_{1},l_{2},r_{2}$
满足:

  • $1 \le l_{1} \le r_{1} \le l_{2} \le r_{2} \le n$
  • $a_{l_{1}}+a_{l_{1}+1}+a_{l_{1}+2}+…+a_{r_{1}-1}+a_{r_{1}} = a_{l_{2}}+a_{l_{2}+1}+a_{l_{2}+2}+…+a_{r_{2}-1}+a_{r_{2}}$

即左侧某区间之和等于右侧某区间之和。

例子:

$b_{i}=[4,3,0,1,2,0]$
则$a$数组:$a_{i}=[16,8,1,2,4,1]$

当 $l_{1}=1, r_{1}=1, l_{2}=2, r_{2}=6$ 时:
$(16)=(8+1+2+4+1)$ 故满足题意,为YES。

读入格式

$T$组数据。

第一行一个$n$,代表数组长度;
第二行分别为$b_{i}$。

输出格式

如果存在,则输出“YES”,否则输出“NO”。

分析

因为为$2^i$的这种数,有个特性就是有两个相同的数,才能得到序列的另一个其他的数。

$1,2,4,8,16,32,…$
上面任意两个数相加都不可能得到该序列中的数【在倍增思想中可提现,如ST表。
任意几个数相加也不可能等于其他几个数相加之和。

【严格证明我也不会_(:з」∠)_……
个人把这个性质称为互斥性。

因此考虑:

  • $b_{i}$数组如果没有两个相同元素出现
    则会因为互斥性的影响,不可能满足条件,则为“NO”
  • $b_{i}$数组存在至少两个相同元素,假设为$b_{i},b_{j}$
    则至少满足条件$l_{1}=r_{1}=i, l_{2}=r_{2}=j$,使得$a_{l_{1}}=b_{l_{2}}$

综上分析:只需要考虑数组中是否存在至少两个相同元素即可。


因此实现方法便是:
排序,然后从$2$到$n$遍历,如果b[i]==b[i-1],满足题意输出“YES”,否则输出“NO”。

代码

代码
#include <bits/stdc++.h>
#define N_MAX 200000
using namespace std;
int main()
{
	int T, n, num[N_MAX + 5];
	scanf("%d", &T);
	while (T--)
	{
		int flag = 1;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			scanf("%d", &num[i]);
		sort(num + 1, num + n + 1);
		for (int i = 2; i <= n; i++)
			if (num[i] == num[i-1])
			{
				flag = 0, printf("YES\n");
				break;
			}
		if (flag)
			printf("NO\n");
	}
}

C. Engineer Artem

比赛状态:AC

题目大意

问题描述

一个矩阵,其每个单元能够通过加一或者不变的操作,
即$b_{i,j}=a_{i,j}$或者$b_{i,j}=a_{i,j}+1$,使得任意相邻两个元素不相等。

例子:

$\begin{matrix} 1 & 1 \\ 3 & 3 \end{matrix}$

可经过变换得到:
$\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}$

读入格式

$T$组数据。

第一行为行和列$n,m$,
接下来$n$行$m$列读入这个矩阵。

输出格式

输出经过变换后的这个矩阵。

个人分析

因为题上说明了答案必存在。
先想着bfs遍历每个单元,如果与周围单元值相同,就让那个单元格$+1$。
这里改变了那个单元格后,可能引起那个单元格又不满足条件,所以又要bfs回去。

类似于贪心的想法,每次确定当前单元格的周围符合条件。
但贪心就要考虑反悔:有可能这里变为不$+1$反而符合条件。
所以用个$vis[i][j]$表示是否被$+1$便于反悔。

个人代码

个人代码
#include <bits/stdc++.h>
#define N_MAX 105
using namespace std;
int val[N_MAX + 5][N_MAX + 5], vis[N_MAX + 5][N_MAX + 5], n, m;
void bfs(int i, int j)
{
	if (i != 1)						//越界限定
		if (val[i - 1][j] != -1)	//未被赋值限定
			if (val[i-1][j]==val[i][j])
			{
				if (!vis[i - 1][j])	//没被访问(+1)
					val[i - 1][j]++, vis[i - 1][j] = 1, bfs(i - 1, j);
				else	//被访问了,该-1
					val[i - 1][j]--, vis[i - 1][j] = 0, bfs(i - 1, j);
			}
	if (j != 1)
		if (val[i][j - 1] != -1)
			if (val[i][j-1]==val[i][j])
			{
				if (!vis[i][j - 1])
					val[i][j - 1]++, vis[i][j - 1] = 1, bfs(i, j - 1);
				else
					val[i][j - 1]--, vis[i][j - 1] = 0, bfs(i, j - 1);
			}
	if (i != n)
		if (val[i + 1][j] != -1)
			if (val[i+1][j]==val[i][j])
			{
				if (!vis[i + 1][j])
					val[i + 1][j]++, vis[i + 1][j] = 1, bfs(i + 1, j);
				else
					val[i + 1][j]--, vis[i + 1][j] = 0, bfs(i + 1, j);
			}
	if (j != m)
		if (val[i][j + 1] != -1)
			if (val[i][j+1]==val[i][j])
			{
				if (!vis[i][j + 1])
					val[i][j + 1]++, vis[i][j + 1] = 1, bfs(i, j + 1);
				else
					val[i][j + 1]--, vis[i][j + 1] = 0, bfs(i, j + 1);
			}
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		memset(val, -1, sizeof(val));
		memset(vis, 0, sizeof(vis));
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				scanf("%d", &val[i][j]);
				if (val[i][j] == val[i - 1][j] || val[i][j] == val[i + 1][j] || val[i][j] == val[i][j - 1] || val[i][j] == val[i][j + 1])
				{
					val[i][j]++, vis[i][j] = 1;
					bfs(i, j);
				}
			}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
				printf("%d ", val[i][j]);
			printf("\n");
		}
	}
}

题解分析

根据矩阵元素的奇偶性决定是否$+1$。

因为如果使矩阵满足如下结构,
则必定保证相邻两个元素奇偶性不同,两元素数也必然不同。 $$\begin{matrix} odd & even & odd & … \\ even & odd & even & … \\ odd & even & odd & … \\ … & … & … & … \end{matrix}$$

题解代码

题解代码
#include <bits/stdc++.h>
using namespace std;
int t, n, m, x;
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				cin >> x;
				if ((i + j + x) % 2)	//根据i,j(即元素位置)确定该是奇还是偶
					cout << x;
				else
					cout << x + 1;
				cout << (j == m - 1 ? '\n' : ' ');
			}
		}
	}
	return 0;
}

D. Powerful Ksenia

比赛状态:未完成(没有时间看题)

题目大意

问题描述

给定$n$个数,每次操作能选择其中三个数$x,y,z$皆变为它们的亦或$x \oplus y \oplus z$,问能否进行不超过$n$次操作使这$n$个数均相等。

读入格式

第一行读入一个$n$,接下来一行读入$n$个数。

输出格式

输出是否能满足条件:

  • 如果能,输出一行YES,并在下一行输出所需的操作数m,在下一行输出m个所分别选择的三个数x,y,z
  • 如果不能,直接输出一行NO

题解分析

首先了解位运算中“三者异或”的基本性质:

  1. $x \oplus x \oplus y = 0 \oplus y = y$
    两个相同的数与另一个不同数三者异或,答案为不同的数。加上本题的要求,则三者均会变成相同的数$y$。
  2. 对三($n$)者异或,转成二进制后,某一位的$1$的个数的奇偶性不变,如表格所示:
    (x,y,z) 1的个数奇偶性 结果 1个数的奇偶性
    (0,0,0) (0个) 0 (0个)
    (0,0,1) (1个) 1 (1个)
    (0,1,0) (1个) 1 (1个)
    (0,1,1) (2个) 0 (0个)
    (1,0,0) (1个) 1 (1个)
    (1,0,1) (2个) 0 (0个)
    (1,1,0) (2个) 0 (0个)
    (1,1,1) (3个) 1 (1个)

基于第一性质:如果我们能把数列分为$n$个$2$个相同的数$(x,x)$,最终加上任意一个数$y$,我们便能将该数列变为符合题意的均为$y$数列。
每经过一次操作后,我们都能得到三个相同的数;而下一次操作如果我们再用上一次操作中的任意一个数,上一次操作便能得到两个相同的数

  • 经过简化:若我们按照$(1,2,\underline3),(\underline3,4,\underline5),(\underline5,6,7),…$这样的顺序操作下去,最终便能得到$(x_1,x_1,x_2,x_2,x_3,x_3,…,x_{n-1},x_{n-1},x_n,x_n,x_n)$这样一个数列。再按照**第一性质**得到结果。
    而要能使用这一种操作,则须满足数列个数为$2*n+1$个,即为**奇数个**。

即:若数列个数为奇数个,则必定可以通过上述操作满足题意。


那分析数列个数为偶数个的情况:

对于最终态分析:
如果我们能满足题意,即变成个数为偶数个的相同元素$x$的数列
对$x$的每一个二进制数位($5_{(10)}$—>$101_{(2)}$)分析,其每一位$1$的个数必定全是$0$或者为偶数个$1$,即**所有数位$1$的个数均为偶数个**。

又因为第二性质——异或后某一数位的$1$的个数的奇偶性不变
对最初态数列的任意一数位假设:

如:

第三位: 0 1 0 1 1 0
第二位: 0 1 1 0 1 1
第一位: 1 1 0 0 0 0

(原数列:1 7 2 4 6 2)

令:该数列长度为$2n$。

  1. $1$的个数为偶数个: 我们任选一个数$x_i$,将这个数放在最后分析,先操作剩下的$2n-1$个数。
    可知这$2n-1$个数为奇数。
    而对于选中的$x_i$,又有两种情况:

    1. 该位为$0$:
      则剩下的$2n-1$个数,该为$1$的个数仍为偶数个,但数却有奇数个。
      要达到最后所有数相同的情况(即该位全是$1$或全是$0$),只能最终全部为$0$。
      因此$x_i$的该位与剩下的$2n-1$个数操作后的该位结果相同。
      又因为为任意一数位,故最终$x_i$这个数必须与剩下的$2n-1$个数操作后的数值相同
    2. 该位为$1$:
      则剩下的$2n-1$个数,该为$1$的个数变为奇数个,而数也有奇数个。
      同理,则最终全部为$1$,也相同

    又因为$x_i$也为任选。
    任意一数$x_i$,其剩下的$2n-1$个数经过异或操作后变为相同数$m$,只有$x_i=m$时,才能满足题意。

  2. $1$的个数为奇数个——不成立:
    由第二性质可直接得出矛盾——最初态该数位的$1$的个数(奇数个)与最终态(偶数个)的奇偶性不一致。
    但同理分析,可以得出任意一数$x_i$,其剩下的$2n-1$个数经过异或操作后变为相同数$m$,必定$x_i \neq m$


综上:只有任意一数$x_i$,其剩下的$2n-1$个数经过异或操作后变为相同数$m$,只有$x_i=m$时,才能满足题意。

  • 经过简化:若我们仍然按照$(1,2,\underline3),(\underline3,4,\underline5),(\underline5,6,7),…$这样的顺序操作下去,
    最终得到$(x_1,x_1,x_2,x_2,x_3,x_3,…,x_{n-1},x_{n-1},x_n,x_n,x_n,y)$这样一个数列。

    按照奇数个数的操作对前$2n-1$个操作,得到相同值$m$。
    若$m=y$,则一定满足题意,否则一定不满足。

即:
若数列个数为偶数个,将前$2n-1$个变为相同数$m$,只有最后一个数$x_{2n}=m$,才能满足题意。

题解代码

题解代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

int n;
int a[maxn];

void op(int i,int j,int k)	//异或操作
{
    a[i] = a[j] = a[k] = a[i]^a[j]^a[k];
}

void out(int i,int j,int k)
{
    cout<<i<<' '<<j<<' '<<k<<endl;
}

int main()
{
    cin>>n;
    for(int i = 1;i <= n;++i) cin>>a[i];

    int m = (n%2 ? n : n-1); // 如果是偶数,操作前n-1个数
    for(int i = 4;i < m;i += 2) op(i-2,i-1,i); // 产生k对相同数
    op(m,m-1,1);
    for(int i = 4;i < m;i += 2) op(i-2,i-1,1); // 选定第一个为最终答案

    if(n%2==0 && a[n]!=a[1])
	{
		cout<<"NO";
    }
    else
	{
		cout<<"YES\n"<<m-2<<endl;
		for(int i = 4;i < m;i += 2) out(i-2,i-1,i);
		out(m,m-1,1);
		for(int i = 4;i < m;i += 2) out(i-2,i-1,1);
    }
    return 0;
}

E. Yurii Can Do Everything

比赛状态:未完成(没有时间看题)

题目大意

问题描述

给定一个数组a[n],要求输出满足以下条件的子数组a[l..r]的个数:

  1. $l+1\leq r-1$,即子数组长度至少为$3$。
  2. $(a_l \oplus a_r) = (a_{l+1}+a_{l+2}+…+a_{r-2}+a_{r-1})$,即两端点异或的值等于中间所有数之和。

读入格式

第一行为数组长度$n$,接下来一行为长度为$n$的数组$a_i$的读入。

输出格式

输出满足条件子数组个数。

数据范围

  • $3\leq n \leq 2*10^5$
  • $1\leq a_i \leq 2^{30}$

题解分析

异或的基本性质的补充:

  1. 任意两数异或,其结果不可能超过他们最大的二进制数位
    根据异或计算结果:

    $0 \oplus 0 = 0$

    最高位往后均为$0$,异或后结果也为0,因此结果的数位不可能超过最高位。

    如:$(3)_{10} \oplus (6)_{10} = (11)_2\oplus (110)_2 = (5)_{10}/(101)_2$,位数不可能超过最高位即$3$。
    最大情况为:$(3)_{10}\oplus (4)_{10} = (11)_2\oplus (100)_2 = (7)_{10}/(111)_2$

    但异或后的数值不能保证与两原数大小的直接关系,但由于数位可以保证,令两数分别为$x,y$,其二进制位数分别为$m,n$。
    可确定$x\oplus y<2^{max(m,n)}$。

    假设最大为$x=(31)_{10}$,$(x)_2=(11111)_2$,
    则$m=5$,$2^m=(32)_{10}=(100000)_2$


这题如果暴力搜索的话,$O(n^2)$TLE。
但由于以上的性质存在,可以跨级别性剪枝。

根据以上性质我们可以粗略感觉到一个剪枝条件:

当$\sum_{i=l+1}^{r-1}a_i\geq 2^{max(m,n)}$时,则证明该区间不满足条件。

但如果搭配暴力搜索,假如选定$l$遍历$r$,$max(m,n)$选择的值可能因为$r$的改变而改变,使得无法通过这个条件来中止后续搜索。

因此我们可以更暴力一点【?】,选定$l$后,我们就假定$max(m,n)$选择的值为$m$,即$l$的位数始终最大。然后向右遍历$r$。
这样当我们找到不满足条件的情况后,后续的搜索便可以中止

可能会问,如果这样选择的区间最大值却是$n$,是否会出现问题?
但如果最大值选的$n$,则一定满足情况$\sum_{i=l+1}^{r-1}a_i\leq 2^m \leq 2^n$,这个区间也符合条件,不会影响的抬走下一个x……

但这样的话,可能有区间就是以$n$,即右端点$r$为最大位数,但$2^m\leq \sum_{i=l+1}^{r-1}a_i\leq 2^n$。
因此我**们再从右向左,选定$r$,令$max(m,n)$选择的是$n$,向左遍历$l$便可解决这种问题**。

这样肯定能保证不漏,但很明显会重复计算
即若有区间满足$\sum_{i=l+1}^{r-1}a_i\leq 2^m \leq 2^n$或$\sum_{i=l+1}^{r-1}a_i\leq 2^n \leq 2^m$,则从左向右和从右向左均满足,会被计算两次。

用“Hash+<STL>set”可以去重计数


但为什么这样剪枝能跨级别性剪枝呢!?……

因为如果要遍历较长的$l\sim r$,则数列应构造为$1,2,4,8,…,2^n$【从右向左$r=n$时,就能让$l$取到最左即$l=1$而中间求和仍少于$2^n$。

这样反而限定了遍历范围为$log_2a_i$,则总复杂度为$O(2nloga_i)$。

题解代码

题解代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;

int n;
ll a[maxn];
set<ll> st;

ll get_max(ll x)
{
    for(ll i = 1LL<<31;i;i >>= 1){
	if(i & x)return i<<1;
    }
}

int main()
{
    cin>>n;
    for(int i = 0;i < n;++i)cin>>a[i];
    for(int l = 0;l < n-2;++l){
	ll s = a[l+1],maxs = get_max(a[l]);
	for(int r = l+2;r < n;++r){
	    if((a[l]^a[r]) == s)st.insert((ll)l*maxn+r);
	    if((s+=a[r]) > maxs)break;
	}
    }
    for(int r = n-1;r > 1;--r){
	ll s = a[r-1],maxs = get_max(a[r]);
	for(int l = r-2;l >= 0;--l){
	    if((a[l]^a[r]) == s)st.insert((ll)l*maxn+r);
	    if((s+=a[l]) > maxs)break;
	}
    }
    cout<<st.size();
    return 0;
}