E. Cardboard for Pictures
如果没有过可能是爆LL，在循环判断即可
二分枚举宽度大小，比较两者面积
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=1e11;
#define LL long long
int vis[N];
void solve() {
LL n, sum;
cin >> n >> sum;
vector<LL> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
auto check = [&](LL x) {
LL res = 0;
for (auto t : v) {
res += (t + x * 2) * (t + x * 2);
if (res > sum) return false;//判断，否则爆LL
}
return res <= sum;
};
LL l = 0, r = 1e10;
while (l + 1 < r) {
LL mid = l + r >> 1;
if (check(mid)) l = mid;
else r = mid;
}
cout << l;
cout << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
注意：会爆int
G. The Morning Star
对（a，b）点发现：如果存在八个方向，则一定在a,b,a+b,a-b这四条直线上
判断如果直线上有x个点，则这些点的贡献是x*(x-1)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=2e9;
#define LL long long
int vis[N];
void solve() {
int n;
cin >> n;
map<LL,LL> m1,m2,m3,m4;//都开LL,不然会爆int
for (int i = 1; i <= n; i++) {
LL x, y;
cin >> x >> y;
m1[x]++;
m2[y]++;
m3[x + y]++;
m4[x - y]++;
}
LL ans = 0;
for (auto v : m1) ans += v.second * (v.second - 1);
for (auto v : m2) ans += v.second * (v.second - 1);
for (auto v : m3) ans += v.second * (v.second - 1);
for (auto v : m4) ans += v.second * (v.second - 1);
cout << ans;
cout << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
H. The Third Letter
前提知识：利用带权的并查集
d[i]表示到祖先的距离，如果有环，则判断距离是否一致，不一致则输出NO
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=2e9;
#define LL long long
LL d[N], fa[N];
int find(int x) {
if (x != fa[x]) {
int t = fa[x];
fa[x] = find(fa[x]);
d[x] += d[t];
}
return fa[x];
}
void solve() {
int n, m;
cin >> n >> m;
bool ok = false;
memset(d, 0, sizeof d);
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
int x1 = find(x);
int y1 = find(y);
if (x1 != y1) {
fa[x1] = y1;
d[x1] = z + d[y] - d[x];//这里是x大
}
else if (d[x] - d[y] != z) ok = true;//搞清楚谁大
}
cout << (ok ? "NO" : "YES");
cout << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}