请添加图片描述


A. GCD vs LCM

题意:

给定数n,找到a,b,c,d四个数满足下列条件:

1.a+b+c+d=na+b+c+d=n
2.gcd(a,b)=lcm(c,d)gcd(a,b)=lcm(c,d)

思路:

取特殊情况,令gcd(a,b)=1gcd(a,b)=1即可。
即构造a=1,b=n3,c=1,d=1a=1,b=n-3,c=1,d=1

时间复杂度:

所需时间与输入规模无关:
O(1)O(1)

AC代码:
在这里插入图片描述

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>

const int N = 2e2+10,M = 2e5+10,INF = 0x3f3f3f3f;

void solve()
{
int n;
std::cin>>n;
std::cout<<1<<' '<<n-3<<1<<' '<<1<<'\n';
}

int main()
{
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cout.tie(nullptr);
int T;
std::cin>>T;
while(T--)
{
solve();
}
return 0;
}

B. Array Cloning Technique

题意:

给定一个长度为n的初始数组副本,你可以进行以下两种操作:

  1. 选择任意一个数组副本,将其复制出一个新的数组副本。
  2. 选择两个数组副本,交换它们的两个元素。

询问将其中任意一个数组副本的全部元素变相同的最少操作次数。

思路:

  1. 首先,我们贪心的选择第一个数组副本作为目标,将这个数组的全部元素变成相同。
  2. 然后,我们记录下初始数组副本中的最大相同数字出现次数maxmax,那么将其他所有元素变成相同的交换(操作1)次数显然是nmaxn-max
  3. 接着我们计算复制数组副本的次数(操作2),我们不难发现每次复制并交换结束后,相同数的个数都会翻倍,所以我们通过这种方式找到最小复制次数即可。

最后,将操作1和操作2的次数相加即可。

时间复杂度:

统计相同数字的最大出现次数中使用了map来完成,所以时间复杂度为:
O(nlogn)O(nlogn)

AC代码:
在这里插入图片描述

cpp
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
#include<bits/stdc++.h>

const int N = 2e2+10,M = 2e5+10,INF = 0x3f3f3f3f;

void solve()
{
int n;
int max = 0;
std::cin>>n;
std::map<int,int> mp;
for(int i = 1 ; i <= n ; i++)
{
int x;
std::cin>>x;
mp[x]++;
if(mp[x] > max)max = mp[x];
}
int res = 0,cnt = n - max;
if(cnt==0)std::cout<<0<<'\n';
else
{
for(;max < n;max <<= 1)res++;
res += cnt;
std::cout<<res<<'\n';
}
}

int main()
{
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cout.tie(nullptr);
int T;
std::cin>>T;
while(T--)
{
solve();
}
return 0;
}

C. Tree Infection

题意:

给定一棵树,现在要去感染这棵树的全部节点,我们可以在每个单位时间内执行以下两种操作(同时进行):

  1. 对于所有的节点,如果他的某个孩子节点被感染,那么可以感染一个其它健康的孩子节点。
    2.任意选择一个健康的节点,并感染它。

询问将整棵树感染的最少时间。

思路:

首先,我们可以发现,感染传播(操作1)只会在一个个"孩子群体"中进行,实际上感染与树并没有太大的关系,我们完全可以把这一个个"孩子群体"取出来。
还是举个例子(第一个案例):

7
1 1 1 2 2 4
很显然,这里的"群体"有这些:
{1},{2,3,4},{5,6},{7}

我们可以先把所有的群体找出来,然后采用贪心策略,从数量大的群体开始感染,采用如下判断方法:

  1. 我们从大到小感染所有"群体"(依次对所有"群体"使用操作1一次,然后让它们内部传播),我们记录下完成上述操作后所有群体还剩下的未感染个数(如果已经全部感染则不用管)。
  2. 如果此时还有剩余节点未被感染,我们让它们内部传播,并手动感染剩余节点最多的"群体"。

即在贪心后模拟感染的过程(实现上可能还是有点复杂了)。

时间复杂度:

使用了map和优先队列,总时间复杂度:O(nlogn)O(nlogn)

AC代码:
在这里插入图片描述

cpp
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
#include<bits/stdc++.h>

const int N = 2e2+10,M = 2e5+10,INF = 0x3f3f3f3f;

void solve()
{
int n,t = 0;
std::cin>>n;
std::priority_queue<int> que;
std::map<int,int> mp;
mp[0] = 1;
for(int i = 1 ; i < n ; i++)
{
int x;
std::cin>>x;
mp[x]++;
}
std::vector<int> num;
for(auto map : mp)num.push_back(map.second);//从大到小排序"群体"
std::sort(num.begin(),num.end());
for(auto val : num)//第一步
{
if(val - 1 - t > 0)que.push(val - 1 - t);
t++;
}
int res = 0;
while(true)
{
if(que.empty()||que.top() - res <= 0)break;//第二步
que.push(que.top()-1);
que.pop();
res++;
}
std::cout<<res+t<<'\n';
}

int main()
{
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cout.tie(nullptr);
int T;
std::cin>>T;
while(T--)
{
solve();
}
return 0;
}

D. GCD Guess

题意:

交互题:
先要猜测一个整数x的大小,你可以按照以下规则询问最多30次:

给出数字aabb,返回gcd(a+x,b+x)gcd(a+x,b+x)

思路:

30次的询问次数,我们应该尝试从位的角度取解决。
那么我们怎么知道每一位取0还是1呢,按照如下方法:

  1. 假设我们已知x mod 2k=ansx\ mod\ 2^k = ans
  2. 那么xansx-ans11~kk位应该全是0
  3. 我们可以用gcd(xans,2k+1)gcd(x-ans,2^{k+1})是否等于2k2^k来判断k+1k+1位取0还是1。
  4. 若等于2k2^k,则取1,若不等,则取0。
  5. 此时询问的a=ansa=-ans,而询问数应该大于0,所以我们询问gcd(xans+2k,2k+1)gcd(x-ans+2^{k},2^{k+1})
  6. 若等于2k2^k,则取0,若不等,则取1。
  7. gcd(xans+2k,2k+1)=gcd(xans+2k,2k+1+(xans+2k))gcd(x-ans+2^{k},2^{k+1})=gcd(x-ans+2^{k},2^{k+1}+(x-ans+2^{k}))(这个转换是为了凑出a和b),所以询问为a=ans+2k,b=ans+2k+2k+1a=-ans+2^k,b=-ans+2^k+2^{k+1}

时间复杂度:

我们每次询问可以确定数xx的某一位:
O(logn)O(logn)

AC代码:
在这里插入图片描述

cpp
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
#include<bits/stdc++.h>
typedef long long ll;
const int N = 2e2+10,M = 2e5+10,INF = 0x3f3f3f3f;

int query(int x,int y)
{
std::cout<<"? "<<x<<' '<<y<<std::endl;
int res;
std::cin>>res;
return res;
}

void solve()
{
int ans = 0;
for(int i = 1 ; i <= 30 ; i++)
{
int res = query((1<<i-1)-ans,(1<<i)+(1<<i-1)-ans);
if(res != (1<<i-1))ans += (1<<i-1);
}
std::cout<<"! "<<ans<<std::endl;
}

int main()
{
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cout.tie(nullptr);
int T;
std::cin>>T;
while(T--)
{
solve();
}
return 0;
}

E. MinimizOR

题意:

给定长度为n的数组,定义花费为aiaj(i !=j)a_i|a_j(i\ !=j),现在给出q个询问:

给出整数llrr,找出区间内的最小花费。

思路:

本题最重要的是证明一个性质:

如果区间内的最大数Amax<2kA_{max} < 2^k(即最大数不超过k位),那么答案一定在k+1k+1个区间最小数内按位或产生。
证明如下:

k=1k=1,只有0和1两个数,显然成立。
现在我们将设结论对kk成立,我们尝试证明对k+1k+1也成立。
分类讨论:

  1. k+1k+1位全是1,那么答案必然出现在之前已经选择的k+1k+1个数中,而且此时选择的k+1k+1个最小数与之前应该是一致的。
  2. k+1k+1位0的个数大于等于2,那么答案必然出现在之前已经选择的k+1个数中,而且此时选择的k+1k+1个最小数与之前应该是一致的。
  3. k+1k+1位0的个数恰好等于1,k+1k+1应该取1,所以答案还是出现在之前选择的k+1k+1个数中,但是此时选择的k+1k+1个最小数与之前不一定一致,因为最坏情况就是之前k+1k+1个数k+1k+1位全是1,而此时k+1k+1位是0的一个数会取代其中的一个数,所以我们这个时候要多取一个数,取k+2k+2个最小数即可。

通过以上说明,我们证明结论:

如果区间内的最大数Amax<2kA_{max} < 2^k(即最大数不超过k位),那么答案一定在k+1k+1个区间最小数内按位或产生

现在的任务就是找到k+1k+1区间最小数,这个可以用线段树完成。
此外,因为AmaxA_{max}的范围并不会很大,所以我们每次并不会真的求出它,我们每次都假定它在边界最大值Amax=2301A_{max}=2^{30}-1,所以每次最多找到31个最小数。

时间复杂度:

这题的常数会特别大,因为每次询问都需要查找最多31次。
O(q(mlogn+m2))(m=min(rl+1,31))O(q*(mlogn+m^2))(m=min(r-l+1,31))

AC代码:
在这里插入图片描述

cpp
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
typedef long long ll;
const int N = 1e5+10,M = 2e5+10,INF = (1ll<<31)-1;
struct Node{
int l,r,v,id;
}tr[N*4];
int w[N];

void pushup(int u)
{
tr[u].v = std::min(tr[u<<1].v,tr[u<<1|1].v);
if(tr[u<<1].v < tr[u<<1|1].v)tr[u].id = tr[u<<1].id;
else tr[u].id = tr[u<<1|1].id;
}

void build(int u,int l,int r)
{
if(l==r)
{
tr[u] = {l,r,w[r],r};
}
else
{
tr[u] = {l,r};
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}

std::pair<int,int> query(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return std::make_pair(tr[u].v,tr[u].id);
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
std::pair<int,int> ans = {INF,INF};
if(l <= mid)ans = std::min(ans,query(u<<1,l,r));
if(r > mid)ans = std::min(ans,query(u<<1|1,l,r));
return ans;
}
}

void modify(int u,int x,int v)
{
if(tr[u].l==x&&tr[u].r==x)
{
tr[u].v = v;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);
}
}

void solve()
{
int n,q;
std::cin>>n;
for(int i = 1 ; i <= n ; i++)std::cin>>w[i];
build(1,1,n);
std::cin>>q;
while(q--)
{
int l,r;
std::vector<int> res,id;
std::cin>>l>>r;
for(int i = 1 ; i <= std::min(31,r - l + 1) ; i++)
{
std::pair<int,int> temp = query(1,l,r);
res.push_back(temp.first);
id.push_back(temp.second);
modify(1,temp.second,INF);
}
int ans = INF;
for(int i = 0 ; i < res.size() ; i++)
for(int j = i + 1 ; j < res.size() ; j++)ans = std::min(ans,res[i]|res[j]);
std::cout<<ans<<'\n';
for(auto _id : id)
{
modify(1,_id,w[_id]);
}
}
}

int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int T;
std::cin>>T;
while(T--)
{
solve();
}
return 0;
}