0%

cf1471

cf1471

虚拟赛,打的时候状态还行,但是wa的多,还卡D了,问题挺多的

A: Strange Partition :水

注意是向上取整,分开最大,求和最小。
代码略。

B: Strange List:水

每被拆一次,这个数多记一次。拆是原子的,不会拆一半。
碰到不能拆中断,即找出最小值mi,此数前最多拆mi+1次,后面最多拆mi次。
代码略。

C:Strange Birthday Party:水

贪心从后面开始满足条件的分即可。
代码略。

D:Strange Definition:思维

题中给的相邻条件可以简单化为二者积为完全平方数。进一步,将两个数各自质因数分解,如果一个因子有偶数次幂,就放到平方里,即乘积是否是完全平方数只与二者的奇数次质因子有关。即需要二者这几个因子同时为奇数。
因为是质因子,所以只要看这些因子的乘积即可唯一确定是哪些因子。所以开map记录这些“剩余因子”乘积即可,相同即相邻。
即 $A =x^2\times a,B=y^2\times b,A\times B=(xy)^2\times a\times b$

0s,即初始,跑一遍,求最大集合势ans1

1s,进行一次操作,把初始“剩余因子”乘积相同的数乘起来,

  • 如果有奇数个, $a\times a\times…\times a=()^2\times a$ ,每个位置“剩余因子”乘积不变。
  • 如果偶数个, $a\times a\times …\times a=()^2\times 1$ 每个位置“剩余因子”乘积变1。

奇数势的集合保持不变。
偶数势1s后变1,然后不变
则1s后为ans2=MAX(ans1,m1)
m1为完全平方数(剩余1)的个数

注意:

  • 质因数分解,在筛素数时,求出最大质因子(mpp)
  • 以后用scanf
  • 注意ll

。。。。为什么这么多注意?。。。。。。:(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
const int maxn=1000010;
const int maxn2=3e5+10;
ll Pri[maxn] = {0};
ll numPri = 0;//从0计数,第0,1,2...个质数
int notPri[maxn] = {1, 1};//0-质数,1-非质数
int mpp[maxn];
void init() {
for (ll i = 2; i < maxn; i++) {
if (!notPri[i]){
Pri[numPri++] = i;
mpp[i]=i;
}
for (ll j = 0; j < numPri && i * Pri[j] < maxn; j++) {
notPri[i * Pri[j]] = 1;
mpp[i*Pri[j]]=Pri[j];
if (!(i % Pri[j]))
break;
}
}
}
int func(int a){
int ans=1;
while(a>1){
int p=mpp[a],now=0;
while(mpp[a]==p){
now++;
a/=p;
}
if(now%2==1)ans*=p;
}
return ans;
}
int a[maxn2];
int b[maxn2];
int main(){
init();
int t;scanf("%d",&t);while(t--){
map<int,int> m1;
int n;scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
b[i]=func(a[i]);
m1[b[i]]++;
}
int ans1=-1;
for(int i=1;i<=n;++i){
ans1=max(ans1,m1[b[i]]);
}
map<int,int>m2;
for(int i=1;i<=n;++i){
if(m1[b[i]]%2==1){
m2[b[i]]++;
}else{
m2[1]++;
}
}
int ans2=max(ans1,m2[1]);
int q;scanf("%d",&q);
ll w;
while(q--){
scanf("%lld",&w);
if(w==0)printf("%d\n",ans1);
else printf("%d\n",ans2);
}
}
return 0;
}