ABC207

B

题意：一个容器，一开始有A个青球，现在你可以进行一种操作：向容器里面放B个青球和C个红球，问是否能够通过t次操作使得青球的个数少于红球个数的D倍

方法：

n次操作后，箱子里有(A + nB)个青，(nC)个红球，要求((A + nB)/(nC) le D ightarrow A +nBle nDC ightarrow A le n(DC-B))

所以只需要判断(DC - B)是否大于0，如果(DC-B>0)那么一定存在一个n满足条件，否则一定不存在

#include<iostream>
using namespace std;

int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int t = c * d - b;
    if(t <= 0){
        cout << -1;
        return 0;
    }
    
    if(a / t * t == a) cout << a / t;
    else cout << a / t + 1;
}

C

题意：给你N个区间，类型包括([l, r], [l, r), (l, r], (l, r)), 找出所有有交集的区间i, j, 满足(1 le i < j le N)的个数

方法：按左端点排序，保存每个区间的位置，(O(n^2))

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct node{
    int l, r, t;
    
    bool operator<(const node &n){
        return l < n.l;
    }
};

vector<node> v;

int check(int i, int j){
    if(v[i].r != v[j].l) return v[i].r > v[j].l;
    if(v[j].t == 3 || v[j].t == 4) return 0;
    return v[i].t == 1 || v[i].t == 3;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++){
        int t, l, r;
        cin >> t >> l >> r;
        v.push_back({l, r, t});
    }
    
    sort(v.begin(), v.end());
    
    int res = 0;
    for(int i = 0; i < n; i ++)
        for(int j = i + 1; j < n; j ++)
            res += check(i, j);
    
    cout << res;
}

BONUS: N <= 1e5

方法：预处理所有区间，由于区间端点都是整数，所以对于开区间，可以+-0.5处理,这样处理不会使原本相交的区间不相交，原本不相交的区间相交，按左端点升序排序所有区间，遍历每一个区间i然后二分后面的最大的满足左端点 <= i的右端点的区间位置

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct node{
    double l, r;
    
    bool operator<(const node &n){
        return l < n.l;
    }
};

vector<node> v;
int n;

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

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++){
        double l, r;
        int t;
        cin >> t >> l >> r;
        if(t == 3 || t == 4) l += 0.5;
        if(t == 2 || t == 4) r -= 0.5;
        v.push_back({l, r});
    }
    
    sort(v.begin(), v.end());
    
    int res = 0;
    for(int i = 0; i < n; i ++){
        int j = find(v[i].r, i + 1, n - 1);
        if(j == -1) continue;
        res += j - i;
    }
    
    cout << res;
}

D

题意：两个点集S，T，判断能否通过旋转和平移使S，T一样

方法：求形心（重心），将两个集合均平移到源点，然后以s1去找T中的满足dist(s1) == dist(ti)的点，这个时候认为找到了T中可能的s1的对应点，求出s1应该旋转多少度到ti，然后将s中的所有点都旋转这个角度，看能不能和t匹配即可

注意：如果s1就是重心的话，那么平移后s1就是(0, 0), 如果实际上S和T可以匹配的话，这个时候由于s1在t中的对应点也为原点，此时旋转角为0，而实际上却需要旋转才可以匹配的话，这个时候会误判为No，所以出现这种情况，swap(s1, s2)就行

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

const int N = 110;

#define P pair<double, double>
#define x first
#define y second

vector<P> s, t;
int n;

void read(vector<P> &v){
    double sx = 0, sy = 0;
    for(int i = 0; i < n; i ++){
        double a, b;
        cin >> a >> b;
        v.push_back({a, b});
        sx += a, sy += b;
    }
    
    double gx = sx / n, gy = sy / n;
    for(auto &t : v){
        t.x -= gx;
        t.y -= gy;
    }
}

double dist(P &t){
    return t.x * t.x + t.y * t.y;
}

double angle(P &p1, P &p2){
    return atan2(p2.y, p2.x) - atan2(p1.y, p1.x);
}

int equal(double a, double b){
    return fabs(a - b) <= 1e-6;
}

P rotate(P &p, double a){
    double x = p.x * cos(a) - p.y * sin(a);
    double y = p.x * sin(a) + p.y * cos(a);
    return {x, y};
}

int main(){
    cin >> n;
    read(s), read(t);
    
    for(int i = 0; i < s.size(); i ++)
        if(s[i].x != 0.0 || s[i].y != 0.0){
            swap(s[0], s[i]);
            break;
        }
    
    for(auto i : t){
        double d2 = dist(i);
        if(equal(d2, dist(s[0]))){
            double a = angle(s[0], i); // 弧度
            int cnt = 0;
            for(auto j : s){
                P p = rotate(j, a);
                for(auto k : t)
                    if(equal(k.x, p.x) && equal(k.y, p.y))
                        cnt ++;
            }
            
            if(cnt == n){
                cout << "Yes";
                return 0;
            }
        }
    }
    
    cout << "No";
}