_WA自动机的blog

过期高中生。

CGR18题解

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

简简单单2篇题解。

B

题意

n次询问，每次给定l,r，求[l,r]内至少删掉多少数，使得剩下的数按位与不为0。 出题人加强版：\(n \leq 2*10^5\),\(l,r \leq 10^9\)

解法

原题数据范围是\(l,r\leq 2*10^5\).先考虑这个怎么做： 按位与不为0，就是存在某一位，满足这个集合所有的数这一位都是1.考虑枚举某一位，前缀和统计个数，即可在对数时间内完成。 加强版不能这么求前缀和了，这迫使我们寻找简便的求某一位为1的个数的算法。考虑二进制加1的过程，我们用以下解法替代前缀和：

1
2
3
4
5
6
7
long long getcount(long long n, int k)
{
    long long res = (n >> (k + 1)) << k;
    if ((n >> k) & 1)
        res += n & ((1ll << k) - 1);
    return res;
}

代码

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

using std::max;

const int N=2e5+100;

typedef long long int64;

int getcount(int n,int k)
{
    int res=(n>>(k+1))<<k;
    if ((n>>k)&1)
        res+=(n&((1<<k)-1));
    return res;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int ans=0;
        for (int i=30;~i;--i)
            ans=max(ans,getcount(r+1,i)-getcount(l,i));
        printf("%d\n",r-l+1-ans);
    }
}

C

题意

你有两个长度为n的01串A和B.每次操作可以选择一个当前为1的点，将除了它以外的所有点的数值取反。求至少多少次操作之后，可以把A变成B.\(n\le 10^5\)

解法

单次变换好像看不出来什么，但是简单模拟可以发现，两次变换相当于交换了一对0和1.所以对于总操作次数为偶数的方案，答案可以直接算出来。奇数次操作相当于先进行了一次操作，再进行偶数次操作。枚举第一次操作的两种情况：（选定的1在B中对应的是1还是0），算出来变换之后01和10各有多少种，就可以O(1)得到答案。

代码

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

using std::min;

const int N=1e5+199;
const int oo=0x3f3f3f3f;

char a[N],b[N];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n;
        scanf("%d",&n);
        scanf("%s%s",a+1,b+1);
        int x=0,y=0,z=0,w=0;
        for (int i=1;i<=n;++i)
        {
            if (a[i]=='0' && b[i]=='0') ++x;
            if (a[i]=='0' && b[i]=='1') ++y;
            if (a[i]=='1' && b[i]=='0') ++z;
            if (a[i]=='1' && b[i]=='1') ++w;
        }
        // printf("DEBUG %d %d %d %d\n",x,y,z,w);
        int ans=oo;
        if (y==z) ans=y*2;
        // 如果第一次操作是10
        if (z && w==x+1) ans=min(ans,2*w+1);// +1是第一次操作
        // 如果第一次操作是11
        if (w && w-1==x) ans=min(ans,2*x+1);// +1是第一次操作
        printf("%d\n",ans==oo?-1:ans);
    }
}

D

题意

给定一棵树，有些边的边权已知，有些边未知。现在有一些限制条件，每个条件形如“从u点到v点，边权的异或和的popcount是奇数还是偶数”。要求给出一种可行的给未知边赋值的方案，满足所有条件；或者指出方案不存在。

题解

考虑以下性质： \[\mathrm{popcount}(x\oplus y)\mod 2=\mathrm{popcount}(x) \mod 2 \oplus \mathrm{popcount}(y) \mod 2\] 这个性质指出，对于每一条边，都可以按照popcount的奇偶性变成01边。如果对于每个点维护它到根01路径上的异或和，记为s。那么每个限制就变成了\(s(x) \oplus s(y)=0/1\)。我们用一种类似二分图染色的方法，对于每个连通块，尝试构造可行的方案。染色完成之后，一条边的权值就是\(s(x)\oplus s(\mathrm{fa}[x])\)。

代码

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

using std::map;
using std::vector;
using std::pair;
using std::minmax;
using std::make_pair;

const int N=4e5+1000;

vector<int> G[N];
int fa[N];

struct Path
{
    int x,y,v;
}P[N];

void dfs(int u,int ff)
{
    fa[u]=ff;
    for (auto v:G[u])
        if (v!=ff) dfs(v,u);
}

int head[N],cnt;

struct Edge
{
    int to,next,w;
}edge[N<<1];

void _add(int u,int v,int w)
{
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}

void add(int u,int v,int w){_add(u,v,w);_add(v,u,w);}

int col[N],f[N];

bool dfs(int u)
{
    bool ans=false;
    for (int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if (col[v]!=-1 && col[v]!=(col[u]^edge[i].w)) return true;
        if (col[v]==-1)
            col[v]=col[u]^edge[i].w,ans|=dfs(v);
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;++i) G[i].clear();
        cnt=0;
        memset(head,0,sizeof(int)*(n+1));
        int tot=0;
        map<pair<int,int>,int> mp;
        for (int i=1;i<n;++i)
        {
            int x,y,v;
            scanf("%d%d%d",&x,&y,&v);
            G[x].push_back(y);
            G[y].push_back(x);
            if (~v)
            {
                int w=__builtin_popcount(v)%2;
                P[++tot]=Path{x,y,w};
                mp[minmax(x,y)]=v;
            } 
        }
        for (int i=1;i<=m;++i)
        {
            int a,b,p;
            scanf("%d%d%d",&a,&b,&p);
            P[++tot]=Path{a,b,p};
        }
        dfs(1,0);
        for (int i=1;i<=tot;++i)
            add(P[i].x,P[i].y,P[i].v);
        memset(col,-1,sizeof(int)*(n+1));
        bool ans=0;
        // for (int i=1;i<=n;++i)
        //     for (int j=head[i];j;j=edge[j].next)
        //     printf("%d %d %d\n",i,edge[j].to,edge[j].w);
        for (int i=1;i<=n;++i)
            if (col[i]==-1) col[i]=1,ans|=dfs(i);
        if (ans==1) {puts("NO");continue;}
        else{
            puts("YES");
            for (int i=2;i<=n;++i)
            {
                if (mp.count(minmax(i,fa[i])))
                    printf("%d %d %d\n",i,fa[i],mp[minmax(i,fa[i])]);
                else printf("%d %d %d\n",i,fa[i],col[i]^col[fa[i]]);
            }
        }
    }
}