A. Air Conditioner

根据题意输出结果。

#include <bits/stdc++.h>
using namespace std;
#define MAX 300005
int main() {
    int X;
    cin>>X;
    X >= 30 ? cout<<"Yes" : cout<<"No";
}

 

B. Distance

输出距离在D以下的点的个数

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAX 300005
int main() {
    LL n, d;
    cin>>n>>d;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        LL x, y;
        scanf("%lld%lld", &x,&y);
        if(x * x + y * y <= d * d)ans++;
    }
    cout<<ans;
}

 

C. Respect

输出由数字7组成的数7777...中，能被K整除的最小的数。

根据递推式 寻找循环节。循环节长度不超过K。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAX 300005
const int maxk = 1e6+5;
bool a[maxk];
int main() {
    LL k;
    cin>>k;
 
    int x = 7;
    int ans = -1;
    int c = 1;
    while(!a[x % k]){
        if(x % k == 0){
            ans = c;
            break;
        }
        a[x % k] = 1;
        c++;
        x = x * 10 + 7;
        x %= k;
    }
 
    cout<<ans<<endl;
 
}

D. Alter Alter

通过交换、修改将一个WR组成的序列修改为不含WR子串的序列。

所有R必须位于W左侧。统计不满足条件字符的个数即可。这里不需要修改操作。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAX 300005
const int maxk = 1e6+5;
int main() {
    LL n;
    cin>>n;
    string s;
    cin>>s;
 
    int cntR = 0;
    for (int i = 0; i < n; ++i) {
        if(s[i] == 'R')cntR++;
    }
 
 
    int rev = 0;
    for (int j = 0; j < n; ++j) {
        if(j < cntR){
            if(s[j] == 'W')rev++;
        }
        else if(s[j] == 'R') rev++;
    }
 
    cout<<(rev)/2<<endl;
}

E. Logs

将N个木棍进行K次切分，求最长长度向上取整的最小值。

二分查找可行解。如果每个木棍的需要的切分次数之和小于K则可行。

要注意一下二分时中值为0的情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAX 300005
const int maxn = 2e5+10;
int a[maxn];
int main() {
    LL n, k;
    cin>>n>>k;
 
    int cntR = 0;
    int ma = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", a+i);
        ma = max(ma, a[i]);
    }
    LL l = 0, r = ma;
    while(l < r){
        int p =  0;
        int m = (l + r + 1) / 2;
        if(m == 0) {
            break;
        }
        else for (int i = 0; i < n; ++i) {
            p += (a[i] + m - 1)/ m;
        }
        if(p > d) l = m;
        else r = m - 1;
    }
    if(r == 0){
        cout<<1;
        return 0;
    }
    int p =  0;
    for (int i = 0; i < n; ++i) {
        p += (a[i] + r - 1)/ r;
    }
    if(p > d)cout<<r+1<<endl;
    else cout<<r<<endl;
}

F. Range Set Query

给定一组数，询问[l, r]区间内不同数的个数

树状数组查询[0,r]、[0,l]区间内的种类的个数。为了防止[0,r)中多计算而[l, r]区间漏计，只将r之前数字的最后一次出现视为唯一出现，倒数第二次出现之前的种类数-1。离线查询得到答案。

#include <bits/stdc++.h>
 
using namespace std;
const int N = 500020;
int n, q, c[N], ans[N], tree[N << 1], last[N], h[N << 1];
struct node {
    int l, r, num;
} qq[N];
 
bool cmp(node x, node y) { return x.r < y.r || (x.r == y.r && x.l < y.l); }
 
void insert(int x, int y) { for (; x <= n; x += x & -x) tree[x] += y; }
 
int query(int x) {
    int y = 0;
    for (; x; x -= x & -x) y += tree[x];
    return y;
}
 
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
        last[i] = h[c[i]];
        h[c[i]] = i;
    }
 
    for (int i = 0; i < q; i++) {
        scanf("%d%d", &qq[i].l, &qq[i].r), qq[i].num = i;
    }
    sort(qq, qq + q, cmp);
    int tmp = 0;
    for (int i = 0; i < q; i++) {
        while (tmp < qq[i].r) {
            tmp++;
            if (last[tmp]) insert(last[tmp], -1);
            insert(tmp, 1);
        }
        ans[qq[i].num] = query(tmp) - query(qq[i].l - 1);
    }
    for (int i = 0; i < q; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}