A

两人策略不会互相造成影响,最优策略是每个人每次拿一个。判断是否 $n_1 \leq n_2$ 即可。

B

先考虑如何计算一个排列的 $f$:设一个位置左边和右边第一个比他小的位置为 $ls_i,rs_i$,答案就是 $\sum_{i=1}^n a_i(rs_i-ls_i-1)$。

另一种思考思路是从小往大放,每次相当于将选出的位置分成左右两个连通块,每次得到的贡献是它所在的连通块跨过它的区间个数,由于区间总个数是一定的,所以我们每次一定要最小化跨过它的区间个数,所以每次选开头或结尾。不难得到串的数量是 $2^{n-1}$ 的。

考虑从小往大放每一个数,假设现在放了 $x$ 个数,如果把这个数放在结尾,就会有至少 $2^{n-x-1}$ 个数比它字典序小,判断一下就行了。

C

直观的考虑是去枚举次大值 $x$ 求出次大值 $=x$ 的概率,发现求这个需要知道

可以考虑求出 $f_x$ 表示次大值 $\geq x$ 的概率,最后差分一下就好了。

考虑这个不好算,我们去考虑如何算次大值 $<x$ 的概率:我们首先枚举钦定次大值在哪个位置,然后分情况讨论:

  1. 最大值 $<x$,那么所有数都有一个取值区间,可以求出概率
  2. 最大值 $\geq x$,枚举一下最大值是哪个,同上

D

二叉树构造。考虑递归构造。

首先发现对于一个点 $v$,它的左/右子树的前序遍历应该是连续的,也就是说假设当前这个子树内点编号是 $[l,r]$,那么应该存在一个 $l \leq x \leq r$,满足左子树编号是 $[l,x]$,右子树编号是 $[x+1,r]$。

假设我们现在构造到了 $x$ 点,先考虑左子树限制:一定有若干限制形如 $y$ 点要在左子树里,也就是说 $[x+1,y]$ 都要在左子树里;考虑右子树限制,若干限制形如 $z$ 点在右子树里,也就是说 $[z,r]$ 在右子树里。相当于 $[y+1,z-1]$ 没有限制。而没有限制的点可以无脑扔到右边,所以我们 dfs 的时候记录当前子树的编号至少要到多少,按照对左子树的限制递归到左边,然后得到左子树需要的最小的节点数,如果和右子树的限制有冲突就直接无解,否则构造右子树即可。

考虑构造的一类问题如果点可以随便加/减就可以考虑能否构造出最值

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
int n,c;
std::vector<int> G[MAXN][2];// 0=L

inline void stop(){
    puts("IMPOSSIBLE");exit(0);
}

int ch[MAXN][2];

inline void print(int v){
    if(!v) return;
    print(ch[v][0]);
    printf("%d ",v);
    print(ch[v][1]);
}

int tot = 1;

inline void work(int v,int t){ // 限制当前节点至少用了t个
    FOR(i,0,1) std::sort(all(G[v][i]));
    if(!G[v][0].empty()){
        int n = ++tot;
        ch[v][0] = n;
        work(n,G[v][0].back());
    }
    if(!G[v][1].empty() && tot >= G[v][1].front()) stop();
    if(!G[v][1].empty()) t = std::max(t,G[v][1].back());
    if(tot < t){
        int n = ++tot;
        ch[v][1] = n;
        work(n,t);
    }
}

int main(){
    scanf("%d%d",&n,&c);
    FOR(i,1,c){
        int u,v;char str[23];scanf("%d%d%s",&u,&v,str+1);
        if(u >= v) stop();
        G[u][str[1]=='R'].pb(v);
    }
    work(1,n);
    print(1);
    return 0;
}

E

可以证明选择的区间的并一定是连续的一段,如果中间有空着的讨论一下把它并到某一边答案一定不会变劣。

首先要求绝对值最小,我们其实可以自由选择绝对值的符号,在最优的限制下这样并不会出问题。(大多数绝对值在最优解的限制下都可以直接扔掉)

先考虑不在开头结尾的区间:

所以我们考虑对绝对值的符号 dp。首先发现一个区间的符号只有可能是 $-2,0,+2$,并且如果这个位置是 $+2$,上一个非 $0$ 位置一定是 $-2$。(其实可以把每个位置看成左右两个插头,每个插头可以选择权值 $-1,1$,并且 $-1$ 对着的非 $0$ 插头一定是 $1$,$1$ 对着的非 $0$ 插头一定是 $-1$)

所以我们可以设 $f_{i,j,0/1/2,1/2}$ 表示考虑到前 $i$ 个数,选了 $j$ 个连续段,当前段的权值是 $0/+2/-2$,上一个非 $0$ 段的权值是 $+2/-2$ 的方案数,转移枚举一下这个点是什么权值,是否和前面拼起来即可,详情可见代码。

现在要处理开头和结尾了:开头只有一个右插头,结尾只有一个左插头,所以可取的值只可能是 $+1/-1$,相当于是一个前后缀最小/最大子段和,处理一下就好了。详情也可以看代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 30000+5;
const int MAXM = 200+5;
int n,k;
// 中间连续最优
LL f[MAXN][MAXM][3][3];
// 考虑了前i个点,已经选出了j段,
LL mx[MAXN],mn[MAXN];int a[MAXN];

int main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d",a+i);
    CLR(f,~0x3f);
    // f[i][1][0/1/2][1/2];
    mx[0] = -1e18;mn[0] = 1e18;
    FOR(i,1,n){
        mx[i] = std::max(mx[i-1],0ll)+a[i];
        mn[i] = std::min(mn[i-1],0ll)+a[i];
    }
    FOR(i,1,n) mx[i] = std::max(mx[i],mx[i-1]),mn[i] = std::min(mn[i],mn[i-1]);
    FOR(i,1,n){
        f[i][1][1][2] = mx[i];
        f[i][1][2][1] = -mn[i];
    }
    FOR(i,1,n){
        FOR(j,2,k-1){
            f[i][j][0][1] = std::max({f[i-1][j][0][1],f[i-1][j-1][0][1],f[i-1][j-1][1][1],f[i-1][j-1][1][2]});
            f[i][j][0][2] = std::max({f[i-1][j][0][2],f[i-1][j-1][0][2],f[i-1][j-1][2][1],f[i-1][j-1][2][2]});
            f[i][j][1][2] = std::max({/*f[i-1][j][1][2],*/f[i-1][j][1][2]+2*a[i],f[i-1][j-1][2][1]+2*a[i],f[i-1][j-1][2][2]+2*a[i],f[i-1][j-1][0][2]+2*a[i]});
            f[i][j][2][1] = std::max({/*f[i-1][j][2][1],*/f[i-1][j][2][1]-2*a[i],f[i-1][j-1][1][1]-2*a[i],f[i-1][j-1][1][2]-2*a[i],f[i-1][j-1][0][1]-2*a[i]});
        }
    }
    mx[n+1] = -1e18;mn[n+1] = 1e18;
    ROF(i,n,1){
        mx[i] = std::max(mx[i+1],0ll)+a[i];
        mn[i] = std::min(mn[i+1],0ll)+a[i];
    }
    ROF(i,n,1) mx[i] = std::max(mx[i],mx[i+1]),mn[i] = std::min(mn[i],mn[i+1]);
    LL ans = -1e18;
    FOR(i,1,n) ans = std::max({ans,f[i][k-1][1][2]-mn[i+1],f[i][k-1][2][1]+mx[i+1],f[i][k-1][0][1]-mn[i+1],f[i][k-1][0][2]+mx[i+1]});
    printf("%lld\n",ans);
    return 0;
}

F

配对问题一看就是网络流问题。首先那个特殊的人没有用,因为要一一配对所以可以唯一确定那个人扮演哪个性别。

注意到每个人是并行的(我居然没注意到 hhh),那么相当于要求最大值最小。考虑二分答案。二分答案后每个人可以到达一些格子。

于是我们可以源点连所有男生,所有女生连汇点,男生连向能到到的格子,女生由能到达的格子连向,流量都是 $1$,看看是不是源点满流就行了。

G

期望线性性变成算 $(i,j)$ 是逆序对的概率。设 $f_{i,x,y}$ 表示 $i$ 轮后 $(x,y)$ 是逆序对的概率。

暴力的转移是枚举每一个可能的区间 $[l,r]$,对应翻转,转移过去即可。复杂度 $O(kn^4)$。

我们发现如果 $x$ 在区间 $[a,b]$ 内翻转的公式是 $b-(x-a) = b+a-x$,于是我们考虑去枚举 $b+a$,解不等式算出来有多少对合法的区间,一起转移即可。复杂度 $O(kn^3)$。

观察转移拆开后可以打二层差分优化。复杂度 $O(kn^2)$。(但是我没写)

如果这题需要取模,就要写线性递推之类的东西,但是这题是小数,所以猜测交换多次后会变得很稳定,我们将 $k$ 和 $1000$ 取 $\min$ 即可通过该题。

Last modification:September 24th, 2020 at 09:08 pm
如果觉得我的文章对你有用,请随意赞赏