1003. 大户爱的宿舍
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e3 + 5;
void init() {}
using ll = long long;
struct Dinic {
struct E {
int v, r;
ll c;
};
int n;
vector<vector<E>> g;
vector<int> dep, cur;
Dinic(int n) : n(n), g(n), dep(n), cur(n) {}
void add(int u, int v, ll c) {
E a{v, (int)g[v].size(), c};
E b{u, (int)g[u].size(), 0};
g[u].push_back(a);
g[v].push_back(b);
}
bool bfs(int s, int t) {
fill(dep.begin(), dep.end(), -1);
queue<int> q;
dep[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto &e : g[u]) {
if (e.c && dep[e.v] == -1) {
dep[e.v] = dep[u] + 1;
q.push(e.v);
}
}
}
return dep[t] != -1;
}
ll dfs(int u, int t, ll f) {
if (u == t || !f)
return f;
for (int &i = cur[u]; i < (int)g[u].size(); i++) {
E &e = g[u][i];
if (!e.c || dep[e.v] != dep[u] + 1)
continue;
ll x = dfs(e.v, t, min(f, e.c));
if (!x)
continue;
e.c -= x;
g[e.v][e.r].c += x;
return x;
}
return 0;
}
ll flow(int s, int t) {
const ll inf = numeric_limits<ll>::max() / 4;
ll ans = 0, f;
while (bfs(s, t)) {
fill(cur.begin(), cur.end(), 0);
while ((f = dfs(s, t, inf))) ans += f;
}
return ans;
}
};
void solve() {
int n, k;
cin >> n >> k;
int s = n + k + 1, t = n + k + 2;
int l = 0, r = n / k, res = 0;
vector<string> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
while (l <= r) {
int mid = (l + r) / 2;
Dinic dinic(n + k + 3);
for(int i=0;i<n;i++)dinic.add(s,i,1);
for(int i=0;i<k;i++)dinic.add(i+n,t,mid);
for (int i = 0; i < n; i++) {
for(int j=0;j<k;j++){
if(a[i][j]=='1'){
dinic.add(i,j+n,1);
}
}
}
// cout<<l<<" "<<r<<" "<<mid<<" "<<endl;
if(dinic.flow(s,t)==mid*k){
res=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
cout << res << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}1004. 大户爱的干草堆
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 1e5 + 5;
vi p[N];
void init() {
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i) p[j].pb(i);
}
}
void solve() {
int n, q;
cin >> n >> q;
vi a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vvpii qs(n + 1);
vi d(q);
for (int i = 0; i < q; i++) {
int x, y, k;
cin >> x >> y >> k;
d[i] = k;
qs[x - 1].pb(mp(i, k));
qs[y].pb(mp(i, k));
}
vvi q1(q);
vi cnt(N);
for(int i = 0; i <= n; i++){
for(auto x: p[a[i]]){
cnt[x]++;
}
for(auto x: qs[i]){
vi tmp;
for(auto y: p[x.s]){
tmp.pb(cnt[y]);
}
if(q1[x.f].empty())q1[x.f]=tmp;
else{
for(int j = 0; j < sz(q1[x.f]); j++)q1[x.f][j]=tmp[j]-q1[x.f][j];
}
}
}
for(int i = 0; i < q; i++){
for(int j=sz(q1[i])-1; j>=0; j--){
for(int k=j+1; k<sz(q1[i]); k++)if(p[d[i]][k]%p[d[i]][j]==0)q1[i][j]-=q1[i][k];
}
int res=0;
for(int j=0; j<sz(q1[i]); j++)res+=q1[i][j]*p[d[i]][j]*p[d[i]][j];
cout<<res<<endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}1005. 大户爱的生成树2
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 1e5 + 5;
void init() {}
struct StoerWagner {
int n;
vector<vector<long long>> g;
StoerWagner(int n) : n(n), g(n, vector<long long>(n)) {}
void add(int u, int v, long long w) {
if (u == v)
return;
g[u][v] += w;
g[v][u] += w;
}
long long flaw() {
const long long INF = (1LL << 62);
vector<int> v(n);
iota(v.begin(), v.end(), 0);
long long ans = INF;
while (v.size() > 1) {
int m = v.size();
vector<long long> w(n, 0);
vector<bool> vis(n, false);
int pre = -1, last = -1;
for (int i = 0; i < m; i++) {
int sel = -1;
for (int x : v) {
if (!vis[x] && (sel == -1 || w[x] > w[sel])) {
sel = x;
}
}
vis[sel] = true;
if (i == m - 1) {
last = sel;
ans = min(ans, w[last]);
for (int x : v) {
if (x == pre || x == last)
continue;
g[pre][x] += g[last][x];
g[x][pre] = g[pre][x];
}
v.erase(find(v.begin(), v.end(), last));
break;
}
pre = sel;
for (int x : v) {
if (!vis[x]) {
w[x] += g[sel][x];
}
}
}
}
return ans;
}
};
void solve() {
int n, m;
cin >> n >> m;
StoerWagner sw(n);
while (m--) {
int u, v, w;
cin >> u >> v >> w;
sw.add(u - 1, v - 1, w);
sw.add(v - 1, u - 1, w);
}
cout << sw.flaw() * (n - 1) / 2 << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}1006. 恋恋的序列
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';
template <typename T>
struct Segment {
int n;
vector<T> tree, lazy;
vector<bool> tag;
Segment(int _n) : n(_n) {
tree.assign(n * 4 + 5, T());
lazy.assign(n * 4 + 5, T());
tag.assign(n * 4 + 5, 0);
}
void build(const vector<T> &a, int p, int l, int r) {
if (l == r) {
tree[p] = a[l];
return;
}
int mid = (l + r) >> 1;
build(a, p << 1, l, mid);
build(a, p << 1 | 1, mid + 1, r);
tree[p] = tree[p << 1] + tree[p << 1 | 1];
}
void push(int p, int l, int r) {
if (!tag[p]) return;
int mid = (l + r) >> 1;
T v = lazy[p];
tree[p << 1] = v * (mid - l + 1);
tree[p << 1 | 1] = v * (r - mid);
lazy[p << 1] = lazy[p << 1 | 1] = v;
tag[p << 1] = tag[p << 1 | 1] = 1;
tag[p] = 0;
}
void update(int p, int l, int r, int ql, int qr, T v) {
if (ql <= l && r <= qr) {
tree[p] = (r - l + 1) * v;
lazy[p] = v;
tag[p] = 1;
return;
}
push(p, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) update(p << 1, l, mid, ql, qr, v);
if (qr > mid) update(p << 1 | 1, mid + 1, r, ql, qr, v);
tree[p] = tree[p << 1] + tree[p << 1 | 1];
}
T query(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[p];
push(p, l, r);
T res = T();
int mid = (l + r) >> 1;
if (ql <= mid) res += query(p << 1, l, mid, ql, qr);
if (qr > mid) res += query(p << 1 | 1, mid + 1, r, ql, qr);
return res;
}
};
void solve() {
//cout << "------------------\n";
int n, m;
cin >> n >> m;
vector<int> a(n + 2);
for (int i = 1; i <= n; i ++) cin >> a[i];
vector<int> b(n + 2);
for (int i = 2; i <= n; i ++) {
b[i] = (a[i] != a[i - 1]);
}
n ++;
Segment<int> seg(n);
seg.build(b, 1, 1, n);
for (int i = 1; i <= m; i ++) {
int op;
cin >> op;
if (op == 1) {
int l, r, x;
cin >> l >> r >> x;
if (l == 1) {
int suc = a[1] ^ (seg.query(1, 1, n, 1, r + 1) % 2);
seg.update(1, 1, n, 1, r, 0);
if (suc == x) seg.update(1, 1, n, r + 1, r + 1, 0);
else seg.update(1, 1, n, r + 1, r + 1, 1);
} else {
int pre = a[1] ^ (seg.query(1, 1, n, 1, l - 1) % 2);
int suc = a[1] ^ (seg.query(1, 1, n, 1, r + 1) % 2);
seg.update(1, 1, n, l + 1, r, 0);
if (pre == x) seg.update(1, 1, n, l, l, 0);
else seg.update(1, 1, n, l, l, 1);
if (suc == x) seg.update(1, 1, n, r + 1, r + 1, 0);
else seg.update(1, 1, n, r + 1, r + 1, 1);
}
} else if (op == 2) {
int l, r;
cin >> l >> r;
if (l == 1) {
int se = seg.query(1, 1, n, r + 1, r + 1);
seg.update(1, 1, n, r + 1, r + 1, se ^ 1);
a[1] ^= 1;
} else {
int fi = seg.query(1, 1, n, l, l);
seg.update(1, 1, n, l, l, fi ^ 1);
int se = seg.query(1, 1, n, r + 1, r + 1);
seg.update(1, 1, n, r + 1, r + 1, se ^ 1);
}
} else {
int l, r;
cin >> l >> r;
cout << seg.query(1, 1, n, l + 1, r) << '\n';
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t --) solve();
}1007. 小白的烦恼
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 1e5 + 5;
void init() {}
void solve() {
int n, m, q;
cin >> n >> m >> q;
vpii a(n);
int B = ceil(sqrt(n));
int B1 = ceil(sqrt(m));
struct Tq {
int mn;
vector<int> v, cnt;
Tq(int sz1, int sz2) : mn(sz2), v(sz1, sz2), cnt(sz2 * 2 + 1) {
cnt[sz2]=sz1;
}
void add(int i, int x) {
cnt[v[i]]--;
v[i] += x;
cnt[v[i]]++;
if (cnt[mn] == 0)
mn++;
if (v[i] < mn)
mn = v[i];
}
};
for (int i = 0; i < n; i++) cin >> a[i].f;
for (int i = 0; i < n; i++) cin >> a[i].s;
vi res(q);
vector<pair<pii,pii>> qq(q);
for(int i = 0; i < q; i++)cin>>qq[i].f.f>>qq[i].f.s>>qq[i].s.f,qq[i].s.s=i;
sort(all(qq),[&](pair<pii,pii> a,pair<pii,pii> b){
if(a.f.f/B==b.f.f/B)return a.f.s<b.f.s;
return a.f.f/B<b.f.f/B;
});
vector<Tq> tq;
for(int i=1;i<=m;i+=B1){
tq.pb(Tq(min(m-i+1,B1),n));
}
auto add=[&](int i,int x){
int j=i/B1;
tq[j].add(i%B1,x);
};
auto del=[&](int i,int x){
int j=i/B1;
tq[j].add(i%B1,-x);
};
int l=-1,r=-1;
for(int i=0;i<q;i++){
auto [p,x1]=qq[i];
auto [ll,rr]=p;
auto [x,y]=x1;
ll-=2,rr--;
x+=n;
while(r<rr)add(a[r+1].f-1,a[r+1].s),r++;
while(r>rr)del(a[r].f-1,a[r].s),r--;
while(l<ll)del(a[l+1].f-1,a[l+1].s),l++;
while(l>ll)add(a[l].f-1,a[l].s),l--;
int ans=-1;
for(int i=0;i<tq.size();i++){
if(tq[i].mn<=x){
for(int j=0;j<tq[i].v.size();j++)
if(tq[i].v[j]<=x){
ans=j+i*B1+1;
break;
}
break;
}
}
res[y]=ans;
}
for(int i:res)cout<<i<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}1008. 恋恋的排列
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
ll a[N], pre[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int n;
ll ma = -1e18, mi = 1e18, t = 0;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
t = min(a[i], t + a[i]);
ma = max({ma, pre[i], pre[i] - mi});
mi = min(mi, t);
}
cout << ma << '\n';
}
return 0;
}1010. 歪歪朋友圈
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e3 + 5;
void init() {}
void solve() {
int n, m;
cin >> n >> m;
vi a(n * m), b(n * m);
for (int i = 0; i < n * m; i++) cin >> a[i];
for (int i = 0; i < n * m; i++) cin >> b[i];
map<int, int> c;
for (int i = 0; i < n * m; i++) c[a[i]] = i;
for (int i = 0; i < n * m; i++) b[i] = c[b[i]];
set<int> s;
for (int i = 0; i < n * m; i++) {
auto it = s.upper_bound(b[i]);
if (it != s.end())
s.erase(it);
s.insert(b[i]);
}
cout << n * m - sz(s) << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}1011. 奶蛙的奶糖
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
if (n <= 2) cout << 2 << '\n';
else if (n <= 17) cout << 17 << '\n';
else if (n <= 687) cout << 687 << '\n';
else cout << -1 << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t --) solve();
}