Week1训练赛

· · 个人记录

A：Even Degrees

Sol： 很好的构造题。构造首先要找到规律，及一种有序的构造方案。有向图一条边对应一个出度，总出度等于总边数。若边数不是偶数，则不存在构造方案。其次，如何理解有序的构造方案。首先在一个有向图中bfs是有序的，但是存在遍历到重复点的情况，说明遍历方式还不够有序。如果我们删掉有向图的几条边，让它成为一棵树，再遍历这棵树，是不是更加有序？那么有向图中的非树边我们不妨随意定向，只需要调整非树边的方向。为什么可以随意定向？因为对于一个节点的出度+1或-1并不会改变它的奇偶性，所以是否存在方案，完全取决于树边的定向。一开始我们可以统一树边的方向，后面根据节点出度奇偶性进行调整。在调整过程中我们要思考，如何保证调整当前树边的时候会不会影响之前已经调整过的树边。将问题分解，如果一上来从父节点到子节点的顺序入手会比较复杂，因为父节点可能存在多条边连向子节点。若先调整子节点，再调整父节点，则已经调整过的子节点不再受父节点往上的祖宗节点影响，所以在树上递归，通过回溯调整树边，是一个可行的方案。当除根节点以外的其它结点出度均为偶数，且总边数为偶数时，则根节点出度也为偶数。

C：Tree and Constraints

Sol： 读题。看到“至少一个”这样类似的限制词，第一感觉是很复杂。正难则反。若得到给出的限制路径上全涂白色的方案数，我们可以通过容斥原理得到最终答案。找规律可以找到，最后得到存在限制不满足的情况是1个不满足-2个不满足+3个不满足……依次类推。这只是初步的计算方法。目前的算法是让我们找到对于上述各种情况（1到M个限制不满足）所有限制边并集的大小x，此时的方案数是2的n-1-x次方，因为其它边可以任意涂色。那我们如何得到这个x呢，通过搜索遍历肯定是不合理的，因为情况数太多。有一个计算路径的方案是通过LCA（此处不讲），还有一个方案是状压dp。观察到数据范围n在50以内，所以很容易想到。而且边只有黑白两色，对应二进制01。此处我们用到一个函数叫做__builtin_popcountll，它可以统计一个数在二进制状态下1的个数。对于每一个限制条件，我们也可以用01表示满足还是不满足，最后通过位运算得到，满足第几个条件。

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=60,M=30;
vector<int>g[N];
int n,m,status[M],son[N];
//树的遍历 
void dfs(int now,int fa)
{
    for(int i=0;i<g[now].size();i++)
    {
        int to=g[now][i];
        if(to==fa)continue;
        //son[x]存的是当前节点到根节点的路径
        //根节点到任意一个节点必经过该节点的父节点
        //所以可以通过父节点计算子节点的路径 
        son[to]=son[now]|(1ll<<(to-1));
        dfs(to,now);
    }
    return;
}
//求解方案数 
int f(int S)
{
    int cur=0,cnt=__builtin_popcountll(S); 
    //通过或运算得到经过的路径的并集 
    for(int i=1;i<=m;i++)if(S&(1ll<<(i-1)))cur|=status[i];
    int res=1ll<<(n-1-__builtin_popcountll(cur));
    //容斥原理基本原理（奇加偶减） 
    if(cnt%2==0)res=-1ll*res;
    return res;
}
signed main()
{
    cin>>n;
    int ans=0;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    cin>>m; 
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        //通过异或运算去除根节点到两个节点的公共部分
        //剩余部分即为u到v经过的节点 
        //status[i]表示每个限制条件对应的路径 
        status[i]=son[u]^son[v];
    }
    for(int S=1;S<=(1<<m)-1;S++)ans+=f(S);
    cout<<((1ll<<(n-1))-ans);
    return 0; 
}

D：Yet Another Path Counting

Sol： 本题基本思路其实很好想。一种是组合数计数，找到两个颜色相同的，计算dx和dy（行、列之差），路径数即为C（dx+dy，dx）。另外一种方案是通过递推，因为只能向右或向下走，对于同一种颜色，f[i][j]+=f[i-1][j]+f[i][j-1]是显而意见的，因为可以操作0次，所以f[i][j]初始为1。但是二者任意取一都通过不了此题。当所有标签全不相同，第二种方案复杂度可达到O（n^4）。同样的，当所有标签全部相同，第一种方案复杂度可达到O（n^4）。假设有B种颜色，第一种方案最坏复杂度为 O（n^4/B），第二种方案最坏复杂度为O（n^2B）。当B取n时，二者平均复杂度最低。这就是根号分治。对于不同情况分类处理，降低平均时间复杂度。常用于优化暴力。但是本题没完，此处还有一个处理阶乘逆元的小技巧，不需要再每次使用（费马小定理）快速幂求逆，详见链接方式二

E：Range Xor Query

Sol： 仔细观察题目的两种操作方式，一个是单点修改，一个是区间查询。这和树状数组的用途如出一辙。对于异或运算a^b=c，同样也满足c^b=a，只需要将树状数组的模板里的+号换成^即可通过。