Part 2 基础算法
P1024 [NOIP2001 提高组] 一元三次方程求解
做法1. 二分
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps = 1e-4;
double a, b, c, d;
double f(double x)
{
return a * x * x * x + b * x * x + c * x + d;
}
int main()
{
cin >> a >> b >> c >> d;
int cnt = 0;
for (int i = -100; i < 100; i ++ )
{
double l = i, r = l + 1;
double fl = f(l), fr = f(r);
if (fl == 0)
{
printf("%.2lf ", l);
++ cnt;
}
if (fl * fr < 0)
{
while (r - l >= eps)
{
double mid = (l + r) / 2;
if (fl * f(mid) <= 0)
{
r = mid;
}
else l = mid;
}
printf("%.2lf ", l);
++ cnt;
}
if (cnt == 3) break;
}
return 0;
}
做法2.盛金公式:
题解博主的博客
一元三次方程:aX的三次方+bX的二次方+cX+d=0
重根判别公式:
A=b的二次方-3ac
B=bc-9ad
C=c的二次方-3bd
当A=B=0时,X1=X2=X3= -b/3a= -c/b = -3d/c
#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;
int main()
{
double a,b,c,d;
double as,bs,t,si;
double x1,x2,x3;
cin>>a>>b>>c>>d;
as=b*b-3*a*c;
bs=b*c-9*a*d;
t=(2*as*b-3*a*bs)/(2*sqrt(as*as*as));
si=acos(t);
x1=(-b-2*sqrt(as)*cos(si/3))/(3*a);
x2=(-b+sqrt(as)*(cos(si/3)+sqrt(3)*sin(si/3)))/(3*a);
x3=(-b+sqrt(as)*(cos(si/3)-sqrt(3)*sin(si/3)))/(3*a);
cout<<fixed<<setprecision(2)<<x1<<" ";
cout<<fixed<<setprecision(2)<<x3<<" ";
cout<<fixed<<setprecision(2)<<x2<<" ";
return 0;
}
解法3. 牛顿迭代
博客
牛顿迭代法,看到没人用这种方法,就写了一个。
对于一个已知的x值,每一次根据函数在这一点的导数,把x移动到,切线与x轴相交的地方。
即x[n+1]=x[n]-f(x)/f'(x),可以证明结果会趋近于函数的一个解,据说这种方法比二分要快。
#include<cstdio>
#include<complex>
#include<algorithm>
#include<set>
using namespace std;
struct func3
{
double a,b,c,d;
func3(double A=0,double B=0,double C=0,double D=0){a=A;b=B;c=C;d=D;}
double operator()(double x){return ((a*x+b)*x+c)*x+d;}
double dvt(double x){return (3.0*a*x+2.0*b)*x+c;}
};
void func3solve(func3 f,double st,double& val,double& sol)
{
for(int i=1;!(abs(f(st))<1e-6) && i<=100;i++)
{
st=st-f(st)/f.dvt(st);
}
val=f(st);sol=st;
}
double fix2(double sol)
{
return (double)int(sol*100.0+(sol>0?0.5:-0.5))/100.0;
}
set<double>solutions;
int main()
{
double a,b,c,d;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
func3 f(a,b,c,d);
for(double i=-100.0;i<=100.0;i+=0.5)
{
double val,sol;
func3solve(f,i,val,sol);
sol=fix2(sol);
if(abs(val)<1e-6 && solutions.find(sol)==solutions.end())
solutions.insert(sol);
}
for(set<double>::iterator it=solutions.begin();it!=solutions.end();it++)
{
double x=(*it);
printf("%.2lf ",x);
}
return 0;
}
两种解法, 第一种解法自己踩坑.....第二种值得学习
P1902 刺杀大使
解法1. bfs + 二分 坑点在于要注意内存限制, 如果再手写PII队列,会爆内存, 所以这里选择STL
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m;
int g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool bfs(int x)
{
memset(st, 0, sizeof st);
queue<PII> q;
q.push(make_pair(1, 1));
st[1][1] = 1;
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int a = t.x + dx[i];
int b = t.y + dy[i];
if(a < 1 || a > n || b < 1 || b > m || st[a][b] || g[a][b] > x) continue;
st[a][b] = true;
if(a == n) return true;
else q.push(make_pair(a, b));
}
}
return false;
}
int main()
{
cin >> n >> m;
int l = 1e8, r = -1e8;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &g[i][j]);
l = min(l, g[i][j]);
r = max(r, g[i][j]);
}
while (l < r)
{
// cout << "l=" << l << " r= " << r << endl;
int mid = l + r >> 1;
if (bfs(mid)) r = mid; // 如果满足要求,说明当前使用的mid可能是最小的最大值,也可能不是,要到左边区间继续找
else l = mid + 1;
}
cout << l << endl;
return 0;
}
解法2 MST最小生成树
佬的博客
最大点权最小
根据最大,我们可以想到如果我们要点转边,两点之间的边权应为两端点的点权最大值。
根据最小,得出:我们需要选择一些边来使第一行和最后一行连通,这些边的权尽量小
现在我的思路就显而易见了:MST(最小生成树)
但是又不是裸的最小生成树。我们不需要选择n-1条边,只需要使首尾两行连通。
所以我们选择Kruskal算法,用并查集维护:
#include<bits/stdc++.h>
using namespace std;
int get()
{
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
const int MaxN = 1005;
const int inf = 0x3f3f3f3f;
int p[MaxN][MaxN];
int n, m, maxn = -inf;
struct Edge {
int u, v, w;
} edge[10000005];
int k = 0;
int fa[10000005];
int MAP(int x, int y) { return (x - 1) * m + y; } //此函数用于求(x,y)在图中的编号
int find(int x) { return (x == fa[x]? x : fa[x] = find(fa[x])); } //一行并查集
bool cmp(Edge a, Edge b) { return a.w < b.w; } //一行cmp
void kruskal() //克鲁斯卡尔算法:
{
sort(edge + 1, edge + k + 1, cmp); //首先将边按权值排序
int st = MAP(1, 1); //指定一个开始点:第一个
int ed = MAP(n, m); //指定一个结束点:最后一个
for(int i = 1; i <= k; i++) { //枚举边:
int u = edge[i].u;
int v = edge[i].v;
int x = find(u), y = find(v); //取出u、v所在连通块
if(x != y) //若在同一连通块,我们就算去合并也没有多大意义,这样可以稍微节省时间
{
maxn = max(maxn, edge[i].w); //更新最大边权
fa[x] = fa[y]; //将两边连通
if(find(st) == find(ed)) return; //如果开始点和结束点连通了,说明可以退出了
}
}
}
int main()
{
n = get(), m = get();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
p[i][j] = get();
fa[MAP(i, j)] = MAP(i, j); //在读入的时候顺便初始化并查集
}
}
//重点:连边
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int u = MAP(i, j); //这个点
int v1 = MAP(i, j + 1); //向右连边
int v2 = MAP(i + 1, j); //向下连边
//因为是无向图,只用向两个方向连边
//权值是两点权间的较小值
if(j + 1 <= m) edge[++k] = {u, v1, max(p[i][j], p[i][j + 1])}; //注意判断越界。
if(i + 1 <= n) edge[++k] = {u, v2, max(p[i][j], p[i + 1][j])};
}
}
/*
for(int i = 1; i <= k; i++) {
printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);
}
*/
kruskal(); //跑MST算法
printf("%d", maxn); //输出解
return 0;
}
分治
P1429 平面最近点对(加强版)
题解
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1000001;
const int INF = 2 << 20;
int n, temp[maxn];
struct Point
{
double x, y;
} S[maxn];
bool cmp(const Point &a, const Point &b)
{
if(a.x == b.x) return a.y < b.y;
else return a.x < b.x;
}
bool cmps(const int &a, const int &b) { return S[a].y < S[b].y; }
double min(double a, double b) { return a < b ? a : b; }
double dist(int i, int j)
{
double x = (S[i].x - S[j].x) * (S[i].x - S[j].x);
double y = (S[i].y - S[j].y) * (S[i].y - S[j].y);
return sqrt(x + y);
}
double merge(int left, int right)
{
double d = INF;
if(left == right) return d;
if(left + 1 == right) return dist(left, right);
int mid = left + right >> 1;
double d1 = merge(left, mid);
double d2 = merge(mid + 1, right);
d = min(d1, d2);
int i, j, k = 0;
for(i = left; i <= right; i++)
if(fabs(S[mid].x - S[i].x) < d) // 这里不太一样
temp[k++] = i;
sort(temp, temp + k, cmps);
for(i = 0; i < k; i++)
for(j = i + 1; j < k && S[temp[j]].y - S[temp[i]].y < d; j++)
{
double d3 = dist(temp[i], temp[j]);
if(d > d3) d = d3;
}
return d;
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%lf%lf", &S[i].x, &S[i].y);
sort(S, S + n, cmp);
return !printf("%.4lf\n", merge(0, n - 1));
}
贪心
P1199 [NOIP2010 普及组] 三国游戏
由于机器是后选且贪心, 人和机器都不可能凑齐最大值
所以我们获胜的方法就是,选择次大值所在行,然后电脑选择最大值另一匹配对象
最终两个都没有最大, 我们选择次大值获胜
所以只需要sort + 找出每一行次大值中最大的一个
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n;
int g[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ )
{
scanf("%d", &g[i][j]);
g[j][i] = g[i][j];
}
int ans = 0;
for (int i = 1; i <= n; i ++ )
{
sort(g[i] + 1, g[i] + n + 1);
if (g[i][n - 1] > ans)
ans = g[i][n - 1];
}
cout << 1 << endl << ans << endl;
return 0;
}
依旧贪心
P2672 [NOIP2015 普及组] 推销员
按照疲劳值排序,每次有两种可能
1. 直接按照疲劳值从高到低选i个
2. 前i - 1个选疲劳值高的, 最后一个根据2 * s + a来找,提前从后往前遍历预处理数组h[i]记录从i到n中上值最大的
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,sum[100010],q[100010],h[100010];//n 疲劳前缀和 前i个最大值 后i个最大值
struct node{
int s;//距离
int a;//疲劳
}v[100010];
bool cmp(node x,node y){return x.a>y.a;}
int main()
{ scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&v[i].s);
for(int i=1;i<=n;i++)scanf("%d",&v[i].a);
sort(v+1,v+1+n,cmp);//按疲劳从高到低排序
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+v[i].a; // 排序后疲劳值的前缀和
for(int i=1;i<=n;i++)q[i]=max(q[i-1],2*v[i].s);//前i个的距离最大值
for(int i=n;i>=1;i--)h[i]=max(h[i+1],2*v[i].s+v[i].a);//后i个最大值
for(int i=1;i<=n;i++)printf("%d\n",max(sum[i]+q[i],sum[i-1]+h[i])); // 要么是直接按疲劳从高到低,要么前i-1个疲劳高的选上,最后一个选距离远的
return 0;
}
还是贪心 完全想不到
P2123 皇后游戏
题解
没啥好说的了直接看题解吧, 证明过程好好捋捋
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 2e4 + 10;
struct Node
{
int x, y, d;
bool operator< (Node &W) const
{
if (d != W.d) return d < W.d;
if (d <= 0) return x < W.x;
return y > W.y;
}
} a[N];
int t, n;
long long c[N];
int main()
{
cin >> t;
for (int k = 1; k <= t; k ++ )
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
scanf("%d%d", &a[i].x, &a[i].y);
if (a[i].x > a[i].y) a[i].d = 1;
else if (a[i].x < a[i].y) a[i].d = -1;
else a[i].d = 0;
}
sort(a + 1, a + n + 1);
LL s = 0;
for (int i = 1; i <= n; i ++ )
{
s += a[i].x;
c[i] = max(c[i - 1], s) + a[i].y;
}
cout << c[n] << endl;
}
return 0;
}
高精度压位
P1303 A*B Problem
#include<iostream>
#include<cstring>
using namespace std;
char a1[50001],b1[50001];
int a[50001],b[50001],i,x,len,j,c[50001];
int main ()
{
cin >>a1 >>b1;//读入两个数
a[0]=strlen(a1);b[0]=strlen(b1);//计算长度
for (i=1;i<=a[0];++i)a[i]=a1[a[0]-i]-'0';//将字符串转换成数字
for (i=1;i<=b[0];++i)b[i]=b1[b[0]-i]-'0';
for (i=1;i<=a[0];++i)for (j=1;j<=b[0];++j)c[i+j-1]+=a[i]*b[j];//按乘法
len=a[0]+b[0]; //原理进行高精乘
for (i=1;i<len;++i)if (c[i]>9){c[i+1]+=c[i]/10;c[i]%=10;}//进位
while (c[len]==0&&len>1)len--;//判断位数
for (i=len;i>=1;--i)cout <<c[i];//输出
return 0;
}