2025牛客暑期多校训练营7-做题&补题记录

一觉睡到一点才醒。紧赶慢赶跑去A310，老许已经写了两题。两个人GJ交了一万发又WA又T，然后突然发现这两题一点不难，G随手换了个构造方法就过了，J不用波兰肉板子直接bfs。绷。四题下播

---

C Forsaken City

找序列前缀最大值和当前元素的极差。

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

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;++i)
        cin>>a[i];
    int ma=a[0],ans=0;
    for(int i=1;i<n;++i)
    {
        ans=max(ans,ma-a[i]);
        ma=max(ma,a[i]);
    }
    cout<<ans<<"\n";
}

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

F The Correlation

操作不改变奇偶性，最小答案是奇数数量乘偶数数量。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353;
void solve()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;++i)
    {
        cin>>a[i];
    }
    if(n==1)
    {
        cout<<0<<"\n";
        return;
    }
    ll l1=0,l2=0;
    for(int i=0;i<n;++i)
    {
        if(a[i]&1) l1++;
        else l2++;
    }
    cout<<l1*l2%MOD<<"\n";
}

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

J Ivory

类似BFS的方式分步计算gcd，可以看做把若干质因数看做一个同一个维度一起考虑，这样就比波兰肉一个一个质数去做要快，就过了。

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

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

void solve()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    if(b>d) swap(b,d),swap(a,c);
    ll k=gcd(a,c);
    if(k==1) 
    {
        cout<<1<<"\n";
        return;
    }
    ll ans=ksm(k,min(b,d));
    vector<pair<ll,ll> > m1,m2;
    m1.push_back(make_pair(a/k,b));
    m2.push_back(make_pair(c/k,b));
    if(d>b)m2.push_back(make_pair(c,d-b));
    while(1)
    {
        bool flag=1;
        vector<pair<ll,ll> > mm1,mm2;
        int n=m1.size(),m=m2.size();
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                ll a=m1[i].first;
                ll c=m2[j].first;
                ll b=m1[i].second;
                ll d=m2[j].second;
                if((k=gcd(a,c))!=1)
                {
                    flag=0;
                    if(b<d)
                    {
                        mm1.push_back(make_pair(a/k,b));
                        mm2.push_back(make_pair(c/k,b));
                        mm2.push_back(make_pair(c,d-b));
                    }
                    else if(b==d)
                    {
                        mm1.push_back(make_pair(a/k,b));
                        mm2.push_back(make_pair(c/k,d));
                    }
                    else
                    {
                        mm1.push_back(make_pair(a/k,d));
                        mm1.push_back(make_pair(a,b-d));
                        mm2.push_back(make_pair(c/k,d));
                    }
                    ans*=ksm(k,min(b,d));
                    ans%=MOD;
                }
            }
        }
        if(flag) break;
        m1=mm1;
        m2=mm2;
    }
    // while(gcd(a,f)!=1)
    // {
    //     k=gcd(a,f);
    //     f/=k;
    //     ans*=ksm(k,min(b,d));
    //     ans%=MOD;
    // }
    cout<<ans<<"\n";

}

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

G Nice Doppelgnger

Guess。预处理一个答案表，输出前n/2项。打表发现答案序列两两元素的乘积不能在答案中，且还需要答案序列元素最多，因此从2开始加入序列，暴力判断即可，设置了上界，复杂度差不多和调和级数类似？基本上是$O(n\log{n})$（不会证（

/*

This code template was updated by Yukii_P on 2025/8/2.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

template<typename T> void chkmin(T& a, T b) { a = std::min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = std::max(a, b); }
template<typename T, const size_t S>
std::ostream& operator<<(std::ostream& o, const std::array<T, S>& x) { for (int i = (o << "[", 0); i < S; ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}
template<typename T>
std::ostream& operator<<(std::ostream& o, const std::vector<T>& x) { for (int i = (o << "[", 0); i < x.size(); ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = ", dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2> 
void dbg2(T x, T2... args) { std::cerr << ", " << x; dbg2(args...); }
template<typename T, typename... T2> 
void dbg1(T x, T2... args) { std::cerr << x; dbg2(args...); }
template<typename T> 
void dbg1(std::vector<T> x, int s) { s = std::min<int>(s, x.size()); for (int i = (std::cerr << "[", 0); i < s; ++i) std::cerr << x[i] << (i + 1 < s ? ", " : "]\n"); }
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e6 + 5;
constexpr int MOD = 998244353;

int vis[N];
vector<int> ans;

void init() {
    vis[1] = 1;
    ans.reserve(N / 2 + 1);
    for (int i = 1; i < N; i++) {
        if (vis[i]) continue;
        ans.push_back(i);
        for (int y : ans) {
            if (1LL * i * y >= N) break;
            vis[i * y] = 1;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    int cnt = 0;
    for (auto x : ans | views::take(n / 2)) {
        cout << x << " ";
    }
    cout << "\n";
}

signed main() {
    
    FIO;
    init();
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

A Loopy Laggon

注意到就秒出。注意不到就寄。观察发现旋转操作可以看成把原矩阵拆成一维序列以后在四个长度为四的环上做了12次置换，因此不改变这个一维序列的逆序对的奇偶性。做完所有操作，如果序列的逆序对数量是奇数则必定破坏，是偶数则有$\frac{1}{2}$的概率没被破坏，k个序列全是偶数即有$2^{-k}$的概率没被破坏。

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

int id,m,k,n;
const int N=105;
int a[N][N];
int s[N*N];

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

int query(int x)
{
    int res=0;
    while(x>0)
    {
        res+=s[x];
        x-=lowbit(x);
    }
    return res;
}

void update(int x,int k)
{
    while(x<N*N)
    {
        s[x]+=k;
        x+=lowbit(x);
    }
}
void solve()
{
    int flag=0;

    for(int l=1;l<=k;++l)
    {
        int ans=0;
        memset(s,0,sizeof(s));
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                cin>>a[i][j];
            }
        }
        if(flag) continue;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                ans+=query(a[i][j]);
                update(a[i][j],1);
            }
        }
        if(ans&1) flag=1;
    }
    cout<<flag;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int TxT=1;
    //cin>>TxT;
    cin>>id>>TxT>>k>>n;
    // pre();
    while(TxT--) solve();
    cout<<"\n";
    return 0;
}