$$\Huge版权声明$$
原作者为 Conan15。
$$\Huge转载请注明出处。$$
$$\Huge 原帖戳这里$$
温馨提示:此题解适合人群为算法学习者,不那么适合语法基础课还没学完的学生,对于初学者,建议看看yxc视频
由于原帖的 markdown die 码超过 10w 字符了写不下,
所以又开了一个……
正文继续!
算法一百零六、缩点
感谢 @Shine_Cai 提供思路。
原理:给定一个 n 个点 m 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大,可以用缩点做。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 15, M = 2e5 + 10;
vector<int> edge[N];
int h[N], e[M], ne[M], idx, p[N];
int in[N];
int n, m;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
in[b]++;
}
int dfn[N], low[N], tot = 0;
stack<int> stk;
bool st[N];
int sz[N], scc[N], color;
void tarjan(int u) {
dfn[u] = low[u] = ++tot;
stk.push(u); st[u] = true;
for (int v : edge[u]) {
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (st[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++color;
while (stk.top() != u) {
scc[stk.top()] = color;
st[stk.top()] = false; stk.pop();
}
scc[stk.top()] = color;
st[stk.top()] = false; stk.pop();
}
}
queue<int> q;
int dp[N];
void topsort() {
for (int i = 1; i <= color; i++) {
dp[i] = sz[i];
if (in[i] == 0) q.push(i);
}
while (q.size()) {
int u = q.front(); q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
dp[v] = max(dp[v], dp[u] + sz[v]); in[v]--;
if (in[v] == 0) q.push(v);
}
}
int ans = 0;
for (int i = 1; i <= color; i++) ans = max(ans, dp[i]);
printf("%d\n", ans);
}
int main() {
memset(h, -1, sizeof h);
n = 2, m = 1;
for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
while (m--) {
int a = 1, b = 2;
edge[a].push_back(b);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++) {
sz[scc[i]] += p[i];
for (int j : edge[i])
if (scc[i] != scc[j]) add(scc[i], scc[j]);
}
topsort();
return 0;
}
算法一百零七、A* 算法(k 短路)
感谢 [@Hugo_Von] 同学的贡献。
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int amou=1e3+90,M=2e4+90;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
int head[amou],hh[amou],nxt[M],ver[M],cnt,edge[M];
bool we[amou];
int H[amou],times[amou];
int n,m,k,S,T;
void add(int head[],int a,int b,int c){
nxt[++cnt]=head[a],head[a]=cnt,ver[cnt]=b,edge[cnt]=c;
}
void Dijkstra(){
priority_queue<PII,vector<PII>,greater<PII> >kl;
kl.push({0,T});
memset(H,0x3f,sizeof H);
H[T]=0;
while(!kl.empty())
{
PII tou=kl.top();
kl.pop();
int i=tou.y;
if(we[i]) continue;
we[i]=1;
for(int io=hh[i];io;io=nxt[io])
{
int v=ver[io];
if(H[v]>H[i]+edge[io])
{
H[v]=H[i]+edge[io];
kl.push({H[v],v});
}
}
}
}
void Astar(){
priority_queue<PIII,vector<PIII>,greater<PIII> >kl;
kl.push({H[S],{0,S}});
while(!kl.empty())
{
PIII tou=kl.top();
kl.pop();
int i=tou.y.y,G=tou.y.x;
times[i]++;
if(i==T)
{
if(times[T]==k)
{
cout<<G;
return;
}
continue;
}
for(int io=head[i];io;io=nxt[io])
{
int v=ver[io];
if(times[v]<k)
kl.push({edge[io]+G+H[v],{edge[io]+G,v}});
}
}
}
int main(){
n=3,m=3,k=2;
S=n,T=1;
int one,two;
cin>>one>>two;
add(head,3,2,one);
add(hh,2,3,one);
add(head,2,1,two);
add(hh,1,2,two);
add(head,3,1,0);
add(hh,1,3,0);
Dijkstra();
Astar();
return 0;
}
算法一百零八、三分
用顶点式 $y=a(x-h)^2+k$
感谢 [@Hugo_Von] 同学的贡献。
#include<bits/stdc++.h>
using namespace std;
int a,b;
long long f(int x){
return (long long)(x-a-b)*(x-a-b);
}
int main(){
cin>>a>>b;
int l=-1,r=1000000000;
while(l+1<r){
int mid1=l+(r-l)/3,mid2=mid1+(r-l)/3;
if(f(mid1)>f(mid2)) l=mid1;
else r=mid2;
}
cout<<l+1;
return 0;
}
算法一百零九、扫描线算法(矩形面积并)
感谢 [@Hugo_Von] 同学的贡献。
#include<bits/stdc++.h>
using namespace std;
long long ans;
long long n;
long long xa,xb,ya,yb;
long long y[210000];
struct smx{
long long ya,yb,x,mark;
}line[210000];
bool cmp(smx a,smx b){return a.x<b.x;}
struct node{
long long c,tag;
}tr[810000];
void pushup(long long num,long long l,long long r) {
if(!tr[num].tag){
if(l==r)tr[num].c=0;
else tr[num].c=tr[num<<1].c+tr[num<<1|1].c;
}
}
void change(long long num,long long l,long long r,long long ya,long long yb,long long k){
if(ya<=l&&r<=yb){
tr[num].tag+=k;
if(tr[num].tag)tr[num].c=y[r+1]-y[l];
else tr[num].c=0;
pushup(num,l,r);
return ;
}
long long mid=(l+r)>>1;
if(ya<=mid)change(num<<1,l,mid,ya,yb,k);
if(mid+1<=yb)change(num<<1|1,mid+1,r,ya,yb,k);
pushup(num,l,r);
}
int main(){
int one,two;
cin>>one>>two;
n=2;
xa=0,ya=0,xb=1,yb=one;
y[1]=ya;y[2]=yb;
line[1]=(smx){ya,yb,xa,3};line[2]=(smx){ya,yb,xb,-3};
xa=10,ya=0,xb=11,yb=two;
y[3]=ya;y[4]=yb;
line[3]=(smx){ya,yb,xa,3};line[4]=(smx){ya,yb,xb,-3};
n<<=1;
sort(y+1,y+n+1);
sort(line+1,line+n+1,cmp);
int len=unique(y+1,y+n+1)-(&y[1])-1;
for(int i=1;i<n;i++){
ya=lower_bound(y+1,y+len+2,line[i].ya)-y;
yb=lower_bound(y+1,y+len+2,line[i].yb)-y-1;
change(1,1,len,ya,yb,line[i].mark);
ans+=tr[1].c*(line[i+1].x-line[i].x);
}
cout<<ans;
return 0;
}
A*算法(k短路):
好的,已加入,谢谢您的贡献!
原帖打不开:(
貌似炸了。
啊!?我去看看
你说得对,很不幸的是,。。。你的电脑炸了
我这里可以 awa
哟这不是阔别已久的 2AK 吗?(我没记错吧
随机算法升级版
随机算法,看脸
扫描线算法(矩形面积并):
已加入
三分(用顶点式$y=a(x−h)^2+k$)
好的,已加入
请问这个算法有什么模板题吗,想去看看(
洛谷P1883
我看不懂,但我大受震撼
??????
其实就是给你两个点一条边,点权为a和b,然后缩完点跑Top排序求最长路,求出来就是a+b。
嘿嘿由于昨天刚好在练 tarjan 所以 P 了一份自己的 die 码上去()()
四边形不等式的做法不叠上去了吗?发在一贴了。
%%%
%%%
你们在楼上吗
三楼
第一间
Orz
打比赛ing.jpg