[BZOJ 1029]建筑抢修

废了。

我彻底废了。

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

代码:

/**************************************************************
    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;
}

[BZOJ 1034]泡泡堂

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

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

代码:

/**************************************************************
    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;
}

[BZOJ 2662]冻结

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

我估计会卡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;
}

[BZOJ 1022]小约翰的游戏

这个题是比较特殊的游戏。因为扩展出最后一个状态的人会输。这种游戏称为Anti-SG游戏。

解决这种题,需要SJ定理:先手必胜当且仅当游戏的SG函数为0而存在一个单一游戏的SG函数大于1,或整个游戏的SG函数不为0且没有任何单一游戏的SG函数大于1。问题迎刃而解。

代码:

/**************************************************************
    Problem: 1022
    User: danihao123
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    register int i,last;
    int n,temp,T;
    bool obey_1;
    scanf("%d",&T);
    while(T--){
        obey_1=false;
        last=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",&temp);
            if(temp>1){
                obey_1=true;
            }
            last=last^temp;
        }
        if((last!=0 && obey_1) || (last==0 && !obey_1)){
            puts("John");
        }else{
            puts("Brother");
        }
    }
    return 0;
}

[BZOJ 2763]飞行路线

分层图最短路处女作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;
}

[BZOJ 1878]HH的项链

扫描线处女作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;
}

[BZOJ 1441]Min

这个问题看似无从下手。

我们可以先取[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;
}

[BZOJ 3040]最短路

窝现在感觉卡SPFA真正常……

卡Dijkstra+普通堆优化感觉很……算了搞一发紧张的可并堆优化。啥你不会写?有pb_ds咋不用呢?

顺便说一下,伪随机数生成(前T条边会用到)一定要开long long!一定要开long long!一定要开long long!重要的事说三遍!

代码:

/**************************************************************
    Problem: 3040
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2816 ms
    Memory:181272 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=1000001,maxm=10000001;
int cnt=0;
int first[maxn];
int to[maxm],next[maxm];
long long dist[maxm];
void Add_Edge(int x,int y,long long z){
    cnt++;
    next[cnt]=first[x];
    first[x]=cnt;
    to[cnt]=y;
    dist[cnt]=z;
}
 
long long d[maxn];
bitset<maxn> vis;
typedef pair<long long,int> my_pair;
typedef __gnu_pbds::priority_queue<my_pair,greater<my_pair> > Heap;
Heap::point_iterator ite[maxn];
Heap Q;
void dij(){
    register int i,u;
    memset(d,0x7f,sizeof(d));
    d[1]=0;
    ite[1]=Q.push(make_pair(0,1));
    while(!Q.empty()){
        u=Q.top().second;
        Q.pop();
        if(vis[u])
            continue;
        vis[u]=true;
        for(i=first[u];i;i=next[i]){
            if(d[to[i]]>(dist[i]+d[u])){
                d[to[i]]=dist[i]+d[u];
                if(ite[to[i]]!=0)
                    Q.modify(ite[to[i]],make_pair(d[to[i]],to[i]));
                else
                    ite[to[i]]=Q.push(make_pair(d[to[i]],to[i]));
            }
        }
    }
}
 
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 n,m,T,rxa,rxc,rya,ryc,rp;
    register int i,j;
    register long long x=0,y=0,z=0,a,b;
    n=readint();
    m=readint();
    T=readint();
    rxa=readint();
    rxc=readint();
    rya=readint();
    ryc=readint();
    rp=readint();
    for(j=0;j<T;j++){
        x=(x*rxa+rxc)%rp;
        y=(y*rya+ryc)%rp;
        a=min(x%n+1,y%n+1);
        b=max(y%n+1,y%n+1);
    }
    for(i=0;i<(m-T);i++){
        x=readint();
        y=readint();
        z=readint();
        Add_Edge(x,y,z);
    }
    dij();
    printf("%lld\n",d[n]);
    return 0;
}

[BZOJ 1050]旅行/[CodeVS 1001]舒适的路线

这两个题是一样的啊……

让路径上最大值最小当然要玩瓶颈路,瓶颈路需要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;
}

[BZOJ 3831]Little Bird

单调队列水体……然而我这蒟蒻仍然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;
}