D - Neighbors (atcoder.jp)

? ? ? ? （1）題意

? ? ? ? ? ? ? ? 給出M組關(guān)系，問(wèn)是否有一個(gè)排列，能表示A[i]和B[i]相鄰

? ? ? ? （2）思路

? ? ? ? ? ? ? ? 考慮如果有環(huán)，顯然不能滿足排列，因?yàn)榕帕兄卸葦?shù)最多為2，若有超過(guò)2的顯然也不行。因此用并查集維護(hù)一下即可。????????

? ? ? ? （3）代碼

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
struct DSU {vector<int> f,siz;int n;DSU(int _n) {n = _n;f.resize(n + 1);siz.resize(n + 1,1);iota(f.begin(),f.end(),0);}inline int find(int x) {if(x == f[x]) return x;return f[x] = find(f[x]);}inline bool same(int x,int y) {x = find(x),y = find(y);return x == y;}inline void merge(int x,int y) {if(same(x,y)) return ;x = find(x),y = find(y);siz[y] += siz[x];f[x] = y;}//目前連通塊個(gè)數(shù)inline int connect() {int res = 0;for(int i = 1;i <= n;i ++) {res += (i == find(i));}return res;}//求某一個(gè)聯(lián)通塊得大小inline int count(int x) {x = find(x);return siz[x];}
};
int deg[N];
void solve()
{int n,m;cin >> n >> m;DSU dsu(n);bool cycle = false;rep(i,1,m) {int u,v;cin >> u >> v;if(dsu.same(u,v)) {cycle = true;}else {dsu.merge(u,v);deg[u] ++,deg[v] ++;}}if(cycle) {cout << "No" << '\n';return;}rep(i,1,n) {if(deg[i] > 2) {cout << "No" << '\n';return;}}cout << "Yes" << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

E - Minimal payments (atcoder.jp)

? ? ? ? （1）題意

? ? ? ? ? ? ? ?阿特科德王國(guó)使用的硬幣有N種： A1?日元、A2?日元、……、AN?日元硬幣。
這里，1=A1?<…<AN?成立，且Ai+1?是每一個(gè)1≤i≤N?1的Ai?的倍數(shù)。

? ? ? ? ? ? ? 如果只用這些硬幣支付一件價(jià)值X日元的商品，那么支付時(shí)使用的硬幣和作為零錢退回的硬幣的最少總數(shù)是多少？

? ? ? ? ? ? ? 當(dāng)Y是一個(gè)至少為X的整數(shù)時(shí)，求正好表示Y日元所需的硬幣數(shù)與正好表示Y?X日元所需的硬幣數(shù)的最小和。

? ? ? ? （2）思路

? ? ? ? ? ? ? ? 對(duì)于每一種支付，我們有兩種決策，要么就是支付到最多的，然后剩下的用小幣去湊，要么就是你多支付一張，小的就湊你多出來(lái)的那部分，因此直接記憶化dp即可。

? ? ? ? （3）代碼

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
ll a[N];
map<ll,map<ll,ll>> dp;
const ll inf = 9e18;
inline ll dfs(ll X,int f)
{if(f == 0 && X) return inf;if(dp[X].count(f)) return dp[X][f];ll r = X % a[f],p = X / a[f];if(!r) return p;return dp[X][f] = min(dfs(r,f - 1) + p,dfs(a[f] - r,f - 1) + p + 1);
}
void solve()
{int n;ll X;cin >> n >> X;rep(i,1,n) cin >> a[i];cout << dfs(X,n);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

F - Jealous Two (atcoder.jp)

? ? ? ? （1）題意

? ? ? ? ? ? ? ? 有一個(gè)長(zhǎng)度為N的A數(shù)組，A[i]代表A對(duì)i這件物品的好感度，有一個(gè)長(zhǎng)度為N的B數(shù)組，B[i]代表B對(duì)i這件物品的好感度，現(xiàn)在讓你求有多少對(duì)[i,j]滿足A[i] >= A[j]并且B[i] <= B[j]。

? ? ? ? （2）思路

? ? ? ? ? ? ? ? 很明顯這是一個(gè)二維偏序問(wèn)題，我們直接sort+樹狀數(shù)組秒了（特殊處理一下重復(fù)的就行）。

? ? ? ? （3）代碼

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 4e5 + 10;
vector<int> ver;
int a[N],b[N];
int get(int x)
{return lower_bound(all(ver),x) - ver.begin() + 1;
}
PII z[N];
template <typename T>
struct Fenwick {const int n;std::vector<T> a;Fenwick (int n) : n(n), a(n + 1) {}void clear() {for(int i = 1;i <= n;i ++) {a[i] = 0;}}void add(int pos, T x) {for (int i = pos; i <= n; i += i & -i) {a[i] += x;}}T query(int x) {T res = 0;for (int i = x; i; i -= i & -i) {res += a[i];}return res;}T query(int l, int r) {if (l == 0 || l > r) {return 0;}return query(r) - query(l - 1);}//找到大于k得第一個(gè)地方T kth(int k) {int pos = 0;for(int j = 31 - __builtin_clz(n);j >= 0;j --) {if(pos + (1 << j) <= n && k > a[pos + (1 << j)]) {pos += 1 << j;k -= a[pos];}}return pos + 1;}
};
//使用Fenwick<ll> fen(n)
void solve()
{int n;cin >> n;rep(i,1,n) {cin >> a[i];ver.pb(a[i]);}rep(i,1,n) {cin >> b[i];ver.pb(b[i]);}sort(all(ver));ll Ans = 0;map<pair<int,int>,int> cnt;rep(i,1,n) {a[i] = get(a[i]);b[i] = get(b[i]);z[i] = {a[i],-b[i]};cnt[z[i]] ++;}for(auto [x,y]: cnt) Ans += 1ll * y * (y - 1) / 2;sort(z + 1,z + 1 + n);Fenwick<int> fen(400000);rep(i,1,n) {fen.add(-z[i].se,1);Ans += i - fen.query(-z[i].se - 1);}cout << Ans;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

H - Minimum Coloring (atcoder.jp)

? ? ? ? （1）題意

? ? ? ? ? ? ? 我們有一個(gè)行數(shù)為H，列數(shù)為W的網(wǎng)格。讓 (i,j)表示從上往下第i行和從左往下第j列的正方形。在這個(gè)網(wǎng)格上有N個(gè)白色棋子，編號(hào)為1到N。棋子i在(Ai?,Bi?)上。你可以支付Ci?的費(fèi)用將棋子i變成黑棋，求每行每列至少有一顆黑子所需的最小總費(fèi)用。

? ? ? ? （2）思路

? ? ? ? ? ? ? ? 很顯然的一個(gè)列拆點(diǎn)，把行向列連邊的費(fèi)用流，不過(guò)這題特殊的是必須行列都有，我們考慮如下建圖。

? ? ? ? ? ? ? ? 把每一行當(dāng)作一個(gè)節(jié)點(diǎn)，從S->i流M的流量，從i->P流m-1的流量，從p向每一列流n-1的流量，從列向t流n的流量，最后給點(diǎn)的邊的[u,v]的價(jià)值w? 相當(dāng)于從u->(v + n)流1的流量費(fèi)用為w，最后跑費(fèi)用流即可。因?yàn)轭}目保證會(huì)出現(xiàn)每行每列至少出現(xiàn)一個(gè)，因此一定會(huì)把n*m的流量流滿。

? ? ? ? （3）代碼

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define uniq(x) x.resize(unique(all(x)) - x.begin())
#define ff first
#define ss second
#define pb push_back
#define emb emplace_back
using namespace std;
using ull = unsigned long long;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;#define RN 100005struct SimplexMinCostMaxFlow {using Flow = ll;using Cost = ll;struct Network {int nxt, to;Flow cap;Cost cost;};Network net_pool[RN * 2];int ncnt = 1;#define nnode(x) net_pool[x]
#define nnxt(x) nnode(x).nxt
#define nto(x) nnode(x).to
#define ncap(x) nnode(x).cap
#define ncost(x) nnode(x).costint head[RN], fa[RN], fe[RN], pi[RN], mark[RN], cyc[RN], ti;inline void addEdge(int u, int v, Flow cap, Cost cost) {nnode(++ncnt) = (Network){head[u], v, cap, cost};head[u] = ncnt;nnode(++ncnt) = (Network){head[v], u, 0, -cost};head[v] = ncnt;}void initTree(int x) {mark[x] = 1;for (int i = head[x]; i; i = nnxt(i)) {int v = nto(i);if (!mark[v] && ncap(i)) {fa[v] = x, fe[v] = i;initTree(v);}}}int phi(int x) {if (mark[x] == ti) return pi[x];return mark[x] = ti, pi[x] = phi(fa[x]) - ncost(fe[x]);}void pushFlow(int e, Cost &cost) {int pen = nto(e ^ 1), lca = nto(e);ti++;while (pen) mark[pen] = ti, pen = fa[pen];while (mark[lca] != ti) mark[lca] = ti, lca = fa[lca];int e2 = 0, f = ncap(e), path = 2, clen = 0;for (int i = nto(e ^ 1); i != lca; i = fa[i]) {cyc[++clen] = fe[i];if (ncap(fe[i]) < f) f = ncap(fe[e2 = i] ^ (path = 0));}for (int i = nto(e); i != lca; i = fa[i]) {cyc[++clen] = fe[i] ^ 1;if (ncap(fe[i] ^ 1) <= f) f = ncap(fe[e2 = i] ^ (path = 1));}cyc[++clen] = e;for (int i = 1; i <= clen; i++) {ncap(cyc[i]) -= f, ncap(cyc[i] ^ 1) += f;cost += 1ll * ncost(cyc[i]) * f;}if (path == 2) return;int laste = e ^ path, last = nto(laste), cur = nto(laste ^ 1);while (last != e2) {mark[cur]--;laste ^= 1;swap(laste, fe[cur]);swap(last, fa[cur]);swap(last, cur);}}pair<Flow, Cost> maxflow(int s, int t) {int lhead = head[s], lhead2 = head[t];addEdge(t, s, 0x7fffffffff, -0x7f7f7f7f);initTree(t);mark[t] = ti = 2, fa[t] = 0;Cost cost = 0;for (int i = 2, pre = ncnt; i != pre; i = i == ncnt ? 2 : i + 1) {if (ncap(i) && ncost(i) < phi(nto(i ^ 1)) - phi(nto(i)))pushFlow(pre = i, cost);}head[s] = lhead, head[t] = lhead2, ncnt -= 2;Flow flow = ncap(ncnt + 2);cost += 1ll * flow * 0x7f7f7f7f;return {flow, cost};}
};SimplexMinCostMaxFlow flow;
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n, m, q;int s, t, p;cin >> n >> m >> q;s = n + m + 1,p = n + m + 2,t = n + m + 3;for(int i = 1;i <= n;i ++) {flow.addEdge(s,i,m,0);flow.addEdge(i,p,m - 1,0);}for(int i = 1;i <= m;i ++) {flow.addEdge(i + n,t,n,0);flow.addEdge(p,i + n,n - 1,0);}for(int i = 1;i <= q;i ++) {int x,y,z;cin >> x >> y >> z;flow.addEdge(x,y + n,1,z);}cout << flow.maxflow(s,t).second;// cout << ans.second << '\n';return 0;
}