RainAir's Blog / zh-CN SDOI.rp++ Thu, 21 Jan 2021 00:09:00 +0800 Thu, 21 Jan 2021 00:09:00 +0800 AtCoder 乱做 /archives/1609/ /archives/1609/ Thu, 21 Jan 2021 00:09:00 +0800 RainAir 感觉只会抄题解。。

AGC020E

首先自己可以想到如果只是要单纯的求一个串的方案数可以区间 dp:观察这个表达式,可以写成

f := g | g + f
g := '0' | '1' | '(' + f + '*' + 'x' +  ')'

其中 x 是一个数字,要求 $x>1$,并且 $f$ 是 $g$ 的一个长度为 $x$ 的循环节。

那么就可以根据上面的定义写出 dp 了:设 $f_{l,r},g_{l,r}$ 表示区间 $[l,r]$ 的答案,根据上面的定义可以得到转移:

$$ \begin{aligned} f_{l,r} &= g_{l,r}+\sum_{i=l}^{r-1} g_{l,i}f_{i+1,r}\\ g_{l,r} &=\begin{cases} 1& l = r\\ \sum_{d|(r-l+1),d < r-l+1}[\text{d 是 s[l,r] 的循环节}] f_{l,l+d-1}& \text{otherwise} \end{cases}\\ \end{aligned} $$

接下来就看题解了。

题解里说,我们把状态改成 $f_s$ 表示字符串 $s$ 的所有子串的方案数,然后类似做就好了。这时候转移 $f$ 就是枚举断开,$g$ 就是枚举循环节,将所有长度为 $d$ 的子串的按位与拿下去做。这样看起来十分暴力,但是我们可以推一下复杂度:设 $T_f(n)$ 表示长度为 $n$ 的 $f$ 的计算时间,$T_g(n)$ 表示长度为 $n$ 的 $g$ 计算时间,有(这里要注意 时间是相加不是相乘):

$$ T_f(n) = \sum_{i=1}^n (n-i+1)T_g(i)\\ T_g(n) = \sum_{d|n,d < n} T_f(d)\\ \Rightarrow T_f(n) = \sum_{i=1}^n (n-i+1)\sum_{d|i,d < i} T_f(d) $$

注意这里第一行是乘 $n-i+1$ 而不是加 $T_f(n-i)$ 的原因 $f$ 不会生成新的串,只会导致 $g$ 被多算几遍,那么一个 $g$ 会被枚举 $n-len+1$ 次。这样大概运算是 29310258 反正能过(

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb push_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#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 = 100+5;
const int ha = 998244353;
std::string str;

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

std::map<std::string,int> f,g;
int F(std::string);
int G(std::string);

inline int F(std::string s){
    if(s.empty()) return 1;
    if(f.count(s)) return f[s];
    int res = 0;
    FOR(i,1,SZ(s)) add(res,1ll*G(s.substr(0,i))*F(s.substr(i,SZ(s)-i))%ha);
    f[s] = res;return res;
}

inline int G(std::string s){
    if(s.empty()) return 1;
    if(s == "0") return 1;
    if(s == "1") return 2;
    if(g.count(s)) return g[s];
    int res = 0;
    FOR(d,1,SZ(s)-1){
        if(SZ(s)%d) continue;
        std::string nxt="";
        FOR(i,0,d-1){
            bool flag = 1;
            for(int j = i;j < SZ(s);j += d) flag &= (s[j]=='1');
            if(flag) nxt += "1";
            else nxt += "0";
        }
        add(res,F(nxt));
    }
    return res;
}

int main(){
    std::cin >> str;
    printf("%d\n",F(str));
    return 0;
}
]]>
0 /archives/1609/#comments /feed/archives/1609/
CF 1455 题解 /archives/1600/ /archives/1600/ Tue, 08 Dec 2020 20:53:12 +0800 RainAir A

$g(x)$ 实际是求原数和去除后缀 $0$ 后的数的比值,发现第一个不同的值一定会在 $10^x$ 达到,所以答案就是字符串长度。

B

我们先假设走了 $m$ 步,并且都是走第一种,那么相当于就是走了 $\frac{m(m+1)}{2}$,发现将第 $i$ 个位置改成第二种操作会减少 $i+1$,我们先找到最小的 $m$ 满足 $\frac{m(m+1)}{2} \geq x$ ,设 $r=\frac{m(m+1)}{2}-x$,发现一定有 $r \leq m$,而我们发现所有位置更改后能减少的量分别是 $2,3,\ldots,m+1$,发现只有 $r=1$ 的时候不能被表示出来,所以 $r=1$ 的时候让 $m+1$ 就是答案了。

C

注意这两个人的策略都是最大化自己的胜利步数,显然后手可以一直不接球等到先手耗尽体力的时候将球打回去,剩下的球先手都接不到,所以后手最大胜利次数就是 $y$,先手由于最后一次球被接住了,胜利次数是 $x-1$。

D

贪心模拟,假设当前手里的数字是 $x$,正在考虑第 $i$ 个位置:

  • $a_{i-1} > a_i$:如果换不了($a_i \leq x$) 就直接输了,否则我们一定会交换,看下是否满足条件
  • $a_{i-1} \leq a_i$:如果 $x < a_i$,因为这个序列是不降的,就意味着以后都不能交换了,所以这时候判一下 $i+1$ 后缀是否有序,如果不有序你一定要交换;如果 $x \geq a_i$ 就可以不管。
#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 = 500+5;
int n,x,a[MAXN];
bool f[MAXN];

inline void Solve(){
    scanf("%d%d",&n,&x);
    FOR(i,1,n) scanf("%d",a+i);
    int p = 1;
    ROF(i,n,2){
        if(a[i-1] > a[i]){
            p = i;break;
        }
    }
    if(p == 1){
        puts("0");
        return;
    }
    int ans = 0;
    if(x < a[1]) std::swap(x,a[1]),++ans;
    FOR(i,2,p){
        if(a[i-1] > a[i]){
            if(a[i] <= x){
                puts("-1");return;
            }
            std::swap(a[i],x);++ans;
            if(a[i-1] > a[i]){
                puts("-1");return;
            }
        }
        else if(x < a[i] && i != p){
            std::swap(a[i],x);++ans;
        }
    }
    printf("%d\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

E

我们设正方形左下角 $(x,y)$ 边长为 $d$,枚举四个点分别对应正方形的哪些点,现在有三个变量 $x,y,d$,但我们发现贡献式子最终是形如若干个 $|x-x_i|,|x+d-x_i|,|y-y_i|,|y+d-y_i|$ 的和,如果将 $d$ 看成常量,发现 $x,y$ 一定会取让某个绝对值为 $0$ 的点,枚举取什么,剩下就变成了求 $\sum_i |d+c_i|$ 的最大值,也是一定会取某个零点的位置,都算算就好了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<LL,LL>
#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

LL xx[5],yy[5],x[5],y[5];
int p[5];

inline LL mabs(LL x){
    return x < 0 ? -x : x;
}

std::vector<LL> S;

inline LL gao(){
    std::sort(all(S));
    int t = S.size()>>1;
    LL p = -S[t-1],res = 0;
    for(auto x:S) res += abs(x+p);
    return res;
}

inline void Solve(){
    FOR(i,1,4) scanf("%lld%lld",xx+i,yy+i),p[i] = i;
    LL ans = 1e18;
    do{
        FOR(i,1,4) x[p[i]] = xx[i],y[p[i]] = yy[i];
        for(auto i:{1,3}){
            for(auto j:{1,2}){
                S.clear();
                LL c = abs(x[1]-x[i])+abs(x[3]-x[i])+abs(y[1]-y[j])+abs(y[2]-y[j]);
                for(auto k:{2,4}) S.pb(x[i]-x[k]);
                for(auto k:{3,4}) S.pb(y[j]-y[k]);
                std::vector<LL> T = S;
                LL mn = 1e18;
                mn = std::min(mn,gao());
                S=T;FOR(k,0,1) S[k] = -S[k];
                mn = std::min(mn,gao());
                S=T;FOR(k,2,3) S[k] = -S[k];
                mn = std::min(mn,gao());
                S=T;FOR(k,0,1) S[k] = -S[k];
                mn = std::min(mn,gao());
                c += mn;
                ans = std::min(ans,c);
            }
        }
    }while(std::next_permutation(p+1,p+4+1));
    printf("%lld\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

F

这题非常好的地方在于 dp 状态表示的不一定是个数,还可以是个字符串(

设 $f_i$ 表示操作完了 $1 \ldots i$ ,前缀的最小字典序,转移的时候分类讨论 $i+1,i+2$ 的操作:

  • U/D ,$f_{i} \to f_{i+1}$
  • L,$f_i \to f_{i+1}$
  • R+U/D,$f_{i} \to f_{i+2}$
  • RL,$f_i \to f_{i+2}$

直接转移即可,复杂度 $O(n^2)$。

可以用滚动数组+二分哈希做到 $O(n \log n)$。

#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 = 500+5;
int n,k;
int mn[26];
std::string f[MAXN],str;

inline std::string ctos(char x){
    return std::string(1,x);
}

inline void Solve(){
    std::cin >> n >> k >> str;str = "0"+str;
    mn[0] = 0;FOR(i,1,k-2) mn[i] = i-1;mn[k-1] = 0;
    f[0].clear();FOR(i,1,n) f[i] = "{";
    FOR(i,0,n-1){
        f[i+1] = std::min(f[i+1],f[i]+ctos('a'+mn[str[i+1]-'a']));
        if(i) f[i+1] = std::min(f[i+1],f[i].substr(0,i-1)+ctos(str[i+1])+f[i].back());
        if(i != n-1) f[i+2] = std::min(f[i+2],f[i]+ctos('a'+mn[str[i+2]-'a'])+ctos(str[i+1]));
        if(i && i != n-1) f[i+2] = std::min(f[i+2],f[i].substr(0,i-1)+ctos(str[i+2])+f[i].back()+ctos(str[i+1]));
    }
    std::cout << f[n] << std::endl;
}

int main(){
    std::ios::sync_with_stdio(false);
    int T;std::cin >> T;
    while(T--) Solve();
    return 0;
}

G

dp 合并可以启发式合并。。这个很妙

先考虑没有 if 咋做:设 $f_{i,x}$ 表示执行了前 $i$ 条语句,当前值是 $x$ 的答案,直接做是 $O(n^2)$ 的。

观察转移相当于全局加上一个值和求一个最小值并单点赋值,用数据结构维护可以做到 $O(n \log n)$。这里可以直接用一个 set 维护最小值,map 维护每个下标对应的在 set 里的值,再维护个整体加标记即可。我们只需要维护可能的值的 dp 值就好了。

if 咋做呢?我们发现 if 内部是独立的,可以做一样的 dp,只是 dp 的初值需要改一下,所以我们遇到 if 就进去做 dp ,做完后考虑如何合并这两个块:我们可以用启发式合并,将大小小的每一种 dp 值都合并到大的里,注意要特判一下 if 条件给的值对应的 dp 值(这里不能单纯去 min,需要覆盖)。

启发式合并复杂度对的原因在于一次转移可以放缩看成加入一个元素,于是复杂度就是显然的 $O(n \log^2 n)$ 了。细节挺多的。

#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

int n,s;

struct Node{// 全局加 单点修改 询问最小值
    LL tag;
    std::map<int,LL> mp;// 位置 i 在 set 内的值
    std::multiset<LL> S;
    Node(LL tag=0) : tag(tag) {}
    inline void update(int p,LL d){
        if(p == s) return;
        if(mp.count(p)) S.erase(S.find(mp[p]));
        mp[p] = d-tag;
        S.insert(mp[p]);
    }

    inline LL get(int p){
        if(!mp.count(p)) return 1e18;
        return mp[p]+tag;
    }

    inline void upmin(int p,LL d){
        if(p == s) return;
        if(get(p) > d) update(p,d);
    }

    inline LL query(){
        return *S.begin() + tag;
    }
};

std::vector<Node> st;
std::vector<int> oo;

int main(){
    scanf("%d%d",&n,&s);
    Node v;v.update(0,0);
    st.pb(v);oo.pb(-114514);
    FOR(i,1,n){
        char opt[12];scanf("%s",opt);
        if(opt[0] == 's'){
            int x,y;scanf("%d%d",&x,&y);
            if(st.back().mp.empty()) continue;
            LL c = st.back().query();
            st.back().tag += y;st.back().upmin(x,c);
        }
        if(opt[0] == 'i'){
            int x;scanf("%d",&x);
            LL c = st.back().get(x);
            Node v;if(c != 1e18) v.update(x,c);
            st.pb(v);oo.pb(x);
        }
        if(opt[0] == 'e'){
            int tp = (int)st.size()-1,o = oo.back();bool flag = 1;
            if(st[tp].mp.size() > st[tp-1].mp.size()) std::swap(st[tp],st[tp-1]),flag = 0;
            for(auto x:st[tp].mp){
                if(x.fi != o) st[tp-1].upmin(x.fi,x.se+st[tp].tag);
                else{
                    if(flag) st[tp-1].update(x.fi,x.se+st[tp].tag);
                }
            }
            st.pop_back();oo.pop_back();
        }
    }
    printf("%lld\n",st[0].query());
    return 0;
}
]]>
2 /archives/1600/#comments /feed/archives/1600/
CF1450 题解 /archives/1599/ /archives/1599/ Mon, 07 Dec 2020 21:29:00 +0800 RainAir A

把 $b$ 都提到最前面就好了。

#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 = 200+5;
char str[MAXN];
int cnt[26],n;

int main(){
    int T;scanf("%d",&T);
    while(T--){
        CLR(cnt,0);scanf("%d",&n);
        scanf("%s",str+1);
        FOR(i,1,n) ++cnt[str[i]-'a'];
        FOR(i,1,cnt[1]) putchar('b');
        FOR(i,0,25){
            if(i == 1) continue;
            FOR(j,1,cnt[i]) putchar('a'+i);
        }
        puts("");
    }
    return 0;
}

B

我们证明答案一定 $\leq 1$:假设答案 $\geq 2$,考虑最后一步和倒数第二步,倒数第二步会把最后一步操作的点直接拉过来,所以最后一步的操作是无效的,可以删去。

#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 = 100+5;
int n,x[MAXN],y[MAXN],k;

inline void Solve(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d%d",x+i,y+i);
    FOR(i,1,n){
        int mx = 0;
        FOR(j,1,n) mx = std::max(mx,std::abs(x[i]-x[j])+std::abs(y[i]-y[j]));
        if(mx <= k){
            puts("1");
            return;
        }
    }
    puts("-1");
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

C1

感觉比较难。。发现三个相邻的点 $i+j \bmod 3$ 两两不同,于是按照 $i+j \bmod 3$ 分类,找一个最小的将其全部翻转即可。

C2

会了 C1 稍微想想就会了。我们现在把 X 分成三类 $x_0,x_1,x_2$,把 O 分成三类 $o_1,o_2,o_3$,显然我们只需要选一对 $p \neq q$,将 $x_p$ 全都变为 O,并且将 $x_q$ 全都变为 X,可以得到这样是 $\leq \frac{1}{3}$ 的。

#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 = 300+5;
char str[MAXN][MAXN];int n;
int mp[MAXN][MAXN];
int cnt[2][3],ps[2];

inline void Solve(){
    scanf("%d",&n);CLR(cnt,0);
    FOR(i,1,n){
        scanf("%s",str[i]+1);
        FOR(j,1,n){
            if(str[i][j] != '.') ++cnt[str[i][j]=='X'][(i+j)%3];
        }
    }
    ps[0] = ps[1] = -1;
    int mn = 1e9;
    FOR(i,0,2){
        FOR(j,0,2){
            if(i == j) continue;
            if(mn > cnt[0][i]+cnt[1][j]){
                mn = cnt[0][i] + cnt[1][j];
                ps[0] = i;ps[1] = j;
            }
        }
    }
    FOR(i,1,n){
        FOR(j,1,n){
            if(str[i][j] == '.') putchar(str[i][j]);
            else{
                if(str[i][j] == 'O') putchar((i+j)%3 == ps[0] ? 'X' : 'O');
                else putchar((i+j)%3 == ps[1] ? 'O' : 'X');
            }
        }
        puts("");
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

D

特判 $k=1$ 和 $k=n$。

考虑 $k \in [2,n-1]$ 的情况:首先最小值 $1$ 肯定要出现且仅出现一次,发现只需要出现一次的位置一定是边界,所以等价于要判断是否只有一个 $1$ 并且这个 $1$ 在边界上,然后删掉这个 $1$ 变成了一个子问题。我们就可以求出最长能凑出多少的排列了。

感觉比 C 简单。。

#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 = 3e5 + 5;
int n,a[MAXN];
bool vis[MAXN];
bool f[MAXN];
int cnt[MAXN];

inline void Solve(){
    scanf("%d",&n);FOR(i,1,n) cnt[i] = 0;
    FOR(i,1,n) scanf("%d",a+i),vis[i] = 0,++cnt[a[i]];
    FOR(i,1,n) vis[a[i]] = 1,f[i] = 0;f[0] = 1;
    int sm = 0;
    FOR(i,1,n) f[i] = f[i-1]&vis[i],sm += vis[i];
    std::reverse(f+1,f+n+1);
    int l = 1,r = n,now = 1;
    while(l <= r){
        if(a[l] != now && a[r] != now) break;
        --cnt[now];
        if(cnt[now]) break;
        if(a[l] == now) ++l,++now;
        else if(a[r] == now) --r,++now;
    }
    --now;
    FOR(i,1,n-now-1) f[i] = 0;
    if(sm == n) f[1] = 1;
    if(vis[1]) f[n] = 1;
    FOR(i,1,n) putchar('0'+f[i]);puts("");
}

int main(){
    int T;scanf("%d",&T);while(T--) Solve();
    return 0;
}

E

其实是个差分约束题(

首先相邻两个人一定奇偶性不同,所以如果不是二分图直接无解。

考虑一条无向边 $(u,v)$,相当于有限制 $|a_u-a_v| = 1$,不妨先写成 $|a_u-a_v| \leq 1$;

考虑一条有向边 $u \to v$,相当于有限制 $a_v-a_u=1$,也就是 $a_v-a_u \leq 1$ 和 $a_v-a_u \geq 1$。

我们按照上面不等式建差分约束然后跑最短路,枚举一个起点,求出距离起点最远的距离,显然这个距离的最大值就是答案。

首先答案一定不能超过这个值,所以我们只要构造出一组合法的解就好了。

我们取能取到最大值的起点,将点 $i$ 的权值直接设为起点到 $i$ 的最短路就好了。因为这是一个二分图,所以无向边的情况不可能有 $a_u=a_v$(因为都是连的 $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 = 200+5;

int G[MAXN][MAXN],dis[MAXN][MAXN];
int n,m;
bool flag=1;
int col[MAXN];
bool vis[MAXN];

inline void dfs(int v){
    vis[v] = 1;
    FOR(i,1,n){
        if(G[v][i] == 1e8 || v == i) continue;
        if(vis[i]) flag &= (col[v]^col[i]);
        else col[i] = col[v]^1,dfs(i);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) FOR(j,1,n) G[i][j] = 1e8;
    FOR(i,1,n) G[i][i] = 0;
    while(m--){
        int i,j,w;scanf("%d%d%d",&j,&i,&w);
        if(!w){
            G[j][i] = std::min(G[j][i],1);
            G[i][j] = std::min(G[i][j],1);
        }
        else{
            G[j][i] = std::min(G[j][i],1);
            G[i][j] = std::min(G[i][j],-1);
        }
    }
    dfs(1);
    if(!flag){
        puts("NO");
        return 0;
    }
    FOR(i,1,n) FOR(j,1,n) dis[i][j] = G[i][j];
    int cir = 1e9;
    FOR(k,1,n){
        FOR(i,1,k-1){
            FOR(j,1,k-1){
                if(i == j) continue;
                cir = std::min(cir,G[k][i]+G[j][k]+dis[i][j]);
            }
        }
        FOR(i,1,n){
            FOR(j,1,n){
                dis[i][j] = std::min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
//    FOR(i,1,n) FOR(j,1,n) if(G[i][j] != 1e9 && i != j) printf("%d %d %d\n",i,j,G[i][j]);
    if(cir < 0){
        puts("NO");
        return 0;
    }
    int mx = 0,ps = -1;
    FOR(i,1,n){
        int c = -1e9;
        FOR(j,1,n) c = std::max(c,dis[i][j]);
        if(mx < c){
            mx = c;ps = i;
        }
    }
    puts("YES");
    printf("%d\n",mx);
    FOR(i,1,n) printf("%d%c",dis[ps][i]," \n"[i==n]);
    return 0;
}

F

还是结论题,完全不会

这个操作实际上就是将原排列分成尽量少的段,将这些段翻转和重排后要求相邻的值不能相同。

那么我们先考虑如何判断对于一个分成了 $k+1$ 段的切割方案,是否存在一种操作方案,能重排后相邻值不相同。

首先我们要保证每段内部不能有相邻相同的对,因为操作影响不到内部的点。

设 $f(c)$ 表示颜色 $c$ 在端点上的出现次数,一个显然的限制是 $f(c) \leq k+2$,我们现在说明只要满足这个限制的所有切割方案都是合法的:

考虑对 $k$ 归纳,如果 $k=0$ 时只有一段,命题显然成立;对于 $k \geq 1$ 的部分,考虑取最大值的 $f(x)$,找出一端是颜色 $x$ 的段,再随便找一个一端是颜色 $y(y \neq x)$ 的段,将 $x,y$ 对着拼在一起,现在相当于是一个 $k-1$ 的局面,我们发现 $f(x)-1 \leq k-1+2$,$f(z) \leq k-1 \leq k$(因为如果非最大值 $> k$ 那么和就超过 $k+2$ 了),所以这个局面是合法的,归纳得证。

所以我们先将所有相邻相同的地方都分开,然后看下是否满足条件,如果满足条件直接输出 $k$,否则我们要多切出一些段来让其满足条件。设最大值为 $f(x)$,分类讨论一下发现每次切开的两边的颜色都不能是 $x$,切到满足条件为止就好了。如果全都切完了还不满足条件就无解。

#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 = 1e5 + 5;
int n,a[MAXN],f[MAXN];

inline void Solve(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),f[i] = 0;
    int k = 0;
    ++f[a[1]];++f[a[n]];
    FOR(i,2,n){
        if(a[i] == a[i-1]){
            ++k;++f[a[i]];++f[a[i-1]];
        }
    }
    int mx = 0,ps = -1;
    FOR(i,1,n){
        if(mx < f[i]-k-2){
            mx = f[i]-k-2;
            ps = i;
        }
    }
    if(!mx){
        printf("%d\n",k);
        return;
    }
    int r = 0;
    FOR(i,2,n) if(a[i] != a[i-1] && a[i] != ps && a[i-1] != ps) ++r;
    if(mx <= r){
        printf("%d\n",k+mx);
    }
    else{
        puts("-1");
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

G

先咕了,等个谁写个中文题解 (

H1

先考虑如何求 $f(c)$:首先发现如果有相邻相同颜色的点可以都删掉,于是我们只需要考虑黑白交替的 $f(c)$ 答案是啥:不难发现是黑色点数量除二。

所以我们可以用栈来搞这个东西:每次加入一个新球,如果栈顶和这个球颜色相同就一块弹出栈,否则弹出栈并让答案 $+1$。不妨考虑哪些黑色点对答案有贡献:我们如果假设第一个点是黑色点的话,第一个点有贡献当且仅当下一个黑色点也是奇数位置的点(说明有一个白色和它配对掉了),如果下一个黑色点是偶数位置的话说明它和上一个黑色点消去了,设奇数位置,偶数位置黑色点数量为 $B_1,B_2$,白色为 $W_1,W_2$,答案就是$\frac{1}{2}|B_1-B_2|$。

如果枚举 $B_1,B_2$ 然后计数很麻烦,考虑 $B_2+W_2=\frac{n}{2}$,所以这个式子可以换成 $\frac{1}{2}|B_1-\frac{n}{2}+W_2|$,我们枚举 $i=B_1+W_2$,设空位置数量为 $p$ ,已经有的 $b_1+w_2=c$,方案数就是 $\binom p {i-c}$,所以答案就是:

$$ \frac{1}{2^p}\sum_{i=0,i \equiv \frac{n}{2} \pmod 2}^n \binom p {i-c} |i-\frac{n}{2}| $$

我们改为枚举 $i-c$,设 $d=c-\frac{n}{2}$式子化简为:

$$ \frac{1}{2^p}\sum_{i=0,i \equiv d \pmod 2}^n \binom p i |i-d| $$

#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 = 3e5 + 5;
const int ha = 998244353;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

int fac[MAXN],inv[MAXN];

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    return (n < 0 || m < 0 || n < m) ? 0 : 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

char str[MAXN];
int n,m;

int main(){
    prework();
    scanf("%d%d",&n,&m);
    scanf("%s",str+1);
    int B1=0,W2=0,p=0;
    FOR(i,1,n){
        B1 += (str[i] == 'b' && (i&1));
        W2 += (str[i] == 'w' && (!(i&1)));
        p += (str[i] == '?');
    }
    int ans = 0;
    FOR(x,0,n){
        int c = C(p,x),d = std::abs(x-(n/2)+B1+W2);
        if(d&1) continue;
        c = 1ll*c*d%ha;
        add(ans,c);
    }
    ans = 1ll*ans*qpow(qpow(2,p))%ha;
    printf("%d\n",ans);
    return 0;
}

H2

首先要解决 $i \equiv d \pmod 2$ 的限制的问题,发现 $\binom n m = \binom {n-1}{m}+\binom{n-1}{m-1}$,所以我们将式子写开,就去掉了这个限制。

现在我们考虑如何维护如下式子的值:

$$ \begin{aligned} \sum_{i=0}^n \binom p i |i-d| = \sum_{i=0}^d \binom p i d-\sum_{i=0}^d \binom p i i+\sum_{i=d+1}^n \binom p i i - \sum_{i=d+1}^n \binom p i d \end{aligned} $$

发现 $\binom n m m= \binom {n-1}{m-1}n$,区间求和可以拆成前缀和询问,所以我们相当于要快速维护

$$ \sum_{i=0}^{lim} \binom p i $$

我们发现 $lim$ 和 $i$ 的变化都是 $O(1)$ 的,所以我们只需要考虑 $lim,p$ 加减 $1$ 的变化即可。

$lim$ 加一直接加上对应的项即可。

$\binom {p+1}{i} = \binom p i + \binom p {i-1}$,所以 $p$ 加一只需要额外维护一下 $0\ldots lim-1$ 的求和即可。

注意特判 $p=1$ 的边界。代码咕了。

]]>
4 /archives/1599/#comments /feed/archives/1599/
「ZR 18 省选 3」题解 /archives/1598/ /archives/1598/ Sun, 06 Dec 2020 21:53:00 +0800 RainAir A. 树的染色

如果确定了某个点的颜色,我们肯定是要求这个点子树内和这个点不同的点的权值和尽量小。

我们设 $f_v$ 表示钦定 $v$ 是白色,子树内是黑色的点的权值和的最小值。

合并子树的时候钦定当前的根是白色,如果儿子 $x$ 和根同色子树和贡献 $a_x$,答案贡献 $f_x$;否则子树和贡献 $f_x$,答案贡献 $a_x$,背包合并即可。复杂度 $O(nm)$。

#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 = 1000+5;
const int MAXM = 5000+5;

std::vector<int> G[MAXN];
int n,a[MAXN];
int f[MAXN];
// 和 v 颜色不同的最小代价 (钦定 v 颜色为 0)
int g[2][MAXM];
bool flag;

inline void dfs(int v){
    if(G[v].empty()){
        f[v] = 0;
        return;
    }
    for(auto x:G[v]) dfs(x);
    int now = 0;CLR(g[now],0x3f);g[now][0] = 0;
    for(auto x:G[v]){
        CLR(g[now^1],0x3f);
        FOR(i,0,MAXM){
            if(i+a[x] < MAXM) g[now^1][i+a[x]] = std::min(g[now^1][i+a[x]],g[now][i]+f[x]);
            if(i+f[x] < MAXM) g[now^1][i+f[x]] = std::min(g[now^1][i+f[x]],g[now][i]+a[x]);
        }
        now ^= 1;
    }
    f[v] = 0x3f3f3f3f;
    FOR(i,0,a[v]) f[v] = std::min(f[v],g[now][i]);
    if(f[v] == 0x3f3f3f3f) flag = 0;
}

inline void Solve(){
    scanf("%d",&n);FOR(i,1,n) G[i].clear();
    FOR(i,2,n){
        int f;scanf("%d",&f);G[f].pb(i);
    }
    FOR(i,1,n) scanf("%d",a+i);
    flag = 1;dfs(1);
    puts(flag?"POSSIBLE":"IMPOSSIBLE");
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

B. 树形图求和

以某个点 $r$ 为根的内向树/外向树计数就是出度矩阵/入度矩阵(可以记成根的度数为 $0$ 的那个)减邻接矩阵,删掉第 $r$ 行第 $r$ 列的行列式。

如何求一条边的出现次数呢?用总次数减掉这条边不出现的次数,于是相当于要每次修改矩阵上的两个点(在同一行),然后求一下行列式。设这个矩阵为 $A$,记 $|A|$ 表示矩阵 $A$ 的行列式。

做法 1:伴随矩阵

记矩阵 $A$ 的代数余子式 $C_{i,j}$ 为删掉第 $i$ 行第 $j$ 列的行列式乘上 $(-1)^{i+j}$。

那么 $A$ 的伴随矩阵 $adj(A)=C^T$。

伴随矩阵有一个性质:$adj(A^{-1}) = \frac{A}{|A|}$,所以可以得到 $adj(A) = \frac{A^{-1}}{|A^{-1}|} = |A|A^{-1}$。(因为有 $|A|*|A^{-1}| = 1$)。

所以我们只需要写个矩阵求逆就能求出伴随矩阵了。

考虑我们如果修改了第 $i$ 行的某些值,如何快速计算新矩阵的行列式?暴力算是单次 $O(n^3)$ 的。

根据拉普拉斯展式,可以得到:

$$ \forall i ,|A| = \sum_{j=1}^n C_{i,j}A_{i,j} $$

所以我们就可以 $O(n)$ 求出来某行修改后的行列式;但是注意到这里只修改了 $O(1)$ 个位置,我们算一下增量就可以 $O(1)$ 求出修改某个位置后的矩阵行列式是啥了。

复杂度 $O(n^3+m)$。

做法 2:多项式

发现 $\sum_{i=1}^n w_i$ 其实就是 $\prod_{i=1}^n (1+w_ix)$ 的一次项系数,所以我们在 $\pmod {x^2}$ 的意义下做多项式运算就好了。

比较难定义的是除法,其实我们就是要求 $ax+b$ 的逆,设逆为 $cx+d$,可以得到 $(ax+b)(cx+d) = 1$,解方程可得 $c=-\frac{a}{b^2},d = \frac{1}{b}$,也就是说 $ax+b$ 的逆是 $-\frac{a}{b^2}x+\frac{1}{b}$,这样就可以转化为乘法了。

#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 = 300+5;
const int ha = 1e9 + 7;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int a[MAXN][MAXN],n,m;
int A[MAXN][MAXN],b[MAXN][MAXN];
// b: 伴随矩阵
// A: 原矩阵
// a: 消元用

struct Edge{
    int u,v,w;
    Edge(int u=0,int v=0,int w=0) : u(u),v(v),w(w) {}
}e[200000+5];

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

inline int Gauss(){
    FOR(i,1,n) b[i][i] = 1;
    int ans = 1;
    FOR(i,1,n){
        int t = -1;
        FOR(j,i,n) if(a[j][i]){t = j;break;}
        if(t != i) std::swap(a[i],a[t]),ans = ha-ans,std::swap(b[i],b[t]);
        ans = 1ll*ans*a[i][i]%ha;
        int inv = qpow(a[i][i]);
        FOR(j,1,n) a[i][j] = 1ll*a[i][j]*inv%ha,b[i][j] = 1ll*b[i][j]*inv%ha;
        FOR(j,1,n){
            if(j == i) continue;
            int t = a[j][i];
            FOR(k,1,n){
                add(a[j][k],ha-1ll*a[i][k]*t%ha);
                add(b[j][k],ha-1ll*b[i][k]*t%ha);
            }
        }
    }
    FOR(i,1,n) FOR(j,1,n) b[i][j] = 1ll*b[i][j]*ans%ha;
    return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,m){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);e[i] = Edge(u,v,w);
        add(a[u][v],ha-1);
        add(a[u][u],1);
    }
    FOR(i,1,n) a[n][i] = a[i][n] = 0;
    --n;
    FOR(i,1,n) FOR(j,1,n) A[i][j] = a[i][j];
    Gauss();
    int ans = 0;
    FOR(i,1,m){
        int u = e[i].u,v = e[i].v,w = e[i].w;
        if(u == n+1) continue;
        int c = (b[u][u]+ha-b[v][u])%ha;
        /*
        add(c,ha-b[u][u]);
        if(v != n+1){
            add(c,b[u][v]);
        }
        c = ha-c;add(c,all);*/
        add(ans,1ll*c*w%ha);
    }
    printf("%d\n",ans);
    return 0;
}

C. 波波老师

建后缀自动机,只出现一次的节点一定是后缀树上的叶子节点。

考虑对于后缀 $i$ ,我们求出最小的 $f_i$,满足 $[i,i+f_i-1]$ 是这个点所代表的区间,相当于我们要对区间 $[i,i+f_i-1]$ 对 $f_i$ 取 $\min$,然后对 $[i+f_i,n]$ 对 $f_{i}+1,f_{i}+2,\ldots$ 这个等差数列取 $\min$。

发现我们可以先做完对 $[i,i+f_i-1]$ 取 $\min$,然后再一遍递推过来($ans_{i}$ 与 $ans_{i-1}+1$ 取 $\min$),现在相当于只需要快速实现区间对一个数取 $\min$。

线段树可以得到 $O(n \log n)$ 的复杂度。

桶排+并查集可以得到 $O(n \alpha(n))$ 的复杂度。

如果你发现对于 $i<j$,一定有 $f_i \leq f_j$,那么就可以用单调队列维护这个东西,复杂度 $O(n)$。

注意 SAM 数组要开 2 倍空间(

#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 = 5e6 + 5;

int ch[MAXN<<1][5],fail[MAXN<<1],len[MAXN<<1],tot = 1,las = 1;
int id[MAXN];
char str[MAXN];
bool vis[MAXN<<1];
int n;

inline int insert(int c){
    int p = las,np = las = ++tot;len[np] = len[p]+1;
    for(;p&&!ch[p][c];p=fail[p]) ch[p][c] = np;
    if(!p) fail[np] = 1;
    else{
        int q = ch[p][c];
        if(len[q] == len[p]+1) fail[np] = q;
        else{
            int nq = ++tot;FOR(i,0,4) ch[nq][i] = ch[q][i];len[nq] = len[p]+1;fail[nq] = fail[q];
            fail[q] = fail[np] = nq;
            for(;p&&ch[p][c]==q;p=fail[p]) ch[p][c] = nq;
        }
    }
    return np;
}

int ans[MAXN];
int f[MAXN];

int main(){
    scanf("%s",str+1);n = strlen(str+1);
    ROF(i,n,1) id[i] = insert(str[i]-'a');
    FOR(i,1,tot) vis[fail[i]] = 1;
    FOR(i,1,n){
        if(vis[id[i]]) f[i] = 1e9;
        else f[i] = len[fail[id[i]]]+1;
//        DEBUG(f[i]);
    }
    std::deque<int> q;
    FOR(i,1,n) ans[i] = 1e9;
    FOR(i,1,n){
        while(!q.empty() && f[q.back()] >= f[i]) q.pop_back();
        q.pb(i);
        ans[i] = f[q[0]];
        while(!q.empty() && q[0]+f[q[0]]-1 <= i) q.pop_front();
    }
    FOR(i,2,n) ans[i] = std::min(ans[i],ans[i-1]+1);
    LL res = 0;FOR(i,1,n) res += ans[i];
    printf("%lld\n",res);
    return 0;
}
]]>
1 /archives/1598/#comments /feed/archives/1598/
AGC038 部分题解 /archives/1596/ /archives/1596/ Fri, 20 Nov 2020 15:38:00 +0800 RainAir E

题意

有一个随机数生成器,生成 $[0,n-1]$ 之内的数,生成第 $i$ 个数的概率为 $\frac{A_i}{S}$,其中 $S=\sum_{i=1}^n A_i$。

当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成,求期望生成次数,对大质数取模。

题解

设第 $i$ 个数最后一次被随机到的时间为 $t_i$,答案就是 $\max t_i$ 的期望。

限制所有都要完成一般都不好做,考虑 $min-max$ 容斥变成枚举一个集合 $S$ ,求 $\min_{i \in S} t_i$ 的期望。

枚举集合后,问题变成求存在 $S$ 内某一个元素被随机 $b_i$ 次这个事件发生的期望时间。我们发现这样还是有可能随机到 $S$ 外的元素的,一个经典套路是算出期望多少次能操作一次 $S$ 内的元素,然后转化为只考虑 $S$ 内元素操作的问题,最后乘上去即可。可以发现这个期望次数为 $\frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i}$。

现在问题在于给定一个集合 $S$ ,在 $S$ 内随机,求存在一个数满足条件的期望时间。首先根据:

$$ \sum_{i \geq 0} P[X=i]i = \sum_{i \geq 0} P[X \geq i] $$

可以得到,我们只需要对于每个时间 $T$ 求出在 $T$ 时间还没结束的概率,求和即可。

我们考虑如何暴力的计算:先枚举在时间 $T$ 结束,接下来枚举序列 $b_i$ 表示集合中元素 $i$ 被随机到的次数,需要满足 $\forall i \in S,b_i < B_i$,$\sum_{i \in S} b_i = T$,这样一个序列的概率就是 $\prod_{i \in T} (\frac{A_i}{\sum_{i \in S} A_i})^{b_i}\frac{T!}{\prod_{i \in S} b_i!}$。

所以答案是:

$$ \sum_{S \subseteq [n],S \neq \emptyset} (-1)^{|S|-1}\frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i} \sum_{T=0}^{\sum_{i \in S} (b_i-1) + 1} \sum_{\{b\},\sum_{i \in S} b_i = T} \prod_{i \in T} (\frac{A_i}{\sum_{i \in S} A_i})^{b_i}\frac{T!}{\prod_{i \in S} b_i!} $$

稍加整理可得

$$ \sum_{S \subseteq [n],S \neq \emptyset} (-1)^{|S|-1} \frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i} \sum_{T=0}^{\sum_{i \in S} (b_i-1) + 1} T!(\frac{1}{\sum_{i \in S} A_i})^T \sum_{\{b\},\sum_{i \in S} b_i = T} \prod_{i \in S} \frac{A_i^{b_i}}{b_i!} $$

于是可以考虑对这个 dp:发现最终答案系数只和 $\sum b_i,\sum A_i$ 有关,我们带着容斥系数 dp,设 $f_{i,j,k}$ 表示考虑前 $i$ 个数,$\sum b_i = j,\sum A_i = k$ 的答案,转移的时候枚举这个位置选或者不选,选的话枚举 $b_i$ 是多少,可以得到转移式子:

$$ f_{i,j,k} = f_{i-1,j,k}-\sum_{x=0}^{B_i-1}\frac{A_i^x}{x!} f_{i-1,j-A_i,k-x} $$

然后最后把应该乘的系数乘上去就好了。

假设 $n,\sum A,\sum B$ 同阶,看起来时间复杂度是 $O(n^4)$ 的,但是实际分析一下:复杂度是:

$$ \begin{aligned} \sum_{i=1}^n \sum_{j=0}^{\sum A_i} \sum_{k=0}^{\sum B_i } \sum_{l=0}^{B_i-1} 1 &= \sum_{i=1}^n \sum_{l=0}^{B_i-1} (\sum A_i) (\sum B_i)\\ &=(\sum A_i)(\sum B_i)^2 \\ &= O(n^3) \end{aligned} $$

所以可以通过此题。代码可能和博客定义的是反的,感性理解一下(

#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 = 400+5;
const int ha = 998244353;
int n,a[MAXN],b[MAXN];
int f[MAXN][MAXN];
int sma,smb;

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int fac[MAXN],inv[MAXN];

int main(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d%d",a+i,b+i);
    FOR(i,1,n) sma += a[i],smb += b[i]-1;
    f[0][0] = -1;
    FOR(i,1,n){
        ROF(j,sma,a[i]){
            ROF(k,smb,0){
                ROF(x,std::min(k,b[i]-1),0){
                    add(f[j][k],(ha-1ll*f[j-a[i]][k-x]*inv[x]%ha*qpow(a[i],x)%ha)%ha);
                }
            }
        }
    }
    int ans = 0;
    FOR(j,0,sma) FOR(k,0,smb){
        int gx = f[j][k];
        gx = 1ll*gx*fac[k]%ha*sma%ha;
        gx = 1ll*gx*qpow(qpow(j,k+1))%ha;
        add(ans,gx);
    }
    printf("%d\n",ans);
    return 0;
}

F

题意

给定两个长度为 $n$ 的排列 $P,Q$,要求你构造两个长度为 $n$ 的排列 $A,B$,满足:

  • $A_i$ 取值 $\{i,P_i\}$
  • $B_i$ 取值 $\{i,Q_i\}$

要求 $A,B$ 不同的位置尽量多,求出这个最多的位置个数。

题解

将 $P,Q$ 分成若干个环,同一个环要么都取 $i$ 要么都取 $P_i/Q_i$。

讨论一下 $P_i,Q_i$ 之间的关系,可以得到以下情况:

  • $P_i=Q_i=i$:无论如何都相等。
  • $P_i,Q_i \neq i,P_i \neq Q_i$:同时不转相等。
  • $P_i=i,Q_i \neq i$:$B_i$ 不转相等。
  • $P_i \neq i,Q_i = i$:$A_i$ 不转相等。
  • $P_i=Q_i,P_i,Q_i \neq i$:同时转相等。

网络流。把 $B$ 倒过来就行了。

#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 = 2e5 + 5;

struct Edge{
    int to,w,nxt;
}e[MAXN<<4];
int head[MAXN],cnt=1,cur[MAXN],dep[MAXN];

inline void add(int u,int v,int w){
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,0,head[v]};head[v] = cnt;
}

int S,T,N;

inline bool bfs(){
    FOR(i,0,N) cur[i] = head[i],dep[i] = 0;
    std::queue<int> q;q.push(S);dep[S] = 1;
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].w > 0 && !dep[e[i].to]){
                dep[e[i].to] = dep[v]+1;
                q.push(e[i].to);
            }
        }
    }
    return dep[T];
}

inline int dfs(int v,int lim=1e9){
    if(v == T) return lim;
    if(!lim) return 0;
    int ans = 0;
    for(int &i = cur[v];i;i = e[i].nxt){
        if(e[i].w > 0 && dep[e[i].to] == dep[v]+1){
            int t = dfs(e[i].to,std::min(lim,e[i].w));
            if(t > 0){
                ans += t;
                e[i].w -= t;
                e[i^1].w += t;
                lim -= t;
                if(!lim) break;
            }
        }
    }
    return ans;
}

inline int Dinic(){
    int ans = 0,flow;
    while(bfs()) while((flow=dfs(S))) ans += flow;
    return ans;
}

int n,p[MAXN],q[MAXN];
bool vis[MAXN];
int belp[MAXN],belq[MAXN];

inline void dfs(int v,int now,int p[],int bel[]){
    vis[v] = 1;bel[v] = now;
    if(vis[p[v]]) return;
    dfs(p[v],now,p,bel);
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",p+i),++p[i];
    FOR(i,1,n) scanf("%d",q+i),++q[i];
    FOR(i,1,n) if(!vis[i]) ++N,dfs(i,N,p,belp);
    FOR(i,1,n) vis[i] = 0;
    FOR(i,1,n) if(!vis[i]) ++N,dfs(i,N,q,belq);
    S = N+1;T = N+2;N = T;
    int ans = n;
    FOR(i,1,n){
        if(p[i] == q[i]){
            if(p[i] == i){
                ans--;continue;
            }
            else{
                add(belp[i],belq[i],1);
                add(belq[i],belp[i],1);
            }
        }
        else{
            if(p[i] == i && q[i] != i){
                add(belq[i],T,1);
            }
            else if(p[i] != i && q[i] == i){
                add(S,belp[i],1);
            }
            else{
                add(belq[i],belp[i],1);
            }
        }
    }
    printf("%d\n",ans-Dinic());
    return 0;
}
/*
p: 割左边=不转 右边=转
q反过来 
何时答案会-1:
p[i]=q[i]=i 无论如何都会-1
p[i],q[i] != i 同时不转
p[i]=i,q[i]!=i 2不转
p[i]!=i,q[i]=i 1不转
p[i]=q[i],p[i],q[i]!=i  同时转
*/
]]>
1 /archives/1596/#comments /feed/archives/1596/
CF1434D Roads and Ramen /archives/1594/ /archives/1594/ Fri, 20 Nov 2020 14:53:40 +0800 RainAir 题意

给出一个 $n$ 个点的数,边有边权,支持翻转一条边的边权,以及求最长的满足路径上边权异或和是 $0$ 的路径。

题解

相当于子树翻转,求相同颜色的直径。

赛时被卡常做法:直接动态维护直径端点,合并的时候暴力枚举合并。

一个比较优秀的做法:转括号序后两个点的距离就是括号匹配后失配的括号数量。先考虑如何快速求区间内失配的括号数量:考虑维护失配的右括号和左括号数量,记为 $a,b$。合并的时候设左儿子的 $a,b$ 为 $la,lb$ ,右儿子为 $ra,rb$。那么新区间的 $a = la+\min(0,ra-lb),b = rb+\min(lb-ra,0)$,路径长度就是

$$ \begin{aligned} la+rb+\min(0,ra-lb)+\min(lb-ra,0) \\ =\max(la+rb+ra-lb,la+rb+lb-ra)\\ =\max((la-lb)+(ra+rb),(la+lb)+(rb-ra))\\ \end{aligned} $$

分开维护这四个括号的最大值即可。也就是分类讨论一下是否跨过当前区间中点即可。

一个更优秀的做法:猜想答案一定有一个端点是直径端点,于是直接找出一条直径,以两个端点为根分开建树,线段树维护即可。

#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 = 5e5 + 5;
int n;

struct Edge{
    int to,w,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

struct DS{
    int mx0[MAXN<<2],mx1[MAXN<<2],tag[MAXN<<2];
    int dfn[MAXN],nfd[MAXN],dep[MAXN],col[MAXN],sz[MAXN],ts = 0;
    #define lc ((x)<<1)
    #define rc ((x)<<1|1)

    inline void pushup(int x){
        mx0[x] = std::max(mx0[lc],mx0[rc]);
        mx1[x] = std::max(mx1[lc],mx1[rc]);
    }

    inline void build(int x,int l,int r){
        if(l == r){
            mx0[x] = mx1[x] = 0;
            if(col[nfd[l]]) mx1[x] = dep[nfd[l]];
            else mx0[x] = dep[nfd[l]];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc,l,mid);build(rc,mid+1,r);
        pushup(x);
    }

    inline void cover(int x){
        tag[x] ^= 1;std::swap(mx0[x],mx1[x]);
    }

    inline void pushdown(int x){
        if(tag[x]){
            cover(lc);cover(rc);tag[x] = 0;
        }
    }

    inline void modify(int x,int l,int r,int L,int R){
        if(l == L && r == R) return cover(x);
        int mid = (l + r) >> 1;pushdown(x);
        if(R <= mid) modify(lc,l,mid,L,R);
        else if(L > mid) modify(rc,mid+1,r,L,R);
        else modify(lc,l,mid,L,mid),modify(rc,mid+1,r,mid+1,R);
        pushup(x);
    }

    inline void dfs(int v,int fa=0){
        dfn[v] = ++ts;nfd[ts] = v;
        dep[v] = dep[fa]+1;sz[v] = 1;
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].to == fa) continue;
            col[e[i].to] = col[v]^e[i].w;
            dfs(e[i].to,v);sz[v] += sz[e[i].to];
        }
    }
    
    inline void update(int u,int v){
        if(dep[u] > dep[v]) std::swap(u,v);
        modify(1,1,n,dfn[v],dfn[v]+sz[v]-1);
    }
}ds1,ds2;

inline int get(int rt){
    int mx = 0,ps = -1;
    std::function<void(int,int,int)> dfs = [&](int v,int fa,int dep){
        if(dep > mx){
            mx = dep;
            ps = v;
        }
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].to == fa) continue;
            dfs(e[i].to,v,dep+1);
        }
    };
    dfs(rt,0,1);
    return ps;
}

int uu[MAXN],vv[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n-1){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);uu[i] = u;vv[i] = v;
        auto add = [&](int u,int v,int w){
            e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
            e[++cnt] = (Edge){u,w,head[v]};head[v] = cnt;
        };
        add(u,v,w);
    }
    int q;scanf("%d",&q);
    int r1 = get(1),r2 = get(r1);
    ds1.dfs(r1);ds1.build(1,1,n);
    ds2.dfs(r2);ds2.build(1,1,n);
    while(q--){
        int x;scanf("%d",&x);
        ds1.update(uu[x],vv[x]);ds2.update(uu[x],vv[x]);
        printf("%d\n",std::max(ds1.mx0[1],ds2.mx0[1])-1);
    }
    return 0;
}
]]>
0 /archives/1594/#comments /feed/archives/1594/
gym100801I Insider's Information /archives/1592/ /archives/1592/ Fri, 20 Nov 2020 14:41:57 +0800 RainAir 题意

要求构造大小为 $n$ 的排列,要求至少 $\lceil \frac{m}{2} \rceil$ 条限制:第 $i$ 条限制 $(a_i,b_i,c_i)$ 形如排列中 $b_i$ 的位置要在 $a_i$ 和 $c_i$ 之间。

题解

神仙题。

这个题一般确定排列的方法都不能用了,我们考虑这个在两个数中间的限制:考虑用按照顺序每次将一个数放到前面或者后面的方式。

因为保证有解,所以肯定能搞出来一个答案,也就肯定有一种放置顺序。我们假设我们知道了放置顺序,考虑如何去构造出答案,分类讨论一下:

假设一个限制中第一个被放入的数是 $a_i$,那么如果下一个数是 $b_i$,就要和 $a_i$ 放在同侧,否则就要放在不同侧。

所以我们加入一个点的时候,算出它放在左边和右边分别能满足多少限制,选择最大的那个即可。这样相当于将所有限制分成若干组,每一组至少取了一半,所以满足题目限制。

现在问题在于如何找到这个放置顺序:发现如果在三元组内是 $b_i$ 先出现,那么怎么放置都不满足条件,所以我们要求出的序列形如要求 $a_i$ 或 $c_i$ 出现在 $b_i$ 之前,用类似拓扑排序的方法即可。

#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 = 2e5 + 5;
int n,m,a[MAXN],b[MAXN],c[MAXN];
std::vector<int> G[MAXN],lim[MAXN];
int deg[MAXN];
int dfn[MAXN],p[MAXN];
bool zt[MAXN];// left=0 right=1
bool vis[MAXN];

int main(){
#ifndef RainAir
    freopen("insider.in","r",stdin);
    freopen("insider.out","w",stdout);
#endif
    scanf("%d%d",&n,&m);
    FOR(i,1,m){
        scanf("%d%d%d",a+i,b+i,c+i);
        G[a[i]].pb(i);
        G[c[i]].pb(i);
        ++deg[b[i]];
    }
    std::queue<int> q;int ts = 0;
    FOR(i,1,n) if(!deg[i]) q.push(i);
    while(!q.empty()){
        int v = q.front();q.pop();
        dfn[v] = ++ts;
        for(auto x:G[v]){
            if(vis[x]) continue;
            vis[x] = 1;
            if(!--deg[b[x]]){
                q.push(b[x]);
            }
        }
    }
    FOR(i,1,m) assert(!(dfn[b[i]] < dfn[a[i]] && dfn[b[i]] < dfn[c[i]]));
    FOR(i,1,n) p[dfn[i]] = i;
    FOR(i,1,m) if(dfn[a[i]] > dfn[c[i]]) std::swap(a[i],c[i]);
    FOR(i,1,m) lim[b[i]].pb(i),lim[c[i]].pb(i);
    FOR(i,1,n){
        int cnt[2];CLR(cnt,0);
        int v = p[i];
        for(auto x:lim[v]){
            if(v == b[x]){
                if(dfn[c[x]] < dfn[b[x]]) continue;
                cnt[zt[a[x]]]++;
            }
            if(v == c[x]){
                if(dfn[b[x]] < dfn[c[x]]) continue;
                cnt[zt[a[x]]^1]++;
            }
        }
        zt[v] = cnt[0] > cnt[1] ? 0 : 1;
    }
    std::vector<int> v1,v2;
    FOR(i,1,n){
        if(zt[p[i]]) v2.pb(p[i]);
        else v1.pb(p[i]);
    }
    std::reverse(all(v2));
    for(auto x:v1) printf("%d ",x);
    for(auto x:v2) printf("%d ",x);
    puts("");
    return 0;
}
]]>
0 /archives/1592/#comments /feed/archives/1592/
降智比赛题解 /archives/1589/ /archives/1589/ Tue, 10 Nov 2020 21:51:00 +0800 RainAir A. 气球

设 $f_i$ 表示最后一次选择的是 $i$ 的答案,暴力转移是枚举一个 $j$,判断 $c_i,c_j$ 是否相同对应乘上系数转移就行了。

我们记 $mx_i$ 表示当前考虑完的所有 $f$ 的时候 $c_k = i$ 的 $f_k$ 的最大值,那么我们转移只需要知道 $mx_{c_i}$ 和剩下的数的最大值就行了,分别记录最大值和次大值是什么即可。

#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
#define int LL
const int MAXN = 1e5 + 5;
int n,q,v[MAXN],c[MAXN];
LL val[MAXN],mx,cmx;

signed main(){
    scanf("%lld%lld",&n,&q);
    FOR(i,1,n) scanf("%lld",v+i);
    FOR(i,1,n) scanf("%lld",c+i);
    while(q--){
        LL a,b;scanf("%lld%lld",&a,&b);
        FOR(i,0,n) val[i] = -1e18;
        mx = 0;cmx = 1;
        LL ans = 0;
        FOR(i,1,n){
            LL f = std::max(b*v[i],val[c[i]]+a*v[i]);
            f = std::max(f,(mx==c[i]?val[cmx]:val[mx])+b*v[i]);
            ans = std::max(ans,f);
            val[c[i]] = std::max(val[c[i]],f);
            if(mx == c[i]) continue;
            if(val[c[i]] > val[mx]) cmx = mx,mx = c[i];
            else if(val[c[i]] > val[cmx]) cmx = c[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

B. 游戏

可以证明:一定是取了若干个整行+一个散行。

反证:假设两行的元素分别是 $a,b$,设分别取到了 $i,j$,那么我们只需要证明:

$$ \begin{aligned} a_{i+1}-b_j \leq a_i+b_j\\ b_{j+1}-a_i \leq a_i + b_j \end{aligned} $$

整理可以得到:

$$ \begin{aligned} a_{i+1}-a_i \leq 2b_j\\ b_{j+1}-b_j \leq 2a_i \end{aligned} $$

而由于 $a,b$ 是从大到小排序的,所以有 $a_{i+1}-a_i \leq 0,b_{j+1}-b_{j} \leq 0$,得证。

但是注意直接去取和最小的整行是不对的,因为可能存在和很小但是前面很大的可能,比如

1e9 1e9 1e9
2e9 1e9 1

取 $4$ 个数,如果直接贪心会全取第一行并且取第二行第一个,是 $5 \times 10^9$,然而实际上应该是全取第二行再取第一行第一个,是 $4 \times 10^9 + 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 = 1000+5;
int n,m,k;
int a[MAXN][MAXN];
LL sm[MAXN];

int main(){
    scanf("%d%d%d",&n,&m,&k);
    FOR(i,1,n) FOR(j,1,m) scanf("%d",&a[i][j]),sm[i] += a[i][j];
    if(k == n*m){
        LL sm = 0;
        FOR(i,1,n) FOR(j,1,m) sm += a[i][j];
        printf("%lld\n",sm);
        return 0;
    }
    FOR(i,1,n) std::sort(a[i]+1,a[i]+m+1),std::reverse(a[i]+1,a[i]+m+1);
    LL ans = 1e18;
    FOR(i,1,n){
        LL gx = 0;
        FOR(j,1,k%m) gx += a[i][j];
        std::vector<LL> S;
        FOR(j,1,n) if(j != i) S.pb(sm[j]);
        std::sort(all(S));
        FOR(i,0,k/m-1) gx += S[i];
        ans = std::min(ans,gx);
    }
    printf("%lld\n",ans);
    return 0;
}
// 选择最大值最小的一行 删除最大值

C. 树

我们可以补集转化计算相交的方案数,两个链有交当且仅当某一个链的 $\text{lca}$ 在另一个链上。枚举在哪个链上,相当于要处理一下以某个点为 $\text{lca}$,长度为 $p/q$ 的链的个数和经过某个点,长度为 $p/q$ 的链的个数。但是注意这样会算重两条链的 $\text{lca}$ 互相包含的情况,不难发现这种情况一定是两条链 $\text{lca}$ 相同的情况,也可以类似算出来。

需要卡常:能预处理的就不要每次都算。

#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 = 3000+5;
int n,p,q;

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],_cnt;

inline void add(int u,int v){
    e[++_cnt] = (Edge){v,head[u]};head[u] = _cnt;
    e[++_cnt] = (Edge){u,head[v]};head[v] = _cnt;
}

LL f[2][MAXN],g[2][MAXN];
int dep[MAXN];

inline void dfs1(int v,int fa=0){
    dep[v] = dep[fa]+1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dfs1(e[i].to,v);
    }
}

bool flag = 0;
int cnt[MAXN];

inline void dfs(int v,int d=0,int fa=0){
    ++cnt[d];
    for(int i = head[v];i;i = e[i].nxt){
        if((flag||dep[e[i].to] > dep[v]) && e[i].to != fa) dfs(e[i].to,d+1,v);
    }
}

inline void gao1(int rt,int p,LL &f){
    CLR(cnt,0);dfs(rt);
    FOR(i,0,p) f += 1ll*cnt[i]*(cnt[p-i]-(i==p-i));
    for(int i = head[rt];i;i = e[i].nxt){
        if(dep[e[i].to] > dep[rt]){
            CLR(cnt,0);dfs(e[i].to,1);
            FOR(i,0,p) f -= 1ll*cnt[i]*(cnt[p-i]-(i==p-i));
        }
    }
}

inline void gao2(int rt,int q,LL &g){
    CLR(cnt,0);dfs(rt);
    FOR(i,0,q) g += 1ll*cnt[i]*(cnt[q-i]-(i==q-i));
    for(int i = head[rt];i;i = e[i].nxt){
        CLR(cnt,0);dfs(e[i].to,1,rt);
        FOR(i,0,q) g -= 1ll*cnt[i]*(cnt[q-i]-(i==q-i));
    }
}

int main(){
//    freopen("C.in","r",stdin);
//    freopen("C.out","w",stdout);
    scanf("%d%d%d",&n,&p,&q);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);
    }
    dfs1(1);
    // f: lca=i
    // g: 经过 i
    // 0: p
    // 1: q
    FOR(i,1,n) gao1(i,p,f[0][i]),gao1(i,q,f[1][i]);flag = 1;
    FOR(i,1,n) gao2(i,p,g[0][i]),gao2(i,q,g[1][i]);
    LL s1 = 0,s2 = 0;
    FOR(i,1,n) s1 += f[0][i],s2 += f[1][i];
    LL ans = 0;
    ans = s1*s2;
    FOR(i,1,n) ans -= f[0][i]*g[1][i];
    FOR(i,1,n) ans -= g[0][i]*f[1][i];
    FOR(i,1,n) ans += f[0][i]*f[1][i];
    printf("%lld\n",ans);
    return 0;
}

D. 小号

最大的构造方案一定是 2 3 4 ... n 1,答案的上界是 $\frac{n(n-1)}{2}$。

我们找到最小的 $t$,满足 $\frac{t(t-1)}{2} \geq s$,设 $r = \frac{t(t-1)}{2}-s$(也就是要减少的数量),那么一定要有 $r \leq t-1$,我们先将前 $t$ 个位置按照 2 3 4 ... t 1 放置,后面的 $a_i=i$。我们考虑先交换 $a_1$ 和 $a_t$,这样可能会让 $r--$ (如果 $t$ 是偶数),仍然有 $r \leq t-1$,然后只需要对应交换 $a_1$ 和 $a_r$ 就好了,这样会让答案减少 $r-1$,交换的位置 $\leq t$,不会超过 $n$。

构造题还是要考虑如何构造最大值。。然后去减少。这题考虑增加就不是很简单,还要努力分析一下缺少的个数来观察是否可以多交换一些东西扩大操作空间。

#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 = 1e5 + 5;
int n,a[MAXN];
LL s;

int main(){
    scanf("%d%lld",&n,&s);
    if(s > 1ll*n*(n-1)/2){
        puts("nO 5oLuTi0N");
        return 0;
    }
    LL t = 1;
    while(t*(t-1)/2 < s) ++t;
    FOR(i,1,t-1) a[i] = i+1;a[t] = 1;
    FOR(i,t+1,n) a[i] = i;
    LL r = t*(t-1)/2-s;
    if(r){
        // r < t
        r -= !((t&1));
        std::swap(a[1],a[t]);
        // r <= t
        std::swap(a[1],a[r+1]);
    }
    FOR(i,1,n) printf("%d%c",a[i]," \n"[i==n]);
    return 0;
}
]]>
0 /archives/1589/#comments /feed/archives/1589/
CF 1437 题解 /archives/1583/ /archives/1583/ Thu, 29 Oct 2020 19:10:12 +0800 RainAir A

判断一下前面能否空出来就就行,也就是 $l \geq r-l+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

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int l,r;scanf("%d%d",&l,&r);
        puts(l >= r-l+1 ? "YES" : "NO");
    }
    return 0;
}

B

相当于不能有子串 1100

那么如果有 11 肯定在后面有一个地方有 00 (反证),所以每次操作最多可以消去两个这样的连续的东西,求出有多少个相邻相同的位置 $x$,答案就是 $\lceil \frac{x}{2} \rceil$。

#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 = 1e5 + 5;
char str[MAXN];

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        scanf("%s",str+1);
        int ans = 0;
        FOR(i,2,n) if(str[i] == str[i-1]) ans++;
        ans = (ans+1)>>1;
        printf("%d\n",ans);
    }
    return 0;
}

C

首先可以发现一个东西:将匹配方式连边,一定存在一种分配方式使得最优解没有包含关系的线段,因为包含关系可以通过交换变成相交,并且代价不变。

排序后可以设 $f_{i,j}$ 表示考虑了前 $i$ 个数,最小的 $j$ 满足 $j$ 开始后面一段数字都没有被用过的代价,转移直接枚举下一个填啥就行了。

#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 = 600+5;
int n,a[MAXN];
bool vis[MAXN];
int f[2][MAXN],now;

int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        FOR(i,1,n) scanf("%d",a+i);
        std::sort(a+1,a+n+1);
        CLR(f,0x3f);
        f[now = 0][0] = 0;
        FOR(i,1,n){
            CLR(f[now^1],0x3f);
            FOR(j,0,3*n){
                if(f[now][j] == 0x3f3f3f3f) continue;
                FOR(k,j+1,3*n){
                    f[now^1][k] = std::min(f[now^1][k],f[now][j]+std::abs(a[i]-k));
                }
            }
            now ^= 1;
        }
        int ans = 1e9;
        FOR(i,1,3*n) ans = std::min(ans,f[now][i]);
        printf("%d\n",ans);
    }
    return 0;
}

D

感性理解一下,我们每次取出深度最小的点,接上连续的一段递增序列作为它的后继即可。

#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 = 2e5 + 5;
int n,a[MAXN];

int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i);
        std::priority_queue<P,std::vector<P>,std::greater<P> > q;
        q.push(MP(0,1));int p = 2;
        int ans = 0;
        while(!q.empty()){
            int dep = q.top().fi;q.pop();ans = std::max(ans,dep);
            int las = -1;std::vector<int> v;
            while(p <= n && las <= a[p]) las = a[p++],v.pb(las);
            for(auto x:v) q.push(MP(dep+1,x));
        }
        printf("%d\n",ans);
    }
    return 0;
}

E

如果没有不能选的限制就是经典 dp:我们观察两个位置 $i<j$ 能同时不改变的条件是 $a_j-a_i-1 \geq j-i-1$,也就是 $a_i-i \leq a_j-j$,最多能不修改的数也就是设 $b_i=a_i-i$,$b_i$ 的非严格最长上升子序列长度。

这个题限定某些数不能改变,先判完无解后相当于变成了强制选取某些位置的最长上升子序列,对于每段分别做即可。

注意这里 infty 开大点。。要不然判无解会判错。。。真正考试对拍的时候还是多试试 corner case 吧。。

#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 = 5e5 + 5;
int n,k;
LL a[MAXN];
std::vector<int> S;
std::vector<LL> SS;

struct BIT{
    #define lowbit(x) ((x)&(-(x)))
    int tree[MAXN],ts[MAXN],now;

    inline void reset(){
        ++now;
    }

    inline void add(int pos,int x){
        while(pos < MAXN){
            if(ts[pos] != now) tree[pos] = 0,ts[pos] = now;
            tree[pos] = std::max(tree[pos],x);
            pos += lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;if(!pos) return 0;
        while(pos){
            if(ts[pos] != now) tree[pos] = 0,ts[pos] = now;
            res = std::max(res,tree[pos]);
            pos -= lowbit(pos);
        }
        return res;
    }
}bit;

int b[MAXN];

int main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d",a+i);
    a[0] = -1e18;a[n+1] = 1e18;
    FOR(i,0,n+1) SS.pb(a[i]-i);
    std::sort(all(SS));SS.erase(std::unique(all(SS)),SS.end());
    FOR(i,0,n+1) b[i] = std::lower_bound(all(SS),a[i]-i)-SS.begin()+1;
    S.pb(0);
    FOR(i,1,k){
        int x;scanf("%d",&x);
        S.pb(x);
    }
    S.pb(n+1);
    FOR(i,1,(int)S.size()-1){
        if(a[S[i]]-a[S[i-1]] < S[i]-S[i-1]){
            puts("-1");
            return 0;
        }
    }
    int ans = 0;
    FOR(i,1,(int)S.size()-1){
        auto work = [&](int l,int r){
            bit.reset();
            int res = 0;
            FOR(i,l,r){
                if(b[i] < b[l]) continue;
                res = bit.query(b[i])+1;
                bit.add(b[i],res);
            }
            return r-l+1-res;
        };
        ans += work(S[i-1],S[i]);
    }
    printf("%d\n",ans);
    return 0;
}

F

居然让我想了一会。。不过也是简单题

直接做我们可能需要记录哪些数选了,状态会爆炸。我们考虑不断往后面加数,如果这个序列的最大值确定了,那么这个序列不改变最大值的前提下的最大长度就确定了,如果知道了目前长度,我们就能知道不改变最大值前提下这个位置的数有多少种可能。

于是设 $f_{i,j}$ 表示放了 $i$ 个数,最大值是 $j$ 的方案数,预处理 $las_i$ 表示最大值是 $i$ 的时候序列的最长长度,$nxt_i$ 表示最大值是 $i$ 要改变最大值可以放的最小的数,$cnt_i$ 表示值为 $i$ 的数的个数,转移:

  • 不改变最大值:$f_{i,j}\times (las_j-i+1) \to f_{i+1,j}$
  • 改变最大值:$f_{i,j}\times cnt_k \to f_{i+1,k}(k \geq nxt_j)$

用一些前缀和技巧可以优化到 $O(n^2)$。

看了一个比较 nb 的做法,大概是我们 dp 的时候只在放满的时候转移(也就是最大值为 $j$ 的时候我们只考虑状态 $f_{las_j,j}$),这个就是设 $f_i$ 表示最大值为 $i$ 的方案数,这样长度就是 $las_i+1$,转移的时候枚举上一次的最大值,乘上一个系数选进去就行了。

$$ \begin{aligned} f_i &= \sum_j f_j\binom{n-las_j-2}{las_i-las_j-1}(las_i-las_j-1)!\\ &= \frac{1}{(n-las_i-1)}\sum_j f_j (n-las_j-2)! \end{aligned} $$

然后前缀和优化一下就 $O(n)$ 了。还是要考虑大多数 dp 状态都是无用的,只对真正有用的决策即可。

#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 = 5000+5;
const int ha = 998244353;
int a[MAXN],n;
int f[2][MAXN],cf[MAXN];
// 选了 i 个数  最大值是 j
std::vector<int> S;
int las[MAXN];// 选了 i 之后 还有几个数可以放
int nxt[MAXN];// 选了 i 之后 下一个必须选啥
int cnt[MAXN];

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i);
    std::sort(a+1,a+n+1);
    FOR(i,1,n) S.pb(a[i]);S.erase(std::unique(all(S)),S.end());
    FOR(i,1,n) cnt[std::lower_bound(all(S),a[i])-S.begin()+1]++;
    int m = S.size();
    FOR(i,1,m){
        las[i] = las[i-1];
        while(las[i]+1 <= n && a[las[i]+1]*2 <= S[i-1]) las[i]++;
    }
    nxt[0] = 1;
    FOR(i,1,m){
        nxt[i] = -1;
        FOR(j,i+1,m){
            if(S[i-1]*2 <= S[j-1]) {nxt[i] = j;break;}
        }
    }
    int now = 0;f[now][0] = 1;
    FOR(i,1,n){
        CLR(f[now^1],0);CLR(cf,0);
        FOR(j,0,m){
            if(!f[now][j]) continue;
            int t = las[j]-i+1+1;
            if(j == 0) t = 0;
            if(t > 0) add(f[now^1][j],1ll*f[now][j]*t%ha);
            if(nxt[j] != -1) add(cf[nxt[j]],f[now][j]);
        }
        FOR(j,1,m) add(cf[j],cf[j-1]),add(f[now^1][j],1ll*cf[j]*cnt[j]%ha);
        now ^= 1;
//        FOR(i,0,m) printf("%d ",f[now][i]);puts("");
    }
    printf("%d\n",f[now][m]);
    return 0;
}

G

建 AC 自动机,我们枚举询问串的每一个后缀,走到对应的节点上,这个串的子串就是 fail 树的祖先,所以相当于要支持单点修改,查询到根的一条链上的最大值,树剖即可。$O(n \log^2 n)$。

题解做法一:我们发现对于一个点,它在 fail 树上到根的路径上终止节点最多有 $O(\sqrt n)$ 个(因为 $\sum_{i=1}^n i = O(n^2)$),所以记录一下每个点上面距离最近的终止节点,暴力跳就好了。$O(q\sqrt n)$。

一个比较 nb 的离线单 log 做法:先把询问和修改挂在树上,我们经过一个点 apply 它的所有操作,现在只有了操作时间的限制,我们用一个线段树,第 $i$ 个位置维护操作时间为 $i$ 的答案,不难发现要支持区间对一个数取 $\max$,撤销,单点求值。因为只需要单点求值,搞个标记永久化就好了,这样就只会改变 $O(\log n)$ 个节点,可以存下来了。这种线段树+撤销都可以考虑下标记永久化...

#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 = 3e5 + 5;

int ch[MAXN][26],fail[MAXN],tot = 1,rt = 1;
int ps[MAXN];

inline void insert(char str[],int id){
    int len = strlen(str+1),v = rt;
    FOR(i,1,len){
        int o = str[i]-'a';
        if(!ch[v][o]) ch[v][o] = ++tot;
        v = ch[v][o];
    }
    ps[id] = v;
}

std::vector<int> G[MAXN];

inline void build(){
    std::queue<int> q;
    FOR(i,0,25){
        if(ch[rt][i]) q.push(ch[rt][i]),fail[ch[rt][i]] = rt;
        else ch[rt][i] = rt;
    }
    while(!q.empty()){
        int v = q.front();q.pop();
        FOR(i,0,25){
            if(ch[v][i]) q.push(ch[v][i]),fail[ch[v][i]] = ch[fail[v]][i];
            else ch[v][i] = ch[fail[v]][i];
        }
    }
    FOR(i,2,tot) G[fail[i]].pb(i);
}

int mx[MAXN<<2];
#define lc ((x)<<1)
#define rc ((x)<<1|1)

inline void update(int x,int l,int r,int p,int d){
    if(l == r){
        mx[x] = d;
        return;
    }
    int mid = (l + r) >> 1;
    if(p <= mid) update(lc,l,mid,p,d);
    else update(rc,mid+1,r,p,d);
    mx[x] = std::max(mx[lc],mx[rc]);
}

inline int query(int x,int l,int r,int L,int R){
    if(l == L && r == R) return mx[x];
    int mid = (l + r) >> 1;
    if(R <= mid) return query(lc,l,mid,L,R);
    if(L > mid) return query(rc,mid+1,r,L,R);
    return std::max(query(lc,l,mid,L,mid),query(rc,mid+1,r,mid+1,R));
}

int dfn[MAXN],sz[MAXN],tp[MAXN],fa[MAXN],son[MAXN];
inline void dfs1(int v){
    sz[v] = 1;
    for(auto x:G[v]){
        fa[x] = v;
        dfs1(x);sz[v] += sz[x];
        if(sz[son[v]] < sz[x]) son[v] = x;
    }
}

inline void dfs2(int v,int tp=1){
    static int ts = 0;dfn[v] = ++ts;::tp[v] = tp;
    if(son[v]) dfs2(son[v],tp);
    for(auto x:G[v]){
        if(x == son[v]) continue;
        dfs2(x,x);
    }
}

inline int query(int x){
    int res = -1;
    while(tp[x] != 1){
        res = std::max(res,query(1,1,tot,dfn[tp[x]],dfn[x]));
        x = fa[tp[x]];
    }
    res = std::max(res,query(1,1,tot,dfn[1],dfn[x]));
    return res;
}

int n,m;
std::multiset<int> S[MAXN];
int val[MAXN];
char str[MAXN];

int main(){
    scanf("%d%d",&n,&m);
    CLR(mx,-1);
    FOR(i,1,n){
        scanf("%s",str+1);
        insert(str,i);
        S[ps[i]].insert(0);
    }
    build();
    dfs1(1);dfs2(1);
    FOR(i,1,n) update(1,1,tot,dfn[ps[i]],*S[ps[i]].rbegin());
    while(m--){
        int opt;scanf("%d",&opt);
        if(opt == 1){
            int p,x;scanf("%d%d",&p,&x);
            S[ps[p]].erase(S[ps[p]].find(val[p]));
            val[p] = x;
            S[ps[p]].insert(val[p]);
            update(1,1,tot,dfn[ps[p]],*S[ps[p]].rbegin());
        }
        else{
            scanf("%s",str+1);int len = strlen(str+1);
            int v = 1,res = -1;
            FOR(i,1,len){
                v = ch[v][str[i]-'a'];
                res = std::max(res,query(v));
            }
            printf("%d\n",res);
        }
    }
    return 0;
}
]]>
0 /archives/1583/#comments /feed/archives/1583/
ZR 2020普转提七连测day5 /archives/1580/ /archives/1580/ Wed, 28 Oct 2020 20:46:00 +0800 RainAir A. 跳石头

首先我们观察一下青蛙是怎么跳的:对于一个断点 $(i,i+1)$,如果有 $x$ 只青蛙往左跳,那么一定有 $x$ 只青蛙往右跳,所以 $a_i$ 一定是偶数。

并且我们发现从 $a_i$ 到 $a_{i+1}$,变化的只可能是 $i+1$ 这一个青蛙,也就是有 $|a_i-a_{i+1}| \in \{0,2,-2\}$。

我们考虑 $a_i$ 到 $a_{i+1}$ 的变化:如果是 $0$ 说明一定是 $i$ 跳到自己,如果多了 $2$ 说明 $i$ 往后跳,少了 $2$ 是往前跳。

所以我们可以得出每个点往哪里跳,然后用类似括号序列的方式配对就行了:遇到往右的加入栈,往左的就随便取出一个。

#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 = 2e5 + 5;
int n,a[MAXN];
int ans[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n-1) scanf("%d",a+i);
    bool flag = 1;
    FOR(i,1,n){
        flag &= !(a[i]&1);
        flag &= (std::abs(a[i]-a[i-1]) == 2 || a[i] == a[i-1]);
    }
    if(!flag){
        puts("No");
        return 0;
    }
    std::vector<int> S;
    FOR(i,1,n){
        if(a[i] == a[i-1]+2){// 左括号
            S.pb(i);
        }
        else if(a[i] == a[i-1]){
            ans[i] = i;
        }
        else{ // 右括号
            if(S.empty()){
                puts("No");
                return 0;
            }
            ans[S.back()] = i;
            ans[i] = S.back();
            S.pop_back();
        }
    }
    if(!S.empty()){
        puts("No");
        return 0;
    }
    puts("Yes");
    FOR(i,1,n) printf("%d%c",ans[i]," \n"[i==n]);
    return 0;
}
/*
1. a[i] 都是偶数 并且正好一半往左一半往右
2.  考虑 a[i] 和 a[i+1]:如果中间不动 a[i]==a[i+1],如果中间往右 a[i+1] = a[i]+2,如果中间往左 a[i+1] = a[i]-2
往右必然要有一个往左 所以遇到往右的可以看成左括号 往左的可以看成右括号 就行了
*/

B. 树

先把颜色相同的缩成一个树,感性理解操作肯定是每次操作同一个联通块,让他的影响不断增大。我们设第一次操作的点是 $x$ ,以 $x$ 为根建树,发现操作最大深度次就能完成。所以我们要让最大深度尽量小,就是直径的长度除以二。

稍微注意下处理重边即可。

#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 = 5e5 + 5;
int n,a[MAXN];
std::vector<int> G[MAXN],T[MAXN];
bool vis[MAXN];
int f[MAXN];

inline int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

inline void merge(int x,int y){
    x = find(x);y = find(y);
    if(x == y) return;
    f[x] = y;
}

inline void dfs(int v){
    vis[v] = 1;
    for(auto x:G[v]){
        if(vis[x]) continue;
        if(a[x] != a[v]) continue;
        merge(v,x);
        dfs(x);
    }
}

int g[MAXN][2],ans;

inline void dfs2(int v,int fa=0){
    for(auto x:T[v]){
        if(x == fa) continue;
        dfs2(x,v);
        if(g[v][0] < g[x][0]+1){
            g[v][1] = g[v][0];
            g[v][0] = g[x][0]+1;
        }
        else if(g[v][1] < g[x][0]+1){
            g[v][1] = g[x][0]+1;
        }
    }
    ans = std::max(ans,g[v][0]+g[v][1]);
}

std::map<P,int> S;

int main(){
    scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i),f[i] = i;
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);G[u].pb(v);G[v].pb(u);
    }
    FOR(i,1,n){
        if(vis[i]) continue;
        dfs(i);
    }
    FOR(v,1,n){
        for(auto x:G[v]){
            if(find(x) != find(v)){
                int a = find(x),b = find(v);
                if(a > b) std::swap(a,b);
                S[MP(a,b)] = 1;
            }
        }
    }
    for(auto x:S){
        T[x.fi.fi].pb(x.fi.se);
        T[x.fi.se].pb(x.fi.fi);
    }
    dfs2(find(1));
    printf("%d\n",(ans+1)/2);
    return 0;
}

C. 背包

如果没有背包的限制,那么答案就是按照重量从大到小排序,求价值的 LDS。

我们按照重量从大到小排序,那么位置 $i$ 我们能得出最多能选几个物品,设 $f_i$ 表示考虑了前 $i$ 个的答案,树状数组优化转移后特判一下能选几个物品的数量限制就行了。也就是 $f_i = \min(f_i,lim_i)$。

#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 = 2e5 + 5;

struct BIT{
    #define lowbit(x) ((x)&(-(x)))
    int tree[MAXN];

    inline void add(int pos,int x){
        while(pos){
            tree[pos] = std::max(tree[pos],x);
            pos -= lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;
        while(pos < MAXN){
            res = std::max(res,tree[pos]);
            pos += lowbit(pos);
        }
        return res;
    }
}bit;

int n;
P a[MAXN];
int lim[MAXN],w[MAXN],m;

inline void Solve(){
    scanf("%d",&n);std::vector<int> S;CLR(bit.tree,0);
    FOR(i,1,n) scanf("%d%d",&a[i].fi,&a[i].se),S.pb(a[i].se);
    std::sort(all(S));S.erase(std::unique(all(S)),S.end());
    FOR(i,1,n) a[i].se = std::lower_bound(all(S),a[i].se)-S.begin()+1;
    std::sort(a+1,a+n+1,[&](const P &x,const P &y){return x.fi > y.fi || (x.fi == y.fi && x.se > y.se);});
    scanf("%d",&m);
    FOR(i,1,m) scanf("%d",w+i);std::sort(w+1,w+m+1);std::reverse(w+1,w+m+1);
    int ans = 0;
    FOR(i,1,n){
        lim[i] = lim[i-1];
        while(lim[i]+1 <= m && w[lim[i]+1] >= a[i].fi) ++lim[i];
        int f = bit.query(a[i].se)+1;f = std::min(f,lim[i]);
        bit.add(a[i].se,f);
        ans = std::max(ans,f);
    }
    printf("%d\n",ans);
}

int main(){
//    freopen("C.in","r",stdin);
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

D. 蚂蚁

先考虑不需要支持修改怎么做:假设现在有 $k$ 只蚂蚁,所在的点分别为 $v_1\ldots v_k$,设每个蚂蚁到达根的时间为 $t_i$,答案就是 $\max t_i$,我们观察一下有哪些限制:

首先,每个蚂蚁的 $t_i \geq dep_{v_i}$,因为就算从开始爬也要花这些时间才能过去。

然后,我们要保证不会在某时刻在同一个点,我们可以发现如果两只蚂蚁在某个时候在同一个点上,那么它们在根的时候也会在同一个点上,所以我们只需要保证 $t_i$ 互不相同就行了。

所以问题变成了,每个变量有一个下界 $lim_i$,要求分配使得变量互不相同,并且最大值尽量小,这是个经典问题:考虑记 $s_i = \sum_{x=1}^k [lim_x \geq i]$,答案显然是 $\max(s_i+i-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 = 1e5 + 5;

int mx[MAXN<<2],tag[MAXN<<2];
#define lc ((x)<<1)
#define rc ((x)<<1|1)

inline void cover(int x,int d){
    mx[x] += d;tag[x] += d;
}

inline void pushdown(int x){
    if(tag[x]){
        cover(lc,tag[x]);
        cover(rc,tag[x]);
        tag[x] = 0;
    }
}

inline void modify(int x,int l,int r,int L,int R,int d){
    if(l == L && r == R){
        cover(x,d);
        return;
    }
    int mid = (l + r) >> 1;pushdown(x);
    if(R <= mid) modify(lc,l,mid,L,R,d);
    else if(L > mid) modify(rc,mid+1,r,L,R,d);
    else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
    mx[x] = std::max(mx[lc],mx[rc]);
}

inline void build(int x,int l,int r){
    tag[x] = 0;
    if(l == r){
        mx[x] = l;return;
    }
    int mid = (l + r) >> 1;
    build(lc,l,mid);build(rc,mid+1,r);
    mx[x] = std::max(mx[lc],mx[rc]);
}

int n,m;
std::vector<int> G[MAXN];
int dep[MAXN];

inline void dfs(int v,int fa=0){
    dep[v] = dep[fa]+1;
    for(auto x:G[v]) if(x != fa) dfs(x,v);
}

inline int query(int x,int l,int r,int L,int R){
    if(L > R) return 1;
    if(l == L && r == R) return mx[x];
    int mid = (l + r) >> 1;pushdown(x);
    if(R <= mid) return query(lc,l,mid,L,R);
    if(L > mid) return query(rc,mid+1,r,L,R);
    return std::max(query(lc,l,mid,L,mid),query(rc,mid+1,r,mid+1,R));
}

std::multiset<int> S;

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,2,n){
        int f;scanf("%d",&f);
        G[f].pb(i);
    }
    dfs(1);build(1,1,n);
    S.insert(0);
    FOR(i,1,m){
        int opt,x;scanf("%d%d",&opt,&x);
        if(opt == 1){
            if(x != 1){
                S.insert(dep[x]);
                modify(1,1,n,1,dep[x],1);
            }
        }
        else{
            if(x != 1){
                S.erase(S.find(dep[x]));
                modify(1,1,n,1,dep[x],-1);
            }
        }
        int t = *S.rbegin();
        printf("%d\n",query(1,1,n,1,t)-1);
    }
    return 0;
}

E. 划分

为啥完全没有思路。。。

我们考虑固定 $1$ 为根,定义每个连通块的根为连通块深度最小的点,我们枚举其中一个连通块的根为 $x \neq 1$,那么有一个连通块根一定为 $1$,我们设剩下的那个连通块的根为 $y$,分类讨论:

如果 $sz_x = |A|$:

  • 如果 $y$ 不是 $x$ 的祖先,$sz_y = sz_x$ 或 $sz_y=n-2sz_x$
  • 如果 $y$ 是 $x$ 的祖先,$sz_y=2sz_x$ 或 $sz_y=n-sz_x$

如果 $sz_x = |C|$:

  • 如果 $y$ 不是 $x$ 的祖先,$sz_y=\frac{n-sz_x}{2}$
  • 如果 $y$ 是 $x$ 的祖先,$sz_y = \frac{n-sz_x}{2}+sz_x = \frac{n+sz_x}{2}$

相当于我们对于一个点,想要询问到根的链上是否有点的 $sz$ 是某个值,这个可以 dfs 的时候处理一个数组搞出来;还需要询问某个点子树外并且不是它的祖先的所有点中是否有点 $sz$ 是某个值,预先处理所有的点的 $sz$ 出现情况,补集转化后变成了求子树内某个值的出现次数,这个可以用类似差分计算增量的方法实现,也就是在进入子树前记录一下要查询的值,然后进入这个子树,遍历完所有的点并且加到桶里后再求一下值,做个差就能得到子树的值。详情可以看代码

#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;

std::vector<int> G[MAXN];
int n;

int sz[MAXN];
int c1[MAXN],c2[MAXN],c3[MAXN];
// c1: 整棵树
// c2: 查询子树用
// c3: 祖先

inline void dfs1(int v,int fa=0){
    sz[v] = 1;
    for(auto x:G[v]){
        if(x == fa) continue;
        dfs1(x,v);
        sz[v] += sz[x];
    }
    ++c1[sz[v]];
}

int ans = 0;

inline void dfs2(int v,int fa=0){
    if(2*sz[v] <= n && c3[2*sz[v]] && 2*sz[v] < n) ans = std::max(ans,sz[v]);
    if(c3[n-sz[v]] && 2*sz[v] < n) ans = std::max(ans,sz[v]);
    if(!((n+sz[v])&1) && c3[(n+sz[v])>>1]) ans = std::max(ans,(n-sz[v])>>1);
    int p1 = c2[sz[v]],p2 = n-2*sz[v] > 0 ? c2[n-2*sz[v]] : -1e9,p3 = (n-sz[v])&1 ? -1e9 : c2[(n-sz[v])>>1];
    ++c3[sz[v]];++c2[sz[v]];
    for(auto x:G[v]){
        if(x == fa) continue;
        dfs2(x,v);
    }
    p1 = c1[sz[v]]-(c2[sz[v]]-p1);
    if(p2 != -1e9) p2 = c1[n-2*sz[v]]-(c2[n-2*sz[v]]-p2);
    if(p3 != -1e9) p3 = c1[(n-sz[v])>>1]-(c2[(n-sz[v])>>1]-p3);
    if(p1 > 0 && 2*sz[v] < n) ans = std::max(ans,sz[v]);
    if(p2 > 0 && 2*sz[v] < n) ans = std::max(ans,sz[v]);
    if(p3 > 0) ans = std::max(ans,(n-sz[v])>>1);
    --c3[sz[v]];
}

int main(){
    scanf("%d",&n);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }
    dfs1(1);dfs2(1);
    printf("%d\n",ans);
    return 0;
}
]]>
0 /archives/1580/#comments /feed/archives/1580/