静下心 做自己能控制的事情
加油
周一
Master of Sequence（推公式 + 数学）
这道题主要是推公式
同时ai <= 1000是突破口，说明很多ai是重复的，可以记录出现次数，然后遍历1到1000
把这个向下取整的式子分离出两个式子
t / ai b / ai 同时看什么时候会多减一个一
不用推，感性一样其实就比较多出来的t % a 和 b % a就可以了
显然如果相减大于等于0，向下取整是0，没有影响
如果小于0，向下取整会多减去一个1
所以我们处理三个部分
第一部分t / ai
可以因为ai <= 1000 可以直接从1遍历一千结合出现次数来处理
第二部分bi / ai 可以O(1)维护
第三部分t % ai 和bi % ai
显然维护bi % ai 然后for1到1000
那么可以开1000个树状数组维护ti % ai,因为是单点修改，区间求和
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int M = 1e3 + 10;
const int N = 1e5 + 10;
int a[N], b[N], f[M][M], num[M], n, m;
ll sum;int lowbit(int x) { return x & -x; }void add(int x, int p, int id)
{x++; for(; x <= 1000; x += lowbit(x)) f[id][x] += p;
}int ask(int x, int id)
{x++;int res = 0;for(; x; x -= lowbit(x))res += f[id][x];return res;
}bool check(ll t, ll k)
{ll res = -sum;_for(i, 1, 1000) res += t / i * num[i] - num[i] + ask(t % i, i);return res >= k;
}int main()
{int T; scanf("%d", &T);while(T--){sum = 0;memset(num, 0, sizeof num);memset(f, 0, sizeof f);scanf("%d%d", &n, &m);_for(i, 1, n) scanf("%d", &a[i]), num[a[i]]++;_for(i, 1, n){scanf("%d", &b[i]);sum += b[i] / a[i];add(b[i] % a[i], 1, a[i]);}while(m--){int op, x, y, k;scanf("%d", &op);if(op <= 2){scanf("%d%d", &x, &y);num[a[x]]--;sum -= b[x] / a[x];add(b[x] % a[x], -1, a[x]);if(op == 1) a[x] = y;else b[x] = y;num[a[x]]++;sum += b[x] / a[x];add(b[x] % a[x], 1, a[x]);}else{scanf("%d", &k);ll l = 0, r = 1e12;while(l + 1 < r){ll m = l + r >> 1;if(check(m, k)) r = m;else l = m;}printf("%lld\n", r);}}}return 0;
}Master of Phi（数论）
用到了挺多的数论知识
积性函数，迪利克雷卷积，欧拉函数通项公式
推出公式这道题就做完了
周二
C. Choosing flowers（思维）
这道题妙啊
关键是发现最优策略一定符合某种性质
显然策略是一些不选，一些选一个，一些选大于1个
首先如果是全部选一个的，那就直接排序了
如果有选大于1个的，可以发现，所有的bi，可以全部选最优的
那么其实这种情况下只有一种花选了bi，其他都是选一个
那就直接枚举那一种花选了bi就可以了，首先先贪心，把大于bi的ai全部都选了，这个过程可以给ai排序然后二分找位置，前缀和。 之后再选当前的ai，再选bi
注意当前的ai可能在前面已选的ai里面，也可能不在，这个细节要判断一下
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
int a[N], b[N], c[N], n, m;
ll s[N];int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);_for(i, 1, m) {scanf("%d%d", &a[i], &b[i]);c[i] = a[i];}sort(c + 1, c + m + 1, greater<int>());_for(i, 1, m) s[i] = s[i - 1] + c[i];ll ans = 0;if(n <= m) ans = s[n];_for(i, 1, m){int pos = upper_bound(c + 1, c + m + 1, b[i], greater<int>()) - c - 1;if(n <= pos) continue;ll res = s[pos], cnt = n - pos;if(a[i] <= b[i]) res += a[i], cnt--;res += cnt * b[i];ans = max(ans, res);}printf("%lld\n", ans);}return 0;
}周三
D. 505（思维 + 状压dp）
自己想的时候发现了4 乘4以上肯定不行
但是没有注意到，如果可以的话，n只有1，2， 3三种取值……
没有利用好这个信息
知道这个后，n=1为0
n=2的话，就是每一个列一的个数为奇偶奇偶……或者偶奇偶奇……
n=3的话状压dp就好了，挺简单的一个状压dp
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e6 + 10;
int a[N], dp[N][8], n, m;int id(int i, int j) { return (i - 1) * m + j; }bool check(int pre, int now)
{int k[5][5];k[1][1] = pre & 1; k[2][1] = (pre >> 1) & 1; k[3][1] = (pre >> 2) & 1;k[1][2] = now & 1; k[2][2] = (now >> 1) & 1; k[3][2] = (now >> 2) & 1;int cnt1 = k[1][1] + k[1][2] + k[2][1] + k[2][2];int cnt2 = k[2][1] + k[2][2] + k[3][1] + k[3][2];return (cnt1 & 1) && (cnt2 & 1);
}int cal(int now, int j)
{int res = 0, t[5];t[1] = now & 1; t[2] = (now >> 1) & 1; t[3] = (now >> 2) & 1;_for(i, 1, 3) res += (t[i] != a[id(i, j)]);return res;
}int main()
{scanf("%d%d", &n, &m);if(n > m) swap(n, m);_for(i, 1, n)_for(j, 1, m)scanf("%1d", &a[id(i, j)]);if(n >= 4) puts("-1");else if(n == 1) puts("0");else if(n == 2){int ans = 0, cnt = 0, t = 0;_for(j, 1, m){int one = (a[id(1, j)] + a[id(2, j)]) % 2;cnt += (one != t);t ^= 1;}ans = max(ans, cnt);t = 1; cnt = 0;_for(j, 1, m){int one = (a[id(1, j)] + a[id(2, j)]) % 2;cnt += (one != t);t ^= 1;}printf("%d\n", min(ans, cnt));}else{int ans = 1e9;memset(dp, 0x3f, sizeof dp);rep(now, 0, 1 << 3) dp[1][now] = cal(now, 1);_for(j, 2, m)rep(pre, 0, 1 << 3)rep(now, 0, 1 << 3)if(check(pre, now)){dp[j][now] = min(dp[j][now], dp[j - 1][pre] + cal(now, j));if(j == m) ans = min(ans, dp[j][now]);}printf("%d\n", ans);}return 0;
}