携程4.15笔试

T1 签到题

#include <iostream>
#include <bits/stdc++.h>
using namespace std;


int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> v(n, vector<char> (m));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) 
            cin >> v[i][j];
    int res = 0;
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < m; j++) {
            if((v[i-1][j-1] == 'y' || v[i-1][j] == 'y' || v[i][j-1] == 'y' || v[i][j] == 'y'))
                if((v[i-1][j-1] == 'o' || v[i-1][j] == 'o' || v[i][j-1] == 'o' || v[i][j] == 'o'))
                    if((v[i-1][j-1] == 'u' || v[i-1][j] == 'u' || v[i][j-1] == 'u' || v[i][j] == 'u'))
                        res++;

        }
    }
    cout << res << endl;
}

T2 发现了128位整型数

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

__uint128_t gcd(__uint128_t a, __uint128_t b) {
    while(b != 0) {
        __uint128_t tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        uint64_t t;
        cin >> t;
        __uint128_t n = t;
        
        __uint128_t max_ = 0, a = 1, b = n - 1;
        for(__uint128_t i = n / 2; i >= 1; i--) {
            if(i * (n - i) < max_) break;
            __uint128_t tmp = i / gcd(i, n - i) * (n - i);
            if(tmp > max_) {
                max_ = tmp;
                a = i;
                b = n - i;
            }
        }
        uint64_t c = a, d = b;
        cout << c << ' ' << d << endl;
    }
}

T3 dfs暴力

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

uint64_t s2i(string s) {
    uint64_t r = 0;
    for(auto& p : s) {
        r = r * 2;
        if(p == '1')  r++;
    }
    return r;
}

uint64_t res = 0;

void dfs(vector<vector<int>>& v, vector<vector<int>>& vis, int now, int head, uint64_t val, uint64_t l, uint64_t r, string& s, int n) {
    if(val >= l && val <= r && now != head) res++;
    if(val > r) return;
    for(int i = 1; i <= n; i++) {
        if(v[now][i] == 1 && !vis[head][i]) {
            uint64_t tmp = val * 2;
            if(s[i-1] == '1') tmp++;
            vis[head][i] = 1;
            v[now][i] = 0;
            v[i][now] = 0;
            dfs(v, vis, i, head, tmp, l, r, s, n);
            // vis[head][i] = 0;
            v[now][i] = 1;
            v[i][now] = 1;
        }
    }
}


int main() {
    int n;
    uint64_t l, r;
    cin >> n >> l >> r;
    vector<vector<int>> v(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> vis(n + 1, vector<int>(n + 1, 0));
    string s;
    cin >> s;
    int a, b;
    for(int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        v[a][b] = 1;
        v[b][a] = 1;
    }
    for(int i = 1; i <= n; i++){
        uint64_t val = 0;
        if(s[i-1] == '1') val++;
            dfs(v, vis, i, i, val, l, r, s, n);
    }
    cout << res << endl;
       
}

T4 中心扩散

#include <iostream>
#include <bits/stdc++.h>
using namespace std;


int main() {
    uint64_t mod = 1000000007;
    int n;
    cin >> n;
    vector<uint64_t> v(n);
    uint64_t res = 0;
    for(int i = 0; i < n; i++) cin >> v[i];
    for(int i = 0; i < n; i++) {
        uint64_t tmp;
        if(v[i] % 2 == 0) tmp = v[i] / 2 * (v[i] + 1);
        else tmp = (v[i] + 1) / 2 * v[i];
        res = (res + tmp) % mod;
        int l = i - 1, r = i + 1;
        while(l >= 0 && r < n) {
            if(v[l] == v[r]) {
                res = (res + v[l]) % mod;
                l--;
                r++;
            }
            else {
                res = (res + min(v[l], v[r])) % mod;
                break;
            }
        }
    }
    cout << res << endl;
}