赛中发现牛客上spj都忘传了，题目顺序和校内的也有些不同，然后也出了各种各样的锅，这里先说一声抱歉。

题面下载：http://dluacm.cn/wp-content/uploads/2023/04/202304.pdf
补题链接：https://ac.nowcoder.com/acm/contest/55416

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^{−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
一句话题意：给一棵 n 个点的树，求树上距离 \geq 3 的点对数

sol1 – 暴力 + LCA

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

时间复杂度 O(n^2\ log\ n)，实现优秀可通过

sol2 – BFS / DFS

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

时间复杂度 O(n^2)

sol3 – 直接统计

距离 = 1 的点对数：2 \cdot (n – 1)

距离 = 2 的点对数：设 d[i] 为点 i 的度数，则以 i 为中心的距离为 2 的点对数为 d[i]\cdot (d[i] – 1) ，总点对数为 \sum_{i=1}^n d[i]\cdot (d[i]-1)

所以答案即为 n\cdot (n-1)-\sum_{i=1}^n d[i]\cdot (d[i]-1)-2\cdot (n – 1)\over 2

时间复杂度 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} 分别为点 P 到栅栏围成的凸多边形的最近距离和最远距离，容易发现答案为 \pi(r_{max}^2-r_{min}^2)

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

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

#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

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

显然答案为 n!\over \Pi_{i=1}^m\ m_i!，直接计算即可，时间复杂度 O(n\ log \ 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

考虑到 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=0 时答案为 \frac{2}{3}，当 k\geq 1 时答案为 1

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

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

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

#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 的情况

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

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

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

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

答案即为删点后剩余的亡灵节点权值和加上叶子位置连通块的数目，遍历一遍图即可，时间复杂度 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,l+n-1] 是否与 [1,l-1] 与 [l+n,2n] 连接而成的字符串相等即可。

sol1 – 暴力匹配

直接判断即可，时间复杂度 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] 和 [1,l-1] + [l+n,2n] 的 hash 函数值，判断是否相等即可

#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();
}