A

判断下切割偶数边后拼接的图形与原图是否相同即可.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int t;
LL n,m;
bool solve() {
    if(n % 2ll == 0ll) {
        if(2ll*m != n) return true;
    }
    if(m % 2ll == 0ll) {
        if(2ll*n != m) return true;
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n>>m;
        if(solve()) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

B

排序后双指针.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+10;
int t,n,a[N],b[N],num[N];
int ans;
void solve() {
    sort(a+1,a+n+1);
    int cnt=0;
    ans=0;
    for(int i=1;i<=n;i++) {
       if(a[i] != a[i-1]) b[++cnt]=a[i];
    }
    for(int l=1,r=1;r<=cnt;r++) {
        while(l < r && b[r] - b[l] >= n) l++;
        ans=max(ans,r-l+1);
    }
    cout<<ans<<"\n";
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        solve();
    }
    return 0;
}

C

推下式子可以发现，一个 $k$ 当且仅当 $ (2k-2)\vert(n-x) $ 或 $ (2k-2)\vert(n+x-2) $ 且 $ k > x-1 $ 时合法。所以我们直接枚举 $n-x$ 与 $n+x-2$ 的因数判断是否合法，注意要用set去重.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int t,x,n;
set<int> s;
void add(int p) {
    if(p & 1) return;
    p/=2; p++;
    if(p >= x) s.insert(p);
    return;
}
void solve() {
    int ans=0;
    for(int i=1;i*i<=n-x;i++) {
        if((n-x) % i == 0) {
            add(i); add((n-x)/i);
        }
    }
    for(int i=1;i*i<=n+x-2;i++) {
        if((n+x-2) % i == 0) {
            add(i); add((n+x-2)/i);
        }
    }
    ans=s.size();
    s.clear();
    cout<<ans<<"\n";
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n>>x;
        solve();
    }
    return 0;
}

D

设 $f(x,y)$ 表示将 $x$ 个人分到 $y$ 组可产生的贡献，那么在分为 $k$ 组时的总收益为 $ \sum_{i=1}^nb\ast f(c\lbrack i\rbrack,k)-(k-1)\ast x $.容易发现（？）这是单峰的，可以用三分求最大值.

至于 $ f(x,y) $，记 $t=\left\lfloor\frac xy\right\rfloor $ $,u=x \, mod\, y$，利用组合知识我们可以给出表达式 $f(x,y) = \frac{u*(t+1)*(x-t-1)+t*(x-t)*(y-u)} 2 $.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+10;
LL f(int x,int y) {
    LL t=x/y,u=x%y;
    LL xx=x,yy=y;
    return (u*(t+1ll)*(1ll*x-t-1ll)+t*(1ll*x-t)*(1ll*y-u))/2ll;
}
int t,n,b,x,c[N];
LL calc(int k) {
    if(k <= 1) return 0;
    LL ans=0;
    for(int i=1;i<=n;i++) ans+=1ll*b*f(c[i],k);
    ans-=(1ll*k-1ll)*x*1ll;
    return ans;
}
void solve() {
    int l=1,r=N,mid;
    LL ans=0;
    while(l <= r) {
        mid=(l+r)/2;
        if(calc(mid-1) <= calc(mid+1)) l=mid+1,ans=mid;
        else r=mid-1;       
        if(t < 0) cout<<"dg:"<<mid<<"\n";
    }
    cout<<max(max(calc(ans),calc(ans-1ll)),calc(ans+1ll))<<"\n";
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n>>b>>x;
        for(int i=1;i<=n;i++) cin>>c[i];
        solve();
    }
    return 0;
}

E

设 $x_0 = x \, mod \, y$，最后所填数的总和一定会表现为 $s = nx_0 + ky$ 的形式.于是我们便可以将问题变为构造一个长度为 $n$ 的序列使其满足 $a_1 = \left\lfloor\frac xy\right\rfloor ,a_{i+1} = 0 \; or \; a_{i+1} =a_i + 1$ 且 $\frac{s-n\ast x_0}y = \sum_{i=1}^na_i $.

考虑dp，设 $f_i$ 为数列和为 $i$ 时的最短方案长度，则转移方程如下：

$ f_i=f_{i-\sum_{k=0}^jk}+j+1 $

$j$ 是 $\sqrt n $ 级别的，$k$的和式可以$O(1)$ 求解，总复杂度$O(n\sqrt n)$.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+10;
int t,n,x,y,s;
LL dp[N];
void solve() {
    for(int i=1;i<=s;i++) dp[i]=1e9;

    for(int i=1;i<=s;i++) {
        for(int j=0,sum=0;j<=s;j++) {
            sum+=j;
            if(sum > i) break;
            if(dp[i-sum] + j + 1 < dp[i]) { 
                dp[i] = dp[i-sum] + j + 1;
            }
        }
    } 
    int sum=0;

    for(int i=1;i<=n;i++) {
        sum+=(x/y)+i-1;
        if(sum > s) break;
        if(dp[s-sum] + i <= n) {
            cout<<"Yes\n";
            for(int j=1;j<=i;j++) cout<<x+(j-1)*y<<" ";
            for(int p=s-sum;p;) {
                int val=0;
                for(int j=0;j<=p;j++) {
                    val+=j;
                    if(val > p) break;
                    if(dp[p] == dp[p-val]+j+1){
                        for(int k=0;k<=j;k++) cout<<x%y+k*y<<" ";
                        p-=val;
                        break;
                    }
                }
            }
            for(int j=1;j <= n-i-dp[s-sum];j++) cout<<x % y<<" ";
            cout<<"\n";
            return;
        } 
    }
    cout<<"No\n";
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n>>x>>y>>s;
        if((LL)n*(x%y) > (LL)s) {
            cout<<"No\n";
            continue;
        }
        s-=n*(x%y);
        if(s % y) {
            cout<<"No\n";
            continue;
        }
        s/=y;
        if(x/y > s) {
            cout<<"No\n";
            continue;
        }
        solve();
    }
    return 0;
}

F

唉数据结构

数学+线段树维护，等最近把手里的事做完再专门练练数据结构吧.