整理的演算法模板合集: ACM模板
點我看演算法全家桶系列!!!
實際上是一個全新的精煉模板整合計劃
目錄
- A - Yet Another String Game
- B - The Great Hero
- C. Searching Local Minimum
- D1 - Painting the Array I
- D2 - Painting the Array II
- E - Continuous City

這場打的頭疼,先更一下C題吧,其他的幾道題明天醒了再更…
現在腦子不太清醒,先口胡一個最簡單的C吧…
來了來了,更一下 A ~ E
(實際上是昨天快兩點才睡著,快九點了才起床,十點才吃完飯開始寫
比賽鏈接:https://codeforces.com/contest/1480
A - Yet Another String Game
Problem 1480A - Yet Another String Game
Alice和 Bob 在玩游戲,Alice 先手,給定一個字串,他們每次可以進行一個操作:讓任意一個沒有被選過的位置上的字符變成另一個不一樣的字符,Alice 想讓字串最后的字典序最小,Bob 想讓字串最后的字典序最大,兩位都會進行最優的操作,請問最后字串會變成什么鬼樣子 ~
Solution
簽到題
模擬一下就行了,兩位都盡量朝著自己的方向去選,所以Alice先選一定選第一個,然后 Bob 會選第二個,為了使得序列的字典序盡可能的打,所以就是奇偶交替進行…
Code
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 50007;
int n, m, t;
string a, b;
int main()
{
scanf("%d", &t);
while(t -- ) {
cin >> a;
int len = a.length();
int cnt = 0, cnt1 = len, num = 0;
for(int i = 0; i < len; ++ i){
if(!(i & 1)) {
if(a[i] == 'a') a[i] = 'b';
else a[i] = 'a';
}
else {
if(a[i] == 'z') a[i] = 'y';
else a[i] = 'z';
}
}
cout << a << endl;
}
return 0;
}
B - The Great Hero
Problem 1480B - The Great Hero
我們的攻擊力為 A A A ,血量為 B B B ,面對 n n n 只怪,其中第 i i i 只怪的攻擊力為 a i a_i ai? ,血量為 b i b_i bi? ,我們可以無限次地攻擊任意一只怪,每次我們和怪都會掉血,規則參見正常的 RPG 游戲,就是當血量小于等于0時,死亡,每次我們和一只怪激情對砍,我們掉 a i a_i ai? 的血量,怪掉 A A A 的血量,請問我們最后能否消滅所有的怪,哪怕在最后一擊之后同歸于盡,
Solution
一個簡單的貪心,開始還以為是一個模擬,然后立馬發現,因為可以同歸于盡,所以我們最后一擊要用到正確的地方,因為我們打的順序無所謂,所以可能存在一種情況,我隨便打,中間死了,但是我把攻擊力最大的哪個怪,放到最后跟他同歸于盡,就會最后死,答案從 NO 變成了 YES,
然后再來分析這么解決,
首先很明顯,對于第 i i i 只怪,我們需要 ? b i A ? \lceil \frac{b_i}{A} \rceil ?Abi??? 次才能打死它,然后每次會掉 a i a_i ai? 的血,如果直接打死它的話,會掉 ? b i A ? × a i \lceil \frac{b_i}{A} \rceil\times a_i ?Abi???×ai? 的血,
所以我們就先模擬一遍,打一遍,然后最后的血量加上攻擊力最大的那只怪的攻擊力,相當于就是把這只放到最后打,要是加上之后的血量大于0,說明成功,否則中間就死了…
因為我特判的是 >0 而不是 >=0 ,我先扣掉了所有的血,再加上最大攻擊力,如果我這時候剩余的血量 >0 說明我活到了最后一只攻擊力最大的怪 例如這個
1
10 10 2
2 1000
50 10
答案就是NO,我的代碼也是NO,我沒辦法活到1000的那個怪 ~
Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef int itn;
const int N = 5e5 + 7, M = 1e6 + 7, mod = 1e9 + 7;
const ll INF = 1e18 + 7;
ll n, m, t;
ll A, B;
PLL a[N];
bool solve()
{
scanf("%lld%lld%lld", &A, &B, &n);
ll maxx = -INF;
for(int i = 1; i <= n; ++ i) {
scanf("%lld", &a[i].x);
maxx = max(maxx, a[i].x);
}
for(int i = 1; i <= n; ++ i) {
scanf("%lld", &a[i].y);
}
ll sum = 0;
for(int i = 1; i <= n; ++ i) {
ll cnt = ceil(a[i].y * 1.0 / A);
sum += cnt * a[i].x;
}
B -= sum;
B += maxx;
if(B > 0) return true;
else return false;
}
int main()
{
scanf("%lld", &t);
while(t -- ) {
bool ans = solve();
if(ans) puts("YES");
else puts("NO");
}
return 0;
}
C. Searching Local Minimum
Problem 1479A - Searching Local Minimum
互動題,有一個 1 1 1 ~ n n n 的一個排列,只會給你 n n n 的值,求一個為 V 字形的數的下標,其中 V 字形數是指下標為 i i i 的一個數, a i ? 1 ≥ a i ≤ a i + 1 a_{i-1}\ge a_i\le a_{i+1} ai?1?≥ai?≤ai+1? ,想讓你找到的這個 i i i,你每次可以詢問這個排列的一個下標的值,你最多可以問 100次,
1 ≤ n ≤ 1 0 5 1\le n \le 10^5 1≤n≤105
Solution
因為題目要找的是一個 v 字形的數,也就是 a i ? 1 ≥ a i ≤ a i + 1 a_{i-1}\ge a_i\le a_{i+1} ai?1?≥ai?≤ai+1? 的這個 i i i,
資料 1 0 5 10^5 105
如果 a i ≤ a i + 1 a_i\le a_{i+1} ai?≤ai+1? 那么 一定 a i ≥ a i ? 1 a_i\ge a_{i-1} ai?≥ai?1? ,不然 i i i 就是答案,同理, a i ≥ a i ? 1 a_i\ge a_{i-1} ai?≥ai?1?,那么 a i ? 1 ≥ a i ? 2 a_{i-1}\ge a_{i-2} ai?1?≥ai?2? ,一次類推,一定是一個單調的
同理若
a
i
≥
a
i
+
1
a_i\ge a_{i+1}
ai?≥ai+1? 也一樣單調,所以二分就行了,若 a[mid] 大于右邊,則答案在左邊…
沒了,睡覺睡覺
Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef int itn;
const int N = 5e3 + 7, M = 1e6 + 7, mod = 1e9 + 7;
const ll INF = 1e18 + 7;
int n, m, t, k, q;
int a[N];
int vis[M];
PII ans[N];
int ask(int x)
{
printf("? %d\n", x);
fflush(stdout);
int res;
scanf("%d", &res);
return res;
}
void solve()
{
int l = 1, r = n;
while(l < r) {
int mid = l + r >> 1;
int rr = ask(mid + 1);
int midd = ask(mid);
if(midd < rr) r = mid;
else l = mid + 1;
}
printf("! %d\n", l);
fflush(stdout);
return ;
}
int main()
{
scanf("%d", &n);
solve();
return 0;
}
D1 - Painting the Array I
Problem 1479B1 - Painting the Array I
給你一個序列 a a a,請你將這個序列撕開分成兩個序列 a ( 0 ) a^{(0)} a(0) 和 a ( 1 ) a^{(1)} a(1),使得將 a ( 0 ) a^{(0)} a(0) 和 a ( 1 ) a^{(1)} a(1) 合并所有相鄰且相同的元素之后,兩個序列剩余的元素個數和最大,
例如:
1 2 3 1
1 2 3 2
答案均為4,
Solution
我們發現直接遇見兩個一樣的就直接加2什么的暴力算的話不一定對,因為后面可能會出現多算的情況,就是你以為分開就好了,可以加,但是它卻和放到的新序列的前一個元素重復,這樣就多加了,
例如:
4 4 2 4 4
答案應該是 4 而不是 5 ,
所以要考慮貪心,分類討論后面可能會發生的情況,
我們一步一步分析,
我們首先設 a ( 0 ) a^{(0)} a(0) 序列的最后一個元素為 x x x , a ( 1 ) a^{(1)} a(1) 的最后一個元素為 y y y ,
分類討論,我們分別考慮什么情況的時候,把當前元素分配給哪一個序列會更優,
對于當前準備去分配的元素 z 1 z1 z1,以及 z 1 z1 z1 后面一位元素 z 2 z2 z2,
(1) 考慮對前面的貢獻
- 當
x == y時,上下兩個序列都無所謂, - 當
x == z1 && y != z1時,很明顯分配給 y y y 會更優, - 當
y == z1 && x != z1時,很明顯分配給 x x x 會更優,
(2) 考慮對后面的貢獻
- 當
x == z2 && y != z2時,很明顯分配給 x x x 會更優,因為可能 z 1 z1 z1 可以填上這個合并的漏洞,填不上的話,就算了,但會更優 - 當
y == z2 && x != z2時,同理很明顯分配給 y y y 會更優, - 當
x == y == z2那就無所謂了 ~ 給誰都行
剩余的所有情況應該像D2那樣去判斷與 x x x , y y y 相同的元素的距離誰最近,就放到誰后面,具體思路 / 證明看下面的 D2 的題解,這里可能是因為資料較弱,所以過掉了,然后我也懶得改了 ~ (往下滑就看到了)
Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 5e6 + 7, M = 6e6 + 7, mod = 1e9 + 7;
const ll INF = 1e18 + 7;
int n, m, t, k;
itn a[N];
int vis[N];
void solve()
{
int ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
}
int x = -1, y = -1;
for(int i = 1; i <= n; ++ i) {
itn z1 = a[i], z2 = a[i + 1];
if(z1 == x && z1 == y) continue;
if(z1 == x) {
y = z1;
ans ++ ;
}
else if(z1 == y) {
x = z1;
ans ++ ;
}
else {
ans ++ ;
if(z2 == x && z2 != y) {
x = z1;
}
else if(z2 == y && z2 != x) {
y = z1;
}
else x = z1;
}
}
printf("%d\n", ans);
}
int main()
{
solve();
return 0;
}
D2 - Painting the Array II
Problem 1479B2 - Painting the Array II
給你一個序列 a a a,請你將這個序列撕開分成兩個序列 a ( 0 ) a^{(0)} a(0) 和 a ( 1 ) a^{(1)} a(1),使得將 a ( 0 ) a^{(0)} a(0) 和 a ( 1 ) a^{(1)} a(1) 合并所有相鄰且相同的元素之后,兩個序列剩余的元素個數和最小,
Solution
我們先按照上面 D1 的貪心策略分析,
我們首先設 a ( 0 ) a^{(0)} a(0) 序列的最后一個元素為 x x x , a ( 1 ) a^{(1)} a(1) 的最后一個元素為 y y y ,
分類討論,我們分別考慮什么情況的時候,把當前元素分配給哪一個序列會更優,使得序列最短,
對于當前準備去分配的元素 z 1 z1 z1,以及 z 1 z1 z1 后面一位元素 z 2 z2 z2,
(1) 首先考慮對前面的貢獻
- 當
x == y時,上下兩個序列給誰都無所謂 - 當
x == z1 && y != z1時,很明顯分配給 x x x 會更優, - 當
y == z1 && x != z1時,很明顯分配給 y y y 會更優,
(2) 若上述條件均為達到就考慮對后面的貢獻
- 當
x == z2 && y != z2時,很明顯分配給 y y y 會更優 - 當
y == z2 && x != z2時,同理很明顯分配給 x x x 會更優
最后一種情況:若x != z2 && y != z2,以及其他的所有剩余情況,這時候就有講究了,
看上去放到哪里都區別不大,但是我們想要最終的答案盡可能地小,也就是讓元素盡可能合并,也就是:
a [ i ] a[i] a[i] 以后和 x x x 相同的元素(假設是 x x xx xx)盡量能和 x x x 合并,也就是以后 x x x 后面都不添加數,
a [ i ] a[i] a[i] 以后和 y y y 相同的元素(假設是 y y yy yy)盡量能和 y y y 合并, 也就是以后 y y y 后面都不添加數,
但是我們總歸是要在 x x x 或者 y y y 后面選擇一個數放進去,假設我們放到了 x x x 后面,這樣也就斷絕了后面的那個與 x x x 相同的元素 x x xx xx 與 x x x 合并的可能性,
所以我們應該取兩個佇列末尾元素: x x x 和 y y y 中 與它們相同的數 x x xx xx 或者 y y yy yy 的距離更近的那個佇列,
我們假設是 y y y ,這樣與 y y y 相同的數 y y yy yy 比與 x x x 相同的數 x x xx xx 距離更近,也就是一個一個來放的話,更先到達兩個佇列面前,是距離更短的那個數,也就意味著最終可以和 y y y 合并的可能性就更大,因此我們就把 a [ i ] a[i] a[i] 放到 x x x 的后面,讓 y y y 去追逐合并的夢想 ~
應該很好理解,非常形象,
我們預處理一下下標 i i i 的最近的下一個相同元素的下標 n e x [ i ] \tt nex[i] nex[i] 就行了,如何實作具體看代碼,很好理解,
總結一下就是:
若x != z2 && y != z2,以及其他的所有剩余情況時:若nex[x] < nex[y] ,我們分配給
y
y
y 更優
若x != z2 && y != z2,以及其他的所有剩余情況時:若nex[x] > nex[y] ,我們分配給
x
x
x 更優
所有條件按照我分析的時候的先后順序if else 判斷即可,因為越往前優先級越大,后面只是有合并的可能性,而前面是直接已經可以合并了,
最后簡單實作一下就行了
Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 5e5 + 7, M = 6e6 + 7, mod = 1e9 + 7;
const ll INF = 1e18 + 7;
int n, m, t, k;
itn a[N], b[N];
vector<int> v[N];
int nex[N];
void solve()
{
int ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
v[a[i]].push_back(i);
}
for(int i = 1; i <= n; ++ i)
nex[i] = n + 1;
for(int i = 1; i <= n; ++ i) {
for(int j = 0; j < (int)v[i].size() - 1; ++ j) {
nex[v[i][j]] = v[i][j + 1];
}
}
int x = 0, y = 0, nex_x = n + 1, nex_y = n + 1;
for(int i = 1; i <= n; ++ i) {
int z1 = a[i], z2 = a[i + 1];
if(z1 == x) {
nex_x = nex[i];
}
else if(z1 == y) {
nex_y = nex[i];
}
else {
ans ++ ;
if(z2 == x && z2 != y) {
y = z1;
nex_y = nex[i];
}
else if(z2 == y && z2 != x) {
x = z1;
nex_x = nex[i];
}
else {
if(nex_x < nex_y) {
y = z1;
nex_y = nex[i];
}
else {
x = z1;
nex_x = nex[i];
}
}
}
}
printf("%d\n", ans);
}
int main()
{
solve();
return 0;
}
E - Continuous City
Problem 1479C - Continuous City
定義中心圖為:
有 n n n 個點,編號為 1 1 1 ~ n n n ,以及 m m m 條有向邊,每一條有向邊上都有一個正整數權值,并且這 m m m 條路都是從編號小的指向編號大的(意味著每次走都會朝著中心 n n n 進發),并且對于任意兩個不同的點,他們之間最多只有一條有向邊,
定義 ( L , R ) (L,R) (L,R) 連續圖為既滿足中心圖,又滿足下述兩個條件的有向圖:
- 所有的從 1 1 1 到 n n n 的簡單路徑的長度 l e n ∈ [ L , R ] len\in[L,R] len∈[L,R],
- 對于任意的 d d d , L ≤ d ≤ R L\le d\le R L≤d≤R,均恰好存在一條且僅有一條從 1 1 1 到 n n n 的簡單路徑的長度等于 d d d,
僅給定
L
L
L 和
R
R
R,請問你能否構造一個符合題意且點數
n
n
n 不超過 32 的
(
L
,
R
)
(L,R)
(L,R) 連續圖,如果不能,輸出 NO ,否則輸出 YES 并輸出該圖的
n
n
n 和
m
m
m (點數與邊數),并輸出
m
m
m 條邊的情況(對于每條邊,輸出
x
,
y
,
z
x,y,z
x,y,z 表示第
i
i
i 條邊從
x
x
x 到
y
y
y 邊長為
z
z
z)
Solution
今天下午(2/10)一定更…
轉載請註明出處,本文鏈接:https://www.uj5u.com/ruanti/258463.html
標籤:其他
