有一些题目的文字题解仍在施工中，先放出部分题的文字题解与参考代码。

赛前难度预测：

签到题: F M B

简单题: G C

中等题: A I

较难题:D H K E

难题: J L

F

简要题意：

给定 个字符串，判断第 个字符串是否是以 Mc 为前缀。大小写敏感。

题解：

签到题，用读入字符串直接判断并累加即可。

时间复杂度 。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1919810,mod=998244353;
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
int a[N],b[N];
char s[N];

void __(){
    cin>>n;
    string s;
    int ans=0;
    for(int i=1;i<=n;i++){
        cin>>s;
        if(s.substr(0,2)=="Mc") ans++;
    }
    cout<<ans<<"\n";
}


int main(){
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}

M

简要题意：

给定若干个时间段，问最早的没被任何时间段覆盖的时间点是多少。

题解：

将一个二维时间 映射到一维时间，可以令 ，那么所有的日期都被映射到了 中，直接使用差分来维护哪些段被覆盖，最后做一个前缀和，即可找到哪些位置没被任何线段覆盖。最后，遍历所有日期，找出最早的未被覆盖的时间点即可。

如果暴力遍历所有被覆盖的日期，在本题的数据范围下也可通过。

时间复杂度为 或 。

参考代码1（暴力）：

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef array<ll,3> a3;
const ll inf=1e18;
ll n,m,k,M,D;
ll l,r;
ll a[N],b[N];
string s[N];
ll seed=1e9+7;
ll d[N][2];
bool tf[N][2];


int cal(int x,int y){
    x--,y--;
    return x*D+y+1;
}

void __(){
    cin>>n>>M>>D;
    assert(M<=100);
    assert(D<=100);
    for(int i=1;i<=n;i++){
        int x,y,xx,yy;
        cin>>x>>y>>xx>>yy;
        assert(x<=M);assert(xx<=M);
        assert(y<=D); assert(yy<=D);
        
        int u=cal(x,y),v=cal(xx,yy);
        assert(u<=v);
        for(int j=u;j<=v;j++) a[j]++;
    }
    int res=cal(M,D);
    for(int i=1;i<=res;i++){
        if(a[i]==0){
            int t=i-1;
            cout<<t/D+1<<" "<<t%D+1<<endl;
            return;
        }
    }
    cout<<"Online\n";
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    // cin>>_;

    while(_--){
        __();
    }
}

参考代码2（差分，前缀和）：

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef array<ll,3> a3;
const ll inf=1e18;
ll n,m,k,M,D;
ll l,r;
ll a[N],b[N];
string s[N];
ll seed=1e9+7;
ll d[N][2];
bool tf[N][2];


int cal(int x,int y){
    x--,y--;
    return x*D+y+1;
}

void __(){
    cin>>n>>M>>D;
    assert(M<=1000);
    assert(D<=1000);
    for(int i=1;i<=n;i++){
        int x,y,xx,yy;
        cin>>x>>y>>xx>>yy;
        assert(x<=M);assert(xx<=M);
        assert(y<=D); assert(yy<=D);
        
        int u=cal(x,y),v=cal(xx,yy);
        assert(u<=v);
        a[u]++,a[v+1]--;
    }
    for(int i=1;i<N;i++) a[i]+=a[i-1];
    int res=cal(M,D);
    for(int i=1;i<=res;i++){
        if(a[i]==0){
            int t=i-1;
            cout<<t/D+1<<" "<<t%D+1<<endl;
            return;
        }
    }
    cout<<"Online\n";
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    // cin>>_;

    while(_--){
        __();
    }
}

B

简要题意：

给定一颗完全二叉树，求给定的序列能否是层序遍历的结点访问顺序。

题解：

由于该算法每次选取的是深度最小的结点，所以就是一个同深度结点随机选择的层序遍历，如果给定序列从左到右的结点深度单调不减，则输出YES,否则输出NO。

也可以模拟该算法的操作，使用 set 存储当前有哪些点，并且依次判断每个点能否取出。

时间复杂度 。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
typedef pair<ll,ll> PII;
ll k,vv,n,m;
int a[N];

int dep[N];
void __(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int now=0;
    for(int i=1;i<=n;i++){
        if(dep[a[i]]<now){
            puts("NO");
            return;
        }
        now=dep[a[i]];
    }
    puts("YES");
}


int main(){
    for(int i=1;i<N;i++) dep[i]=dep[i/2]+1;
    int _=1;
    cin>>_;
    while(_--){
        __();
    }
}

G

简要题意：

给定一个数组 ，可以修改任何一个位置的数，问最终数组有多少可能性，使得所有长度至少为 的区间的二进制或值与原来相同。

题解：

当修改第 个位置的数时，只有包含 的区间或值可能被改变。我们首先要使得所有包含 位置的长度为 的区间或值与原来相同。根据或运算的结合律，如果所有长度为 的区间或值不变，那么所有包含 的区间或值一定不变。因此，我们只需要使得 与其相邻的数或值不变即可。

假设当前的数为 ，与 相邻的数为 ,我们对于修改后的数 二进制下每一位的情况分类讨论：

假设 的这一位为 ，那么 这一位必须填 ；

假设 的这一位为 ，且 的这一位为 ，那么 这一位必须填 ；

假设 的这一位为 ，且 的这一位为 ，那么 这一位可以填 也可以填 ,记为 ?；

记 为 所有数位中 ? 的个数， 位置的方案数为 。由于规定了 ，因此需要将上述方案数减去 。

将所有位置可以被修改的方案数相加，即为答案。

时间复杂度 。

参考代码:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef std::pair<int,int> PII;
const int N=1919810;

int _;
ll n,k;

ll a[N],b[N],c[N],d[N];
ll dp[N];

ll mi[N];

int wei[35];


void gao(int x,int y){
    for(int i=0;i<k;i++){
        int u=(x>>i)&1;
        int v=(y>>i)&1;
        if(v==0) wei[i]=0;
        if(v==1){
            if(u==0) wei[i]=1;
        }
    }
}

void __(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    ll ans=0;
    for(int i=1;i<=n;i++){
        memset(wei,-1,sizeof wei);
        for(int j=0;j<k;j++) b[j]=(a[i]>>j)&1;
        if(i!=1) gao(a[i-1],a[i-1]|a[i]);
        if(i!=n) gao(a[i+1],a[i+1]|a[i]);
        int cnt=0;
        for(int j=0;j<k;j++) if(wei[j]==-1) cnt++;
        
        ans+=mi[cnt]-1;
    }
    cout<<ans<<"\n";
}

int main(){
    mi[0]=1;
    for(int i=1;i<=30;i++) mi[i]=mi[i-1]*2;
    int _;
    cin>>_;
    while(_--){
        __();
    }
}

C

简要题意：

给定两个长度为 的数组 ，每次操作可以选择 中的若干个位置，并在模 意义下加一或者减一，问多少次操作后可以使得 变成 。

题解1：

首先有一个观察是，如果同时对第 个舞台使用一操作和二操作，答案一定不会变得更优。因此我们可以将所有数分成两类，一类只使用一操作，一类只使用二操作。

我们计算出对每个 只使用一操作变为 的步数 得到一个新数组，我们的目标就是将 中的数全部变为 。

将 从小到大排序，我们可以依次枚举相邻的两个数 和 ，将 ~ 的所有数通过 操作变成 ，将 ~ 的所有数通过 操作变成 ，那么花费为 ，枚举所有可能的位置取最小值即可。

注意可能所有的数都通过 或者 达到 。

时间复杂度 。

参考代码（by StarSilk):

#include<bits/stdc++.h>
using namespace std;
long long a[200002],b[200000],inf=1000000000000000000LL;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,n,m,i;
	long long ans;
	for(cin>>T;T>0;T--)
	{
		cin>>n>>m;
		for(i=1;i<=n;i++)cin>>a[i];
		for(i=1;i<=n;i++)cin>>b[i];
		for(i=1;i<=n;i++)a[i]=(a[i]+m-b[i])%m;
		a[0]=0;
		a[n+1]=m;
		sort(a+1,a+n+1);
		ans=inf;
		for(i=0;i<=n;i++)ans=min(ans,m-a[i+1]+a[i]);
		cout<<ans<<'\n';
	}
	return 0;
}

题解2：

我们对于每个舞台计算一个pair ,并按照第一关键字排序。可以发现，如果对第 个舞台不断使用一操作，那么对于所有的 舞台全部使用一操作，答案一定不会变劣。

因此我们预处理一个第二关键字的后缀max，在枚举 的同时计算 与 的后缀max之和，最后统计最小值即可。

时间复杂度 。

参考代码2:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
#define int long long
typedef pair<ll,ll> PII;

ll q,n,m,k;

int a[N],b[N];
vector<int> e[N];

ll ans;
PII res[N];
ll mx[N];
void __(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	ans=1e18;
	for(int i=1;i<=n;i++){
		res[i].first=(b[i]-a[i]+m)%m;
		res[i].second=m-res[i].first;
	}
	sort(res+1,res+1+n);
	mx[n+1]=0;
	for(int i=n;i>=0;i--) mx[i]=max(mx[i+1],res[i].second);
	for(int i=0;i<=n;i++) ans=min(ans,res[i].first+mx[i+1]);
	cout<<ans<<"\n";
}



signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        __();
    }

}

I

简要题意：

定义一个字符的代价为单个字符在字符串中的最远距离，字符串的代价为所有在字符串中出现过的字符的代价之和。 现在给定一个包含?与前个小写字母的字符串，要求你把每个?全部替换为前个小写字母中的一种，问最小的代价，并输出构造方案。

题解：

我们用贡献的角度来分析这个问题。

首先，我们可以先找出每种字符最左边出现的位置 和最右边出现的位置 ，并将 中所有的问号替换为对应字符。这个操作一定不会增加对答案的贡献。

此时，整个字符串被分为了若干个字符和问号交替的段。如果将问号替换为一个未出现过的字符，则会对答案增加 的贡献，否则则会至少增加 的贡献。因此，我们可以先尽可能将问号替换为未出现的字符。

当所有字符都在字符串中出现后，无论我们如何替换字符，都至少会增加 的贡献。我们考虑对每个字母段不断向外扩展：对于所有与字母相邻的 ? ，我们将这个 ? 替换为与之相邻的字母，这样就能保证每次替换?都恰好增加 的贡献。由于在之前的过程中，字符串中至少有一个字符，因此上述构造过程是可行的，并且能够达到答案的下界。

在实现时，可以先顺着遍历一遍字符串，并用一个变量now记录沿边界扩展的字符。如果当前字符不为?，则将now替换为当前的字符，否则则将当前的?替换为now。由于可能出现以?开头的情况，因此在顺着做完一遍之后还要倒着做一遍。

时间复杂度 。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
typedef pair<ll,ll> PII;
ll k,vv,n,m;
int a[N];

int dep[N];
int l[30],r[30];
bool tf[30];
void __(){
    cin>>n>>m;
    string s;
    cin>>s;
    // cout<<s.size()<<endl;
    memset(tf,false,sizeof tf);
    memset(l,0x3f,sizeof l);
    memset(r,-0x3f,sizeof r);
    for(int i=0;i<s.size();i++){
        if(s[i]=='?') continue;
        int t=s[i]-'a';
        tf[t]=1;
        l[t]=min(l[t],i);
        r[t]=max(r[t],i);
    }
    int ans=0;
    for(int i=0;i<m;i++){
        if(l[i]>r[i]) continue;
        ans+=r[i]-l[i];
        for(int j=l[i];j<=r[i];j++){
            if(s[j]=='?'){
                char ch='a'+i;
                s[j]=ch;
            }
        }
        
    }
    int idx=0;
    for(int i=0;i<s.size();i++){
        if(s[i]!='?') continue;
        while(idx<m&&tf[idx]) idx++;
        if(idx>=m) break;
        char ch='a'+idx;
        tf[idx]=1;
        s[i]=ch;
    }
    char now='?';
    for(int i=0;i<s.size();i++){
        if(s[i]=='?'){
            s[i]=now;
            if(now!='?') ans++;
        }else{
            now=s[i];
        }
    }
    now='?';
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]=='?'){
            s[i]=now;
            if(now!='?')  ans++;
        }else{
            now=s[i];
        }
    }
    cout<<ans<<"\n";
    cout<<s<<"\n";
}


int main(){
    int _=1;
    cin>>_;
    while(_--){
        __();
    }
}

A

简要题意：

给定一棵树，初始在 号节点，每个点有点权，每条边有边权。经过一条边时会消耗与边权相等的体力，每条边可以经过无数次。每次到达一个点时，会回复与点权相等的体力。对于除 外的每个点，求出能够走到这个点最少需要的初始体力。

题解：

对于每个点，一共有两种策略：一种是直接沿着 号节点到该节点的路径直接行走，另一种是走到一个其它分支，在一条边上反复横跳把体力蹭到无限。我们可以考虑预处理出所有点的答案，然后对某些 “走到了就可以蹭到无限的点” 进行标记。在输出 点的答案时，我们直接输出当前点与所有特殊点答案的最小值即可。

我们首先考虑如何找出所有特殊点。对于一条边 ,一个显然需要满足的条件是 。如果一个点 满足 ，那么走到点后，一定能够有足够的体力在这条边上反复横跳，从而获得无穷的体力。否则则需要在这条边上多走一步，在该过程中仍有可能花费更多的体力。因此，我们先找出所有满足 的边，并分别判断 是否大于 。如果是，则对应点就是要找的特殊点。

您可能会担心：需不需要考虑在一条较长的路径上反复横跳的情况？

这是不需要的。一条路径的体力变化过程能够拆成若干条边的体力变化过程的叠加，一条能够反复横跳的路径必然包含一条能够反复横跳的边。因此考虑了所有特殊边之后，就相当于考虑了所有能够反复横跳的路径的情况。

接下来的问题是如何预处理出所有点的答案。考虑将体力的变化过程看成一条折线，那么经过一条边时折线将会向下，而到达一个新的节点时折线将会向上。在移动的过程中我们要保证折线的最低点不小于 。

我们记录两个变量 ,其中 表示走到 点所需要的最小体力， 表示当初始体力为 时，走到 点还剩下多少体力。在折线图中， 为左端点的高度， 为右端点的高度。

假设 之间的边权为 ,我们思考如何用 的信息递推出 的信息。在从 出发向 的移动过程中，折线会先向下移动 ；到达 时,折线会向上移动 。如下图所示：

我们只需要根据向下移动 后折线的最低点是否低于 进行分类讨论。如果这个最低点不低于 ，那么就不用对折线做任何动作（如上图所示）；否则，则需要将整个折线向上平移，直到最低点不低于 为止。如下图所示：

由此，我们可以写出最终的递推式：

有了上述递推式与判定条件之后，我们只需要对整棵树进行一遍 即可统计出所有答案。

当然，本题也存在一些诸如最短路的其它做法，在此处不再赘述。

时间复杂度 。

参考代码1：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=3e5+10;
int n,q;
ll a[N];
vector<PII> e[N];
ll dp[N],leave[N];
bool tf[N];


void dfs(int x,int fa){
	for(auto [j,w]:e[x]){
		if(j==fa) continue;
		dp[j]=dp[x];
		ll nw=leave[x]-w;
		ll need=max(0ll,-nw);
		dp[j]+=need;
		nw=max(0ll,nw);
		leave[j]=nw+a[j];
		dfs(j,x);
	}
}

void __(){
	cin>>n;
	for(int i=2;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++) e[i].clear(),tf[i]=0;
	dp[1]=0,leave[1]=0;
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[u].push_back({v,w});
		e[v].push_back({u,w});
		if(w*2<a[u]+a[v]){
			if(a[u]>w) tf[u]=1;
			if(a[v]>w) tf[v]=1;
		}
	}
	dfs(1,-1);
	ll mn=1e18;
	for(int i=1;i<=n;i++){
		if(tf[i]) mn=min(mn,dp[i]);
	}
	for(int i=2;i<=n;i++) printf("%lld ",min(mn,dp[i]));
	printf("\n");
}

int main() {
	int _;
	cin>>_;
	while(_--){
		__();
	}
}

参考代码2 (最短路，Sakuya_maid)

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ULL;
using LL = long long;

mt19937_64 rd(time(0));
constexpr int N = 3e5 + 5, mod = 998244353;
constexpr double eps = 1e-8;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define fi first
#define se second
#define int long long
#define lowbit(x) (x & (-x))
#define PII pair<int, int>
#define mid ((l + r) >> 1)

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int ksm(int a, int b){
    a %= mod;
    int res = 1;
    while(b){
        if(b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int n, m;
int a[N];
void Sakuya()
{
    cin >> n;

    for(int i = 2; i <= n; ++ i)cin >> a[i];

    vector g(n + 1, vector<PII>());

    for(int i = 1; i <= n - 1; ++ i){
        int u, v, w;cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    vector<bool>vis(n + 1);
    vector<int>dp(n + 1);

    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>q;

    q.emplace(0, 0, 1);
    
    int flag = 1e18;

    while(q.size()){
        auto [dis, has, u] = q.top();
        q.pop();

        if(dis == flag){
            break;
        }

        if(vis[u])continue;
        vis[u] = true;
        dp[u] = dis;

        for(auto [v, w] : g[u]){
            if(vis[v])continue;
            auto now = has + w;
            
            if(now <= 0){
                q.emplace(dis, now - a[v], v);

                if(a[u] + a[v] > 2 * w){
                    flag = min(flag, dis);
                }
            }else {
                q.emplace(dis + now, -a[v], v);

                if(a[u] + a[v] > 2 * w){
                    flag = min(flag, dis + now);
                }
            }

            
        }
    }

    for(int i = 2; i <= n; ++ i){
        if(!vis[i]){
            dp[i] = flag;
        }
        cout << dp[i] << " ";
    }
    cout << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    for (cin >> T; T -- ; )
        Sakuya();

}

D

简要题意：

一维坐标上有若干条线段，现在需要放置两条长度为 的线段，使得与它们中至少一条相交的线段数量最多。

题解：

考虑将所有其他线段的右端点向右延长 ，即从 变为 ，那么题目转化为了放两个点，使得使得与它们中至少一条相交的线段数量最多。

将所有线段的左端点和右端点取出，称为关键点，将所有关键点排序。

从左到右枚举每个关键点，将第一个点放置在这个关键点上，并且动态维护不覆盖到该点的线段。使用区间加，区间求最值的线段树可以求出另一个点放置后能得到的最大贡献。由于是从小到大枚举关键点，所以每条线段最多被删除一次和加入一次。

由于该题线段值域为 ，那么需要用动态开点线段树,或者可以通过对所有关键点离散化后再建线段树即可用普通的懒标记线段树完成。

时间复杂度

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+10;
typedef long long ll;
typedef pair<ll,ll> PII;

ll p,q,n,m,k;

int a[N];
int l[N],r[N];



typedef struct{
    int l,r;
    int mx;
    int tag;
}Node;

Node tr[N<<2];


void pushup(int u){
    tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}

void pushdown(int u){
    if(tr[u].tag){
        tr[u<<1].mx+=tr[u].tag;
        tr[u<<1].tag+=tr[u].tag;
        tr[u<<1|1].mx+=tr[u].tag;
        tr[u<<1|1].tag+=tr[u].tag;
        tr[u].tag=0;
    }
}

void build(int u,int l,int r){
    tr[u]={l,r};
    if(l==r){
        tr[u].mx=0;
    }else{
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].mx++;
        tr[u].tag++;
    }else{
        int mid=tr[u].l+tr[u].r>>1;
        pushdown(u);
        if(l<=mid) modify(u<<1,l,r);
        if(r>mid) modify(u<<1|1,l,r);
        pushup(u);
    }
}

void __(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
        r[i]+=k;
	}
    vector<ll> segs;
    for(int i=1;i<=n;i++){
        segs.push_back(l[i]);
        segs.push_back(r[i]);
    }
    sort(segs.begin(),segs.end());
    segs.erase(unique(segs.begin(),segs.end()),segs.end());
    build(1,1,segs.size());
    vector<PII> v;
    for(int i=1;i<=n;i++) v.push_back({l[i],r[i]});
    sort(v.begin(),v.end());
    priority_queue<PII,vector<PII>,greater<PII> > q;
    int ans=0;
    for(auto [l,r]:v){
        while(q.size()&&q.top().first<l){
            PII ttt=q.top();
            q.pop();
            int ri=lower_bound(segs.begin(),segs.end(),ttt.first)-segs.begin()+1;
            int le=lower_bound(segs.begin(),segs.end(),ttt.second)-segs.begin()+1;
            modify(1,le,ri);
        }
        q.push({r,l});
        int sz=q.size();
        // cout<<l<<" "<<r<<endl;
        // cout<<sz<<" "<<tr[1].mx<<endl;
        ans=max(ans,tr[1].mx+sz);
    }
    printf("%d\n",ans);
    
}

//32 16

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        __();
    }

}

H

简要题意：

有 种鼠鼠，第 种鼠鼠的数量为 ,购买这种鼠鼠能够获得 的利润。现在要将每只鼠鼠都装到笼子里，一个笼子的成本为 元，最多容纳 只鼠鼠。同一个笼子中，第 种鼠鼠的数量不能超过 ,求最大能够获得的净利润。

题解：

首先思考一个问题：当确定购买了哪些品种的鼠鼠，我们至少需要多少个笼子？

一个明显的下界是 ，其中 的含义是选中的鼠鼠的总数。接下来，我们以构造的方式证明该下界可以取到。

考虑一个格点，其高度为 ,宽度为笼子的总数 。我们对每个品种的鼠鼠依次进行放置，并按照从下至上，从左至右的顺序放置。每次放置一只新的鼠鼠时，我们找出最下面存在空格子的一行，将鼠鼠放置到该行最左侧的空格子中，具体效果如下图所示（不同的颜色代表不同种类的鼠鼠）：

按照此种放置方式，一个合法的 需要满足以下两个条件：

1. 格点的总数能够容纳所有的鼠鼠
2. 对于每一列，第 个品种的鼠鼠连续高度不能超过 。

当 时，由于 ,显然能够满足第一个条件；

对于第二个条件，只需要满足 即可。由于,因此第二个条件也能满足。

由此，我们证明了最少需要的笼子数量为 。

有了这个条件之后，我们可以把每种鼠鼠按照 排序，并按这个顺序将鼠鼠加入一个 背包。设 表示当鼠鼠的总数为 时，利润之和的最大值。每次加入一个鼠鼠的时候，就可以以 为体积， 为价值，按照 背包的转移方式进行转移。当加入一个鼠鼠之后，当前的 最大值就确定为 了。我们可以在每次加入鼠鼠后遍历每个状态。当鼠鼠的总数为 时，所需要的笼子个数就为 ,我们根据净利润的计算公式计算出净利润为 ，统计最小值即可。

由于背包的体积最大为 ，因此总时间复杂度为。

参考代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef std::pair<int,int> PII;
const int N=1e6+10;

int _;
ll n,x,d;

ll a[N],c[N],w[N];
ll dp[N];

void __(){
    
    cin>>n>>x>>d;
    for(int i=1;i<=n*5000;i++) dp[i]=-1e18;
    dp[0]=0;
    int tot=0;
    vector<array<ll,3>> ar; 
    // ar.push_back({0ll,0ll,0ll});
    // ar.resize(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>w[i];
    // for(int i=1;i<=n;i++) tot+=a[i];
    for(int i=1;i<=n;i++){
        array<ll,3> res;
        res[0]=(a[i]+c[i]-1)/c[i];
        res[1]=a[i];
        res[2]=w[i];
        ar.push_back(res);
    } 
    sort(ar.begin(),ar.end());
    ll ans=0;
    for(auto &[mx,v,w]:ar){
        tot+=v;
        for(int i=tot;i>=v;i--){
            dp[i]=max(dp[i],dp[i-v]+w);
            ll cages=max(mx,(i+x-1)/x);
            ll val=dp[i]-cages*d;
            ans=max(ans,val);
        }
    }
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--){
        __();
    }
}

K

首先，本题可能由于卡常，给各位选手带来了不好的体验。负责人在此对被卡常的选手致以诚挚的歉意。

简要题意：

给定 个点，求出这 个点能够构成的本质不同的恰好含有一个直角内角的筝形的数量。

题解：

首先介绍一个十分无脑的做法：

首先枚举直角顶点 A ，以 A为原点建立平面直角坐标系。再枚举一个点B,计算AB作为直角边的情况。

我们将AB沿A逆时针旋转90°,得到另一条直角边AC。如果C点存在于给定的点集内，则继续执行如下步骤：

计算出 BC 的中点 O ,并算出∠BAC的角平分线AO的斜率。我们要找的最后一个点 D 一定在射线 AO 上，并且满足|AD| > |AO|。因此，我们可以在角平分线上的所有点中进行二分，并统计对应的数量。

最后还需要计算A点关于O点的对称点是否存在，计算正方形的数量并减去。

上述做法的复杂度为 ，但由于需要使用map或者哈希对斜率以及射线上的点进行预处理，本做法的运行时间较为缓慢。

实际上，平面上的点最多只能构造出 个筝形（含退化），并且仅含一个直角内角的筝形数量远远达不到这一上界。因此不进行二分，直接遍历角平分线上的所有点的复杂度也是可以接受的。

在验题时，这两种方法都有人实现，并且运行时间相当。在设置时限时，我们对所有 的代码进行了测试，最终设置的时限使得最慢的 代码能够贴着时限通过，并且使得任何一个 做法均无法通过。但比赛时似乎有众多选手写出了正确复杂度但得到TLE的情况，负责人再次为出现这一情况为大家磕头谢罪。

参考代码1（ 大常数map+模拟+二分 )：

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
PII e[N];
ll cnt,cntsq;
set<PII> se;
vector<PII> dots;
map<PII,vector<int>> mp;
int dx[4]={1,-1,-1,1},dy[4]={1,1,-1,-1};

int xiangxian(int ux,int uy){
    if(ux>=0){
        if(uy>=0) return 0;
        else return 3;
    }else{
        if(uy>=0) return 1;
        else return 2;
    }
}


void cal2(PII x){
    x.first*=2,x.second*=2;
    PII xl;
    int bei;
    if(x.first==0){
        xl={0,1};
        bei=x.second;
        if(x.second<0){
            xl={0,-1};
            bei=-x.second;
        }
    }else if(x.second==0){
        xl={1,0};
        bei=x.first;
        if(x.first<0){
            xl={-1,0};
            bei=-x.first;
        }
    }else{
        ll gg=__gcd(abs(x.first),abs(x.second));
        xl={x.first/gg,x.second/gg};
        bei=gg;
        // if(x.first<0){
        //     xl.first*=-1;
        //     xl.second*=-1;
        //     bei=-bei;
        // }
    }
    mp[xl].push_back(bei);
}

int cal0(PII x){
    bool flag=0;
    if(x.first<0) flag=1;
    PII xl;
    int bei;
    if(x.first==0){
        xl={0,1};
        bei=x.second;
        if(x.second<0){
            xl={0,-1};
            bei=-x.second;
        }
    }else if(x.second==0){
        xl={1,0};
        bei=x.first;
        if(x.first<0){
            xl={-1,0};
            bei=-x.first;
        }
    }else{
        ll gg=__gcd(abs(x.first),abs(x.second));
        xl={x.first/gg,x.second/gg};
        bei=gg;
        // if(x.first<0){
        //     xl.first*=-1;
        //     xl.second*=-1;
        //     bei=-bei;
        // }
    }
    if(!mp.count(xl)) return 0;
    vector<int> &vec=mp[xl];
    // cout<<bei<<" ";
    // cout<<endl;
    // for(auto j:vec) cout<<j<<" ";
    // cout<<endl;
    // if(!flag){
        auto it=lower_bound(vec.begin(),vec.end(),bei);
        int id=it-vec.begin()+1;

        if((*it)==bei) id++;
        return max(0,(int)vec.size()-id+1);
    // }else{
    //     auto it=lower_bound(vec.begin(),vec.end(),bei);
    //     int id=it-vec.begin()+1;
    //     if((*it)==bei) id--;
    //     return id;
    // }
}

void cal(int med){
    dots.clear();
    se.clear();
    mp.clear();
    for(int i=1;i<=n;i++){
        if(i==med) continue;
        dots.push_back({e[i].first-e[med].first,e[i].second-e[med].second});
    }
    for(auto t:dots){
         se.insert(t);
         cal2(t);
    }
    for(auto &[x,y]:mp){
        sort(y.begin(),y.end());
        // for(auto j:y) cout<<j<<" ";
        // cout<<endl;
    }
    for(auto [x,y]:dots){
        int xx=xiangxian(x,y);
        xx=(xx+1)%4;
        int nwx=abs(y),nwy=abs(x);
        nwx*=dx[xx],nwy*=dy[xx];
        if(!se.count({nwx,nwy})) continue;
        int midx=x+nwx,midy=y+nwy;
        cnt+=cal0({midx,midy});
        int sqx=midx,sqy=midy;
        // cout<<med<<" "<<x<<" "<<y<<" "<<nwx<<" "<<nwy<<" "<<sqx<<' '<<sqy<<endl;
        if(se.count({sqx,sqy})) cntsq++;
    }
}

void __(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>e[i].first>>e[i].second;
        // e[i].first*=2,e[i].second*=2;
    }
    for(int i=1;i<=n;i++){
        cal(i);
        // cout<<cnt<<" "<<cntsq<<endl;
    }
    cout<<cnt-cntsq<<"\n";
}


int main(){
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}

参考代码2（遍历角平分线上的所有点，by 成都信息工程大学——冰冷帝企鹅）：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f
#define vi vector <int>
#define vvi vector <vi>
#define endl '\n'
#define ll long long
//#define int long long
using namespace std;
ll maxn = 1e18;
constexpr int mod = 998244353, N = 2e5 + 5, M = 2e5 + 5;
struct Point{
  ll x , y;
  bool operator < (Point oth) const{
  	if( y == oth.y ) return x < oth.x;
  	else return y < oth.y;
  }
};
ll len(Point a,Point b){
  return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
Point round(Point a,Point b){
  ll dx = b.x - a.x , dy = b.y - a.y;
  ll nx = a.x + dy , ny = a.y - dx;
  return (Point){nx,ny};
}
ll cross(Point a,Point b){
  return a.x * b.y - a.y * b.x;
}
ll dao(Point a,Point b){
  return a.x*b.x + a.y*b.y;
}
void solve()
{
  int n;
  cin >> n;
  vector<Point> a(n+10);
  map<Point,int> mp;
  vector<map<pair<ll,ll>,vector<ll>>> ac(n+10);
  for( int i = 1 ; i <= n ; i++ ){
  	cin >> a[i].x >> a[i].y;
  	mp[a[i]]++;
  }
  for( int i = 1 ; i <= n ; i++ ){
  	for( int j = 1 ; j <= n ; j++ ){
  		if( i == j ) continue;
  		ll dx = a[j].x - a[i].x , dy = a[j].y - a[i].y;
  		ll g = gcd( abs(dx) , abs(dy) );
  		dx /= g , dy /= g;
  		ac[i][{dx,dy}].push_back(len(a[i],a[j]));
  	}
  }
  ll ans = 0;
  for( int i = 1 ; i <= n ; i++ ){
  	Point b = a[i];
  	for( int j = 1 ; j <= n ; j++ ){
  		if( j == i ) continue;
  		Point c = a[j];
  		Point d = round(b,c);
  		if( !mp.count(d) ) continue;
  		Point e = round(d,b);
  		ll dx = e.x - b.x , dy = e.y - b.y;
  		ll g = gcd( abs(dx) , abs(dy) );
  		dx /= g , dy /= g;
  		if( !ac[i].count({dx,dy}) ) continue;
  		ll x = len(b,e);
  		assert( x == len(c,d) );
  		auto & t = ac[i][{dx,dy}];
//			ll num = 
  		for( auto y : t ){
  			if( y * 4 > x && y != x ) ans++;
  		}
//			if( mp.count(e) && num > 0 ) num--;
//			ans += num;
  	}
  }
  cout << ans << endl;	
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0); //cout.tie(0);
  
  int t = 1;
  //	cin >> t; 
  while(t --) solve();
  
  return 0;
}

/*
2 1 0
2 4 0
2 6 0
2 7 1
3 1 0
3 2 1
4 3 0
5 2 0
6 1 0
6 5 1
7 4 0
7 8 0
8 2 0
3


2 0
2 0
2 0
2 1
3 0
3 1
4 0
5 0
6 0
6 1
7 0
7 0
8 0
3

*/

以下是出题人题解：

首先枚举直角顶点 A ，以 A为原点建立平面直角坐标系。对其它点进行极角排序，并通过双指针找到所有带45°角的三角形 ABD。

此时，我们需要判断第四个点是否存在。假设AB为直角边，我们需要求解D点关于线段AB的对称点C。

为了保证是凸多边形,我们可以对45°角两条射线上的点再做一次双指针来统计所有满足题意的带有45°角的三角形，复杂度瓶颈在排序，为。

由于坐标范围较小，可以全程使用整数运算来加速，判断45°角可以使用余弦定理两边平方。

参考代码3:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct p2{
	ll x,y;
	friend p2 operator+(p2 a,p2 b){return {a.x+b.x,a.y+b.y};}
	friend p2 operator-(p2 a,p2 b){return {a.x-b.x,a.y-b.y};}
	friend ll operator*(p2 a,p2 b){return a.x*b.x+a.y*b.y;}
	friend ll operator^(p2 a,p2 b){return a.x*b.y-a.y*b.x;}
	friend bool operator<(p2 a,p2 b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);}
	ll len2() {return x*x+y*y;}
	p2 nor(){return {-y,x};}
	void rd(){cin>>x>>y;}
	double ang(){return atan2(y,x);}
};
vector<p2> vp;
set<p2> mp;
int square=0;
int res=0;
void solve(){
	int n;cin>>n;
	for(int i=0;i<n;i++){
		p2 tp;tp.rd();
		vp.push_back(tp);
		mp.insert(tp);
	}
	for(int i=0;i<n;i++){
		p2 O=vp[i];
		vector<p2> v;
		for(int j=0;j<n;j++){
			if(j==i) continue;
			v.push_back(vp[j]);
		}

		sort(v.begin(), v.end(), [&](p2 a, p2 b) {
			p2 aa=a-O,bb=b-O;
		    bool ha = (aa.y > 0) || (aa.y == 0 && aa.x > 0);
		    bool hb = (bb.y > 0) || (bb.y == 0 && bb.x > 0);
		    if (ha != hb)  return ha > hb;
		    ll cj=aa^bb;
		    if (cj)  return cj > 0;
		    return (aa.len2()<bb.len2());
		});

		vector<int> vv={0},sz;
		for(int j=1;j<n-1;j++){
			ll cj=(v[j]-O)^(v[j-1]-O);
			ll dj=(v[j]-O)*(v[j-1]-O);
			if(cj || (cj==0 && dj<0))
				vv.push_back(j);
		}
		int m=vv.size();
        for(int j=0;j<m-1;j++){
            sz.push_back(vv[j+1]-vv[j]);
        }sz.push_back(n-1-vv[m-1]);
		for(int l=0,r=1;l<m;l++){
			while(1){
				p2 l1=v[vv[l]]-O;
				p2 r1=v[vv[r]]-O;
				if ( (l1^r1)<0 ) break;//不在同侧
				if ( (l1*r1)<0 || 2*(l1*r1)*(l1*r1) < (l1*l1)*(r1*r1) ) break;//大于45°
				if (2*(l1*r1)*(l1*r1) == (l1*l1)*(r1*r1) ){ // 夹角cos^2=0.5
					for(int L=0,R=0;L<sz[l];L++){
						while(1){
							if(R==sz[r]) break;
							if((O-v[vv[r]+R] )*(v[vv[l]+L]-v[vv[r]+R])<=0) R++;
							else break;
						}
						if(R==sz[r]) break;
						p2 l2=v[vv[l]+L]-O;
						p2 r2=v[vv[r]+R]-O;
						p2 ff=l2.nor()+O;//对称点
						if(mp.count(ff)){
							if(mp.count(ff+l2)) res--;
							res+=sz[r]-R;
						}
					}
				}
				if((r+1)%m == l) break;
				else r=(r+1)%m;
			}
		}
	}
	cout<<res<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

E

简要题意：

给定一个仅含有大写字母的字符串，你需要对这个字符串进行重新排列，使得该新字符串不含有长度对于 的回文串，并输出方案。如果不存在合法方案，请输出 。

题解：

一个字符串合法，当且仅当：串中任意两个相同的字母，它们之间的距离都 即对任意 , 若 ，则

记可重字符集为结论：，定义是合法字符集，当且仅当不满足以下两种情况的任意一种： 最多字母的数量 (记为L1) ，例如aaaabbcc、aaaabbbcc； ，且最多、第二多字母的数量都 (记为L2)，例如aaaabbbbcc。

为了符合要求，如果想尽可能多的放某种字母，最好的方式是放在位置最多有 个位置。 故 满足L1时一定排列不出符合要求的串。 若 满足L2，最多的字母有且只有一种情况放得下：放在位置，恰好 个位置。 但是有两种不同的字母都出现了 次，不可能都放在位置1,4,7,...,n。 故 满足 L2 时一定排列不出符合要求的串。

---

以下是繁杂的构造证明过程：若 是合法字符集，一定存在一种排列 的方案，使得最大回文串长度为 。

构造方法： 为了字典序最小，从左往右一个个确定。

记 为前 个字母选择完毕之后，剩余的字母的可重集。确定第个字母 时，只能从 中有的字母选择。

由定义 ，可知 一定合法。

确定字母 时，必须满足两个条件：

条件1：不与 相同(否则立刻产生回文串)； 条件2：选择 后，剩下的字母组成的字符集 合法(否则后 个位置一定会产生回文串)。

考虑 中所有字母，从符合条件1,2的字母中，选字典序最小的。

---

如果这种方法成功构造完了整个串，这个串一定符合要求，且不可能存在比这个串字典序更小的解(每一位都不可能有更小的选择)。下面通过反证法证明一定可以构造完整个串。

假设这种方法在某种情况下失败，记第一次失败的位置为 ，即前 个字母已经确定完毕，但 中所有字母都不符合条件1或2，导致第 个字母无法选择。

由于k是第一次失败的位置， 一定都是合法的字符集。

若 中所有字母都不符合条件1(即 中所有字母都与 或 相同)，则 至多有 种字母。

若 有 种字母，由 合法知 只有 个字母，假设为a。

由a与 或 相同，可知 只有3个字母，但含有 个 a (或 只有 个字母，但含有 个a)，与 都合法矛盾。 若 有 种字母，由 合法知 只有 个字母，假设为ab。 由于a,b都与 或 相同，可知 ， 为ab或ba，即 一定为aabb，与 合法矛盾。

若 中存在字母 符合条件1，则 一定不符合条件2。

由 合法的定义可知，若 合法， 中出现次数最多的字母一定符合条件2。

（若 个字母可以排列成符合要求的串，将出现次数最多的字母删去一个，剩下 个字母一定也可以排列成符合要求的串） 假设 中出现次数最多的字母为 a（如果有两种字母出现次数同为最多，假设为 a,b）

则a,b一定不符合条件1(即a,b等于 或 )，一定有 a， b。

不符合条件2，则选择 后剩下的字符集 一定不合法，即 满足L1或L2。

若选择 后， 满足L1： 此时 中出现次数最多的字母一定是a，假设a出现了 次，由于 有 个字母，则

a不符合条件1，则 中一定有a，故在 中a至少出现 次。

最多有 个字母，而 ，即 满足L1，与 都合法矛盾。 若选择 后， 满足L2：

此时 中出现次数最多的字母一定是 a,b，假设a,b都出现了次，则 。 a,b不符合条件1，则 一定是ab或ba。故在 中a,b都至少出现了 次。

有 个字母，且 ，即 满足L2，与 合法矛盾.

综上，由反证法证明了构造方法的正确性，问题得解。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define For(i,j,k) for(int i=j;i<=k;++i)
typedef long long ll;
const int N=1e6+5;
char ch[N]; int a[29];
bool check(int n){
    int ma1=0,ma2=0;
    For(i,0,25){
        if (a[i]>ma1) ma2=ma1,ma1=a[i];
        else if (a[i]>ma2) ma2=a[i];
    }
    if (ma1>(n-1)/3+1) return 0;
    if (n%3==1){
        if (ma1==n/3+1&&ma2==n/3+1) return 0;
    }
    return 1;
}
void fun(int n){
    For(i,1,n) ++a[ch[i]-'A'];
    ch[0]=ch[1]=0;
    if (!check(n)) {printf("-1\n"); return;}
    For(i,2,n+1){
        For(j,0,25) if (a[j]>0&&ch[i-2]!='A'+j&&ch[i-1]!='A'+j){
            --a[j];
            if (check(n-i+1)){
                ch[i]='A'+j; break;
            }
            ++a[j];
        }
    }
    For(i,2,n+1) printf("%c",ch[i]); printf("\n");
    return;
}
int main(){
    int _,n; cin>>_;
    while(_--){
        scanf("%s",ch+1); n=strlen(ch+1);
        fun(n); memset(a,0,sizeof(a));
    }
    return 0;
}

J

题解：

（待施工）

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<ll,ll> PII;

ll q,n,m,k;

int a[N],b[N];
vector<int> e[N];
char s[N];
int p[N];
ll _move;

ll ans=0;
ll tr[N];

ll sz[3][N],sz_upd[3][3][N];
int tot[3];

void clr(){
	for(int i=0;i<=_move*2;i++) tr[i]=0;
}

int lowbit(int x){
	return x&-x;
}

void add(ll x,ll c){
	assert(x>=0);
	for(int i=x;i<=_move*2;i+=lowbit(i)) tr[i]+=c; 
}

ll query(ll x){
	assert(x>=0);
	ll sum=0;
	for(int i=x;i>0;i-=lowbit(i)) sum+=tr[i];
	return sum;
}

void dfs_pre(int x,int fa){
	for(int i=0;i<3;i++){
		// tot[a[x]]++;
		if(a[x]!=i) sz[i][x]=1;
		else sz[i][x]=0;
	}
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			sz_upd[i][j][x]=0;
			if(a[x]!=i) sz_upd[i][j][x]--;
			if(a[x]!=j) sz_upd[i][j][x]++;
		}
	}
	for(auto u:e[x]){
		if(u==fa) continue;
		dfs_pre(u,x);
		for(int i=0;i<3;i++) sz[i][x]+=sz[i][u];
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				sz_upd[i][j][x]+=sz_upd[i][j][u];
			}
		}
	}
}


void dfs12(int x,int fa){
	if(x!=1){
		ans+=query(k-sz_upd[1][2][x]+_move);
		
		ll leave=(n-tot[0]-sz[0][x]+sz[1][x]);
		add(leave+_move,1);
	}	

	for(auto j:e[x]){
		if(j==fa) continue;
		dfs12(j,x);
	}
	if(x!=1){
		ll leave=(n-tot[0]-sz[0][x]+sz[1][x]);
		add(leave+_move,-1);
	}	
}


void dfs21(int x,int fa){
	if(x!=1){
		ans+=query(k-sz_upd[2][1][x]+_move);
		ll leave=(n-tot[0]-sz[0][x]+sz[2][x]);
		add(leave+_move,1);
	}	

	for(auto j:e[x]){
		if(j==fa) continue;
		dfs21(j,x);
	}
	if(x!=1){
		ll leave=(n-tot[0]-sz[0][x]+sz[2][x]);
		add(leave+_move,-1);
	}	
}



void dfs1(int x,int fa){//两子树相隔
	if(x!=1){
		int leave=n-tot[0]-sz[0][x]+sz[1][x];
		add(sz_upd[0][2][x]+_move,-1);
		ans+=query(k-leave+_move);
	}
	for(auto j:e[x]){
		if(j==fa) continue;
		dfs1(j,x);
	}
	if(x!=1){
		int leave=n-tot[0]-sz[0][x]+sz[1][x];
		add(sz_upd[0][2][x]+_move,1);
	}
}

void dfs10(int x,int fa){
	if(x!=1){
		ans-=query(k-sz_upd[0][2][x]+_move);
		int leave=n-tot[0]-sz[0][x]+sz[1][x];
		add(leave+_move,1);
	}
	for(auto j:e[x]){
		if(j==fa) continue;
		dfs10(j,x);
	}

	if(x!=1){
		int leave=n-tot[0]-sz[0][x]+sz[1][x];
		add(leave+_move,-1);
	}
}


void __(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) e[i].clear();
	scanf("%s",s+1);
	_move=n*2+15;
	memset(tot,0,sizeof tot);
	for(int i=1;i<=n;i++){
		if(s[i]=='R') a[i]=0;
		else if(s[i]=='G') a[i]=1;
		else a[i]=2;
	}
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	ans=0;
	int ccc=3;
	while(ccc--){
		clr();
		for(int i=0;i<3;i++) tot[i]=0;
		for(int i=1;i<=n;i++) tot[a[i]]++;
		dfs_pre(1,-1);
		clr();
		dfs12(1,-1);
		clr();
		dfs21(1,-1);
		clr();

		for(int i=2;i<=n;i++){
			ll leave=(n-tot[0]-sz[0][i]+sz[1][i]);
			add(sz_upd[0][2][i]+_move,1);
		}
		dfs1(1,-1);
		clr();
		dfs10(1,-1);
		for(int i=1;i<=n;i++) a[i]=(a[i]+1)%3;
	}
	clr();
	cout<<ans<<"\n";
}



int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        __();
    }

}

参考代码2（by SATSKY_2025target_LGM ):

#include<bits/stdc++.h>
using namespace std;using ll=long long;using i128=__int128;using ull=unsigned long long;using ld=long double;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pdd=pair<ld,ld>;
clock_t tcl;void toS(){tcl=clock();}void toT(char c=':'){cout<<"Time"<<c<<double(clock()-tcl)<<'\n';}
const ll inf=1e17,Bas=(1ll<<30)-1;const ld eps=1e-10;//const int M=998244353;
bool tso=0;
template<typename T>struct Fenwick{int n,B;vector<T>a;//for sum
    void init(int n_){n=n_+1;for(B=1;B*2<=n;B<<=1);a.assign(n+1,T{});}Fenwick(int n_=0){init(n_);}
    void add(int x,const T&v){if(x<0)exit(1);for(int i=x;i<=n;i+=i&-i)a[i]+=v;}
    T sum(int x){if(x<0)return 0;T ans{};for(int i=min(x,n);i;i-=i&-i)ans+=a[i];return ans;}
    T rS(int l,int r){return sum(r)-sum(l-1);}
	int kth(int k){int res=0;for(int b=B;b;b>>=1)if(res+b<=n&&a[res+b]<k)k-=a[res+=b];return res+1;}};
struct S
{	
    int n,k,rk=0,Bas[3];vector<int>a,l,r;vector<vector<int>>pre,es;ll res=0;
    Fenwick<int>A[3][3];
    void g_dfn(int x,int lst)
    {
        l[x]=++rk;for(int z=0;z<3;z++)pre[z][rk]=pre[z][rk-1]+(a[x]==z);
        for(auto&k:es[x])if(k^lst)g_dfn(k,x);r[x]=rk;
    }
    int gco(int l,int r,int a){return r-(l-1)-(pre[a][r]-pre[a][l-1]);}//o to a
    int gco2(int l,int r,int a,int b){return pre[a][r]-pre[a][l-1]-(pre[b][r]-pre[b][l-1]);}//a to b
    void spr(int x,int lst)
    {
        if(tso)cout<<x<<"-"<<lst<<"-A"<<'\n';
        for(int a=0;a<3;a++)for(int b=0;b<3;b++)if(b^a)
        {
            int c=3-a-b;
            int Bu=gco2(l[x],r[x],b,c);//Bas[a]+Bu+?<=k(+n)
            res+=A[a][b].sum(k+n-Bas[a]-Bu);
            int Bd=gco2(l[x],r[x],a,c);
            res-=A[a][b].sum(k+n-Bas[a]-Bd);
        }
        if(tso)cout<<x<<"-"<<lst<<"-B"<<'\n';
        if(x^1)for(int a=0;a<3;a++)for(int b=0;b<3;b++)if(b^a)
        {
            A[a][b].add(gco2(l[x],r[x],a,b)+n,1);
        }
        if(tso)cout<<x<<"-"<<lst<<"-C"<<'\n';
        for(auto&k:es[x])if(k^lst)spr(k,x);
        if(tso)cout<<x<<"-"<<lst<<"-D"<<'\n';
        if(x^1)for(int a=0;a<3;a++)for(int b=0;b<3;b++)if(b^a)
        {
            A[a][b].add(gco2(l[x],r[x],a,b)+n,-1);
        }
        if(tso)cout<<x<<"-"<<lst<<"-E"<<'\n';
    }
    void solve()
	{
        cin>>n>>k;a.resize(n+1);l=r=a;es.resize(n+1);pre.resize(3,vector<int>(n+1,0));
        for(int a=0;a<3;a++)for(int b=0;b<3;b++)if(b^a)A[a][b].init(n*2);
        string s;cin>>s;for(int i=1;i<=n;i++)a[i]=(s[i-1]=='R')?0:2-(s[i-1]=='G');
        for(int i=1,u,v;i<n;i++)cin>>u>>v,es[u].push_back(v),es[v].push_back(u);g_dfn(1,0);
        for(int a=0;a<3;a++)
        {
            Bas[a]=gco(1,n,a);int bas=Bas[a]-n*2;
            vector<vector<int>>f(2,vector<int>(n*2+1));
            for(int z=0;z<2;z++)
            {
                int mi=n;
                for(int i=2;i<=n;i++)
                {
                    int dv=gco2(l[i],r[i],a,(a+z+1)%3)+n;
                    mi=min(mi,dv);f[z][dv]++;
                }
                bas+=mi;if(mi)for(int i=mi;i<=n*2;i++)f[z][i-mi]=f[z][i],f[z][i]=0;f[z].resize(n+1);
            }
            Fenwick<int>B;B.init(n+2);for(int i=0;i<=n;i++)B.add(i+1,f[0][i]);         
            for(int i=0;i<=n;i++)res+=ll(f[1][i])*B.sum(k-bas-i+1);//v0+v1+bas<=k
            for(int i=2;i<=n;i++)
            {
                int dv[2];for(int z=0;z<2;z++)dv[z]=gco2(l[i],r[i],a,(a+z+1)%3);
                if(dv[0]+dv[1]+Bas[a]<=k)res--;
            }
        }
        //cout<<(res%M+M)%M<<"--\n";
        spr(1,0);
        cout<<res<<"\n";
	}
};
void precal()
{
    
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	precal();int t=1;cin>>t;
	while(t--){S SS;SS.solve();}
}
/*
*/

L

简要题意：

一个"新版国王"的攻击范围为国王，车，马的范围的结合。现在给定一个 的棋盘，求出这个棋盘中在新版国王之间无法互相攻击到的情况下，至多能放置多少个"新版国王"，并输出方案。

题解1：

我们先思考国王之间能够构造出什么样的基本结构。将国王“斜着放”可以尽可能节省空间，构造得到的基本结构如下图所示：

由于两个国王无法处于同一行或者同一列，因此答案的上界是 。根据上述构造，从直觉上来看，当 较大时，可能存在一种构造方式使得上界能够取到。

接下来给出基于上述“斜着放”的一种构造方式。由于将行列翻转不会使得答案改变，当 时，我们可以对行列进行翻转。在下面的过程中，我们钦定 ：

在上图的构造方式中，国王占据了 等奇数行的位置，我们可以尝试在其下方再构造一条斜线，如下图所示：

下方的斜线能够占 等偶数行的位置，我们只需要再放两个棋子，分别放在第 行的某个位置即可。

由上图可见，第一条斜线占据了所有的奇数列，而第二条斜线占据了最小的 个偶数列，我们只需要找到较大的没有被使用的的两个偶数列，分别将棋子放到该列的第二行/第四行即可。

下图分别呈现了 与 的两种构造方式,分别代表 为偶数和 为奇数的构造方式：

当 为偶数时，我们可以将最后两个棋子放在 与 的位置；

当 为奇数时，我们可以将最后两个棋子放在 与 的位置。

对于上述构造方法，我们可以构造出所有 的情况。

对于 的情况，由于情况数很少，我们可以直接进行搜索求解合法方案。由于国王无法处于同一行或者同一列，单组数据的搜索的状态数是阶乘级别的，加上一些剪枝后运行速度可以接受。

对于 ，但 的情况 ，根据上述的构造方式，只要满足 即可构造出合法方案。因此我们可以直接令 并进行搜索。

在设置时限的时候，我们将时限设置为了带有剪枝的搜索代码的运行时间的十倍左右。

当然也可以使用打表或者直接对小数据分类讨论的方式。但对小数据进行分类讨论可能会非常麻烦。

参考代码（搜索）：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
vector<int> res[N],ces[N];
int ans;
int M;
int b[N],a[N];
bool check(){
    int ans=0;
    vector<PII> vec;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) if(res[i][j]) vec.push_back({i,j});
    }
    assert(vec.size()==n);
    set<int> se1,se2;
    for(auto [x,y]:vec){
        if(se1.count(x)) return false;
        if(se2.count(y)) return false;
        se1.insert(x);
        se2.insert(y);
    }
    for(auto [x,y]:vec){
        // cout<<x<<" "<<y<<endl;
        for(int dx=-2;dx<=2;dx++){
            for(int dy=-2;dy<=2;dy++){
                if(abs(dx)==2&&abs(dy)==2) continue;
                if(dx==0&&dy==0) continue;
                int nx=x+dx,ny=y+dy;
                if(nx<0||nx>=n) continue;
                if(ny<0||ny>=n) continue;
                // cout<<"--"<<nx<<" "<<ny<<endl;
                if(res[nx][ny]){
                    // cout<<"--"<<nx<<" "<<ny<<endl;
                     return false; 
                }
            }
        }
        // cout<<114514<<endl;
    }
    // cout<<114514<<endl;
    return true;
}

bool tf[N];

void dfs(int x,int res){
    if(x>=n){
        if(res>ans){
            ans=res;
            for(int i=0;i<n;i++) b[i]=a[i];
        }
    }else{
        a[x]=-1;
        dfs(x+1,res);
        for(int i=0;i<M;i++){
            if(tf[i]) continue;
            if(ces[x][i]>0) continue;
            tf[i]=1;
            a[x]=i;
            
            for(int dx=-2;dx<=2;dx++){
                for(int dy=-2;dy<=2;dy++){
                    if(abs(dx)==2&&abs(dy)==2) continue;
                    int nwx=x+dx,nwy=i+dy;
                    if(nwx<0||nwx>=n) continue;
                    if(nwy<0||nwy>=m) continue;
                    ces[nwx][nwy]++;
                }
            }
            dfs(x+1,res+1);
            for(int dx=-2;dx<=2;dx++){
                for(int dy=-2;dy<=2;dy++){
                    if(abs(dx)==2&&abs(dy)==2) continue;
                    int nwx=x+dx,nwy=i+dy;
                    if(nwx<0||nwx>=n) continue;
                    if(nwy<0||nwy>=m) continue;
                    ces[nwx][nwy]--;
                }
            }
            
            tf[i]=0;
            a[x]=-1;
        }
    }
}

void __(){
    
    cin>>n>>m;
    bool flag=0;
    if(n>m){
        swap(n,m);
        flag=1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) res[i].push_back(0),ces[i].push_back(0);
    }
    // cout<<n<<endl;
    int t=min(n,m);

    if(t>=8){
        ans=t;
        for(int i=0;i<n;i+=2) res[i][i]=1;
        if(n%2==0){
            res[1][n-3]=1;
            res[3][n-1]=1;
        }else{
            res[1][n-4]=1;
            res[3][n-2]=1;
        }
        for(int i=5,j=1;i<n;i+=2,j+=2) res[i][j]=1;
    }else{
        M=min(m,8);
        ans=0;
        for(int i=0;i<=M;i++) tf[i]=0;
        dfs(0,0);
        // for(int i=0;i<n;i++) cout<<b[i]<<" ";
        // cout<<endl;
        for(int i=0;i<n;i++){
            if(b[i]!=-1) res[i][b[i]]=1;
        }
    }



    cout<<ans<<"\n";
    if(!flag)
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++) cout<<res[i][j];
            cout<<"\n";
        }
    else 
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++) cout<<res[j][i];
            cout<<"\n";
        }
    // check();
    // assert(check());
    
    for(int i=0;i<n;i++){
        res[i].clear();
        ces[i].clear();
    }
}


int main(){
    
    int _=1;
    cin>>_;
    // n=8;
    while(_--){
        __();
        n++;
    }
}

题解2：

可以首先考虑较简单的问题，即正方形的情况：

由于不能同行和同列的性质，王的数量至多 ，我们可以尝试寻找一种方案使得对于足够大的 网格，一定能放下 个王。为了放下最多棋子，考虑如何让棋子能贴的足够近又不互相攻击：可以通过纸笔手算，或者对较小的正方形暴力打表然后找规律，来得到一个可行的方案。

其中一种方案如下：

当 为 的倍数时，将棋子分为 组：

同组内棋子一定不会互相攻击，当 时，组间的间隔足够大，因此组间不会互相攻击，得到了合法的构造。图中为 的方案

若 或 ，可以先如上所述构造 的方案，再裁剪掉左上角或右下角。图中蓝框为的方案:

按照如上方案我们对 的正方形均实现了完备构造。

对于长方形，如果 ，构造边长为的正方形即可；

如果且，构造的正方形并裁剪前行/列即可；

剩余的 的情况数很少，打表或暴力 均可实现，手动构造可能会比较麻烦。

参考代码2（ 手动构造，by wjy666 ):

#include <bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
int a[10][10][10]={
{{1,0,0,0,0,0}},
{{1,0,0,0,0,0},{0,0,0,1,0,0}},
{{1,0,0,0,0,0},{0,0,0,0,0,1},{0,0,1,0,0,0}},
{{0,0,0,1,0,0},{1,0,0,0,0,0},{0,0,0,0,0,1},{0,0,1,0,0,0}},
{{0,0,0,1,0,0},{1,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,1,0},{0,1,0,0,0,0}},
{{0,0,0,1,0,0},{1,0,0,0,0,0},{0,0,0,0,0,1},{0,0,1,0,0,0},{0,0,0,0,0,0},{0,0,0,0,1,0}}
};
void pra(int n,int m){
    int cnt=0;
    if (n>m){
        For(i,0,n-1)
            For(j,0,m-1) if (a[m-1][j][i]) ++cnt; printf("%d\n",cnt);
        For(i,0,n-1){
            For(j,0,m-1) printf("%d",a[m-1][j][i]);
            printf("\n");
        }
    }
    else{
        For(i,0,n-1)
            For(j,0,m-1) if (a[n-1][i][j]) ++cnt; printf("%d\n",cnt);
        For(i,0,n-1){
            For(j,0,m-1) printf("%d",a[n-1][i][j]);
            printf("\n");
        }
    }
}
bool b[1005][1005]; int k;
void pr(int i,int j){
    if (i>=k||j>=k) printf("0");
    else printf("%d",b[i][j]);
}
int main(){
    int t; cin>>t;
    while(t--){
        int n,m; cin>>n>>m;
        if (n<=6&&m<=6) {pra(n,m); continue;}
        //
        k=max(min(n,m),7); memset(b,0,sizeof(b));
        while(k%3!=0) ++k;
        int x=0,y=0;
        For(i,1,k/3) b[x][y]=1,++x,y+=3;
        y=1;
        For(i,1,k/3) b[x][y]=1,++x,y+=3;
        y=2;
        For(i,1,k/3) b[x][y]=1,++x,y+=3;
        //
        printf("%d\n",min(n,m));
        if (max(min(n,m),7)%3==0){
            if (n>m){
                For(i,0,n-1){
                    For(j,0,m-1) pr(j,i);
                    printf("\n");
                }
            }
            else{
                For(i,0,n-1){
                    For(j,0,m-1) pr(i,j);
                    printf("\n");
                }
            }
        }
        else{
            if (n>m){
                For(i,1,n){
                    For(j,1,m) pr(j,i);
                    printf("\n");
                }
            }
            else{
                For(i,1,n){
                    For(j,1,m) pr(i,j);
                    printf("\n");
                }
            }
        }
    }
    return 0;
}