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即可