2021.8.2 队测题解

显然题目是不公开的，所以只会写出每个题的解法，不会贴链接和题面。

失落的世界

显然有一个二分做法，每次二分一个 $c$ ，从 $1$ 开始跳出 $c$ 的距离，然后看能不能接着跳，不能跳就跳回来，最劣询问次数是 $2\log n$ ，可以拿到 $80$ 分。

考虑优化，我们发现以 $1$ 号点为起点太亏了，考虑确定一个合适的起始点使得一定可以成功地跳到，显然这个是可以倒推过来的，我们可以一开始就确定这个起始点，询问次数为 $\log n$ ，可以拿到 $100$ 分。

#include <bits/stdc++.h>
#include "world.h"
using namespace std;
typedef long long ll;
ll mi[70];
long long Guess(long long n) {
    ll L = 1, R = n - 1;
    int tot = 0;

    while (L <= R) {
        mi[++tot] = (L + R) / 2;
        L = mi[tot] + 1;
    }

    ll P = n;
    int fl = -1;

    for (int i = tot; i >= 1; i--)
        P += mi[i] * fl, fl *= -1;

    L = 1, R = n - 1;
    Query(P);
    fl = (tot & 1) ? 1 : -1;

    while (L <= R) {
        ll mid = (L + R) / 2;
        bool pp = Query(P + mid * fl);
        P += mid * fl;

        if (pp)
            R = mid - 1;
        else
            L = mid + 1;

        fl *= -1;
    }

    return R + 1;
}

谜域的界外

我们发现，每次对坐标的增加是平方级别的，所以在给定的数据范围内，最多只有 $\log$ 级别的碎片个数，所以有用的碎片个数是很少的。

考虑枚举出所有的碎片，显然所选择的碎片一定是一个区间，枚举这个区间，并求一下答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e18;
ll x[1000], y[1000];
ll ax, ay, bx, by, sx, sy, t;
int tot;
int main() {
    cin >> x[0] >> y[0] >> ax >> ay >> bx >> by;
    cin >> sx >> sy >> t;

    for (int i = 1; x[i - 1] <= M / ax && y[i - 1] <= M / ay; i++) {
        x[i] = x[i - 1] * ax + bx;
        y[i] = y[i - 1] * ay + by;
        tot++;
    }

    int ans = 0;

    for (int i = 0; i <= tot; i++) {
        for (int j = i; j >= 0; j--) {
            ll D = abs(sx - x[i]) + abs(sy - y[i]);
            int dx = i - j + 1;

            for (int k = i - 1; k >= j; k--)
                D += abs(x[k + 1] - x[k]) + abs(y[k + 1] - y[k]);

            if (D > t)
                break;

            ans = max(ans, dx);

            if (i == tot)
                continue;

            D += abs(x[i + 1] - x[j]) + abs(y[i + 1] - y[j]);

            if (D > t)
                continue;

            ans = max(ans, ++dx);

            for (int k = i + 2; k <= tot; k++) {
                D += abs(x[k] - x[k - 1]) + abs(y[k] - y[k - 1]);

                if (D > t)
                    break;

                ans = max(ans, ++dx);
            }
        }

        for (int j = i; j <= tot; j++) {
            ll D = abs(sx - x[i]) + abs(sy - y[i]);
            int dx = j - i + 1;

            for (int k = i + 1; k <= j; k++)
                D += abs(x[k] - x[k - 1]) + abs(y[k] - y[k - 1]);

            if (D > t)
                break;

            ans = max(ans, dx);

            if (i == 0)
                continue;

            D += abs(x[i - 1] - x[j]) + abs(y[i - 1] - y[j]);

            if (D > t)
                continue;

            ans = max(ans, ++dx);

            for (int k = i - 2; k >= 0; k--) {
                D += abs(x[k + 1] - x[k]) + abs(y[k + 1] - y[k]);

                if (D > t)
                    break;

                ans = max(ans, ++dx);
            }
        }
    }

    printf("%d\n", ans);
}

聚合的塔尖

新科技：根号分治。

对于 $k$ 的大小分治，如果 $k\ge \sqrt{n}$ ，显然这样的询问不会太多，直接暴力拓扑排序求出所有点的答案，否则的话，我们预处理出对于每个点距离最大的 $\sqrt{n}$ 个点，显然对于每个询问的出发点，距离最大的 $\sqrt{n}$ 个点不会全部被删，暴力做即可。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef pair<int, int> pii;
const int N = 2e5 + 10;
int n, m, q;
vector<int> G[N + 2], UG[N + 2];
vector<pii> mi[N + 2], tmp1, tmp2;
int wn[N + 2], ban[N + 2];
int main() {
    scanf("%d %d %d", &n, &m, &q);
    int T = sqrt(n);

    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d %d", &x, &y);
        G[x].pb(y);
        UG[y].pb(x);
    }

    for (int i = 1; i <= n; i++) {
        for (int j : UG[i]) {
            tmp1.clear();

            for (pii k : mi[j])
                tmp1.pb(mp(k.fi + 1, k.se));

            tmp2.resize(tmp1.size() + mi[i].size());
            merge(tmp1.begin(), tmp1.end(), mi[i].begin(), mi[i].end(), tmp2.begin(), greater<pii>());
            mi[i].clear();

            for (pii k : tmp2)
                if (!wn[k.se]) {
                    mi[i].pb(k);
                    wn[k.se] = 1;

                    if (mi[i].size() >= T)
                        break;
                }

            for (pii k : mi[i])
                wn[k.se] = 0;
        }

        if (mi[i].size() < T)
            mi[i].pb(mp(0, i));
    }

    while (q--) {
        int s, k;
        scanf("%d %d", &s, &k);

        if (k >= T) {
            memset(wn, -1, sizeof wn);
            wn[s] = 0;

            for (int i = s - 1; i >= 1; i--)
                for (int j : G[i])
                    if (wn[j] != -1)
                        wn[i] = max(wn[i], wn[j] + 1);

            for (int i = 1; i <= k; i++) {
                scanf("%d", &ban[i]);
                wn[ban[i]] = -1;
            }

            int ans = -1;

            for (int i = 1; i <= n; i++)
                ans = max(ans, wn[i]);

            printf("%d\n", ans);
            memset(wn, 0, sizeof wn);
        } else {
            for (int i = 1; i <= k; i++) {
                scanf("%d", &ban[i]);
                wn[ban[i]] = 1;
            }

            int ans = -1;

            for (pii i : mi[s])
                if (!wn[i.se]) {
                    ans = i.fi;
                    break;
                }

            printf("%d\n", ans);

            for (int i = 1; i <= k; i++)
                wn[ban[i]] = 0;
        }
    }
}

沉眠的回声

考虑 dp，设 $f_{i,j,k}$ 表示对于在 $i$ 轮，当前问的人能否确定 $(j,k)$ 是不是答案。

转移的话，显然在上两轮知道了，他一定就知道，如果在上两轮只有一个状态不知道，他也一定就知道了，如果在上一轮对手只有一个状态不知道，他也一定知道了。

就用类似这几条暴力转移即可，时间复杂度位置，但跑的好像挺快😀

#include<bits/stdc++.h>
using namespace std;
bool f[20][310][310];
int s,t;
void work1(int turn,int n,int m) {
    int num1=0,f1=0,f2=0;
    int num2=0,f3=0,f4=0;
    int num3=0,f5=0,f6=0;
    int z=n*m;
    for(int i=s;i*i<=z;i++)
        if(z%i==0&&z/i<=300) {
            int j=z/i;
            if(turn==1||!f[turn-1][i][j]) num1++,f1=i,f2=j;
            if(turn>=3&&!f[turn-2][i][j]) num2++,f3=i,f4=j;
            if(f[turn-1][i][j])
            if(turn<=3||!f[turn-3][i][j]) num3++,f5=i,f6=j;
        }
    if(num1==1&&f1==n&&f2==m) f[turn][n][m]=1;
    if(num2==1&&f3==n&&f4==m) f[turn][n][m]=1;
    if(num3==1&&f5==n&&f6==m) f[turn][n][m]=1;
}
void work2(int turn,int n,int m) {
    int num1=0,f1=0,f2=0;
    int num2=0,f3=0,f4=0;
    int num3=0,f5=0,f6=0;
    int z=n+m;
    for(int i=s;i<=z-i;i++)
        if(z-i<=300) {
            int j=z-i;
            if(turn==1||!f[turn-1][i][j]) num1++,f1=i,f2=j;
            if(turn>=3&&!f[turn-2][i][j]) num2++,f3=i,f4=j;
            if(f[turn-1][i][j])
            if(turn<=3||!f[turn-3][i][j]) num3++,f5=i,f6=j;
        }
    if(num1==1&&f1==n&&f2==m) f[turn][n][m]=1;
    if(num2==1&&f3==n&&f4==m) f[turn][n][m]=1;
    if(num3==1&&f5==n&&f6==m) f[turn][n][m]=1;
}
bool fl;
string S;
int main() {
    cin>>s>>S>>t;
    if(S=="Alice") fl=1;
    else fl=0;
    for(int i=1;i<=t+2;i++) {
        for(int n=s;n<=300;n++)
            for(int m=n;m<=300;m++) {
                if(i>=3) f[i][n][m]=f[i-2][n][m];
                if(f[i][n][m]) continue;
                if(fl) work1(i,n,m);
                else work2(i,n,m);
            }
        fl^=1;
    }
    int sum=s+s;
    while(1) {
        if(sum>=1000) break;
        for(int n=s;n<=sum-n;n++) {
            int m=sum-n;
            if(!f[t+1][n][m]||!f[t+2][n][m]) continue;
            int fl=0;
            for(int k=1;k<=t;k++) if(f[t][n][m]) fl=1;
            if(fl) continue;
            printf("%d %d\n",n,m);
            return 0;
        }
        sum++;
    }
}

cnyz's Blog