2022-11-1总结

选举

Description

Alice 和 Bob 要竞选魔方市市长。
有 $n$ 个选民，编号为 $1 \sim n$，它们中有的人支持 Alice ，有的人支持 Bob ，还有的人保持中立。
现在你需要把选民分成若干个区间，每个区间的长度在 $[l,r]$ 中。如果一个区间中支持 Alice 的人比支持 Bob 的人多，那么 Alice 得一票，一个区间中支持 Bob 的人比支持 Alice 的人多，那么 Bob 得一票。
Alice 想要赢得选举，于是它请你合理地分区间，使得它获得的票数减去 Bob 获得的票数最大。

Input

第一行三个整数 $n$, $l$, $r$，第二行 $n$ 个整数，每个整数为 $1,0$ 或 $−1$，第 $i$ 个数为 $1$ 表示它支持 Alice ，为 $−1$ 表示它支持 Bob ，为 $0$ 表示它保持中立。

Output

行一个整数表示 Alice 获得的票数减去 Bob 获得的票数的最大值。如果没有合法的方案输出 Impossible。

Hint

$1 \le n \le 10^6, 1 \le l \le r \le n$

Solution

$O(n^2)$ 的暴力 DP 很好想，考虑怎么去优化，因为权值有 $0,1,-1$ 所以没法单调队列，考虑以前缀和为下标建值域线段树维护 $\max$ ，可以通过控制区间来知道哪些 DP 值需要 $+1/-1$，时间复杂度 $O(n \log n)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int n, l, r;
int a[N], sum[N];
int f[N];

namespace tr {
    struct node {
        int ls, rs;
        int max = -INT_MAX;
    } a[N*10];
    int root, node_cnt;
    multiset<int> s[N*2];
    void modify(int pos, int val, int type, int &i = root, int l = -1e6, int r = 1e6);
    int query(int ql, int qr, int i = root, int l = -1e6, int r = 1e6);
}

int type(int l, int r);

int main()
{
    cin >> n >> l >> r;
    for(int i = 1; i <= n; i++)
        cin >> a[i], sum[i] = sum[i - 1] + a[i];
    
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    for(int i = l; i <= n; i++)
    {
        if(i-r > 0) tr::modify(sum[i-r-1], f[i-r-1], -1);
        tr::modify(sum[i-l], f[i-l], 1);
        
        f[i] = max(f[i], tr::query(-1e6, sum[i]-1)+1);
        f[i] = max(f[i], tr::query(sum[i], sum[i]));
        f[i] = max(f[i], tr::query(sum[i]+1, 1e6)-1);
    }
    
    if(f[n] < -n)
        cout << "Impossible";
    else
        cout << f[n] << "\n";
}

int type(int l, int r)
{
    if(sum[r]-sum[l-1] > 0)
        return 1;
    else if(sum[r]-sum[l-1] == 0)
        return 0;
    else
        return -1;
}

namespace tr {
    #define ls(i) a[i].ls
    #define rs(i) a[i].rs
    #define lmid ((l+r)>>1)
    #define rmid ((l+r+2)>>1)
    void pushup(int i)
    {
        a[i].max = max(a[ls(i)].max, a[rs(i)].max);
    }
    void modify(int pos, int val, int type, int &i, int l, int r)
    {
        if(!i) i = ++node_cnt;
        if(l == r)
        {
            multiset<int> &si = s[N+l];
            if(type == 1) si.insert(val);
            else si.erase(si.find(val));
            a[i].max = si.empty() ? -INT_MAX : *si.rbegin();
            return void();
        }
        if(pos <= lmid) modify(pos, val, type, ls(i), l, lmid);
        if(pos >= rmid) modify(pos, val, type, rs(i), rmid, r);
        pushup(i);
    }
    int query(int ql, int qr, int i, int l, int r)
    {
        if(ql <= l and r <= qr) return a[i].max; int ans = -INT_MAX;
        if(ql <= lmid) ans = max(ans, query(ql, qr, ls(i), l, lmid));
        if(qr >= rmid) ans = max(ans, query(ql, qr, rs(i), rmid, r));
        return ans;
    }
}

卡片

Description

小象有 $n$ 张卡片，第 $i$ 张卡片上有一个数字 $a_i$。 Alice 和 Bob 轮流选择卡片 (不能重复)，如果某次选择后已选择的卡片上的数字的最大公约数为 $1$ 或者没有卡片可以选择，那么当前角色失败。
你需要求出：

1、如果双方都选择最优策略，谁会获胜；

2、如果双方都随机选取， Alice 获胜的概率。

Input

第一行一个整数 $t$ 表示数据组数。
每组数据第一行一个整数 $n$，第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$。

Output

每组数据输出一行，包含一个整数和一个实数，用一个空格隔开。整数为 $1$ 表示 Alice 获胜，$0$ 表示 Bob 获胜。实数表示获胜概率，保留 $4$ 位小数。

Hint

$t \le 10, n \le 100, a_i \le 10^5$

Solution

一个状态只与当前 $\gcd$ 和已选卡片数量有关，记录这两个信息，并把每个 $a_i$ 的约数拆开。

#include <bits/stdc++.h>
using namespace std;

#define gcd __gcd
typedef double db;
const int N = 105;
const int A = 1e5+10;
int n, a[N], tmp[A];
int f[A][N];
db g[A][N];

void solve();

int main()
{
    int T; cin >> T;
    while(T --> 0)
    {
        memset(g, 0, sizeof(g));
        memset(f, 0, sizeof(f));
        memset(tmp, 0, sizeof(tmp));
        solve();
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j*j <= a[i]; j++)
            if(a[i]%j == 0)
            {
                tmp[j]++;
                if(j*j != a[i]) tmp[a[i]/j]++;
            }
    
    for(int i = 1; i <= n; i++)
        f[1][i] = g[1][i] = 1;
    
    for(int i = 2; i <= 100000; i++)
        for(int j = tmp[i]; j >= 1; j--)
        {
            g[i][j] = (1-g[i][j+1])*(tmp[i]-j);
            if(j != tmp[i]) f[i][j] = f[i][j+1]^1;
            
            for(int k = 1; k <= n; k++)
                if(a[k]%i != 0)
                {
                    int v = gcd(a[k], i);                    
                    g[i][j] += 1-g[v][j+1];
                    f[i][j] |= f[v][j+1]^1;
                }
            if(j < n) g[i][j] /= n-j;
        }
    
    bool flag = false; db ans = 0;
    for(int i = 1; i <= n; i++)
    {
        flag |= f[a[i]][1]^1;
        ans += (1-g[a[i]][1])/n;
    }
    printf("%d %.4f\n", flag, ans);
}