整理的演算法模板合集： ACM模板
點我看演算法全家桶系列！！！
實際上是一個全新的
精煉模板整合計劃
比賽鏈接：https://codeforces.com/gym/102992
- A. 構造
- D. 圖論
- E. 構造，爆搜
- F. 期望，三分
- H. 抽屜原理，爆搜打表，組合計數
- I. 計算幾何
- J. 博弈論，吉司機線段樹
- K. 數論，簽到
- L. 思維，簽到
- M. 樹上背包 O ( n 2 ) O(n^2) O(n2)
A、Ah, It’s Yesterday Once More
Problem
對于給定的 n × m n \times m n×m 的方格， 0 0 0 代表障礙， 1 1 1 代表袋鼠，有一串隨機生成的長為 5 × 1 0 4 5 \times 10^4 5×104的指令，僅包含 LRUD \text{LRUD} LRUD 字符，分別表示將所有袋鼠同時向某個方向移動（若能移動，即不經過障礙、不超出方格范圍），現要求構造一個 n × m n \times m n×m 方格圖，使得對于隨機生成的 500 500 500 串指令，至少有 125 125 125 個滿足執行后，所有袋鼠不都在同一個方格，要求構造的袋鼠方格連通、且不含環，
1 ≤ n , m ≤ 20 1 \le n, m \le 20 1≤n,m≤20，
Solution
我們只需要執行 1 4 \cfrac{1}{4} 41? 的指令執行即可，也就是每只袋鼠至少有一個方向是墻，所以我們可以構造一個不對稱的路徑，以及一些分岔路口，例如一些 Z 字形路徑，注意袋鼠們必須連通以及不能有環，
#include<bits/stdc++.h>
using namespace std;
int main(){
char ans[21][21] = {
"20 20",
"11011111011111011111",
"10110100110100110100",
"11101101101101101101",
"10011011011011011001",
"10110110110110110111",
"01101101101101101101",
"11011011011011011011",
"10110110110110110110",
"11101101101101101101",
"10011011011011011001",
"10110110110110110111",
"01101101101101101101",
"11011011011011011011",
"10110110110110110110",
"11101101101101101101",
"10011011011011011001",
"10110110110110110111",
"01101101101101101101",
"01011001011001011001",
"11110111110111110111",
};
for(int i = 0; i <= 20; ++i){
cout << ans[i] << endl;
}
return 0;
}
D、Degree of Spanning Tree
Problem
給出一個無向圖，尋找它的一棵生成樹，要求生成樹上每個點的度數都要小于等于 n 2 \cfrac{n}{2} 2n? ，
Solution
首先隨便找到一棵生成樹，尋找它度數最大的點，在所有節點中，度數大于 n 2 \cfrac{n}{2} 2n? 的節點最多只有一個，若找不到直接輸出，找到了則令其為根節點，對所有不在生成樹上的邊進行列舉，若這條邊的起點終點在樹上的lca是根節點，則說明這條邊的加入可以令根節點度數-1，但是在兩個點都是根節點的兒子節點的情況下，會令選擇的另一邊的節點度數+1，所以在刪邊加邊的程序中要判斷是否會導致其他節點度數大于 n 2 \cfrac{n}{2} 2n?，
動態加邊刪邊求lca實在是不會…但是還好可以用并查集來做，首先將根節點的所有子樹各自構成集合，集合祖先為根節點的兒子節點，每次遍歷邊查詢兩端點是否在同一集合即可，
Code
#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;
vector<pair<int,int>> es;
map<pair<int,int>,int> mp;
struct Edge{
int to,nxt;
}edges[maxn << 2];
int head[maxn], idx;
int deg[maxn];
void add(int u,int v)
{
edges[idx] = {v,head[u]}, head[u] = idx++;
edges[idx] = {u,head[v]}, head[v] = idx++;
}
int pre[maxn];
int chose[maxn];
int fi(int x) {return x == pre[x] ? x : pre[x] = fi(pre[x]);}
void dfs(int u,int fa, int sig)
{
pre[u] = sig;
for(int i = head[u];~i;i = edges[i].nxt){
int v = edges[i].to;
if(v == fa) continue;
dfs(v,u,sig);
}
}
void init(int n,int m)
{
mp.clear();
es.clear();
for(int i = 0;i <= n;++i){
head[i] = -1;
deg[i] = 0;
pre[i] = i;
}
for(int i = 0;i <= m;++i){
chose[i] = 0;
}
idx = 0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d %d",&n,&m);
init(n,m);
for(int i = 0;i < m;++i){
int u,v;
scanf("%d%d",&u,&v);
if(u > v) swap(u,v);
es.push_back({u,v});
}
sort(es.begin(),es.end());
es.erase(unique(es.begin(),es.end()),es.end());
m = static_cast<int>(es.size()); // 洗掉重邊自環
for(int i = 0;i < m;++i){
int u = es[i].first;
int v = es[i].second;
mp[{u,v}] = mp[{v,u}] = i;
int fu = fi(u),fv = fi(v);
if(fu != fv){
add(u,v); //kruskal 建生成樹
pre[fu] = fv;
deg[u]++;
deg[v]++;
chose[i] = 1;
}
}
int flag = 0;
for(int i = 2;i <= n;++i){
if(fi(i) != fi(1)) flag = 1;
}
if(flag) {
puts("No");
continue;
}
int rt = -1;
for(int i = 1;i <= n;++i){
if(deg[i] > n/2){
rt = i;
break;
}
}
if(rt == -1){
puts("Yes");
for(int i = 0;i < m;++i){
if(chose[i]){
printf("%d %d\n",es[i].first,es[i].second);
}
}
continue;
}
for(int i = 1;i <= n;++i) pre[i] = i;
for(int i = head[rt];~i;i = edges[i].nxt){
dfs(edges[i].to,rt,edges[i].to);
}
for(int i = 0;i < m;++i){
if(chose[i]) continue;
int u = es[i].first, v = es[i].second;
int fu = fi(u), fv = fi(v);
if(fu == fv || u == rt || v == rt) continue;
deg[rt]--;
deg[u]++;
deg[v]++;
deg[fu]--;
if(deg[u] > n/2 || deg[v] > n/2){ //檢測是否可行，不可行就恢復
deg[fu]++;
deg[fv]--;
if(deg[u] > n/2 || deg[v] > n/2){
deg[rt]++;
deg[u]--;
deg[v]--;
deg[fv]++;
continue;
}
else{
pre[fv] = fu;
chose[i] = 1;
chose[mp[{rt,fv}]] = 0;
}
}
else{
pre[fu] = fv;
chose[i] = 1;
chose[mp[{rt,fu}]] = 0;
}
if(deg[rt] <= n/2) break;
}
if(deg[rt] <= n/2){
puts("Yes");
for(int i = 0;i < m;++i){
if(chose[i]){
printf("%d %d\n",es[i].first,es[i].second);
}
}
}
else puts("No");
}
return 0;
}
E、Evil Coordinate
Problem
在一個直角坐標系中，給定起點 ( 0 , 0 ) (0, 0) (0,0)，一個障礙 ( m x , m y ) (m_x, m_y) (mx?,my?) 以及一串長度為 n n n 的指令，僅包含 L / R / U / D \text{L / R / U / D} L / R / U / D 字符，分別表示向左右上下移動，請你調整指令順序讓移動程序不經過 ( m x , m y ) (m_x, m_y) (mx?,my?)，有解輸出指令字符，無解輸出 impossible \text{impossible} impossible ，
1 ≤ n ≤ 1 0 5 , ? 1 0 9 ≤ m x , m y ≤ 1 0 9 , ∑ n i ≤ 1 0 6 1\le n \le 10^5, -10^9 \le m_x, m_y \le 10^9, \sum n_i \le 10^6 1≤n≤105,?109≤mx?,my?≤109,∑ni?≤106 ，
Solution
開始想的是左右走完，然后上下，發現可以先上下再左右，然后又發現反例，然后也可以先左再上再下再右，明白了，所有的方向排列一共有 4 ! = 24 4!=24 4!=24 種，直接求全排列，然后對于每一個排列，分別判斷即可，
最后注意 ios 加速之后 puts 就不能用了…
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;
bool cal(int x,int y, int l,int r,int u, int d,vector<int> v)
{
string res;
for(int i = 0;i < v.size();++i){
if(v[i] == 1) while(l--) res.push_back('L');
if(v[i] == 2) while(r--) res.push_back('R');
if(v[i] == 3) while(u--) res.push_back('U');
if(v[i] == 4) while(d--) res.push_back('D');
}
int flag = 0;
int nx = 0,ny = 0;
for(int i = 0;i < res.size();++i){
if(res[i] == 'L') nx--;
if(res[i] == 'R') nx++;
if(res[i] == 'U') ny++;
if(res[i] == 'D') ny--;
if(nx == x && ny == y){
flag = 1;
}
}
if(!flag) {
cout<<res<<endl;
return 1;
}
else return 0;
}
int main()
{
int t;
cin>>t;
while(t--){
int x,y;
cin>>x>>y;
string s;
cin>>s;
int l,r,u,d;
l = r = u = d = 0;
int nx = 0,ny = 0;
int flag = 0;
for(int i = 0;i < s.size();++i){
if(s[i] == 'L') l++,nx--;
if(s[i] == 'R') r++,nx++;
if(s[i] == 'U') u++,ny++;
if(s[i] == 'D') d++,ny--;
if(nx == x && ny == y){
flag = 1;
}
}
if((x == 0 && y == 0) || (x == nx && y == ny)){
puts("Impossible");
continue;
}
vector<int> v = {1,2,3,4};
flag = 0;
do{
if(cal(x,y,l,r,u,d,v)){
flag = 1;
break;
}
}while(next_permutation(v.begin(),v.end()));
if(!flag) puts("Impossible");
}
return 0;
}
F、Fireworks
Problem
制作一支煙花需要花費 n n n 分鐘，每支煙花有 p × 1 0 ? 4 p \times 10^{-4} p×10?4的概率是完美的，每次可以花費 m m m 分鐘點燃之前制作的所有煙花，若發現至少有一支完美的，則停止，問最優策略下，最短的停下的時間期望是多少？
多組資料， 1 ≤ T ≤ 1 0 4 , 1 ≤ n , m ≤ 1 0 9 , 1 ≤ p ≤ 1 0 4 1 \le T \le 10^4, 1 \le n, m \le 10^9, 1 \le p \le 10^4 1≤T≤104,1≤n,m≤109,1≤p≤104 ，
Solution
不是完美煙花的概率 q = 1 ? ( p × 1 0 ? 4 ) q = 1 - (p \times 10^{-4}) q=1?(p×10?4)，假設最優策略為連續制作 k k k 支煙花后花費 m m m 的時間一次全部點燃，若發現有完美煙花則停止，若沒有則回到初始狀態，繼續執行最優策略，發現實際上求的就是期望最早第幾次成功，也就是前 k ? 1 k-1 k?1 次失敗，第 k k k 次成功發現只有兩種情況，顯然服從幾何分布（前 k ? 1 k-1 k?1 次失敗，第 k k k 次成功 ），即 n n n 重伯努利實驗的幾何概型，根據幾何概型的期望公式得： E ( X ) = 1 1 ? q k E(X) = \cfrac{1}{1 - q^k} E(X)=1?qk1?，期望時間為 f ( k ) = n × k + m 1 ? q k f(k) = \cfrac{n \times k + m}{1 - q^k} f(k)=1?qkn×k+m? ，顯然答案就是峰值，打表發現這是一個單峰函式，直接三分答案即可，或者也可以二分 + 求導，
Code
#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-9;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;
int n, m, t;
double p;
double qpow(double a, ll b)
{
double res = 1;
while(b) {
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
double f(double k)
{
double ans = 0;
double up = k * n + m;
double down = 1 - qpow((1 - p), k);
return up / down;
}
void solve()
{
scanf("%d%d%lf", &n, &m, &p);
p /= 10000.0;
ll l = 1, r = 1e18;
while(r - l > 2) {
ll x = (2 * l + r) / 3;
ll y = (2 * r + l) / 3;
//cout << l << " " << r <<endl;
if(f(x) < f(y) + eps) r = y;
else l = x;
}
printf("%.10f\n", min({f(l), f(l + 1), f(l - 1), f(l + 2)}));
}
/*
3
1 1 5000
1 1 1
1 2 10000
*/
int main()
{
scanf("%d", &t);
while(t -- ) {
solve();
}
}
H、Harmonious Rectangle
Problem
定義 Harmonious Rectangle 為一個矩形記憶體在
{
color
(
x
1
,
y
1
)
=
color
(
x
1
,
y
2
)
color
(
x
2
,
y
1
)
=
color
(
x
2
,
y
2
)
或
{
color
(
x
1
,
y
1
)
=
color
(
x
2
,
y
1
)
color
(
x
1
,
y
2
)
=
color
(
x
2
,
y
2
)
\begin{cases} \text{color}(x_1, y_1) = \text{color}(x_1, y_2)\\ \text{color}(x_2, y_1) = \text{color}(x_2, y_2)\\\end{cases} \\或\\\begin{cases} \text{color}(x_1, y_1) = \text{color}(x_2, y_1)\\ \text{color}(x_1, y_2) = \text{color}(x_2, y_2)\\ \end{cases}
{color(x1?,y1?)=color(x1?,y2?)color(x2?,y1?)=color(x2?,y2?)?或{color(x1?,y1?)=color(x2?,y1?)color(x1?,y2?)=color(x2?,y2?)?
其中這四個點是矩形的端點， 問一個 n × m n\times m n×m 的矩陣，每個點可以涂 0 ， 1 ， 2 0，1，2 0，1，2 三種顏色，存在多少種矩陣是和諧矩陣，
n , m ≤ 3000 n,m\le 3000 n,m≤3000
Solution
憑感覺可知
n
n
n 和
m
m
m 大于某個數后，一定全都含有和諧矩陣，（不然就沒法玩了 ，如果后面資料大，答案不是公式那將毫無意義 ）即任意一種染色的方案都有貢獻，即答案就是染色總方案，每個格子有三種顏色可選，總方案為
3
n
×
m
3^{n\times m}
3n×m，然后爆搜找邊界就行了，
或者說使用抽屜原理，三種顏色，任意一組 ( a , b ) (a,b) (a,b) 每個都有三種選擇，一共有 3 × 3 = 9 3\times 3=9 3×3=9 種，根據抽屜原理，若 m a x { n , m } > 9 max\{n,m\}>9 max{n,m}>9 則無論怎么排列，都一定存在 和諧矩形，
可以在線搜索所有非法矩陣，列舉當前點是否可以放某個顏色的點，將爆搜優化到 3 n n 2 3^nn^2 3nn2，對 9 × 9 9 \times 9 9×9 以下的矩陣達打表輸出即可，
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int res = 0;
int mat[9][9] = {{3,9,27,81,243,729,2187,6561},
{9,66,390,1800,6120,13680,15120,0},
{27,390,3198,13176,27000,13680,15120,0},
{81,1800,13176,24336,4320,0,0,0},
{243,6120,27000,4320,4320,0,0,0},
{729,13680,13680,0,0,0,0,0},
{2187,15120,15120,0,0,0,0,0},
{6561,0,0,0,0,0,0,0}};
void dfs(int cur,int n,int m) //爆搜打表代碼
{
if(cur == n * m){
res++;
return ;
}
for(int col = 0;col < 3;++col){
int x = cur / m;
int y = cur % m;
bool flag = 1;
for(int i = 0;i < x && flag;++i){
for(int j = 0;j < y && flag;++j){
if(mat[i][y] == mat[i][j] && mat[x][j] == col){
flag = 0;
break;
}
if(mat[i][y] == col && mat[i][j] == mat[x][j]){
flag = 0;
break;
}
}
}
mat[x][y] = col;
if(flag)dfs(cur + 1, n, m);
}
}
ll qpow(ll a, ll b)
{
ll res = 1;
while(b){
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
int t;
cin>>t;
while(t--){
ll n,m;
cin>>n>>m;
if(n == 1 || m == 1) puts("0");
else if(n < 9 && m < 9){
printf("%lld\n",(qpow(3,n*m)-mat[n-1][m-1]+mod) % mod);
}
else{
printf("%lld\n",qpow(3,n*m));
}
}
return 0;
}
I、Interested in Skiing
Problem
二維平面 [ ? m , m ] × R [-m, m] \times \mathbb{R} [?m,m]×R 上有 n n n 條線段作為障礙，以端點坐標 ( x 1 , y 1 ) (x_1, y_1) (x1?,y1?) 和 ( x 2 , y 2 ) (x_2, y_2) (x2?,y2?) 表示，起點為 ( 0 , ? inf ? ) (0, -\inf) (0,?inf) 的一個點以 v y v_y vy?的速度向 y \text{y} y 軸正方向移動，終點為 ( 0 , inf ? ) (0, \inf) (0,inf) ，求最小的 v x ? v_x^* vx??，使得當水平速度 v x > v x ? v_x \gt v_x^* vx?>vx?? 時，能從起點移動到終點，無解則輸出 ? 1 -1 ?1 ，
1 ≤ n ≤ 100 , 1 ≤ m ≤ 1 0 4 , 1 ≤ v y ≤ 10 , ? m ≤ x 1 , x 2 ≤ m , ? 1 0 ? 4 ≤ y 1 , y 2 ≤ 1 0 4 1 \le n \le 100, 1 \le m \le 10^4, 1 \le v_y \le 10, -m \le x_1, x_2 \le m, -10^{-4} \le y_1, y_2 \le 10^4 1≤n≤100,1≤m≤104,1≤vy?≤10,?m≤x1?,x2?≤m,?10?4≤y1?,y2?≤104，
J - Just Another Game of Stones
Problem
給定一個長度為 n n n 的陣列 a i a_i ai? ，有 q q q 次操作：
1 l r x 1~l~r~x 1 l r x ，表示令 a i = max ? { a i , x } , i ∈ [ l , r ] a_i = \max\{a_i, x\}, i \in [l, r] ai?=max{ai?,x},i∈[l,r]，
2 l r x 2~l~r~x 2 l r x ，表示詢問用 [ l , r ] [l, r] [l,r] 的石堆和額外的一堆有 x x x 個石子的石堆一起，進行 Nim \text{Nim} Nim 博弈的必勝情況的第一步操作種數，
1 ≤ n , q ≤ 2 × 1 0 5 , 1 ≤ l , r ≤ n , 0 ≤ a i , x < 2 30 ? 1 1 \le n, q \le 2 \times 10^5, 1 \le l, r \le n, 0 \le a_i, x \lt 2^{30} - 1 1≤n,q≤2×105,1≤l,r≤n,0≤ai?,x<230?1，
Solution
經典 Nim \text{Nim} Nim 博弈，若所有石子堆的石子數量的異或和為 0 0 0 則先手必敗，否則先手必勝，那么我們假設當前區間異或和為 S S S，顯然我們想要必勝，只需要取石子使得當前狀態變為必敗態送給對手，即在一堆里取石子，使得異或和變為 0 0 0 ，顯然有結論：對于一個石子數量為 a i a_i ai? 的石堆，取走 a i ? a i ⊕ S a_i - a_i \oplus S ai??ai?⊕S 個石子，使得異或和 S S S 變為 0 0 0，也就是說若當前結點權值 a i a_i ai?，當 a i ≥ a i ⊕ S a_i\ge a_i \oplus S ai?≥ai?⊕S ，則對該石子堆進行修改，即為一種合法的操作，故答案（總操作種數）即為區間里 a i ≥ a i ⊕ S a_i \ge a_i \oplus S ai?≥ai?⊕S 的結點的數量，顯然異或是不進位的加法，即我們只需要考慮，對于當前區間的異或和 S S S ， S S S 的最高位 1 1 1，若 a i a_i ai? 在該最高位也是 1 1 1 ，則必有 a i ≥ a i ⊕ S a_i\ge a_i\oplus S ai?≥ai?⊕S ，反之一定不成立，
這個題主要就是看會不會SGB,如果會的話就很簡單了，對于opt 1可以用SegmentTreeBeats的操作進行維護，對于opt 2可以考慮為線段樹的每個節點維護區間異或和，并開一個桶記錄每個位對應個數，向上合并的時候直接暴力合并就行了，總體復雜度 O ( n l o g n × 30 ) O(nlogn\times 30) O(nlogn×30)
記得考慮操作 2 加進來的石頭…
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
const int maxn = 2e5+5;
struct node
{
ll mi;
ll smi;
ll xsum;
ll cntmi;
ll cnt[31];
ll tag;
}tree[maxn*4];
ll a[maxn];
struct Segment_tree_beats
{
void pushup(int rt){
if(tree[rt<<1].mi < tree[rt<<1|1].mi){
tree[rt].mi = tree[rt<<1].mi;
tree[rt].cntmi = tree[rt<<1].cntmi;
tree[rt].smi = min(tree[rt<<1].smi,tree[rt<<1|1].mi);
tree[rt].xsum = tree[rt<<1].xsum^tree[rt<<1|1].xsum;
for(int i = 0;i <= 30;++i)tree[rt].cnt[i] = tree[rt<<1].cnt[i]+tree[rt<<1|1].cnt[i];
}
else if(tree[rt<<1].mi > tree[rt<<1|1].mi){
tree[rt].mi = tree[rt<<1|1].mi;
tree[rt].cntmi = tree[rt<<1|1].cntmi;
tree[rt].smi = min(tree[rt<<1|1].smi,tree[rt<<1].mi);
tree[rt].xsum = tree[rt<<1|1].xsum^tree[rt<<1].xsum;
for(int i = 0;i <= 30;++i)tree[rt].cnt[i] = tree[rt<<1].cnt[i]+tree[rt<<1|1].cnt[i];
}
else{
tree[rt].mi = tree[rt<<1].mi;
tree[rt].cntmi = tree[rt<<1].cntmi+tree[rt<<1|1].cntmi;
tree[rt].smi = min(tree[rt<<1].smi,tree[rt<<1|1].smi);
tree[rt].xsum = tree[rt<<1].xsum^tree[rt<<1|1].xsum;
for(int i = 0;i <= 30;++i)tree[rt].cnt[i] = tree[rt<<1].cnt[i]+tree[rt<<1|1].cnt[i];
}
}
void pushtag(int rt,int val){
if(tree[rt].mi >= val)return;
if(tree[rt].cntmi&1){
tree[rt].xsum^=tree[rt].mi;
tree[rt].xsum^=val;
}
for(int i = 0;i <= 30;++i){
if(tree[rt].mi>>i&1)tree[rt].cnt[i]-=tree[rt].cntmi;
if(val>>i&1)tree[rt].cnt[i]+=tree[rt].cntmi;
}
tree[rt].mi = val;
tree[rt].tag = val;
}
void pushdown(int rt){
if(tree[rt].tag==-1)return;
pushtag(rt<<1,tree[rt].tag),pushtag(rt<<1|1,tree[rt].tag);
tree[rt].tag = -1;
}
void build(int rt,int l,int r){
tree[rt].tag = -1;
if(l==r){
tree[rt].mi = a[l];
tree[rt].xsum = a[l];
tree[rt].cntmi = 1;
tree[rt].smi = 1e18;
for(int j = 0;j <= 30;++j){
if(a[l]>>j&1)tree[rt].cnt[j]++;
}
return;
}
int mid = l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
void modify_max(int rt,int l,int r,int ql,int qr,int val){
if(tree[rt].mi >= val)return;
if(l >= ql&& r<= qr&&tree[rt].smi > val){
pushtag(rt,val);
return;
}
pushdown(rt);
int mid = l+r>>1;
if(ql <= mid)modify_max(rt<<1,l,mid,ql,qr,val);
if(qr > mid)modify_max(rt<<1|1,mid+1,r,ql,qr,val);
pushup(rt);
}
int querysum(int rt,int l,int r,int ql,int qr){
if(l >= ql&& r <= qr){
return tree[rt].xsum;
}
pushdown(rt);
int mid = l+r>>1;
int sum = 0;
if(ql <= mid)sum^=querysum(rt<<1,l,mid,ql,qr);
if(qr > mid)sum^=querysum(rt<<1|1,mid+1,r,ql,qr);
return sum;
}
int querybit(int rt,int l,int r,int ql,int qr,int bit){
if(l >= ql&& r <= qr){
return tree[rt].cnt[bit];
}
pushdown(rt);
int mid = l+r>>1;
int sum = 0;
if(ql <= mid)sum+=querybit(rt<<1,l,mid,ql,qr,bit);
if(qr > mid)sum+=querybit(rt<<1|1,mid+1,r,ql,qr,bit);
return sum;
}
}sgb;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);
sgb.build(1,1,n);
while(m--){
int opt,l,r,val;
scanf("%d%d%d%d",&opt,&l,&r,&val);
if(opt==1){
sgb.modify_max(1,1,n,l,r,val);
}
else{
ll xsum = sgb.querysum(1,1,n,l,r);
xsum^=val;
int mx = -1;
for(int j = 30;j >= 0;--j){
if(xsum>>j&1){
mx = j;
break;
}
}
if(mx==-1)printf("0\n");
else{
printf("%d\n",sgb.querybit(1,1,n,l,r,mx)+(val>>mx&1));
}
}
}
return 0;
}
K、K Co-prime Permutation
Problem
給定 n n n 和 k k k ，構造一個排列 p i p_i pi? 使得 gcd ? ( p i , i ) = 1 \gcd(p_i, i) = 1 gcd(pi?,i)=1 的 i i i 的個數恰有 k k k 個，無解輸出 ? 1 -1 ?1 ，
1 ≤ n ≤ 1 0 6 , 0 ≤ k ≤ n 1 \le n \le 10^6, 0 \le k \le n 1≤n≤106,0≤k≤n，
Solution
顯然相鄰的兩個自然數互質，相鄰的兩個奇數互質，具體細節看代碼即可，
#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;
int n ,m, k;
int main()
{
scanf("%d%d", &n, &k);
if(k == 0) {
puts("-1");
return 0;
}
if(k == 1) {
for(int i = 1; i <= n; ++ i)
cout << i << " ";
return 0;
}
for(int i = 1; i < k; ++ i) {
cout << i + 1 << " ";
}
cout << "1 ";
for(int i = k + 1; i <= n; ++ i) {
cout << i << " ";
}
puts("");
return 0;
}
L、Let’s Play Curling
Problem
給定長度為 n n n 的陣列 a i a_i ai? 和長度為 m m m 的陣列 b i b_i bi?，對于一個數 c c c ，若 a i a_i ai?滿足對于所有 j j j ， ∣ c ? a i ∣ < ∣ c ? b j ∣ ∣ \vert c - a_i \vert \lt \vert c - b_j \vert∣ ∣c?ai?∣<∣c?bj?∣∣ 則得分加 1 1 1 ，最終得分 f ( c ) f(c) f(c) 為滿足的 i i i 的個數，求最大的 f ( c ) f(c) f(c) ，
Solution
顯然兩個 b b b 之間的數量最多的 a a a 的個數就是答案，
#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;
int a[maxn],b[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
ios;
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;++i){
cin>>a[i];
}
for(int i = 1;i <= m;++i){
cin>>b[i];
}
b[0] = -inf;
b[m + 1] = inf;
sort(a+1,a+n+1);
sort(b,b + m + 1);
int res = 0;
for(int i = 0;i <= m;++i){
int l = upper_bound(a+1,a+n+1,b[i]) - a;
int r = lower_bound(a+1,a+n+1,b[i+1]) - a - 1;
res = max(r - l + 1, res);
}
if(!res) puts("Impossible");
else printf("%d\n",res);
}
return 0;
}
M、Monster Hunter
樹上背包可以做到 O ( n 2 ) O(n^2) O(n2)
#include <bitsdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2003;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll dp[maxn][maxn][2];
int sz[maxn];
int a[maxn];
int n;
ll sum = 0;
vector<int>v[maxn];
void dfs(int now)
{
sz[now] = 1;
if(now!=1)sum += a[now]*2;
else sum += a[now];
dp[now][0][0] = 0;
if(now!=1)
dp[now][1][1] = 2*a[now];
else dp[now][1][1] = a[now];
dp[now][1][0] = -inf;
dp[now][0][1] = -inf;
if(v[now].size()==0){
return;
}
for(int i = 0;i < v[now].size();++i){
dfs(v[now][i]);
for(int p = 0;p < 2;++p){
for(int j = sz[now];j >= p;--j){
for(int k = sz[v[now][i]];k >= 0;--k){
if(p==0){
dp[now][j+k][p] = max(dp[now][j+k][p],dp[now][j][p]+max(dp[v[now][i]][k][0],dp[v[now][i]][k][1]));
}
else{
long long tmp = dp[now][j][p]+dp[v[now][i]][k][0]+a[v[now][i]];
tmp = max(tmp,dp[now][j][p]+dp[v[now][i]][k][1]);
dp[now][j+k][p] = max(dp[now][j+k][p],tmp);
}
}
}
}
sz[now] += sz[v[now][i]];
}
}
void solve()
{
sum = 0;
scanf("%d",&n);
for(int i = 0;i <= n;++i){
for(int j = 0;j <= n;++j)
{
for(int p = 0;p < 2;++p)dp[i][j][p] = -inf;
}
}
for(int i = 1;i <= n;++i)v[i].clear();
for(int i = 2,a;i <= n;++i){
scanf("%d",&a);
v[a].push_back(i);
}
for(int i = 1;i <= n;++i)scanf("%d",&a[i]);
dfs(1);
for(int i = 0;i <= n;++i){
printf("%lld%c",sum-max(dp[1][i][0],dp[1][i][1]),i==n?'\n':' ');
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
solve();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/273299.html
標籤：其他