A. Trape

算法1

枚举每个点，这个点可能被某个梯形包含，再枚举这个梯形，判断他包含的点。 时间复杂度$O(M*50*(25+75)/2)$

#include<bits/stdc++.h>
using namespace std;
bool st;
const int N=6e3,K=2.6e3;
int n,m;
short int sum[N][N],ans;
bool ed;
signed main(){
    freopen("trape.in","r",stdin);
    freopen("trape.out","w",stdout);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        x+=K;
        y+=K;
        for(int i=y-50;i<=y;i++){
            int dx=(y-i+1)>>1;
            for(int j=x-75;j<=x;j++){
                if(j+dx<=x&&j+75-dx>=x){
                    sum[i][j]++;
                    ans=max(ans,sum[i][j]);
                }
            }
        }
    }
    //cerr<<(&st-&ed)/1024/1024<<" MB\n";
    cout<<ans;
    return 0;
}

我们可以枚举下底边

就像这样，我们可以使左边界和右边界不断右移（相当于一个滑块），计算出每次移动后梯形内部点数，显然可以用单调队列做到O（M^2）

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXM=10011;
int N, M;
struct Point{
    int x, y;
    int lsum, rsum;
} P[MAXM];
int lsR[MAXM], rsR[MAXM];
int cmpls(int a, int b){
    return P[a].lsum<P[b].lsum;
}
int cmprs(int a, int b){
    return P[a].rsum<P[b].rsum;
}
int Y, LS, RS;
int Ans, ANS;
int main(){
        freopen("trape.in","r",stdin); 
    freopen("trape.out","w",stdout); 
    ios_base::sync_with_stdio(false);

    cin >> N >> M;

    for(int i=1;i<=M;++i){
        cin >> P[i].x >> P[i].y;
        P[i].lsum=2*P[i].x-P[i].y;
        P[i].rsum=2*P[i].x+P[i].y;
    }

    for(int i=1;i<=M;++i){
        lsR[i]=i;rsR[i]=i;
    }

    sort(lsR+1, lsR+M+1, cmpls);
    sort(rsR+1, rsR+M+1, cmprs);

    for(int Y=-N, l, r;Y<=N;++Y){
        l=0;r=0;Ans=0;
        for(int j=1;j<=M;++j){
            LS=P[lsR[j]].lsum;
            RS=LS+(Y+75)*2;
            while(r<M && P[rsR[r+1]].rsum<=RS){
                ++r;
                if(Y<=P[rsR[r]].y && P[rsR[r]].y<=Y+50)    ++Ans;
            }
            while(l<M && P[lsR[l+1]].lsum<LS){
                ++l;
                if(Y<=P[lsR[l]].y && P[lsR[l]].y<=Y+50)    --Ans;
            }
            ANS=max(Ans, ANS);
        }
    }

    cout << ANS << endl;

    return 0;
}

B Candies

算法1 (10%)

思路： 暴力模拟
复杂度： $O(NK)$
描述： 按照题意直接模拟每次操作的过程。

算法2 (30%)

思路： 使用STL set优化
复杂度： $O(K\log N)$
描述： 在算法1的基础上，使用set来维护最大值和最小值，将查找操作优化到对数级别。

算法3（100%）

从小到大培训，到左边找到一个位置推平次数小于等于k的位置l，找到右侧对于的位置R

//peiyinsong代码
#include<bits/stdc++.h>
#define int long long
const int M=1e5+5;
using namespace std;
int n,k,sum[M],mus[M],a[M],l,r,T;
void solve(){
    cin>>n>>k;
    sum[0]=mus[n+1]=0;
    l=1,r=n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    for(int i=n;i>=1;i--)mus[i]=mus[i+1]+a[i];
    if(k>=sum[n]){
        if(sum[n]%n==0)cout<<"0";
        else cout<<"1";
    }else{
        for(int i=1;i<=n;i++)if(i*a[i]-sum[i]<=k)l=i;
        for(int i=n;i>=1;i--)if(mus[i]-((n-i+1)*a[i])<=k)r=i;
        if(l+1>=r){
            if(sum[n]%n==0)cout<<"0";
            else cout<<"1";
        }else {
            int cr=k-(mus[r]-((n-r+1)*a[r])),cl=k-(l*a[l]-sum[l]);
            cr/=(n-r+1);
            cl/=l;
            a[r]-=cr,a[l]+=cl;
            cout<<a[r]-a[l];
        }
    }
}
signed main(){
    //freopen("candies.in","r",stdin);
    //freopen("candies.out","w",stdout);
    cin>>T;
    while(T--)solve(),putchar('\n');
    return 0;
}

算法4 (100%)

思路： 二分查找 + 数学分析
描述： - 当 $K$ 很大时，糖果数会趋近相同（最多相差0或1） - 先将 $a_i$ 排序，分别二分找出： - $L$: 糖果数小于等于 $L$ 的堆能通过 $K$ 次操作变为相同 - $R$: 糖果数大于等于 $R$ 的堆能通过 $K$ 次操作变为相同 - 判断： - 如果 $L \geq R$，则检查 $N$ 是否能整除总糖果数，能则输出0，否则输出1 - 如果 $L < R$，则答案为 $R - L$

  #include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=110000;
int n, a[MAXN];
ll m, s[MAXN];
inline ll read()
{
    ll x=0; char ch=0;
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return x;
}
bool check1(int k)
{
    int p=lower_bound(a+1, a+n+1, k)-a-1;
    return 1ll*p*k-s[p]<=m;
}
bool check2(int k)
{
    int p=upper_bound(a+1, a+n+1, k)-a;
    return s[n]-s[p-1]-1ll*(n-p+1)*k<=m;
}
int main()
{
    freopen("candies.in", "r", stdin);
    freopen("candies.out", "w", stdout);
    int T=read();
    while (T--)
    {
        n=read(); m=read();
        for (int i=1; i<=n; i++) a[i]=read();
        sort(a+1, a+n+1);
        for (int i=1; i<=n; i++) s[i]=s[i-1]+a[i];
        int l1=1, r1=1E9;
        while (l1<r1)
        {
            int mid=l1+r1+1>>1;
            if (check1(mid)) l1=mid;
            else r1=mid-1;
        }
        int l2=1, r2=1E9;
        while (l2<r2)
        {
            int mid=l2+r2>>1;
            if (check2(mid)) r2=mid;
            else l2=mid+1;
        }
        if (l1>=l2) puts(s[n]%n==0?"0":"1");
        else printf("%d\n", l2-l1);
    }
    return 0;
}

C. Game

算法1 (30%/70%)

思路： 枚举 + 暴力模拟
复杂度： $O(nX)$，其中 $X$ 为坐标范围
描述： - 设初始位置在 $x_1$ 的人属于Alice - 枚举Alice的 $n$ 种移动选择 - 每次暴力模拟移动所有人的位置 - 操作后与最终位置重合的人属于Alice，其余属于Bob - 检查Bob的唯一选择是否可行

算法2 (100%)

思路： Bitset优化
复杂度： $O(\frac{nX}{64})$
描述： 使用Bitset来维护每个位置是否有人，大幅提升模拟效率。

#include <cstdio>
#include <bitset>
using namespace std;
const int MAXN=77000;
const int MAXM=110000;
const int M=(1e5/32+1)*32;
bitset<MAXM> A, B, C, A2, B2;
int a[MAXN], b[MAXN];
inline void shift(bitset<MAXM>& b, int k)
{
    if (k>=0) b<<=k; else b>>=-k;
}
int main()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    for (int i=1; i<=n; i++) scanf("%d", &b[i]);
    for (int i=1; i<=n; i++) A.set(a[i]);
    for (int i=1; i<=n; i++) B.set(b[i]);
    int dx, dy;
    for (int i=1; i<=n; i++)
    {
        dx=b[i]-a[1];
        C=A; shift(C, dx); C&=B;
        B2=B; B2^=C; shift(C, -dx);
        A2=A; A2^=C;
        dy=B2._Find_first()-A2._Find_first();
        shift(A2, dy);
        if(A2==B2) break;
    }
    printf("%d %d\n", dx, dy);
    return 0;
}

D.Rcomb

Rcomb

算法1

先考虑 $80$ 分的部分分。设 $f(n, i)$ 表示还剩 $n$ 张试卷，第 $i$ 张试卷的期望贡献次数。

那么有转移

$$ \begin{aligned} & f(n, 1) = \frac 1 {n-1} + f(n-1,1) \\ & f(n, n) = \frac 1 {n-1} + f(n - 1, n - 1) \\ & f(n, i) = \frac 2 {n-1} + \frac{i-1}{n-1} f(n-1,i-1) + \frac{n-i}{n-1} f(n-1,i) \end{aligned} $$

这个复杂度是平方的，能通过 $80$ 分。

对于这个部分分，还有一种思考方向，是设 $f(i, j)$ 表示合并完 $[i, j]$ 区间的期望代价。那么 $$f(i, j) = \sum\limits_{k=i}^j a_k + \frac{1}{j-i} \sum\limits_{k=i}^{j-1} f(i, k) + f(k + 1, j)$$

利用前缀和优化，也可以做到平方。

对于 $100$ 分的数据，考虑拆贡献。每个数到答案的贡献，是上面这个式子转移中的第一个 $\sum$。我们需要知道每个数被包含在了长度为多少的区间。

第 $k$ 个数对答案的贡献，可以考虑它往左边合并的概率。当左边有 $k - 1$ 个数时，有 $k - 1$ 种合并的可能，合并到它的概率是 $\dfrac 1 {k-1}$。右边同理，合并到它的概率是 $\dfrac 1 {n-k}$。当左右操作了一轮后，合并到它的概率增加到 $\dfrac 1 {k-2}$。我们对这个求和，就可以了。

最终的复杂度是 $O(n)$。

算法2

实际上有更优的 $O(n)$ 复杂度算法。通过找规律推式子可以得到结论。具体见标程。

/*
    任务1 枚举所有合并的顺序
    任务2 区间dp n^3
    任务3 区间dp优化 n^2 

    子任务4 
    合并的作用是独立的，可以分开计算期望 
    f[i]为i和左右两侧的数合并产生的贡献。i=1的时候只能和右侧合并 
    随着合并个数i的减少，每次合并到他的概率是1/(i-1) 

*/ 
#include <iostream>
#include <iomanip>
using namespace std;
const int MAXN=5e5+9;
int N;
double Num[MAXN];
double v=0.0;
double ans=0.0;
int main(){
    freopen("rcomb.in","r",stdin); 
    freopen("rcomb.out","w",stdout); 
    cin >> N;
    for(int i=1;i<=N;++i)
        cin >> Num[i];
    for(int i=1;i<N;++i)
        v+=1.0/(double)(i);
    ans=Num[1]*v;

    for(int i=2, l=1, r=N-1;i<=N;++i, ++l, --r){//和左右两侧和并的概率。 
        v-=1.0/(double)(r);
        v+=1.0/(double)(l);
        ans+=Num[i]*v;
    }
    cout << fixed << setprecision(3) << ans << endl;
    return 0;
}

rcomb

game

考虑一个暴力。不妨令 $x_1$ 属于 $A$，我们枚举它和哪个 $y$ 对应，就知道 $A$ 的命令。然后去掉所有可以满足 $A$ 命令的人，看看剩下的人是不是合法。这个可以做到 $O(nV)$。

然后利用 bitset 压位优化。复杂度 $O(\dfrac {nV} w)$

p.s. 这玩意儿假了