526互联

ErikTse2023Codeforces思维提升赛（4）

发布时间 2023-11-01 20:17:28作者: TJUEZ

A

An array a consisting of k integers is strictly increasing if \(a_{1}<a_{2}<⋯<a_{k}\). For example, the arrays \([1,3,5], [1,2,3,4], [3,5,6]\) are strictly increasing; the arrays \([2,2], [3,7,5], [7,4,3], [1,2,2,3]\) are not.

For a strictly increasing array a of k elements, let's denote the characteristic as the number of different elements in the array \([a_{2}−a_{1},a_{3}−a_{2},…,a_{k}−a_{k−1}]\). For example, the characteristic of the array \([1,3,4,7,8]\) is \(3\) since the array $[2,1,3,1] $contains \(3\) different elements: \(2, 1\) and \(3\).

You are given two integers \(k\) and \(n (k≤n)\). Construct an increasing array of k integers from \(1\) to \(n\) with maximum possible characteristic.

Input

The first line contains one integer \(t (1≤t≤819)\) — the number of test cases.

Each test case consists of one line containing two integers \(k\) and \(n (2≤k≤n≤40)\).

Output

For each test case, print \(k\) integers — the elements of the strictly increasing array a with the maximum possible characteristic. If there are multiple answers, print any of them.

题意

给定序列的长度\(k\)以及序列中最大数\(n\)，要求通过使用1~n中的任意k个数，构造一个长度为\(k\)的单调递增序列，并使整个序列的特色程度最高。

特色程度指的是：\([a_{2}−a_{1},a_{3}−a_{2},…,a_{k}−a_{k−1}]\)中不同元素的个数。

例如\([1,2,4,7]\)，差分以后为\([1,2,3]\)，特色程度为3；\([1,2,3,4]\)，差分以后为\([1,1,1]\),特色程度为\(1\)。

题解

思路一

我们可以观察到，对于有多个解的情况，只是差分数组内部数字的顺序发生了改变，不同元素的个数还是一样的，我们不妨将差分数组形式化为\([1,2,3,4……t,1,1,1,1,1]\)的形式。其中前\(t\)个数成等差数列，\(t\)即为特色程度的值；后\(k-t\)个数是为了满足题目要求的凑够\(k\)个数且最大的数不超过\(n\)。

显然，对于初始元素是1的情况，整个差分数组的元素和应该小于等于\(n\)。

为什么初始元素是1？我们贪心地想，不从1开始的话就浪费了至少1个空间。

我们可以得到方程：\(1+2+...+t+k-t≤n\)

差分数组后面有若干个\(1\)，这个若干也可以是\(0\)，所以列的方程把\(1\)都放在后面是没有问题的。

化简并解方程：\((1+t)\times{t\div2}+k-t≤n\)

最终可以得到：\(t^{2}-t≤2\times(n-k)\)

据此，我们可以解出一个满足条件的最大的\(t\)，依照这个值来进行数列的构造即可造出一个符合题意的解。

前\(t\)个数依次按照差分数组递增，后\(k-t\)个数逐增即可。

但还要注意一个问题：\(t≤k?\) 比如\(n=4，k=1\)，此时\(t\)为 \(3\)，但是我们也不能输出\(t\)个数，这不符合题意。

所以我们还需要对\(t≤k?\)进行一次判断，如果\(t≥k\) 的话，输出\(k\)个数就行了。

思路二

先顺序设定一个变差数列a，长度为k，\([1,2,4,7,11,……]\)

在逆序设定一个等差数列b，最后一个数为n，差为1，长度为k,即\([n-k+1,n-k+2,……,n]\)

每一次都输出\(min(a[i],b[i]) (1<=i<=k)\)，

可以发现其实连数组都不需要开，用变量记录一下当前的两个值即可。

代码

#include <bits/stdc++.h>

using namespace std;

void solve(){
	
	int n,k;
	cin>>k>>n;
	int t=0;
	while(true){//循环求t
		if(t*t-t>2*n-2*k){
			t--;
			break;
		}
		t++;
		
	}
	//cout<<t<<endl;
	int now=1;int cnt=1;//cnt记录差分前t位的值
	for(int i=1;i<=min(k,t);i++){//进行k与t大小的判断
		cout<<now<<" ";
		now+=cnt;
		cnt++;
		
	}
	if(k<t)return ;//k<t就不用再输出了
	for(int i=1;i<=k-t;i++)
	{
		cout<<now<<" ";
		now++;//后k-t位差分的值都为1
	}
	cout<<endl;
}

int main(){
	
	int _;
	cin>>_;
	for(int i=1;i<=_;i++){
		
		solve();
	}
}

B BINARY INVERSIONS

You are given a binary array† of length \(n\). You are allowed to perform one operation on it at most once. In an operation, you can choose any element and flip it: turn a \(0\) into a \(1\) or vice-versa.

What is the maximum number of inversions‡ the array can have after performing at most one operation?

† A binary array is an array that contains only zeroes and ones.

‡ The number of inversions in an array is the number of pairs of indices i,j such that \(i<j\) and \(a_i>a_j\).

Input

The input consists of multiple test cases. The first line contains an integer \(t (1≤t≤10^4)\) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer \(n (1≤n≤2⋅10^5)\) — the length of the array.

The following line contains n space-separated positive integers \(a_1, a_2,..., a_n (0≤a_i≤1)\) — the elements of the array.

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2⋅10^5\).

Output

For each test case, output a single integer — the maximum number of inversions the array can have after performing at most one operation.

题意

给定一个二进制字符串，求其最大逆序对个数，求之前可以进行至多一次操作，即将某个\(0\)变成\(1\)或者将某个\(1\)变成\(0\)。

题解

显然，对于每一个\(1/0\)来说，它们对于总逆序对个数奉献取决于其后面的\(0\)的个数\(b\)以及前面的\(1\)的个数\(c\)，所以假设\(b_i\) \(c_i\)分别为第\(i\)个数的后面的\(0\)的个数以及前面的\(1\)的个数，由于最多只能改变一个数，所以遍历维护最大贡献值即可(不变也是有可能的)

对于\(1\),将它变为\(0\)的贡献为\(c_i-b_i\),对于\(1\),将它变为\(1\)的贡献为\(b_i-c_i\)

时间复杂度\(O(n)\)

可以观察得到，贡献最大的一定是最左边的0或者最右边的1，所以只有不变，变最左0和变最右1这三种选择。

代码

#include <bits/stdc++.h>

using namespace std;
const int N=2e5+10;
int a[N];
int b[N];
int c[N];
void solve(){
	int n;
	cin>>n;
	memset(c,0,sizeof c);
	memset(b,0,sizeof b);//每一个新样例都要重置b，c
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int cnt=0;
	long long ans=0;
	for(int i=n;i>=1;i--){//逆序维护后继0的个数，顺便求不操作的ans
		b[i]=cnt;
		
		if(a[i]==0)cnt++;
		if(a[i]==1)ans+=b[i];
		
	}
	//cout<<"ans"<<ans<<endl;
	cnt=0;
	for(int i=1;i<=n;i++){//顺序维护前继1的个数
		c[i]=cnt;
		if(a[i]==1)cnt++;
		
	}	
	
	/*for(int i=1;i<=n;i++){
		cout<<b[i]<<" ";
	}
	cout<<endl;
		for(int i=1;i<=n;i++){
		cout<<c[i]<<" ";
	}
	cout<<endl;*/
	cnt=0;
	int temp=0;
	for(int i=1;i<=n;i++){//遍历判断每一位的贡献值
		
		if(a[i]==0)cnt=b[i]-c[i];
		else cnt=c[i]-b[i];
		//cout<<cnt<<endl;
		temp=max(temp,cnt);//维护最大贡献值
	}
	
	cout<<ans+temp<<endl;//即为答案
	
}

int main(){
	
	int _;
	cin>>_;
	for(int i=1;i<=_;i++){
	//	cout<<i<<"ci:  "<<endl;
		solve();
	}
}

C. awoo's Favorite Problem

You are given two strings s and t, both of length n. Each character in both string is 'a', 'b' or 'c'.

In one move, you can perform one of the following actions:

  • choose an occurrence of "ab" in s and replace it with "ba";

  • choose an occurrence of "bc" in s and replace it with "cb".

You are allowed to perform an arbitrary amount of moves (possibly, zero). Can you change string $s $ to make it equal to string \(t\)?

Input

The first line contains a single integer \(q (1≤q≤10^4)\) — the number of testcases.

The first line of each testcase contains a single integer \(n (1≤n≤10^5)\) — the length of strings s and t.

The second line contains string s of length n. Each character is 'a', 'b' or 'c'.

The third line contains string t of length n. Each character is 'a', 'b' or 'c'.

The sum of n over all testcases doesn't exceed 105.

Output

For each testcase, print "YES" if you can change string s to make it equal to string t by performing an arbitrary amount of moves (possibly, zero). Otherwise, print "NO".

题意

对于一个仅含'a''b''c'的字符串，其中①"ab"可以变成"ba"；②"bc"可以变成"cb"，两种操作都可以执行任意次

判断字符串\(s\)能不能变为\(t\)

例如bcaabababc →cbbababaac

题解

根据操作的性质，我们可以发现

①a和c的相对位置与b无关

②a只能向右移动

③c只能向左移动

这三个条件就是判断字符串能否变形成功的充分必要条件。

为了判断这三个条件，我们可以进行如下操作：

①删除\(s\)和\(t\)中的'b'，首先判断是否相等，不相等的话可以直接输出NO了

②判断是否\(s\)中第\(i\)个'a'的下标都小于等于\(t\)中第\(i\)个'a'的下标

③判断是否\(s\)中第\(i\)个'c'的下标都大于等于\(t\)中第\(i\)个'c'的下标

时间复杂度\(O(n)\)

#include <bits/stdc++.h>

using namespace std;
const int N=2e5+10;

void solve(){
	string ss,tt,s,t;
	vector<int>sa,sc,ta,tc;//分别存储s、t中'a','c'的下标
	int n;
	cin>>n;
	cin>>s>>t;
	for(int i=0;i<n;i++){
  
		if(s[i]!='b')ss+=s[i];	
		if(s[i]=='a')sa.push_back(i);
		if(s[i]=='c')sc.push_back(i);
	}
	for(int i=0;i<n;i++){

		if(t[i]!='b')tt+=t[i];
		
		if(t[i]=='a')ta.push_back(i);
		if(t[i]=='c')tc.push_back(i);
	}
	//cout<<ss<<endl<<tt<<endl;
	if(ss!=tt){//ss,tt即为去除'b'之后的s和t
		cout<<"NO"<<endl;
		return ;
	}
	for(int i=0;i<sa.size();i++){
		if(sa[i]>ta[i])
		{
			cout<<"NO"<<endl;
		return ;
		}
	}
	for(int i=0;i<sc.size();i++){
		if(sc[i]<tc[i])
		{
			cout<<"NO"<<endl;
		return ;
		}
	}
	cout<<"YES"<<endl;
	return ;
	
	
}

int main(){
	
	int _;
	cin>>_;
	for(int i=1;i<=_;i++){
	//	cout<<i<<"ci:  "<<endl;
		solve();
	}
}

D. Rock and Lever

Danik urgently needs rock and lever! Obviously, the easiest way to get these things is to ask Hermit Lizard for them.

Hermit Lizard agreed to give Danik the lever. But to get a stone, Danik needs to solve the following task.

You are given a positive integer \(n\), and an array a of positive integers. The task is to calculate the number of such pairs \((i,j)\) that $i<j $and \(a_i\) & \(a_j≥a_i⊕a_j\), \(aj≥ai⊕aj\), where & denotes the bitwise AND operation, and ⊕ denotes the bitwise XOR operation.

Danik has solved this task. But can you solve it?

Input

Each test contains multiple test cases.

The first line contains one positive integer \(t (1≤t≤10)\) denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer \(n (1≤n≤10^5)\) — length of the array.

The second line contains n positive integers \(a_i (1≤a_i≤10^9)\) — elements of the array.

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(10^5\).

Output

For every test case print one non-negative integer — the answer to the problem.

题意

判断序列内每一个数与其右边的所有数中，满足对应关系的对数。对应关系为 \(a_i\) & \(a_j≥a_i⊕a_j\), &为并运算，⊕为异或运算。

思路

1&1=1；1&0=0&1=0&0=0；

1⊕1=0⊕0=0；1⊕0=0⊕1=1；

所以对于位运算的判断，我们发现这只取决于最高位的\(1\)的位次。例如对于数\(a_j\)，它的最高位的1出现在t位，那么所有在它前面的最高位的1同样出现在t位的数\(a_i\)，都满足 \(a_i\) & \(a_j≥a_i⊕a_j\)

所以我们只需要遍历数列，对于每一个数x都获取其最高位的1的位次\(getwei(x)\)，并且使用一个\(sum\)数组记录已经遍历过的数的最高位的1的位次对应的数字数。

那么假设sum[i]存的是最高位的1位次为i的数字的个数，那么\(ans+=sum[getwei(x)]\),然后再将\(sum[getwei(x)]\)++即可。

代码

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+10;
int a[N];
int num[100];

int getwei(int n){//统计最高位的1的位数（从右往左数）
	int cnt=0;
	while(n>0){
		cnt++;
		n>>=1;
	}
	return cnt;
}


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

memset(num,0,sizeof num);

long long ans=0;
for(int i=1;i<=n;i++)
{
	int t=getwei(a[i]);
	ans+=num[t];//更新答案
	num[t]++;//更新num数组
}
    
    cout<<ans<<endl;
}

int main(){
	
    long long _;
    cin>>_;
    for(long long i=1;i<=_;i++){
        solve();
    }
}

E. Two Arrays

RedDreamer has an array a consisting of \(n\) non-negative integers, and an unlucky integer \(T\).

Let's denote the misfortune of array b having length m as \(f(b)\) — the number of pairs of integers \((i,j)\) such that \(1≤i<j≤m\) and \(bi+bj=T\). RedDreamer has to paint each element of a into one of two colors, white and black (for each element, the color is chosen independently), and then create two arrays c and d so that all white elements belong to \(c\), and all black elements belong to $d $(it is possible that one of these two arrays becomes empty). RedDreamer wants to paint the elements in such a way that \(f(c)+f(d)\) is minimum possible.

For example:

  • if \(n=6, T=7\) and \(a=[1,2,3,4,5,6],\) it is possible to paint the \(1\)-st, the \(4\)-th and the \(5\)-th elements white, and all other elements black. So \(c=[1,4,5], d=[2,3,6]\), and \(f(c)+f(d)=0+0=0\);

  • if n=3, T=6 and a=[3,3,3], it is possible to paint the 1-st element white, and all other elements black. So \(c=[3], d=[3,3]\), and \(f(c)+f(d)=0+1=1\).

Help RedDreamer to paint the array optimally!

题意

给定数组长度n和一个正整数t，将n中的数分为2组，使得两组各自内部的数对和为t的对数数量最少。

思路

观察得到：只要把所有小于\(t/2\)的放一组，大于\(t/2\)的放一组，等于\(t/2\)的交替尽量均匀分组即可。但是要注意一个细节，t是奇数时，要注意除2后的取整问题，这时候所有小于等于下取整的应该在一组，大于等于上取整的在另外一组。

代码

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+10;
int a[N];


void solve(){
int n,t;
cin>>n>>t;

for(int i=1;i<=n;i++){
	cin>>a[i];
} 
bool flag=0;
for(int i=1;i<=n;i++){
	if(a[i]<(t+1)/2){//将边界问题统一了，不需要分别讨论t的奇偶性
		cout<<1<<" ";
	}
	else if(a[i]>t/2){
		cout<<0<<" ";
	}
	else {
		cout<<flag<<" ";
		flag=!flag;
	}
	
}
cout<<endl;

}

int main(){
	
    long long _;
    cin>>_;
    for(long long i=1;i<=_;i++){
        solve();
    }
}