yLOI2020题解
Actinoi
11月 23, 2020
T1金陵谣：
题目大意：
求有多少 满足 。
推导这个式子，可得到：
因此，枚举 ，若 a * c * y % (c * d - b * y) == 0 则存在一组解。最后统计有多少可行解即可。
#include <cstdio>
int main() {
int T; scanf("%d", &T);
while (T--) {
long long a, b, c, d, cnt = 0;
scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
for (long long y = 1; b * y < c * d; y++) {
if (a * c * y % (c * d - b * y) == 0) {
cnt++;
}
}
printf("%lld\n", cnt);
}
return 0;
}
T2：不离
题目大意：
每件衣服都有一个穿戴前的力量值和精神值，以及穿戴后能增加的力量值和精神值。安排一个穿衣顺序，使得每件衣服都穿上，求最小的最初力量值与在初始力量值最小的前提下，初始精神值。
首先很容易可以想到 的做法，即暴力枚举 以及排列顺序。
接着，优化这个算法：
graph LR
A[a*b*n!] -->|a*b| B[二分答案a与b]
A -->|n!| C[在二分check中实现, 每次把满足a但不满足b的衣服以b为关键字用优先队列维护, 每次更新a之后更新里力量值与优先队列, 更新b之后从优先队列中弹出元素]
因此，复杂度便降到了 。
#include <queue>
#include <cstdio>
#include <algorithm>
#define MAXN 100001
#define MAXLL 1000000000000001
struct node{
long long a, b, c, d;
}pos[MAXN];
bool cmp_a(node x, node y) {
return x.a < y.a;
}
struct cmp_b{
long long pos, b;
bool operator < (const cmp_b &x) const {
return x.b < b;
}
};
long long n;
long long min(long long a, long long b) {return a < b ? a : b;}
long long max(long long a, long long b) {return a > b ? a : b;}
std::priority_queue<cmp_b> q; //按照 b 从小到大的次序
bool check(long long a, long long b) {
while (!q.empty()) {
q.pop();
}
long long head = 1; //head 存储当前压到第几个a了
for (int i = 1; i <= n; i++) { //把所有小于a的压进去
if (pos[i].a > a) break;
if (pos[i].b > b) { //能满足a但是不能满足b
q.push((cmp_b){i, pos[i].b});
}
if (b >= pos[i].b && a >= pos[i].a) {
a += pos[i].c, b += pos[i].d;
}
head++;
}
while (1) {
bool tag = false;
while (!q.empty()) {
if (q.top().b <= b) {
tag = true;
a += pos[q.top().pos].c, b += pos[q.top().pos].d;
q.pop();
} else {
break;
}
}
while (pos[head].a <= a && head <= n) {
tag = true;
if (pos[head].b > b) { //能满足a但是不能满足b
q.push((cmp_b){head, pos[head].b});
}
if (b >= pos[head].b && a >= pos[head].a) {
a += pos[head].c, b += pos[head].d;
}
head++;
}
if (head > n && q.empty()) {
return true;
}
if (!tag && (head <= n || !q.empty())) return false;
}
return true;
}
int main() {
//freopen("forever.in", "r", stdin);
//freopen("forever.out", "w", stdout);
int T; scanf("%d", &T);
long long max_force = 0, max_spirit = 0; scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld %lld %lld %lld", &pos[i].a, &pos[i].b, &pos[i].c, &pos[i].d);
max_force = max(max_force, pos[i].a), max_spirit = max(max_spirit, pos[i].b);
}
std::sort(pos + 1, pos + 1 + n, cmp_a); //按照 a 从小到大进行排序
long long la = 0, ra = max_force, ansa = MAXLL, ansb = MAXLL; //二分a
while (la <= ra) {
bool tag = false;
long long a = (la + ra) >> 1, tmp_b = MAXLL, lb = 0, rb = max_spirit;
while (lb <= rb) { //二分b
long long b = (lb + rb) >> 1;
if (check(a, b)) { //a, b能够成为可行解
tmp_b = min(tmp_b, b), tag = true;
rb = b - 1;
} else {
lb = b + 1;
}
}
if (tag) {
if (ansa > a) {
ansa = a, ansb = tmp_b;
} else if (ansa == a && ansb > tmp_b) {
ansb = tmp_b;
}
ra = a - 1;
} else {
la = a + 1;
}
}
printf("%lld %lld\n", ansa, ansb);
//fclose(stdin);
//fclose(stdout);
return 0;
}
T3：泸沽寻梦
题目大意：
给定一个数列，进行 次操作，每次将 与 位置上的数异或 ，每此操作结束后求有多少区间异或和为。最后输出所有回答的按位异或之和、有多少次回答的答案是奇数，以及所有答案中的最大值和最小值。
可以求一个异或前缀和，如果区间 的异或和为 ，那么可以通过异或的性质得到 。
因此，可以开一个 unordered_map 来存 pre 中的每个数字出现过多少次，则每个相同前缀和的数字两两都可以组成一个区间，也就是 。所以复杂度为 。
#include <cstdio>
#include <unordered_map>
#define MAXN 1000001
int num[MAXN];
long long pre[MAXN]; //前缀异或和
std::unordered_map<int, int> total; //存储每个数字出现的次数
std::unordered_map<int, bool> vis; //每个数字是否被访问过
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if(ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int main() {
//freopen("dream.in", "r", stdin);
//freopen("dream.out", "w", stdout);
int n, m; n = read(), m = read();
for (int i = 1; i <= n; i++) {
num[i] = read();
pre[i] = 1ll * num[i] ^ pre[i - 1];
total[pre[i]]++;
}
long long sum = 0;
total[0]++;
for (int i = 0; i <= n; i++) {
if (!vis[pre[i]]) {
vis[pre[i]] = true;
if (total[pre[i]] >= 2) sum += 1ll * total[pre[i]] * (total[pre[i]] - 1) / 2; //计算组合数
}
}
long long ans_sum = 0, js = 0, max_ans = 0, min_ans = 9223372036854775807;
while (m--) {
int p, x; p = read(), x = read();
sum = sum - total[pre[p]] + 1;
total[pre[p]]--;
pre[p] ^= x;
sum = sum + total[pre[p]];
total[pre[p]]++;
ans_sum ^= sum;
if (sum % 2 == 1) js++;
if (sum > max_ans) max_ans = sum;
if (sum < min_ans) min_ans = sum;
}
printf("%lld\n%lld\n%lld\n%lld\n", ans_sum, js, max_ans, min_ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}