暑期cspj模拟赛4

T1

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 100;

long long a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    long long nmax = -1e18;
    long long nmin = 1e18;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        nmax = max(nmax, a[i]);
        nmin = min(nmin, a[i]);
    }

    cout << (nmax - nmin + 1) / 2 << endl;

    return 0;
}

T2

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

int factor(int n) {
    int res = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
                if (cnt % 2 == 0) {
                    res *= i;
                }
            }
        }
    }
    return res;
}

bool issquare(int n) {
    int x = sqrt(n);
    return x * x == n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T, m;
    cin >> T >> m;
    while (T--) {
        int a, b, c;
        cin >> a >> b >> c;
        int delta = b * b - 4 * a * c;
        // 无解
        if (delta < 0) {
            cout << "NO" << '\n';
            continue;
        }
        int p = abs(b);
        int q = abs(-a * 2);

        if (a * b > 0) {
            p = -p;
        }

        // 有理根
        if (issquare(delta)) {
            p += sqrt(delta);     // 一定是加上
            int g = gcd(p, q);
            p /= g;
            q /= g;
            cout << p;
            if (q != 1) {
                cout << '/' << q;
            }
            cout << '\n';
            continue;
        }
        else {
            // 无理根
            // 有理部分
            if (b != 0) {
                int g = gcd(p, q);
                p /= g;
                q /= g;
                cout << p;
                if (q != 1) {
                    cout << '/' << q;
                }
                cout << '+';
            }
            // 无理部分
            int r = factor(delta);
            q = abs(-a * 2);
            delta /= r * r;

            int g = gcd(r, q);
            r /= g;
            q /= g;

            if (r != 1) {
                cout << r << '*';
            }
            cout << "sqrt(" << delta << ")";
            if (q != 1) {
                cout << '/' << q;
            }
            cout << '\n';
        }
    }
    return 0;
}

T3

#include <bits/stdc++.h>
int n,m;
struct Node {
    int x,y,z;
};

Node v[1000010];
std::unordered_map<int, std::unordered_map<int, std::unordered_set<int>>> mapset;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        std::cin >> v[i].x >> v[i].y >> v[i].z;
        mapset[v[i].y][v[i].z].insert(v[i].x);
    }

    int ans = 0;
    for (int i = 0; i < m; ++i) {
        int a = v[i].x;
        int b = v[i].y;
        int c = v[i].z;
        for (auto it : mapset[a][b]) {
            if (mapset[b][c].count(it) && mapset[a][c].count(it)) {
                ans++;
            }
        }
    }
    std::cout << ans;
    return 0;
}

T4

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

ll n, m, s;
ll y, ans;
ll w[200010], v[200010];
ll l[200010], r[200010];
ll qzh1[200010], qzh2[200010];

bool check(ll wq) {
	y = 0;
	memset(qzh1, 0, sizeof(qzh1));  
	memset(qzh2, 0, sizeof(qzh2));
	// 多测不清空，爆零两行泪 
	for (int i = 1; i <= n; i++) {
		if (w[i] > wq)  // > 过了检测通过线 
			qzh1[i] = qzh1[i - 1] + 1, qzh2[i] = qzh2[i - 1] + v[i]; // 前缀和加上 
		else
			qzh1[i] = qzh1[i - 1], qzh2[i] = qzh2[i - 1];  // 承继原来的前缀 
	}
	for (int i = 1; i <= m; i++) {
		int rrrr = r[i];
		int llll = l[i];
		y += (qzh1[rrrr] - qzh1[llll - 1]) * (qzh2[rrrr] - qzh2[llll - 1]);  // 直接照着式子，简单分析，就会发现这跟式子几乎一模一样/doge 
	}
	if (y > s)
		return 1;  // 判断差值大还是小，为了二分的更改做准备 
	else
		return 0;
}

int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	for (int i = 1; i <= m; i++)
		cin >> l[i] >> r[i];
	int lll = 1;
	int rrr = 2000010;  
	ans = s;
	while (lll <= rrr) { // 二分答案 
		int mid = lll + (rrr - lll) / 2;  // 防爆ll， 原式子：(lll + rrr) / 2 
		if (check(mid))
			lll = mid + 1;
		else
			rrr = mid - 1;
			ans = min(ans, llabs(s - y)); // 为了防止爆int， 所以写llabs 
	}
	cout << ans;
}