noip模拟43 solutions
最近确实一直可以直接做掉第一题，不过今天有点不顺利
今天还初步认识了数位dp，之前只是知道而已，现在大概是会了
改题的过程很是艰辛。。。
T1 第一题
就还是树形dp，直接由儿子向父亲合并
对儿子按照子树最大深度排序，先判断是否用而儿子更新儿子，还是新来一个
就切了。。。。
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=1e5+5;
int n;
int to[N*2],nxt[N*2],head[N],rp;
void add_edg(int x,int y){
to[++rp]=y;
nxt[rp]=head[x];
head[x]=rp;
}
int dep[N],mxd[N],fa[N];
void dfs_pre(int x){
dep[x]=dep[fa[x]]+1;
mxd[x]=dep[x];
for(re i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa[x])continue;
fa[y]=x;dfs_pre(y);
mxd[x]=max(mxd[x],mxd[y]);
}
}
struct node{
int who,mxn;
node(){}
node(int x,int y){who=x;mxn=y;}
bool operator < (node x)const{
return mxn<x.mxn;
}
};
int val[N],sum[N];
void dfs_ans(int x){
if(!nxt[head[x]]&&to[head[x]]==fa[x]){
sum[x]=1;
return ;
}
vector<node> vec;vec.clear();
for(re i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa[x])continue;
dfs_ans(y);
vec.push_back(node(y,mxd[y]));
val[x]+=sum[y];
}
sort(vec.begin(),vec.end());
for(re i=0;i<vec.size();i++){
if(i&&vec[i-1].mxn-dep[x]<dep[x])sum[x]--,val[x]+=vec[i-1].mxn-dep[x];
sum[x]+=sum[vec[i].who];val[x]+=val[vec[i].who];
}
}
signed main(){
scanf("%d",&n);
for(re i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
add_edg(x,y);add_edg(y,x);
}
dfs_pre(1);dfs_ans(1);
printf("%d",val[1]);
}
T2 第二题
好像我的做法假了，不对是Varuxn的，他假了
就是我们对每一个需要更新的点，放到SPFA的队列中
每次便利所有的相邻的点，然后更新当前点
再进行一个比较，得到是否需要将其他点放入队列
复杂度玄学就像SPFA一样
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
const int N=1e5+5;
ll n,m,k,maxn;
vector<int> vec[N];
int px[10]={0,0,0,-1,-1,1,1};
int py[10]={0,-1,1,0,1,-1,0};
ll val[N],wal[N],cnt;
ll to[N*12],nxt[N*12],head[N],rp;
void add_edg(int x,int y){
to[++rp]=y;
nxt[rp]=head[x];
head[x]=rp;
}
queue<int> q;
bool vis[N];
bool check(ll x){
ll mx=0,ret=0;
memcpy(val,wal,sizeof(val));
for(re i=1;i<=cnt;i++){
bool flag=false;
for(re j=head[i];j;j=nxt[j])
if(val[to[j]]-val[i]>x){
ret+=val[to[j]]-val[i]-x;
val[i]=val[to[j]]-x;
flag=true;
}
if(flag)q.push(i),vis[i]=true;
}
while(!q.empty()){
int now=q.front();vis[now]=false;q.pop();
mx=0;for(re i=head[now];i;i=nxt[i])
mx=max(mx,val[to[i]]);
if(mx-val[now]>x){
ret+=mx-val[now]-x;
val[now]+=mx-val[now]-x;
}
for(re i=head[now];i;i=nxt[i]){
if(val[now]-val[to[i]]<=x)continue;
ret+=val[now]-val[to[i]]-x;
val[to[i]]+=val[now]-val[to[i]]-x;
if(!vis[to[i]])q.push(to[i]),vis[to[i]]=true;
}
}
return ret<=k;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(re i=1;i<=n;i++){
vec[i].reserve(m+10);vec[i].push_back(0);
for(re j=1;j<=m;j++){
ll x;scanf("%lld",&x);
wal[++cnt]=x;maxn=max(maxn,x);
vec[i].push_back(cnt);
}
}
for(re i=1;i<=n;i++)
for(re j=1;j<=m;j++)
for(re l=1;l<=6;l++){
int x=i+px[l],y=j+py[l];
if(x<=0||x>n||y<=0||y>m)continue;
add_edg(vec[i][j],vec[x][y]);
}
//cout<<cnt<<endl;
ll l=0,r=maxn,mid;
while(l<r){
mid=l+r>>1;
//cout<<mid<<endl;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%lld",r);
}
T3 第三题
这个让我学习了数位dp，好难啊真的，我改了好久才改过
这个好像是从低位到高位吧，我也不太会看这个，没办法，真不会。
我们设f[i][j][s][t]表示，从低到高前i位，一共有j个一，是否卡下界，是否卡上界
里面有当前选择的个数和这些个数的加和
我们就像线段树一样转移，按照没有个数限制的转移
当出现个数限制的时候，就直接先向下搜当前位为0的情况
再向下搜当前位为1的情况，这样就找到了准确的值了
注意，要判断当前dfs是否有限制，没有限制的话，可以用来更新记忆化数组
有限制就不行了，所以还是要弄一个flag来判断一下的
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define pa pair<ll,ll>
#define mpa make_pair
#define fi first
#define se second
const ll inf=0x3f3f3f3f3f3f3f3f;
ll T,l,r,a,b;
pa f[35][35][2][2];
pa dfs(int i,int j,int s,int t,ll limt,int flag){
if(i<0||j<0||!limt)return mpa(0ll,0ll);
if(f[i][j][s][t].fi<=limt&&f[i][j][s][t].fi!=-1)return f[i][j][s][t];
int fro=s&(l>>i),beh=t&(((r>>i)^1)&1);pa fr,af;
if(fro)fr=mpa(0ll,0ll);
else fr=dfs(i-1,j,s&(((l>>i)^1)&1),t&(((r>>i)^1)&1),limt,flag);
if(beh)af=mpa(0ll,0ll);
else af=dfs(i-1,j-1,s&((l>>i)&1),t&((r>>i)&1),limt-fr.fi,flag);
if(!flag)f[i][j][s][t]=mpa(fr.fi+af.fi,fr.se+af.se+af.fi*(1ll<<i));
return mpa(fr.fi+af.fi,fr.se+af.se+af.fi*(1ll<<i));
}
ll get_ans(ll x){
ll ret=0;
for(re i=0;i<=30;i++){
if(x>=f[30][i][1][1].fi){
if(f[30][i][1][1].fi==-1)continue;
x-=f[30][i][1][1].fi;
ret+=f[30][i][1][1].se;
continue;
}
ret+=dfs(30,i,1,1,x,1).se;
break;
}
return ret;
}
signed main(){
scanf("%lld",&T);
while(T--){
memset(f,-1,sizeof(f));//cout<<f[1][1][1][1].fi<<endl;
scanf("%lld%lld%lld%lld",&l,&r,&a,&b);
a=r-l+1-a+1;b=r-l+1-b+1;
if(a>b)swap(a,b);
f[0][0][0][0]=f[0][0][0][1]=mpa(1ll,0ll);
f[0][0][1][0]=f[0][0][1][1]=mpa((l^1ll)&1ll,0ll);
f[0][1][0][0]=f[0][1][1][0]=mpa(1ll,1ll);
f[0][1][0][1]=f[0][1][1][1]=mpa(r&1ll,r&1ll);
for(re i=1;i<=30;i++){
f[30][i][1][1]=dfs(30,i,1,1,inf,0);
}
printf("%lld\n",get_ans(b)-get_ans(a-1));
}
}
T4 第四题
这，，，，一眼就是dp吧(wqnmd,lz反正看不出来)
我只是解释一下这个\(k^2\)是如何拆分的
这个好说，后面直接展开就是前面的了
那么后面的就可以转换成组合数了，这样的话直接就变成对组合的求解了
具体含义就是，当前序列中一共可以选出多少对K来在+K
这个+K就可以解释成我一共有多少种方案可以选到K，
至于后面的g为什么是n-i-1，因为我们钦定有一位是选择K的
而K这一位又可以随意移动，所以×(n-i)
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
const int N=3005;
ll n,mod;
ll f[N][N],g[N][N],beh[N][N];
ll ans[N];
signed main(){
scanf("%lld%lld",&n,&mod);
f[0][0]=1;
for(re i=1;i<=n;i++)
for(re j=1;j<=i;j++)
f[i][j]=(f[i-1][j]*j+f[i-1][j-1])%mod;
for(re i=1;i<=n;i++)g[0][i]=1;
for(re i=1;i<=n;i++)
for(re j=1;j<=n;j++)
g[i][j]=(g[i-1][j]*j+g[i-1][j+1])%mod;
for(re i=1;i<=n;i++)
for(re j=n;j>=1;j--)
beh[i][j]=(beh[i][j+1]+f[i-1][j]*(g[n-i][j]+2*(n-i)*g[n-i-1][j]%mod))%mod;
for(re i=1;i<=n;i++)
for(re x=1;x<=n;x++){
ans[x]=(ans[x]+beh[i][x])%mod;
/*for(re y=x;y<=n;y++)
ans[x]=(ans[x]+f[i-1][y]*(g[n-i][y]+2*(n-i)*g[n-i-1][y]%mod))%mod;*/
ans[x]=(ans[x]+f[i-1][x-1]*(g[n-i][x]+2*(n-i)*g[n-i-1][x]%mod))%mod;
}
for(re i=1;i<=n;i++)printf("%lld ",ans[i]);
}