2021牛客寒假算法基础集训营2

C 牛牛与字符串border

#include <bits/stdc++.h>

//#pragma GCC optimize(2)
#define int long long
using namespace std;
//const int mod = 998244353;
typedef long long LL;
typedef long long ll;
const int inf = 1e18;
//const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int N = 1e5 + 10000;

int a[maxn];
int vis[maxn][26];
int mode[maxn];

void solve() {
    int n,l;
    cin>>n>>l;
    string s;
    cin>>s;
    int ll;
    if (l>n/2 ) ll=n-l;
    else {
        ll=__gcd(n,l);
    }
    for (int i = 0; i < ll; ++i) {
        for (int j = 0; j < 26; ++j) {
            vis[i][j]=0;
        }
        mode[i]=0;
    }
    for (int i = 0; i < n; ++i) {
        vis[i%ll][s[i]-'a']++;
        if (vis[i%ll][s[i]-'a']>vis[i%ll][mode[i%ll]])
            mode[i%ll]=s[i]-'a';
    }
    for (int i = 0; i < n; ++i) {
        printf("%c",mode[i%ll]+'a');
    }
    cout<<"\n";
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

D 牛牛与整除分块

#include <bits/stdc++.h>

#pragma GCC optimize(2)
#define int long long
using namespace std;
//const int mod = 998244353;
const int inf = 1e18;
const __int128 mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 4e6 + 10;

void solve() {
    int n,x;
    cin>>n>>x;
    int sq=sqrt(n);
    if (sq>=x){
        cout<<x;
    } else{
        int f=n/sq!=sq;
        cout<<sq*2+f-n/x;
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

E 牛牛与跷跷板

#include <bits/stdc++.h>

//#pragma GCC optimize(2)
#define int long long
using namespace std;
//const int mod = 998244353;
typedef long long LL;
typedef long long ll;
const int inf = 1e18;
//const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int N = 1e5 + 10000;

struct node{
    int l,r,id;
    node(int l=0,int r=0,int id=0){
        this->l=l;
        this->r=r;
        this->id=id;
    }
};
bool operator < (const node &a,const node &b){
    return a.l<b.l;
}
int n,m,dis[maxn],l,r,y;
vector<node>vec[maxn];
vector<int >g[maxn];
queue<int >q;

void solve() {
    cin>>n;
    for (int i = 1; i <=n; ++i) {
        cin>>y>>l>>r;
        vec[y].emplace_back(l,r,i);
    }
    for (int i = 0; i < maxn; ++i) {
        sort(vec[i].begin(),vec[i].end());
        for (int j = 1; j < vec[i].size(); ++j) {
            if (vec[i][j-1].r==vec[i][j].l){
                g[vec[i][j-1].id].push_back(vec[i][j].id);
                g[vec[i][j].id].push_back(vec[i][j-1].id);
            }
        }
    }
    for (int i = 0; i < maxn; ++i) {
        auto p1=vec[i].begin();
        auto p2=vec[i+1].begin();
        while (p1!=vec[i].end()&&p2!=vec[i+1].end()){
            if (max(p1->l,p2->l)<min(p1->r,p2->r)){
                g[p1->id].push_back(p2->id);
                g[p2->id].push_back(p1->id);
            }
            if (p1->r<=p2->r) p1++;
            else p2++;
        }
    }
    memset(dis,-1,sizeof(dis));
    dis[1]=0;
    q.push(1);
    while (!q.empty()){
        int now=q.front();
        q.pop();
        for(auto &i:g[now]){
            if (dis[i]==-1){
                dis[i]=dis[now]+1;
                q.push(i);
            }
        }
    }
    cout<<dis[n];
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

F 牛牛与交换排序

#include <bits/stdc++.h>

#pragma GCC optimize(2)
#define int long long
using namespace std;
//const int mod = 998244353;
const int inf = 1e10;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int N = 4e6 + 10;

int a[maxn];
int n;

int check(){
    int res=1;
    int l=1,f=1;
    for (int i = 1; i <=n; ++i) {
        if (a[i]==i&&f) l++;
        else f=0;
        if (f==0&&a[i]==l) {
            res=i-l+1;
        }
    }
    return res;
}

void solve() {
    cin>>n;
    for (int i = 1; i <=n; ++i) {
        cin>>a[i];
    }
    int f=1;
    int l=check();
    for (int i = 1; i <=n-l+1; ++i) {
        if (a[i]==i) continue;
        else{
            if (a[i+l-1]!=i){
                f=0;
                break;
            }
            int j=i;
            int k=i+l-1;
            while (j<k){
                swap(a[k],a[j]);
                j++,k--;
            }
        }
    }
    
    for (int i = 1; i <n; ++i) {
        //cout<<a[i];
        if (a[i]>a[i+1]) {
            f=0;
            break;
        }
    }
    cout<<(f?"yes":"no")<<"\n";
    if (f) cout<<l;
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

G 牛牛与比赛颁奖

#include <bits/stdc++.h>

//#pragma GCC optimize(2)
#define int long long
using namespace std;
//const int mod = 998244353;
typedef long long LL;
typedef long long ll;
const int inf = 1e18;
//const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 1e5 + 10000;

pair< int ,int > a[maxn];
int sum[maxn];
int top=0;
int jj,yy,tt,sc;

void solve() {
    int n,m;
    cin>>n>>m;
    int j=(n+9)/10;
    int y=(n+3)/4;
    int t=(n+1)/2;
    for (int i = 0; i < m; ++i) {
        int l,r;
        cin>>l>>r;
        a[top++]=make_pair(l,1);
        a[top++]=make_pair(r+1,-1);
    }
    sort(a,top+a);
    int now=0;
    for(int i=0;i<=top;i++){
        now+=a[i].second;
        if (i!=top&&a[i].first!=a[i+1].first){
            sum[now]+=a[i+1].first-a[i].first;
        }
    }
    for (int i = m; i; --i) {
        if (sc<j) jj=i;
        if (sc<y) yy=i;
        if (sc<t) tt=i;
        sc+=sum[i];
        sum[i]+=sum[i+1];
    }
    cout<<sum[jj]<<" "<<sum[yy]-sum[jj]<<" "<<sum[tt]-sum[yy];
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

H 牛牛与棋盘

#include <bits/stdc++.h>

#pragma GCC optimize(2)
#define int long long
using namespace std;
//const int mod = 998244353;
const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N=8e7+10000;

int a[maxn];

void solve() {
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((i+j)%2) {
                cout<<"1";
            } else cout<<"0";
        }
        cout<<"\n";
    }
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

I 牛牛的“质因数”

#include <bits/stdc++.h>

#pragma GCC optimize(2)
#define int long long
using namespace std;
//const int mod = 998244353;
const int inf = 1e18;
const __int128 mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 4e6 + 10;

string ss[N];
int prime[N];
int top = 0;
bool visit[N];

void Prime() {
    for (int i = 2; i <= N; i++) {
        if (!visit[i]) {
            prime[++top] = i;
            ss[i] = to_string(i);
        }
        for (int j = 1; j <= top && i * prime[j] <= N; j++) {
            visit[i * prime[j]] = 1;
            ss[i * prime[j]] = ss[prime[j]] + ss[i];
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

inline void write(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

void solve() {
    Prime();
    int n;
    cin >> n;
    __int128 sum = 0;
    for (int i = 2; i <= n; ++i) {
        __int128 x = 0;
        int l = ss[i].size();
        for (int j = 0; j < l; ++j)
            x = x * 10 + ss[i][j] - '0';
        //cout<<ss[i]<<" "<<x<<"\n";
        x %= mod;
        sum += x;
        sum %= mod;
    }
    write(sum);
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

J 牛牛想要成为hacker

#include <bits/stdc++.h>

#pragma GCC optimize(2)
#define int long long
using namespace std;
//const int mod = 998244353;
const int inf = 1e10;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int N = 4e6 + 10;

int a[maxn];
int n;

void solve() {
    int n;
    cin>>n;
    a[0]=0;
    a[1]=1;
    int dex=-1;
    for (int i = 2; i <=100; ++i) {
        a[i]=a[i-2]+a[i-1];
        if (a[i]>1e9){
            dex=i;
            break;
        }
    }
    for (int i = 1; i <=n; ++i) {
        if (i<dex-2||dex==-1){
            cout<<a[i+2];
        } else{
            cout<<1;
        }
        cout<<" ";
    }
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}