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

评论

Tachibana_Kanade
桶排可以做到$o(n)$T_T
peehs_moorhsum
第一题直接单调栈就是O(n)啊？

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-04-25 06:33:37