牛客2025秋季算法编程训练联赛4-基础组

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

1
0

1

gcd(1,0) 由于 b=0，不会递归，即是递归0次。

1
1

3

gcd(2,1)会递归一次至gcd(1,0)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans=INT_MAX;
pair<int,int>a[100];
signed main(){
	int t,n;
	cin>>t;
	while(t--){
		cin>>n;
		a[0].first=1,a[0].second=0;
		a[1].first=2,a[1].second=1;
		for(int i=2;i<=100;i++){
			a[i].first=a[i-1].first+a[i-1].second;
			a[i].second=a[i-1].first;
		}
		cout<<a[n].first+a[n].second<<endl;
	}
	//gcd(a,b);
} 

一行一个字符串S，只包含题目中的六种括号字符

输出为一行"Yes" 或"No"

(){}[]

Yes

({[]})

Yes

([)]

No

1≤∣S∣≤1000000

#include<bits/stdc++.h>
using namespace std;
string s;
stack<char>stk;
bool f(){
	for(char c:s){
		if(c=='('||c=='{'||c=='['){
			stk.push(c);
		}
		else{
			if(stk.empty()){
				return false;
			}
			else{
				char top=stk.top();
				if((c==')'&&top=='(')||
				   (c=='}'&&top=='{')||
				   (c==']'&&top=='[')){
				   	stk.pop();
				}
				else{
					return false;
				}
			}
		}
	}
	return stk.empty();
}
int main(){
	getline(cin, s);
	if(f()){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
	
}

第一行两个整数n,k。
第二行n个整数,a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​。

输出一个整数，代表最大余数。

5 3
1 2 3 0 8

6

1∗2∗3mod  998244353=61*2*3\mod 998244353=61∗2∗3mod998244353=6

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int a[200030];
int power(int b,int n) {
    int ans=1;
    while(n>0) {
        if((n&1)==1) {
            ans=(ans*b)%mod;
        }
        b=(b*b)%mod;
        n>>=1;
    }
    return ans;
}
signed main() {
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    if(k==0){
        cout<<1<<endl;
        return 0;
    }
    int ans=1;
    int zero_count=0;
    for(int i=1;i<=k;i++) {
        if(a[i]==0)zero_count++;
        else ans=(ans*a[i])%mod;
    }
    int res=(zero_count==0)?ans:0;
    for(int i=k+1;i<=n;i++){
        if(a[i-k]==0) zero_count--;
        else{
            ans=(ans*power(a[i-k],mod-2))%mod;
        }
        if(a[i]==0) zero_count++;
        else ans=(ans*a[i])%mod;
        if(zero_count==0){
            res=max(res,ans);
        }else{ 
            res=max(res,0LL);
        }
    }
    cout <<res%mod<<endl;
    return 0;
}

输出一个整数，代表答案。

5
1 2 3 2 1

2

子段 [1,3] 和子段 [3,5] 是合法子段。

n≤200000,0≤ai​≤2^30−1

#include<bits/stdc++.h>
using namespace std;
long long prefix;
int a[200020];
int main(){
    int n;
    cin>>n;
    unordered_map<long long ,long long>mp;
    mp[0]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        prefix^=a[i];
        mp[prefix]++;
    }
    long long ans=0;
    for(auto &p : mp){
        long long c=p.second;
        ans+=c*(c-1)/2;
    }
    cout<<ans;
    
    
}

一行输出一个数字，代表最小的解。

111+1

22

11+11=22

9998765432111

1112345678999

12+35

38

23984692+238752+2+34+

5461

注意，答案长度可能长达500000个字符。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
int res[MAXN];
int main() {
    string s;
    cin>>s;
    vector<char>digits;
    int k=0;
    for(char c:s) {
        if(c=='+'){
            k++;
        }
		else{
            digits.push_back(c);
        }
    }
    sort(digits.begin(),digits.end());
    int n=digits.size();
    int m=k+1;
    int len=n/m;
    int r=n%m;
    int start=0;
    if(r>0){//有r组数需要多一位数 
        int S1=0;
        for(int i=0;i<r;i++){
            S1+=digits[start++]-'0';
        }
        res[len]+=S1;//所以从len开始 
    }
    for(int j=len-1;j>=0;j--){
        int S=0;
        for(int i=0;i<m;i++) {//先把最小的数给最高位，所以从len-1开始 
            S+=digits[start++]-'0';
        }
        res[j]+=S;
    }
    int L=len+10;//防止进位时候越界 
    for (int i=0;i<L-1;i++) {
        if(res[i]>=10){
            res[i+1]+=res[i]/10;
            res[i]%=10;
        }
    }
    int high=L-1;
    while(high>0&&res[high]==0){
        high--;
    }
    for(int i=high;i>=0;i--){
        cout<<res[i];
    }
    cout<<endl;
    return 0;
}