CSP模拟13
T1考场降智,写了个假的模拟,没签上到。T3空间爆了,直接CE(应该是线段树写挂了).
y
xt在四个角,取最大值,排序.
Code
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[++tot]=max({calc(1,1,i,j),calc(i,j,1,m),calc(i,j,n,1),calc(i,j,n,m)});
}
}
sort(a+1,a+1+tot,cmp);
for(int i=1;i<=n*m;i++){
printf("%d ",a[i]);
}
S
神奇的转化.
$ num= \Sigma _{i=1} ^{n} (k>=i) $ num即大于等于k的数.对于每一个k进行求解.我们现在只关心与k的大小关系不在乎具体数.我们把>=k的看作1,< k 的看做0.最后统计ret为1的方案数 *i!(n-i)!(数不确定).已经是第3次见到这个技巧了,其他两次都是数据结构middle,排序都是求跟中位数差不多的东西.放在DP还是挺妙的.
要滚数组.
Code
signed main(){
// freopen("in","r",stdin);
n=read();
for(int i=1;i<=n-1;i++)
s[i]=read();
fac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=fac[i-1]%mod*i%mod;
dp[1][0][0]=1;
dp[1][1][1]=1;
int now=0;
for(int i=2;i<=n;i++){
memset(dp[now],0,sizeof(dp[now]));
for(int j=0;j<=n;j++){
if(s[i-1]==0){
dp[now][j][0]=(dp[now][j][0]+dp[now^1][j][1]+dp[now^1][j][0])%mod;
if(j){
dp[now][j][1]=(dp[now][j][1]+dp[now^1][j-1][1])%mod;
dp[now][j][0]=(dp[now][j][0]+dp[now^1][j-1][0])%mod;
}
}else{
if(j){
dp[now][j][1]=(dp[now][j][1]+dp[now^1][j-1][1]+dp[now^1][j-1][0])%mod;
}
dp[now][j][1]=(dp[now][j][1]+dp[now^1][j][1])%mod;
dp[now][j][0]=(dp[now][j][0]+dp[now^1][j][0])%mod;
}
}
now^=1;
}
int ans=0;
for(int i=1;i<=n;i++){
ans=(ans+dp[now^1][n-i+1][1]%mod*fac[i-1]%mod*fac[n-i+1]%mod)%mod;
}
printf("%lld ",ans%mod);
return 0;
}
p
结论:对于两个点集$ S,T $ 设他们直径端点的集合为 $ f(S),f(T) $ 那么有 $ f(S \cup T) \subset (f(S) \cup f(T)) $
最大距离其实就是直径,直接线段树维护直径的两个端点.
Code
#include<cstdio>
#include<iostream>
#define lc (k<<1)
#define rc (k<<1|1)
using namespace std;
const int N=1e5+5;
inline 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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
struct Node{
int to,next;
}e[N<<1];
int lk[N],ntot;
void add(int x,int y){
e[++ntot]=(Node){y,lk[x]};
lk[x]=ntot;
}
int n,m;
int dep[N],top[N],son[N],f[N],siz[N];
int dfs1(int x,int fa){
f[x]=fa;dep[x]=dep[fa]+1;
siz[x]=1;
for(int i=lk[x];i;i=e[i].next){
int y=e[i].to;
if(y==fa)
continue;
siz[x]+=dfs1(y,x);
if(siz[y]>siz[son[x]])
son[x]=y;
}
return siz[x];
}
void dfs2(int x,int t){
top[x]=t;
if(son[x])
dfs2(son[x],t);
for(int i=lk[x];i;i=e[i].next){
int y=e[i].to;
if(y==f[x]||y==son[x])
continue;
dfs2(y,y);
}
}
int get_lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
x=f[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
return x;
}
int get_dis(int x,int y){
if(!(x+y))
return -1;
if(!x||!y)
return 0;
return dep[x]+dep[y]-(dep[get_lca(x,y)]*2);
}
struct Tree{
int l,r;
}t[N<<2];
Tree push_up(Tree ls,Tree rs){
Tree ans={0,0};
int dis=0,dis1=0;
dis=get_dis(ls.l,ls.r);
ans=ls;
dis1=get_dis(rs.l,rs.r);
if(dis1>dis)
dis=dis1,ans=rs;
dis1=get_dis(ls.l,rs.l);
if(dis1>dis){
dis=dis1;
ans.l=ls.l,ans.r=rs.l;
}
dis1=get_dis(ls.l,rs.r);
if(dis1>dis){
dis=dis1;
ans.l=ls.l,ans.r=rs.r;
}
dis1=get_dis(ls.r,rs.l);
if(dis1>dis){
dis=dis1;
ans.l=ls.r,ans.r=rs.l;
}
dis1=get_dis(ls.r,rs.r);
if(dis1>dis){
dis=dis1;
ans.l=ls.r,ans.r=rs.r;
}
return ans;
}
void update(int k,int l,int r,int pos){
if(l==r){
if(!t[k].l)
t[k].l=t[k].r=l;
else
t[k].l=t[k].r=0;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid)
update(lc,l,mid,pos);
else
update(rc,mid+1,r,pos);
t[k]=push_up(t[lc],t[rc]);
}
Tree query(int k,int l,int r,int L,int R){
if(L<=l&&r<=R)
return t[k];
int mid=(l+r)>>1;
Tree ans1={0,0},ans2={0,0};
if(L<=mid)
ans1=query(lc,l,mid,L,R);
if(R>mid)
ans2=query(rc,mid+1,r,L,R);
return push_up(ans1,ans2);
}
int main(){
// freopen("in","r",stdin);
n=read(),m=read();
for(int i=1;i<=n-1;i++){
int x=read(),y=read();
add(x,y),add(y,x);
}
dfs1(1,0);dfs2(1,1);
// printf("%d",get_lca(2,4));
while(m--){
int opt=read();
if(opt==1){
int x=read();
update(1,1,n,x);
}else{
int l=read(),r=read();
Tree ans=query(1,1,n,l,r);
printf("%d\n",get_dis(ans.l,ans.r));
}
}
return 0;
}
m
AT_arc096_c
题解
oj卡常.