Problem 1. Redistricting
将(H)看做(+1)，(G)看做(-1)，得到一个前缀和数组(sum_i)
记(dp_i)为考虑到(i)时的答案，有(dp_i=min(dp_j+[sum_i-sum_jleq 0]))
直接(dp)时间是(O(nk))的，使用单调队列优化时间复杂度降为(O(nlog_2k))
注意单调队列是双关键字的，第一关键字是(dp)，第二是(sum)
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define fir first
#define sec second
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define maxd 1000000007
#define eps 1e-6
typedef long long ll;
const int N=100000;
const double pi=acos(-1.0);
int n,k,dp[300300],sum[300500];
char s[300500];
struct hnode{int val,id;};
bool operator <(hnode p,hnode q)
{
if (p.val==q.val) return sum[p.id]>sum[q.id];
else return p.val>q.val;
}
priority_queue<hnode> q;
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
freopen("redistricting.in","r",stdin);
freopen("redistricting.out","w",stdout);
n=read();k=read();
scanf("%s",s+1);
rep(i,1,n)
if (s[i]=='H') sum[i]=sum[i-1]+1;else sum[i]=sum[i-1]-1;
memset(dp,0x3f,sizeof(dp));dp[0]=0;
q.push((hnode){0,0});
rep(i,1,n)
{
while (q.top().id<i-k) q.pop();
dp[i]=q.top().val;
if (sum[q.top().id]>=sum[i]) dp[i]++;
q.push((hnode){dp[i],i});
}
printf("%lld",dp[n]);
return 0;
}
Problem 2. Exercise Route
对于一条非树边((u_1,v_1))，将它加入一棵树后树上刚好出现一个环
要使得加入两条非树边((u_1,v_1),(u_2,v_2))后形成一个包含这两条边的环，则原来的两个小环路径必有交
问题转化成有多少对((u_1,v_1).(u_2,v_2))满足在树上的两条路径有交边
先考虑一个一维的问题：给出(n)个区间([L_i,R_i])，询问有多少对区间有交集
做法：对于每个(L_x)，答案减去(L_i<L_x)的区间数；对于每个(R_x)，答案加上(L_I<R_x)的区间数，这样的话对于一个区间([L_x,R_x])，我们统计了所有的(L_xleq L_ileq R_x)的区间，符合区间交的定义
实现：我们类比差分的思想，在(L_i)处打上(+1)的(tag)，之后做一遍前缀和。注意预处理掉(L_i=L_j)的情况
在树上的话，我们将路径((u,v))拆成((u,lca))和((v,lca))，这样做一遍树上差分+树上前缀和即可
具体的，对于一条路径((u,lca))，我们找到(lca)在该路径上的儿子(p)，在(p)上打一个(+1tag)即可
注意避免重复计数
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define fir first
#define sec second
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define maxd 1000000007
#define eps 1e-6
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
const int N=100000;
const double pi=acos(-1.0);
struct node{int to,nxt;}sq[400200];
int all=0,head[200200];
int n,m,sp[200200][2],fa[200200][20],dep[200200],lca[200200];
ll tag[200200],val[200200];
map<pii,int> tax;
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
void add(int u,int v)
{
all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
}
void dfs1(int u,int fu)
{
dep[u]=dep[fu]+1;fa[u][0]=fu;
rep(i,1,19)
fa[u][i]=fa[fa[u][i-1]][i-1];
int i;
for (i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (v!=fu) dfs1(v,u);
}
}
int LCA(int u,int v)
{
if (dep[u]<dep[v]) swap(u,v);
int tmp=dep[u]-dep[v];
per(i,19,0)
if ((tmp>>i)&1) u=fa[u][i];
if (u==v) return u;
per(i,19,0)
if (fa[u][i]!=fa[v][i]) {u=fa[u][i];v=fa[v][i];}
return fa[u][0];
}
int nxt(int u,int fu)
{
if (u==fu) return -1;
per(i,19,0)
if ((fa[u][i]) && (dep[fa[u][i]]>dep[fu])) u=fa[u][i];
return u;
}
void dfs2(int u,int fu)
{
val[u]=val[fu]+tag[u];int i;
for (i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (v!=fu) dfs2(v,u);
}
}
int main()
{
freopen("exercise.in","r",stdin);
freopen("exercise.out","w",stdout);
n=read();m=read();
rep(i,1,n-1)
{
int u=read(),v=read();
add(u,v);add(v,u);
}
dfs1(1,0);ll ans=0;
rep(i,n,m)
{
sp[i][0]=read();sp[i][1]=read();
lca[i]=LCA(sp[i][0],sp[i][1]);
int nx=nxt(sp[i][0],lca[i]),ny=nxt(sp[i][1],lca[i]);
if (nx!=-1) {tag[nx]++;ans-=tag[nx];}
if (ny!=-1) {tag[ny]++;ans-=tag[ny];}
if ((nx!=-1) && (ny!=-1))
{
if (nx>ny) swap(nx,ny);
ans-=tax[mp(nx,ny)];tax[mp(nx,ny)]++;
}//防止(u_1,v_1)(u_2,v_2)被记做2组
}
dfs2(1,0);
rep(i,n,m)
{
int u=sp[i][0],v=sp[i][1];
ans+=(val[u]+val[v]-val[lca[i]]*2);
}
printf("%lld
",ans);
return 0;
}
Problem 3. Train Tracking 2
具有一定思维难度的(dp)题
记所有数为(a_1,a_2,cdots,a_n)
注意到当(c_i eq c_{i+1})时，我们可以确定某些数，这启发着我么去考虑一段(c)值相同的连续段
假设我们有一个极大连续段(c_i=c_{i+1}=cdots=c_j=v)，那么它们能影响到的数一共有(j-i+k)个
记(f_i)表示强制(a_i=v)时的方案数，记(p=10^9-v)，暴力(dp)的话就是枚举上一个为(v)的位置，即(f_i=sum_{j=i-k}^{i-1}p^{i-j-1}f_j)，显然超时
优化的话考虑将上面的那个式子进行错位相减，得到(f_i=(p+1)f_{i-1}-p^kf_{i-k-1})。这个式子的实际意义时，第(i-1)个数可以任意取（不必限制为(v)）的方案数，减去([i-1,i-k])中的数均大于(v)的不合法的方案数，时间复杂度(O(n))，可以接受
接下来就是防止(a_i)被重复考虑或者未被考虑了，若(c_{i-1}>c_i)可以看做是(a_{i+k-1})已被确定，同时它以前的数已在(c_{i-1})中被考虑到（因为(a_{i+k-2}...a_igeq c_{i-1}>c_i)），此时计算的(a)的长度就会减少一个(k)，对于(c_{j+1}>c_j)的情况也是如此
最后就是长度为(len)的序列的答案应为(f_{len+1})，因为我们并未强制(a)的最后一位是(v)
代码十分简单
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define fir first
#define sec second
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define maxd 1000000007
#define eps 1e-6
typedef long long ll;
const int N=1000000000;
const double pi=acos(-1.0);
int n,k,a[100100];
ll dp[100100];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
ll qpow(ll x,int y)
{
ll ans=1;
while (y)
{
if (y&1) ans=ans*x%maxd;
x=x*x%maxd;y>>=1;
}
return ans;
}
ll solve(int val,int len)
{
dp[0]=1;dp[1]=1;
int i;ll p=N-val,tmp=qpow(p,k);
rep(i,2,len+1)
{
dp[i]=(p+1)*dp[i-1]%maxd;
if (i-k-1>=0) dp[i]=(dp[i]-tmp*dp[i-k-1]%maxd+maxd)%maxd;
}
return dp[len+1];
}
int main()
{
freopen("tracking2.in","r",stdin);
freopen("tracking2.out","w",stdout);
n=read();k=read();
rep(i,1,n-k+1) a[i]=read();
int ans=1,i,j=0;
for (i=1;i<=n-k+1;i=j+1)
{
j=i;
while ((j<=n-k+1) && (a[i]==a[j])) j++;j--;
int len=j+k-i;
if ((i>1) && (a[i]<a[i-1])) len-=k;
if ((j<n-k+1) && (a[j]<a[j+1])) len-=k;
if (len>0) ans=ans*solve(a[i],len)%maxd;
}
printf("%lld",ans);
return 0;
}