acwing-239-奇偶游戏(离散化+前缀和+带权并查集）

题意：

小A和小B在玩一个游戏。

首先，小A写了一个由0和1组成的序列S，长度为N。

然后，小B向小A提出了M个问题。

在每个问题中，小B指定两个数 l 和 r，小A回答 S[l~r] 中有奇数个1还是偶数个1。

机智的小B发现小A有可能在撒谎。

例如，小A曾经回答过 S[1~3] 中有奇数个1， S[4~6] 中有偶数个1，现在又回答 S[1~6] 中有偶数个1，显然这是自相矛盾的。

请你帮助小B检查这M个答案，并指出在至少多少个回答之后可以确定小A一定在撒谎。

即求出一个最小的k，使得01序列S满足第1~k个回答，但不满足第1~k+1个回答。

 

解：

1，n的范围在1e9，但是m的范围在1e4，m次输入每次最多两个数，所以数据大概在2e4,需要离散化一下，将不同数据映射进去；

2，使用前缀和 和 并查集处理问题

计算l和r范围内1的数有奇数个还是偶数个，即为计算sum【r】-sum[l-1];，具体的题中不用进行计算...

并查集即为前缀和中每个元素的奇偶性（奇数-奇数=偶数，偶数-偶数=偶数，奇偶性不同时，会出现差值为奇数的情况）

所有前缀和元素会合并到一个祖先之中，d[x]维护x与根节点奇偶性是否相同

 如果两个元素已经合并在同一个祖先下，那么就可以根据他们与祖先的奇偶性异同，得到他们的异同，判断他们与输入的异同是否一致 如果不一致就是发生矛盾，输出答案...

%2!=&1

异或是相同为0，不同为1，奇数末尾&1=0，偶数末尾&1=1；

奇数%2=1，偶数%2=0...

代码：

#include<bits/stdc++.h>
const int maxn=1e6+10;
typedef long long ll;
using namespace std;

ll n;
int m;

int fa[maxn],d[maxn];
int cnt=0;
unordered_map<int ,int> mp;

int get(int x)//离散化
{
    if(mp.count(x)==0) mp[x]=++cnt;
    return mp[x];
}

void init()
{
    for(int i=1; i<=maxn-10; i++) 
     fa[i]=i;
}

int find(int x)
{
    if(x!=fa[x])
    {
        int root=find(fa[x]);
        d[x]+=d[fa[x]]%2;//判断奇偶
        fa[x]=root;
    }
    return fa[x];
}

int main()
{
    cin>>n>>m;
    int ans=m;
    init();
    for(int i=1; i<=m; i++)
    {
        int x,y;
        string  s;
        cin>>x>>y>>s;
        x=get(x-1),y=get(y);
        int fx=find(x),fy=find(y);
        if(fx==fy)
        {
            if(s=="even")
            {
                //奇偶性相同
                if((d[x]+d[y])%2!=0)//奇数，有矛盾
                {
                    ans=i-1;
                    break;
                }
            }
            else if(s=="odd")
            {//奇偶性不同
                if((d[x]+d[y])%2!=1)//偶数，有矛盾
                {
                    ans=i-1;
                    break;
                }
            }
        }
        else
        {//合并
            fa[fx]=fy;//0，1区分奇偶
            int add=0;
            if(s=="odd") add=1;
            d[fx]=(d[x]+d[y]+add)%2;
        }
        
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
}

 acwing164可达性统计（bitset使用+拓扑排序）

题意：统计一个点能到多少个点，输出

解：

首先用拓扑排序对点进行排序，再使用bitset进行位运算压缩，求并集。

bitset的使用：

类似于bool，但是它的每个位置只占1bit（特别小）

bitset的原理大概是将很多数压成一个，从而节省空间和时间

一般来说bitset会让你的算法复杂度 /32

定义bitset<maxn> bit;

bitset支持所有的位运算；

对于一个叫做bit的bitset：
bit.size() 返回大小（位数）
bit.count() 返回1的个数
bit.any() 返回是否有1
bit.none() 返回是否没有1
bit.set() 全都变成1
bit.set(p) 将第p + 1位变成1（bitset是从第0位开始的！）
bit.set(p, x) 将第p + 1位变成x
bit.reset() 全都变成0
bit.reset(p) 将第p + 1位变成0
bit.flip() 全都取反
bit.flip(p) 将第p + 1位取反
bit.to_ulong() 返回它转换为unsigned long的结果，如果超出范围则报错
bit.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错
bit.to_string() 返回它转换为string的结果

 

此题用到bit.count(),bit.reset(),当然此题的bit是一个数组；

代码：

#include<bits/stdc++.h>
const int maxn=3e4+10;
typedef long long ll;
using namespace std;

vector<int> G[maxn];
vector<int> Tup;
bitset<maxn> F[maxn];
int in[maxn];
int n, m;

void Tupo()
{
    queue<int> que;
    for (int i = 1;i <= n;i++)
    {
        if (in[i] == 0)
            que.push(i);
    }
    while (!que.empty())
    {
        int node = que.front();
        que.pop();
        Tup.push_back(node);
        for (int i = 0;i < G[node].size();i++)
        {
            int to = G[node][i];
            if (--in[to] == 0)
                que.push(to);
        }
    }
}


void Solve()
{
    for (int i = n-1;i >= 0;i--)
    {
        int x = Tup[i];
        F[x].reset();
        F[x][x] = 1;
        for (int k = 0;k < G[x].size();k++)
        {
            F[x] |= F[G[x][k]];
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 1;i <= m;i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        in[v]++;
    }
    Tupo();
    Solve();
    for (int i = 1;i <= n;i++)
        printf("%d\n", (int)F[i].count());

    return 0;
}