A. A-characteristic

题目链接
由于出现数字只可能是1或-1，那么假设数列全为-1，依次枚举1出现的个数，可以得出结论不是所有数字都有答案的，由于会有重复数字出现，只需要枚举1的个数x<=n/2即可。

// Problem: A. A-characteristic
// Contest: Codeforces - Codeforces Round 868 (Div. 2)
// URL: https://codeforces.com/contest/1823/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=110;
int t,n,k;
int res[N];
bool cal(int l,int r){
	if(l*(l-1)/2+r*(r-1)/2==k){
		for(int i=1;i<=l;i++) res[i]=1;
		for(int i=l+1;i<=n;i++) res[i]=-1;
		return true;
	}
	return false;
}
bool check(int x){
	int mid=x>>1;
	for(int i=x;i>=mid;i--){
		if(cal(i,x-i)){
			return true;
		}
	}
	return false;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>k;
		if(check(n)){
			puts("YES");
			for(int i=1;i<=n;i++){
				cout<<res[i]<<" ";
			}
			puts("");
		}else{
			puts("NO");
		}
	}
	return 0;
}

B. Sort with Step

题目链接
只能交换相隔k个位置的数字，假如k为1，那么可以看作冒泡排序必然有解
k>1时，将数组按照下标i分组，i%k0的为一组，i%k1的为一组，...，i%k==k-1的为一组，要想可以按照递增序列上升，同时由于数字x<n,且只会出现一次。所以如果不先更换一组数据就有解的话，同一组内的数字对k取模的结果必然一致。不一致的话当不一致的数字为2时，可以交换一次得到解，否则无解。

// Problem: B. Sort with Step
// Contest: Codeforces - Codeforces Round 868 (Div. 2)
// URL: https://codeforces.com/contest/1823/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=2e5+10;
int t,n,k;
int p[N],tmp[N];
vector<int> q[N];
LL getnum(int l,int r){
	if(l>=r) return 0;
	int mid=(l+r)>>1;
	LL ans=getnum(l,mid)+getnum(mid+1,r);
	int i=l,j=mid+1,cnt=0;
	while(i<=mid&&j<=r){
		if(p[i]<=p[j]) tmp[cnt++]=p[i++];
		else{
			ans+=mid-i+1;
			tmp[cnt++]=p[j++];
		}
	}
	while(i<=mid) tmp[cnt++]=p[i++];
	while(j<=r) tmp[cnt++]=p[j++];
	for(i=l,j=0;i<=r;i++,j++){
		p[i]=tmp[j];
	}
	return ans;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		for(int i=0;i<k;i++){
			q[i].clear();
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&p[i]);
			q[i%k].push_back(p[i]);
		}
		if(k==1){
			puts("0");
			continue;
		}
		int res=0;
		for(int i=0;i<k;i++){
			// sort(q[i].begin(),q[i].end());
			// for(int j=0;j<q[i].size();j++){
				// p[i+j*k]=q[i][j];
				// cout<<q[i][j]<<" ";
			// }
			// cout<<endl;
			for(int j=0;j<q[i].size();j++){
				if(q[i][j]%k!=i) res++; 
			}
		}
		// LL res=getnum(1,n);
		// cout<<res<<endl;
		// for(int i=1;i<=n;i++){
			// cout<<p[i]<<" ";
		// }
		// cout<<endl;
		if(res==0) puts("0");
		else if(res==2) puts("1");
		else puts("-1");
	}

	return 0;
}

C. Strongly Composite

题目链接
比赛的时候没做出来但是思路对的，先贴代码

// Problem: C. Strongly Composite
// Contest: Codeforces - Codeforces Round 868 (Div. 2)
// URL: https://codeforces.com/contest/1823/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=1010,M=1e5+10;
int T;
int n,k;

int main(){
	/*
	res
	暂时想出来的思路是计算出所有乘数中每个质数的数量，
	然后同一个素数下每两个组合，直至每个素数均剩下0或1个,res+=每个素数的数量/2
	然后计算剩余个数为1的素数的个数count如果可以整除3那么res+=count/3,否则就看乘积是不是强合数，是的话res=1,不是res=0
	*/
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		map<int,int> q;
		for(int i=0;i<n;i++){
			int x;
			scanf("%d",&x);
			for(int j=2;j<=x/j;j++){
				while(x%j==0){
					x/=j;
					q[j]++;
				}
			}
			if(x!=1) q[x]++;
		}
		int res=0,rem=0;
		for(PII p:q){
			int num=p.x;
			int cnt=p.y;
			res+=cnt/2;
			rem+=cnt%2;
		}
		res+=rem/3;
		printf("%d\n",res);
	}

	return 0;
}

思路证明：对于一个强合数x，对其进行因式分解x=\(d^{p_1}_{1}\)\(d^{p_2}_{2}……\)\(d^{p_{m-1}}_{m-1}\)\(d^{p_m}_{m}\),那么x的因子数量为D=$\prod_{i=1}^m{(d_i+1)} \( 数字的质因子个数为m,合因数的个数为D-m-1.x是强合数m<=D-m-1即2*m+1<=D,由于\)d_i$+1>=2,那么D>=\(2^m\)
对于强合数的一个弱条件，2*m+1<=\(2^m\),当m为1或2时不成立其余成立，那么由于D>=\(2^m\),所以当m为1或2时，x为强合数
即如果是一个强合数，质因子个数大于等于3
接下来找出所有数列中的质因子得到(\(p^i\),\(c^i\)),前为质因子，后为所有数中质因子个数。
最优策略是对于同一质因子求\(\sum_i{ci/2}\),剩下个数r=\(\sum_i(ci\%2)\)
res+=\(\sum_i{ci/2}\)+r/3即可