[ 算法竞赛进阶指南 0x00 ] 杂谈
持续更新。。。。
汉诺塔
首先考虑n个盘子3塔的经典Hanoi问题，设dn表示求解n个盘子3塔问题的最少步数，显然有
dn=2∗dn−1+1
含义为把前n−1个盘子从A借助C转移到B，再将第n个盘子转移到C，最后把n−1个盘子从B借助A转移到C。
类似地，对于本题，设f[n]表示求解n个盘子4塔问题的最小步数，则有
fn=min(2∗fi+dn−i)(1≤i<n)
含义为把前i个盘子在4柱的情况下从A转移到B，再将n−i个盘子在3柱的情况下从A转移到D，最后再将i个盘子在4柱的情况下从B转移到D
那么对于n盘m塔的问题(m>4)，就有
fn,m=min(2∗fi,m+fn−i,m−1)(1≤i<n)
使得我们可以在O(n2∗m)的复杂度内求解该问题
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
typedef long long ll;
const int maxn = 25 + 5 ;
const int INF = 0x3f3f3f3f;
int n, m, mod;
int dp[20];
int d[20];
signed main() {
fastio;
d[1] = 1;
for(int i = 2; i <= 15; i++) {
d[i] = d[i - 1] * 2 + 1;
}
memset(dp, 0x3f, sizeof(dp));
dp[1] = 1;
for(int i = 2; i <= 15; i++) {
for(int j = 1; j < i; j++) {
dp[i] = min(dp[i], d[i - j] + dp[j] * 2);
} // 2 * 4塔模式 + 1 * 3塔模式
}
for(int i = 1; i <= 12; i++) {
cout << dp[i] << endl;
}
return 0;
}
对顶堆
小堆(pop大的) 保持小堆刚好大于大根堆一个 这样小堆队首第一个就是中位数
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
typedef long long ll;
const int maxn = 1e4 + 5 ;
int n, m, mod;
int a[maxn];
int que[maxn], tail, head;
signed main() {
fastio;
int t;
cin >> t;
for(int cas = 1; cas <= t; cas++) {
priority_queue<int, vector<int>, greater<int> > xh;
priority_queue<int, vector<int>, less<int> > dh;
cin >> m;
cin >> n;
cout << m << " " << (n + 1) / 2 << endl;
tail = 1;
head = 1;
for(int i = 1; i <= n; i++) {
cin >> m;
if(i == 1)
xh.push(m);
else if(xh.top() < m)
xh.push(m);
else
dh.push(m);
if(xh.size() < dh.size())
xh.push(dh.top()), dh.pop();
else if(xh.size() > dh.size()+1)
dh.push(xh.top()), xh.pop();
if(i & 1)
que[tail++] = xh.top();
}
for(int i = head; i < tail; i++) {
cout << que[i] << " ";
if(i % 10 == 0)
cout << endl;
}
cout << endl;
}
return 0;
}
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
typedef long long ll;
const int maxn = 1e4 + 5 ;
int n, m, mod;
int a[maxn];
int que[maxn], tail, head;
signed main() {
fastio;
int t;
cin >> t;
for(int cas = 1; cas <= t; cas++) {
priority_queue<int, vector<int>, greater<int> > xh;
priority_queue<int, vector<int>, less<int> > dh;
cin >> m;
cin >> n;
cout << m << " " << (n + 1) / 2 << endl;
tail = 1;
head = 1;
for(int i = 1; i <= n; i++) {
cin >> m;
if(i == 1)
xh.push(m);
else if(xh.top() < m)
xh.push(m);
else
dh.push(m);
if(xh.size() < dh.size())
xh.push(dh.top()), dh.pop();
else if(xh.size() > dh.size()+1)
dh.push(xh.top()), xh.pop();
if(i & 1)
que[tail++] = xh.top();
}
for(int i = head; i < tail; i++) {
cout << que[i] << " ";
if(i % 10 == 0)
cout << endl;
}
cout << endl;
}
return 0;
}
约数之和
分治 入门 极大的降低复杂度
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 100000 + 5 ;
const int INF = 0x3f3f3f3f ;
const int mod = 9901 ;
int p[50], c[50];
int cnt;
void divide(int n) {
cnt = 0;
for(int i = 2; i <= sqrt(n); i++) {
if(n % i == 0) {
p[++cnt] = i, c[cnt] = 0;
while(n % i == 0)
n /= i, c[cnt]++;
}
}
if(n > 1)
p[++cnt] = n, c[cnt] = 1;
}
int power(int a, int b) {
int res = 1 % mod;
while(b) {
if(b & 1)
res = 1ll * res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int sum(int pt, int ct) {
if(ct == 0)
return 1;
if(ct % 2 == 1)
return ((1 + power(pt, (ct + 1) >> 1)) * sum(pt, (ct - 1) >> 1)) % mod;
else
return ((1 + power(pt, ct >> 1)) * sum(pt, (ct >> 1) - 1) % mod + power(pt, ct)) % mod;
}
signed main() {
fastio;
int a, b;
cin >> a >> b;
if(a == 0) {
cout << 0 << endl;
return 0;
}
divide(a);
int ans = 1;
for(int i = 1; i <= cnt; i++) {
ans = (ans * sum(p[i], c[i] * b)) % mod;
}
cout << ans << endl;
return 0;
}
最佳牛围栏 二分左右边界问题
二分平均值
当平均值够的时候 我们的某个不小于L的字段和应该大于0
此时 对于每个值-=mid
不断二分
最后找刚好使字段和足够支持mid的l r 便是答案
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 100000 + 5 ;
const int INF = 0x3f3f3f3f ;
const int mod = 9901 ;
const double eps = 1e-8;
int n, L;
double a[maxn], b[maxn];
double sum[maxn];
bool chk(double mid) {
for(int i = 1; i <= n; i++)
b[i] = a[i] - mid;
for(int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + b[i];
double min_val = 1e10, ans = -1e10;
for(int i = L ; i <= n; i++) {
min_val = min(min_val, sum[i-L]);
ans = max(ans, sum[i] - min_val);
}
return ans >= 0;
}
signed main() {
fastio;
cin >> n >> L;
for(int i = 1; i <= n; i++)
cin >> a[i];
double l = 0, r = 1e8;
while(r-l>=eps) {
double mid = (l + r) / 2;
if(chk(mid))
l = mid;
else
r = mid;
}
cout << (int)(r * 1000) << endl;
return 0;
}
三分
链接 ： [ 三分法 ] 单峰(单谷)函数 三分找极点 ；
七夕祭
这题和货舱选址 用中位数 并且 和 均分纸牌有关
首先我们 先想 对一个列 or 行 进行纸牌均分 而且他是成环的 我们可以考虑从k人隔开
跑 P33 上 前缀和那个公式 但是我们发现 为了让这个和最小 我们最好 选中位数(货舱选址) 所以这题就这样狗出来了
ps N, M, 这东西打反也没有谁了 wa2法。。。
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int maxn = 100000 + 5;
int N, M, T;
int c[2][maxn], a[maxn], s[maxn];
signed main(){
cin >> N >> M >> T;
for(int i = 1; i <= T; i ++ ) {
int x, y;
cin >> x >> y;
c[0][y] ++;
c[1][x] ++;
}
if((T % N) != 0 && (T % M) != 0) {
cout << "impossible" << endl;
return 0;
}
int ans = 0, flag = 0, ok = 0;
if((T % M) == 0){
int TM = T / M;
for(int i = 1; i <= M; i ++ ) {
a[i] = c[0][i] - TM;
s[i] = s[i - 1] + a[i];
}
sort(s + 1, s + 1 + M);
int mid = s[M + 1 >> 1];
for(int i = 1; i <= M; i ++ ) {
ans += abs(s[i] - mid);
}
ok = 1;
}
if((T % N) == 0){
int TM = T / N;
for(int i = 1; i <= N; i ++ ) {
a[i] = c[1][i] - TM;
s[i] = s[i - 1] + a[i];
}
sort(s + 1, s + 1 + N);
int mid = s[N + 1 >> 1];
for(int i = 1; i <= N; i ++ ) {
ans += abs(s[i] - mid);
}
flag = 1;
}
if(flag && ok) cout << "both " << ans << endl;
else if(flag) cout << "row " << ans << endl;
else cout << "column " << ans << endl;
return 0;
}
倍增 未完 待续
