四舍五入 100pts
对于一个数 $ x $ ，可以发现它的答案可以分成两部分，一部分在 $ [2x + 1, n] $ 范围内，一部分在小于它的数的范围内，前者 $ \Theta(1) $ 算，对于后者，我们发现满足这个要求的数 $ y $ 一定有 $ x \mod y < w(x, y) $ （ $ w(x, y) $ 定义为如果 $ x \mod y = 0 $，则 $ w(a, b) = \frac xy - 1 $，否则 $ w(a, b) = \lfloor \frac xy \rfloor $ ）；
对于每个数，可以处理出所有小于它的满足后者的答案，这个可以差分维护；
复杂度是调和级数的，$ \Theta(n \ln n) $；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n;
long long a[5000005];
long long w(long long x, long long y) {
if (x % y == 0) return x / y - 1;
else return x / y;
}
int main() {
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
long long sum = 0;
for (long long i = 1; i <= n; i++) {
for (long long j = i; j <= n; j += i) {
a[j]++;
a[j + w(i, 2) + 1]--;
}
sum += a[i];
cout << sum + max(0ll, 1ll * n - 1ll * (2 * i)) << ' ';
}
return 0;
}
填算符 10pts
发现 $ \And $ 放前面不劣，所以把所有 $ \And $ 放在前面可以得到一个最大的答案；
考虑顺次倒着填 $ \And $，那么我们只需判断当前所得到的答案与能够忍受的二进制位上的最小答案是否在二进制位上有交集即可；
我们需要维护一段 $ \And $，然后再一段 $ | $，再一个 $ \And $，前面的一段 $ \And $ 直接前缀和维护，中间的一段 $ | $ 用线段树维护即可；
时间复杂度：$ \Theta(n \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
int n, k;
long long a[5000005], b[5000005];
long long ans;
set<int> s;
namespace SEG{
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
struct sss{
int l, r;
long long sum;
}tr[5000005];
inline void push_up(int id) {
tr[id].sum = (tr[ls(id)].sum | tr[rs(id)].sum);
}
void bt(int id, int l, int r) {
tr[id].l = l;
tr[id].r = r;
if (l == r) {
tr[id].sum = a[l];
return;
}
int mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
push_up(id);
}
long long ask(int id, int l, int r) {
if (l > r) return 0;
if (tr[id].l >= l && tr[id].r <= r) return tr[id].sum;
int mid = (tr[id].l + tr[id].r) >> 1;
if (r <= mid) return ask(ls(id), l, r);
else if (l > mid) return ask(rs(id), l, r);
else return (ask(ls(id), l, mid) | ask(rs(id), mid + 1, r));
}
}
int main() {
freopen("bitop.in", "r", stdin);
freopen("bitop.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
ans = a[1];
b[1] = a[1];
for (int i = 2; i <= n; i++) {
b[i] = (b[i - 1] & a[i]);
}
for (int i = 2; i <= k + 1; i++) {
ans &= a[i];
}
for (int i = k + 2; i <= n; i++) {
ans |= a[i];
}
SEG::bt(1, 1, n);
int res = k;
long long now = 0;
for (int i = n - 1; i >= 1; i--) {
if (res >= i) break;
if (res == 0) break;
now = b[res];
now = (now | SEG::ask(1, res + 1, i));
now = (now & a[i + 1]);
if ((now & ans) == ans) {
s.insert(i);
res--;
} else {
ans ^= (a[i + 1] & ans);
}
}
for (int i = 1; i <= res; i++) cout << i << ' ';
for (auto it = s.begin(); it != s.end(); it++) cout << *it << ' ';
return 0;
}
网格 22pts
DP；
部分分暴搜但是没写？；
考虑我们需要维护的东西，有以前的答案，到当前位的末尾的数（不完全）与以前的答案的并，这是一个大体的思路；
考虑先乘再加的性质，我们以加为分割点，把所有的乘算出来相加即可；
所以设 $ f_{i, j}, g_{i, j}, h_{i, j}, w_{i, j} $ 分别表示以前已经确定的答案，最后一个数与前面数的乘积，截止到上一个加号所有数（除了最后一个）的乘积，到 $ (i, j) $ 的路径数，转移分三种情况，具体见代码；
注意最后一个数组，我们要考虑所有路径的和，所以注意在更新 $ h_{i, j} $ 时首先应该乘上 $ w_{i, j} $；
时间复杂度：$ \Theta(nm) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
const long long mod = 998244353;
int n, m;
char s[2005][2005];
long long f[2005][2005], g[2005][2005], h[2005][2005], w[2005][2005];
int main() {
freopen("grid.in", "r", stdin);
freopen("grid.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> s[i][j];
}
}
h[1][1] = 1;
w[1][1] = 1;
g[1][1] = (s[1][1] - '0');
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) continue;
f[i][j] = (f[i - 1][j] + f[i][j - 1]) % mod;
g[i][j] = (g[i - 1][j] + g[i][j - 1]) % mod;
h[i][j] = (h[i - 1][j] + h[i][j - 1]) % mod;
w[i][j] = (w[i - 1][j] + w[i][j - 1]) % mod;
if (s[i][j] == '*') {
h[i][j] = g[i][j];
g[i][j] = 0;
}
if (s[i][j] == '+') {
f[i][j] = (f[i][j] + g[i][j]) % mod;
h[i][j] = w[i][j];
g[i][j] = 0;
}
if (s[i][j] >= '0' && s[i][j] <= '9') {
g[i][j] = (g[i][j] * 10 % mod + (s[i][j] - '0') * h[i][j] % mod) % mod;
}
}
}
cout << (f[n][m] + g[n][m]) % mod;
return 0;
}
矩形 48pts
可以联想到以前做过的找四个顶点不完全相同的矩形个数，此题同理，可以 $ \Theta(nm \log n) $ 做拿到48pts好像可以去掉 $ \log $ 但没有细想；
考虑正解，发现有小常数的部分分，于是联想到 $ \Theta(n \sqrt n) $ 或 $ \Theta(n \log^2 n) $ 的做法；
继承暴力的思路，以 $ x $ 为数组下标，将所有纵坐标等于 $ x $ 的点分为一类，那么我们发现：
-
对于一个 $ size $ 较大的类个数不会太多，我们直接开一个桶暴力遍历维护一下即可；
-
对于 $ size $ 较小的类，其中包含的点数不会太多，所以我们直接处理出所有点对，然后
Hash一下，开一个map记一下即可；
所以根号分治，时间复杂度 $ \Theta(n \sqrt n) $，常数很大，要用cc-hash-table;
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
int n;
int sq;
vector<int> v[200005], a, b;
bool t[200005], vis[200005];
long long ans;
cc_hash_table<long long, long long> mp;
int main() {
freopen("rect.in", "r", stdin);
freopen("rect.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
sq = sqrt(n);
int x, y;
for (int i = 1; i <= n; i++) {
cin >> x >> y;
v[x].push_back(y);
}
for (int i = 1; i <= n; i++) {
if (v[i].size() >= sq) a.push_back(i);
else if (v[i].size()) b.push_back(i);
sort(v[i].begin(), v[i].end());
}
for (int i = 0; i < a.size(); i++) {
vis[a[i]] = true;
for (int j = 0; j < v[a[i]].size(); j++) {
t[v[a[i]][j]] = true;
}
for (int j = 1; j <= n; j++) {
if (!v[j].size() || vis[j]) continue;
long long sum = 0;
for (int k = 0; k < v[j].size(); k++) {
if (t[v[j][k]]) sum++;
}
ans += (sum * (sum - 1)) / 2;
}
for (int j = 0; j < v[a[i]].size(); j++) {
t[v[a[i]][j]] = false;
}
}
for (int i = 0; i < b.size(); i++) {
for (int j = 0; j < v[b[i]].size(); j++) {
for (int k = j + 1; k < v[b[i]].size(); k++) {
long long now = v[b[i]][j] * 10000000000 + v[b[i]][k];
ans += 1ll * mp[now];
mp[now]++;
}
}
}
cout << ans;
return 0;
}