[比赛题解]CWOI2019-1
比赛日期：2019.10.12
T1
一道神仙DP题。
我们考虑\(dp[i][j][k]\)表示最后\(i\)位数,\(i-1\)位都是9，最后一位为\(j\)，最后\(i\)位数以前的部分最大数为\(k\)时，把最后\(i\)位数减到负数最小需要多少次。\(re[i][j][k]\)代表这个状态下，把这个数减到负数时，负数+10的值。
那么每次操作就会减去\(min(最后i位数中最小值,k)\)。
我们先预处理出\(dp\)和\(re\)数组（从低位向高位递推）。
然后读入给的数，考虑把除1之外所有位数变成9。那么从第二位向高位枚举，每次把当前位减掉1，直到减到9（最后一次注意退位），同时记录在这个过程中走了多少步。因为对于一个前缀全为9，最后一位无论是什么，减去一个小于10的数得到的数的前缀还是全为9。
全部变成9之后即可从高位到低位统计答案即可。
貌似状态设置成“全是9”也可以，但是没试过。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long dp[20][10][10],res[20][10][10];
long long ans=0;
char s[20];
int num[20];
void init() {
for(int i=0;i<=9;i++) {
for(int j=0;j<=9;j++) {
if(i<j) {//当前位较小
dp[1][i][j]=1;
res[1][i][j]=i-j+10;
}
else {//当前位较大
dp[1][i][j]=2;
res[1][i][j]=10-j;
}
}
}
for(int i=2;i<=18;i++) {
for(int j=0;j<=9;j++) {
for(int k=0;k<=9;k++) {
res[i][j][k]=j;
for(int n=9;n>=0;n--) {
dp[i][j][k]+=dp[i-1][res[i][j][k]][max(n,k)];
res[i][j][k]=res[i-1][res[i][j][k]][max(n,k)];
}
}
}
}
}
void just_do_it() {
scanf("%s",s+1);int len=strlen(s+1);
for(int i=1;i<=len;i++)num[i]=s[i]-'0';
reverse(num+1,num+1+len);
int now=num[1];
for(int i=2;i<=len;i++) {
while(num[i]!=9) {
int ma=0;
for(int j=i;j<=len;j++)ma=max(ma,num[j]);
if(!ma)break;//无法退位
num[i]--;
for(int j=i;num[j]<0;j++) {//退位
num[j]=9;num[j+1]--;
}
ans+=dp[i-1][now][ma];
now=res[i-1][now][ma];
}
}
for(int i=len;i>=2;i--) {
while(num[i]) {
ans+=dp[i-1][now][num[i]];
now=res[i-1][now][num[i]];
num[i]--;
}
}
if(now)ans++;
printf("%lld",ans);
}
int main() {
init();
just_do_it();
}T2
我们考虑三种情况
- 被覆盖点为祖先-后代关系
- 被覆盖点没有祖先-后代关系
- 被覆盖点相等
这三类都可以转换为统计某些点的子树内点的个数。（比如说第二种情况就是统计路径两端分别在\(u,v\)子树内的路径条数）。对于一个端点，我们可以把他转换为\(dfs\)序在一定范围内的点，而对于一条路径，我们可以把它转换成矩阵坐标在一定范围内的点。然后扫描线二维数点就好了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
#define ll long long
using namespace std;
const int maxn=1e5+1000;
int root[maxn],ls[maxn*80],rs[maxn*80],head[maxn],cnt,idx,n,m,dep[maxn],po[maxn],f[maxn][23],size[maxn],dfn[maxn],dfn_cnt;
ll ans1=0,ans2,ans3,sum[maxn*80];
vector<int>list[maxn];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
struct gg {
int u,v,next;
}side[maxn*2];
//pair<int,int>ori[maxn];
struct data {
int first,second;
}ori[maxn];
void insert(int u,int v){
struct gg add={u,v,head[u]};side[++cnt]=add;head[u]=cnt;
}
void dfs(int now,int fa) {
dep[now]=dep[fa]+1;size[now]=1;dfn[now]=++dfn_cnt;
f[now][0]=fa;for(int i=1;i<=22;i++)f[now][i]=f[f[now][i-1]][i-1];
for(int i=head[now];i;i=side[i].next) {
int v=side[i].v;if(v==fa)continue;
dfs(v,now);size[now]+=size[v];
}
}
int lca(int u,int v) {
if(dep[u]<dep[v])swap(u,v);
for(int i=22;i>=0;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i];
if(u==v)return u;
for(int i=22;i>=0;i--)if(f[u][i]!=f[v][i]){u=f[u][i],v=f[v][i];}
return f[u][0];
}
int build(int l,int r) {//主席数，版本表示u的范围，线段树表示v的范围
int now=++idx;
if(l==r)return now;
int mid=(l+r)>>1;
ls[now]=build(l,mid);
rs[now]=build(mid+1,r);
return now;
}
bool cop(data x,data y) {
return x.first<y.first;
}
int insert(int sync,int l,int r,int tar) {
int now=++idx;
ls[now]=ls[sync],rs[now]=rs[sync],sum[now]=sum[sync]+1;
if(l==r)return now;
int mid=(l+r)>>1;
if(tar<=mid) {
ls[now]=insert(ls[sync],l,mid,tar);
}
else {
rs[now]=insert(rs[sync],mid+1,r,tar);
}
return now;
}
ll query(int sy1,int sy2,int l,int r,int tl,int tr) {
ll tot=sum[sy2]-sum[sy1];
if(tl<=l&&r<=tr)return tot;
tot=0;int mid=(l+r)>>1;
if(tl<=mid) {
tot+=query(ls[sy1],ls[sy2],l,mid,tl,tr);
}
if(tr>=mid+1) {
tot+=query(rs[sy1],rs[sy2],mid+1,r,tl,tr);
}
return tot;
}
int jump(int l,int h) {
for(int i=22;i>=0;i--)if(dep[f[l][i]]>dep[h])l=f[l][i];
return l;
}
signed main() {
scanf("%lld%lld",&n,&m);
for(int i=1;i<n;i++){int u,v;scanf("%lld%lld",&u,&v);insert(u,v);insert(v,u);}
dfs(1,0);
for(int i=1;i<=m;i++) {
scanf("%lld%lld",&ori[i].first,&ori[i].second);
if(dep[ori[i].first]>dep[ori[i].second])swap(ori[i].first,ori[i].second);
if(ori[i].first==ori[i].second)po[ori[i].first]++;
list[dfn[ori[i].first]].push_back(dfn[ori[i].second]);
list[dfn[ori[i].second]].push_back(dfn[ori[i].first]);
}
root[0]=build(1,m);sort(ori+1,ori+1+m,cop);
for(int i=1;i<=n;i++) {
root[i]=root[i-1];
for(int j=0;j<list[i].size();j++)root[i]=insert(root[i],1,n,list[i][j]);
}
//for(int i=1;i<=n;i++)
for(int i=1;i<=m;i++) {
int u=ori[i].first,v=ori[i].second;//查询u，v被多少路径包含
//int lu,lv,ru,rv;
if(lca(u,v)==u) {//祖先-儿子关系
int p=jump(v,u);
ans1+=query(root[0],root[dfn[p]-1],1,n,dfn[v],dfn[v]+size[v]-1);
ans1+=query(root[dfn[p]+size[p]-1],root[n],1,n,dfn[v],dfn[v]+size[v]-1);
}
else {
ans1+=query(root[dfn[u]-1],root[dfn[u]+size[u]-1],1,n,dfn[v],dfn[v]+size[v]-1);
// ans1+=query(root[dfn[v]-1],root[dfn[v]+size[v]-1],1,n,dfn[u],dfn[u]+size[u]-1);
}
ans1--;
}
ans2=m*(m-1)/2;ans3=gcd(ans1,ans2);
cout<<ans1/ans3<<'/'<<ans2/ans3;
return 0;
}