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

思洋带飞。

---

M Digit Sum

Guess。1~9显然a取1即可，其他数无解。不会证。

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

int n;
void solve()
{
    cin>>n;
    if(n>=10)
    {
        cout<<"-1\n";
    }
    else
    {
        cout<<"1\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 Too many catgirls nya

不太像题。读字符串，给每行末尾加” nya”。

/*

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

*/
#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

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

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

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 = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    cout << n << " nya\n";
    string s;
    getline(cin, s);
    for (int i = 0; i < n; ++i) {
        string s;
        getline(cin, s);
        cout << s << " nya\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        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

*/

F Military Training

看成两点的中点在x和y轴同时移动一个单位即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll sx1,sy1,sx2,sy2,tx1,ty1,tx2,ty2;
void solve()
{
    cin>>sx1>>sy1>>sx2>>sy2>>tx1>>ty1>>tx2>>ty2;
    ll sx=sx1+sx2;
    ll sy=sy1+sy2;
    ll tx=tx1+tx2;
    ll ty=ty1+ty2;
    cout<<max(abs(tx-sx),abs(sy-ty))<<"\n";
}

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

C Epoch-making

思洋做的。还没补。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T1,typename T2>
ostream& operator<<(ostream& o,const tuple<T1,T2>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T1,typename T2,typename T3>
ostream& operator<<(ostream& o,const tuple<T1,T2,T3>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";
}

template<typename T,const size_t S>
ostream& operator<<(ostream& o,const array<T,S>& arr){
	for(int i=(o<<"[",0);i<S;++i)o<<arr[i]<<(i+1<S?",":"");
	return o<<"]\n";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	for(int i=(o<<"[",0);i<vec.size();++i)o<<vec[i]<<(i+1<vec.size()?",":"");
	return o<<"]\n";
}

constexpr int M = 2e5+5, mod = 998244353;// 1e9+7;
constexpr double pi = acos(-1), eps = 1e-9;

void solve(){
	int n,m;
	cin>>n>>m;
	vector<int> w(n),dep(n);
	vector<vector<int>> G(n);
	for(auto& i:w)cin>>i;
	for(int u,v,i=0;i<m;++i){
		cin>>u>>v;
		--u,--v;
		G[u].emplace_back(v);
		dep[v]|=(1<<u);
	}
	vector<int> dis(1<<n,1e9);
	using obj=tuple<int,int>;
	priority_queue<obj,vector<obj>,greater<obj>> pq;
	pq.emplace(0,0);
	dis[0]=0;
	while(!pq.empty()){
		auto [d,cur]=pq.top();
		pq.pop();
		if(d>dis[cur])continue;
		if(cur==(1<<n)-1)break;
		vector<tuple<int,int>> vec;
		for(int u=0;u<n;++u){
			if((cur>>u)&1){
				continue;
			}
			if((dep[u]&cur)==dep[u]){
				vec.emplace_back(w[u],1<<u);
			}
		}
		ranges::sort(vec);
		for(int s=0;auto [t,u]:vec){
			s|=u;
			int nxt=cur|s;
			if(dis[nxt]>d+t){
				dis[nxt]=d+t;
				pq.emplace(d+t,nxt);
			}
		}
	}
	cout<<dis.back()<<"\n";
	
	return;
}

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

G Permutation

思洋做的。注意到是笛卡尔树，后续观察没想清楚。

没补待填坑。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T1,typename T2>
ostream& operator<<(ostream& o,const tuple<T1,T2>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T1,typename T2,typename T3>
ostream& operator<<(ostream& o,const tuple<T1,T2,T3>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";
}

template<typename T,const size_t S>
ostream& operator<<(ostream& o,const array<T,S>& arr){
	for(int i=(o<<"[",0);i<S;++i)o<<arr[i]<<(i+1<S?",":"");
	return o<<"]\n";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	for(int i=(o<<"[",0);i<vec.size();++i)o<<vec[i]<<(i+1<vec.size()?",":"");
	return o<<"]\n";
}

constexpr int M = 1e6+5, mod = 998244353;// 1e9+7;
constexpr double pi = acos(-1), eps = 1e-9;

int stk[M],top;
int ls[M],rs[M];
ll fac[M],ifac[M];

ll qpow(ll x,ll y){
	ll res=1;
	for(;y;y>>=1){
		if(y&1)(res*=x)%=mod;
		(x*=x)%=mod;
	}
	return res;
}

ll inv(ll x){
	return qpow(x,mod-2);
}

void init(){
	fac[0]=ifac[0]=1;
	for(int i=1;i<M;++i){
		fac[i]=fac[i-1]*i%mod;
		ifac[i]=inv(fac[i]);
	}
}

ll C(int n,int k){
	return fac[n]*ifac[k]%mod*ifac[n-k]%mod;
}

void solve(){
	int n;
	cin>>n;
	vector<int> p(n);
	for(auto& i:p)cin>>i;
	top=-1;
	for(int i=0;i<n;++i)ls[i]=rs[i]=-1;
	// stk 维护笛卡尔树中节点对应到序列中的下标
	for (int i = 0; i < n; i++) {
		int k = top;  // top 表示操作前的栈顶，k 表示当前栈顶
		while (k >= 0 && p[stk[k]] > p[i]) k--;  // 维护右链上的节点
		if (~k) rs[stk[k]] = i;  // 栈顶元素.右儿子 := 当前元素
		if (k < top) ls[i] = stk[k + 1];  // 当前元素.左儿子 := 上一个被弹出的元素
		stk[++k] = i;                     // 当前元素入栈
		top = k;
	}
//	for(int i=0;i<n;++i)cout<<tie(ls[i],rs[i])<<" ";cout<<"\n";
	ll ans=1;
	auto dfs=[&](auto&& dfs,int cur,int l,int r,int dep){
		if(cur==-1)return;
		int cnt=r-l+1;
		(ans+=C(cnt+dep-1,dep))%=mod;
		dfs(dfs,ls[cur],l,cur-1,dep+1),dfs(dfs,rs[cur],cur+1,r,dep+1);
	};
	int cur=ranges::min_element(p)-p.begin();
	dfs(dfs,cur,0,n-1,1);
	cout<<ans<<"\n";
	
	return;
}

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

B Date

找合法日期子序列个数。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T1,typename T2>
ostream& operator<<(ostream& o,const tuple<T1,T2>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T1,typename T2,typename T3>
ostream& operator<<(ostream& o,const tuple<T1,T2,T3>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";
}

template<typename T,const size_t S>
ostream& operator<<(ostream& o,const array<T,S>& arr){
	for(int i=(o<<"[",0);i<S;++i)o<<arr[i]<<(i+1<S?",":"");
	return o<<"]\n";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	for(int i=(o<<"[",0);i<vec.size();++i)o<<vec[i]<<(i+1<vec.size()?",":"");
	return o<<"]\n";
}

constexpr int M = 1e5+5, mod = 998244353;// 1e9+7;
constexpr double pi = acos(-1), eps = 1e-9;

ll y[M][2];
ll dp0[2][4],dp1[4][4];
ll dd[2][32],mm[2][13];
int dim[]{-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
ll ans;

void solve(){
	int n;
	string s;
	cin>>n>>s;
	for(int z=0,i=0;i<n;++i){
		int t=s[i]-'0';
		if(!t){
			++z;
			(dp0[1][0]+=dp0[0][0])%=mod;
			(dp0[1][1]+=dp0[0][1])%=mod;
			for(int j=0;j<4;++j){
				(dp0[0][j!=0]+=dp1[1][j])%=mod;
			}
		}
		for(int j=0;j<4;++j){
			(dp1[3][(j*10+t)%4!=0]+=dp1[2][j])%=mod;
		}
		for(int j=0;j<4;++j){
			(dp1[2][(j*10+t)%4]+=dp1[1][j])%=mod;
		}
		for(int j=0;j<4;++j){
			(dp1[1][(j*10+t)%4]+=dp1[0][j])%=mod;
		}
		dp1[0][t%4]++;
		ll y0000=i128(1)*z*(z-1)/2*(z-2)/3*(z-3)/4%mod;
		y[i][0]=(dp1[3][0]-dp0[1][1]+mod-y0000+mod)%mod;
		y[i][1]=(dp1[3][1]+dp0[1][1])%mod;
//		cout<<tie(y[i][0],y[i][1])<<" ";
	}
	auto check=[&](int x){return 1<=x&&x<=31;};
	for(int i=n-1;i>2;--i){
		(y[i-1][0]+=mod-y[i-2][0])%=mod;
		(y[i-1][1]+=mod-y[i-2][1])%=mod;
		int t=s[i]-'0';
		if(t==0){
			for(int j=0;j<=9;++j){
				(mm[1][j]+=mm[0][j])%=mod;
			}
		}
		if(t==1){
			for(auto j:{10,11,12}){
				(mm[1][j]+=mm[0][j])%=mod;
			}
		}
		if(1<=t&&t<=9){
			for(int j=1;j<=dim[t];++j){
				(mm[0][t]+=dd[1][j])%=mod;
			}
		}
		if(t<=2){
			for(int j=1;j<=dim[t+10];++j){
				(mm[0][t+10]+=dd[1][j])%=mod;
			}
		}
		if(t==2){
			(mm[0][0]+=dd[1][29])%=mod;
		}
		for(int j=0;j<=9;++j){
			if(!check(t*10+j))continue;
			(dd[1][t*10+j]+=dd[0][j])%=mod;
		}
		dd[0][t]++;
		ll tot=0;
		for(int j=1;j<=12;++j){
			(tot+=mm[1][j])%=mod;
		}
		(ans+=tot*(y[i-1][0]+y[i-1][1])%mod+mm[1][0]*y[i-1][0]%mod)%=mod;
//		cout<<ans<<"\n";
	}
	cout<<ans<<"\n";
	
	return;
}

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

A AVL tree

注意到树高为h的AVL树，其子树树高均为h-1或一个h-1一个h-2。定义$f[u][h]$为以u为根，变为树高为h的AVL树需要操作的次数。预处理从零建树需要的操作数，按照三种情况转移即可。

/*

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

*/
#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 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

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

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

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 = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<array<int, 30>> f(n + 1);
    vector<int> ls(n + 1), rs(n + 1), sz(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> ls[i] >> rs[i];
    }
    f[0][1] = 1;
    for (int i = 2; i < 30; ++i) {
        f[0][i] = 1 + f[0][i - 1] + f[0][i - 2];
    }
    for (int i = 1; i <= n; ++i) {
        ranges::fill(f[i], inf);
    }
    auto dfs = [&](auto&& dfs, int u) -> void {
        if (!u) return;
        dfs(dfs, ls[u]);
        dfs(dfs, rs[u]);
        sz[u] = sz[ls[u]] + sz[rs[u]] + 1;
        f[u][0] = sz[u], f[u][1] = sz[u] - 1;
        for (int i = 2; i < 30; ++i) {
            f[u][i] = min({f[ls[u]][i - 1] + f[rs[u]][i - 1], f[ls[u]][i - 2] + f[rs[u]][i - 1], f[ls[u]][i - 1] + f[rs[u]][i - 2]});
        }
    };
    dfs(dfs, 1);
    cout << ranges::min(f[1]) << "\n";
}

signed main() {
    
    FIO;
    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

*/