大连大学ACM程序设计竞赛（4月赛）题解

赛中发现牛客上spj都忘传了，题目顺序和校内的也有些不同，然后也出了各种各样的锅，这里先说一声抱歉。出题人罗刹师以死谢罪（已经被暴打了）

A.大欢喜帝I

难度预测：Medium-Hard 比较暴力的做法：因为N只有50，我们用set去维护要烧的顺序（不用优先队列，因为激励后要修改），当烧掉一个人后，暴力遍历应该被激励的人。

另一种做法：使用优先队列维护，如果一个人被激励，则打上标记。出队列出到有标记的人的时候，计算激励时间，再放入队列。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
void Solve(){
    int n,m,k;
    LL ans=0;
    cin>>n>>m>>k;
    vector<vector<int>> u(n+1,vector<int>(m+1)),d=u,vis=u;
    vector<vector<LL>> val(n+1,vector<LL>(m+1));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            u[i][j]=i-1,d[i][j]=i+1,vis[i][j]=1;
    priority_queue<pair<LL,pair<int,int>>,vector<pair<LL,pair<int,int>>>,greater<pair<LL,pair<int,int>>>> q;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            cin>>val[i][j];
            q.push({val[i][j],{i,j}});
        }
    while(k){
        auto [tim,point]=q.top();
        auto [x,y]=point;
        q.pop();
        vis[x][y]-=1;
        if(vis[x][y]){
            q.push({val[x][y],{x,y}});
            continue;
        }
        --k;
        ans=tim;
        if(d[x][y]<=n&&(vis[d[x][y]][y]!=1||val[d[x][y]][y]!=tim)){
            u[d[x][y]][y]=u[x][y],d[u[x][y]][y]=d[x][y];
            vis[d[x][y]][y]=2;
            val[d[x][y]][y]=(3*val[d[x][y]][y]-ans+1)/2;
        }
    }
    cout<<ans<<'\n';
}
int main(){
    Solve();
    return 0;
}

B.大欢喜帝II

难度预测：Hard 作为本场比赛的压轴题之一，还是有一定难度的。 由于数据范围均有提升，所以我们只能考虑线性遍历。 我们可以发现，尽管人很多，但是当激励次数非常多的时候，后面的增加时间无限接近于0，本题忽略小数，所以保守起见我们最多激励64次（即计算到$2^{\mathrm{-}64}2^\{-64\}$）。 由于只会影响正后方，我们从前向后遍历，记录某个人被烧的时间。 由于前面被烧的人时间已经被记录，所以当我们遍历到某个人时，就可以算出他被烧的时间。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#include <regex>
#include <list>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define linf 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
using namespace std;
struct node {
    ll sec;
    ll x;
    ll y;
    bool operator < (const node& a) const {
        if (sec == a.sec && x == a.x) return y < a.y;
        if (sec == a.sec) return x < a.x;
        return sec < a.sec;
    }
};

int main() {
   // freopen("D:\\C\\1.txt", "r", stdin);
    //freopen("D:\\C\\2.txt", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    ll n, m, k, a;
    cin >> n >> m >> k;
    vector<vector<ll>> nums(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a;
            nums[i].push_back(a);
        }
    }
    map<ll, ll> mp;
    ll cnt = 0;
    vector<ll> pu;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cnt = 1;
            for (auto& l : mp) {
                //cout << l.first << " " << nums[j][i] << endl;
                if (l.first > nums[i][j]) break;
                if (cnt >= 63) break;
                for (int ii = 0; ii < l.second; ii++) {
                    if (cnt >= 63) break;
                    nums[i][j] += ((nums[i][j] - l.first) >> cnt);
                    cnt++;
                }
            }
            pu.push_back(nums[i][j]);
        }
        for (auto ii : pu) {
            mp[ii]++;
        }
        pu.clear();
    }
    
    ll re = 0;

    for (auto& i : mp) {
        //cout << i.first << " " << i.second << endl;
        re += i.second;
        if (re >= k) {
            re = i.first;
            break;
        }
    }
    cout << re << endl;
    return 0;
}

C. 通关

难度预测：Easy 根据“在进入第i关后，你当前的伤害值s变为当前伤害值s和该关卡伤害值的最小值”，所以很容易想到贪心。 我们将关卡伤害值从大到小排序，然后遍历一遍，即可得出答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define endl '\n'
#define all(v) v.begin(),v.end()
#define random(x) rand()%(x)
#define randomm(a,b) (rand()%((b)-(a)+1))+(a)
#define inf 0x7f7f7f7f
const ll mod=1e9+7;
const int N=5e5+5;
pair<int,int> p[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%d",&p[i].first);
        p[i].second=i;
    }
    for(int i=1;i<=n;++i){
        int t;
        scanf("%d",&t);
    }
    sort(p+1,p+n+1,greater<pair<int,int>>());
    printf("YES\n");
    for(int i=1;i<=n;++i)
        printf("%d%c",p[i].second,i==n?'\n':' ');
}
int main()
{

    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

D.樱花

难度预测：Medium 一句话题意：给一棵 $nn$ 个点的树，求树上距离 $\ge 3\backslash geq\; 3$ 的点对数

sol1 - 暴力 + LCA

记 $d[x]d[x]$ 为点 $xx$ 到根的距离，枚举所有的点对，求出 $xx$ 和 $yy$ 的最近公共祖先$(LCA)(LCA)$，则 $xx$ 和 $yy$ 的距离 $dis=d[x]+d[y]-2\cdot d[LCA(x,y)]dis=d[x]+d[y]-2\backslash cdot\; d[LCA(x,y)]$，统计所有 $dis\ge 3dis\backslash geq\; 3$ 的点对即可

时间复杂度 $O(n^{2}logn)O(n^2\backslash \; log\backslash \; n)$，实现优秀可通过

sol2 - BFS / DFS

对于每个点 $xx$ ，从 $xx$ 出发遍历一遍树，用 $d[y]d[y]$ 表示点 $yy$ 与点 $xx$ 的距离，统计 $d[y]\ge 3d[y]\; \backslash geq\; 3$ 的点的数目，最后求和即可

时间复杂度 $O(n^2)O(n^2)$

sol3 - 直接统计

距离 $=1=\; 1$ 的点对数：$2\cdot (n-1)2\; \backslash cdot\; (n\; -\; 1)$

距离 $=2=\; 2$ 的点对数：设 $d[i]d[i]$ 为点 $ii$ 的度数，则以 $ii$ 为中心的距离为 $22$ 的点对数为 $d[i]\cdot (d[i]-1)d[i]\backslash cdot\; (d[i]\; -\; 1)$ ，总点对数为 ${\sum }_{i=1}^{n}d[i]\cdot (d[i]-1)\backslash sum\_\{i=1\}^n\; d[i]\backslash cdot\; (d[i]-1)$

所以答案即为 $\frac{n\cdot (n-1)-{\sum }_{i=1}^{n}d[i]\cdot (d[i]-1)-2\cdot (n-1)}{2}n\backslash cdot\; (n-1)-\backslash sum\_\{i=1\}^n\; d[i]\backslash cdot\; (d[i]-1)-2\backslash cdot\; (n\; -\; 1)\backslash over\; 2$

时间复杂度 $O(n)O(n)$

#include <bits/stdc++.h>
using namespace std ;
const int N = 5005 ;
int n ;
int d[N] ;
int main()
{
	ios::sync_with_stdio(false) ;
	cin >> n ;
	for(int i = 1, a, b; i < n; ++ i)
	{
		cin >> a >> b ;
		d[a] ++ ; d[b] ++ ;
	}
	int ans = n * (n - 1) ;
	for(int i = 1; i <= n; ++ i) ans -= d[i] * (d[i] - 1) ;
	assert(ans % 2 == 0) ;
	cout << ans / 2 - n + 1 << '\n' ;
	return 0 ;
}

E.小w的抽奖游戏

难度预测：Medium-Hard

设 $r_{min},r_{max}r\_\{min\},r\_\{max\}$ 分别为点 $PP$ 到栅栏围成的凸多边形的最近距离和最远距离，容易发现答案为 $\pi (r_{max}^2-r_{min}^2)\backslash pi(r\_\{max\}^2-r\_\{min\}^2)$

$r_{max}r\_\{max\}$：遍历所有凸多边形上的点，取最大值

$r_{min}r\_\{min\}$：点到凸多边形的最近距离一定在凸多边形的某条边上取得，只需要求对于所有的边 $(i,i+1)(i,i+1)$，求出$PP$ 到该边的最短距离，取最小值即可

#include<bits/stdc++.h>
using namespace std ;
#define ld long double
const int N = 1e6 + 5 ;
constexpr double PI = 3.1415926535 ;
constexpr double eps = 1e-8 ;
struct Point
{
	ld x, y ;
	Point operator+(const Point &a) const
	{
		return {x + a.x, y + a.y} ;
	}
	Point operator-(const Point &a) const
	{
		return {x - a.x, y - a.y} ;
	}
	double operator^(const Point &a) const
	{
		return x * a.y - y * a.x ;
	}
	double operator*(const Point &a) const
	{
		return x * a.x + y * a.y ;
	}
	double len() const
	{
		return sqrtl((*this) * (*this)) ;
	}
}p[N] ;
 
struct Line 
{
	Point p, v ;
	double dist(const Point a) const 
	{
		return abs(v ^ (a - p)) / v.len() ;
	}
} ;
int toleft(Line a, Point b)
{
	double t = a.v ^ (b - a.p) ;
	return (t > eps) - (t < -eps) ;
}
double dis(Point a, Point b)
{
	return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) ;
}
int main()
{
	int n ; scanf("%d",&n) ;
	for(int i=1;i<=n;++i)
	{
		double x, y ; scanf("%lf%lf",&x,&y) ;
		p[i] = {(ld)x, (ld)y} ;
	}
	int px, py ; scanf("%d%d",&px,&py) ; Point q = {(ld)px, (ld)py} ;
	double ans_min = 1e18, ans_max = 0 ;
	for(int i=1;i<=n;++i)
	{
		ans_max = max(ans_max, dis(p[i], q)), ans_min = min(ans_min, dis(p[i], q)) ;
		Line uv = {p[i], p[i % n + 1] - p[i]} ;
		Point vt = {-uv.v.y, uv.v.x} ;
		Line nowlin = {q, vt} ;
		if(toleft(nowlin, p[i]) * toleft(nowlin, p[i % n + 1]) == -1)
			ans_min = min(ans_min, uv.dist(q)) ;
	}
	printf("%.9lf\n", PI * (ans_max * ans_max - ans_min * ans_min)) ;
	return 0 ;
}

F.十三幺

难度预测：medium 由于十三幺需要每种幺九各一张，再加上它们中的任意一个作为将牌，所以我们可以使用计数的思路。 计数的同时，设立一个将牌标记和点炮标记，分别表示是否已经有将牌和是否需要被点炮。 因为要考虑所有和牌可能，当没有将牌的时候，所有的幺九牌都是需要和的牌。 如果有将牌，则输出没有的幺九牌。 需要被点炮的时候，考虑其他人打出的牌是否为自己需要的牌。 最后如果和，输出88，否则根据其他人已经打出的牌输出。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#include <regex>
#include <list>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f

using namespace std;

struct point {
	int x, y;
	point() {};
	point(int _x, int _y): x(_x), y(_y) {};
	bool operator < (const point a) {
		return a.x < x;
	}
	friend istream &operator >>(istream &in, point &a) {
		in >> a.x >> a.y;
		return in;
	}
	friend ostream &operator <<(ostream &out, point &a) {
		out << a.x << " " << a.y;
		return out;
	}
};


int main() {
    int n;
    map<string,int> all;
    set<string> needwin;
    set<string> have;
    for(int i=1;i<=9;i+=8){
        needwin.insert(to_string(i)+"w");needwin.insert(to_string(i)+"b");needwin.insert(to_string(i)+"t");
    }
    needwin.insert("df");needwin.insert("nf");needwin.insert("xf");needwin.insert("bf");
    needwin.insert("zz");needwin.insert("ff");needwin.insert("bb");
    int num=14;
    bool jiang=0;
    string s,t;
    for(int i=0;i<13;i++){
        cin>>s;
        //if(needwin.count(s)) all[s]++;
        if(needwin.count(s)&&have.count(s)==0){
            num--;
            have.insert(s);
        }
        else if(needwin.count(s)&&have.count(s)&&jiang==0){
            num--;
            jiang=1;
        }
    }
    //cout<<num<<endl;
    cin>>n;
    while(n--){
        cin>>s;
        if(s=="00"){
            cin>>t;
            if(needwin.count(t)&&have.count(t)==0){
               // cout<<1<<endl;
                num--;
                have.insert(t);
            }
            else if(needwin.count(t)&&have.count(t)&&jiang==0){
                num--;
                jiang=1;
            }
        }
        else{
            if(num==1){
                if(jiang==0){
                    if(needwin.count(s)) num--;
                }
                else{
                    for(auto i:needwin){
                        if(have.count(i)==0&&s==i) num--;
                    }
                }
            }
            if(needwin.count(s)) all[s]++;
        }
    }
    assert(num>=0);
    //cout<<num<<endl;
    if(num==0){
        cout<<88<<endl;
    }
    else{
        int num=0;
        if(jiang==0){
            for(auto i:needwin){
               // cout<<i<<" "<<all[i]<<endl;
                if(have.count(i)){
                    num+=3-all[i];
                }
                else{
                    num+=4-all[i];
                }
            }
        }
        else{
            for(auto i:needwin){
                if(have.count(i)==0){
                    num+=4-all[i];
                }
            }

        }
        cout<<num<<endl;
    }
	return 0;
}

G.投篮球

难度预测：Medium

本质上是 $nn$ 个不同的球放到 $mm$ 个容量不同的盒子，且所有盒子的容量的和为 $nn$

显然答案为 $\frac{n!}{{\mathrm{\Pi }}_{i=1}^m{m}_i!}n!\backslash over\; \backslash Pi\_\{i=1\}^m\backslash \; m\_i!$，直接计算即可，时间复杂度 $O(nlogn)O(n\backslash \; log\; \backslash \; n)$

#include<bits/stdc++.h> 
using namespace std ;
const int N = 1e6 + 5 ;
#define ll long long
const int mod = 998244353 ;
ll jc[N], inv[N] ;
ll qsm(ll a, ll b)
{
	ll ans = 1 ;
	while(b)
	{
		if(b & 1) ans = ans * a % mod ;
		a = a * a % mod ; b >>= 1 ;
	}
	return ans ;
}
void init(int n = N - 5)
{
	jc[0] = 1 ;
	for(int i=1;i<=n;++i) jc[i] = jc[i - 1] * i % mod ;
	inv[n] = qsm(jc[n], mod - 2) ;
	for(int i=n;i>=1;--i) inv[i - 1] = inv[i] * i % mod ;
}
ll C(int n, int m)
{
	return jc[n] * inv[m] % mod * inv[n - m] % mod ;
}
int mi[N] ;
int main()
{
	int n, m ; scanf("%d%d", &n, &m) ; init(n) ;
	for(int i=1;i<=m;++i) scanf("%d", &mi[i]) ;
	ll ans = jc[n] ;
	for(int i=1;i<=m;++i) ans = ans * inv[mi[i]] % mod ;
	printf("%lld\n", ans) ;
	return 0 ;
}

H.彩色序列

难度预测：Medium

考虑到 $mm$ 的范围很小，可以直接枚举每个颜色代表左括号/右括号，判断括号序列的合法性即可。

时间复杂度 $O(n{2}^m)O(n2^m)$，加上剪枝很难跑到这个上限

#include<bits/stdc++.h>
using namespace std ;
const int N = 2e5 + 5 ;
int c[N] ;
int n,m ;
int main()
{
	scanf("%d%d",&n,&m) ;
	for(int i=1;i<=n;++i) scanf("%d",&c[i]) ;
	auto check = [&](int res)
	{
		int cnt = 0 ;
		for(int i=1;i<=n;++i)
		{
			int now = res >> (c[i] - 1) & 1 ;
			if(cnt && now == 1) cnt -- ;
			else if(now == 0) cnt ++ ;
			else return false ;
		}
		return cnt == 0 ;
	} ;
	for(int j=0;j<(1<<m);j++) if(check(j)) return puts("Yes"), 0 ;
	puts("No") ;
	return 0 ;
}

I.天下归心

难度预测：Medium-Easy 解法1：并查集维护所有点，能找到曹操就标记。 解法2：dfs或bfs。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#include <regex>
#include <list>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f

using namespace std;

struct point {
	int x, y;
	point() {};
	point(int _x, int _y): x(_x), y(_y) {};
	bool operator < (const point a) {
		return a.x < x;
	}
	friend istream &operator >>(istream &in, point &a) {
		in >> a.x >> a.y;
		return in;
	}
	friend ostream &operator <<(ostream &out, point &a) {
		out << a.x << " " << a.y;
		return out;
	}
};


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n,k;
        cin>>n>>k;
        int num[n+1];
        int cc=0;
        for(int i=1;i<=n;i++){
            cin>>num[i];
            if(num[i]==1)cc=i;
        }
        vector<int> ve[n+1];
        int a,b;
        while(k--){
            cin>>a>>b;
            ve[a].push_back(b);
            ve[b].push_back(a);
        }
        queue<int> q;
        bool vis[n+1];
        memset(vis,0,sizeof vis);
        q.push(cc);
        while(!q.empty()){
            int t=q.front();
            q.pop();
            if(vis[t]==1) continue;
            vis[t]=1;
            for(int i=0;i<ve[t].size();i++){
                if(vis[ve[t][i]]==1) continue;
                q.push(ve[t][i]);
            }
        }
        for(int i=1;i<=n;i++){
            if(vis[i]==1) cout<<num[i]<<" ";
            else if(num[i]==0) cout<<0<<" ";
            else cout<<-1<<" ";
        }
        cout<<endl;

    }
	return 0;
}

J.石头剪刀布

难度预测：Easy

结论题，当 $k=0k=0$ 时答案为 $\frac{2}{3}\backslash frac\{2\}\{3\}$，当 $k\ge 1k\backslash geq\; 1$ 时答案为 $11$

第一局 Alice 赢、平局、输的概率分别为 $\frac{1}{3}\backslash frac\{1\}\{3\}$，如果平局或 Alice 反悔则会继续进行下一局

从第二局开始，由于 Bob 随机出拳且不会出上一局重复的，那么 Alice 在最优策略下一定不会输（如 Bob 上一局出了拳，这局 Bob 不会出拳，Alice 可以出剪刀保证自己不败）

所以若 Alice 不能反悔，则获胜概率为 $\frac{2}{3}\backslash frac\{2\}\{3\}$，若能反悔，获胜概率为 $11$

#include<bits/stdc++.h>
using namespace std ;
int main()
{
    int T;scanf("%d",&T);
    while(T--){
	    int n ; scanf("%d",&n) ;
	    printf("%s\n", n ? "1.0000000000" : "0.6666666667") ;
    }
	return 0 ;
}

K.计算面积

难度预测：Easy 小学数学，直接算即可

#include<bits/stdc++.h>
using namespace std ;
int main()
{
	int T ; cin >> T ;
	while(T --)
	{
		int x, y, z, d ;
		cin >> x >> y >> z ;
		if(x == 1) cout << y * z << endl ;
		else if(x == 2) cout << y * z / 2 << endl ;
		else cin >> d, cout << (y + z) * d / 2 << endl ;
	}
	return 0 ;
}

L.Raksasa的圣战

难度预测：Hard 由于本题数据有误，请注意 num2 = 0 的情况

赛后我们查看代码，Aging1986 大佬过了，其他人均被卡在了第二个测试点上。和大佬说句抱歉（罗刹师orz）

首先，我们不断把树上叶子节点中的亡灵军团从树中删除，直到找不到这样的叶子节点。

删点后得出的树上剩余所有亡灵节点都是军队的必经点。

因为亡灵军团每次战斗前都可以复生，所以军队的最优方案是只经过每个亡灵军队节点仅一次

假设阵眼和空地相连形成了若干连通块，我们把这些连通块缩点后，军队经过非叶子位置的连通块可以直接放置该连通块所有的圣灵石，但到达叶子位置联通块是必须保证剩余人数不为 $00$

答案即为删点后剩余的亡灵节点权值和加上叶子位置连通块的数目，遍历一遍图即可，时间复杂度 $O(n)O(n)$

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
vector<pair<int, int>> ine ;
vector<vector<int>> g ;
vector<int> val, fa ;
int get(int x)
{
	return x == fa[x] ? x : fa[x] = get(fa[x]) ;
}
pair<ll, bool> dfs(int x, int f)
{
	bool flag = val[x] == -2 && x != get(1) ;
	ll ans = val[x] > 0 ? val[x] : 0 ;
	for(auto y : g[x]) if(y != f)
	{
		auto [a, b] = dfs(y, x) ;
		if(b) ans += a, flag = 1 ;
	}
	return {ans + (ans == 0 && flag), flag} ; 
}
void solve()
{
	int n ; scanf("%d", &n) ;
	ine.resize(n) ; g.resize(n + 1) ;
	val.resize(n + 1) ; fa.resize(n + 1) ;
    bool flag = 1 ;
	for(int i=1;i<=n;++i)
    {
        scanf("%d", &val[i]), fa[i] = i ;
        if(val[i] == -2) flag = 0 ;
    }
	for(int i=1,x,y;i<n;++i)
	{
		scanf("%d%d", &x, &y) ;
		ine[i] = {x, y} ;
		if(val[x] <= 0 && val[y] <= 0)
		{
			int l = get(x), r = get(y) ;
			if(l != r)
			{
				if(val[l] == -2) fa[r] = l ;
				else fa[l] = r ;
			}
		}
	}
    if(flag) return (void) printf("0\n") ;
	for(int i=1;i<=n;++i) fa[i] = get(i) ;
	for(auto [x, y] : ine) if(fa[x] != fa[y])
	{
		g[fa[x]].push_back(fa[y]) ;
		g[fa[y]].push_back(fa[x]) ;
	}
	printf("%lld\n", max(dfs(get(1), -1).first, 1ll)) ;
	ine.clear() ; g.clear() ;
	val.clear() ; fa.clear() ;
}
int main()
{
	int T ; scanf("%d", &T) ;
	while(T--) solve() ;
	return 0 ;
}

M.CV大师

难度预测：Easy

对于所有的 $l\in [1,n]l\backslash in\; [1,n]$，判断 $[l,l+n-1][l,l+n-1]$ 是否与 $[1,l-1][1,l-1]$ 与 $[l+n,2n][l+n,2n]$ 连接而成的字符串相等即可。

sol1 - 暴力匹配

直接判断即可，时间复杂度 $O(n^2)O(n^2)$

#include <bits/stdc++.h>
using namespace std ;
void solve()
{
	int n ; cin >> n ;
	string s ; cin >> s ; s = "_" + s ;
	for(int l = 1; l <= n; ++ l)
	{
		int r = l + n - 1, p = 1 ;
		bool flag = 1 ;
		for(int i = 1; i <= n; ++ i)
		{
			while(l <= p && p <= r) p ++ ;
			if(s[l + i - 1] != s[p]) { flag = 0 ; break ; }
			p ++ ;
		}
		if(flag) return (void) (cout << s.substr(l, n) << '\n') ;
	}
}
int main()
{
	ios::sync_with_stdio(false) ;
	int T ; cin >> T ;
	while(T --) solve() ;
	return 0 ;
}

sol2 - Hash

判断相等时，直接截取 $[l,l+n-1][l,l+n-1]$ 和 $[1,l-1][1,l-1]$ + $[l+n,2n][l+n,2n]$ 的 $hashhash$ 函数值，判断是否相等即可

#include <bits/stdc++.h>
using namespace std;
//const int N = 1e2 + 5;
typedef long long ll;
typedef unsigned long long ULL;
#define endl '\n'
//#define scanf scanf_s
int mod = 998244353;
const int N = 10010, P = 131, Q = 13331;

int n, m;
ULL h[N], p[N] = { 1 }, q[N] = { 1 }, h2[N];

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

ULL get2(int l, int r)
{
    return h2[r] - h2[l - 1] * q[r - l + 1];
}


void solve()
{
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for (int i = 1; i <= 2 * n; i++)
    {
        h[i] = h[i - 1] * P + s[i - 1]; // 将字符转换成P进制的数，+ 的 str[i] 是字符的ASCII码值
        h2[i] = h2[i - 1] * Q + s[i - 1];
    }
    for (int i = 1; i <= n; ++i) {
        ULL res1 = get(i, i + n - 1);
        ULL res2 = get(0, i - 1) * p[2 * n - (i + n - 1)] + get(i + n, 2 * n);
        ULL res3 = get2(i, i + n - 1);
        ULL res4 = get2(0, i - 1) * q[2 * n - (i + n - 1)] + get2(i + n, 2 * n);
        if (res1 == res2 && res3 == res4) {
            for (int j = 0; j < n; ++j) {
                cout << s[i + j - 1];
            }
            cout << endl;
            return;
        }
    }

}


int main()
{
    for (int i = 1; i <= 10000; i++)
    {
        p[i] = p[i - 1] * P;
        q[i] = q[i - 1] * Q;
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t; cin >> t; while (t--)
        solve();
}