两日总结八

总结时间2022/7/30-8/1

比赛总结：这两天一共打了两场比赛

蔚蓝杯4：

 

其中只要是N题目，比赛的时候一直耗着，就是因为一个int128的使用，要使用快读快写，还有就是GCD里面也要修改。这一场没有报0了，主要就是死磕N题目去了，换了几种写法，分数加减都试了，然后公式也简化了，但是就是数据范围long long 差了那么一点，然后其他的题目没心情怎么去想，反正就是没有一点状态！！！就是下面这个题目：

#include <bits/stdc++.h>
using namespace std;
#define re  // register
#define ll __int128
#define OST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl "\n"
ll cnt[16], a[100005];
ll n;

inline int read() {
    re int t  = 0;
    re char v = getchar();
    while (v < '0') v = getchar();
    while (v >= '0') t = (t << 3) + (t << 1) + v - 48, v = getchar();
    return t;
}
inline __int128 gcd(__int128 x, __int128 y) { return y ? gcd(y, x % y) : x; }
inline void write(__int128 x) {
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
pair<ll, ll> add(pair<ll, ll> a, pair<ll, ll> b) {
    ll tmp  = a.second / gcd(a.second, b.second) * b.second;
    a.first = tmp / a.second * a.first;
    b.first = tmp / b.second * b.first;
    pair<ll, ll> res;
    res.first  = a.first + b.first;
    res.second = tmp;
    tmp        = gcd(res.first, res.second);
    res.first /= tmp;
    res.second /= tmp;
    return res;
}
int main() {
    OST;
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        for (int j = 0; j < 15; j++) {
            if (a[i] & (1 << j)) { cnt[j]++; }
        }
    }
    vector<ll> num;
    for (int i = 1; i <= n; i++) {
        ll tmp = 0;
        for (int j = 0; j < 15; j++) {
            if (cnt[j]) {
                cnt[j]--;
                tmp += (1 << j);
            }
        }
        num.push_back(tmp);
    }
    ll pingfenzi = 0, pingfenmu = n;
    for (int i = 0; i < n; i++) { pingfenzi += num[i]; }
    ll tmp;
    tmp = gcd(pingfenzi, pingfenmu);
    pingfenzi /= tmp;
    pingfenmu /= tmp;
    pair<ll, ll> b   = {-pingfenzi, pingfenmu};
    pair<ll, ll> ans = {0, 0};
    for (int i = 0; i < n; i++) {
        pair<ll, ll> c   = {num[i], 1};
        pair<ll, ll> res = add(c, b);
        res.first *= res.first;
        res.second *= res.second;
        res.second *= n;
        if (i == 0)
            ans = res;
        else
            ans = add(ans, res);
        //         cout << ans.first << " " << ans.second << endl;
    }
    tmp = gcd(ans.first, ans.second);
    ans.first /= tmp;
    ans.second /= tmp;
    write(ans.first);
    putchar('/');
    write(ans.second);
    return 0;
}

蔚蓝杯5：

 

这场没有什么说的，不算，其中要不是简单题目，要不就是洛谷上面的原题。唯一一点收获就是F题目吧，想法十分的简单，就是从上往下看能看到的多个圆的周长，洛谷题下落圆，这里就是要计算出一个圆被其他圆遮住的部分，而且不要算重复（这点就是比较难处理），可以用线段树，更好的方法就是用极角，计算得到被遮住的L_R两个范围，遍历其他所有圆更新这个范围。比他小的时就跳过，超过范围的就是更新更大的遮挡区间即可，最后排序用所有圆的周长减去这些遮住的即可。

#include <bits/stdc++.h>
using namespace std;
#define pair pair<double, double>
const int N      = 1e3 + 5;
const double eps = 1e-7;
double x[N], y[N], r[N];
const double PI = acos(-1);
int n;
double funPow(double tmp) { return (double) (tmp * tmp); }
double dist(double x1, double y1, double x2, double y2) { return sqrt(funPow(x2 - x1) + funPow(y2 - y1)); }
double reduce(double x) {
    x += PI * 2, x = x - (int) (x / (PI * 2)) * (PI * 2);
    return x;
}
int main() {
    while (cin >> n && n) {
        vector<pair> p;
        double res = 0.0;
        for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];
        for (int i = 1; i <= n; i++) {
            p.clear();
            for (int j = i + 1; j <= n; j++) {
                double d = dist(x[i], y[i], x[j], y[j]);
                if (d >= r[i] + r[j] - eps) continue;
                if (d <= fabs(r[i] - r[j]) + eps) {
                    if (r[j] > r[i]) { p.push_back({0, 2 * PI}); }
                    continue;
                }
                double tmp   = (d - (funPow(r[j]) - funPow(r[i])) / d) / 2;
                double jiao  = acos(tmp / r[i]);
                double zhong = reduce(atan2(x[i] - x[j], y[i] - y[j]) + PI / 2);
                double L = reduce(zhong - jiao), R = reduce(zhong + jiao);
                //                 cout << L << " " << zhong  <<  " " << R << endl;
                if (L - eps > R) {
                    p.push_back({L, 2 * PI});
                    p.push_back({0.0, R});
                } else {
                    p.push_back({L, R});
                }
            };
            sort(p.begin(), p.end());
            res += 2 * PI * r[i];
            double LL = 0, RR = 0;
            for (int j = 0; j < (int) p.size(); j++) {
                if (p[j].first > RR) {
                    res -= (RR - LL) * r[i];
                    LL = p[j].first;
                }
                RR = max(RR, p[j].second);
            }
            res -= (RR - LL) * r[i];
        }
        printf("%.10lf\n", res);
    }

    return 0;
}

然后就是其他的刷题：

这一场的补题：

 

 

 然后就是额外刷题目最近一直在刷CF1600-1700的题目，主要是感觉这次暑假的训练都是偏向思维还有数论，所以刷刷CF题目：