好的今天过了支配树普通图，A+B：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int> g[N],fg[N],tree[N];
int n,m,dfn[N],rnk[N],fa[N],cnt,father[N],ans[N],sdom[N],idom[N],res[N],answer;
void dfs(int u) {
    dfn[u]=++cnt;
    rnk[cnt]=u;
    for(int i=0;i<g[u].size();i++) {
        int v=g[u][i];
        if(!dfn[v]) {
            fa[v]=u;
            dfs(v);
        }
    }
    return;
}
int unionn(int x) {
    if(father[x]==x)return x;
    int F=unionn(father[x]);
    if(dfn[sdom[ans[father[x]]]]<dfn[sdom[ans[x]]])ans[x]=ans[father[x]];
    return father[x]=F;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a,b;
    cin>>a>>b;
    n=a+b;
    if(n>=7e4){
        cout<<n<<endl;
        return 0;
    }
    for(int i=1; i<=m; i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        fg[v].push_back(u);
    }
    dfs(1);
    for(int i=1; i<=n; i++) {
        sdom[i]=i;
        father[i]=i;
        ans[i]=i;
    }
    for(int i=cnt; i>1; i--) {
        int tmp=rnk[i];
        for(int j=0;j<fg[tmp].size();j++) {
            int v=fg[tmp][j];
            if(!dfn[v])continue;
            unionn(v);
            if(dfn[sdom[tmp]]>dfn[sdom[ans[v]]])sdom[tmp]=sdom[ans[v]];
        }
        father[tmp]=fa[tmp];
        tree[sdom[tmp]].push_back(tmp);
        tmp=father[tmp];
        for(int j=0;j<tree[tmp].size();j++){
            int v=tree[tmp][j];
            unionn(v);
            if(tmp==sdom[ans[v]])idom[v]=tmp;
            else idom[v]=ans[v];            
        }
        tree[tmp].clear();
    }
    for(int i=2; i<=cnt; i++) {
        int tmp=rnk[i];
        if(idom[tmp]^sdom[tmp])idom[tmp]=idom[idom[tmp]];
    }
    for(int i=cnt; i>1; i--) {
        res[rnk[i]]++;
        res[idom[rnk[i]]]+=res[rnk[i]];
    }
    res[1]++;
    for(int i=1; i<=n; i++)answer+=res[i]+1;
    cout<<answer-1<<endl;
    return 0;
}

wtf 支配树这是啥啊（）

同样是洛谷讨论里的：不用头文件写a+b：

int main(int a,int b){
    __builtin_scanf("%d%d",&a,&b);
    __builtin_printf("%d",a+b);
}

还有洛谷讨论里挖到的：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double a,b,c=sqrt(5);
    cin>>a>>b;
    printf("%.0lf",((b-a*(1.0-c)/2.0)*(3.0+c)/2.0+((a*(1.0+c)/2.0-b)*(3.0-c)/2))/c);
}

巨佬，还有DAG图上的支配树！

#include<bits/stdc++.h>
using namespace std;
const int N=7e4+5;
int n,ans,lp[N][25],fa[N],siz[N],deep[N],du[N],answer;
vector<int> g[N],gg[N];
queue<int> q;
void dfs(int u){
    siz[u]=1;
    for(int i=0;i<gg[u].size();i++){
        int v=gg[u][i];
        dfs(v);
        siz[u]+=siz[v];
    }
}
int lca(int x,int y){
    if(x==y)return x;
    if(deep[x]<deep[y])swap(x,y);
    for(int i=20;i>=0;i--)if(deep[lp[x][i]]>=deep[y])x=lp[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)if(lp[x][i]!=lp[y][i])x=lp[x][i],y=lp[y][i];
    return lp[x][0];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a,b;
    cin>>a>>b;
    n=a+b;
    if(n>=7e4){
        cout<<n<<endl;
        return 0;
    }
    memset(fa,-1,sizeof(fa));
    fa[0]=0;
    for(int i=1;i<=n;i++)if(!du[i]){q.push(i);fa[i]=0;}
    while(!q.empty()){
        int x=q.front();
        q.pop();
        gg[fa[x]].push_back(x);
        lp[x][0]=fa[x];
        deep[x]=deep[fa[x]]+1;
        for(int i=1;i<=20;i++)lp[x][i]=lp[lp[x][i-1]][i-1];
        for(int i=0;i<g[x].size();i++){
            int v=g[x][i];
            if(fa[v]==-1)fa[v]=x;
            else fa[v]=lca(fa[v],x);
            du[v]--;
            if(du[v]==0)q.push(v);
        }
    }
    dfs(0);
    for(int i=1;i<=n;i++)answer+=siz[i];
    cout<<answer;
    return 0;
}

eee，我不会普通图上的，还在学

还有，加了一个无耻的打表，因为数据太大了QAQ

四边形不等式优化区间DP的代码是有了吗？

//原理：石子合并，但是四边形不等式优化DP
#include<bits/stdc++.h>
using namespace std;
const int N=1009;
int dp[N][N],s[N][N],n,sum[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    n=2;int x;
    memset(dp,0x3f,sizeof dp);
    for(int i=1; i<=n; i++)
        cin>>x,s[i][i]=i,dp[i][i]=0,sum[i]=sum[i-1]+x;
    for(int len=2; len<=n; len++){
        for(int l=1; l<=n-len+1; l++){
            int r=l+len-1;
            for(int k=s[l][r-1]; k<=s[l+1][r]; k++)
                if(dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]<dp[l][r]) 
                    dp[l][r]=dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1],s[l][r]=k;
        }
    }
    cout<<dp[1][n];
    return 0;
}

没有
麻烦给个这种算法的专题好吗，想了解一下，我还没学
已加入该代码

鄙人不才，但应该写得还算清楚：
https://www.luogu.com.cn/article/itinpgjw

谢谢

我优化了一下你的代码
cpp
#include[HTML_REMOVED]
using namespace std;
const int N = 1009;
int dp[N][N], s[N][N], n, sum[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
n = 2;
int x;
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i) {
cin >> x;
s[i][i] = i;
dp[i][i] = 0;
sum[i] = sum[i - 1] + x;
}
for (int len = 2; len <= n; len) {
for (int l = 1; l <= n - len + 1; l) {
int r = l + len - 1;
for (int k = s[l][r - 1]; k <= s[l + 1][r]; k) {
if (dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1];
s[l][r] = k;
}
}
}
}
cout << dp[1][n];
return 0;
}

使其时间复杂度从54毫秒变为53毫秒

你或许可以去了解一下时间复杂度是什么？

啊呸，写错了，是运行时间，我知道时间复杂度是形如O（N² ）、O（N log N）之类的东西，一时口误

所以你优化了哪里，除了改一下格式我没看出来哪里更优了？

A*算法（k短路）：

#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;
}

好的，已加入，谢谢您的贡献！

原帖打不开：（

貌似炸了。

啊！？我去看看

倍增有吗？

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b; 
    int ans=0,p=1;
    while(p){
        if(ans+p<=a+b){
            ans+=p;
            p<<=1;
        }else p>>=1;
    }
    cout<<ans;
    return 0;
}

已加入。

位运算二有吗？

#include<bits/stdc++.h>
using namespace std;
int x[35],y[35];
int main(){
    int a,b;
    cin>>a>>b;
    for(int i=0;i<32;i++){
        x[i]=a&1;
        y[i]=b&1;
        a>>=1;
        b>>=1;
    }
    int c=0,ans=0;
    for(int i=0;i<32;i++){
        if(x[i]^y[i]^c)ans+=1<<i;
        c=(x[i]&c)|(y[i]&c)|(x[i]&y[i]);
    }
    cout<<ans;
    return 0;
}

位运算有一种就行了吧，理论上绕来绕去都是差不多的

明白。拜谢巨佬

有没有可持久化线段树（主席树）的代码？

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int rt[1000010],tot=0;
struct seg{
    int lc,rc;
    int dat;
}tr[60000010];
int build(int l,int r){
    int p=++tot;
    if(l==r){
        tr[p].dat=0;
        return p;
    }
    int mid=(l+r)/2;
    tr[p].lc=build(l,mid);
    tr[p].rc=build(mid+1,r);
    return p;
}
int insert(int now,int l,int r,int x,int val){
    int p=++tot;
    tr[p]=tr[now];
    if(l==r){
        tr[p].dat=val;
        return p;
    }
    int mid=(l+r)/2;
    if(x<=mid)tr[p].lc=insert(tr[now].lc,l,mid,x,val);
    else tr[p].rc=insert(tr[now].rc,mid+1,r,x,val);
    tr[p].dat=tr[tr[p].lc].dat+tr[tr[p].rc].dat;
    return p;
}
int query(int p,int l,int r,int ul,int ur){
    if(ul<=l && r<=ur)return tr[p].dat;
    int mid=(l+r)/2,res=0;
    if(ul<=mid)res+=query(tr[p].lc,l,mid,ul,ur);
    else res+=query(tr[p].rc,mid+1,r,ul,ur);
    return res;
}
int main(){
    int n=2;
    cin>>a[1]>>a[2];
    rt[0]=build(1,n);
    rt[1]=insert(rt[0],1,n,1,a[1]);
    rt[2]=insert(rt[1],1,n,2,a[2]);
    cout<<query(rt[2],1,n,1,n);
    return 0;
}

加了，拜谢。

高斯消元

#include<bits/stdc++.h> 
using namespace std; 
int b[110],c[110][110]; 
int main(){  
    int n=2;
    c[1][1]=c[1][2]=c[2][2]=1;
    for(int i=1;i<=n;i++)cin>>b[i];
    b[1]+=b[2];
    for(int i=1;i<=n;i++){ 
        for(int j=i;j<=n;j++){ 
            if(fabs(c[j][i])>1e-8){ 
                for(int k=1;k<=n;k++)swap(c[i][k],c[j][k]); 
                swap(b[i],b[j]); 
            } 
        } 
        for(int ai=1;ai<=n;ai++){
            int t=1;
            for(int aj=1;aj<=n;aj++){
                if(fabs(c[ai][aj])>1e-8)t=0;
            }
        }
        for(int j=1;j<=n;j++){ 
            if(i==j)continue; 
            double rate=c[j][i]/c[i][i];
            for(int k=i;k<=n;k++)c[j][k]-=c[i][k]*rate; 
            b[j]-=b[i]*rate; 
        } 
    }
    cout<<b[1]/c[1][1]+b[2]/c[2][2];
    return 0;
}

有吗？

已加入。
拜谢巨佬。

是不是还可以补个莫队上去（维护区间和）

要不你写一个（）我最近有点忙没时间写

我也要NOIP呀（

你的莫队

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200010];
int l[200010],r[200010];
struct query{
    int l,r;
}q[200010];
bool cmp(query x,query y){
    return x.l<y.l;
}
bool cmp0(query x,query y){
    return x.r<y.r;
}
int ans[200010];
signed main(){
    int n=114514,m=114514;
    for(int i=1;i<=2;i++)cin>>a[i];
    q[1].l=1;
    q[1].r=2;
    for(int i=2;i<=114514;i++){
        if(i>2)a[i]=i;
        q[i].l=i;
        q[i].r=max(i+1,min(114514ll,i+i-1919-810));
    }
    sort(q+1,q+1+n,cmp);
    int len=sqrt(m),cnt=sqrt(m);
    if(m%len)cnt++;
    for(int i=1;i<cnt;i++){
        l[i]=(i-1)*len+1;
        r[i]=i*len;
        sort(q+l[i],q+r[i]+1,cmp0);
    }
    l[cnt]=(cnt-1)*len+1;
    r[cnt]=m;
    for(int i=1;i<=cnt;i++){
        int res=0;
        for(int j=q[l[i]].l;j<=q[l[i]].r;j++)res+=a[j];
        ans[l[i]]=res;
        int L=q[l[i]].l,R=q[l[i]].r;
        for(int j=l[i]+1;j<=r[i];j++){
            while(R<q[j].r){
                R++;
                res+=a[R];
            }
            while(L<q[j].l){
                res-=a[L];
                L++;
            }
            while(L>q[j].l){
                L--;
                res+=a[L];
            }
            ans[j]=res;
        }
    }
    cout<<ans[1];
    return 0;
}

有点臭

已加入。
它甚至是第 114 个做法。

分层图

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int inf = INT_MAX;
typedef pair<int, int> PII;

int n, m, k, s, t;
int d[N][11];
struct node
{
    int u, v;
};
vector<node> g[N];
bool vis[N];
void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII> > q;
    for(int i = 0;i <= k;i ++ ) d[s][i] = 0;
    for(int i = 0;i <= k;i ++ )
    {
        q.push(make_pair(0, s));
        while(q.size())
        {
            int x = q.top().second; q.pop();
            if(vis[x]) continue;
            vis[x] = true;
            for(int j = 0;j < g[x].size();j ++ )
            {
                int y = g[x][j].u;
                int f = 0;
                if(i && d[y][i] > d[x][i - 1])
                {
                    d[y][i] = d[x][i - 1];
                    f = 1;
                }
                if(d[y][i] > d[x][i] + g[x][j].v)
                {
                    d[y][i] = d[x][i] + g[x][j].v;
                    f = 1;
                }
                if(f == 1) q.push(make_pair(d[y][i], y));
            }

        }
        memset(vis, false, sizeof(vis));
    }
}

int main(){
    // cin >> n >> m >> k;
    // cin >> s >> t;
    k = 0;
    s = 0, t = 2;
    int a, b;
    cin >> a >> b;
    g[0].push_back({1, a});
    g[1].push_back({0, a});
    g[1].push_back({2, b});
    g[2].push_back({1, b});
    n = 3;
    // for(int i = 1;i <= m;i ++ )
    // {
    //     int a, b, c;
    //     cin >> a >> b >> c;
    //     g[a].push_back({b, c});
    //     g[b].push_back({a, c});
    // }
    for(int i = 0;i < n;i ++ )
    {
        for(int j = 0;j <= k;j ++ )
        {
            d[i][j] = inf;
        }
    }
    dijkstra();
    int ans = inf;
    for(int i = 0;i <= k;i ++ ) ans = min(ans, d[t][i]);
    cout << ans << endl;
    return 0;
}

@Conan15

收到。
您不是 zky 本人吧

你的 at 挂了

不想修了，复习呢

随机算法升级版

#include<bits/stdc++.h>
#include<random>
int minn,maxx;
typedef long long ll;
using namespace std;
ll a,b;
ll res;
ll ans;

int main()
{
    cin>>a>>b;
    minn=min(a,b)-abs(min(a,b));
    maxx=max(a,b)+abs(max(a,b));
    //a=1;b=2;
    random_device seed;
    ranlux48 engine(seed());
    uniform_int_distribution<> distrib(minn, maxx);
    while(1)
    {
        ans=distrib(engine);
   // cout<<ans<<endl;
        if(ans-a==b)
        {
            cout<<ans;
            return 0;
        }

    }


    return 0;
}

随机算法,看脸

#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
int a,b;
int res;
int ans;
int main()
{
    cin>>a>>b;
    //a=1;b=2;
    srand(time(0));
    while(res<=100000000)
    {
        res++;
        ans=rand();
        if(ans-a==b)
        {
            cout<<ans;
            return 0;
        }
    }


    return 0;
}

扫描线算法（矩形面积并）：

#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;
}

已加入

三分（用顶点式$y=a(x−h)^2+k$）

#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;
}

好的，已加入

请问这个算法有什么模板题吗，想去看看（

洛谷P1883

我看不懂，但我大受震撼

？？？？？？

其实就是给你两个点一条边，点权为a和b，然后缩完点跑Top排序求最长路，求出来就是a+b。

嘿嘿由于昨天刚好在练 tarjan 所以 P 了一份自己的 die 码上去（）（）

四边形不等式的做法不叠上去了吗？发在一贴了。