洛谷刷题记录(绿到蓝)
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);
}