Record - Dec. 1st, 2020 - Exam. REC

Prob. 1

Desc. & Link.

行走的形式是比较自由的，因为只要走到了最优答案处就可以不管了，所以不需要考虑游戏的结束。

考虑二分答案。

然后预处理出每个节点到 $s$（另一棵树就是 $t$）的距离。

判断答案合法性：

首先枚举 $A$ 树的每个节点（节点编号小于当前二分的答案），然后判断需要构成答案的 $B$ 树上的节点距离 $t$ 的距离的奇偶性是否一致即可。

但是这样有一个问题：我们如何确保这个答案是整个一轮移动过程中最大的？

仔细考虑一下，我们判断成功的依据是行走过程中所有和不超过我们当前二分的值，那么转为判断这个问题（意思就是前面降智了）。

因为这是一棵树，所以该走的路径一定会走。

因为我们枚举了 $A$ 树中的节点，所以每次从哪两个节点走到 $s$、$t$ 是固定下来的。

草，直接 bfs 判断找可达最小值就行了。

$\Theta(n\log_{2}^{2}n)$，我觉得不行，先写。

草卡卡常过了。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 1e6 + 5;

namespace IO{
    const int sz=1<<22;
    char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
    inline char gc(){
        return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
    }
    template<class T> void gi(T& x){
        x=0; char c=gc();
        for(;c<'0'||c>'9';c=gc());
        for(;c>='0'&&c<='9';c=gc())
            x=x*10+(c-'0');
    }
    inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
    inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
    template<class T> void pi(T x,char c='\n'){
        if(x==0) pc('0'); int t=0;
        for(;x;x/=10) p[++t]=x%10+'0';
        for(;t;--t) pc(p[t]); pc(c);
    }
    struct F{~F(){flush();}}f; 
}
using IO::gi;
using IO::pi;

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
    int to, nx;
    GraphSet ( int T = 0, int N = 0 ) { to = T, nx = N; }
} asA[MAXN * 2], asB[MAXN * 2];

int n, s, t, cntA, cntB, beginA[MAXN], beginB[MAXN], disA[MAXN], disB[MAXN], visA[MAXN], visB[MAXN];

void makeEdgeA ( const int u, const int v ) { asA[++ cntA] = GraphSet ( v, beginA[u] ), beginA[u] = cntA; }
void makeEdgeB ( const int u, const int v ) { asB[++ cntB] = GraphSet ( v, beginB[u] ), beginB[u] = cntB; }

void dfsA ( const int u, const int lst, const int dis ) {
    disA[u] = dis;
    for ( int i = beginA[u]; i; i = asA[i].nx ) {
        int v = asA[i].to;
        if ( v == lst )    continue;
        dfsA ( v, u, dis + 1 );
    }
}

void dfsB ( const int u, const int lst, const int dis ) {
    disB[u] = dis;
    for ( int i = beginB[u]; i; i = asB[i].nx ) {
        int v = asB[i].to;
        if ( v == lst )    continue;
        dfsB ( v, u, dis + 1 );
    }
}

void behaveOneSide ( int ark, int& mnA, int& mnB, int& ord, priority_queue<int, vector<int>, greater<int>>& align ) {
    int preSave = mnA;
    while ( ! align.empty () ) {
        int u = align.top ();
        if ( u + mnB > ark )    break;
        else    align.pop ();
        for ( int i = beginA[u]; i; i = asA[i].nx ) {
            int v = asA[i].to;
            if ( visA[v] )    continue;
            visA[v] = 1, align.push ( v );
            mnA = MIN ( mnA, v );
        }
    }
    if ( mnA == preSave )    ++ ord;
    else    ord = 0;
}

void behaveAnotherSide ( int ark, int& mnA, int& mnB, int& ord, priority_queue<int, vector<int>, greater<int>>& align ) {
    int preSave = mnB;
    while ( ! align.empty () ) {
        int u = align.top ();
        if ( u + mnA > ark )    break;
        else    align.pop ();
        for ( int i = beginB[u]; i; i = asB[i].nx ) {
            int v = asB[i].to;
            if ( visB[v] )    continue;
            visB[v] = 1, align.push ( v );
            mnB = MIN ( mnB, v );
        }
    }
    if ( mnB == preSave )    ++ ord;
    else    ord = 0;
}

priority_queue<int, vector<int>, greater<int>> oneQ, anotherQ;
bool check ( const int x ) {
    for ( int i = 1; i <= n; ++ i )    visA[i] = visB[i] = 0;
    for ( ; ! oneQ.empty (); oneQ.pop () ) ;
    for ( ; ! anotherQ.empty (); anotherQ.pop () ) ;
    oneQ.push ( s ), anotherQ.push ( t );
    visA[s] = 1, visB[t] = 1;
    int turn = 0, mnA = s, mnB = t, ord = 0;
    while ( mnA > 1 || mnB > 1 ) {
        turn ^= 1;
        if ( turn )    behaveOneSide ( x, mnA, mnB, ord, oneQ );
        else    behaveAnotherSide ( x, mnA, mnB, ord, anotherQ );
        if ( ord > 2 )    break;
    }
    if ( mnA == 1 && mnB == 1 )    return 1;
    else    return 0;
}

int solve ( int l, int r ) {
    while ( l + 1 < r ) {
        int mid = ( l + r ) >> 1;
        if ( check ( mid ) )    r = mid;
        else    l = mid;
    }
    return r;
}

int main () {
    int tCase;
    gi ( tCase );
    while ( tCase -- > 0 ) {
        gi ( n ), cntA = cntB = 0;
        for ( int i = 1; i <= n; ++ i )    beginA[i] = 0, beginB[i] = 0;
        for ( int i = 1, u, v; i < n; ++ i ) {
            gi ( u ), gi ( v );
            makeEdgeA ( u, v ), makeEdgeA ( v, u );
        }
        for ( int i = 1, u, v; i < n; ++ i ) {
            gi ( u ), gi ( v );
            makeEdgeB ( u, v ), makeEdgeB ( v, u );
        }
        gi ( s ), gi ( t );
        // dfsA ( s, 0, 0 ), dfsB ( t, 0, 0 );
        pi ( solve ( 1, n << 1 ) );
    }
    return 0;
}

Prob. 2

Desc. & Link.

$n$ 很小，$q$ 也很小。

感觉这个 $n$ 不是 $2^{n}$ 的算法也不是多项式算法欸。

但复杂度一定与 $n$ 有关……

草这玩意儿折半是不是可以折半搜索？

我们可以搜出两边我们可以凑出的价格，分别记为 $A_{i},i\in[1,C_{A}]$、$B_{i},i\in[1,C_{B}]$。

然后让 $A,B$ sorted。

然后枚举 $A_{i}$，找到 $B$ 中最大的能与 $A_{i}$ 相加小于等于需要的值，然后算下贡献即可（bullshit）。

不是为什么用快读本地过数据提交瓦爆啊。。。

#include<cstdio>
#include<algorithm>
using namespace std;
void read(long long &hhh)
{
    long long x=0;
    char c=getchar();
    while(((c<'0')|(c>'9'))&(c^'-'))    c=getchar();
    if(c^'-')    x=c^'0';
    char d=getchar();
    while((d>='0')&(d<='9'))
    {
        x=(x<<3)+(x<<1)+(d^'0');
        d=getchar();
    }
    if(c^'-')    hhh=x;
    else    hhh=-x;
}
void writing(long long x)
{
    if(!x)    return;
    if(x>9)    writing(x/10);
    putchar((x%10)^'0');
}
void write(long long x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    else if(!x)
    {
        putchar('0');
        putchar('\n');
        return;
    }
    writing(x);
    putchar('\n');
}
long long n,q,endone,beginano,onesiz,onebuc[2000005],anosiz,anobuc[2000005],opl,opr,cud[45];
void dfs(long long now,long long cur)
{
    if(now==endone+1)    onebuc[++onesiz]=cur;
    else
    {
        dfs(now+1,cur+cud[now]);
        dfs(now+1,cur);
    }
}
void exdfs(long long now,long long cur)
{
    if(now==n+1)    anobuc[++anosiz]=cur;
    else
    {
        exdfs(now+1,cur+cud[now]);
        exdfs(now+1,cur);
    }
}
long long solve(long long mos)
{
    long long now=anosiz;
    long long res=0;
    for(long long i=1;i<=onesiz;++i)
    {
        while(now&&onebuc[i]+anobuc[now]>mos)    now--;
        res+=now;
    }
    return res;
}
int main()
{
//    read(n);
//    read(q);
    scanf("%lld%lld",&n,&q);
//    for(long long i=1;i<=n;++i)    read(cud[i]);
    for(long long i=1;i<=n;++i)    scanf("%lld",&cud[i]);
    endone=(n>>1);
    beginano=endone+1;
    dfs(1,0);
    exdfs(beginano,0);
    sort(onebuc+1,onebuc+onesiz+1);
    sort(anobuc+1,anobuc+anosiz+1);
    while(q--)
    {
        scanf("%lld%lld",&opl,&opr);
//        read(opl);
//        read(opr);
//        write(solve(opr)-solve(opl-1));
        printf("%lld\n",solve(opr)-solve(opl-1));
    }
    return 0;
}

Prob. 4

Desc. & Link.

相当于在树上对于每一个点找出找出一条以其为链顶的链。

设 $f_{u}$ 为 $u$ 的答案。

$$ f_{u}=\max_{v\in\text{son}(u)}\{f_{v}+(a_{u}-\text{dis}(u,v))\times b_{v},0\} $$

有乘法，然后题目中一堆常数。

:-) 斜率优化

我们令 $s_{u}=\text{dis}(1,u)$，然后

$$ \begin{aligned} f_{u} &=\max_{v\in\text{son}(u)}\{f_{v}+(a_{u}+s_{u}-s_{v})\times b_{v},0\} \\ &=\max_{v\in\text{son}(u)}\{(a_{u}-s_{u})\times b_{v}+f_{v}-s_{v}\times b_{v},0\} \end{aligned} $$

令 $y=f_{u},x=a_{u}-s_{u},k=b_{v},b=f_{v}-s_{v}\times b_{v}$，那么这个东西就是一个 $y=kx+b$。

那么我们现在需要在子树里维护凸包，并且能够支持合并凸包和插入直线。