2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
题目链接
Problems:
Problem A. Exam
你和朋友一起写一些判断题，现知两人答案以及朋友正确题数，求你最多正确的题数
分别统计和朋友答案相同、不同的题目数量计算即可
AC代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int k; cin >> k;
int cnt1 = 0, cnt2 = 0;
string s1, s2; cin >> s1 >> s2;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] == s2[i]) cnt1++;
else cnt2++;
}
int ans = min(cnt1, k);
ans += cnt2 - max(0, (k - cnt1));
cout << ans << endl;
return 0;
}
Problem B. Coprime Integers
求 i=a∑bj=c∑d[gcd(i,j)=1]
题目和 BZOJ 2301: [HAOI2011]Problem b 几乎一样
具体请看 BZOJ 2301: [HAOI2011]Problem b 题解 BZOJ 2301 [HAOI2011]Problem b(莫比乌斯反演+容斥原理)
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 5;
bool is_prime[maxn];
vector<int> prime;
int mu[maxn];
ll prefix[maxn];
void Sieve() {
memset(is_prime, true, sizeof(is_prime));
mu[1] = 1;
for (int i = 2; i < maxn; ++i) {
if (is_prime[i]) {
prime.push_back(i);
mu[i] = -1;
}
for (auto &it : prime) {
if (it * i >= maxn) break;
is_prime[i * it] = false;
if (i % it == 0) {
mu[i * it] = 0;
break;
}
mu[i * it] = -mu[i];
}
}
for (int i = 1; i < maxn; ++i) prefix[i] = prefix[i - 1] + mu[i];
}
ll Get(int n, int m) {
if (n > m) swap(n, m);
ll ans = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += (prefix[r] - prefix[l - 1]) * (n / l) * (m / l);
}
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
Sieve();
int a, b, c, d; cin >> a >> b >> c >> d;
ll ans = Get(b, d);
ans -= Get(b, c - 1); ans -= Get(a - 1, d);
ans += Get(a - 1, c - 1);
cout << ans << endl;
return 0;
}
Problem F. Rectangles
求 n 个矩形中奇数个矩形覆盖区域的面积和
矩形面积异或并，和矩形面积并极其相似，利用扫描线+线段树进行计算
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> x;
int Get(int k) {
return lower_bound(x.begin(), x.end(), k) - x.begin();
}
class seg_tree {
public:
struct node {
int v, lazy;
node(int _v = 0, int _lazy = 0): v(_v), lazy(_lazy) {}
};
node Unite(const node &k1, const node &k2) {
node ans;
ans.v = k1.v + k2.v;
return ans;
}
void Pull(int o) {
tree[o] = Unite(tree[o << 1], tree[o << 1 | 1]);
}
void Push(int o, int l, int r) {
int m = (l + r) >> 1;
if (tree[o].lazy != 0) {
tree[o << 1].v = x[m] - x[l - 1] - tree[o << 1].v;
tree[o << 1 | 1].v = x[r] - x[m] - tree[o << 1 | 1].v;
tree[o << 1].lazy ^= 1;
tree[o << 1 | 1].lazy ^= 1;
tree[o].lazy = 0;
}
}
int n;
vector<node> tree;
void Build(int o, int l, int r) {
if (l == r) return;
int m = (l + r) >> 1;
Build(o << 1, l, m);
Build(o << 1 | 1, m + 1, r);
Pull(o);
}
seg_tree(int _n): n(_n) {
tree.resize(n << 2);
Build(1, 1, n);
}
void Modify(int o, int l, int r, int ll, int rr) {
if (ll <= l && rr >= r) {
tree[o].v = x[r] - x[l - 1] - tree[o].v;
tree[o].lazy ^= 1;
return;
}
Push(o, l, r);
int m = (l + r) >> 1;
if (ll <= m) Modify(o << 1, l, m, ll, rr);
if (rr > m) Modify(o << 1 | 1, m + 1, r, ll, rr);
Pull(o);
}
void Modify(int ll, int rr) {
Modify(1, 1, n, ll, rr);
}
node Query(int o, int l, int r, int ll, int rr) {
if (ll <= l && rr >= r) return tree[o];
Push(o, l, r);
int m = (l + r) >> 1;
node ans;
if (ll <= m) ans = Unite(ans, Query(o << 1, l, m, ll, rr));
if (rr > m) ans = Unite(ans, Query(o << 1 | 1, m + 1, r, ll, rr));
Pull(o);
return ans;
}
node Query() {
return Query(1, 1, n, 1, n);
}
};
struct seg {int l, r, h, flag;};
bool operator < (seg k1, seg k2) {return k1.h < k2.h;}
vector<seg> s;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
for (int i = 0, x1, y1, x2, y2; i < n; ++i) {
cin >> x1 >> y1 >> x2 >> y2;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
x.emplace_back(x1); x.emplace_back(x2);
s.emplace_back((seg){x1, x2, y1, 1});
s.emplace_back((seg){x1, x2, y2, -1});
}
sort(s.begin(), s.end());
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
seg_tree sgt(x.size());
ll ans = 0;
for (int i = 0, l, r; i < s.size() - 1; ++i) {
l = Get(s[i].l), r = Get(s[i].r);
sgt.Modify(l + 1, r);
ans += (ll)sgt.Query().v * (s[i + 1].h - s[i].h);
}
cout << ans << endl;
return 0;
}
Problem G. Goat on a Rope
有一矩形和一点，以点为圆心做与矩形不相交的最大圆，求半径
直接求出点到矩形四条线段的最短距离即可
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db inf = 1e20;
const db eps = 1e-9;
int Sgn(db k) {return fabs(k) < eps ? 0 : (k < 0 ? -1 : 1);}
int Cmp(db k1, db k2) {return Sgn(k1 - k2);}
db min(db k1, db k2) {return Cmp(k1, k2) < 0 ? k1 : k2;}
struct point {db x, y;};
point operator - (point k1, point k2) {return (point){k1.x - k2.x, k1.y - k2.y};}
point operator + (point k1, point k2) {return (point){k1.x + k2.x, k1.y + k2.y};}
db operator * (point k1, point k2) {return k1.x * k2.x + k1.y * k2.y;}
db operator ^ (point k1, point k2) {return k1.x * k2.y - k1.y * k2.x;}
db GetLen(point k) {return sqrt(k * k);}
db DisP2P(point k1, point k2) {return sqrt((k2 - k1) * (k2 - k1));}
struct line {point s, t;};
typedef line seg;
db GetLen(line k) {return GetLen(k.t - k.s);}
db DisP2Line(point k1, line k2) {return fabs((k1 - k2.s) ^ (k2.t - k2.s)) / GetLen(k2);}
db DisP2Seg(point k1, line k2) {
if (Sgn((k1 - k2.s) * (k2.t - k2.s)) < 0 || Sgn((k1 - k2.t) * (k2.s - k2.t)) < 0) {
return min(DisP2P(k1, k2.s), DisP2P(k1, k2.t));
}
return DisP2Line(k1, k2);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(3);
point goat; db x1, y1, x2, y2;
cin >> goat.x >> goat.y >> x1 >> y1 >> x2 >> y2;
db ans = inf;
ans = min(ans, DisP2Seg(goat, (line){(point){x1, y1}, (point){x2, y1}}));
ans = min(ans, DisP2Seg(goat, (line){(point){x1, y1}, (point){x1, y2}}));
ans = min(ans, DisP2Seg(goat, (line){(point){x2, y1}, (point){x2, y2}}));
ans = min(ans, DisP2Seg(goat, (line){(point){x1, y2}, (point){x2, y2}}));
cout << ans << endl;
return 0;
}
Problem H. Repeating Goldbachs
给出一个偶数 n(n≥4) ，每次使 n 分解为差最大的两个素数之和，并用两个素数之差的绝对值替换 n 直到 n<4 ，求分解次数
直接暴力递归分解即可
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
bool is_prime[maxn];
vector<ll> prime;
void Sieve() {
memset(is_prime, true, sizeof(is_prime));
for (ll i = 2; i < maxn; ++i) {
if (is_prime[i]) prime.emplace_back(i);
for (auto &it : prime) {
if (it * i >= maxn) break;
is_prime[i * it] = false;
}
}
}
ll Find(ll k) {
if (k < 4) return 0;
for (auto &it : prime) {
if (is_prime[k - it]) {
int diff = abs(it - (k - it));
if (diff & 1) continue;
return Find(diff) + 1;
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
Sieve();
ll x; cin >> x;
cout << Find(x) << endl;
return 0;
}
Problem J. Time Limits
每组数据需要跑 tk ms ，求跑 s 次数据最少设定的时限（以秒为单位）
找出时限最大值 max 计算 ceil(1000max×s) 即可
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
ll n, s; cin >> n >> s;
vector<ll> arr(n);
ll Max = -inf;
for (auto &it : arr) {
cin >> it;
Max = max(Max, it);
}
cout << (Max * s + 999) / 1000 << endl;
return 0;
}
Problem L. Liars
n 个人围成一圈，每个人会说真话或者假话，现每个人说出他认为说真话的人数区间，求最多说真话的人数
用差分数组对所有说真话人数的可能性进行计数，之后暴力找出合法的最大值即可
AC代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
vector<int> diff(n + 1, 0);
for (int i = 0, l, r; i < n; ++i) {
cin >> l >> r;
diff[l]++;
if (r != n) diff[r + 1]--;
}
vector<int> cnt(n + 1, 0);
cnt[0] = diff[0];
int ans = -1;
for (int i = 1; i <= n; ++i) {
cnt[i] = cnt[i - 1] + diff[i];
if (cnt[i] == i) ans = i;
}
cout << ans << endl;
return 0;
}
查看8道真题和解析