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

[CF 705C]Thor

这题我考试的时候想出各种蜜汁数据结构。

但是正解是:暴力!

好了好了,暴力也是要优化的。首先给消息编号,然后用一个bitset记下来哪个删了哪个没删,这个都能想到。

不过接下来有个挺头疼的问题:操作3阅读的信息可能在操作2中会被再次阅读,如此一来效率就很低了……咋整?

注意大消息队列里的消息编号肯定是升序的,每个程序的消息队列的编号也是升序的,所以说大队列中同一程序的消息的编号和该程序自身队列中的消息编号的顺序是一致的。如此一来,在操作3中可以顺便把程序队列中的消息也删掉,效率大为提升。

代码:

#include <cstdio>
#include <queue>
#include <utility>
#include <cctype>
#include <bitset>
using namespace std;
const int maxn=300001;
typedef pair<int,int> pii;
bitset<maxn> vis;
queue<int> S[maxn];
queue<pii> Q;
// 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(){
	register int ans=0,cnt=0;
	register int temp,temp_2,q,u,v;
	int n;
	n=readint();
	q=readint();
	while(q--){
		u=readint();
		v=readint();
		if(u==1){
			cnt++;
			S[v].push(cnt);
			Q.push(make_pair(v,cnt));
			ans++;
		}else{
			if(u==2){
				while(!S[v].empty()){
					temp=S[v].front();
					S[v].pop();
					if(!vis[temp]){
						vis[temp]=true;
						ans--;
					}
				}
			}else{
				while(!Q.empty() && (temp=Q.front().second)<=v){
					temp=Q.front().second;
					temp_2=Q.front().first;
					Q.pop();
					if(!vis[temp]){
						vis[temp]=true;
						S[temp_2].pop();
						ans--;
					}
				}
			}
		}
		writeint(ans);
		putchar('\n');
	}
	return 0;
}

[BZOJ 1715]虫洞

呜……这题现在才A

这道题就是给一个图让判断有没有负环,没什么难度

然后……我写邻接表竟然开小内存了……

尽管如此我感觉我写此题时的代码风格还是不错的,比较值得学习

代码:

/**************************************************************
    Problem: 1715
    User: danihao123
    Language: C++
    Result: Accepted
    Time:92 ms
    Memory:920 kb
****************************************************************/
 
#include <cstdio>
#include <queue>
#include <cstring>
#include <cctype>
using namespace std;
const int maxn=501,maxm=5201;
namespace Graph{
    int n;
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void AddEdge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    inline void ClearGraph(){
        memset(first,0,sizeof(first));
        memset(next,0,sizeof(next));
        memset(to,0,sizeof(to));
        memset(dist,0,sizeof(dist));
        tot=0;
    }
    int cnt[maxn];
    bool inQueue[maxn];
    int d[maxn];
    bool SPFA(){
        register int i,u;
        queue<int> Q;
        memset(cnt,0,sizeof(cnt));
        memset(inQueue,0,sizeof(inQueue));
        for(i=1;i<=n;i++){
            d[i]=0;
            cnt[i]=1;
            inQueue[i]=true;
            Q.push(i);
        }
          
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            for(i=first[u];i;i=next[i]){
                if(d[to[i]]>d[u]+dist[i]){
                    d[to[i]]=d[u]+dist[i];
                    if(!inQueue[to[i]]){
                        Q.push(to[i]);
                        inQueue[to[i]]=true;
                        if(++cnt[to[i]]>n)
                            return true;
                    }
                }
            }
        }
        return false;
    }
};
inline int readint(){
    register char c;
    register int temp=0;
    c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        temp=temp*10+c-'0';
        c=getchar();
    }
    return temp;
}
int main(){
    register int i,m,w,u,v,d;
    int F;
    F=readint();
    while(F--){
        Graph::n=readint();
        m=readint();
        w=readint();
        Graph::ClearGraph();
        for(i=1;i<=m;i++){
            u=readint();
            v=readint();
            d=readint();
            Graph::AddEdge(u,v,d);
            Graph::AddEdge(v,u,d);
        }
        for(i=1;i<=w;i++){
            u=readint();
            v=readint();
            d=readint();
            Graph::AddEdge(u,v,-d);
        }
        if(Graph::SPFA())
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

[CodeVS 1012]最大公约数和最小公倍数问题

很经典的问题了吧……然而现在才A……

应注意[tex]P*Q=x*y[/tex],然而[tex]P[/tex]和[tex]Q[/tex]都可表示为[tex]x[/tex]的乘积,问题就好思考多了。答案就是[tex]y/x[/tex]的质因子的子集数(同一种质因子不能同时分配到P与Q中,否则gcd(P,Q)会不等于x)。

注意有可能无解!

代码:

#include <iostream>
using namespace std;
inline int fj(int x){
	register int i,ans=0;
	for(i=2;i<=x && x>1;i++)
		if(!(x%i)){
			ans++;
			while(!(x%i))
				x/=i;
		}
	return ans;
}
int main(){
	int a,b;
	register int ans;
	cin>>a>>b;
	if(b%a)
		ans=0;
	else
		ans=a==1?1:1<<fj(b/a);
	cout<<ans<<endl;
	return 0;
}

[BZOJ 3725]Matryca

很有意思的思考题。

这道题通过特殊情况我们可以猜想,假设最近两个不同色块距离为[tex]x[/tex](这是半闭半开序列长度),则答案为[tex]n-x+1[/tex]。然而事实就是如此。

代码:

/**************************************************************
    Problem: 3725
    User: danihao123
    Language: C++
    Result: Accepted
    Time:216 ms
    Memory:1796 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000001;
char buf[maxn];
int main(){
    int n;
    register int i,now;
    char last_s=0;
    scanf("%s",buf);
    n=strlen(buf);
    register int ans=n;
    for(i=0;i<n;i++){
        if(buf[i]!='*'){
            if(last_s){
                if(buf[i]!=last_s){
                    ans=min(ans,i-now);
                    last_s=buf[i];
                    now=i;
                }else{
                    now=i;
                }
            }else{
                last_s=buf[i];
                now=i;
            }
        }
    }
    printf("%d\n",n-ans+1);
    return 0;
}

[BZOJ 4325]斗地主

是的你没有看错!就是这道坑提!

这题基本是个半成品,歧义真的,真的,真的很大。

至于方法?我们注意到同样的牌能一起出就尽可能避免拆开。例如,四带二分成炸弹加两单点(对子)肯定不好。三带一或者三带二也如此。先考虑不出顺子的最优解,并据此进行深度限制,再考虑出顺子。

然后,DFS暴搜即可。

顺便讲一下坑点:

  1. 顺子可以有A。
  2. 三带一,三带二,四代二都可以有头。但是大小头要区别开。

代码:

/**************************************************************
    Problem: 4325
    User: danihao123
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int ans;
int cnt[5],hand[15];
void dfs(int x){
    if(x>ans)
        return;
    int i,j,rest=0;
    memset(cnt,0,sizeof(cnt));
    for(i=0;i<=14;i++){
        cnt[hand[i]]++;
    }
    while(cnt[4]>0){
        cnt[4]--;
        rest++;
        if(cnt[2]>=2)
            cnt[2]-=2;
        else
            if(cnt[1]>=2)
                cnt[1]-=2;
    }
    while(cnt[3]>0){
        cnt[3]--;
        rest++;
        if(cnt[2]>0)
            cnt[2]--;
        else
            if(cnt[1]>0)
                cnt[1]--;
    }
    if(hand[0] && hand[1] && cnt[1]>=2)
        rest--;
    ans=min(ans,cnt[1]+cnt[2]+rest+x);
    for(i=3;i<=10;i++){
        for(j=i;j<=14 && hand[j];j++){
            hand[j]--;
            if(j-i+1>=5)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]++;
    }
    for(i=3;i<=12;i++){
        for(j=i;j<=14 && hand[j]>=2;j++){
            hand[j]-=2;
            if(j-i+1>=3)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=2;
    }
    for(i=3;i<=13;i++){
        for(j=i;j<=14 && hand[j]>=3;j++){
            hand[j]-=3;
            if(j-i+1>=2)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=3;
    }
}
int main(){
    int T,u,v;
    register int i;
    scanf("%d%d",&T,&n);
    while(T--){
        ans=n;
        memset(hand,0,sizeof(hand));
        for(i=1;i<=n;i++){
            scanf("%d%d",&u,&v);
            if(!u){
                if(v==2)
                    hand[1]++;
                else
                    hand[0]++;
            }else{
                if(u==1)
                    hand[14]++;
                else
                    hand[u]++;
            }
        }
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

[CF 676B]Pyramid of Glasses

这题可以直接模拟,貌似也可过。但复杂度很高。

我们可以直接把t个单位的酒放入第一个杯,然后向下溢出,以此类推,这样复杂度就很优秀了。

代码:

#include <iostream>
using namespace std;
const int maxn=12;
int n;
long double k[maxn][maxn];
int call(int x){
	int i,ans=0;
	long double temp;
	if(x>n)
		return 0;
	for(i=1;i<=n;i++){
		if(k[x][i]>=1.0){
			ans++;
			if(k[x][i]>1.0 && x<n){
				temp=(k[x][i]-1.0)/2;
				k[x][i]=1.0;
				k[x+1][i]+=temp;
				k[x+1][i+1]+=temp;
			}
		}
	}
	return ans+call(x+1);
}
int main(){
	cin>>n>>k[1][1];
	cout<<call(1)<<endl;
	return 0;
}

[BZOJ 4152]The Captain

这题初看有些棘手。但是毕竟是最短路,[tex]min(abs(x_{1}-x_{2}),abs(y_{1}-y_{2}))[/tex]这样的边,大可以分成两条边来建,于是乎min就形同虚设了。并且我们可以看到这样建图有一个好处:跨越若干点的方案可以一定可以分成图上的若干边。问题大为简化,迎刃而解。

但这提有个丧病的地方:卡SPFA。加了一些优化照样挂。所以我一气之下写了可并堆优化的Dijkstra :)当然可并堆用的是pb_ds辣。

代码:

/**************************************************************
    Problem: 4152
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4888 ms
    Memory:17412 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <cctype>
#include <bitset>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
const int maxn=200001;
int n;
inline int abs(int x){
    return x<0?-x:x;
}
  
int first[maxn];
int next[maxn*4],to[maxn*4],dist[maxn*4];
int graph_cnt=0;
inline void Add_Edge(int x,int y,int d){
    graph_cnt++;
    next[graph_cnt]=first[x];
    first[x]=graph_cnt;
    to[graph_cnt]=y;
    dist[graph_cnt]=d;
}
  
int d[maxn];
bitset<maxn> vis;
typedef pair<int,int> my_pair;
typedef __gnu_pbds::priority_queue<my_pair,greater<my_pair> > Heap;
Heap::point_iterator ite[maxn];
Heap Q;
int 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]));
            }
        }
    }
    return d[n];
}
  
int pr[maxn][2];
int order1[maxn],order2[maxn];
int cmp1(const int i,const int j){
    return pr[i][0]<pr[j][0];
}
int cmp2(const int i,const int j){
    return pr[i][1]<pr[j][1];
}
// 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(){
    register int i;
    n=readint();
    for(i=1;i<=n;i++){
        pr[i][0]=readint();
        pr[i][1]=readint();
        order1[i]=i;
        order2[i]=i;
    }
    sort(order1+1,order1+1+n,cmp1);
    sort(order2+1,order2+1+n,cmp2);
    for(i=1;i<=n;i++){
        if(i!=1){
            Add_Edge(order1[i],order1[i-1],pr[order1[i]][0]-pr[order1[i-1]][0]);
            Add_Edge(order2[i],order2[i-1],pr[order2[i]][1]-pr[order2[i-1]][1]);
        }
        if(i!=n){
            Add_Edge(order1[i],order1[i+1],pr[order1[i+1]][0]-pr[order1[i]][0]);
            Add_Edge(order2[i],order2[i+1],pr[order2[i+1]][1]-pr[order2[i]][1]);
        }
    }
    printf("%d\n",dij());
    return 0;
}

[BZOJ 1756]小白逛公园

这题是很经典的线段树题。

我们可以发现最长子序列或跨越中点,或不跨越中点。若不跨越则肯定在左子或右子中,跨越则是左子最大后缀和和右子最大前缀和之和。问题便迎刃而解。(当然,求区间最大前缀/后缀和要用上区间和)

需注意此题可能会出现a>b!

代码:

/**************************************************************
    Problem: 1756
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2604 ms
    Memory:49648 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500001;
struct Node{
    int L,R;
    int maxP,maxS,ans,sum;
};
Node Tree[maxn*4];
int A[maxn];
void merge(Node& O,Node& LC,Node& RC){
    O.sum=LC.sum+RC.sum;
    O.maxP=max(LC.maxP,LC.sum+RC.maxP);
    O.maxS=max(RC.maxS,RC.sum+LC.maxS);
    O.ans=max(max(LC.ans,RC.ans),LC.maxS+RC.maxP);
}
void maintain(int o){
    Node& O=Tree[o],LC=Tree[o<<1],RC=Tree[o<<1|1];
    merge(O,LC,RC);
}
void build_tree(int o,int L,int R){
    Node& O=Tree[o];
    O.L=L;
    O.R=R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=A[L];
    }else{
        int M=L+(R-L)/2;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
        maintain(o);
    }
}
void update(int o,int p,int v){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=v;
    }else{
        int M=L+(R-L)/2;
        if(p<=M)
            update(o<<1,p,v);
        else
            update(o<<1|1,p,v);
        maintain(o);
    }
}
int ql,qr;
Node query(int o){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(ql<=L && R<=qr){
        return Tree[o];
    }
    int M=L+(R-L)/2;
    Node ANS,LC,RC;
    if(ql<=M){
        LC=query(o<<1);
        if(qr>M){
            RC=query(o<<1|1);
            merge(ANS,LC,RC);
            return ANS;
        }else{
            return LC;
        }
    }else{
        RC=query(o<<1|1);
        return RC;
    }
}
int main(){
    int n,m;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&A[i]);
    build_tree(1,1,n);
    int k,a,b;
    Node ans;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&k,&a,&b);
        if(k&1){
            if(a>b)
                swap(a,b);
            ql=a;
            qr=b;
            ans=query(1);
            printf("%d\n",ans.ans);
        }else{
            update(1,a,b);
        }
    }
    return 0;
}