danihao123's Blog

这个题需要一些脑洞。

给出任意三点，如果我们两两求LCA，肯定有两组相同，剩下那一组就是最优集合点了。为啥？画图理解一下吧……

代码：

/**************************************************************
    Problem: 1787
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4068 ms
    Memory:80900 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define TWO_POW(n) (1<<(n))
 
const int maxn=500001,maxm=1000001;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
int d[maxn];
int dep[maxn];
int anc[maxn][32];
void dfs(int x,int father,int depth,int dis){
    d[x]=dis;
    anc[x][0]=father;
    dep[x]=depth;
    int i;
    GRAPH_REP(i,x){
        if(to[i]!=father)
            dfs(to[i],x,depth+1,dis+dist[i]);
    }
}
 
int n;
inline void InitLCA(){
    register int i,j;
    for(j=1;TWO_POW(j)<n;j++){
        REP_B(i,n){
            if(anc[i][j-1]!=-1){
                anc[i][j]=anc[anc[i][j-1]][j-1];
            }
        }
    }
}
 
int QueryLCA(int x,int y){
    register int j,log;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;TWO_POW(log)<=dep[x];log++);
    log--;
    for(j=log;j>=0;j--)
        if(dep[x]-TWO_POW(j)>=dep[y])
            x=anc[x][j];
    if(x==y)
        return y;
    for(j=log;j>=0;j--){
        if(anc[x][j]!=-1 && anc[x][j]!=anc[y][j]){
            x=anc[x][j];
            y=anc[y][j];
        }
    }
    return anc[x][0];
}
inline int make_dis(int x,int y){
    return d[x]+d[y]-2*d[QueryLCA(x,y)];
}
 
int main(){
    int u,v,D;
    int x,y,z,QinDing;
    int m;
    register int i,j;
    scanf("%d%d",&n,&m);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        Add_Edge(u,v,1);
        Add_Edge(v,u,1);
    }
    memset(anc,-1,sizeof(anc));
    dfs(1,-1,0,0);
    InitLCA();
    REP(i,m){
        scanf("%d%d%d",&u,&v,&D);
        x=QueryLCA(u,v);
        y=QueryLCA(u,D);
        z=QueryLCA(v,D);
        if(x==y){
            QinDing=z;
        }else{
            if(x==z){
                QinDing=y;
            }else{
                QinDing=x;
            }
        }
        printf("%d %d\n",QinDing,make_dis(QinDing,u)+make_dis(QinDing,v)+make_dis(QinDing,D));
    }
    return 0;
}

终于A了！

做了4个月了，终于A了！

这个题其实不难。只要用树状数组维护主席树即可。不过请注意，此题的实际数据范围远比10000大！

代码：

/**************************************************************
    Problem: 1901
    User: danihao123
    Language: C++
    Result: Accepted
    Time:540 ms
    Memory:32712 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=120051;
const int maxlogn=31;
const int maxnode=maxn*20;
 
// ChairTree
int sumv[maxnode];
int lc[maxnode],rc[maxnode];
int ct_cnt=0;
int build_tree(int L,int R){
    int ans=++ct_cnt;
    if(R>L){
        int M=L+(R-L)/2;
        lc[ans]=build_tree(L,M);
        rc[ans]=build_tree(M+1,R);
    }
    return ans;
}
int p,v;
int update(int o,int L,int R){
    int ans=++ct_cnt;
    sumv[ans]=sumv[o];
    lc[ans]=lc[o];
    rc[ans]=rc[o];
    if(R>L){
        int M=L+(R-L)/2;
        if(p<=M)
            lc[ans]=update(lc[ans],L,M);
        else
            rc[ans]=update(rc[ans],M+1,R);
    }
    sumv[ans]+=v;
    return ans;
}
int LT_siz,RT_siz;
int LT[maxlogn],RT[maxlogn];
int query(int L,int R,int k){
    if(L==R)
        return L;
    int i;
    int LT_ans=0,RT_ans=0,the_ans,M=L+(R-L)/2;
    for(i=1;i<=LT_siz;i++)
        LT_ans+=sumv[lc[LT[i]]];
    for(i=1;i<=RT_siz;i++)
        RT_ans+=sumv[lc[RT[i]]];
    the_ans=RT_ans-LT_ans;
    if(k<=the_ans){
        for(i=1;i<=LT_siz;i++)
            LT[i]=lc[LT[i]];
        for(i=1;i<=RT_siz;i++)
            RT[i]=lc[RT[i]];
        return query(L,M,k);
    }else{
        for(i=1;i<=LT_siz;i++)
            LT[i]=rc[LT[i]];
        for(i=1;i<=RT_siz;i++)
            RT[i]=rc[RT[i]];
        return query(M+1,R,k-the_ans);
    }
}
 
int rt[maxn];
int siz;
inline int lowbit(int x){
    return x&(-x);
}
int n;
void change(int pos,int value,int delta){
    p=value;
    v=delta;
    while(pos<=n){
        rt[pos]=update(rt[pos],1,siz);
        pos+=lowbit(pos);
    }
}
int get_ans(int l,int r,int k){
    int temp=l-1;
    LT_siz=RT_siz=0;
    while(temp>0){
        LT[++LT_siz]=rt[temp];
        temp-=lowbit(temp);
    }
    while(r>0){
        RT[++RT_siz]=rt[r];
        r-=lowbit(r);
    }
    return query(1,siz,k);
}
int pre[maxn];
int A[maxn],A2[maxn];
int real_siz=0;
void init_CT(){
    register int i,pos;
    sort(A2+1,A2+1+real_siz);
    siz=unique(A2+1,A2+1+real_siz)-A2-1;
    rt[0]=build_tree(1,siz);
    for(i=1;i<=n;i++)
        rt[i]=rt[0];
    for(i=1;i<=n;i++){
        pos=lower_bound(A2+1,A2+1+siz,pre[i])-A2;
        change(i,pos,1);
    }
}
inline int get_lsh(int x){
    return lower_bound(A2+1,A2+1+siz,x)-A2;
}
 
int Query[maxn][4];
int main(){
    int m,u,v,d;
    char buf[3];
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&pre[i]);
        A2[++real_siz]=pre[i];
    }
    for(i=1;i<=m;i++){
        scanf("%s%d%d",buf,&u,&v);
        Query[i][1]=u;
        Query[i][2]=v;
        if(buf[0]=='C'){
            Query[i][0]=1;
            A2[++real_siz]=v;
        }else{
            Query[i][0]=0;
            scanf("%d",&Query[i][3]);
        }
    }
    init_CT();
    for(i=1;i<=m;i++){
        if(Query[i][0]){
            change(Query[i][1],get_lsh(pre[Query[i][1]]),-1);
            pre[Query[i][1]]=Query[i][2];
            change(Query[i][1],get_lsh(Query[i][2]),1);
        }else{
            printf("%d\n",A2[get_ans(Query[i][1],Query[i][2],Query[i][3])]);
        }
    }
    return 0;
}

废了。

我彻底废了。

就一个贪心水体。按截止时间排序然后遍历，当前花时间能干完就干，不能的话看能不能把更劣的选择换。仅此而已。

代码：

/**************************************************************
    Problem: 1029
    User: danihao123
    Language: C++
    Result: Accepted
    Time:396 ms
    Memory:2764 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
const int maxn=150001;
struct Node{
    int a,b;
    bool operator <(const Node& x) const{
        return b<x.b;
    }
    bool operator >(const Node& x) const{
        return b>x.b;
    }
};
Node T[maxn];
priority_queue<ll> Q;
int main(){
    int n;
    register int i,ans=0;
    register ll cur=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&T[i].a,&T[i].b);
    sort(T+1,T+1+n);
    for(i=1;i<=n;i++){
        if(cur+T[i].a<=T[i].b){
            cur+=T[i].a;
            Q.push(T[i].a);
        }else{
            if(Q.size() && Q.top()>T[i].a){
                cur-=Q.top();
                Q.pop();
                cur+=T[i].a;
                Q.push(T[i].a);
            }
        }
    }
    printf("%d\n",Q.size());
    return 0;
}

这题其实就是一个田忌赛马类问题。贪心即可。

如果你不知道田忌赛马怎么贪，可以看《骗分导论》相关介绍（然而那个贪心不是骗分算法哦）。

代码：

/**************************************************************
    Problem: 1034
    User: danihao123
    Language: C++
    Result: Accepted
    Time:256 ms
    Memory:1604 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=100001;
int a[maxn],b[maxn];
int n;
inline int solve(int *A,int *B){
    register int L1=1,R1=n,L2=1,R2=n,ans=0;
    while(L1<=R1 && L2<=R2){
        if(A[L1]>B[L2]){
            ans+=2;
            L1++;
            L2++;
        }else{
            if(A[R1]>B[R2]){
                ans+=2;
                R1--;
                R2--;
            }else{
                if(A[L1]==B[R2])
                    ans++;
                L1++;
                R2--;
            }
        }
    }
    return ans;
}
int main(){
    register int i,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    printf("%d %d\n",solve(a,b),2*n-solve(b,a));
    return 0;
}

又是一道分层图最短路水题……

我估计会卡SPFA（或许可能不卡？），所以再次写了pb_ds优化Dijkstra。

代码：

/**************************************************************
    Problem: 2662
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:868 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=51,maxk=51,maxm=2005;
int cnt=0;
int first[maxn];
int to[maxm],next[maxm];
int dist[maxm];
inline void Add_Edge(int x,int y,int z){
    cnt++;
    next[cnt]=first[x];
    first[x]=cnt;
    to[cnt]=y;
    dist[cnt]=z;
}
 
int d[maxn][maxk];
bitset<maxn> vis[maxk];
struct Node{
    int x,k,d;
    bool operator <(const Node& itt) const{
        return d<itt.d;
    }
    bool operator >(const Node& itt) const{
        return d>itt.d;
    }
};
typedef __gnu_pbds::priority_queue<Node,greater<Node> > Heap;
Heap::point_iterator ite[maxn][maxk];
Heap Q;
int n,k;
inline void relax(int x,int y,int p){
    d[x][y]=p;
    if(ite[x][y]!=0)
        Q.modify(ite[x][y],(Node){x,y,p});
    else
        ite[x][y]=Q.push((Node){x,y,p});
}
int dij(){
    register int i,u,v,ans=0x7f7f7f7f;
    memset(d,0x7f,sizeof(d));
    d[1][0]=0;
    ite[1][0]=Q.push((Node){1,0,0});
    while(!Q.empty()){
        u=Q.top().x;
        v=Q.top().k;
        Q.pop();
        if(vis[u][v])
            continue;
        vis[u][v]=true;
        for(i=first[u];i;i=next[i]){
            if(v<k){
                if(d[to[i]][v+1]>(d[u][v]+dist[i]/2)){
                    relax(to[i],v+1,d[u][v]+dist[i]/2);
                }
            }
            if(d[to[i]][v]>d[u][v]+dist[i]){
                relax(to[i],v,d[u][v]+dist[i]);
            }
        }
    }
    for(i=0;i<=k;i++)
        ans=min(ans,d[n][i]);
    return ans;
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
    int m;
    register int i,u,v,d;
    n=readint();
    m=readint();
    k=readint();
    for(i=1;i<=m;i++){
        u=readint();
        v=readint();
        d=readint();
        Add_Edge(u,v,d);
        Add_Edge(v,u,d);
    }
    writeint(dij());
    putchar('\n');
    return 0;
}

分层图最短路处女作TAT

很明显要求你求一个分层图上的最短路。不过没必要把分层图构出来，手写转移即可。还有卡SPFA是怎么回事？出题人你粗来我保证不打死你……

然而沉迷pb_ds，不能自拔。

代码：

/**************************************************************
    Problem: 2763
    User: danihao123
    Language: C++
    Result: Accepted
    Time:268 ms
    Memory:3136 kb
****************************************************************/
 
#include <cstdio>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>
#include <cctype>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn=10001,maxm=100001,maxk=11;
typedef pair<int,int> pii;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
struct Node{
    pii pnt;
    int d;
    bool operator <(const Node& x) const{
        return d<x.d;
    }
    bool operator >(const Node& x) const{
        return d>x.d;
    }
};
 
typedef __gnu_pbds::priority_queue<Node,greater<Node> > Heap;
Heap::point_iterator ite[maxn][maxk];
Heap Q;
int n,k;
bool vis[maxn][maxk];
int d[maxn][maxk];
inline void relax(int u,int v,int di){
    d[u][v]=di;
    if(ite[u][v]!=0)
        Q.modify(ite[u][v],(Node){make_pair(u,v),di});
    else
        ite[u][v]=Q.push((Node){make_pair(u,v),di});
}
int Dijkstra(int s,int t){
    register int i,u,v;
    pii temp;
    memset(d,0x7f,sizeof(d));
    d[s][0]=0;
    ite[s][0]=Q.push((Node){make_pair(s,0),0});
    while(!Q.empty()){
        temp=Q.top().pnt;
        Q.pop();
        u=temp.first;
        v=temp.second;
        if(vis[u][v])
            continue;
        vis[u][v]=true;
        for(i=first[u];i;i=next[i]){
            if(v<k){
                if(d[u][v]<d[to[i]][v+1]){
                    relax(to[i],v+1,d[u][v]);
                }
            }
            if(d[u][v]+dist[i]<d[to[i]][v]){
                relax(to[i],v,d[u][v]+dist[i]);
            }
        }
    }
    register int ans=0x7f7f7f7f;
    for(i=0;i<=k;i++)
        ans=min(ans,d[t][i]);
    return ans;
}
int main(){
    int m,s,t,u,v,d;
    register int i;
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&d);
        Add_Edge(u,v,d);
        Add_Edge(v,u,d);
    }
    printf("%d\n",Dijkstra(s,t));
    return 0;
}

扫描线处女作TAT

直接离线，按左端点排序扫描。每个点要保存后继相同节点，每种元素第一次出现的位置都加1。然后扫描的时候有后继就给后继加。之后求区间和即可。

代码：

/**************************************************************
    Problem: 1878
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1344 ms
    Memory:8444 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=50001,maxm=200001;
int T[maxn];
int n;
inline int lowbit(int x){
    return x&(-x);
}
inline void update(int p,int v){
    while(p<=n){
        T[p]+=v;
        p+=lowbit(p);
    }
}
inline int query(int p){
    register int ans=0;
    while(p>0){
        ans+=T[p];
        p-=lowbit(p);
    }
    return ans;
}
 
struct Query{
    int l,r;
    int id;
    int ans;
    bool operator <(const Query& x) const{
        return l==x.l?r<x.r:l<x.l;
    }
};
Query Q[maxm];
bool cmp2(const Query& a,const Query& b){
    return a.id<b.id;
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
 
int next[maxn];
int A[maxn];
int pos[1000001];
int main(){
    int m,maxA=0;
    register int i,j;
    n=readint();
    for(i=1;i<=n;i++){
        A[i]=readint();
        maxA=max(maxA,A[i]);
    }
    for(i=n;i;i--){
        next[i]=pos[A[i]];
        pos[A[i]]=i;
    }
    for(i=1;i<=maxA;i++)
        if(pos[i])
            update(pos[i],1);
    m=readint();
    for(i=1;i<=m;i++){
        Q[i].l=readint();
        Q[i].r=readint();
        Q[i].id=i;
    }
    sort(Q+1,Q+1+m);
    register int tot=1;
    for(i=1;i<=m;i++){
        while(tot<Q[i].l){
            if(next[tot])
                update(next[tot],1);
            tot++;
        }
        Q[i].ans=query(Q[i].r)-query(Q[i].l-1);
    }
    sort(Q+1,Q+1+m,cmp2);
    for(i=1;i<=m;i++){
        writeint(Q[i].ans);
        putchar('\n');
    }
    return 0;
}

这个问题看似无从下手。

我们可以先取[tex]n=2[/tex]，然后你就发现你似乎要解[tex]A_{1}X_{1}+A_{2}X_{2}>0[/tex]，而且还要求[tex]S[/tex]最小？你想到了什么？扩展欧几里得？对头！

由扩欧推广可得答案就是所有数的最大公约数。

代码：

/**************************************************************
    Problem: 1441
    User: danihao123
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    register int ans,i;
    int n,temp;
    scanf("%d",&n);
    scanf("%d",&temp);
    ans=abs(temp);
    for(i=2;i<=n;i++){
        scanf("%d",&temp);
        ans=gcd(ans,abs(temp));
    }
    printf("%d\n",ans);
    return 0;
}

这两个题是一样的啊……

让路径上最大值最小当然要玩瓶颈路，瓶颈路需要MST，然后Kruskal求MST时最小边不是不可控的！也就是说我们可以控制最小边，从而求出符合要求的生成树，然后凿出瓶颈路。

所以我们可以直接枚举最小边，然后Kruskal求生成树，之后求瓶颈路。至于是否有解，第一遍Kruskal（第一遍求的其实是MST）之后看看是否联通即可。

不过这个题求瓶颈路个人建议用BFS而不是DFS，且不谈BFS效率高还不易炸堆栈段（尽管这个题没有炸堆栈段的隐患），DFS本身细节就很多，容易错。

代码：

/**************************************************************
    Problem: 1050
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3588 ms
    Memory:1172 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <bitset>
#include <vector>
#include <queue>
using namespace std;
const int maxn=501,maxm=10001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REPB(i,n) for(i=1;i<=(n);i++)
#define CUS_REP(i,u,v) for(i=(u);i<(v);i++)
#define REP_G(i,u) for(i=first[u];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))
typedef pair<int,int> pii;
int n;
int S,T;
 
// Graph
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int G_cnt=0;
inline void Add_Edge(int u,int v,int d){
    G_cnt++;
    next[G_cnt]=first[u];
    first[u]=G_cnt;
    to[G_cnt]=v;
    dist[G_cnt]=d;
}
inline void Clear_Graph(){
    CL_ARR(first,0);
    CL_ARR(next,0);
    CL_ARR(to,0);
    CL_ARR(dist,0);
    G_cnt=0;
}
 
// BFS
bitset<maxn> vis;
struct Node{
    int x,maxv,minv;
};
pii BFS(){
    register int a,b,i;
    queue<Node> Q;
    Node tt;
    Q.push((Node){S,-1,0x7fffffff});
    vis[S]=true;
    while(!Q.empty()){
        tt=Q.front();
        Q.pop();
        if(tt.x==T)
            return make_pair(tt.maxv,tt.minv);
        REP_G(i,tt.x){
            if(!vis[to[i]]){
                vis[to[i]]=true;
                Q.push((Node){to[i],max(tt.maxv,dist[i]),min(tt.minv,dist[i])});
            }
        }
    }
}
 
// BINGCHA Set
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    CL_ARR(rank,0);
}
 
// MST
struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
vector<Edge> E;
bool OK=false;
pii ans;
void MST(int x){
    register int i,a,b,cnt=0;
    pii que;
    register double jia,yi;
    Clear_Graph();
    init_set();
    CUS_REP(i,x,E.size()){
        if(!is_same(E[i].u,E[i].v)){
            Add_Edge(E[i].u,E[i].v,E[i].d);
            Add_Edge(E[i].v,E[i].u,E[i].d);
            cnt++;
            union_set(E[i].u,E[i].v);
            if(cnt==n-1)
                break;
        }
    }
    if(is_same(S,T)){
        OK=true;
    }else{
        return;
    }
    vis.reset();
    que=BFS();
    a=que.first;
    b=que.second;
    jia=((double)a)/((double)b);
    yi=(double(ans.first))/(double(ans.second));
    if(jia<yi){
        ans.first=a;
        ans.second=b;
    }
}
 
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main(){
    int m;
    register int i,u,v,d;
    n=readint();
    m=readint();
    REP(i,m){
        u=readint();
        v=readint();
        d=readint();
        E.push_back((Edge){u,v,d});
    }
    S=readint();
    T=readint();
    sort(E.begin(),E.end());
    ans.first=0x7fffffff;
    ans.second=1;
    REP(i,m){
        MST(i);
        if(!OK){
            if(!i){
                puts("IMPOSSIBLE");
                return 0;
            }else{
                break;
            }
        }
    }
    d=gcd(ans.first,ans.second);
    ans.first/=d;
    ans.second/=d;
    if(ans.second==1)
        printf("%d\n",ans.first);
    else
        printf("%d/%d\n",ans.first,ans.second);
    return 0;
}

单调队列水体……然而我这蒟蒻仍然WA一墙

这个题本质是一个动态规划，然后我们发现取区间递推最小值这个任务可以交给单调队列君来做~不过优先级似乎是一个问题……

优先级直接按照递推值来搞即可，递推值一样的话才按照高度比。因为就算递推值比较小但高度会带来额外影响，也不过是1，这样撑死也不会使答案更差

但凡是单调队列的题，都会有神秘细节，这题也不例外……顺便说一下这题不要傻乎乎的用pair

代码：

/**************************************************************
    Problem: 3831
    User: danihao123
    Language: C++
    Result: Accepted
    Time:11596 ms
    Memory:16228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=1e6+1;
int D[maxn],f[maxn];
bool d_cmp(int x,int y){
    if(f[x]==f[y])
        return D[x]<D[y];
    else
        return f[x]>f[y];
}
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && d_cmp(D.back(),x))
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
DQueue hhh;
int main(){
    register int i,temp,ans;
    int n,Q,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&D[i]);
    scanf("%d",&Q);
    while(Q--){
        scanf("%d",&k);
        hhh.push(1);
        f[1]=0;
        for(i=2;i<=n;i++){
            while(hhh.size()>k)
                hhh.pop();
            temp=hhh.top();
            f[i]=f[temp]+(D[temp]<=D[i]);
            hhh.push(i);
        }
        printf("%d\n",f[n]);
        hhh.clear();
    }
    return 0;
}