比赛链接

Codeforces Round #682 (Div. 2)

总结范围

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$便于反悔。

个人代码

Pastebin链接

个人代码

#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。

题解分析

参考自“哈哈哈哈哈哈”在知乎上的题解。

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

$x \oplus x \oplus y = 0 \oplus y = y$
即两个相同的数与另一个不同数三者异或，答案为不同的数。加上本题的要求，则三者均会变成相同的数$y$。

对三($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$的个数为偶数个：我们任选一个数$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$时，才能满足题意。
$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$，才能满足题意。

题解代码

Pastebin链接

题解代码

#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]的个数：

$l+1\leq r-1$，即子数组长度至少为$3$。
$(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}$

题解分析

参考自“哈哈哈哈哈哈”在知乎上的题解。

异或的基本性质的补充：

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

$0 \oplus 0 = 0$

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

如：$(3){10} \oplus (6){10} = (011)2\oplus (110)2 = (101)2 = (5){10}$，位数不可能超过最高位即$3$。
最大情况为：$(3){10}\oplus (4){10} = (011)_2\oplus (100)_2 = (111)2 = (7){10}$

但异或后的数值不能保证与两原数大小的直接关系，但由于数位可以保证，
令两数分别为$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(2n\log a_i)$。

题解代码

Pastebin链接

题解代码

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

来自于“哈哈哈哈哈哈”在知乎上的题解。