2020牛客寒假算法基础集训营4

A

找规律即可发现,取n次gcd ,最小的结果即是给a + kb

例如

0 ---- (1,0)

1 ---- (2,1)

2 ---- (3,2)

3 ---- (5,3)

#include<bits/stdc++.h>
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int mod = 1e9 + 7;

ll a[100] = {1,3,5};


int main(int argc, char *argv[]) {
    SIS;
    int t;
    int n;
    cin >> t;
    for(int i = 3; i <= 100; i++){
        a[i] = a[i - 1] + a[i - 2];
    }
    
    while(t--){
        cin >> n;
        cout << a[n] << endl;
    }   
    return 0;
}

B

#include<bits/stdc++.h>
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int mod = 1e9 + 7;



int main(int argc, char *argv[]) {
    SIS;
    string s;
    stack<int> stk;
    cin >> s;
    if(s.size() < 1){
        cout << "Yes" << endl;
        return 0;
    }
    int vis = 0;
    for(int i = 0;i < s.size(); i++){
        if(s[i] == '(' || s[i] == '{' || s[i] == '['){
            stk.push(i);
        }
        else {
            if(!stk.empty()){
                char ch = s[stk.top()];
            if(ch == '(' && s[i] == ')')stk.pop();
            else if(ch == '{' && s[i] == '}') stk.pop();
            else if(ch == '[' && s[i] == ']') stk.pop();
            }else{
                vis = -1;
            }
        }
    }
    //cout << stk.size();
    if(stk.size() < 1 && vis != -1)cout << "Yes" << endl;
    else if(stk.size() >= 1 || vis == -1)cout << "No" << endl;


    
    
    return 0;
}

C

#include<bits/stdc++.h>
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
//const int mod = 1e9 + 7;
const int modd = 998244353;
const int maxn = 800010;
ll a[maxn];

struct node{
    ll l,r,v;
    node() {l = r = v = 0;}
}tree[maxn];


void update(ll ind){
    tree[ind].v = (tree[ind * 2].v  % modd * tree[ind * 2 + 1].v % modd);
    return ;
}



void build(ll ind, ll l, ll r){
    tree[ind].l = l;
    tree[ind].r = r;
    if(l == r){tree[ind].v = a[l]; return ;}
    ll mid = (l + r) / 2;
    build(ind * 2,l ,mid );
    build(ind * 2 + 1,mid + 1, r);
    update(ind);
}

ll query(ll ind, ll l, ll r){
    if(tree[ind].l == l &&  tree[ind].r == r) return tree[ind].v;
    ll mid = (tree[ind].l + tree[ind].r) / 2;
    if(r <= mid)return query(ind * 2, l , r) % modd;
    if(l > mid) return query(ind * 2 + 1, l, r) % modd;
    return query(ind * 2,l,mid) % modd * query(ind * 2 + 1, mid + 1, r) % modd;
}

ll maxx = 0;
int main(int argc, char *argv[]) {
    SIS;
    ll n;
    ll k;
    cin >> n >> k;
    for(ll i = 1;i <= n;i++){
        cin >> a[i];
    }
    build(1,1,n);
    for(ll i = 1;i <= n + 1 - k; i++){
        ll s = query(1,i,i - 1 + k) % modd;
        maxx = max(s, maxx);
    }
    cout << maxx;
    
    
    return 0;
}

D

记录前缀异或和,如果有xorsum[r] ^ xorsum[l + 1] == 0那么即有 xorsum[l + 1] == xorsum[r];

由于题目所说,只要起点与终点其一不同,就代表一段,那么我们使用map记录前缀异或和出现的次数,注意一开始mp[0] = 1.如果如果出现相同的异或和代表一段

#include<bits/stdc++.h>
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int mod = 1e9 + 7;


int a[1000005];
int main(int argc, char *argv[]) {
    SIS;
    int n;
    ll ans = 0;
    map<int,int> mp;
    ll cs = 0;
    cin >> n;
    mp[0] = 1;
    for(int i = 1;i <= n; i++){
        cin >> a[i];
        cs ^= a[i];
        ans += mp[cs];
        mp[cs] += 1;    
    }
    cout << ans << endl;    
    return 0;
}

E

我们记录有有几个加号,可以知道需要组成多少个整数

并且,我们统计每个数字有多少个

因为贪心原则,我们将从个位---十位----百位开始安排每一个整数里面具体的数字

假设最大的数字为‘9’,那么每个整数的个位一定是使用最大的‘9’ ,而后我们又知道需要取几个整数,安排几个数字,所以我们可先将最大位的数字加起来

例如23984692+238752+2+34+

答案为2369+2359+248+248+237=5461

我们可根据竖式计算得到结果

我们发现5个数字的个位都是最大的,然后呈现单调递减.如此安排才能局部最小.而后我们将其加起来存入数组,41 22 12 4 大整数加法

sum[i + 1] = sum[i] / 10; //十位得到 进位数

sum[i] %= 10; // 个位剩余树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int cnt[20];
int sum[500050];
 
char s[500050];
int main() {
    cin>>s;
    int ccnt = 1;
    int n = strlen(s);
    for(int i=0;i<n;i++){
        if(isdigit(s[i])){
            cnt[s[i]-'0']+=1;
        }else{
            ccnt+=1;
        }
    }
    int p = 0,cp = 0;
    for(int i=10;i>=1;i--){
        while(cnt[i]){
            sum[cp]+=i;
            cnt[i]-=1;
            p = (p+1)%ccnt;
            if(p == 0)cp+=1;
        }
    }
    for(int i=0;i<500010;i++){
        sum[i+1]+=sum[i]/10;
        sum[i]%=10;
    }
    int opt = 0;
    for(int i=500010;i>=0;i--){
        if(opt || sum[i]){
            cout<<sum[i];
            opt = 1;
        }
    }
    cout<<endl;
    return 0;
}

I

#include<bits/stdc++.h>
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 300030;

struct P{
    int a,b,c;
    bool operator <(const P &rhs)const{
        if(a == rhs.a) return c > rhs.c;
        return a < rhs.a;
    }
}alp[maxn];


int main(int argc, char *argv[]) {
    SIS;
    int n;
    cin >> n;
    for(int i=0;i<n;i++) cin>>alp[i].a>>alp[i].b>>alp[i].c;
    sort(alp, alp + n);
    multiset<int> pool;
    multiset<int> :: iterator it;
    int ans = 0;
    for(int i = 0;i < n;i++){
        if(alp[i].c){
            it = pool.lower_bound(alp[i].b);
            if(it != pool.begin()){
                --it;
                pool.erase(it);
                ans += 1;
            }
        }else{
            pool.insert(alp[i].b);
        }
    }
    cout << ans << endl;
    return 0;
}