第 9 场 小白入门赛 — 蓝桥杯

比赛地址

第 9 场 小白入门赛 - 蓝桥云课

1 . 省赛总动员

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  cout << "No.1" << endl ;
  return 0;
}

2 . 盖印章

解方程即可，因为题目确定有解

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl 'n'
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;
inline void solve(){
	int n , m , k ; cin >> n >> m >> k ;
	LL f = n * m  ;
	LL cnt = 0 , a , b ;
	for(LL i=1;i<=f;i++){
		char c ; cin >> c ;
		if(c=='1') cnt ++ ;
	}
	a = cnt - 2 * k ;
	b = k - a ;
	cout << a << " " << b << endl ;
}
 
signed main()
{
    IOS
    int _ = 1;
    while(_ --) solve();
    return 0;
}

3 . 字符串迁移

先用差分+前缀和统计每个位置上需要移动的次数；

然后遍历，更改每个位置上的字符 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl 'n'
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;

using namespace std;

char get(char c,int k){
    return 'a' + ((c - 'a' + k) % 26 + 26) % 26;
}

inline void solve(){
	int n , q ; cin >> n >> q ;
	string s ; cin >> s ;
	vector<int> a(n + 2 , 0) ;
	while(q--){
		int l  , r , k ; cin >> l >> r >> k ;
        k%=26 ;
		a[l]=(a[l]+k)%26 ;
		a[r+1]=(a[r+1]-k)%26;
	}
	for(int i=1;i<=n;i++) a[i] = (a[i-1]+a[i]) % 26 ;
	for(int i=1;i<=n;i++){
		s[i-1] = get(s[i-1],a[i]) ;
	}
	cout << s << endl ;
}
 
signed main()
{
    IOS
    int _ = 1;
    while(_ --) solve();
    return 0;
}

4 . 字典树考试

这题考察位运算 ， 先统计32位，每个位置上1的个数，记在b数组中 ;

对于每个数位上1的个数x,产生贡献 : x*(x-1)/2;

遍历累加到答案即可 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl 'n'
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
using namespace std;

int a[N] ;
int b[32] ;

// 按位与 : 同1为1 

// 01
// 10
// 11

inline void solve() {
	int n ; cin >> n ;
	for(int i=1;i<=n;i++) cin >> a[i] ;
	LL ans = 0 ;
	for(int i=1;i<=n;i++){
		int x = a[i] ;
		for(int j=0;j<32;j++){
			if((x>>j)&1) b[j]++ ; 
		}
	}
	
	//  (n-1) ~ 1 : 1 + n-1 * (n-1)*n /2;
	for(int i=0;i<32;i++){
		int x = b[i] ;
		ans += 1LL * x * (x-1) / 2 ;
	}
	cout << ans << endl ;
}


signed main()
{
    IOS
    int _ = 1;
    while (_--) solve();
    return 0;
}

5 . 无理数位数查询

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define lowbit(i) ((i) & -(i))
#define ull unsigned long long
#define int long long
using namespace std;
const int mod = 1e9 + 7;
__int128 ksm(__int128 base, __int128 n)
{
    __int128 res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = (res * base);
        base = (base * base);
        n >>= 1;
    }
    return res;
}
void solve()
{
    int n, m;
    cin >> n >> m;
    int k = 0 , c = 0 , ki;
    for (int i = 1; true; i++)
    {
        __int128 b = ksm(m, i) - 1;
        b -= ksm(m, i - 1) - 1;
        __int128 e = b * i + k;
        if (e >= n)
        {
            ki = i;
            break;
        }
        k = e;
    }
    n -= k;
    int b = n / ki;
    c = n % ki;
    if (c == 0)
        c = ki, b--;
    int kk = ksm(m, ki - 1) - 1 + b + 1;
    vector<int> x;
    while (kk)
    {
        x.push_back(kk % m);
        kk /= m;
    }
    cout << x[x.size() - c] << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--)
    {
        solve();
    }
}

6 . 贝贝的集合

答案只有可能为1,2 ;

用优先队列模拟 ，每次取最小的两个 ， 相等，插入a+1,不相等直接输出2并返回 ;

#include <iostream>
#include <queue>
using namespace std;

int main(void) {
    int n ; cin>>n;
    priority_queue<int, vector<int>, greater<int> > que ; 
    for (int i=1; i<=n; i++){
        int x ; cin >> x ;
        que.push(x) ;
    }
    while (que.size() >= 2) {
        int t1 = que.top() ; que.pop() ;
        int t2 = que.top() ; que.pop() ;
        if (t1 != t2) {cout<<2<<'n';return 0;}
        que.push(t1+1);
    }
    cout<<1<<'n';
    return 0;
}