周赛Round31

D.map模拟静态数组

给一个数列，要完成两种操作：在一个指定元素的右侧插入，删除指定元素。 维护序列首先考虑一下最经典的两种结构：数组和链表，数组插入和删除都需要O(n)，而本题操作次数有1e5，舍去。链表插入是只需要O(1)，但是寻找插入位置需要O(n)，也不行。

看起来都不行了，那怎么办呢？实际上这是我们的思路被这两种经典模型限制住了，除了数组和指针链表外，还有一种维护序列插入删除的结构：静态链表，对于每一个元素，直接记录他左右的元素，那么插入时，就可以O(1)找到插入位置，O(1)完成修改。不过本题元素大小有1e9，单纯用数组的话会MLE，可以用map进行离散化，代价是寻找插入位置从O(1)变成了O(logn)，但也还能接受。

需要注意的是在最左侧插入删除需要特判，也可以先插入inf和-inf作为两侧元素，就不用特判了。

using namespace std;
map<int,int>l,r;
int main(){
    int q,x,y,head=0,cnt=0;
    cin>>q;
    for(int i=1;i<=q;i++){
        int op;
        cin>>op;
        if(op==1){
            cnt++;
            cin>>x>>y;
            if(y==0){//最左侧插入
                if(head){//如果不为空
                    l[head]=x;
                    r[x]=head;
                    head=x;
                }
                else head=x;//如果为空
            }
            else{//其他位置插入
                r[x]=r[y];
                l[x]=y;
                l[r[y]]=x;
                r[y]=x;
            }
        }
        else{
            cnt--;
            cin>>x;
            if(head==x){//删除最左侧
                head=r[x];
            }
            else{//删除其他位置
                r[l[x]]=r[x];
                l[r[x]]=l[x];
            }
        }
    }
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++){
        cout<<head<<' ';
        head=r[head];
    }
}

还有另一种思路也是可行的，使用指针链表，然后用map<int,node*>记录每个元素所在节点的地址，也可以O(logn)找到操作元素，O(1)操作

E.背包dp变形

可以把数列中一些元素取反，问是否能使数列元素和为零，如果可以，求最小操作次数。

由于元素个数2e2，元素绝对值不超过2e2，进行任意操作，元素和绝对值都不会超过4e4，一共只有8e4种可能的取值，那么可以用一种相当暴力的办法：维护一个dp(i,j)，记录对于前i个元素，使数列元素和为j，最少需要的操作次数，对于每一个i，都遍历8e4个可能取值进行转移。

具体来说，对于i,j，第i个元素为x，那么当前元素x可以选择保持初始符号，直接加进来，那么dp(i,j)从dp(i-1,j-x)转移过来，也可以选择取反再加，那么dp(i,j)从dp(i-1,j+x)+1转移过来，由于进行了取反操作，操作次数加一。

需要注意的是j+x，j-x需要判断是否越界;由于转移过程中要取min，要给dp数组赋初始值inf;并且对于(-4e4,4e4)的下标，由于数组下标只能取正数，需要把它们映射到(0,8e4)上，映射后的4e4对应原来的0。最后检查dp(n,4e4)是否为初始值(inf)判断能否使元素和为0。

using namespace std;
int dp[250][80050];
int main(){
    int n;
    cin>>n;
    memset(dp,0x3f,sizeof(dp));//初始值赋inf
    dp[0][40000]=0;//开始和为0，操作数为0
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        for(int j=0;j<=80000;j++){
            if(j-x>=0&&j-x<=80000)dp[i][j]=min(dp[i][j],dp[i-1][j-x]);
            if(j+x>=0&&j+x<=80000)dp[i][j]=min(dp[i][j],dp[i-1][j+x]+1);
        }
    }
    if(dp[n][40000]<n)cout<<dp[n][40000];//如果不为初始值，说明可能
    else cout<<-1;//否则不可能
}

F.插板法

两种元素分别有x,y个，问段数为分别为[1,x+y]的摆放方式分别有几种。

假设段数为i,由于只有两种元素，只能两种元素交叉排列，如果i为偶，两种元素段数都为i/2,如果i为奇，那么开头元素有i/2+1段，另一个有i/2段。两种元素都可能在第一个，那么总的方案数就是x在第一个的方案数+y在第一个的方案数。

假设x在第一个，那么问题就转化为了求把x分为(i/2+i%2)段，y分为i/2段的方案数，很显然由于被分的元素都是无区别的，这就是一个插板法：把m个无区别的东西分成k份，等价于在m-1个空里选k-1个进行插板，总方案数为C(m-1,k-1)。

接下来就简单了，但需要注意的是用到阶乘最好先预处理，用的时候直接查表，并且求阶乘时可能会爆int，最好直接define int ll；这种做法可能会出现需要分的段数比x,y还多的情况，不需要在主函数里进行特判，直接在C(m,k)里面对于k>m,k<0进行特判返回零就可以了。

using namespace std;
#define ll long long
const int mod=1e9+7;
const int N=1e3+10;
#define int ll
ll fac[N],ifac[N];
ll qpow(int a,int b){
    ll ret=1;
    while(b){
        if(b&1)ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
ll inv(int x){
    return qpow(x,mod-2);
}
void init(int x){
    fac[0]=1;
    for(int i=1;i<=x;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    ifac[x]=inv(fac[x]);
    for(int i=x-1;i>=0;i--){
        ifac[i]=ifac[i+1]*(i+1)%mod;
    }
}
ll C(int m,int k){
    if(m<0||k<0||k>m)return 0;
    return fac[m]*ifac[k]%mod*ifac[m-k]%mod;
}
signed  main(){
    int x,y;
    cin>>x>>y;
    init(1000);
    for(int i=1;i<=x+y;i++){
        int k1=i/2+i%2,k2=i/2;
        cout<<(C(x-1,k1-1)*C(y-1,k2-1)%mod+C(y-1,k1-1)*C(x-1,k2-1)%mod)%mod<<'\n';
    }
}