整理的演算法模板合集: ACM模板
點我看演算法全家桶系列!!!
實際上是一個全新的精煉模板整合計劃
目錄
- A、P7337 『MdOI R4』Fun
- B、P7338 『MdOI R4』Color
- C、P7339 『MdOI R4』Kotori
- D、P7340 『MdOI R4』Balance
- E、P7341 『MdOI R4』Phoenix
- F、P7342 『MdOI R4』Destiny
這場月賽就離譜
Div1,一千多人參加,除了兩位大佬兩題以外,其他人最多一題…
C題可并堆,D題分數規劃,E題PQ樹,F題生成函式NTT,離譜
A、P7337 『MdOI R4』Fun
Problem A. Fun
VG 的學校有 n n n 個人要去考 NOIP,
每個人有一個交通方式,第 i i i 個人的交通方式為 t i t_i ti? , t i = 1 t_i=1 ti?=1表示這個人坐學校大巴, t i = 0 t_i=0 ti?=0 表示這個人自己去考場,
每個人有一個頹廢值,第 i i i 個人的頹廢值為 q i q_i qi? , q i = 1 q_i=1 qi?=1表示這個人愿意打狼, q i = 0 q_i=0 qi?=0 表示這個人不愿意打狼,
每個人去考場時會買一瓶快樂水,但如果坐大巴且愿意打狼的人數(即滿足 t i = 1 t_i=1 ti?=1 且 q i = 1 q_i=1 qi?=1 的 i i i 個數) k k k 不小于 m m m ,則這 k k k 個人只需要買 m m m 瓶快樂水,
現在,VG 統計出了所有人的交通方式和頹廢值,他希望請求你幫他求出最終所有人買快樂水的總瓶數,
Soluiotn
簽到題,讀懂題意直接模擬就行了(我看到題還楞了一下,怎么這么簡單???
可能是因為資料太少,我用快讀快輸還沒有直接scanf跑的快…
時間復雜度:
O
(
n
)
O(n)
O(n)
Code
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 5007;
int n, m;
int t[N], q[N];
int type;
int main()
{
scanf("%d%d%d", &n, &m, &type);
for(int i = 1; i <= n; ++ i) {
scanf("%d", &t[i]);
}
for(int i = 1; i <= n; ++ i) {
scanf("%d", &q[i]);
}
int k = 0;
for(int i = 1; i <= n; ++ i) {
if(t[i] && q[i]) {
k ++ ;
}
}
int ans = n - k;
if(k >= m) {
ans += m;
}
else ans += k;
printf("%d\n", ans);
return 0;
}
B、P7338 『MdOI R4』Color
Problem B. Color
小 M 同學有一張 2 2 2 行 n n n 列的方格紙,一開始所有格子都是白色的,
她決定對一些格子染色,具體地,每次她會選擇兩個相鄰的(四聯通的,也就是有公共邊的)白色格子,其中一個染成紅色,另一個染成藍色,
她的目標是通過任意次操作讓指定的一些格子變成紅色,對其他格子沒有要求,請你幫她判斷一下,能否通過上述操作達成目標呢?
Soluiotn
簡單畫圖模擬以后,直接貪心即可,
我直接亂搞瘋狂分類討論瘋狂貪心然后就過了…因為只有兩行,所以情況不會太多 ~
好吧我這個思路其實就是正解,
不過我見過有人用Dinic滿分來著hhh
還有用匈牙利跑二分圖匹配99分的hhh
簡單講一下思路:題目要求每次染色的時候必須選擇兩個白色格子,也就是只能選擇沒有染過色的格子,然后給我們一個期望染色的方案,并且沒有標 1 是 0 的格子的顏色是不做要求的,
所以我們就可以直接根據它給定的期望方案去染色,對于每一個1來說,因為只有兩行,所以我們分類討論(若有 n n n 行 m m m 列就是經典的網路流最大匹配了 ~ )
根據題意只有相鄰的才能選上一塊染色,所以我們只需要考慮每個1的上下左右,也就是上下行和前后列,優先考慮前面一列,然后考慮上下以及后面的只有一個0的情況,若沒有0直接 NO ,剩下最后一種情況就是下和后,或者上和后都可以選,我們優先考慮下或者上,也就是同一列的那個格子,因為同一列第
i
i
i 列的格子,之后 第
i
+
1
i+1
i+1 列可以用到,而后一列即第
i
+
1
i+1
i+1 的那個可選的格子, 第
i
+
2
i+2
i+2 列也可以使用 ~ 然后我們模擬的時候染成紅色的時候就置為 1 ,藍色就置為 2 ,然后就沒了
時間復雜度: O ( n ) O(n) O(n)
Code
然后就是我10分鐘一通亂搞AC的丑陋的代碼了 ~
#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;
string a, b;
bool solve()
{
scanf("%d", &n);
cin >> a >> b;
for(int i = 0; i < n; ++ i) {
bool flag1 = 0, flag2 = 0;
if(a[i] == '1') flag1 = 1;
if(b[i] == '1') flag2 = 1;
if(flag1) {
if(i != 0 && a[i - 1] == '0') {
a[i - 1] = '2';
}
else if(i != n - 1 && a[i + 1] == '1' && b[i] == '0') {
b[i] = '2';
}
else if(i != n - 1 && a[i + 1] == '0' && b[i] == '1') {
a[i + 1] = '2';
}
else if(i != n - 1 && a[i + 1] == '1' && b[i] == '1') {
return false;
}
else if(i == n - 1) {
if(b[i] == '1') return false;
}
else if(b[i] == '0'){
b[i] = '2';
}
else if(a[i + 1] == '0')
a[i + 1] == '2';
else return false;
}
if(flag2) {
if(i != 0 && b[i - 1] == '0') {
b[i - 1] = '2';
}
else if(i != n - 1 && b[i + 1] == '1' && a[i] == '0') {
a[i] = '2';
}
else if(i != n - 1 && b[i + 1] == '0' && a[i] == '1') {
b[i + 1] = '2';
}
else if(i != n - 1 && b[i + 1] == '1' && a[i] == '1') {
return false;
}
else if(i == n - 1) {
if(a[i] == '1') return false;
}
else if(a[i] == '0'){
a[i] = '2';
}
else if(b[i + 1] == '0')
b[i + 1] == '2';
else return false;
}
}
return true;
}
int main()
{
scanf("%lld", &t);
while(t -- ) {
if(solve()) puts("RP");
else puts("++");
}
return 0;
}
C、P7339 『MdOI R4』Kotori
Problem C. Kotori

琴里yyds

可并堆直接秒 (霧
我們的琴里可以在每一輪的比賽當中幫助任意一個人 + m +\ m + m 票,所以我們可以模擬這個程序,因為整個比賽程序是 k 輪,每輪每次都是兩個人比賽,也就是左區間和右區間,那么我們直接按照題意模擬比賽,實際上總復雜度只有 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n) ,是可以通過本題的,具體的模擬思路看代碼會更好理解一些,所有不能獲勝的都已經被篩掉了,剩下的都是可能獲勝者,
#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 = 5e6 + 7, M = 1e6 + 7, mod = 1e9 + 7;
const int INF = 1e9 + 7;
int n, m, t, k, q;
int a[N], maxx;
int vis[N];
void solve()
{
maxx = -INF;
scanf("%d%d", &k, &m);
n = (1 << k);
for(int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
vis[i] = true;
}
for(int i = 1; i <= k; ++ i) {
int step = 1 << i;//從兩個人開始,模擬每輪的比賽
for(int j = 1; j <= n; j += step) {
int minL = INF;
itn minR = INF;
for(int pos = j; pos <= j + step / 2 - 1; ++ pos) {
if(vis[pos]) {
minL = min(minL, a[pos]);
}
}
for(int pos = j + step / 2; pos <= j + step - 1; ++ pos) {
if(vis[pos]) {
minR = min(minR, a[pos]);
}
}
for(int pos = j; pos <= j + step / 2 - 1; ++ pos) {
if(a[pos] + m < minR) { //連右邊最菜的(你的對手)加上kotori的幫助都打不過,再見 ~
vis[pos] = false;
}
}
for(int pos = j + step / 2; pos <= j + step - 1; ++ pos) {
if(a[pos] + m < minL) { //連左邊最菜的(你的對手)加上kotori的幫助都打不過,再見 ~
vis[pos] = false;
}
}
}
}
if(vis[1]) {
puts("Kotori");
}
else puts("Yoshino");
}
int main()
{
scanf("%d", &t);
while(t -- ) {
solve();
}
return 0;
}
正解
最后我們發現整個比賽的程序實際上就是一個歸并排序 ~
我們可以直接用歸并排序解決,
每次刪掉最小的不滿足條件的人,然后對剩余的進行歸并
時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)

約會大作戰建議只看前兩季(
不過好訊息是第四季已經有訊息啦!建議第三季直接補原作,不過確實,能動就行(

啥時候Yoshino(四系乃)也拿個世萌啊
D、P7340 『MdOI R4』Balance
Problem D Balance

Solution
我來分析一下這道題是怎么思考的吧,
首先我們要求的是一對點 ( i , j ) (i,j) (i,j) ,使得 f ( i , j ) f(i,j) f(i,j) 在 f ( i , t ) f(i,t) f(i,t) 中是第 x x x 小,在 f ( s , j ) f(s,j) f(s,j) 中是第 y y y 小,也就是
a i + b j p i + q j ≥ f ( i , t ) v a l x t h \cfrac{a_i+b_j}{p_i+q_j}\ge f(i,t)val_{xth} pi?+qj?ai?+bj??≥f(i,t)valxth?
a i + b j p i + q j ≥ f ( s , j ) v a l y t h \cfrac{a_i+b_j}{p_i+q_j}\ge f(s,j)val_{yth} pi?+qj?ai?+bj??≥f(s,j)valyth?
那么我們肯定來考慮一個一般性的問題:
f ( i , j ) = a i + b j p i + q j ≥ v a l f(i,j)=\cfrac{a_i+b_j}{p_i+q_j}\ge val f(i,j)=pi?+qj?ai?+bj??≥val
也就是如何得到一個通用的解法
然后可以發現這實際上就是一個01分數規劃的模板結構,
我們對其進行分數規劃:
將他乘開:
a i + b j ≥ ( p i + q j ) × v a l a_i+b_j\ge (p_i+q_j)\times val ai?+bj?≥(pi?+qj?)×val
合并同類項
a i ? p i × v a l ≥ q j × v a l ? b j a_i-p_i\times val\ge q_j\times val - b_j ai??pi?×val≥qj?×val?bj?
( a i ? p i × v a l ) + ( b j ? q j × v a l ) ≥ 0 (a_i-p_i\times val)+(b_j-q_j\times val)\ge 0 (ai??pi?×val)+(bj??qj?×val)≥0
我們設
U i = a i ? p i × v a l U_i=a_i-p_i\times val Ui?=ai??pi?×val
V j = b j ? q j × v a l V_j=b_j-q_j\times val Vj?=bj??qj?×val
即 U i + V j ≥ 0 U_i+V_j\ge 0 Ui?+Vj?≥0
我們發現 U i U_i Ui? 僅與 i i i 和 v a l val val 有關, V j V_j Vj? 僅與 j j j 和 v a l val val 有關,并且映射到圖上, f ( i , j ) = a i + b j p i + q j ≥ v a l f(i,j)=\cfrac{a_i+b_j}{p_i+q_j}\ge val f(i,j)=pi?+qj?ai?+bj??≥val 和 f ( i , j ) = a i + b j p i + q j ≤ v a l f(i,j)=\cfrac{a_i+b_j}{p_i+q_j}\le val f(i,j)=pi?+qj?ai?+bj??≤val 一定是嚴格分開的,中間有一個明顯的分界線,
并且
U
i
U_i
Ui? ,
V
j
V_j
Vj? 在固定的
(
i
,
j
)
(i,j)
(i,j) 時會隨著
v
a
l
val
val 的變化而變化,所以我們可以很自然地 根據分數規劃的套路 想出二分
v
a
l
val
val ,然后判斷當前的
v
a
l
=
m
i
d
val = mid
val=mid 是否存在一個
U
y
+
V
x
≥
0
U_y+V_x\ge 0
Uy?+Vx?≥0
至于為什么是 U y U_y Uy? 和 V x V_x Vx?,根據題意我們想要找的是 f ( i , j ) f(i,j) f(i,j) 在 f ( i , t ) f(i,t) f(i,t) 中是第 x x x 小, i i i 是固定的,也就是 U i U_i Ui? 是固定的,我們排序后找到第二維 j j j 也就是 V j V_j Vj?里的第 x x x 小值,即在 V V V 中找第 x x x 小值,同理,在 U U U 中找第 y y y 小值,
但是我們這里只是想要找到整個序列的第
x
x
x 小元素以及第
y
y
y 小的元素,所以我們可以直接使用 nth_element 期望
O
(
n
)
O(n)
O(n) 線性地找到,而不需要暴力排序之后
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 找到,
簡單介紹一下
nth_element:
nth_element(a, a + n, a + len);陣列長度為
len,該函式的作用是使第 n n n 大元素處于第 n n n 位置(從 0 0 0 開始,其位置是下標為 n n n 的元素),并且比這個元素小的元素都排在這個元素之前,比這個元素大的元素都排在這個元素之后,但不能保證他們是有序的,如果是自己手寫的結構體,也可以在nth_element的最后面加上比較函式cmp,大量資料隨機訪問下
nth_element是 O ( n ) O(n) O(n) 的,
時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)
對不起我講的有點亂,下午我再梳理一下

Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 5e6 + 7, mod = 1e9 + 7;
const double INF = 1e9 + 7;
int n, m, t;
int x, y;
struct node
{
itn id, a, q;
int b, p;
double val;
}a[N], b[N];
bool cmp(node a, node b) // 因為我們找的是第 x 小,所以要多載比較運算子
{
return a.val < b.val;
}
bool check(double val)
{
for(int i = 1; i <= n; ++ i) {
a[i].val = a[i].a - val * a[i].p;
b[i].val = b[i].b - val * b[i].q;
}
nth_element(a + 1, a + y, a + 1 + n, cmp);
nth_element(b + 1, b + x, b + 1 + n, cmp);
if(a[y].val + b[x].val >= 0)
return true;
return false;
}
void solve()
{
scanf("%d%d%d", &n, &x, &y);
for(int i = 1; i <= n; ++ i) {
scanf("%d%d%d%d", &a[i].a, &b[i].b, &a[i].p, &b[i].q);
a[i].id = i;
b[i].id = i;
}
double l = -INF, r = INF;
for(int i = 1; i <= 60; ++ i) {
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%d %d\n", a[y].id, b[x].id);//nth_element 已經幫我們把答案放到正確的位置了 ~
return ;
}
int main()
{
scanf("%d", &t);
while(t -- ) {
solve();
}
}
E、P7341 『MdOI R4』Phoenix
PQ - Tree 可過,下輩子一定寫(
F、P7342 『MdOI R4』Destiny
推一下式子,生成函式 + NTT 可過,下輩子一定寫(
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/258815.html
標籤:其他
上一篇:c語言 最簡版 貪吃蛇 小游戲
下一篇:貪吃蛇
