CF R868 (div.2)

A. A-characteristic

题意：构造1|-1数列，使数组中两两相乘值为1的对数为k

思路：显而易见与1|-1的出现顺序无关，总结规律易知当1数量为2时对数为一，3时对数为3（1+（3-1）），4时对数为6（3+（4-1）），-1同理，数据量较小，枚举个数即可

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 int ans[105];
 5 
 6 void init()
 7 {
 8     ans[1]=0;
 9     for (int i=2;i<=101;i++) ans[i]=i-1+ans[i-1];    
10 }
11 
12 int main()
13 {
14     ios::sync_with_stdio(false);
15     cin.tie(0);cout.tie(0);
16     init();
17     int t;
18     cin>>t;
19     while (t--){
20         int n,k;
21         cin>>n>>k;
22         int ps=1;
23         for (int i=1;i<=n;i++){
24             if (ans[i]+ans[n-i]==k){
25                 ps=0;
26                 cout<<"YES"<<'\n';
27                 for (int j=0;j<i;j++) cout<<1<<" ";
28                 for (int j=0;j<n-i;j++) cout<<-1<<" ";
29                 cout<<'\n';
30                 break;
31             }
32         }
33         if (ps) cout<<"NO"<<'\n';
34     }
35 }

B. Sort with Step

题意：如果可以通过多次ai与a（i+k）交换使数组变成最小排列就输出0；如果只是这么做做不到但可以做将任意两个元素交换操作一次后就可以做到就输出1，否则输出-1

思路：若是答案为0，在ai位置上的数对k取模必然等于i对k取模（关系闭包），若有两个位置不能满足就输出1，超过两个就输出-1

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     ios::sync_with_stdio(false);
 8     cin.tie(0);cout.tie(0);
 9     int t;
10     cin>>t;
11     while (t--){
12         int n,k;
13         cin>>n>>k;
14         int sum=0;
15         for (int i=1;i<=n;i++){
16             int q;
17             cin>>q;
18             if (q%k!=i%k){
19                 sum++;
20             }
21         }
22         if (!sum) cout<<0<<'\n';
23         else if (sum==2) cout<<1<<'\n';
24         else cout<<-1<<'\n';
25     }
26 }

C. Strongly Composite

题意：一个数因子中若质数个数小于等于合数个数，那么这个数就是强壮数，给你n个数相乘，需要将其转化成强壮数相乘的形式，问最多可以转化成几个强壮数相乘

思路：强壮数可以以两种形式得到，一是n^2，二是至少三个质数相乘，所以可以将给出的数全变成质数相乘的形式并统计每种质因子有多少个，相同的两两配对，不同的三三配对即可获得答案

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int maxn=1e4;
 5 int prime[maxn],ans;
 6 bool vis[maxn];
 7 map<int,int> mp;
 8 set<int> s;
 9 
10 void init()//素数筛找质数
11 {
12     vis[0]=vis[1]=true;
13     for (int i=2;i<maxn;i++){
14         if (!vis[i]) prime[++prime[0]]=i;
15         for (int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){
16             if (i%prime[j]==0) break;
17             vis[i*prime[j]]=true;
18         }
19     }
20 }
21 
22 void toans(int q)//分解数为质数积
23 {
24     for (int i=1;i<=prime[0];i++){
25         if (q%prime[i]==0){
26             s.insert(prime[i]);
27             while (q%prime[i]==0) q/=prime[i],mp[prime[i]]++;
28         }
29         if (q==1) return;
30     }
31     s.insert(q);
32     mp[q]++;
33 }
34 
35 int main()
36 {
37     ios::sync_with_stdio(false);
38     cin.tie(0);cout.tie(0);
39     init();
40     int t;
41     cin>>t;
42     while (t--){
43         mp.clear();
44         s.clear();
45         ans=0;
46         int n,q;
47         cin>>n;
48         for (int i=0;i<n;i++){
49             cin>>q;
50             toans(q);
51         }
52         int tem=0;
53         for (auto p:s){
54             ans+=mp[p]/2;
55             tem+=mp[p]%2;
56         }
57         ans+=tem/3;
58         cout<<ans<<'\n';
59     }
60 }