ABC205

C

题意：给你a, b, c, 判断\(a^c\) 和 \(b^c\)谁大\(?10^9≤A,B≤10^9,1≤C≤10^9\)

方法：如果c为奇数直接判断ab大小，否则判断绝对值的大小

#include
#include
#include

using namespace std;

void out(int x, int y){
    if(x > y) cout << ">";
    if(x < y) cout << "<";
    if(x == y) cout << "=";
}

signed main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(c & 1) out(a, b);
    else out(abs(a), abs(b));
}

D

题意：给你一个长为N的升序序列A，Q个询问，每次给一个k，问第k小的不包含在A中的整数，假设A为\(4,5,6,8,10\)，如果k为3，答案就是3，因为3是不包含在A中第3小的数字

方法：对于A（下标从1开始，另外在最开头加一个a0 = 0）中的一个元素ai，ai - i表示不包含a1~ai时，ai左侧的从1开始的数字个数，然后二分找最大的满足ai - i小于k的位置idx，答案 = \(k - (a[idx] - idx) + a[idx] = k + idx\)

#include
using namespace std;

const int N = 1e5 + 10;

#define int long long

int n, q;
int a[N], idx[N];

int find(int x){
    int l = 0, r = n;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(a[mid] - mid < x) l = mid;
        else r = mid - 1;
    }
    return l;
}

signed main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    
    while(q --){
        int k;
        cin >> k;
        int idx = find(k);
        cout << k + idx << endl;
    }
}