Solution to the fourth "intelligence Cup" National College Students' IT skills competition (group B of the final)

T229470 A. Xiao Zhi's doubts

call string Of substr Method , Violence is enough .

#include<bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
signed main(){
    
    string s;
    cin>>s;
    int n=s.size();
    int ans=0;
    for(int i=0;i<n-7;i++){
    
        // if(s[i]=='c'&&s[i+1]=='h'&&s[i+2]=='u'&&s[i+3]&&s[i+4])
        string t=s.substr(i,8);
        if(t=="chuanzhi") ans++;
    }
    cout<<ans<<endl;
    return 0;
}

T229471 B. A triple

Triple cycle violence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N];
void solve(){
    
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
    
        cin>>a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
    
        for(int j=i;j<n;j++){
    
            for(int k=j;k<n;k++){
    
                if(a[i]+a[j]==a[k]) ans++;
            }
        }
    }
    cout<<ans<<endl;
}
signed main(){
    
    int _;
    cin>>_;
    while(_--) solve();
    return 0;
}

T229472 C. Line up

As long as another array has the number of that array , In exchange for $n^2$ Once, you can , Line up as you want , Bubbling .

But I misunderstood this question , I changed b Array . The title means to change a Array ,wa3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N], b[N], c[N], d[N];
void solve() {
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
    
        cin >> a[i];
        c[i]=a[i];
    }
    for (int j = 0; j < n; j++) {
    
        cin >> b[j];
        d[j]=b[j];
    }
    sort(c,c+n);
    sort(d,d+n);
    for(int i=0;i<n;i++){
    
        if(c[i]!=d[i]){
    
            cout<<"NO"<<endl;
            return;
        }
    }
    vector<int> ans;
    vector<int> res;
    for (int i = 0; i < n; i++) {
    
        if (a[i] == b[i])
            continue;
        int pos = -1;
        for (int j = i + 1; j < n; j++) {
    
            if (a[j] == b[i]) {
    
                pos = j;
            }
        }
        for (int j = pos; j > i; j--) {
    
            ans.push_back(j+1);
            res.push_back(j);
            swap(a[j], a[j - 1]);
        }
    }
    cout << "YES" << endl;
    for (int i = 0; i < ans.size(); i++) {
    
        cout << ans[i] << " " << res[i] << endl;
    }
    cout << "0 0\n";
}
signed main() {
    
    int _;
    cin >> _;
    while (_--)
        solve();
    return 0;
}

R71214110 Memorizing words

Two points answer m,check Words , Let's start with the first few , Judge how many days he will recite , and k Comparison .

leetcode The original title is ,leetcode410https://leetcode-cn.com/problems/split-array-largest-sum/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N];

bool check(vector<int> &nums, int x, int m) {
    
    long long sum = 0;
    int cnt = 1;
    for (int i = 0; i < nums.size(); i++) {
    
        if (sum + nums[i] > x) {
    
            cnt++;
            sum = nums[i];
        } else {
    
            sum += nums[i];
        }
    }
    return cnt <= m;
}

int work(vector<int> &nums, int m) {
    
    long long left = 0, right = 0;
    for (int i = 0; i < nums.size(); i++) {
    
        right += nums[i];
        if (left < nums[i]) {
    
            left = nums[i];
        }
    }
    while (left < right) {
    
        long long mid = (left + right) >> 1;
        if (check(nums, mid, m)) {
    
            right = mid;
        } else {
    
            left = mid + 1;
        }
    }
    return left;
}
void solve() {
    
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
    
        cin >> nums[i];
        nums[i] *= nums[i];
    }

    cout<<work(nums,k)<<endl;

}
signed main() {
    
        solve();
    return 0;
}

T229475 F1. Living in a tree （easy version）

According to the nature of the xor ,a To b XOR of a To c Exclusive or of . This middle point can be taken at will , So let's take a root node . If there is xor[u] ^ xor[v]== k.

Treelike DFS.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define int unsigned long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
vector<pair<int, int> > g[N];

int xorr[N];

void dfs(int u, int f, int val) {
    
    xorr[u] = val;
    for (int i = 0; i < g[u].size(); i++) {
    
        int next = g[u][i].first, w = g[u][i].second;
        if (next == f)
            continue;
        dfs(next, u, w ^ val);
    }
}

void solve() {
    
    int n, m, u, v, w, k;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
    
        cin >> u >> v >> w;
        g[u].push_back({
    v, w});
        g[v].push_back({
    u, w});
    }
    dfs(n-1, 0, 0);
    while (m--) {
    
        cin >> u >> v >> k;
        if ((xorr[u] ^ xorr[v]) == k) {
    
            cout << "YES\n";
        } else {
    
            cout << "NO\n";
        }
    }
}
signed main() {
    
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}