寒假训练营1

E dfs

被骗了，名字叫贪心，实际上是dfs。

注意到比赛场数只有10场，每场只有3种结果，爆搜复杂度也只有3^10，果断dfs。教训是数据小到能爆搜，就直接爆搜。

    if(x==m+1){//比完了
        int p0=p[0];
        sort(p.begin(),p.end(),cmp);
//        rep(i,0,p.size()-1)cout<<p[i]<<' ';
//        cout<<'\n';
        rep(i,0,p.size()-1){//计算排名
            if(p[i]==p0){
                ans=min(ans,i+1);
                return;
            }
        }
    }
    vector<int>q;
    q=p;
    int uu=u[x]-1,vv=v[x]-1;
    q[uu]+=3;//第一个人赢
    dfs(x+1,q);
    q=p;
    q[vv]+=3;//第二个人赢
    dfs(x+1,q);
    q=p;
    q[vv]++;//平局
    q[uu]++;
    dfs(x+1,q);
}
void solve(void){ 
    cin>>n>>m;
    vector<int>a;
    rep(i,1,n){
        int t;
        cin>>t;
        a.push_back(t);
    }
    rep(i,1,m){
        cin>>u[i]>>v[i];
    }
   ans=1e9; 
   dfs(1,a);
   cout<<ans<<'\n'; 
}

F 第二类斯特林数

m个数按位或结果是2^n-1，意味着右边前n位都至少有一个数该位为一。

任意两个数按位与等于0，意味着任意两个数都没有任意一位相同。那么右侧前n位每一位有且只有一个数该位为1，接下来就是这n个1在m个数里如何排列的问题了。

m个数是升序的，那么就只有升序排列一种排列方式。

m个数都不为0，意味着每个数至少有一个数位为1。

综上可以抽象成n个有区别的球（n个不同数位上的1），放到m个无区别的盒子里（m个数，由于只有一种排列，可以是求组合数，也就是无区别的），并且每个盒子都非空（每个数都不为0），这就是第二类斯特林数的定义。

具体就求法是1/(m!)* sigma((-1)^k * (m-k)^n * C(m,k))，(m-k)^n * C(m,k)表示选k个盒子空着，球随意装进剩余盒子中，（-1）^k表示用容斥选算出所有盒子非空的方案数，1/m!表示只算组合数

需要注意的是阶乘可以先预处理出来。

一个坑点是m可能比n大，那么一定有盒子是空的，但又要求所有数不为0，也就是所有盒子非空，那么此时方案数为0

{
    int ret = 1;
    while (n)
    {
        if (n & 1) ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ret;
}
ll inv(ll x){
	return power(x, mod-2);
} 
void init(int N)//预处理阶乘和阶乘逆元的表
{
 
    fac[0] = 1;//预处理阶乘和阶乘的逆元
    for (int i = 1; i <= N; i++)
    {
        fac[i] = fac[i - 1] * i%mod;
    }
    ifac[N] = inv(fac[N]);//费马小定理
    for (int i=N - 1; i >= 0; i--)
    {
        ifac[i] = ifac[i + 1] * (i + 1)%mod;
    }
}
ll C(int m, int k)
{
    if (k < 0 || k >m  || m < 0) {//特判
        return 0;
    }
    return fac[m] * ifac[m - k] % mod * ifac[k] % mod;
}
void solve(void){ 
	int n,m;
    cin>>n>>m;
    init(m);
    ll ans=0;
    rep(k,0,m){
		if(k%2==0){
			ans=(ans+C(m,k)*power(m-k,n)%mod)%mod;
		} 
		else {
			ans=(ans-C(m,k)*power(m-k,n)%mod+mod)%mod;
		}
//        cout<<C(m,k)<<' '<<power(m-k,n)<<' '<<ans<<'\n';
    }
	cout<<ans*ifac[m]%mod;
}

H.数位操作

看似是背包，实际上是到数学。看不出来规律就先试几个例子，可以发现对于最大容量k，如果我们选其中一位1的位置i，那么所有cost的i位为0，更高位为k的子集，更低位随意的物品都能选，因为cost之间执行的操作是按位或，i的更高位都是k的子集，按位或之后也是k的子集，更低位虽然可能全为1，但是第i为为0了，更低位全为1也是小于k的，那么满足上述条件的cost全或起来也不会超过k。

那么我们可以枚举k为1的位置i，然后计算出每一个位置的最大value，再取最大值就是答案。

虽然思路有了，但是实现其实也不简单，遍历cost所有位判断这个物品能不能选，其实很容易出错。一个简单的做法是先构造一个i位为0，高位与k相同，低位全是1的数，然后依次判断cost是否是它的子集，如果是则该物品能选。

ll get(int x){
	ll ret=0;
	rep(i,1,n)
		if((x&w[i])==w[i])//如果是子集
        	ret+=v[i];//选上
	return ret;
}
void solve(void){ 
    cin>>n>>m;
    int t=m;
    rep(i,1,n)cin>>v[i]>>w[i];
    ll ans=get(m);//初始值
    rep(i,0,30)
    	if((m>>i)&1){
    		int k=((t>>(i+1))<<(i+1))|((1<<i)-1);//构造用于判断的数
			ans=max(get(k),ans);
		}
	cout<<ans<<'\n';
}

I.统计推断

没想到还会考这种题。其实题干不太严谨，统计推断只能得出最有可能的结果，而不能求出一个100%确定的结果，因此应该问“这组数据更可能是谁生成的”，而不是“这组数据是谁生成的”

显然第一种方法x,y是均匀的，但第二种方法，当x,y靠近边界时，更有可能被舍掉，因此越靠近边界密度越低。因此可以统计一下落在某个区间里的点数，如果和均匀分布的期望相差超过一定值，就可以判定是第二种，否则是第一种。

    int n,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y,r;
        cin>>x>>y>>r;
        if(abs(x)<=70&&abs(y)<=70)cnt++;//统计落在边长140的正方形内点数
    }
    int ans=(70.0*70)/(100*100)*1e5;//均匀分布下，落在该区域内的点数的期望
    if(abs(ans-cnt)>2000)cout<<"buaa-noob";//差的太多了则否定假设
    else cout<<"bit-noob";
}

K.基环树

看到关系，就应该想到建图，因为边可以表示关系。第i题的题干是：第ai题的答案是_。这实际上是在说i题和ai题的答案只要确定一个，另一个也就确定了，这就是一种关系，我们可以依此建图。

注意到每个题都只能决定一道其它题，也就是说把题看成点，所有点出度都为1，那么这张图一共n个点，n条边，实际上是一棵树再加了一条边，形成了一个环，也就是一颗基环树。

实际上只有位于环上的题的答案才是自由的，可枚举的，因为确定了环上答案后，链上答案都可以倒退唯一确定。因此对于一颗基环树，我们只需要枚举并检验环上有几种可行的答案，然后再把不同树的答案乘起来就是总方案数。

接下来就是具体实现，枚举并检验环上的答案，可以任选一点，枚举它的选项，对每一个选项，顺着往后推，直到再回到起点，看此时推出来的起点答案和枚举的答案是否相同，如果相同，这就是一个合法答案。

另一个问题是怎么找到环上一点。一种简单的方法是用并查集，因为环一定位于每个连通块的末端，那么只要每次合并并查集时都把后一个点的祖先作为祖先，最终整个连通块的祖先一定是环上一点。