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