A. 01矩形
枚举上下界，two-pointers
// Author: xiaruize
// #pragma GCC optimize("-ofast")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 5e4 + 10;
// bool st;
int n, m;
char s[35][N];
int llim, rlim;
int cnt[N][35];
// bool en;
void solve()
{
cin >> n >> m;
rep(i, 1, n) cin >> (s[i] + 1);
rep(i, 1, n)
{
rep(j, 1, m)
{
cnt[j][i] = cnt[j][i - 1] + (s[i][j] == '1');
}
}
cin >> llim >> rlim;
if (llim == 0 && rlim == n * m)
{
cout << (long long)n * (long long)(n + 1) / 2ll * (long long)m * (long long)(m + 1) / 2ll << endl;
return;
}
long long res = 0;
rep(u, 1, n)
{
rep(d, u, n)
{
int curl = 0, curr = 0, r = 0, rr = 0;
for (int l = 1; l <= m; l++)
{
while (r <= m && curl < llim)
{
r++;
curl += cnt[r][d] - cnt[r][u - 1];
}
while (rr <= m && curr <= rlim)
{
rr++;
curr += cnt[rr][d] - cnt[rr][u - 1];
}
// cerr << u << ' ' << d << ' ' << l << ' ' << r << ' ' << rr << endl;
res += 1ll * (rr - r);
curl -= cnt[l][d] - cnt[l][u - 1];
curr -= cnt[l][d] - cnt[l][u - 1];
}
}
}
cout << res << endl;
}
signed main()
{
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
return 0;
}
B. 商店购物
前面 \(dp\) 后面组合
dp可以考虑前缀和优化或者容斥
// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;
int fac[10000009], inv[10000009];
int qpow(int a, int b)
{
int ans = 1;
while (b)
{
if (b & 1)
ans = (ans * a) % MOD;
a = (a * a) % MOD;
b /= 2;
}
return ans;
}
void init()
{
fac[0] = 1;
for (int i = 1; i <= 10000000; i++)
fac[i] = (fac[i - 1] * i) % MOD;
inv[10000000] = qpow(fac[10000000], MOD - 2);
for (int i = 10000000 - 1; i >= 0; i--)
inv[i] = (inv[i + 1] * (i + 1)) % MOD;
}
int C(int x, int y)
{
if (x < 0 || x < y || y < 0)
return 0;
if (x == y || y == 0)
return 1;
else
return fac[x] * inv[x - y] % MOD * inv[y] % MOD;
}
// bool st;
int n, m, k;
int w[305];
int dp[90005], s[90005];
// bool en;
void solve()
{
init();
cin >> n >> m >> k;
rep(i, 1, m) cin >> w[i];
int sum = 0;
dp[0] = 1;
rep(i, 0, min(k, 90000ll)) s[i] = 1;
rep(i, 1, m)
{
sum += w[i];
sum = min(sum, min(k, 90000ll));
per(j, sum, 1)
{
if (j > w[i])
(dp[j] += ((s[j - 1] - s[j - w[i] - 1]) % MOD + MOD) % MOD) %= MOD;
else
(dp[j] += s[j - 1]) %= MOD;
}
rep(j, 1, min(k, 90000ll))
{
s[j] = (s[j - 1] + dp[j]) % MOD;
// cerr << dp[j] << ' ';
}
// cerr << endl;
}
int res = 0;
int t = n - m;
if (t)
rep(i, 0, sum)
{
// cerr << i << ' ' << dp[i] << endl;
res = (res + dp[i] * C(k - i + t - 1, t - 1) % MOD) % MOD;
}
else
res = dp[k];
cout << res << endl;
}
signed main()
{
// freopen("shopping.in", "r", stdin);
// freopen("shopping.out", "w", stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
return 0;
}
C. 友好城市
今天才知道原来强联通分量除了tarjan还有别的做法
kosaraju 在 \(n\) 较小的图中可以 bitset 优化获得比 tarjan 更优的时间复杂度
然后就莫队板子了
// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 3e5 + 10;
// bool st;
int n, m, q;
bitset<155> bt[155], bt2[155];
int tot[155][155];
pii eg[N];
bitset<155> vis;
vector<int> vec;
struct node
{
int l, r, id;
} s[N];
// bool en;
int unit;
bool cmp(node a, node b)
{
return (a.l / unit == b.l / unit
? (a.r == b.r ? 0 : ((a.l / unit) & 1) ^ (a.r < b.r))
: a.l < b.l);
}
void dfs(int x)
{
vis[x] = 0;
bitset<155> tmp = (vis & bt[x]);
int cur = tmp._Find_first();
while (cur != 155)
{
dfs(cur);
bitset<155> tmp = (vis & bt[x]);
cur = tmp._Find_first();
}
// cerr << x << endl;
vec.push_back(x);
}
int cnt = 0;
int ans[N];
void dfs2(int x)
{
vis[x] = 0;
cnt++;
bitset<155> tmp = (vis & bt2[x]);
int cur = tmp._Find_first();
while (cur != 155)
{
dfs2(cur);
bitset<155> tmp = (vis & bt2[x]);
cur = tmp._Find_first();
}
}
int curl = 1, curr = 0;
void add(int x)
{
tot[eg[x].first][eg[x].second]++;
if (tot[eg[x].first][eg[x].second] == 1)
{
bt[eg[x].first][eg[x].second] = 1;
bt2[eg[x].second][eg[x].first] = 1;
}
}
void del(int x)
{
tot[eg[x].first][eg[x].second]--;
if (!tot[eg[x].first][eg[x].second])
{
bt[eg[x].first][eg[x].second] = 0;
bt2[eg[x].second][eg[x].first] = 0;
}
}
void solve()
{
cin >> n >> m >> q;
unit = sqrt(m);
rep(i, 1, m)
{
cin >> eg[i].first >> eg[i].second;
}
rep(i, 1, q)
{
cin >> s[i].l >> s[i].r;
s[i].id = i;
}
sort(s + 1, s + q + 1, cmp);
// cerr << "flag" << q << endl;
rep(i, 1, q)
{
// cerr << "fl" << endl;
int res = 0;
auto [l, r, id] = s[i];
vec.clear();
// cerr << l << ' ' << r << ' ' << id << endl;
while (curr < r)
{
curr++;
add(curr);
}
while (curr > r)
{
del(curr);
curr--;
}
while (curl < l)
{
del(curl);
curl++;
}
while (curl > l)
{
curl--;
add(curl);
}
rep(i, 1, n)
{
vis[i] = 1;
}
rep(i, 1, n)
{
if (vis[i])
dfs(i);
}
rep(i, 1, n)
{
vis[i] = 1;
}
reverse(ALL(vec));
for (auto v : vec)
{
// cerr << v << ' ';
if (vis[v])
{
cnt = 0;
dfs2(v);
// cerr << "flag" << cnt << endl;
res = res + cnt * (cnt - 1) / 2;
}
}
// cerr << endl;
ans[id] = res;
}
rep(i, 1, q) cout << ans[i] << endl;
}
signed main()
{
freopen("friend.in", "r", stdin);
freopen("friend.out", "w", stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
return 0;
}
D. 旅行计划
6.5k的代码使我的手旋转。
树上对链做询问，还要修改，明显是树链剖分+线段树
一般来说，可以用线段树维护一个dp，但是这题中是没有决策的，也就是存在贪心
那么可以用线段树维护 \(f,g\) 分别表示在点数最小的情况下最多剩多少油，不考虑点数最多剩多少油
我们发现后一种情况的点数可以且最少为前一种情况 \(+1\)，所以这是好维护的
然后考虑拿 \(20\times 20\) 的状态转移仍然不行，这时可以拿初始的状态来转移，因为初始状态下是 \(20\times 1\) 的矩阵，所以每次转移是 \(O(20)\) 的，可以通过
// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e5 + 10;
const int M = 25;
// bool st;
int n;
int a[N];
vector<int> g[N];
struct node
{
int num, val;
bool operator<(node b) const
{
if (num != b.num)
return num < b.num;
return val > b.val;
}
};
struct Matrix
{
node f[M];
int g[M];
Matrix()
{
fill(f, f + M, (node){INF, 0});
memset(g, 0, sizeof(g));
}
void set(int x)
{
rep(i, 1, M - 1)
{
f[i] = {0, i - 1};
g[i] = max(i - 1, x - 1);
}
f[0] = {1, x - 1};
g[0] = x - 1;
}
Matrix operator*(Matrix b) const
{
Matrix res;
rep(i, 0, M - 1)
{
res.f[i] = min((node){f[i].num + b.f[f[i].val].num, b.f[f[i].val].val}, (node){f[i].num + b.f[g[i]].num + 1, b.f[g[i]].val});
res.g[i] = b.g[g[i]];
}
return res;
}
} mat[N];
struct vect
{
node f;
int g;
vect()
{
f = {INF, 0};
g = 0;
}
void clear()
{
f = {0, 0};
g = 0;
}
vect operator*(Matrix b) const
{
vect res;
rep(i, 0, M - 1)
{
res.f = min((node){f.num + b.f[f.val].num, b.f[f.val].val}, (node){f.num + b.f[g].num + 1, b.f[g].val});
res.g = b.g[g];
}
return res;
}
} res;
struct segment_tree
{
#define ls p << 1
#define rs p << 1 | 1
Matrix sum[N << 2][2];
void build(int p, int l, int r)
{
if (l == r)
{
sum[p][0] = sum[p][1] = mat[l];
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
sum[p][0] = sum[ls][0] * sum[rs][0];
sum[p][1] = sum[rs][1] * sum[ls][1];
}
void update(int p, int l, int r, int x)
{
if (l == r)
{
sum[p][0] = sum[p][1] = mat[l];
return;
}
int mid = l + r >> 1;
if (mid < x)
update(rs, mid + 1, r, x);
else
update(ls, l, mid, x);
sum[p][0] = sum[ls][0] * sum[rs][0];
sum[p][1] = sum[rs][1] * sum[ls][1];
}
void query(int p, int l, int r, int ll, int rr, int ty)
{
if (ll <= l && r <= rr)
{
res = res * sum[p][ty];
return;
}
int mid = l + r >> 1;
if (!ty)
{
if (mid >= ll)
query(ls, l, mid, ll, rr, ty);
if (mid < rr)
query(rs, mid + 1, r, ll, rr, ty);
}
else
{
if (mid < rr)
query(rs, mid + 1, r, ll, rr, ty);
if (mid >= ll)
query(ls, l, mid, ll, rr, ty);
}
}
} seg;
int fa[N], top[N], siz[N], dep[N];
int son[N], st[N], en[N], tot, rnk[N];
// bool en;
void dfs(int x, int fat)
{
dep[x] = dep[fat] + 1;
fa[x] = fat;
siz[x] = 1;
for (auto v : g[x])
{
if (v == fat)
continue;
dfs(v, x);
siz[x] += siz[v];
if (!son[x] || siz[son[x]] < siz[v])
son[x] = v;
}
}
void dfs2(int x, int fat, int tp)
{
// cerr << x << ' ' << tp << endl;
top[x] = tp;
st[x] = ++tot;
mat[tot].set(a[x]);
rnk[tot] = x;
if (son[x])
dfs2(son[x], x, tp);
for (auto v : g[x])
{
if (v != son[x] && v != fat)
{
dfs2(v, x, v);
}
}
en[x] = tot;
}
int lca(int u, int v)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
u = fa[top[u]];
}
if (dep[u] < dep[v])
return u;
return v;
}
void calc(int x, int d, int ty)
{
if (!d)
return;
if (dep[x] - dep[top[x]] + 1 <= d)
{
if (!ty)
{
calc(fa[top[x]], d - dep[x] + dep[top[x]] - 1, ty);
seg.query(1, 1, n, st[top[x]], st[x], ty);
}
else
{
seg.query(1, 1, n, st[top[x]], st[x], ty);
calc(fa[top[x]], d - dep[x] + dep[top[x]] - 1, ty);
}
}
else
{
seg.query(1, 1, n, st[x] - d + 1, st[x], ty);
}
}
void solve()
{
cin >> n;
rep(i, 1, n) cin >> a[i];
rep(i, 1, n - 1)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
dfs2(1, 0, 1);
seg.build(1, 1, n);
int q;
cin >> q;
while (q--)
{
char c;
int x, y;
cin >> c >> x >> y;
if (c == 'Q')
{
res.clear();
int p = lca(x, y);
// cerr << x << ' ' << y << ' ' << p << endl;
calc(x, dep[x] - dep[p], 1);
calc(fa[y], dep[y] - dep[p], 0);
cout << res.f.num << endl;
}
else
{
a[x] = y;
mat[st[x]].set(y);
seg.update(1, 1, n, st[x]);
}
}
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
return 0;
}