2023杭电多校(8)

有点事结果鸽了两场牛客多校，杭电7懒得写题解了(

1005

不难发现无非分三种情况

一种两边都是$1$，一种两边都是$0$，一种一$1$一$0$

于是直接贪心，把所有连续段压成一份，对于最后一种情况很好解决，只有一个方向能走，直接走就好。

对于前两种情况，显然如果先手两个1，取完还能构造一个两个1的情况，后手就输了。如果不是这种情况的话，肯定取那个取完露出尽可能少的0的情况。

贪心做下去即可。

#include <bits/stdc++.h>

#define LL long long
#define ULL unsigned long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f;

void solve()
{
    int n;
    string s;
    cin >> n >> s;

    vector<PII> v;
    int cnt = 0;
    int num = 1;
    int now = s[0] - '0';

    if (n == 1)
    {
        if (s[0] == '0')
        {
            cout << "-1" << endl;
        }
        else
        {
            cout << "1" << endl;
        }
        return;
    }
    for (int i = 1; i < n; i++)
    {
        int x = s[i] - '0';
        if (x == now)
        {
            num++;
        }
        else
        {
            PII p1(now, num);
            v.push_back(p1);
            now = x;
            num = 1;
        }
        if (i == n - 1)
        {
            PII p1(now, num);
            v.push_back(p1);
        }
    }

    // for (int i = 0; i < v.size(); i++)
    // cout << v[i][0] << ' ' << v[i][1] << endl;

    int ans = -2;
    int c = 0;
    for (int l = 0, r = v.size() - 1;; c ^= 1)
    {
        // cerr << l << "  " << r << "   " << c << endl;
        if (l == r)
        {
            if (v[l].x != c)
            {
                ans = c ^ 1;
                break;
            }
            else if (v[l].x == c && v[l].y == 1)
            {
                ans = -1;
                break;
            }
            else
            {
                ans = c;
                break;
            }
        }

        if (c != v[l].x && c != v[r].x)
        {
            ans = c ^ 1;
            break;
        }
        else if (c == v[l].x && c != v[r].x)
        {
            if (v[l].y == 1)
            {
                l++;
                continue;
            }

            v[l].y--;
        }
        else if (c != v[l].x && c == v[r].x)
        {
            if (v[r].y == 1)
            {
                r--;
                continue;
            }
            v[r].y--;
        }
        else
        {
            if (v[l].y != 1 || v[r].y != 1)
            {
                ans = c;
                break;
            }
            else
            {
                if (v[l + 1].y > v[r - 1].y)
                    r--;
                else
                    l++;
            }
        }
    }

    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

1007

并查集即可

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5+10;
int fa[mx];
int Get(int x){
    if (x == fa[x]) return x;
    else return fa[x] = Get(fa[x]);
}
void Solve(){
    int N,M;
    cin >> N >> M;
    for (int i = 1 ; i <= N ; i ++){
        fa[i] = i;
    }
    for (int i = 1 ; i <= M ; i ++){
        int u,v;
        cin >> u >> v;
        int fx = Get(u),fy = Get(v);
        fa[fx] = fy;
    }
    int T,t;
    cin >> T >> t;
    bool flag = false;
    for (int i = 1 ; i < T ; i ++){
        int x;
        cin >> x;
        if (Get(x)!=Get(t)){
            flag = true;
        }
    }
    if (!flag) cout << "YES\n";
    else cout << "NO\n";
}
int main(){
    std::ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--){
        Solve();
    }
    return 0;
}

1008

题目是求$0~p$随机的n阶矩阵的秩的期望

我们考虑一行一行的构造这个东西

$f_{i,j}$表示考虑到第$i$行，秩为$j$的概率

那么我们就需要考虑当前和前面的是否线性相关

转移就是

$f[i][j] = f[i-1][j] * \frac{p^j}{p^n} + (1-\frac{p^{j-1}}{p^n}) * f[i-1][j-1]$

注意全$0$阵的特判

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mx = 5015;
const int MOD = 1e9+7;
int pw[mx];
int f[5005][5005];
int Pow(int x,int y){
    int ans = 1;
    for (;y;){
        if (y & 1) ans = 1ll * ans * x %MOD;
        x = 1ll * x * x % MOD;
        y >>=1;
    }
    return ans;
}
signed main(){
    int T;
    cin >> T;
    while (T--){
        int N,P;
        cin >> N >> P;
        int n = Pow(P,N);
        int invN = Pow(n,MOD-2);
        f[1][0] = invN;
        f[1][1] = (1-invN+MOD)%MOD;
        //cout << f[1][0] << " " << f[1][1] << endl; 
        pw[0] = 1;
        for (int i = 1 ; i <= N ; i ++){
            pw[i] = pw[i-1] * P % MOD;
        }
        for (int i = 2 ; i <= N ; i ++){
            f[i][0] = f[i-1][0] * invN%MOD;
            for (int j = 1 ; j <= i ; j ++){
                f[i][j] = (1ll * (f[i-1][j] * pw[j] % MOD * invN %MOD)%MOD + 1ll * f[i-1][j-1] * (1ll-(pw[j-1]*invN)%MOD+MOD)%MOD)%MOD;
            }
        }
        int ans = 0;
        for (int i = 1 ; i <= N ; i ++){
            ans = (ans + f[N][i] * i%MOD)%MOD;
        }
        cout << ans%MOD << endl;
    }
    return 0;    
}

1010

打表不难发现答案只有1，2，3三种

1很好判断

2考虑:

假设当前距离为$t$，第一次加的数字为$x^2$,第二次为$y^2$

一定有

$t = x^2 + y^2$

或者

$t = x^2 - y^2$

前者需要满足$x^2$和$y^2$都小于$t$

后者的话，$t = (x+y)(x-y)$，$\sqrt{t}$的枚举一下因数算即可。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin >> T;
    while (T--){
        int a,b;
        cin >> a >> b;
        int T = abs(a-b);
        int y = sqrt(T);
        if (1ll*y * y == T){
            cout << 1 << '\n';
            continue;
        }
        bool flag = false;
        for (int i = 1 ; i <= sqrt(T) ; i++){
            int ttt = T - i * i;
            int yy = sqrt(ttt);
            if (yy * yy == ttt){
                flag = true;
                break;
            }
            if (T%i == 0){
                int xx = i,yy = T/i;
                if ((xx + yy) %2 != 0) continue;
                int t = (xx + yy)/2;
                int tt = abs(xx - yy) /2;
                if (t < tt) swap(t,tt);
                if (t * t - tt * tt == T || tt * tt - t * t == T) {
                    flag = true;
                    break;
                }
            }
        }
        if (flag) cout << 2 <<'\n';
        else cout << 3 << '\n';
    }
    return 0;
} 

$04$感觉是个很典的线性基求$k$大子集异或和，然后二分一下就行。但是$2^{250}$好麻烦，写了个$bitset$+手写加减比较，没写完(