整理的演算法模板合集： ACM模板
點我看演算法全家桶系列！！！
實際上是一個全新的精煉模板整合計劃
目錄
- A. Shifting Stacks
- B - Eastern Exhibition
- C1 - Guessing the Greatest (easy version)
- C2 - Guessing the Greatest (hard version)
- D - Max Median
- E - Paired Payment
- F - Pairs of Paths
A. Shifting Stacks
Translation
你有 n n n 堆積木，第 i i i 個堆疊包含 h i h_i hi? 塊，它的高度是這堆積木的數量，在一次移動中，你可以從第 i i i 個堆疊中取出一個積木（如果至少有一個積木的話）并將其放入第 i + 1 i +1 i+1 個堆積木中，問你能否將讓積木的高度序列嚴格遞增？
注意，堆疊的數量始終保持不變，也就是說哪怕這堆里沒有積木了，這個堆也不會消失，
Solution
簽到題 ~
很明顯我們只需要構造出一個 0 , 1 , 2 , ? n + 好 多 0,1,2,\cdots n+ 好多 0,1,2,?n+好多 的序列即可，就是前面的都堆到最后面，中間不夠的話也可以借給他，然后就沒了 ~
AC Code
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 2e5 + 7;
const ll INF = 4e18;
int n, m, t;
int a[N], b, k1, k2;
bool solve()
{
ll ans = 0;
scanf("%d", &n);
for(int i = 1;i <= n; ++ i) {
scanf("%d", &a[i]);
}
int x = 0;
for(int i = 1; i <= n; ++ i, x ++ ) {
if(a[i] > x) {
ans += a[i] - x;
a[i] = x;
}
else {
ll tmp = x - a[i];
if(ans < tmp) {
puts("NO");
return ;
}
else ans -= tmp;
}
}
puts("YES");
}
int main()
{
scanf("%d", &t);
while(t -- ) {
solve();
}
}
B - Eastern Exhibition
Problem
Translation
你和你的朋友住在 n n n 個房子里（？），每個房子都位于一個二維的平面上，在一個點上有整數坐標，同一地點可能有好多個不同的房子擠一塊（），市長問你展覽館要建到哪里，請你輸出所有房子到這個展覽館的距離最近的點的數量（必須是整數點），注意展覽館同樣可以建在其他房子頭上（霧），定義兩點 ( x 1 , y 1 ) (x_1,y_1) (x1?,y1?) 和 ( x 2 , y 2 ) (x_2,y_2) (x2?,y2?) 之間的距離為 ∣ x 1 ? x 2 ∣ + ∣ y 1 ? y 2 ∣ |x_1-x_2|+|y_1-y_2| ∣x1??x2?∣+∣y1??y2?∣，
Solution
簽到題 ~
很明顯這就是中位數的板子題，但是它把一維拓展到了二維，但是沒什么區別
首先考慮一維怎么算，首先若 n n n 是奇數，很明顯答案就一定是 1 1 1，中位數固定了，
若是偶數，那么中間的那兩個點之間的坐標都可以建（包括兩個點，因為可以建到房子頭上），那么對于二維來說，就是這個矩形里的所有的點都可以建唄，就乘起來 ~ 沒了…
AC Code
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 2e4 + 7;
const ll INF = 4e18;
int n, m, t;
int x[N], y[N];
void solve()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) {
scanf("%d%d", &x[i], &y[i]);
}
sort(x + 1, x + 1 + n);
sort(y + 1, y + 1 + n);
ll numx = x[n / 2 + 1] - x[n / 2] + 1;
ll numy = y[n / 2 + 1] - y[n / 2] + 1;
if(n & 1)
printf("1\n");
else printf("%lld\n", numx * numy);
}
int main()
{
scanf("%d", &t);
while(t -- ) {
solve();
}
}
C1 - Guessing the Greatest (easy version)
C2 - Guessing the Greatest (hard version)
直接寫的正解，然后這兩題就一樣了，所以就放一塊了 ~
先睡覺
題解待更…
AC Code
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
typedef int itn;
const ll INF = 4e18;
inline int read()
{
int re=0,k=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
return re*k;
}
int n, m, t, p;
int ask(int l, int r)
{
if(l == r) return -1;
printf("? %d %d\n", l, r);
fflush(stdout);
int res;
scanf("%d", &res);
return res;
}
bool check(int l, int r)
{
return ask(l, r) == p;
}
void solve()
{
scanf("%d", &n);
p = ask(1, n);
int l, r, mid;
if(ask(p, n) == p) {
l = p;
r = n;
while(l <= r) {
mid = (l + r) >> 1;
if(check(p, mid)) {
r = mid - 1;
}
else l = mid + 1;
}
printf("! %d\n", l);
fflush(stdout);
}
else {
l = 1;
r = p;
while(l <= r) {
mid = (l + r) >> 1;
if(check(mid, p)) {
l = mid + 1;
}
else r = mid - 1;
}
printf("! %d\n", r);
fflush(stdout);
}
}
int main()
{
solve();
}
D - Max Median
題解待更…
AC Code
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 2e5 + 7;
const int INF = N * 10;
int n, m, t, k;
int a[N], b, k1, k2;
itn sum[N];
bool check(int mid)
{
int minn = INF;
for(int i = 1; i <= n; ++ i) {
int val;
if(a[i] >= mid) val = 1;
else val = -1;
sum[i] = sum[i - 1] + val;
if(i >= k)
minn = min(minn, sum[i - k]);
if(minn < sum[i]) return true;
}
return false;
}
void solve()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
}
int l = 1, r = n, ans;
while(l <= r) {
int mid = l + r >> 1;
if(check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
printf("%d\n", ans);
}
int main()
{
solve();
}
E - Paired Payment
Translation
有
n
n
n 城市和
m
m
m 條無向邊，形成一個無向加權圖但不保證連通，每條邊都有一個權值
w
w
w，政府制定了一項新的法律：你從一個城市出發，一次必須連續走兩條路才能到達另一個城市，假設從
a
a
a 到
b
b
b ，再從
b
b
b 到
c
c
c ，相當于僅從
a
a
a 走到了
c
c
c ，中間城市僅路過不到達，花費的金額為
(
w
a
b
+
w
b
c
)
2
(w_{ab}+w_{bc})^2
(wab?+wbc?)2，問從起點
1
1
1 開始到其余所有點的最小花費，若無法到達輸出 -1 ，
2 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ m i n ( n ? ( n ? 1 ) 2 , 2 ? 1 0 5 ) 2 \leq n \leq 10^5,1 \leq m \leq min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5) 2≤n≤105,1≤m≤min(2n?(n?1)?,2?105)
對于每一條邊（保證無重邊）
1 ≤ v i , u i ≤ n , 1 ≤ w i ≤ 50 , u i ≠ v i 1 \leq v_i, u_i \leq n,1 \leq w_i \leq 50,u_i \neq v_i 1≤vi?,ui?≤n,1≤wi?≤50,ui??=vi?
Solution
很明顯就是一個最短路問題，看上去直接跑一個 Dijkstra 就行了，但是本題特殊就特殊在行走的方式不同，這里每一條直接連通的邊并不能直接到達，每次行動必須有一個中間城市作為跳板，且花費為 ( w a b + w b c ) 2 (w_{ab}+w_{bc})^2 (wab?+wbc?)2，看上去好像沒法做，因為如果直接暴力連邊，那么對于每一條邊來說，需要與它下一條邊組合起來再連接，時間復雜度光連邊就需要 O ( n 2 ) O(n^2) O(n2) …
一步一步來，首先給你的直接相連的邊是一定要連起來的，但是肯定不是 Dijkstra 中可以走的邊，所以 “經典” 思路，我們要把他們連到虛擬映射點上把他們區分開，具體怎么映射現在還不知道，因為不能暴力連邊，點數很大，所以我們考慮一下能不能預處理出一張可以直接轉移的圖來跑最短路，我們來分析一下邊和點的性質，
根據題意，我們一次移動需要跳過一個城市，所以對于每一個城市（點）來說只有兩個狀態，一個是作為中間節點，被跳過去，一個是作為終點，到達，所以我們可以朝著這個方向思考如何分別表示這兩個狀態，由于我們每次只輸入一條邊，也就意味著我們知道當前這條邊的權值，但是不知道下一條邊（下一層）的權值，也不知道上一條邊（上一層）的權值，好像沒法玩了，但是如果你仔細讀題就會發現， w ≤ 50 w\le50 w≤50 ！哦，那沒事了， 也就是說我們一共只有 50 50 50 種情況，我們就可以將這 50 50 50 種邊全部連起來，連的時候分別分配一個虛擬節點，然后算出它們的這一整條路（兩條拼一塊）的實際權值（連了不一定用嘛），我們在轉移的時候只需要從虛擬起點出發經過題目中給定的路線在虛擬圖中的映射最終到達虛擬終點即可，這就是解題的大致思路，
解釋一下就是：我們假設當前邊為 ( x , y , w ) (x,y,w) (x,y,w) ，我們現在要給他建圖，那么對于這條邊的兩端 x x x 和 y y y，一共只有兩種情況：
情況一：點 x x x 作為中間結點，上一層 a a a 跳過 x x x 到達 y y y
情況二：點 x x x 作為上一次轉移的終點同時也是這一次轉移的起點，跳過 y y y 到達下一層 b b b
分別來分析：
對于情況一，我們現在已知從 x x x 到 y y y 的邊的權值 w w w ，不知道從 a a a 到 x x x 的權值，那么我們就可以先列舉 1 → 50 1\to50 1→50 作為從 a a a 到 x x x 的權值，這樣我們現在已知的資訊為：上一層到中間節點 x x x 的距離， x x x 到終點 y y y 的距離，
對于情況二，我們現在已知從 x x x 到 y y y 的邊的權值 w w w ，不知道從 y y y 到 b b b 的權值，那么我們同樣列舉 1 → 50 1\to50 1→50 作為從 y y y 到 b b b 的權值，這樣我們現在已知的資訊為： x x x 到中間節點 y y y 的距離， y y y 到下一層終點 b b b 的距離，
所以考慮如何根據這些已知條件的同性設計出一個 hash映射函式來得到虛擬點的下標，就是一個很經典的 hash，我們知道每個節點的下標 x x x，和權值 w w w，我們可以令 h a s h = x × p + w hash =x\times p+w hash=x×p+w，我們設中間節點的 w w w 為邊的權值，終點的 w w w 為 0 0 0 ，就好像是上半段往下半段匹配一樣，因為每一半段都只有自己的權值大小，我們就按照這個性質去設計，
這樣我們就得到了建圖代碼：
void add(itn x, int y, int w)
{
__add(Hash(x, 0), Hash(y, w), 0);
for(int i = 1; i <= 50; ++ i) {
__add(Hash(x, i), Hash(y, 0), (i + w) * (i + w));
}
}
這樣我們轉移的時候，對于情況二，從邊 ( x , y , w 1 ) (x,y,w1) (x,y,w1) 開始，從 H a s h ( x , 0 ) Hash(x, 0) Hash(x,0) 經過 H a s h ( y , w 1 ) Hash(y, w1) Hash(y,w1) （權值為 0 0 0），這里的 H a s h ( y , w 1 ) Hash(y,w1) Hash(y,w1) 的hash值等于下一條邊 ( k , z ， w 2 ) (k,z，w2) (k,z，w2) 的中間結點列舉到的 w 1 w1 w1 ，即 H a s h ( k , w 1 ) Hash(k,w1) Hash(k,w1)（題中給的路線）也就是 y = k y=k y=k，然后從 H a s h ( k , w 1 ) Hash(k, w1) Hash(k,w1) 到 H a s h ( z , 0 ) Hash(z, 0) Hash(z,0)，權值為已經預處理好的 ( w 1 + w 2 ) 2 (w1+w2)^2 (w1+w2)2，
至于這里hash里的 p p p ，取一個大于 50 50 50 的質數就行了，不要太大，大了會RE
建完圖以后，我們只需要從起點
1
1
1 的虛擬映射點出發跑一遍 Dijkstra ，最終每個點的最短路就是每個點的虛擬映射的 dist ，
最后注意一共 m ≤ 2 × 1 0 5 m\le2\times 10^5 m≤2×105，每條邊需要連 52 × 2 = 104 52\times2=104 52×2=104，總邊數為 2 × 1 0 7 + 8 2\times 10^7+8 2×107+8，前向星開不下，所以改成 vector 存邊就行了
AC Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e7 + 7, M = 1e7 + 7, mod = 1e9 + 7, INF = 0x3f3f3f3f;
typedef long long ll;
typedef int itn;
typedef pair<int, int> PII;
int n, m, k, t;
int dist[M];
typedef struct
{
itn y, w;
}edge;
vector<edge>G[M];
int Hash(int x, int w)
{
return x * 57 + w;
}
void __add(int x, int y, int w)
{
G[x].push_back((edge){y, w});
}
void add(itn x, int y, int w)
{
__add(Hash(x, 0), Hash(y, w), 0);
for(int i = 1; i <= 50; ++ i) {
__add(Hash(x, i), Hash(y, 0), (i + w) * (i + w));
}
}
void dijkstra(int S)
{
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
priority_queue<PII, vector<PII>, greater<PII> >q;
q.push({0, S});
while(q.size()) {
itn x = q.top().second;
int d = q.top().first;
q.pop();
if(d != dist[x]) continue;
for(auto it : G[x]) {
itn y = it.y, w = it.w;
if(dist[y] > d + w) {
dist[y] = d + w;
q.push({dist[y], y});
}
}
}
}
int main()
{
//init();
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
add(x, y, w);
add(y, x, w);
}
dijkstra(Hash(1, 0));
for(int i = 1; i <= n; ++ i) {
if(dist[Hash(i, 0)] == INF) dist[Hash(i, 0)] = -1;
printf("%d ", dist[Hash(i, 0)]);
}
puts("");
return 0;
}
F - Pairs of Paths
待更…
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/261428.html
標籤：其他
上一篇：Android：View的getLocalVisibleRect（）和getGlobalVisibleRect（）的區別