平均数
题意是让求平均值第K小的连续子区间。
发现直接计算无论怎么优化都是 \(n^2\) 的，然后发现这样找K个的似乎可以考虑二分答案。
简单推一下式子。
记 \(sum[i]\) 为前缀和，显然符合条件的区间有：
即
\[sum[j] - j \times mid \leq sum[i] - i\times mid \]默认 \(j < i\)，区间为 \([i+1,j]\)，所以显然下标从0开始。
所以问题转化为一个类似01分数规划的东西，check的话用树状数组求逆序对，注意处理下标为0。
代码写得有点长，而且没有卡常所以有点慢。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 10;
const double eps = 1e-8;
double sum[maxn];
int w[maxn];
long long n, k;
void Add(int i, int val) {
for (; i <= 100001; i += (i & (-i))) w[i] += val;
}
int Ask(int i) {
int ans = 0;
for (; i; i -= i & (-i)) ans += w[i];
return ans;
}
struct node {
double data;
int pos;
}tmp[maxn];
bool cmp(node x, node y) { return x.data < y.data; }
bool Check(double mid) {
long long cnt = 0;
tmp[0] = (node) { 0, 0 };
for (int i = 1; i <= n; i++)
tmp[i] = (node) { sum[i] - mid * i, i};
sort(tmp, tmp + 1 + n, cmp);
for (int i = n; i >= 0; i--) {
cnt += Ask(tmp[i].pos + 1);
Add(tmp[i].pos + 1, 1);
}
for (int i = 0; i <= n; i++) Add(i + 1, -1);
return cnt >= k;
}
int main() {
freopen("ave.in", "r", stdin);
freopen("ave.out", "w", stdout);
scanf("%lld %lld", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%lf", &sum[i]);
sum[i] += sum[i - 1];
}
double l = 1.0, r = 1000000000.0, mid;
while (r - l > eps) {
mid = (l + r) / 2;
//cout<<mid<<endl;
if (Check(mid)) r = mid;
else l = mid;
}
printf("%.4lf\n", l);
return 0;
}
涂色游戏
并不是很会推这个式子...c一波学长题解吧...
设 \(f[i][j]\) 代表第\(i\)列选\(j\)个颜色的方案数，
\(g[i][j]\)代表用任意\(i\)个颜色填\(j\)个块的方案数，
\(h[i][j]\)代表上一列选\(i\)个颜色这一列选\(j\)个的方案数
\(g[i][j]=g[i-1][j-1] \times (p-i+1)+g[i][j-1] \times i\)，就是第二类斯特林数;
\(h[j][k]=\frac{g[k][n]}{C_{p}^{k}} \times \sum_{x=max(q,j,k)}^{min(p, j+k)}C_{j}^{j+k-x}C_{p-j}^{x-j}\)
\(f[i][j]=f[i-1][k] \times h[k][j]\)
发现\(f\)的转移跟\(i\)无关，再加上\(m\)如此巨大，可以矩阵乘。
其实并不用真正写一个矩阵快速幂，但我还是无脑套了板子...
另外，注意卡常。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int mo = 998244353;
int n, m, p, q;
long long g[maxn][maxn], h[maxn][maxn], c[maxn][maxn];
struct Mat {
long long w[maxn][maxn];
Mat() {
memset(w, 0, sizeof w);
}
void init() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = (i == j ? 1 : 0);
}
}
}
Mat operator * (const Mat &b) const {
Mat c;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
c.w[i][j] += w[i][k] * b.w[k][j] % mo;
}
c.w[i][j] %= mo;
}
}
return c;
}
};
long long Qpow(long long x, int t) {
long long s = 1;
while (t) {
if (t & 1) s = s * x % mo;
x = x * x % mo;
t >>= 1;
}
return s;
}
Mat Matpow(Mat x, int t) {
Mat s;
s.init();
while (t) {
if (t & 1) s = s * x;
x = x * x;
t >>= 1;
}
return s;
}
int main() {
//freopen("color.in", "r", stdin);
//freopen("color.out", "w", stdout);
cin >> n >> m >> p >> q;
for (int i = 0; i <= p; i++)
c[i][0] = 1;
for (int i = 1; i <= p; i++)
for (int j = 1; j <= i; j++)
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mo;
g[0][0] = 1, g[1][1] = 1, g[2][1] = 1;
for (int i = 1; i <= p; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = (g[i - 1][j - 1] * (p - i + 1) % mo + g[i][j - 1] * i % mo) % mo;
}
}
for (register int j = 1; j <= n; j++) {
for (register int k = 1; k <= n; k++) {
long long sum = 0;
for (int x = max(q, max(j, k)); x <= min(p, j + k); x++)
sum = (sum + c[j][j + k - x] * c[p - j][x - j] % mo) % mo;
h[j][k] = g[k][n] * Qpow(c[p][k], mo - 2) % mo * sum % mo;
}
}
Mat base, ans;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
base.w[i][j] = h[i][j];
for (int i = 1; i <= min(p, n); i++) {
ans.w[1][i] = g[i][n];
}
base = Matpow(base, m - 1);
ans = ans * base;
long long sum = 0;
for (int i = 1; i <= min(n, p); i++)
sum = (sum + ans.w[1][i]) % mo;
cout << sum << endl;
return 0;
}
序列
考场上打了1h+的主席树挂了...
用线段树套vector水过。
每个节点开一个vector，存下能够完全覆盖此节点代表区间的询问的x值。（注意保证vector有序）
然后考虑每个a[i]的贡献，从根一直到区间为i的叶子节点，每到一个节点就在该节点的vector里二分一下，由于一个询问最多只会更新一个节点一次，所以贡献不会算重。
ans[i]记录a[i]的贡献。
修改的话直接计算更新即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 1e5 + 10;
inline int read() {
int s = 0, w = 1;
char c = getchar();
while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
return s * w;
}
struct tree {
vector<int> qe;
}t[maxn << 2];
#define ls (u << 1)
#define rs (u << 1 | 1)
void Update(int u, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr) {
t[u].qe.push_back(val);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) Update(ls, l, mid, ql, qr, val);
if (qr > mid) Update(rs, mid + 1, r, ql, qr, val);
return;
}
int Get(int u, int val) {
int ans, flag = 1;
/*for (int i = 0; i < t[u].qe.size(); i++) {
if (t[u].qe[i] > val) {
flag = 0;
ans = i;
break;
}
}
if (flag) ans = t[u].qe.size();*/
int l = 0, r = t[u].qe.size() - 1, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (t[u].qe[mid] > val) r = mid - 1;
else l = mid + 1;
}
//cout << "************" << endl;
//printf("ans = %d l = %d\n", ans, l);
//cout << "************" << endl;
return l;
}
int Ask(int u, int l, int r, int pos, int val) {
if (l == r) {
return Get(u, val);
}
int mid = (l + r) >> 1;
int ans = 0;
ans += Get(u, val);
if (pos <= mid) ans += Ask(ls, l, mid, pos, val);
else ans += Ask(rs, mid + 1, r, pos, val);
return ans;
}
int n, m, q;
int a[maxn];
int aa[maxn];
struct node {
int l, r, x;
}qq[maxn];
bool cmp(node aa, node bb) { return aa.x < bb.x; }
int main() {
freopen("seq.in", "r", stdin);
freopen("seq.out", "w", stdout);
n = read(), m = read(), q = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= m; i++) {
qq[i].l = read(), qq[i].r = read(), qq[i].x = read();
}
sort(qq + 1, qq + 1 + m, cmp);
for (int i = 1; i <= m; i++) {
Update(1, 1, n, qq[i].l, qq[i].r, qq[i].x);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
aa[i] = Ask(1, 1, n, i, a[i]);
ans += aa[i];
}
printf("%d\n", ans);
//for (int i = 1; i <= n; i++)
//cout << aa[i] << endl;
int u, v, pos, val;
while (q--) {
u = read(), v = read();
pos = u ^ ans;
val = v ^ ans;
ans -= aa[pos];
aa[pos] = Ask(1, 1, n, pos, val);
ans += aa[pos];
printf("%d\n", ans);
}
}