携程 4.12 笔试

Q1

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

int main() {
    int t; scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int n; scanf("%d", &n);
        if (n <= 3) {
            printf("-1\n");
        } else if (n % 2 == 0) {
            printf("%d %d\n",n, n);
        } else {
            printf("%d %d\n", n - 1, n + 1);
        }
    }
}
// 64 位输出请用 printf("%lld")

Q2

#include <algorithm>
#include <cstdio>
#include <iostream>
#define int long long
#define ll long long
using namespace std;
const int N = 2e5 + 10;
char s[N];
int a[N];
int w[N];
int c[N];
signed main() {
    int n; scanf("%lld", &n);
    scanf("%s", s);
    for (int i = 0; i < n - 1; i++) {
        scanf("%lld", &w[i]);
    }
    for (int i = 0; i < n; i++) {
        a[i] = s[i] - '0';
    }

    ll total = 0L;
    int len = 0;
    for (int i = 0; i < n; i++) {
        int j = i + 1;
        while (j < n && a[j] == a[i]) {
            j++;
        }
        j--;
        // [i, j] 

        if (j < n - 1) {
            // printf("%lld\n", w[j]);
            c[len++] = w[j];
        }

        // printf("%d %d\n", i, j);
        for (int k = i; k < j; k++) {
            total = total + w[k];
        }
        i = j;
    }
    sort(c, c + len);

    // for (int i = 0; i < len; i++) {
    //     printf("%lld ", c[i]);
    // }
    ll ans = total;

    if (len > 0) {
        ans += c[len - 1];
    }

    if (len > 1) {
        ans += c[len - 2];
    }

    printf("%lld\n", ans);
}
// 64 位输出请用 printf("%lld")

Q3

#include <iostream>
#include <algorithm>
#define left LLL
#define right RRR
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int x[N], left[N], right[N];
char s[N];

signed main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; i++) {
            scanf("%d", &x[i]);
        }
        scanf("%s", s);
        int leftNum = 0, rightNum = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                left[leftNum++] = x[i];
            } else {
                right[rightNum++] = x[i];
            }
        }
        sort(left, left + leftNum);
        sort(right, right + rightNum);

        ll ans = 0L;
        int posLeft = leftNum - 1;
        int r = rightNum - 1;

        while (r >= 0 && right[r] > left[posLeft]) {
            r--;
        }
        int l = r;

        while (posLeft >= 0) {

            while (r >= 0 && right[r] > left[posLeft]) {
                r--;
            }

            while ((left[posLeft] - right[l]) <= 2 * k && l >= 0) {
                l--;
            }
            ans += 1LL * (r - l);
            posLeft -= 1;
        }
        printf("%lld\n", ans);
    }
}
// 64 位输出请用 printf("%lld")

Q4

import java.util.Scanner;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static class Pair {
        int value;
        int count;
        Pair(int v, int c) {
            value = v;
            count = c;
        }
    }
    private static long power(long x, long n, long mod) {
        if (n == 0) return 1;
        if (n == 1) return x;
        long m = power(x, n / 2, mod);
        m = m * m % mod;
        if (n % 2 == 1) {
            m = m * x;
        }
        return m;
    } 
    public static void main(String[] args) {
        int mod = (int)(1e9 + 7);
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int times = 0; times < t; times++) {
            int n = in.nextInt(), m = in.nextInt();
            Queue<Pair> q = new ArrayDeque<Pair>();
            q.add(new Pair(n, 1));
            int res = 0;
            for (int i = 0; i < m; i++) {
                HashMap<Integer, Integer> map = new HashMap<>();
                // System.out.println("i = " + i);
                while (q.size() > 0) {
                    Pair e = q.poll();
                    map.put(e.value / 2 + 1, (map.getOrDefault(e.value / 2 + 1, 0) + 2 * e.count % mod) % mod);
                    if (e.value % 2 == 1) {
                        map.put(2, (map.getOrDefault(2, 0) + e.count) % mod);
                    }
                }
                boolean flag = true;
                for (HashMap.Entry<Integer, Integer> e: map.entrySet()) {
                    q.add(new Pair(e.getKey(), e.getValue()));
                    if (e.getKey() > 2) {
                        flag = false;
                    }
                }
                if (flag) {
                    res = m - 1 - i;
                    break;
                }
            }
            long ans = 0;
            while (q.size() > 0) {
                Pair e = q.poll();
                if (e.value == 1) {
                    long one = (res + 1) * power(2, res, mod) % mod;
                    ans = (ans + one * e.count % mod) % mod;
                } else if (e.value == 2) {
                    long one = power(2, res + 1, mod);
                    ans = (ans + one * e.count % mod) % mod;
                } else {
                    ans = (ans + e.value * e.count % mod) % mod;
                }
            }
            System.out.println(ans);
        }
    }
}