Gym入口

Preface

和小木虫一起vp的，赛后补了队友独立写出来的题以及赛时尝试开的两道金牌题。题解顺序： M-J-D-H-G-F-B

M. V-Diagram

签到题，题意大概是给定一个V型数组，取一个最大平均值的子V型数组。
赛时WA了两次后才得到了正确思路。
首先，V型数组至少有3个元素，而且要求是子数组，那么可以去掉的只有两端不与极小值直接相邻的部分。
可以考虑贪心，如果我们要去掉一端的一部分，那么去掉那端全部不与极小值相邻的元素一定是最优的。(因为我们去掉一端时，是先去掉大的再去掉小的，那么要去掉一定是全部去掉)
而贪心一个一个去是不可取的，因为可能去掉一个元素会让平均值减小，但是去掉那一整段又可以让平均值变大。
而去掉两端一定是劣的(这样把较大的值全全去掉了)
故答案为不去，去掉左端可以去掉的部分，去掉右端可以去掉的部分三者平均值中取最大值。
code:

void solve()
{
    int n;
    cin >> n;
    vector<ll>a(n);
    deque<ll>d;
    ll sum = 0;
    int p = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
 
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i - 1]) {
            p = i - 1;
            break;
        }
    }
 
    ll pre = 0, suf = 0;
    int pcnt = 0, scnt = 0;
    for (int i = 0; i < p - 1; i++) {
        pre += a[i];
        pcnt++;
    }
    for (int i = p + 2; i < n; i++) {
        suf += a[i];
        scnt++;
    }

    double ans = sum / (double)(n);
    ans = max(ans, (sum - pre) / (double)(n - pcnt));
    ans = max(ans, (sum - suf) / (double)(n - scnt));
    printf("%.14llf\n", ans);
    return;
 
}

J. Mysterious Tree

交互题
题意：给一颗树,是链或者是菊花。使用\(\left\lceil\frac{n}{2}\right\rceil + 3\)次询问是否存在一条边\(\{u,v\}\)来确定。交互是自适应的。
无论是链还是菊花，都只有\(n-1\)条边，是稀疏图,而问不出一条存在的边，我们便完全无法确定图的类型。所以考虑如何在有限的询问次数中去问出特定类型图的其中一条边。
如果是链，那么是无法通过某种特定的询问序列去问出某条存在的边的。(也就是说，对任何询问序列(询问是不能自适应的，因为问出一条边存在前，得到的都是不存在的返回)，都可以构造出一条链不被问到任意一条边)。
而如果是一颗菊花，我们考虑询问\(\{v_1,v_2\},\{v_3,v_4\}...\)而遍历到每一个顶点。如果这棵树是一颗菊花，那么它存在一个顶点与其他所有顶点之间有边。当询问到这个顶点时，就可以问出一条边。这样一个询问序列，最多消耗\(\left\lceil\frac{n}{2}\right\rceil\)次询问。
问出一条边\(\{u,v\}\)后，我们仍需用剩下3次询问去确定这到底是链还是菊花。如果是菊花，取其他顶点\(w\),分别询问\(u,v\)是否与\(w\)有边。
1. 均没有边，那么是一条链。
2. 其一有边，不妨设是\(\{u,w\}\)，这时菊花和链还是均有可能。那我们再用最后一次机会询问\(u\)和其他顶点是否有边。
2.1. 如果无边，那么不可能是菊花，是链
2.2. 如果有边，一定是菊花。

code:

int T,n,res;
mt19937 rnd(time(0));
void work(int x,int y){
	int z=rnd()%n+1;
	while(z==x||z==y)
		z=rnd()%n+1;
	cout<<"? "<<x<<" "<<z<<endl;
	cin>>res;
	if(!res)swap(x,y);
	cout<<"? "<<x<<" "<<z<<endl;
	cin>>res;
	if(!res){
		cout<<"! 1"<<endl;
		return;
	}
	int o=rnd()%n+1;
	while(o==x||o==y||o==z)
		o=rnd()%n+1;
	cout<<"? "<<x<<" "<<o<<endl;
	cin>>res;
	if(res)cout<<"! 2"<<endl;
	else cout<<"! 1"<<endl;
}
void solve(){
	cin>>n;
	if(n%2==0){
		for(int i=1;i<=n;i+=2){
			cout<<"? "<<i<<" "<<i+1<<endl;
			cin>>res;
			if(res){
				work(i,i+1);
				return;
			}
		}
	}else{
		for(int i=1;i<n;i+=2){
			cout<<"? "<<i<<" "<<i+1<<endl;
			cin>>res;
			if(res){
				work(i,i+1);
				return;
			}
		}
		cout<<"? "<<n<<" "<<n-1<<endl;
		cin>>res;
		if(res){
			work(n,n-1);
			return;
		}
	}
	cout<<"! 1"<<endl;
}

D. Operator Precedence

妙妙构建题加上智慧的样例
(vp的时候真红温了)
实际上完全不用管样例，为了让乘式的值尽可能小，不妨将中间全部控制为1，只留最后一部分为变量，解二元一次方程(控制解为整数)即可构造出合法序列。
最后构造出的序列是形如\(-1,2,-1,2,...,n-2,1\)的数列。
code:

void solve()
{
    int n;
    cin >> n;
    if (n == 2) {
        cout << "1 -3 -3 1" << endl;
    }
    else {
        for (int i = 0; i < n - 1; i++) {
            cout << "-1 2 ";
        }
        cout<<n-2<<" 1 "<<endl;
    }
    return;
}

H. Sugar Sweet II

节点之间的依赖关系组成一颗外向基环树(或森林)(关于外向树，内向树和基环树可以了解一下)。外向基环树节点的k级祖先是确定的。
对于节点\(v\)，如果\(a_v < b_v\)那么这个节点一定可以获得加成，如果\(a_v >= b_v + w_v\),那么一定不能获得加成，如果介于中间，则可否获得加成取决于节点选取的顺序。我们可以先预处理一遍所有节点，把一定可以获得加成的节点概率\(p_v\)设成1，一定不能获得加成的节点概率设成0。这些节点均为已确定的节点。
对于中间状态的节点，我们推导它获得加成的概率。
每个中间节点的状态，取决于其父节点的状态，往前递推，取决于其一系列祖先节点的状态。而想要获得加成，只能是其父节点\(f_1\)已获得加成后，再选择该节点。由数学归纳法，如果其最小的确定状态祖先为k级祖先(存在环上的例外情况)，那么\(f_1,f_2,...f_{k-1}\)都获得加成，该节点才能获得加成。若\(p_{f_k} = 0\),这些情况都不可能发生，即\(p_{f_0} = p_{f_1} = ... = p_{f_{k-1}} = 0\)。若\(p_{f_k} = 1\),则满足条件的事件发生顺序只有\(\{f_{k-1},f_{k-2},...,f_1,f_0\}\),由排列数的公式，得到\(p_{f_0} = \frac{1}{A_k^k} = \frac{1}{k!}\).此外，有一种特殊情况，即某个圈中没有任何已确定节点，那么由于任何节点被选取后其父节点仍处于加成状态，其概率应为0，从而这个环内所有点概率均为0。
实现上，我们从所有已确定的点处执行一遍dfs，dfs遇到已确定的点就返回，否则按照规则计算该点处的概率。剩下的未访问的点即为特殊情况中的点，将其概率设为0即可。
关于计算k的阶乘倒数的算法，或许我的计算方法有可以优化的地方。
code:

void dfs(vector<vector<int>>&g, vector<ll>& p, int s, ll t)
{
    if (p[s] == -1) {
        return;
    }
    else {
        for (auto j : g[s]) {
            if (p[j] == -1) {
                p[j] = inv(t) % mod * p[s] % mod;
                dfs(g, p, j, t + 1);
            }
        }
    }
    return;
}

void solve()
{
    int n;
    cin >> n;
    vector<ll>a(n + 1), b(n + 1), w(n + 1);
    vector<vector<int>>g(n + 1);
    vector<ll>p(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        g[b[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    
    for (int i = 1; i <= n; i++) {
        if (a[i] < a[b[i]]) {
            p[i] = 1;
        }
        if (a[i] >= a[b[i]] + w[b[i]]) {
            p[i] = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        dfs(g, p, i, 2);
    }

    for (int i = 1; i <= n; i++) {
        if (p[i] == -1)
            p[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        ll ans = (a[i] + (w[i] * p[i] % mod)) % mod;
        cout << ans << " ";
    }
    cout << endl;
    return;
}

G. Snake Move

贪吃蛇，给出初始的蛇头蛇身位置和地图状态，每步操作可以上/下/左/右移动一格或者缩短蛇身一格。询问到达所有位置的最小步数，以平方和的形式输出。
如果不是蛇身节点，那么最小步数就是蛇头到这个点的操作距离(这可能不等于路径距离)，如果是从蛇尾数起的第k个节点(蛇尾是第一个)，那么最小步数是操作距离和len-k取min.
可以做到\(O(mn)\)，具体实现是使用bfs。使用一个二维数组来模拟队列。
code:

const int N=1e7+4;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,m,k,f[3004][3004];
char c[3004][3004];int v[3004][3004];
int a[100004],b[100004];
int ans[3004][3004];
vector<pair<int,int> >V[N];
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++)
		scanf("%d%d",&a[i],&b[i]),v[a[i]][b[i]]=i;
	for(int i=1;i<=n;i++){
		scanf("%s",c[i]+1);
		for(int j=1;j<=m;j++)if(c[i][j]=='#')
			v[i][j]=-1;
	}
	memset(ans,0x3f,sizeof(ans));
	ans[a[1]][b[1]]=0;
	V[0].emplace_back(a[1],b[1]);
	unsigned long long ret=0;
	for(int i=0;i<N;i++){
		for(auto[p,q]:V[i])if(ans[p][q]==i){
			ret+=(unsigned long long)i*i;
			for(int d=0;d<4;d++){
				int P=p+dx[d],Q=q+dy[d];
				if(!P||!Q||P>n||Q>m||v[P][Q]<0)continue;
				int D=i+1;
				if(v[P][Q]>0&&k-v[P][Q]>=D)D=k-v[P][Q]+1;
				if(D<ans[P][Q])
					ans[P][Q]=D,V[D].emplace_back(P,Q);
			}
		}
	}
	cout<<ret;
}

F. Top Cluster

大概题意：给一个带边权(路径长)和点权的树，保证点权两两不同。多次询问一个节点\(v\)的k-邻域内所有点权集合的mex。需要做到每次询问在\(\log n\)的时间内解决才不会tle。
大概是第一次做这种糅合了一些树上算法知识的题。
需要的算法： Euler序求LCA，二分，树的直径及其性质。

分析：
求出k邻域内的点集显然是\(O(n)\)的，如果我们暴力求解k-邻域内的点，再求解mex显然是不行的。
计算两点间的距离是可以做到\(O(n\log n)\)预处理\(O(1)\)查询的，使用的是通过Euler序将求解LCA转化成求解RMQ。而我们求解某个点\(v\)的k-邻域mex，即是找出一个具有如下性质的边界值\(r\)：
1. 点权小于\(r\)的点均存在，且全部位于\(v\)的k-邻域内。
2. 点权为\(r\)的点不存在，或者位于\(v\)的k-邻域外。

接着推进上面所述思路的可行性。
我们可以观察到边界值\(r\)是满足二分答案的条件的：对于小于\(r\)的值均满足第一条性质，大于r的值均不满足第一条性质。所以我们如果能够在\(O(1)\)时间内进行一次判断，就可以使用二分法将单次询问的时间复杂度降到\(O(\log n)\)。
如何判断一个点集内的点是否全在k-邻域内呢？首先，因为使用二分法，我们会按点权排序。所以我们check的点集是固定的，即按点权排序后的前缀和。所以点集我们可以预先处理出来。
判断树上点集是否在范围内，可以转化为求点集内的点到给定点的最大距离。所以我们求解这些点集的直径，而树上任意点到这些点集内的点的最大距离一定等于到直径端点的最大距离。所以我们从check一个点集内的所有点变成判check直径的端点。求解前缀和集合的直径可以\(O(n)\)解决。
于是，我们得出了这个\(O(n\log n)\)的解法。
code:

vector<int>w;
unordered_map<int, int>idx;
vector<vector<pair<int, ll>>>g;
vector<int>dfn;
vector<int>dval;
vector<int>elr;
vector<int>eidx;
vector<ll>dis;
vector<vector<int>>lca;
vector<pair<int, int>>dia;
int dfncnt = 0;

void get_elr(int r,int fa)
{
    if (dfn[r] != 0)
        return;
    else {
        dfn[r] = dfncnt++;
        dval[dfn[r]] = r;
        elr.push_back(dfn[r]);
        eidx[r] = elr.size() - 1;
        for (auto [p, d] : g[r]) {
            if (p != fa) {
                dis[p] = dis[r] + d;
                get_elr(p, r);
                elr.push_back(dfn[r]);
            }
        }
    }
    return;
}

int Lca(int u, int v)
{
    int iu = eidx[u], iv = eidx[v];
    if (iu > iv)
        swap(iu, iv);
    int len = iv - iu + 1;
    int k = floor(log2(len));
    int index = min(lca[iu][k], lca[iv - (1 << k) + 1][k]);
    return dval[index];
}

ll dist(int u, int v)
{
    return dis[u] + dis[v] - 2 * dis[Lca(u, v)];
}

void merge(pair<int, int>& a, pair<int, int>&other)
{
    pair<int, int>res = other;
    ll len = dist(other.first, other.second);
    ll len1 = dist(a.first, other.first), len2 = dist(a.first, other.second);
    if (len1 > len) {
        res = { a.first,other.first };
        len = len1;
    }
    if (len2 > len) {
        res = { a.first,other.second };
        len = len2;
    }
    a = res;
    return;
}

void solve()
{
    int n, q;
    cin >> n >> q;
    const int inf = 1e9;
    int len = floor(log2(n * 2 - 1));
    w.resize(n);
    dfn.resize(n);
    dval.resize(n+1);
    eidx.resize(n);
    //elr.resize(n * 2 + 1);
    g.resize(n);
    dis.resize(n);
    lca.resize(n * 2 - 1, vector<int>(len + 1, inf));
    for (int i = 0; i < n; i++) {
        cin >> w[i];
        idx[w[i]] = i;
    }
    //auto a = w;
    sort(w.begin(), w.end());
    for (int i = 1; i < n; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        u--;
        v--;
        g[u].push_back({ v,d });
        g[v].push_back({ u,d });
    }
    get_elr(0, 0);
    int elrlen = 2 * n - 1;
    
    for (int i = 0; i < elrlen; i++) {
        lca[i][0] = elr[i];
    }
    for (int i = 1; i <= len; i++) {
        for (int j = 0; j + (1 << i) - 1 < elrlen; j++) {
            lca[j][i] = min(lca[j][i - 1], lca[j + (1 << (i - 1))][i - 1]);
        }
    }

    //sort as w
    dia.resize(n);
    for (int i = 0; i < n; i++) {
        dia[i] = { idx[w[i]],idx[w[i]] };
    }

    for (int i = 1; i < n; i++) {
        merge(dia[i], dia[i - 1]);
    }

    int rlim = n;
    for (int i = 0; i < n; i++) {
        if (w[i] != i) {
            rlim = i;
            break;
        }
    }
    
    while (q--) {
        ll x, k;
        cin >> x >> k;
        x--;
        int l = -1, r = rlim;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            int midi = lower_bound(w.begin(), w.end(), mid) - w.begin();
            ll d = max(dist(x, dia[midi].first), dist(x, dia[midi].second));
            if (d <= k) {
                l = mid;
            }
            else {
                r = mid;
            }
        }
        cout << r << endl;
    }
    return;
}

B. Festival Decorating

这题有着蜜汁check，考虑误差范围好像可以用多项式科技解决(但是我不会QWQ)。不过学习了这题利用bitset精确求解的解法。bitset,太强大！
由于答案的优先级是下标(并非位置)较小的优先，我们可以按下标顺序枚举该点可以贡献的答案，已有答案的距离不再枚举。可行的枚举位置需要两步操作得出：
1. 去除同颜色的灯
2. 去除已获得答案的距离对应位置的灯

剩余有灯的位置均为可贡献答案的位置。
这显然是一个\(O(n^2)\)的做法，其中我们枚举出来可以贡献答案的位置以及记录答案操作有\(n\)的数量级，但是找到这些位置的操作数是\(n^2\)级别的。这时我们就可以利用我们的bitset,降低没有关联其他操作的常数，达到\(O(\frac{n^2}{\omega})\)的时间复杂度。
具体做法：
我们用一个二维vector存不同颜色的点，用bitset \(mp\)存数轴的状态(有灯为1，无灯为0),并且再用一个bitset \(getans\)存以及获得了答案的距离的状态(未获得答案为0).
对于操作1，这是关联了遍历某个特定颜色点集的操作，bitset无法降低时间复杂度。但是我们可以使用Big Small(根号分治)来降低时间复杂度。对于出现次数大于\(\sqrt N\)的颜色，我们预处理出初始序列取出掉这些点得到的序列，时间复杂度为\(O(N)\)，但是这种操作不会大于\(\sqrt N\)次。对于出现次数小于\(\sqrt N\)的颜色，我们每次遇到时再执行操作1即可，每次执行的时间复杂度不超过\(O(\sqrt N)\),最多操作\(n\)次。通过根号分治，我们将操作1的总时间复杂度降到\(O(n\sqrt N)\)级别。
对于操作2，这是只使用了bitset的操作，时间复杂度被bitset优化。我们获取目前考虑的点的位置\(x\)，可枚举的位置用bitset表示即为\(mp >>x \& \sim getans\)。这部分的时间复杂度为\(O(\frac{n^2}{\omega})\)
做完预处理操作后，遍历bitset，找到为1的位置填入答案即可。G++里bitset有_Find_first()和pos._Find_next(p)函数，比较好写。为什么MSVC没有这些函数 :(
把对应两种操作的算法组合起来，即可得到使用bitset的正解。
code:

void solve()
{
    const int N = 250001;
    const int sq = sqrt(N);
    int n, q;
    cin >> n >> q;
    vector<int>a(n);
    vector<int>cl(n);
    //vector<int>mp(N);
    vector<int>ans(N);
    vector<vector<int>>g(N);
    bitset<N>s;
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        a[i] = x;
        cl[i] = c;
        //mp[x] = c;
        s[x] = true;
        g[c].push_back(x);
    }
    vector<bitset<N>>msk;
    vector<int>idx(N,-1);
    for(int i =1;i<=N;i++){
        if(g[i].size() >= sq){
            bitset<N>st;
            for(auto j:g[i])
                st.set(j);
            idx[i] = msk.size();
            msk.push_back(s&(~st));
        }
    }
    bitset<N>getans;
    for(int i =0;i<n;i++){
        bitset<N>pos;
        if(idx[cl[i]] == -1){
            pos = s;
            for(auto j:g[cl[i]])
                pos[j] = 0;
        }else{
            pos = msk[idx[cl[i]]];
        }
        pos >>= a[i];
        pos &= ~getans;
        for(int p = pos._Find_first();p != pos.size();p = pos._Find_next(p) ){
            ans[p] = i + 1;
            getans.set(p);
        }
    }

    while(q--){
        int d;
        cin>>d;
        cout<<ans[d]<<endl;
    }
    return;
}

(ps: 难产了两周的补题题解终于生出来了)