做题笔记[AGC001]

做题笔记[AGC001]

A - BBQ Easy

标签：贪心

难度：★☆☆☆☆

题目大意

将 \(2n\) 个数分为 \(n\) 组，每个数有值 \(L_i\)，每组两个数，每个数都被且只被分到一组。一组的权值是两个数值的最小值，分组方案的值就是每组值之和，求分组方案的最大值。

数据范围

\(1\le n\le 100,1\le L_i\le 100\)。

解题思路

考虑贪心。将数组排序后按顺序两两分组即可。

参考代码

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 205
int n,a[MAXN];
int main(){
    cin>>n;
    n*=2;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    int ans=0;
    for(int i=1;i<=n;i+=2) ans+=a[i];
    cout<<ans;
    return 0;
}

B - Mysterious Light

标签：思维

难度：★★★☆☆

题目大意

有一个边长为 \(N\) 的三枚镜子构成的正三角形，顶点为 \(A, B, C\)。有一束光线，放在 \(AB\) 段的 \(P\) 点上，使得 \(AP=X\)。这个步枪将会沿着平行于 \(BC\) 的方向发射一道光。

光以直线传播，以镜子的形式反射，也会被自己的轨迹反射，当光回到初始点的时候，光被吸收。

下面的图显示了当 \(N=5, x=2\) 时的光轨迹。

给定 \(N\) 和 \(x\)，求出光线的总长度。

数据范围

\(2≤N≤10^{12}\)，\(1≤x≤N-1\)。

解题思路

把这个三角形看成被对角线分割的正方形，手动模拟长度，可以发现每一段的长度是一个辗转相减的过程，最后剩下的那一段就是 \((N,x)\)。可以得到答案就是 \(3(N-(N,x))\)。

参考代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,x;
int main(){
    cin>>n>>x;
    cout<<3ll*(n-__gcd(x,n));
    return 0;
}

C - Shorten Diameter

标签：树论、枚举

难度：★★☆☆☆

题目大意

给你一棵 \(N\) 个点的无向树，定义点 \(u\) 和 \(v\) 之间的距离是从 \(u\) 到 \(v\) 的简单路径上的边数。

你需要删除一些点，使树的直径小于等于 \(K\)，当且仅当删除某点不会对树的联通性产生影响时才可以删除。

问至少删除多少点才可以满足要求。

数据范围

\(2≤N≤2000\)，\(1≤K≤N-1\)。

解题思路

因为 \(N\) 比较小，我们考虑枚举每个点，计算以这个点为中心时，最少删去多少个点才能满足要求，具体地：

• 若 \(N\) 为偶数，我们设这个点为中心，遍历整张图，删去距离这个点超过 \(k/2\) 的点。
• 若 \(N\) 为奇数，我们设这个点连接的某一条边为中心（枚举），遍历整张图，删去距离这个点超过 \(\lfloor k/2 \rfloor\)。

时间复杂度 \(O(n^2)\)。

参考代码

#include<iostream>
#include<vector>
using namespace std;
#define MAXN 2005
int n,k,cnt,ans=0x3f3f3f3f;
vector<int> g[MAXN];
void dfs(int u,int fa,int dis){
    cnt+=(dis>k/2);
    for(auto v:g[u]){
        if(v==fa) continue;
        dfs(v,u,dis+1);
    }
}
int main(){
    cin>>n>>k;
    for(int x,y,i=1;i<n;i++){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    if(k&1){
        for(int u=1;u<=n;u++){
            for(auto v:g[u]){
                cnt=0;
                dfs(v,u,0);
                dfs(u,v,0);
                ans=min(ans,cnt);
            }
        }
        cout<<ans;
    }
    else{
        for(int u=1;u<=n;u++){
            cnt=0;
            for(auto v:g[u]){
                dfs(v,u,1);
            }
            ans=min(ans,cnt);
        }
        cout<<ans;
    }
    return 0;
}

D - Arrays and Palindrome

标签：构造、回文串

难度：★★★★☆

题目大意

给定一个长 \(m\) 的序列 \(A\)，和参数 \(n=\sum\limits_{i=1}^m A_i\)，构造两个正整数数列 \(a,b\)，满足：

• \(a\) 数列的数字总和是 \(N\) 且是 \(A\) 序列的一个排列；
• \(b\) 数列的数字总和是 \(N\)；
• 如果存在某个数列 \(s\) 满足以下两个条件， 则 \(s\) 的所有元素必定相同：
  • 对于 \(s\) 的最开始的 \(a_1\) 个元素，接下来的 \(a_2\) 个元素，更后面的 \(a_3\) 个，等等，都构成回文串；
  • 对于 \(s\) 的最开始的 \(b_1\) 个元素，接下来的 \(b_2\) 个元素，更后面的 \(b_3\) 个，等等，都构成回文串。

数据范围

\(1\le N,A_i\le 10^5,1\le M\le 100\)。

解题思路

一道很好的构造题。

考虑构成一个长度为 \(n\) 的回文串，会有 \(n/2\) 个相等关系。而让所有元素相等，必须交叉安排两个数组，使得串首尾都留出一个接口，如下图：

不难发现，如果 \(A\) 中有大于两个长度为奇数的串，就无法满足制约关系。对于合法的解，不妨将长度为奇数的串转到两边，然后让 \(b\) 数组差 \(a\) 的空子安排就好。

参考代码

#include<iostream>
using namespace std;
#define MAXN 100005
int n,m,a[MAXN];
int main(){
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        cnt+=(a[i]&1);
    }
    if(cnt>2){
        cout<<"Impossible";
        return 0;
    }
    for(int i=1;i<=m;i++) if(a[i]&1){
        if(i!=1) swap(a[i],a[1]);
        break;
    }
    for(int i=m;i>1;i--) if(a[i]&1){
        if(i!=m) swap(a[i],a[m]);
        break;
    }
    for(int i=1;i<=m;i++) cout<<a[i]<<" ";
    cout<<endl;
    if(m==1){
        if(n!=1) cout<<2<<endl<<a[1]-1<<" "<<1;
        else cout<<1<<endl<<1;
        return 0;
    }
    else{
        if(a[1]==1) cout<<m-1<<endl;
        else{
            cout<<m<<endl;
            cout<<a[1]-1<<" ";
        }
        for(int i=2;i<m;i++) cout<<a[i]<<" ";
        cout<<a[m]+1;
    }
    return 0;
}

E - BBQ Hard

标签：组合计数、动态规划

难度：★★★★☆

题目大意

有 \(n\) 个数对 \((a_i, b_i)\)，求

\[ \sum_{i=1}^{n}\sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j} \]

答案对 \(10 ^ 9 + 7\) 取模。

数据范围

\(2\le N\le 2\times 10^5,1\le A_i,B_i\le 2000\)。

解题思路

首先考虑一个组合式 \(x+y\choose x\) 的几何意义，就是从点 \((0,0)\) 走到 \((x,y)\)，每一步只能向右或向上走的方案数。这个式子是可以转移的： \[ {x+y\choose x }={x+y-1\choose x}+{x+y\choose x-1} \] 单独求一次可以在 \(O(A_iB_i)\) 的时间求出来。现在考虑题目中的式子，也就是说对于每个 \(1\le i<j\le n\)，求从 \((0,0)\) 按照上述方案走到 \((a_i+a_j,b_i+b_j)\) 的方案数。

为了简化思考，我们现在改变一下表述方式：对于每个 \(1\le i<j\le n\)，求从 \((-a_j,-b_j)\) 走到 \((a_i,b_i)\)，即向左下平移，但是大小不变。我们以 \((a_i,a_j)\) 为主元，求解其他点（负的）到这个点的方案和即可。

我们考虑动态规划。开始给每个负点 \((-a_i,-b_i)\) \(1\) 的权值，设计 \(f_{i,j}\) 表示从左下角走到这个点的方案数，求解即可。

注意上述状态求解了所有的 \(i,j\) 的解，我们需要删去 \(i,i\) 的解，通过组合计数可得这部分要删去的解的个数是 \(\sum\limits_{i=1}^n{2a_i+2b_2\choose2a_i}\)。因为 \(i,j\) 和 \(j,i\) 算重，需要将答案数除以 \(2\)。

参考代码

#include<iostream>
using namespace std;
#define MAXN 200005
#define MAXA 2005
#define mod 1000000007
typedef long long ll;
ll f[MAXA<<1][MAXA<<1],n,a[MAXN],b[MAXN];
ll maxa,maxb,ans;
ll mul[MAXA<<2],inv[MAXA<<2];
int C(int n,int m){
    return mul[n]*inv[m]%mod*inv[n-m]%mod;
}
ll qpow(ll a,ll b){
    ll w=1;
    while(b){
        if(b&1) w=w*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return w;
}
void init(){
    mul[0]=1;
    for(int i=1;i<=4009*2;i++) mul[i]=mul[i-1]*i%mod;
    inv[4009*2]=qpow(mul[4009*2],mod-2);
    for(int i=4009*2-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int main(){
    init();
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        f[2005-a[i]][2005-b[i]]++;
        maxa=max(maxa,a[i]);
        maxb=max(maxb,b[i]);
    }
    for(int i=2005-maxa;i<=2005+maxa;i++){
        for(int j=2005-maxb;j<=2005+maxb;j++){
            f[i][j]=(f[i][j]+f[i-1][j]+f[i][j-1])%mod;
        }
    }
    for(int i=1;i<=n;i++) ans=(ans+f[2005+a[i]][2005+b[i]])%mod;
    for(int i=1;i<=n;i++) ans=(ans-C((a[i]+b[i])<<1,a[i]<<1))%mod;
    ans=1ll*ans*inv[2]%mod;
    ans=(ans%mod+mod)%mod;
    cout<<ans;
    return 0;
}

F - Wide Swap

标签：思维、拓扑排序、线段树

难度：★★★★★

题目大意

给出一个元素集合为 \(\{1,2,\dots,N\}\) 的排列 \(P\)，当有 \(i,j\) \((1\leq i<j\leq N)\) 满足 \(j-i\geq K\) \((1\leq K\leq N-1)\) 且 \(|P_{i}-P_{j}|=1\)时，可以交换 \(P_{i}\) 和 \(P_{j}\)。

求：可能排列中字典序最小的排列。

数据范围

\(1\leq N\leq 5\times10^5\) 。

解题思路

考虑按照上述方式交换元素有什么特殊性质。

我们建立 \(P\) 的反置换 \(Q\)，即 \(P_{Q_i}=i\)，将 \(P_i\) 的值作为 \(Q\) 的下标，\(i\) 作为 \(Q\) 的值。不难发现，可以交换 \(Q_i\) 和 \(Q_{i+1}\) 的条件是 \(|Q_i-Q_{i+1}|\le K\)。

通过人类的智慧思考发现，若存在一组 \(1\le i<j\le N\)，满足 \(|Q_i-Q_j|>K\)，不管怎样交换，这两个数的相对位置不会改变。

这个性质放回到 \(P\) 中，等价于：\(\forall 1\le i \le N,j\in(i-K,i+k),i\not=j\)，若 \(P_i\) 和 \(P_j\) 满足偏序关系 \(P_i<P_j\)，则无论怎样交换，最后在 \(i,j\) 位置上的数仍满足偏序关系 \(P_i<P_j\)。

例子 \(\quad\) 对于排列 \(P=\{4,5,7,8,3,1,2,6\}\)，有 \(P_2=5,P_3=7\)，在 \(K=3\) 的情况下，无论怎样交换，两个位置上的数仍满足小于关系。例如交换成 \(P'=\{1,2,6,7,5,3,4,8\}\)，满足 \(2<6\)。

这样，我们可以找出所有的偏序关系，建图后通过拓扑排序，就可以知道这些数的最小排列。

例如，我们按照大于关系见图，即找到下标 \((i-K,i+K)\) 内比 \(P_i\) 小的数连边，按照拓扑顺序给下标从 \(N\) 到 \(1\) 赋值。

但是这个图是 \(O(NK)\) 大小的，无法建图，我们利用这道题的特殊性质：每个点可能连出边的节点范围是 \((i-K,i+K)\)。一开始没有入度的点就是这个范围内的最大值，可以利用线段树查找。然后在左右子区间找区间最大值，再检查是否合法即可（见代码）。

时间复杂度 \(O(N\log N)\)。

参考代码

#include<iostream>
#include<queue>
using namespace std;
#define MAXN 500005
#define mid ((tree[p].l+tree[p].r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
#define inf 0x3f3f3f3f
typedef pair<int,int> pii;
int n,k,a[MAXN],ans[MAXN];
struct node{
    int l,r,maxx,pos;
}tree[MAXN<<2];
priority_queue<int> q;
void update(int p){
    if(tree[ls].maxx>tree[rs].maxx){
        tree[p].maxx=tree[ls].maxx;
        tree[p].pos=tree[ls].pos;
    }
    else{
        tree[p].maxx=tree[rs].maxx;
        tree[p].pos=tree[rs].pos;
    }
}
void build(int l,int r,int p){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].maxx=a[l];
        tree[p].pos=l;
        return;
    }
    build(l,mid,ls);
    build(mid+1,r,rs);
    update(p);
}
pii query(int l,int r,int p){
    if(l>r) return {-inf,0};
    if(l<=tree[p].l&&r>=tree[p].r) return {tree[p].maxx,tree[p].pos};
    if(l>mid) return query(l,r,rs);
    if(r<=mid) return query(l,r,ls);
    pii lc=query(l,r,ls),rc=query(l,r,rs),c;
    if(lc.first>rc.first) c=lc;
    else c=rc;
    return c;
}
void modify(int goal,int p){
    if(tree[p].l==tree[p].r){
        tree[p].maxx=-inf;
        return;
    }
    if(goal<=mid) modify(goal,ls);
    else modify(goal,rs);
    update(p);
}
void chk(int p){
    if(p==0) return;
    pii now=query(max(1,p-k+1),min(p+k-1,n),1);
    if(now.second==p&&now.first!=-inf) q.push(p);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,n,1);
    for(int i=1;i<=n;i++) chk(i);
    int now=n;
    while(q.size()){
        int u=q.top();
        q.pop();
        ans[u]=now--;
        modify(u,1);
        int lpos=query(max(1,u-k+1),u-1,1).second;
        int rpos=query(u+1,min(u+k-1,n),1).second;
        chk(lpos);chk(rpos);
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}