_WA自动机的blog

过期高中生。

CF1617题解

发表于 更新于 阅读次数： Valine：

简简单单1篇题解。

B

Prob

给定一个\(n\)，求一组\(a,b,c\)使得\(a+b+c=n\)且\(\mathrm{gcd}(a,b)=c\)

Sol

令c=1，题目转化为已知z,求一组互质的x,y,满足x+y=z.

根据更相减损术，(a,b)=(a,a+b)=(a,c);所以我们只需要找到一个和c互质的a，问题就解决了。可以直接枚举。

Code

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
#include <cstdio>
#include <algorithm>

using std::__gcd;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n;
        scanf("%d",&n);
        int c=1;
        if (n&1)
        {
            int c=1;
            int now=n-1;
            int a=2;
            while (__gcd(a,now)>1) ++a;
            int b=now-a;
            printf("%d %d %d\n",a,b,c);
        }
        else
        {
            int c=1,p=(n-1)/2,q=p+1;
            printf("%d %d %d\n",p,q,c);
        }
    }
}

C

Prob

给定长度为n的序列A，每次可以任选一个\(A_i\)和一个\(x\)，令\(A_i=A_i \mod x\).求至少多少次操作之后，可以将A变成1~n的排列？

Sol

考虑一个数x可以变成的数的区间是\([1,\lfloor(x-1)/2\rfloor]\) 所以把序列排序，显然如果一个数可以不变那不变是最优的 所以贪心地填就可以了，如果某一个数填不了，证明不合法。

Code

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
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>

const int N=1e5+1000;

using std::sort;
using std::set;

int a[N];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n;
        scanf("%d",&n);
        for (int i=1;i<=n;++i)
            scanf("%d",a+i);
        sort(a+1,a+n+1);
        set<int> s;
        for (int i=1;i<=n;++i) s.insert(i);
        bool ok=true;
        int cnt=0;
        for (int i=1;i<=n;++i)
        {
            if (a[i]<=n && s.count(a[i])) s.erase(a[i]);
            else
            {
                int lim=(a[i]-1)/2;
                auto p=s.upper_bound(lim);
                if (p==s.begin()) {ok=false;break;}
                else --p;
                ++cnt;s.erase(p);
            }
        }
        printf("%d\n",ok?cnt:-1);
    }
}

D1

Prob

有n个人站成一行。一部分人是兔子，另外一部分则是猿猴。保证人数是3的倍数，且兔子的个数k满足\(\frac{n}{3}<k<\frac{2n}{3}\)。每次可以询问交互器\(i,j,k\)三个人里面兔子多还是猿猴多，交互器会如实回答你。
要求：用至多2n次询问确定每个人的身份。

Sol

考虑如果我们知道了有两个人身份相反，那么可以在n-2次询问内得知所有其他人的身份。
如何找身份相反的人呢？一个简单的想法是考虑每次将区间右移一格：这样如果答案不相同，则出现了两个身份相反的人。根据k的范围，询问结束之前一定能找到一对。此时询问次数为n-2.这里根据已知的答案可以直接找出谁是1，谁是0.
然后询问其他人的身份，此时询问次数为2n-4.

D2

将D1的询问次数上限减少到n+6次，其余条件不变。

Sol

下文均设兔子为0，猿猴为1. 考虑将序列按三个一组分段
我们称0多的段为0-段，1多的段为1-段。 一定存在相邻的两段 一段为0-段，另外一段为1-段。 假设我们这两段为\([i,i+2],[i+3,i+5]\).我们追加询问\((i+1,i+2,i+3)\)和\((i+2,i+3,i+4)\).对于这两段，包括\((i,i+1,i+2)\)和\((i+3,i+4,i+5)\)在内，一共询问了4次。这四次里面必有两个相邻的答案相反，于是我们找出来了一对身份相反的人。此时，询问次数是\(\frac{n}{3}+2\).

现在确定剩下的人的身份。考虑对于每段，我们用两次询问确定所有人的身份：
不妨设这段为0-段（1-段方法类似），起始点为i，已知的1位置为a：
我们可以询问\((i,i+1,a)\).
* 如果答案为0，证明i和i+1均为0.一次询问确定第三个人.

  • 如果答案为1，证明两个人一个是1，一个是0，i+2是0.一次询问确定其中一个。

最后一个问题：如果a或b在区间内呢？两次询问确定其余的两个人即可。
对于每个区间我们用了两次询问。总的询问次数为\(n+2\).

Code

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
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <tuple>

const int N=2e4+1000;

int ans[N];
int res[N];

int query(int a,int b,int c)
{
    printf("? %d %d %d\n",a,b,c);
    fflush(stdout);
    int x;
    scanf("%d",&x);
    return x;
}

void query(int p,int n,int &a,int &b)
{
    int tmp[4];
    int j=(p-1)*3+1;
    tmp[0]=res[p];
    tmp[1]=query(j+1,j+2,j+3);
    tmp[2]=query(j+2,j+3,j+4);
    tmp[3]=res[p+1];
    for (int i=0;i<3;++i)
    {
        if (tmp[i]^tmp[i+1])
        {
            if (tmp[i]==0) a=j+i,b=a+3;
            else b=j+i,a=b+3;
        }
    }
    return;
}

void query0(int p,int a,int b)
{
    int i=(p-1)*3+1;
    int res=query(i,i+1,b);
    if (res==0)
    {
        ans[i]=ans[i+1]=0;
        ans[i+2]=query(i+2,a,b);
    }
    else
    {
        ans[i+2]=0;
        ans[i+1]=query(i+1,a,b);
        ans[i]=ans[i+1]^1;
    }
}

void query1(int p,int a,int b)
{
    int i=(p-1)*3+1;
    int res=query(i,i+1,a);
    if (res==1)
    {
        ans[i]=ans[i+1]=1;
        ans[i+2]=query(i+2,a,b);
    }
    else
    {
        ans[i+2]=1;
        ans[i+1]=query(i+1,a,b);
        ans[i]=ans[i+1]^1;
    }
}

void solve(int n)
{
    for (int i=1;i<=n/3;++i)
        res[i]=query((i-1)*3+1,(i-1)*3+2,(i-1)*3+3);
    int p=0;
    for (int i=1;i<n/3;++i)
        if (res[i]^res[i+1]) p=i;
    int a,b;
    query(p,n,a,b);
    // printf("%d %d %d\n",p,a,b);
    ans[a]=0;ans[b]=1;
    for (int i=1;i<=n/3;++i)
    {
        int L=(i-1)*3+1,R=L+2;
        if ((L<=a && a<=R) || (L<=b && b<=R))
        {
            for (int i=L;i<=R;++i)
                if (i!=a && i!=b) ans[i]=query(i,a,b);
        }
        else
        {
            if (res[i]==0) query0(i,a,b);
            else query1(i,a,b);
        }
    }
    printf("! ");
    int cnt=0;
    for (int i=1;i<=n;++i)
        if (ans[i]==0) ++cnt;
    printf("%d ",cnt);
    for (int i=1;i<=n;++i)
        if (ans[i]==0) printf("%d ",i);
    putchar('\n');
    fflush(stdout);
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n;
        scanf("%d",&n);
        solve(n);
    }
}