请添加图片描述

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=n−3,c=1,d=1a=1,b=n-3,c=1,d=1

时间复杂度：

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

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

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)次数显然是n−maxn-max。
  3. 接着我们计算复制数组副本的次数(操作2)，我们不难发现每次复制并交换结束后，相同数的个数都会翻倍，所以我们通过这种方式找到最小复制次数即可。

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

时间复杂度：

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

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

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代码：
在这里插入图片描述

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次：

给出数字aa和bb，返回gcd(a+x,b+x)gcd(a+x,b+x)

思路：

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

  1. 假设我们已知x mod 2k=ansx\ mod\ 2^k = ans
  2. 那么x−ansx-ans的11~kk位应该全是0
  3. 我们可以用gcd(x−ans,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(x−ans+2k,2k+1)gcd(x-ans+2^{k},2^{k+1})。
  6. 若等于2k2^k，则取0，若不等，则取1。
  7. gcd(x−ans+2k,2k+1)=gcd(x−ans+2k,2k+1+(x−ans+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代码：
在这里插入图片描述

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的数组，定义花费为ai∣aj(i !=j)a_i|a_j(i\ !=j)，现在给出q个询问：

给出整数ll和rr，找出区间内的最小花费。

思路：

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

如果区间内的最大数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=230−1A_{max}=2^{30}-1，所以每次最多找到31个最小数。

时间复杂度：

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

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

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;
}