关于 THUSC2022 C 的一些奇怪想法

· · 个人记录

首先有一个很显然的第一个点做法，只对有宝藏的点全部为入边，其他至少有一条出边。

然后这个是显然的，可以选出一棵生成树来将宝藏节点作为根然后这些边全部方向连向父亲，其他与宝藏节点的连边也变成连向宝藏节点。

因此可以唯一确定宝藏节点。

然后我们随机选点，（假设获得 4 分），n=10^6 不成立的概率大概是：

\dfrac{999999\times\dots\times (1000000-5000)}{1000000^{5000}}=0.000003640491548

然后我就照着这个写了，然后我挂了。

感觉要被区分了，有老哥能帮帮调错吗/kk

#include "treasure.h"
#include<bits/stdc++.h>
using namespace std;
void Alice(const int testid,const int n,const int m,const int x,const int u[],const int v[],bool dir[]){
    vector<int> g[1000009];
    bool in[1000009],vst[1000009];queue<int> q;
    for(int i=0;i<m;i++) dir[i]=-1;
    for(int i=0;i<m;i++) g[u[i]].push_back(i),g[v[i]].push_back(i);
    in[x]=1,q.push(x);
    while(!q.empty()){
        int p=q.front();q.pop(),in[p]=0;
        vst[p]=1;
        for(int i=0;i<g[p].size();i++){
            if(p==v[g[p][i]]){
                dir[g[p][i]]=0;
                if(!in[u[g[p][i]]]&&!vst[u[g[p][i]]]) q.push(u[g[p][i]]),in[u[g[p][i]]]=1;
            }
            else{
                dir[g[p][i]]=1;
                if(!in[v[g[p][i]]]&&!vst[v[g[p][i]]]) q.push(v[g[p][i]]),in[v[g[p][i]]]=1;
            }
        }
    }
}
int Bob(const int testid,const int n){
    vector<pair<int,bool>> q;bool flag;
    bool vst[1000009];
    for(int i=0;i<n;i++){
        flag=1;int u=((rand()<<15)+rand())%n;
        while(vst[u]) u=((rand()<<15)+rand())%n;
        vst[u]=1;
        q=discover(u);
        for(int j=0;j<q.size();j++){if(q[j].second!=1){flag=0;break;}}
        if(flag) return u;
    }
}

噔 噔 咚

挂了。柿子不对。

上面的东西就不删了，留个纪念。