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

[POJ 2388]Who's in the Middle

这题题面长得挺吓人的(英文……),不过就是让你求中位数……

我怀疑会有卡快排的数据,不过我用的是STL的sort(sort好像用的不是普通的快排)

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=10000;
int A[maxn];
int main(){
	register int i;
	int n;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&A[i]);
	sort(A,A+n);
	printf("%d\n",A[n>>1]);
	return 0;
}

[CF 371B]Fox Dividing Cheese

狐狸的三种操作的实质是除二,除三,除五。由此我们可以猜想在最优策略下,两块蛋糕最后的重量应该是[tex]gcd(a,b)[/tex]。然后试除即可。

(大胆猜想,不用证明

代码:

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
	if(!b)
		return a;
	else
		return gcd(b,a%b);
}
static int P[3]={2,3,5};
inline int min_fj(int source,int direction){
	register int i,ans=0;
	source/=direction;
	if(source==1)
		return 0;
	for(i=2;i>=0;i--){
		while(source%P[i]==0){
			source/=P[i];
			ans++;
		}
	}
	if(source==1)
		return ans;
	else
		return -1;
}
int main(){
	register int direction,t1,t2;
	int a,b;
	cin>>a>>b;
	if(a==b){
		cout<<0<<endl;
		return 0;
	}
	direction=gcd(a,b);
	t1=min_fj(a,direction);
	if(t1==-1){
		cout<<-1<<endl;
		return 0;
	}
	t2=min_fj(b,direction);
	if(t2==-1){
		cout<<-1<<endl;
		return 0;
	}
	cout<<t1+t2<<endl;
	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;
}

[CodeVS 3269]混合背包

哎……现在才敢说真正会背包DP……

这个题可以分成三类问题分别处理,然后用一个一维数组一起递推。

0-1背包和完全背包都很简单。多重背包直接递推的话复杂度很高,可以考虑单调队列优化……然而窝太弱……不过还是用了

代码:

#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=201,maxv=200001;
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && x>D.back())
            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();
    }
};
int d[maxv];
int v;
void pack(int V,int W,int c){
	register int i,j,m;
	if(c==1){
		for(i=v;i>=V;i--)
			d[i]=max(d[i],d[i-V]+W);
	}else{
		if(c==-1){
			for(i=V;i<=v;i++)
				d[i]=max(d[i],d[i-V]+W);
		}else{
			c=min(c,v/V);
			for(i=0;i<V;i++){
				m=(v-i)/V;
				DQueue Q;
				for(j=0;j<=m;j++){
					if(Q.size()==c+1)
						Q.pop();
					Q.push(d[j*V+i]-j*W);
					d[j*V+i]=Q.top()+j*W;
				}
			}
		}
	}
}
int main(){
	register int i;
	int n,x,y,z;
	scanf("%d%d",&n,&v);
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		pack(x,y,z);
	}
	printf("%d\n",d[v]);
	return 0;
}

[CodeVS 1044]拦截导弹

第一问很显然是最长不升子序列,直接DP即可。

第二问咋整?暴力?网络流?

其实就是最长不降子序列。具体证明嘛……自己找吧。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=22;
int d[maxn],f[maxn];
int A[maxn];
int main(){
    int n;
    register int i,j,ans=0;
    for(n=1;;n++)
        if(scanf("%d",&A[n])!=1)
            break;
    n--;
    for(i=1;i<=n;i++){
        d[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]>=A[i])
                d[i]=max(d[i],d[j]+1);
        ans=max(ans,d[i]);
    }
    printf("%d\n",ans);
    ans=0;
    for(i=1;i<=n;i++){
        f[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]<=A[i])
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    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;
}

[洛谷 P2679]子串

DP神题……

第一眼都能看出来是DP,然后大约构思就出来了,但细节很复杂啊……

看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态,但是注意[tex]A[i]=B[j][/tex](字符数组细节此处未予考虑)的情况和整体情况要独立对待,否则这题只能233

然后下面就不难想了。但是注意直接开数组会233,要开滚动数组防MLE。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
    register int i,j,p,now,pre;
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",A,B);
    d[0][0][0][1]=1;
    for(i=1;i<=n;i++){
        now=i%2;
        pre=1-now;
        d[now][0][0][1]=1;
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1])
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
                    d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
                }
            else
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=0;
                    d[now][j][p][1]=d[pre][j][p][1];
                }
        }
    }
    printf("%d\n",d[n%2][m][k][1]);
    return 0;
}