E. Water Taps
题意：
每个水龙头有一个流量限制\(a_i\)，温度\(t_i\)，现在让你控制每个水龙头的出水量\(x_i\)，使得最终的水温为\(T\)，水温的公式为$\frac{\sum \limits_{i=1} ^{n}x_i t_i }{\sum \limits_{i=1} ^{n}t_i } $
思路：
二分总水量\(T\)，按照最坏分配方法（按照\(t\)从小到大排序）和最好分配方法（按照\(t\)从大到小排序）来分配出水量，分别算出分子，与$\sum \limits_{i=1}^{n}t_i $ \(T\)比较，看这个式子是否在最小值和最大值之间。
View Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const double eps = 1e-8;
const int inf = 1e9;
struct node {
double a, t;
} e[N];
int n;
double T;
double na[N];
bool cmp(node a, node b) {
if (a.t == b.t) return a.a < b.a;
return a.t < b.t;
}
bool check(double flow) {
double minv = 0, maxv = 0;
double temp = flow;
for (int i = 1; i <= n; i++) {
double now = min(flow, e[i].a);
flow -= now;
minv += now * e[i].t;
}
flow = temp;
for (int i = n; i >= 1; i--) {
double now = min(flow, e[i].a);
flow -= now;
maxv += now * e[i].t;
}
flow = temp;
if (flow * T <= maxv && flow * T >= minv) return 1;
return 0;
}
signed main() {
scanf("%d%lf", &n, &T);
double all = 0;
for (int i = 1; i <= n; i++) {
scanf("%lf", &e[i].a);
all += e[i].a;
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &e[i].t);
}
sort(e + 1, e + n + 1, cmp);
double l = 0, r = all;
for (int i = 1; i <= 200; i++) {
double mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
printf("%.10lf\n", l);
}
F. Runner's Problem
题意：
给定一个\(3×m\)的矩阵，起点为\((2,1)\)，终点为\((2,m)\)，每次在不越界的情况下，在\((i,j)\),每次可以走向\((i+1,j+1)、(i,j+1)、(i-1,j+1)\)，输入\(n\)个障碍物，输入给个障碍物所在的行和占据的起始列和行,问到终点的方案数
思路：
数据范围不大的情况下，直接线性\(dp\)
\(dp(i,j)=dp(i-1,j-1)+dp(i,j-1)+dp(i+1,j-1)\)
\(m\)比较大，考虑用矩阵快速幂加速计算，构造矩阵\(\begin{pmatrix}
1& 1& 0 \\
1& 1& 1\\
0& 1& 1
\end{pmatrix}\)
\(\begin{pmatrix}dp(1,j-1)\\dp(2,j-1)\\dp(3,j-1)\end{pmatrix}\) \(\begin{pmatrix}
1& 1& 0 \\
1& 1& 1\\
0& 1& 1
\end{pmatrix}=\begin{pmatrix}dp(1,j)\\dp(2,j)\\dp(3,j)\end{pmatrix}\)
考虑有障碍物，所以分段用矩阵快速幂计算
View Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
struct Matrix {
int a[5][5];
int n, m;
Matrix() {
n = m = 0;
memset(a, 0, sizeof a);
}
void clear() { memset(a, 0, sizeof a); }
Matrix operator*(const Matrix &t) const {
Matrix ans;
ans.n = n, ans.m = t.m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= m; k++) {
ans.a[i][k] =
(ans.a[i][k] + a[i][j] * t.a[j][k] % mod) % mod;
}
}
}
return ans;
}
};
int n, m;
struct node {
int x, l, r;
} e[N];
vector<int> pos;
int c[4][N];
int s[4];
Matrix Matpower(Matrix &A, int k) {
Matrix res;
// res.a[1][1] = 1, res.a[2][2] = 1, res.a[3][3] = 1;
res.n = res.m = A.n;
for (int i = 1; i <= res.n; i++) {
res.a[i][i] = 1;
}
while (k) {
if (k & 1) res = res * A;
k >>= 1;
A = A * A;
}
return res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
pos.push_back(1);
pos.push_back(m);
for (int i = 1; i <= n; i++) {
cin >> e[i].x >> e[i].l >> e[i].r;
pos.push_back(e[i].l - 1);
pos.push_back(e[i].r);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
for (int i = 1; i <= n; i++) {
e[i].l = lower_bound(pos.begin(), pos.end(), e[i].l) - pos.begin();
e[i].r = lower_bound(pos.begin(), pos.end(), e[i].r) - pos.begin();
c[e[i].x][e[i].l]++;
c[e[i].x][e[i].r + 1]--;
}
Matrix dp, t;
dp.n = 3, dp.m = 1;
t.n = t.m = 3;
dp.a[2][1] = 1;
int len = pos.size();
for (int i = 1; i < len; i++) {
t.clear();
for (int j = 1; j <= 3; j++) {
for (int k = 1; k <= 3; k++) {
t.a[j][k] = 1;
}
}
t.a[1][3] = t.a[3][1] = 0;
for (int j = 1; j <= 3; j++) {
s[j] += c[j][i];
if (s[j]) {
for (int k = 1; k <= 3; k++) {
t.a[j][k] = 0;
}
}
}
t = Matpower(t, pos[i] - pos[i - 1]);
dp = t * dp;
// cout<<pos[i]-pos[i-1]<<endl;
}
cout << dp.a[2][1] << endl;
}
G. Castle Defense
题意：
在\(i\)号位置有\(a_i\)个弓箭手，\(i\)号弓箭手的攻击距离为\(r\)，所以可以攻击到\(j\)处，\(|i-j|≤r\)，现在定义\(i\)城墙的防御力为可以攻击到该处的弓箭手数量，城墙的防御力为所有城墙防御力的最小值，现在可以派\(k\)个小兵增援，问城墙的防御力最高可以是多少？
思路：
由于每个小兵相当于是给一段区间同时加\(1\),所以直接差分，然后直接二分防御力，从前往后扫每个地方的防御力，不够的话就贪心在范围内的最右边加小兵
View Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int n, r, k;
int a[N];
int dif[N];
int pre[N];
int t[N], now[N];
bool check(int x) {
for (int i = 1; i <= n; i++) {
t[i] = dif[i];
}
int have = k;
for (int i = 1; i <= n; i++) {
now[i] = now[i - 1] + t[i];
if (now[i] < x) {
int cha = x - now[i];
if (cha > have) return 0;
// t[i] += cha;
now[i] = x;
have -= cha;
if (i + 2 * r + 1 <= n) t[i + 2 * r + 1] -= cha;
}
}
return 1;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> r >> k;
int maxv = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxv += a[i];
dif[max(1ll, i - r)] += a[i];
if (i + r + 1 <= n) dif[i + r + 1] -= a[i];
}
int l = 0, r = maxv + k;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
cout << l << endl;
}
H. Path Counting
题意:
\(1\)为根节点，现在深度为\(i\)的点有\(a_i\)个子节点，现在让你输出长度为\(k\)的条数，(1,2)点对的路径和(2,1)点对的路径相同
思路：
由于这个树同一深度下的子树形态相同，定义dp(i,j)为深度为\(i\)的点为起点，向下走长度为\(j\)的路径条数。
那么\(dp(i,j)=dp(i+1,j-1)×a_i\)
定义f(i,j)为深度为\(i\)的点，第一步为向上走，走的路径长度为\(j\)的路径条数。
\(f(i,j)=f(i-1,j-1)+(a_i-1)×dp(i,j-2)\)
统计答案时，还要乘上深度为\(i\)的点的个数
最终输出答案时，还要除以2，因为这种统计会算重
由于卡空间，所以要么滚动优化，要么不开\(f\)数组，接着用\(dp\)算答案
View Code
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
const int mod = 1e9 + 7;
const int N = 5005;
int f[N][2 * N];
int a[N];
int pre[N];
int n;
int ans[N * 2];
int qmi(int a, int k) {
int res = 1;
while (k) {
if (k & 1) res = (ll)res * a % mod;
k >>= 1;
a = (ll)a * a % mod;
}
return res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0) ;
cout.tie(0) ;
cin >> n;
int inv = qmi(2, mod - 2);
for (int i = 1; i <= n - 1; i++) {
cin >> a[i];
}
pre[1] = 1;
for (int i = 2; i <= n; i++) {
pre[i] = (ll)pre[i - 1] * a[i - 1] % mod;
}
for (int i = 1; i <= n; i++) f[i][0] = 1;
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= n - i; j++) {
f[i][j] = (ll)f[i + 1][j - 1] * a[i] % mod;
ans[j] = (ans[j] + (ll)f[i][j] * pre[i] % mod) % mod;
}
}
for(int i=1;i<=n;i++) {
f[1][i]=0;
}
for (int i = 2; i <= n; i++) {
for (int j = 2 * n - 2; j >= 1; j--) {
f[i][j] = f[i - 1][j - 1];
if (j >= 2)
f[i][j] = (f[i][j] + (ll)(a[i - 1] - 1) * f[i][j - 2] % mod) % mod;
ans[j] = (ans[j] + (ll)f[i][j] * pre[i] % mod) % mod;
}
}
for (int i = 1; i <= 2 * n - 2; i++) {
ans[i] = (ll)ans[i] * inv % mod;
cout << ans[i] << " ";
}
}