noone___'s blog
0%

30801202-AGC001

发表于 更新于 分类于
AGC001

B

给出光源位置，求反射总距离

考虑到 $N\leq 10^{12}$ ，找规律

每次看成从一个平行四边形的右下角 $(a,b)$ 向外发射

所以下一个平行四边形状态为：

显然任意 $a,b$ 为 $0$ 时终止

设 $f(a,b)$ 为从点 $(a,b)$ 开始的路径长度，则

然而显然能找到规律，路径总长度为 $n-\gcd(n,x)$

这十分玄学，在VP的时候猜的，还不会证qwq

1
2
3
4
5
6
7
ll n,x;
int main(){
    scanf("%lld%lld",&n,&x);
    printf("%lld\n",3*(n-__gcd(n,x)));
    getchar(),getchar();
    return 0;
}

C

删除树的一些叶节点使直径 $\leq k$ 求最少删除的点数

考虑到 $n\leq 2000$ ,所以 是dp 可以考虑枚举中心

再按 $n$ 的奇偶考虑一下中心是边还是点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int N=2e3+100;
int head[N],Next[N<<1],ver[N<<1],tot;
int n,k,ans=INT_MAX,d[N][N];

inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot; ver[++tot]=u,Next[tot]=head[v],head[v]=tot;}

void dfs(int now,int fa,int *d){
    for(rei i=head[now];i;i=Next[i]){
        rei y=ver[i]; if(y==fa) continue;
        d[y]=d[now]+1; dfs(y,now,d);
    }
}

int main(){
    scanf("%d%d",&n,&k);
    for(rei i=1,u,v;i<n;++i){ scanf("%d%d",&u,&v); add(u,v);}
    for(rei i=1;i<=n;++i) dfs(i,0,d[i]);
    if(k&1){
        for(rei i=1;i<=tot;i+=2){
            rei u=ver[i],v=ver[i+1],res=0;
            for(rei i=1;i<=n;++i) res+=d[u][i]>k/2 && d[v][i]>k/2;
            ans=min(res,ans);
        }
    }
    else{
        for(rei i=1;i<=n;++i){
            rei res=0;
            for(rei j=1;j<=n;++j) res+=d[i][j]>k/2;
            // printf("%d\n",res);
            ans=min(ans,res);
        }
    }
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}

D

给定了数列 $A$ 的重排列，构造出数列 $A,B$ ，满足 $\sum_A=\sum_B$ ，且能由两数列划分出的回文串的字符串只由同种字符构成

神仙构造题

按回文的对应相等关系连边，例，对于 $a_1$ ，$1\rightarrow a_1 , 2\rightarrow a_1-1 , …$ ，依次连边，$b$ 同理

满足条件当且仅当将其连成一个连通块，每次连的边数为 $\sum_{i=1}\left\lfloor \frac{a_i}{2} \right\rfloor$

显然若有 $2$ 个以上的 $a_i$ 为奇数则无法构成连通块

先考虑特殊情况：当 $M=1$ 只需令 $a_1=N,b_1=1,b_2=N-1$ 即可

推广可得：所有奇数放在开头结尾构成 $A$,再使开头 $+1$ ,结尾 $-1$ 构造 $B$

可以发现这样使中间的连边错开且前后两边错开，边数恰为 $n-1$ ，构成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N=110;
int n,a[N],b[N];

int main(){
    scanf("%*d%d",&n);
    for(rei i=0;i<n;++i) scanf("%d",&a[i]);
    if(n==1) return *a==1 ? puts("1\n1\n1\n") : printf("%d\n2\n1 %d\n",*a,*a-1) ,0;
    rei mid=partition(a,a+n,[](const int x)->bool{ return x%2; })-a;
    if(mid>2) return puts("Impossible"),0;
    a[n]=*a;
    for(rei i=1;i<=n;++i) printf("%d%c",a[i],i==n ? 10 : 32);
    memcpy(b+1,a+1,n<<2);
    ++b[1],--b[n],n-=!b[n];
    printf("%d\n",n);
    for(rei i=1;i<=n;++i) printf("%d%c",b[i],i==n ? 10 : 32);
    getchar(),getchar();
    return 0;
}

E

求 $\displaystyle{\sum_{i=1}^n\sum_{j=i+1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j}}$

在焦作一中听过

考虑组合数的几何意义，$\binom{x+y}{x}$ 即为从 $(0,0)\rightarrow (x,y)$ 的方案数

$\binom{a_i+b_i+a_j+b_j}{a_i+a_j}$ 即为从点 $(0,0) \ \Rightarrow \ (a_i+a_j,b_i+b_j)$ 的方案数，平移得 $(-a_i,-b_i) \ \Rightarrow \ (a_j,b_j)$ 的方案数，dp即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N=2e5+100,M=2100,S=2050;
const int mod=1e9+7,INV2=5e8+4;
ll a[N],b[N],f[M<<1][M<<1],mul[M<<2],inv[M<<2];
int n; ll ans;

inline void fix(ll &x){ while(x>=mod) x-=mod; while(x<0) x+=mod;}
inline int qpow(ll x,ll y){ rei res=1; while(y){ if(y&1) res=(ll) res*x%mod; x=(ll) x*x%mod; y>>=1;} return res;}
inline ll get_inv(ll x){ return qpow(x,mod-2)%mod;}
inline ll get_C(int n,int m){ return mul[n]*inv[n-m]%mod *inv[m]%mod;}
inline void init(){
    mul[0]=1,inv[0]=get_inv(mul[0]);
    for(rei i=1;i<=8000;++i) mul[i]=mul[i-1]*i%mod,inv[i]=get_inv(mul[i]);
}

int main(){
    init();
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d%d",&a[i],&b[i]),++f[ S-a[i] ][ S-b[i] ];
    for(rei i=1;i<=(S<<1);++i) for(rei j=1;j<=(S<<1);++j) fix(f[i][j]+=(f[i-1][j]+f[i][j-1])%mod);
    for(rei i=1;i<=n;++i) fix(ans+=(((f[ S+a[i] ][ S+b[i] ]-get_C( (a[i]<<1)+(b[i]<<1),(a[i]<<1))+mod)%mod)+mod)%mod);
    fix(ans*=INV2);
    printf("%lld\n",ans);
    getchar(),getchar();
    return 0;
}

F

给定排列 $P$，当且仅当 $i,j$ 满足 $|p_i-p_j|=1$ 且 $|i-j|\geq k$ 是可以交换 $p_i$ 和 $p_j$ ，求最终字典序最小的排列

又是我不会的神仙题

将下标与权值交换位置，即构造序列 $q_{p_i}=i$

由此有很好的性质：

  • 变换的条件变为：当 $|q_i-q_{i+1}|\geq k$ 时交换 $q_i,q_{i+1}$ , 那么对于 $q_i$ ,$q_j\in [q_i-k+1,q_i+k-1]$ 始终在它后面

  • 字典序最小可以转变为下标尽量小，权值尽量小，所以拓扑+贪心即可

另：建图可以优化边数，用线段树维护偏序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
const int N=5e5+100;
const int INF=0x3f3f3f3f;
int head[N],ver[N<<1],Next[N<<1],in[N],tot;
int val[N<<2];
int n,m,k,ans[N],p[N];
priority_queue<PII> q;

inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot,++in[v];}
namespace ST{
    void change(int now,int l,int r,int pos,int v){
        val[now]=min(val[now],v); if(l==r) return ;
        rei mid=l+r>>1;
        if(pos<=mid) return change(now<<1,l,mid,pos,v);
        else return change(now<<1|1,mid+1,r,pos,v);
    }
    int query(int now,int l,int r,int L,int R){
        if(L>R) return INF;
        if(L<=l && r<=R) return val[now];
        rei res=INF,mid=l+r>>1;
        if(L<=mid) res=min(res,query(now<<1,l,mid,L,R));
        if(R>mid) res=min(res,query(now<<1|1,mid+1,r,L,R));
        return res;
    }
}

int main(){
    memset(val,0x3f,sizeof val);
    scanf("%d%d",&n,&k);
    for(rei i=1,x;i<=n;++i) scanf("%d",&x),p[x]=i;
    for(rei x=n,y;x;--x){
        y=ST::query(1,1,n,max(p[x]-k+1,1),p[x]-1); if(y!=INF) add(x,y);
        y=ST::query(1,1,n,p[x]+1,min(p[x]+k-1,n)); if(y!=INF) add(x,y);
        ST::change(1,1,n,p[x],x);
    }
    for(rei i=1;i<=n;++i) if(!in[i]) q.push(mk(-p[i],i));
    while(q.size()){
        rei x=q.top().second; q.pop();
        ++m; ans[ p[x] ]=m;
        for(rei i=head[x];i;i=Next[i]){
            rei y=ver[i]; if(--in[y]==0) q.push(mk(-p[y],y));
        }
    }
    for(rei i=1;i<=n;++i) printf("%d\n",ans[i]);
    getchar(),getchar();
    return 0;
}