P6510 奶牛排队

给定一组数据,从,找到两个一组连续的数,最左边的数是最小的,最右边的数是最大的.

我们调用单调栈的模版,首先求出A右侧第一个的位置,再求出B左侧第一个的位置.A右侧第一个小于A的数在B的右边,B左侧第一个大于B的数在A左边就可以了.

然后枚举​,看看最合适的​在哪里,遍历的方法如下:

  • 首先确定B,B左侧第一个大于B的数位.
  • 然后确定A,A从K+1开始遍历,然后判断A右侧第一个小于A的位置是不是在B右边
  • 计算值B的位置-A的位置+1.
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct statype{
	int bhei,bpos,ahei,apos;
}sta[100010];
int top=-1;
int main(){
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		top++;
		cin>>sta[top].bhei;
		sta[top].ahei=sta[top].bhei;
		sta[top].bpos=i;
		sta[top].apos=i;
		while(sta[top].bhei>sta[top-1].bhei&&top>=1){
			if(sta[top].ahei>sta[top-1].ahei){
				sta[top].ahei=sta[top-1].ahei;
				sta[top].apos=sta[top-1].apos;
			}
			sta[top-1]=sta[top];
			top--;
		}
		if(ans<sta[top].bpos-sta[top].apos+1)
			ans=sta[top].bpos-sta[top].apos+1;
	}
	if(ans==1)
		ans=0;
	cout<<ans<<endl;
return 0;
}
  • 如果是遇到了左括号,就递归求括号内的元素.
  • 如果是遇到了右括号,就把括号内的数据返回给上层.
  • 如果是遇到了a,就把当前的结果+1即可.
  • 如果是遇到了|,根据max(a,b,c)=max(a,max(b,c))的结合率进行递归求解,递归求解|右边的值,与当前计算得来的值进行比较.(因为遇到了|就代表当前部分的串已经结束了).、

P3719 rexp.

给出一个由(,),|,a组成的序列,求化简后有多少个a。

1、形如aa…a|aa…a|aa…a的,化简结果为“|”两边a的个数最多的一项,例如a|aa|aaa=aaa 2、先算带括号的序列,例如(a|a)|aaa=aaa

依次输入一个字符,分成下面几种情况:

  • 如果是遇到了左括号,就递归求括号内的元素.
  • 如果是遇到了右括号,就把括号内的数据返回给上层.
  • 如果是遇到了a,就把当前的结果+1即可.
  • 如果是遇到了|,根据max(a,b,c)=max(a,max(b,c))的结合率进行递归求解,递归求解|右边的值,与当前计算得来的值进行比较.(因为遇到了|就代表当前部分的串已经结束了).

P1185 绘制二叉树

这一题是非常复杂的一个模拟,下面分成几个部分来讲:

首先是初始化的操作:

void init(){
    if(n==1){
        h=1;
        w=1;
    }
    else if(n==2){
        h=3;
        w=5;
    }
    else{
        h=3;
        for(int i=3;i<=n;i++)h*=2;
        w=6*(1<<(n-2))-1;//计算画布大小
    }
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            c[i][j]=' ';
        }
    }
    int temp=1;
    isJiedian[1]=temp;
    for(int i=1;i<n;i++){
        temp=temp+g[n-i]+1;
        isJiedian[i+1]=temp;
    }
}

首先先计算画布的大小,初始化成空格,然后计算对于这个画布,画布的哪几行可以存放点的信息.

我们用数组来模拟树,用[X][Y]来模拟这是树的第X行和第Y个元素.

    scanf("%d %d",&n,&m);
    while(m--){
        scanf("%d %d",&x,&y);
        b[x][y]=true;
    }
    init();
    dfs(1,w/2+1,1,1,1);

然后标记已经被删除的点,从根结点(1,w/2+1)开始搜索.

搜索分成四类,一种是非叶子结点类型.dfs(画布的行,画布的列,树的行,树的列,下一个点的类型)

    if(k==1){
        c[x][y]='o';
        X++;
        Y=Y*2-1;
        if(!b[X][Y]){
            dfs(x+1,y-1,X,Y,2);
        }
        Y++;
        if(!b[X][Y]){
            dfs(x+1,y+1,X,Y,3);
        }
    }

非叶子结点可以同时往左和右搜索(前提是这个结点的左儿子和右儿子没有被删掉),X++和Y=Y*2-1是计算左儿子和右儿子在模拟数组中的值.

左下和右下走的列,这种点只能往左或者是右搜索,搜索的变数就是下一行是不是应该存储的是树的结点.

    else if(k==2){
        c[x][y]='/';
        if((x+1)==isJiedian[X]){
            dfs(x+1,y-1,X,Y,1);
        }
        else{
            dfs(x+1,y-1,X,Y,2);
        }
    }
    else{
        c[x][y]=92;
        if((x+1)==isJiedian[X]){
            dfs(x+1,y+1,X,Y,1);
        }
        else{
            dfs(x+1,y+1,X,Y,3);
        }
    }

最后一种就是叶子结点,是时候该返回了.

	if(x==h){c[x][y]='o';return;}

P3956 棋盘

有一个m×m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。

任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的), 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时,如果两个格子的颜色相同,那你不需要花费金币;如果不同,则你需要花费 1个金币。另外, 你可以花费 2个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用, 而且这个魔法的持续时间很短,也就是说,如果你使用了这个魔法,走到了这个暂时有颜色的格子上,你就不能继续使用魔法; 只有当你离开这个位置,走到一个本来就有颜色的格子上的时候,你才能继续使用这个魔法,而当你离开了这个位置(施展魔法使得变为有颜色的格子)时,这个格子恢复为无色。现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少?

转化为最短路径的问题.首先先构造图,构造图的同时我们需要找到出发点和终点.然后做djkstra算法即可.

那么怎么构建图?我们可以分成两种形式的问题.

  • 遍历所有带颜色的点,如果两个点相邻,这两个点之间的距离就是0和1.
  • 如果这两个点只差了一格,那么距离就是2+0或者1.
  • 假如说终点是没有颜色的,加上所有点到终点的边.
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include <cstring>
#define N 1002
int map[N][2],z[N][N],distance[N];
int start,end,flag;
int color[N];
int m,n;
int cloud[N];
void makeGraph(){
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(abs(map[i][0]-map[j][0])+abs(map[i][1]-map[j][1])==1){
                z[i][j]=z[j][i]=abs(color[i]-color[j]);
            }
            if(abs(map[i][0]-map[j][0])+abs(map[i][1]-map[j][1])==2){
                z[i][j]=z[j][i]=2+abs(color[i]-color[j]);
            }
        }
    }
    if(!flag){
        for(int i=1;i<=n;i++){
            if(abs(map[i][0]-map[end][0])+abs(map[i][1]-map[end][1])==1){
                z[i][end]=z[end][i]=2;
            }
        }
        n++;
    }

}
//对每条边进行松弛操作.
void makeDj(int k){
    distance[k]=0;
    int maxn,t;
    for(int i=1;i<=n;i++){
        maxn=99999999;
        for(int j=1;j<=n;j++){
            if(cloud[j]==0&&distance[j]<maxn){
                maxn=distance[j];
                t=j;
            }
        }
        cloud[t]=1;
        for(int j=1;j<=n;j++){
            distance[j]=std::min(distance[t]+z[t][j],distance[j]);
        }
    }
}
int main(){
    memset(z,1,sizeof(z));
    memset(distance,1,sizeof(distance));
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&map[i][0],&map[i][1],&color[i]);
      //在这里map记录了每个点的数据,所以说i和j可以代表点的序号
        if(map[i][0]==1&&map[i][1]==1){
            start=i;
        }
        else if(map[i][0]==m&&map[i][1]==m){
            end=i;
            flag=1;
        }
    }
    if(!flag){
        end=n+1;
        map[end][0]=map[end][1]=m;
    }
    makeGraph();
    makeDj(start);
    if(distance[end]<16843009)
    printf("%d\n",distance[end]);
    else if(m!=1){
        puts("-1");
    }
    else{
        puts("0");
    }
}

P1983 车站分级(拓扑排序)

一条单向的铁路线上,依次有编号为 1,2,…,n的 n个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站x的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点),现在给定了若干个停靠的关系,现在求最多有几级?

建图,然后拓扑排序即可.

首先是建图:

    while(m--){
        memset(is, 0, sizeof(is));
        scanf("%d",&s);
        for(int i=1;i<=s;i++){
            scanf("%d",&stations[i]);
            is[stations[i]]=true;
        }
        for(int i=stations[1];i<=stations[s];i++){
            if(!is[i]){
                for(int j=1;j<=s;j++){
                    if(!tuopu[i][stations[j]]) {
                        tuopu[i][stations[j]]=1;
                        rudu[stations[j]]++;
                    }
                }
            }
        }
    }

对于每一条铁路线路,我们有边:[没停靠的站][停靠的站]=1.

    int top=1;
    while(top){
        top=0;
        for(int i=1;i<=n;i++){
            if(!rudu[i]&&!shanchu[i]){
                ruduweizero[top++]=i;
                shanchu[i]=true;
            }
        }
        for(int i=0;i<top;i++){
            for(int j=1;j<=n;j++){
                if(tuopu[ruduweizero[i]][j]) {
                    tuopu[ruduweizero[i]][j]=0;
                    rudu[j]--;
                }
            }
        }
        ans++;
    }

然后进行拓扑排序,把入度为1的点全部删除掉.

P1038 神经网络

神经网络就是一张有向图,图中的节点称为神经元,而且两个神经元之间至多有一条边相连.这一级传递给下一级的激励是由上一级传递给这一级的激励决定的.

现在给定每个神经元一开始的激励,然后给定神经元之间的激励传递函数.求输出神经元的输出激励.

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 105
#define M 10005
int n,p;
struct egdes{
    int y;
    int val;
    int next;
}a[M];
struct answers{
    int val;
    int x;
}ans[N];
int total;
int c[N],u[N],rudu[N],chudu[N],head[M];
int cnt;
std::queue <int> q;
bool vis[N];
void add(int x,int y,int val){
    cnt++;
    a[cnt].y=y;
    a[cnt].val=val;
    a[cnt].next=head[x];
    head[x]=cnt;
}
bool cmp(struct answers a,struct answers b){
    return a.x<b.x;
}
int main(){
  //输入初态
    scanf("%d %d",&n,&p);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&c[i],&u[i]);
      //把初始的结点放入队列
        if(c[i]) {
            q.push(i);
            vis[i]=true;
        }
        else c[i]-=u[i];
    }
  //输入边的构造,链式前向星
    for(int i=1;i<=p;i++){
        int x,y,val;
        scanf("%d %d %d",&x,&y,&val);
        add(x, y, val);
        rudu[y]++;
        chudu[x]++;
    }
  //从初始值开始往后传递,一条边可以进行一次传递,然后把后面的点入队.这样子可以保证按照拓扑排序的顺序来进行遍历.
    while(!q.empty()){
        int f=q.front();
        q.pop();
        vis[f]=0;
        //non-exicited
        if(c[f]<0){
            continue;
        }
        //the edge start from front
        for(int i=head[f];i;i=a[i].next){
            int y=a[i].y;
            c[y]+=a[i].val*c[f];
            if(!vis[y]){
                q.push(y);
                vis[y]=1;
            }
        }
    }
    //计算所有被激活的而且出度为0的值(最终值.)
    for(int i=1;i<=n;i++){
        if(c[i]>0&&chudu[i]==0){
            total++;
            ans[total].x=i;
            ans[total].val=c[i];
        }
    }
    std::sort(ans+1,ans+1+total,cmp);
    if(total){
        for(int i=1;i<=total;i++){
            printf("%d %d\n",ans[i].x,ans[i].val);
        }
    }
    else{
        printf("NULL");
    }
}

P1381 单词背诵

灵梦有 n个单词想要背,但她想通过一篇文章中的一段来记住这些单词。文章由 m个单词构成,她想在文章中找出连续的一段,其中包含最多的她想要背的单词(重复的只算一个)。并且在背诵的单词量尽量多的情况下,还要使选出的文章段落尽量短,这样她就可以用尽量短的时间学习尽可能多的单词了。

我们每次记录此时有多少个单词,若比之前多,则直接更新长度与数量。 然后在更新左边 l,若最左边的单词不想背,或后文已出现就更新,把长度去最短即可。

#include <map>
#include <string>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define N 100005
std::map<std::string,int> tongji;
std::map<std::string,bool> flags;
std::string s1[N];
std::string s2;
int n,m,l;
int ans1,ans2;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        std::cin>>s2;
        flags[s2]=1;
    }
    scanf("%d",&m);
    l++;
    for(int i=1;i<=m;i++){
        std::cin>>s1[i];
        if(flags[s1[i]]) tongji[s1[i]]++;
        if(tongji[s1[i]]==1) {
            ans1++;
            ans2=i-l+1;
        }
        while(l<=i){
            //不用背
            if(!flags[s1[l]]) {
                l++;
                continue;
            }
            //后问已经出现了
            if(tongji[s1[l]]>1){
                tongji[s1[l]]--;
                l++;
                continue;
            }
            break;
        }
        ans2=std::min(ans2,i-l+1);
    }
    printf("%d\n%d\n",ans1,ans2);
}

 

隐藏