最近开坑补一下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;
}
鄂公网安备 42010202000505 号