UOJ Logo Tachibana_Kanade的博客

博客

USACO 2019 January Contest Platinum

2019-01-24 21:21:54 By Tachibana_Kanade

最近开坑补一下usaco...太弱了

Problem 1. Redistricting

Statement

给一个序列,把他分割成若干个子区间,定义一个子区间是好的当且仅当这个区间内$H$的数量$>G$的数量 最大化好的区间的个数。$N\leq 3e5$

Solution

令$dp_{i}$表示前$i$个字母的答案

不难注意到$dp_{i}=min_{max(0,i-k)\leq j\leq i-1}\;\;\;\;{dp_{j}+(S_{i}-S_{j}\geq 0)}$

(令$H=-1,G=1,S$为前缀和)

那么分两种情况

第一种情况是$S_{i}\geq S_{j}$, 显然$dp_{i}=min{dp_{j}}+1$

第二种情况是$S_{i} < S_{j}$,显然$dp_{i}=min{dp_{j}}$

不难得出,问题实际上是在问,在能满足$dp_{t}=min{dp_{j}}$的情况下,是否可以得到$S_{t}>S_{i}$

那么用单调队列维护即可。

找$min{dp_{j}}$也用单调队列维护。

时间复杂度$O(n\log n)$,带$\log$是因为要离散化。

Conclusion

考试的时候,想到$dp$了就没有细想,长期以来想到$log^{2}$就不想想$log$的坏毛病暴露了出来

写了个$Fenwick Tree$套$Set$挂的比暴力还惨。。

其实离正解一步之遥

这个故事告诉我们,很多题其实我们都会做,但是我们的自我放纵和懒惰导致我们没有能解出这道题

这在考试中是不应该发生的。

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 300001;

int n, m, s[maxn], c[maxn], T, f[maxn];
char a[maxn];
deque<pii> pre[maxn];
deque<pii> dq;

int main()
{
    fp("redistricting.in","r",stdin);
    fp("redistricting.out","w",stdout);
    sf("%d%d",&n,&m);
    sf("%s",a+1);
    fo(i,1,n) s[i] = (a[i] == 'H' ? -1 : 1) + s[i-1];
    int tot = 0; fo(i,1,n) c[++tot] = s[i];
    sort(c+1,c+tot+1);
    tot = unique(c+1,c+tot+1)-(c+1);
    fo(i,1,n) s[i] = lower_bound(c+1,c+tot+1,s[i])-c;
    int ans = 0;
    fo(i,1,n)
    {
        T = i - m;
        if(i - m <= 0) f[i] = (c[s[i]] >= 0); else f[i] = inf;
        while(SZ(dq) && dq.front().se < T) dq.pop_front();
        int last = (SZ(dq) > 0 ? dq.front().fi : inf);
        if(last == inf) goto gg;

        while(SZ(pre[last]) && pre[last].front().se < T) pre[last].pop_front();
        if(SZ(pre[last]) && pre[last].front().fi > s[i]) 
            gmin(f[i], last); 
        else 
            gmin(f[i], last + 1);
        while(SZ(pre[f[i]]) && pre[f[i]].back().fi < s[i]) pre[f[i]].pop_back();
        pre[f[i]].pb(mp(s[i], i));

        gg:;
        while(SZ(dq) && dq.back().fi > f[i]) dq.pop_back();
        dq.push_back(mp(f[i], i));
    }
    pf("%d\n",f[n]);
    return 0;
}

Problem 2. Exercise Route

Statement

给一棵树,再另外给出$M$条边,问能从这些边中选两个,能产生的简单环的总数。

Solution

注意到,加入一条边必定会形成一个环,两条边所形成的两条环如果有交集,则正好可以产生一个且仅一个简单环。

问题转化为判断多少个环相交

考虑把$x->y$拆成$x->lca,lca->y$,那么问题简单很多。

然而这会重复计算,比如说和第一个边有交,和第二个边也有交那就会被算两次,不过这个比较容易剔除

因为这种情况发生的条件是当且仅当他们的端点的$LCA$一样,且,两条到$LCA$的边也是相同的两条边。

那么剩下的就是前缀和计数辣!

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

/*
the critical observation here is:
two non-standard trails will produce either exactly one simple cycle if they overlap

clearly if they disjoint, u wouldnt even be able to walk between them
why there are only one answer
c->d->lca(b,d)->b->a
thats the only possible path

now our problem is how to count pairs of non-standadr pairs that overlap
break each path down to 2 paths x->lca, lca->y
count how many pairs of that overlap is much easier
but this would overcount
just get rid of the cases where lca(a,b)=lca(c,d) and 
                            last edge from a to lca(a,b) = last edge from c to lca(c,d)
                            last edge from b to lca(a,b) = last edge from d to lca(c,d)
and now suppose there are no overcounting 
*/
const int maxn = 200050;

int n, m, x[maxn], y[maxn], anc[maxn];
int fa[maxn][20], dep[maxn], f[maxn], g[maxn];
VI adj[maxn];
map<pii,int> cnt;

void dfs(int u, int fax = 0)
{
    for(auto p : adj[u]) if(p != fax)
    {
        fa[p][0] = u;
        dep[p] = dep[u] + 1;
        dfs(p, u);
    }
}
int lca(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    int c = dep[x] - dep[y];
    fd(i,19,0) if(c & (1<<i)) x = fa[x][i];
    fd(i,19,0) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return x == y ? x : fa[x][0];
}
int findst(int x, int y) // y is an ancestor of x
{
    if(x == y) return -1;
    fd(i,19,0) if(dep[fa[x][i]] > dep[y]) x = fa[x][i];
    return x;
}
void calc(int u, int v)
{
    g[u] = v;
    for(auto p : adj[u]) if(p != fa[u][0])
        calc(p, v + f[p]);
} 
int main()
{
    fp("exercise.in","r",stdin);
    fp("exercise.out","w",stdout);
    sf("%d%d",&n,&m);
    m -= n - 1;
    fo(i,2,n) 
    {
        int u, v;
        sf("%d%d",&u,&v);
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1);
    fo(j,1,19) fo(i,1,n) fa[i][j] = fa[fa[i][j-1]][j-1];
    ll ans = 0;
    fo(i,1,m)
    {
        sf("%d%d",&x[i],&y[i]);
        anc[i] = lca(x[i], y[i]);
        int tx = findst(x[i], anc[i]);
        if(tx != -1) 
        {
            f[tx] ++;
            ans -= f[tx];
        }
        int ty = findst(y[i], anc[i]);
        if(ty != -1)
        {
            f[ty] ++;
            ans -= f[ty];
        }
        // cout << x[i] << ' ' << y[i] << ' ' << anc[i] << ' ' << tx << ' ' << ty << endl;
        if(tx != -1 && ty != -1)
        {
            if(tx > ty) swap(tx, ty);
            ans -= cnt[mp(tx, ty)];
            cnt[mp(tx, ty)] ++;
        }
    }
    calc(1, f[1]);
    fo(i,1,m) ans += g[x[i]] + g[y[i]] - 2 * g[anc[i]];
    pf("%lld\n",ans);
    return 0;
}

Problem 3.Train Tracking 2

Statement

有一个$N$个数组成的序列,每个数的大小在$[1,10^{9}]$,然后已知每个区间$[i,i+K-1]$的最小值,求多少个序列满足这样的条件。

Solution

这种题直接做不好做,考虑从一般到特殊,从特殊到一般的思路。

考虑$N=K$的情况,我们只需要确定一个数的值,其他数的下限已知,所以答案显而易见。

如果说,$W$值全是一样($W$为区间最小值),那么我们就可以用动态规划来计算。

令$f_{i}$表示第$i$个点的值被区间最小值决定的答案

那么有$f_{i}=\sum_{j=1}^{k}x^{j-1}f_{i-j}$

观察$f_{i+1}=f_{i}+\sum_{j=1}^{k}x^{j}f_{i-1-j}$

不难发现$f_{i+1}=f_{i}+x(f_{i}-x^{k-1}f_{i-k})$

那么考虑$W$值不想等的情况,同样采用从特殊到一般的策略

考虑$W_{1}=W_{2}=...=W_{n-k}\neq W_{n-k+1}$的情况

那么有两种情况

1.$W_{n-k} < W_{n-k+1}$,这种情况的话,我们可以直接确定$n-k$这个位置的值

2.$W_{n-k} > W_{n-k+1}$, 我们可以直接确定$n$这个位置的值

那这个显然可以被拓展,不难发现,经过这样的比较厚,我们会得到一些critical points(也就是被确定了的值)

那么我们原本的区间被分割成了若干个连续的子区间,而这些子区间内的W又是一样的,显然可以采用我们刚才所讨论的dp

这样就做完啦~~时空复杂度$O(n)$

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 100050;
const int MX = 1000000000;
const int P = 1e9+7;

int n, K, W[maxn], f[maxn], pw[maxn];

int calc(int len, int val)
{
    // we want to count that len when all the windows = val, the number of scenarios
    int X = MX - val;
    pw[0] = 1; fo(i,1,K) pw[i] = (pw[i-1] * 1ll * X) % P;
    f[0] = f[1] = 1; 
    fo(i,2,K) f[i] = (f[i-1] * 1ll * (X+1))%P;
    if(len < K) return (f[len] * 1ll * (X+1))%P;
    fo(i,K,len) 
    {
        f[i+1] = f[i];
        f[i+1] = (f[i+1] - 1ll * f[i-K] * pw[K-1]) % P;
        f[i+1] = (f[i+1] % P + P) % P;
        f[i+1] = (f[i+1] * 1ll * X) % P;
        f[i+1] = (f[i+1] + f[i]) % P;
    }
    return f[len+1];
}
int main()
{
    fp("tracking2.in","r",stdin);
    fp("tracking2.out","w",stdout);
    sf("%d%d",&n,&K);
    fo(i,1,n-K+1) sf("%d",&W[i]);
    vector<pii> crp;
    crp.pb(mp(0,0));
    fo(i,1,n-K)
    {
        if(W[i] < W[i+1]) crp.pb(mp(i,W[i]));
        else if(W[i] > W[i+1]) crp.pb(mp(i+K,W[i]));
    }
    crp.pb(mp(n+1,W[n-K+1]));
    int ans = 1;
    for(int i = 1; i < SZ(crp); ++ i)
    {
        int l = crp[i-1].fi + 1, r = crp[i].fi - 1;
        D("%d %d %d %d\n",l,r,crp[i].se,calc(r-l+1,crp[i].se));
        if(l <= r) ans = (ans * 1ll * calc(r-l+1, crp[i].se)) % P; 
    }
    pf("%d\n",ans);
    return 0;
}

IOI2018 day1 Solution

2019-01-09 19:45:35 By Tachibana_Kanade

花了三天断断续续地补完了QAQ

Combo

Statement

有一个只由$A,B,X,Y$构成的母串$S$,保证首字母在整个母串里只会出现一次

现在你需要交互不超过$n+2$次,每次可以询问一个字符串(长度不超过$4N$),交互端会返回在你询问的串中出现的母串的最长前缀。

$N\leq 1000$

Solution

考虑首字母可以花$2$次来确定:询问$AB$然后在询问$A$或者$X$。

那么现在假设首字母是$A$,怎么才能一次性确定某位的字母呢?

不难想到,利用返回值来判断字母,我们可以考虑用$S+B+S+XY+S+XX+S+XB$来询问

那么如果返回值是$|S|$,答案显然是$Y$,如果是$|S|+1$则是$B$,若是$|S|+2$则是$X$

注意最后一个字母要用和第一个字母一样的方法去判断。

这样总共会询问$N-2+4=N+2$次,最大长度为$4(N-2)+7=4N-1$,可以通过所有测试数据。

Code

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

string convert(int x)
{
    if(x == 1) return "A";
    else if(x == 2) return "B";
    else if(x == 3) return "X";
    else return "Y";
}
int candi[4];
string guess_sequence(int n)
{
    int first;
    string ret = "";
    if(press("AB"))
    {
        if(press("A")) first = 1, ret = "A";
        else first = 2, ret = "B";
    }
    else 
    {
        if(press("X")) first = 3, ret = "X";
        else first = 4, ret = "Y"; 
    }
    srand(time(NULL));
    fo(i,1,4) if(i != first) candi[i] = i;
    fo(i,2,n-1) 
    {
        random_shuffle(candi+1,candi+3+1);
        fo(a,1,3)
        {
            fo(b,1,3) if(a != b)
            {
                string tmp = ret + convert(candi[a]);
                fo(c,1,3)
                    tmp = tmp + ret + convert(candi[b]) + convert(candi[c]);
                int answer = press(tmp);
                if(answer == i + 1) ret = ret + convert(candi[b]);
                else if(answer == i) ret = ret + convert(candi[a]);
                else fo(k,1,3) if(k != a && k != b) {ret = ret + convert(candi[k]); break;}
                goto loop;
            }
        }
        loop:;
    }
    if(n != 1)
    {
        random_shuffle(candi+1,candi+3+1);
        string tmp = ret + convert(candi[1]) + ret + convert(candi[2]);
        if(press(tmp) == n) 
        {
            tmp = ret + convert(candi[1]);
            if(press(tmp) == n) {ret = tmp; goto gg;}
            ret = ret + convert(candi[2]); goto gg;
        }
        ret = ret + convert(candi[3]);
        gg:;
    }
    return ret;
}

Seats

Statement

给一个$N\times M$的矩阵,矩阵元素为$0...N\times M-1$的一个排列,现在需要支持交换矩阵中某两个元素,计算有多少个$good$子矩阵

$good$子矩阵定义为由$0...A\times B-1$构成的$A\times B$的子矩阵。

$N\times M\leq 10^{6}$

Solution

考虑$N=1$的情况

不难注意到,子矩阵放在整个矩阵中看起来像$-----+++++-----$一样 ($+$为$0...t-1$,我们正在考虑大小为$t$的子矩阵是否合法)

那么用线段树去维护是否正好有两个分界点即可。

同理,考虑编号$0...t-1$的格子染成黑色,其他格子染白色。

那么如果用$2\times 2$的小矩阵去覆盖整个矩阵的话,不难发现黑色格子形成一个矩形的充要条件:

1.恰好有$4$个小矩阵中包含正好$1$个黑格子【矩形的四角】 2.不存在有小矩形包含$3$个黑格子【保证是封闭且凸】

于是考虑用线段树去维护,维护最小值和最小值个数即可。

时间复杂度$O(HW\log HW)$

Code

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

const int maxn = 1000050;
const int dx[] = {0,0,1,1};
const int dy[] = {1,0,0,1};

struct node{int l, r, cnt; pii v, tag;}t[maxn<<2];
int one[maxn], tri[maxn];
int h, w, r[maxn], c[maxn];
vector<vector<int> > A;
VI sur;

void build(int l, int r, int k)
{
    t[k].l = l; t[k].r = r;
    if(l == r)
    {
        t[k].v.fi = one[l];
        t[k].v.se = tri[l];
        t[k].tag = mp(0, 0);
        t[k].cnt = 1;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, k<<1);
    build(mid+1, r, k<<1|1);
    t[k].v = min(t[k<<1].v, t[k<<1|1].v); t[k].cnt = 0;
    if(t[k<<1].v == t[k].v) t[k].cnt += t[k<<1].cnt;
    if(t[k<<1|1].v == t[k].v) t[k].cnt += t[k<<1|1].cnt;
}
void pd(int k)
{
    t[k<<1].tag.fi += t[k].tag.fi;
    t[k<<1].tag.se += t[k].tag.se;
    t[k<<1].v.fi += t[k].tag.fi;
    t[k<<1].v.se += t[k].tag.se;
    t[k<<1|1].tag.fi += t[k].tag.fi;
    t[k<<1|1].tag.se += t[k].tag.se;
    t[k<<1|1].v.fi += t[k].tag.fi;
    t[k<<1|1].v.se += t[k].tag.se;
    t[k].tag = mp(0, 0);    
}
void modify(int l, int r, pii x, int k)
{
    if(l > r) return;
    if(l <= t[k].l && t[k].r <= r)
    {
        t[k].v.fi += x.fi;
        t[k].v.se += x.se;
        t[k].tag.fi += x.fi;
        t[k].tag.se += x.se;
        return;
    }
    pd(k);
    int mid = t[k].l + t[k].r >> 1;
    if(r <= mid) modify(l, r, x, k<<1);
    else if(l > mid) modify(l, r, x, k<<1|1);
    else modify(l, mid, x, k<<1), modify(mid+1, r, x, k<<1|1);
    t[k].v = min(t[k<<1].v, t[k<<1|1].v); t[k].cnt = 0;
    if(t[k<<1].v == t[k].v) t[k].cnt += t[k<<1].cnt;
    if(t[k<<1|1].v == t[k].v) t[k].cnt += t[k<<1|1].cnt;
}    
void getx(int x, int y)
{
    sur.clear();
    fo(k,0,3) sur.pb(A[x+dx[k]][y+dy[k]]);
    sort(sur.begin(), sur.end());
}
void update(int x, int y, int w)
{
    getx(x, y);
    modify(sur[0], sur[1]-1, mp(w, 0), 1);
    modify(sur[2], sur[3]-1, mp(0, w), 1);
}
void upd(int x, int y, int val)
{
    update(x, y-1, -1);
    update(x-1, y, -1);
    update(x, y, -1);
    update(x-1, y-1, -1);
    A[x][y] = val;
    update(x, y-1, 1);
    update(x-1, y, 1);
    update(x, y, 1);
    update(x-1, y-1, 1);    
}
int ask()
{
    return (t[1].v.fi == 4 && t[1].v.se == 0) ? t[1].cnt : 0;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) 
{
    int n = R.size();
    h = H; w = W;
    fo(i,0,H+1) 
    {
        vector<int> cur;
        fo(j,0,W+1) cur.pb(H*W+1);
        A.pb(cur);
        cur.clear();
    }
    fo(i,0,n-1) 
    {
        r[i+1] = R[i] + 1; 
        c[i+1] = C[i] + 1;
        A[r[i+1]][c[i+1]] = i+1;
    }
    fo(i,0,H) fo(j,0,W)
    {
        getx(i, j);
        ++ one[sur[0]]; -- one[sur[1]];
        ++ tri[sur[2]]; -- tri[sur[3]];
    }
    fo(i,1,H*W) one[i] += one[i-1], tri[i] += tri[i-1];
    build(1, H*W, 1); 
}
int swap_seats(int a, int b) 
{
    ++ a; ++ b;
    int x = A[r[a]][c[a]], x2 = A[r[b]][c[b]];
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    upd(r[a], c[a], x);
    upd(r[b], c[b], x2);
    return ask();
}

Werewolf

Statement

给定一张$N$个点,$M$条边的无向连通图,有$Q$个询问。

你从$S$出发,到达$E$,你初始是人形态,要求到达$E$的时候是狼人形态。

人形态的时候不能经过城市$0...L-1$, 狼人形态的时候不能经过城市$R+1..N-1$,你只能从人变到狼人。

问是否存在一种路径能让你到达$E$

$N,M,Q\leq 2\times 10^{5}$

Solution

不难发现题目等价于询问从$S$出发只走$\geq L$的点的路径,和从$E$出发只走$\leq R$的点的路径,是否会有交集。

考虑如果点都很连续,那么这道题就很好做

所以我们不如类似$kruskal$那样:

1.倒序加入新点$x$

2.枚举$>x$的邻接点$y$

3.找到$y$所在的连通块的根,把它的父亲设置为$x$

那么这样的话,我们发现在这棵树上,某个点的子树一定是这个点只经过不超过该点权值,所能到达的点。

同理,构造第二棵,要求是不小于而并非不超过。

这样的话我们只需要利用树上倍增(我个人更倾向于说是二分),就可以把所有可以要求的点锁定在一个子树里

问题等价于询问两个树的子树是否有交集。

以在两棵树的dfs序为坐标,那么问题就变为了一个二维数点,用主席树或者扫描线加线段树就可以了。

时间复杂度$O(Q\log N+M\log M)$。

Code

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

const int maxn = 200050;

int fa[maxn];
struct KruskalT
{
    VI adj[maxn];
    int tot, anc[maxn][20], in[maxn], out[maxn];
    void link(int u, int v) 
    {
        adj[u].emplace_back(v);
        anc[v][0] = u;
    }
    void init(int N)
    {
        fo(j,1,19) 
            for(int i = 0; i < N; ++ i)
                if(anc[i][j-1] != -1)
                    anc[i][j] = anc[anc[i][j-1]][j-1];
    }
    int getsub(int u, int x, int oper) // oper = 0 => >= L[i], 1-> <=R[i]
    {
        if(oper == 0)
        {
            fd(i,19,0) 
                if(anc[u][i] != -1 && anc[u][i] >= x) 
                    u = anc[u][i];
            if(u >= x) return u;
            else return -1;
        }
        else
        {
            fd(i,19,0)
                if(anc[u][i] != -1 && anc[u][i] <= x) 
                    u = anc[u][i];
            if(u <= x) return u;
            else return -1;
        }
    }
    void dfs(int u)
    {
        in[u] = ++ tot;
        for(auto p : adj[u]) dfs(p);
        out[u] = tot;
    }
}Tu, Tv, T;
int ls[maxn*20], rs[maxn*20], nd[maxn*20], tot;
int rt[maxn], bag[maxn];

int getfa(int x){return fa[x] == x ? x : fa[x] = getfa(fa[x]);}
void add(int &now, int pre, int p, int l, int r)
{
    now = ++ tot;
    nd[now] = nd[pre] + 1; ls[now] = ls[pre]; rs[now] = rs[pre];
    if(l == r) return;
    int mid = l + r >> 1;
    if(p <= mid) add(ls[now], ls[pre], p, l, mid);
    else add(rs[now], rs[pre], p, mid+1, r);
}
int ask(int now, int pre, int l, int r, int L, int R)
{
    if(!now) return 0;
    if(l <= L && R <= r) return nd[now] - nd[pre];
    int mid = L + R >> 1;
    if(r <= mid) return ask(ls[now], ls[pre], l, r, L, mid);
    else if(l > mid) return ask(rs[now], rs[pre], l, r, mid+1, R);
    else return ask(ls[now], ls[pre], l, mid, L, mid) +
                ask(rs[now], rs[pre], mid+1, r, mid+1, R);
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  int Q = S.size(), M = X.size();
  std::vector<int> A(Q);
  // construct two trees
  for(int i = 0; i < N; ++ i) fa[i] = i;
  memset(Tu.anc,0xff,sizeof(Tu.anc));
  memset(Tv.anc,0xff,sizeof(Tv.anc));
  for(int i = 0; i < M; ++ i) T.link(X[i], Y[i]), T.link(Y[i], X[i]);
  for(int i = N-1; i >= 0; -- i)
  {
      for(auto p : T.adj[i]) if(p > i)
      {
          int fx = getfa(p);
          if(fx != i)    {fa[fx] = i; Tu.link(i, fx); D("%d %d\n",i,fx);}
      }
  }
  D("~~~~~~~~~~\n");
  for(int i = 0; i < N; ++ i) fa[i] = i;
  for(int i = 0; i < N; ++ i)
  {
      for(auto p : T.adj[i]) if(p < i)
      {
          int fx = getfa(p);
          if(fx != i) {fa[fx] = i; Tv.link(i, fx); D("%d %d\n",i,fx);}
      }
  }
  D("~~~~~~~~~\n");
  //build up binary lifting stuffs
  Tu.init(N); Tv.init(N);
  Tu.dfs(0); Tv.dfs(N-1);
  //insert points into persistent rangetree
  for(int i = 0; i < N; ++ i) 
      bag[Tu.in[i]] = Tv.in[i];
  for(int i = 1; i <= Tu.tot; ++ i) 
  {
      add(rt[i], rt[i-1], bag[i], 1, Tv.tot);
      D("%d\n",ask(rt[i],rt[i-1],bag[i],bag[i],1,Tv.tot));
  }
  //now query
  for(int i = 0; i < Q; ++ i)
  {
      int x = Tu.getsub(S[i], L[i], 0), y = Tv.getsub(E[i], R[i], 1);
      if(x == -1 || y == -1) {A[i] = 0; continue;}
      D("%d %d %d\n",i,x,y);
      D("[%d,%d] [%d,%d]\n",Tu.in[x],Tu.out[x],Tv.in[y],Tv.out[y]);
      A[i] = ask(rt[Tu.out[x]], rt[Tu.in[x]-1], Tv.in[y], Tv.out[y], 1, Tv.tot);
      A[i] = (A[i] > 0);
  }
  return A;
}

ATSC2017解题报告

2017-10-06 21:09:30 By Tachibana_Kanade

前言

有人会问ATSC是啥,自然是安徒生菜Australian Team Selection Contest啦

本蒟蒻考爆炸了→_→,但是为了业界良心,以及后人不会再思博,我拿出来共享一下2333

版权?未经授权别想了,反正他也看不懂中文(flag

详细题解参见在下的博客:http://medalplus.com

D1T1 Banarby's Farm

题目大意

给你一个网格图,每个点有个高度,你可以走上下左右四个方向,当且仅当相邻点和当前点的高度差不超过一个给定的常数$k$,你作为苦逼农场主,为了去铲金坷垃,你得从$(S_{x},S_{y})$出发,到$(E_{x},E_{y})$去。你想了一下,发现...你去不了。于是你需要搭桥,两个点之间能搭桥当且仅当

  1. 两点在同一行或者同一列
  2. 他们的高度差不超过$k$
  3. 他们之间的所有点(不包括两端)的高度都严格小于他们的高度

因为经济危机,你得最小化需要的桥的数量。数据范围$N,M\leq 1000,H\leq 10^{9}$

Solution

几乎是签到题,根据性质三,我们不难想到用单调栈去优化建图,然后跑堆优化的$dijkstra$,这样时间复杂度就是$O(nm+nmlognm)$了。

D1T2 Eastconnex

题目大意

悉尼修了新路,城市由$N$条横向高速公路和$M$条纵向泥巴路组成。泥巴路从左往右标号,高速公路从下往上标号,泥巴路之间的距离间隔都是$1$,第$i$条高速路和第$i+1$条高速路的距离间隔为$A_{i}$,记$(i,j)$表示第$i$条泥巴路和第$j$条高速公路的交点。在泥巴路上走一个长度单位只需要$1$美元,而第$i$条高速公路上走一个长度单位则需要$C_{i}$美元。有$Q$个询问,每次询问从$(x,y)$出发,到达$(a,b)$的最小花费。$N,Q\leq 10^{5},M\leq 10^{9},everything else\leq 10^{9}$

强制在线

Solution

先对$A$做前缀和。

不难发现,正解一定长这样$(x,y)->(x,i)->(a,i)->(a,b)$,然后分三种情况讨论,我们发现花费为$\left | A_{y1}-A_{i} \right |+\left | X_{1}-X_{2} \right |\times Cost_{i}+\left | A_{y2}-A_{i} \right |$,然后根据小学数学,我们画端点分区间讨论,一共有三种情况分别为$\left\{\begin{matrix}A_{y1}-A_{i}+\left | X_{1}-X_{2} \right |\times Cost_{i}+A_{y2}-A_{i}\\A_{i}-A_{y1}+\left | X_{1}-X_{2} \right |\times Cost_{i}+A_{y2}-A_{i}\\A_{i}-A_{y1}+\left | X_{1}-X_{2} \right |\times Cost_{i}+A_{i}-A_{y2}\end{matrix}\right.$

相信大家都会做了QAQ,情况一三凸壳上树,线段树上做CHT,情况二RMQ问题。

证明?反证法证明。留bu给gao读su者ni自he己he思he考he。

D1T3 Guards

题目大意

悉尼大学有$N$幅世界名画,其中包含蒙娜考拉等,编号$1$到$N$,排成一排。第$i$幅画的价值为$V[i]$。你是著名神偷·怪盗基德,你要去偷画,但是可惜,大学有$G$个条子,每个条子保护$[S_{i},E_{i}]$内的所有画。但是第$i$个条子可以被$C_{i}$刀贿赂从而离开岗位,你的收益是偷到的画的价值减去用来贿赂的钱。聪明的你,能写个程序算一波么?$N,M\leq 2\times10^{5},V[i],C[i]\leq 10^{9}$

Solution

设$f[i]$表示前$i$幅画的答案,其中强制购买第$i$幅画

那么我们考虑存在这样一个指针$j$从$i$开始,往$i$走。那么有转移方程$f[i]=max\left \{ f[j-1]-counter+v[i] \right \}$

其中$counter$表示所有以我们中途$j$遇到的点为起点,终点$\geq i$的守卫的贿赂价值总和。

不难发现每个守卫的贡献都是对前缀所增加的。而守卫因为$i$的增加而逐渐被扔掉,所以我们很容易用双指针扫描线+线段树去优化这个转移方程。

时间复杂度$O(n\log n)$

D2T1 Mahjong

题目大意

连连看(原题是麻将但是。。我实在不懂和麻将有什么关系,不如翻译成连连看好了),有$P$对点是配对的,给出一张无向图,不保证连通,无重边无自环。图上的每一个点保证都有配对对象。两个点能消去当且仅当

  1. 他们是配对的。
  2. 他们之间存在一条路径,不经过任何还没被消除的点。

试问最多能消去几对点?

Solution

考虑对点建DSU?关系不满足传递性,GODIE!

那么按照边建DSU,DSU同时附带维护SET,那么每次合并采用启发式合并,然后利用宽搜的方式去扩展状态即可。

时间复杂度$O(m\log n)$

D2T2 Sushi Selection

题目大意

有$T$个店,每个店卖$A_{i}$个寿司,因为做促销,在第$i$家店,买$k$个寿司,所需要的价格为$\sum_{j=0}^{k}V[i][j]$,保证$V[i][j]\geq V[i][j+1]$

你要买$M$个寿司,最小化花费。$M\leq\sum A_{i}\leq 10^{5},T\leq 230$

Soltuion

不难用反证法证明至多有一家店没买完。

于是问题就变成了经典问题,限定性01背包问题。我们直接用CDQ分治做即可。

D2T3 Ez

不想写了。。。直接主席树即可。

完结。感觉还是自己SB考挂了没去IOI,真的菜鸡。

Tachibana_Kanade Avatar