P2367 语文成绩(差分前缀和)

题目描述

语文老师总是写错成绩,所以当她修改成绩的时候,总是累得不行。她总是要一遍遍地给某些同学增加分数,又要注意最低分是多少。你能帮帮她吗?

输入格式

第一行有两个整数 ,代表学生数与增加分数的次数。

第二行有 个数,,代表各个学生的初始成绩。

接下来 行,每行有三个数代表给第 x个到第 y个学生每人增加 z分。

现在有一个数组,我们要对一个数组的一个小区间统一进行加减操作,就是需要做差分操作.

首先我们需要做一个差分数组,差分数组是数组的两个元素之间的差值.然后对每一个区间做加减运算的时候,我们只需要在首尾处对差分树组进行操作.进行操作.然后再进行合并即可.合并的操作就是给定数组的第一个元素,根据差分数组的定义进行加即可.

1、首先构造差分数组.

2、接着对每一次小区间加减进行操作.

3、然后合并差分数组.

//这个时候还不会stl,甚至还没有养成用宏来开数组的习惯
#include<stdio.h>
int n,p,a[5000005],f[5000005],ans=9999999,sum;
int min(int a,int b){
    return a<b?a:b;
}
int main(){
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=p;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        f[x]+=z;
        f[y+1]-=z;
    }
    for(int i=1;i<=n;i++){
        sum+=f[i];
        a[i]=sum;
        ans=min(ans,a[i]);
    }
    printf("%d",ans);
}

双倍经验:CF44C Holiday (差分前缀和)

对于有若干个区间,求一个点被多少个区间覆盖的问题就可以使用差分前缀和的思想.因为答案数组是全0的,对应的差分数组也是全0,输入每一个区间就相当于在这个区间做加1操作.然后合并即可

那么差分是怎么做的,下面看题:

天假期,安排个人来浇花,第i个人负责天,问花是否可以每天都被浇水且不重复。 可以的话输出“OK”,不可以的话输出最早出问题的那天的天号以及那天花被浇了多少次水。

这道题就是有若干个区间,你需要找到每个点被多少个区间覆盖.那么我们可以进行差分,每一次进行+1操作即可,由于一开始数组取值为0,所以说初始的构造差分数组的步骤可以省略/

#include <stdio.h>
#define N 105
int a[N];
int b[N];
int k[N];
int n,m;
int flag;
int i;
int ans;
int main(){
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d %d",&a[i],&b[i]);
        k[a[i]]++;
        k[b[i]+1]--;
    }
    for(int i=1;i<=n;i++){
        k[i]+=k[i-1];
        if(k[i]!=1){
            printf("%d %d",i,k[i]);
            return 0;
        }
    }
    printf("OK");
}

P1160 队列安排(队列模版题,包含队列的添加和删除操作)

image-20220406211731519

这道题就是一个纯粹的队列的模拟问题,我们可以采用数组模拟链表的策略,就是记录两个数组,来记录左边和右边的人是谁,就是在i右边的人,是i左边的人是谁,添加的时候先判断是左边还是右边,插入的方法和删除的方法不需要多说了,这就是一个双向队列的模版.插入的时候注意插入的顺序即可

#include<stdio.h>
int n,m,nex[100010],be[100010],t[100010];
int head=1;
int main()
{
    scanf("%d",&n);
    for(int i=2,k,p;i<=n;i++)
    {
        scanf("%d%d",&k,&p);
        if(!p)
        {
            int before=be[k];
            nex[before]=i;nex[i]=k;            
            be[k]=i;be[i]=before;
            if(k==head)    head=i;
        }else
        {
            nex[i]=nex[k];nex[k]=i;    
            be[nex[i]]=i;be[i]=k;     
        }
    }
    scanf("%d",&m);
    for(int i=1,c;i<=m;i++)
        scanf("%d",&c),t[c]=1;
    for(int i=1;i<=n;i++)
    {
        if(!t[head])    printf("%d ",head);
        head=nex[head];
    }
//better delete.
//int be=be[i];
//int nex=nex[i];
//nex[be]=nex;
//be[nex]=be;
    return 0;
}

P1044 栈

给定一个数,入栈序列一共有多少个出栈序列.

本质上是数学题,但是在计算机中比较难以计算.所以说用卡特兰数的定义是直接RE.

#include<stdio.h>
int n,m,nex[100010],be[100010],t[100010];
int head=1;
int computeCMN(int m, int n) {
	if (n == 0 || m == n) return 1;
	int c1 = computeCMN(m - 1, n);
	int c2 = computeCMN(m - 1, n - 1);
	return c1 + c2;
}
int main()
{
    scanf("%d",&n);
    printf("%d",computeCMN(2*n,n)-computeCMN(2*n,n-1));
}

那我们怎么办呢?我们这个时候还知道卡特兰序列有这么一个性质:

这个时候我们就可以进行递推就可以得到啦!

#include<stdio.h>
int n,m,nex[100010],be[100010],t[100010];
int head=1;
int main()
{
    scanf("%d",&n);
    nex[0]=1;
    nex[1]=1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<i;j++){
            nex[i]+=nex[j]*nex[i-j-1];
        }
    }
    printf("%d",nex[n]);
}

当然还有一种更加巧妙的.

P1449 后缀表达式(栈的经典问题)

所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。

如:对应的后缀表达式为:。’@’为表达式的结束符号。‘.’为操作数的结束符号。

#include<stdio.h>
char s[100005];
int stack[100005];
int main(){
    int top=0,i=0,x;
    scanf("%s",s);
    while(s[i]!='@'){
        switch (s[i])
        {
        case '+':stack[--top]+=stack[top+1];break;//出栈之后再进栈
        case '-':stack[--top]-=stack[top+1];break;
        case '*':stack[--top]*=stack[top+1];break;
        case '/':stack[--top]/=stack[top+1];break;       
        default:
            x=0;
            while(s[i]!='.'){
                x=x*10+s[i++]-'0';
            }
            stack[++top]=x;
            break;
        }
        i++;
    }
    printf("%d",stack[top]);
}

遍历整个字符串,如果是基本的数字的话就把数字计算(计算方式和C语言学过的一模一样,数字字符串转数字的方法)出来然后入栈.如果是运算符就把栈顶的两个数字取出来做运算符对应的运算然后再放回栈中.

(双倍经验) P1981 表达式求值

给定一个只包含加法和乘法的算术表达式,请你编程计算表达式的值。

先输入一个符号然后输入一个数字,然后判断符号的类型,如果是乘的话,优先级最高,就可以先做.取一个数然后乘,如果是加的话就直接把这个数字push进去就好了,因为只用处理乘,剩下的堆栈中存放的就是加法的加数.

#include<stdio.h>
#include<stack>
using namespace std;
//char s[100005];
//int stack[100005];
stack<int> num;
stack<char> op;
#define MOD 10000
int main(){
    char ch;
    int number;
    int n1,n2;
    scanf("%d",&number);
    num.push(number);
    while(1){
        ch=getchar();
        if(ch=='\n') break;
        scanf("%d",&number);
        if(ch=='*'){
            n1=num.top();
            num.pop();
            num.push((n1%MOD)*(number%MOD));
        }
        if(ch=='+'){
            num.push(number);
        }
    }
    int sum = 0;
    while (!num.empty()) {
        sum += num.top();
        sum %= 10000;
        num.pop();
    }
    printf("%d",sum);
}

 

P1165 日志分析(模拟栈)

image-20220406214705134

#include<stdio.h>
#include<math.h>
#include<string.h>
int n,p,now,maxn;
int s[200005];
int top=-1;
int max(int x,int y){
    return x>y?x:y;
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&p);
        if(p==0)
        {
            scanf("%d",&s[++top]);
            s[top]=max(s[top],s[top-1]);
        }
        else if(p==1)
        {
            if(top==-1)continue;
            s[top--]=0;
        }
        else if(p==2)
            printf("%d\n",s[top]);
    }
    return 0;
}
  1. 操作0(集装箱进库操作,相当于进栈),如果输入的数小于之前的最大值,就仍然存储原来的最大值因为后进先出,当前的如果小,永远不可能被操作2询问到,所以存了也没用,不然入栈,栈顶+1.栈f,就是从元素的最大值.
  2. 操作1(集装箱出库操作,相当于出栈),直接栈顶-1.因为我们不需要知道最近入栈的元素是什么.所以说我们只需要知道当前所有元素的最大值就好了,一个元素的出栈就是我们不需要再讨论包含它的最大值,仅此而已.栈顶就是少了刚入栈的最大值即可.
  3. 操作2(集装箱询问操作,由于此时的栈顶是最大值,可以直接输出)

P5788 单调栈模版

定义函数为第i个元素之后第一个大于的下标,求

举一个生活中的例子,就是对于若干个人排队,往后看,你可以看到第一个比你高的人,比你矮的人你全部都看不见,会被遮住,所以说这些点我们也不需要考虑了.

所以我们可以从后往前扫描并且维护一个栈,在栈中小于等于的要删掉,那么栈顶的就是第一个比大的下标.因为堆栈具有单调性质,在栈底的下标最大,在栈顶的下标最小.那我们从下标最小的栈顶往下走,找到第一个满足题目条件的下标.不满足题目条件的下标由于之后肯定用不到所以说可以删除.

最后一步就是这个数入栈.

#include <iostream>
#include <algorithm>
#include <cstdio>
#define N = 3000005;
int a[N], st[N], ans[N];
int top;
int n;

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=n;i>=1;i--) {
		while(top&&a[st[top]]<=a[i])	top--;
		ans[i]=st[top];
		st[++top]=i;
	} 
	for(int i=1;i<=n;i++)	printf("%d ",ans[i]);
	return 0;
}

P1886 滑动窗口/单调队列模版.

有一个长为 的序列,以及一个大小为的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。

首先是样例:

8 3
1 3 -1 -3 5 3 6 7

下文中我们用q来表示单调队列,p来表示其所对应的在原列表里的序号。

  1. 由于此时队中没有一个元素,我们直接令1进队。此时,q={1},p={1}。
  2. 现在3面临着抉择。下面基于这样一个思想:假如把3放进去,如果后面2个数都比它大,那么3在其有生之年就有可能成为最小的。此时,q={1,3},p={1,2}
  3. 下面出现了-1。队尾元素3比-1大,那么意味着只要-1进队,那么3在其有生之年必定成为不了最小值,原因很明显:因为当下面3被框起来,那么-1也一定被框起来,所以3永远不能当最小值。所以,3从队尾出队。同理,1从队尾出队。最后-1进队,此时q={-1},p={3} 输出-1
  4. 出现-3,同上面分析,-1>-3,-1从队尾出队,-3从队尾进队。q={-3},p={4}。 输出-3
  5. 出现5,因为5>-3,同第二条分析,5在有生之年还是有希望的,所以5进队。此时,q={-3,5},p={4,5} 输出-3
  6. 出现3。3先与队尾的5比较,3<5,按照第3条的分析,5从队尾出队。3再与-3比较,同第二条分析,3进队。此时,q={-3,3},p={4,6}输出-3
  7. 出现6。6与3比较,因为3<6,所以3不必出队。由于3以前元素都<3,所以不必再比较,6进队。因为-3此时已经在滑动窗口之外,所以-3从队首出队。此时,q={3,6},p={6,7} 输出3
  8. 出现7。队尾元素6小于7,7进队。此时,q={3,6,7},p={6,7,8}。 输出3

总结一下: 假设入队从后往前比较:

(1)如果:

入队

(2)如果

出队,继续比较,知道队列没有元素或者有

#include<stdio.h>
#include<stack>
#include<math.h>
#include<string.h>
using namespace std;
//char s[100005];
//int stack[100005];
//stack<int> num;
//stack<char> op;
#define MOD 10000
#include<map>
#include<queue>
int xianxu[1000];
int a[10000005],value[100000005],queue1[100000005];
int main()
{
    int n,k;
    int h=1,t=1;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        //维护单调队列
        while(h<t&&value[t-1]>a[i])t--;
        value[t]=a[i];
        queue1[t++]=i;
        if(i-queue1[h]>=k)h++;
        if(i>=k) printf("%d ",value[h]);
    }
    puts("");
    h=1,t=1;
    for(int i=1;i<=n;i++){
        while(h<t&&value[t-1]<a[i])t--;
        value[t]=a[i];
        queue1[t++]=i;
        if(i-queue1[h]>=k)h++;
        if(i>=k) printf("%d ",value[h]);
    }
}

UVA540 团体队列(队列模拟)

个团队的人正在排长队。每有一个新来的人时,他会从队首开始向后搜寻,如果发现有队友正在排队,他就会插队到他队友的身后;如果没有发现任何一个队友排队,他就只好站在长队的队尾。输入每个团队中所有队员的编号,要求支持如下 种指令:ENQUEUE x:编号为 x 的人进入长队。DEQUEUE:长队的队首出队。STOP:停止模拟。对于每个 DEQUEUE 指令,输出出队的人的编号。

这道题也是一个队列的模拟题,这一道题的难点就是在如何找到队友并插入.构建一个二维数组太慢了,不如我们用一下stl吧,这个stl叫做map,这个map可以帮我们做哈希映射,我们可以在很快的时间内找到序号和对应的分组.

就是说我们可以首次调用map[x]=y,建立的映射,这个映射的查找是的,

#include<stdio.h>
#include<stack>
#include<math.h>
#include<string.h>
using namespace std;
#define MOD 10000
#include<map>
#include<queue>
int t,number=0;
char* str;
int x;
int main()
{
    str=(char*)malloc(50);
    while(scanf("%d",&t)==1&&t>0){
        map<int ,int> team;
        printf("Scenario #%d\n",++number);
        for(int i=0;i<t;i++){
            int n;
            scanf("%d",&n);
            int code;
            while(n--){
                scanf("%d",&code);
                team[code]=i;
            }
        }
        queue<int> q,q_sup[100005];
        while(1){
            scanf("%s",str);
            if(*str=='S') break;
            else if(*str=='D'){
                x=q.front();
                printf("%d\n",q_sup[x].front());
                q_sup[x].pop();
                if(q_sup[x].empty()) q.pop();
            }
            else if(*str=='E'){
                scanf("%d",&x);
                int t=team[x];
                if(q_sup[t].empty())q.push(t);
                q_sup[t].push(x);
            }
        }
        printf("\n");
    }
}

一开始先建立map的映射关系,然后进行操作的时候我们维护一个主队列,主队列里面存储着小组的顺序,然后维护一个小组队列,存储着小组里面有什么人,由于插入的时候只会插入到每个小组的人后面,所以说出队也是按照小组的顺序出队,只有这个小组的所有人都出队了(判断方法,小组队列为空),才轮到另外一个小组出队.所以说入队的时候看看你是不是小组第一个,如果是的话就在主队列排一个队.出队的时候看看你是不是小组最后一个,如果是的话,就出主队列.总之由于出队一定是一个队一个队的顺序出队的,我们只需要记录队与队之间的顺序和队内部的顺序就好了.

P1162 填涂颜色(简单深搜)

由数字组成的方阵中,有一任意形状闭合圈,闭合圈由数字构成,围圈时只走上下左右个方向。现要求把闭合圈内的所有空间都填写成.例如:的方阵(),涂色前和涂色后的方阵如下:

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1 

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
#include<stdio.h>
#include<stack>
#include<math.h>
#include<string.h>
using namespace std;
//char s[100005];
//int stack[100005];
stack<int> num;
stack<char> op;
#define MOD 10000
int N,a[100][100];
void dfs(int x,int y){
    if(a[x][y]!=0)return ;
    a[x][y]=-1;
    if(x+1<=N)dfs(x+1,y);
    if(x-1>=1)dfs(x-1,y);
    if(y+1<=N)dfs(x,y+1);
    if(y-1>=1)dfs(x,y-1);
}
int main()
{
    
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=N;i++)
        if(a[1][i]==0)dfs(1,i);
        else if(a[N][i]==0)dfs(N,i);
    for(int i=1;i<=N;i++)
        if(a[i][1]==0)dfs(i,1);
        else if(a[i][N]==0)dfs(i,N);
    for(int i=1;i<=N;i++)
    {
        if(a[i][1]==-1)printf("0");
        else if(a[i][1]==0)printf("2");
        else printf("1");
        for(int j=2;j<=N;j++)
        {
            if(a[i][j]==-1)printf(" 0");
            else if(a[i][j]==0)printf(" 2");
            else printf(" 1");
        }
        printf("\n");
    }
    return 0;
}

这里就是深度优先搜索,从边界开始进行搜索,遇到了可用的点就先进行标记,完后往上下左右搜索,遇到不可用的点(墙)就停止,这个时候没搜索到的就是被墙围起来的那部分.

P1042 乒乓球(字符串小模拟)

image-20220410195828465

不贴代码了,这道题就是模拟题,我们就依次读取,维护两组元素,分别是11分下的胜负和21分下的胜负,用一个数组存储胜负的信息.a[N][0]存储的就是第N局的信息.判断每一局结束的标准就是分数是否超过了11(21)分并且两位选手的分差是不是大于2.

P1553 数字反转升级版(字符串小模拟)

给定一个数,请将该数各个位上数字反转得到一个新数。

这次与NOIp2011普及组第一题不同的是:这个数可以是小数,分数,百分数,整数。整数反转是将所有数位对调;小数反转是把整数部分的数反转,再将小数部分的数反转,不交换整数部分与小数部分;分数反转是把分母的数反转,再把分子的数反转,不交换分子与分母;百分数的分子一定是整数,百分数只改变数字部分。整数新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零;小数新数的末尾不为0(除非小数部分除了0没有别的数,那么只保留1个0);分数不约分,分子和分母都不是小数(约分滴童鞋抱歉了,不能过哦。输入数据保证分母不为0),本次没有负数。

给定一个数,请将该数各个位上数字反转得到一个新数。

这次与NOIp2011普及组第一题不同的是:这个数可以是小数,分数,百分数,整数。

  • 整数反转是将所有数位对调。
  • 小数反转是把整数部分的数反转,再将小数部分的数反转,不交换整数部分与小数部分。
  • 分数反转是把分母的数反转,再把分子的数反转,不交换分子与分母。
  • 百分数的分子一定是整数,百分数只改变数字部分。

这次我们来了解一下string的一些操作:

# include<iostream>
# include<string>
 
using namespace std;
 
bool isZero(string s)
{
	int j = 0;
	for(int i = 0;s[i];++i)
		if(s[i] == '0')
			j++;
			
	if(j == s.length())
		return true;
	else
		return false;
}
 
//倒置 
void transpos(string s1,string &s2)
{
	for(int i = s1.length()-1,j = 0;i >= 0;--i)
		s2 += s1[i];
}
 
//去除前导0
void dePreZero(string s1,string &s2)
{
	int i = 0;
	while(s1[i] == '0')
		i++;
	s2.assign(s1,i,s1.npos);
 }
 
//去除后缀0
void  deSufZero(string s1,string &s2)
{
	int i = s1.length()-1;
	while(s1[i] == '0')
	{
		i--;
	}
	s2.assign(s1,0,i+1);
}
 
int main()
{
	string s,ans,tmp;
	int idx;//特殊符号的位置 
	
	getline(cin,s);
	if(s.find('.',0) != -1)
	{
		idx = s.find('.',0);
		tmp.assign(s,0,idx);
		if(isZero(tmp))
			ans.assign("0");
		else
		{
			transpos(tmp,ans);
			dePreZero(ans,ans);
		}	
		cout << ans;
		cout << '.';
		tmp.clear();
		ans.clear();
		tmp.assign(s,idx+1,s.npos);
		if(isZero(tmp))
			ans.assign("0");
		else
		{
			transpos(tmp,ans);
			deSufZero(ans,ans);
		}
		cout << ans; 
	}
	else if(s.find('/',0) != -1)
	{
		idx = s.find('/',0);
		tmp.assign(s,0,idx);
		if(isZero(tmp))
			ans.assign("0");
		else
		{
			transpos(tmp,ans);
			dePreZero(ans,ans);
		}
		cout << ans << "/";
		tmp.clear();
		ans.clear();
		tmp.assign(s,idx+1,s.npos);
		if(isZero(tmp))
			ans.assign("0");
		else
		{
			transpos(tmp,ans);
			dePreZero(ans,ans);
		}
		cout << ans; 
	}
	else if(s.find('%',0) != -1)
	{
		idx = s.find('%',0);
		tmp.assign(s,0,idx);
		if(isZero(tmp))
			ans.assign("0");
		else
		{
			transpos(tmp,ans);
			dePreZero(ans,ans);
		}
		cout << ans << '%';
	}
	else
	{
		if(isZero(s))
			ans.assign("0");
		else
		{
			transpos(s,ans);
			dePreZero(ans,ans);
		}
		cout << ans;
	}
 
 	return 0;
}

首先是前面几个辅助的函数,函数的声明里面有一个代表函数对这个变量的修改也会顺便引起对主程序里面变量的修改(和传指针一样).首先是转置函数,从后往前把字符串的值添加到中,由于已经做好了运算符重载,所以我们可以直接用+来进行添加元素的操作.接着就是去除前导0和后置0的,无非就是从前往后遍历和从后往前遍历而已.

那就分成几种就好办了,第一种就是小数,我们找到小数点,然后把小数点前面的值做一次翻转,去掉前面的0,然后小数点后面的值做一次翻转,去掉后面的0.就可以了 分数也是一样,找到分数符号,下亦同. 百分号,从1~s.length()-1处理即可.去掉前缀0. 整数最简单.

P1332 Logo语言(字符串递归)

Logo 语言命令可以指挥海龟在屏幕中爬行。本问题只使用 Logo 语言的三个语句:前进 FD,倒退 BK和重复 REPEAT,因此,海龟只在一条直线上来回爬行。输入一行 logo 的命令行,输出海龟在屏幕中离开原来位子的距离(假设屏幕很大,可以让海龟移开 1000000010000000 的距离)。

例如:

  • 输入 FD 100 ,输出:100。
  • 输入 FD 100 BK 150, 输出:50。
  • 输入 REPEAT 5[FD 100 BK 50], 输出:250。
  • 输入 REPEAT 5[ FD 50 REPEAT 10[FD 100]], 输出:5250。

一般来说,遇到带括号的式子,朴素的想法就是递归.对于括号的处理往往是系数*括号内的内容值,括号内的内容也可以理解为一个式子的值,递归的基本条件也达成了.那我们就通过cin来处理字符串,(当然你用一个函数参数表示现在处理到什么位置也可以,或者用一个全局变量也可以).这道题用printf感觉不太行,就用cin了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define maxn 100005
#define ll long long
int handle(){
    char ch,x;string a;int n,ans=0;
    while (cin>>ch){
        if (ch==']') break;
        cin>>a>>n;
        if (ch=='R'){
          	//读入‘[’
            x=getchar();
            ans+=n*handle();
          	//读入空格
            x=getchar();
        }
        if (ch=='F'){
          	//读入空格
            x=getchar();
            ans+=n;
        }
        if (ch=='B'){
            x=getchar();
            ans-=n;
        }
        if (x==']') break;
    }  
    return ans;
}
int main(){
    cout<<abs(handle());
    return 0;
}

首先先读取一下第一个指令的字符,反正只有几种,一个是FD前进,BK后退和REPEAT重复.那就每一次读取都读取一个字符串(输入剩下来的字符,比如说“EPEAT”,“D”,“K”等).还有一个数字,然后根据功能进入到不同的值中,(如果遇到了]就代表这一层括号已经结束了,可以返回递归的结果).(需要处理括号然后求出括号内的值的就需要用到递归,递归地求出值然后传给主函数)

P3375 KMP字符串匹配(KMP模版)

用字符串匹配就用KMP最好不过了2333

#include<algorithm>
#include <stdio.h>
#include <cstring>
#define N 1000000+5
using namespace std;
char a[N];
char b[N];
int kmp[N];
int main(){
    scanf("%s",a+1);
    scanf("%s",b+1);
    int a_length=strlen(a+1);
    int b_length=strlen(b+1);
    int p;
    for(int i=2;i<=b_length;i++){
        p=kmp[i-1];
        while(p&&b[p+1]!=b[i]){
            p=kmp[p];
        }
        if(b[p+1]==b[i]) kmp[i]=p+1;
    }
    p=0;
    for(int i=1;i<=a_length;i++){
        if(b[p+1]==a[i]) p++;
        else{
            while(p && b[p+1]!=a[i])p=kmp[p];
            if(b[p+1]==a[i])p++;
        }
        if(p==b_length)printf("%d\n",i-b_length+1);
    }
    for(int i=1;i<=b_length;i++)printf("%d ",kmp[i]);
}

首先就是KMP数组.就是字符串的前位组成的子串种前j位和后j位一样,比如说"".其中,就是这个字符串前5位的前3位和后3位都是""

然后就是匹配,不匹配就直接从重新开始,就酱紫...

P1030 给定中序后序求先序(双倍经验P1827 美国血统)

#include<stdio.h>
#include<iostream>
#include<cstring>
#define N 10
char houxu[N];
char zhongxu[N];
int find(char ch){
    int i=0;
    while(zhongxu[i]!=ch){
        i++;
    }
    return i;
}
void DFS(int l1,int r1,int l2,int r2){
    char ch = houxu[r2];
    printf("%c",ch);
    int m = find(ch);
    if(m>l1) DFS(l1, m-1,l2,r2-r1+m-1);//r1-m是右子树的数目
    if(m<r1) DFS(m+1, r1, l2-l1+m, r2-1);
    
}
int main(){
    scanf("%s",zhongxu);
    scanf("%s",houxu);
    int len=strlen(zhongxu);
    DFS(0,len-1,0,len-1);
}

首先我们在数据结构课中做这种题就是先找到后序遍历中找到根结点.然后根据根结点把中序遍历序列分成两部分.左中右,然后在搜索左子树和右子树.即可,搜索的函数就是(中序遍历首,中序遍历尾,后序遍历首,后序遍历尾).分成左右两个子树进行搜索即可.

中序:左中右 后序:左右中 然后按照这个规则进行切割,切割出左子树的部分和右子树的部分即可.

P1087 FBI树(二叉树递归构造和模拟)

image-20220410211808841

我们递归判断的时候可以这么做,如果这个树长度只有1,那么我们可以通过这个树的本身来判断究竟是B还是I树.如果这个树的长度比较长,那我们判断左子树和右子树的类型来判断这个树是FBI中的哪一种.进行遍历就好了,所以说甚至建树都不用建,用一个dfs打一个搜索就好啦!

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
#define N 2000
char str[N];
int n;
int tree(int l,int r){
    int mid=(l+r)/2;
    if(l==r){
        if(str[l]=='1') {
            printf("I");
            return 1;
        }
        else {
            printf("B");
            return 0;
        }
    }
    int le,ri;
    if(l<r){
        le=tree(l,mid);
        ri=tree(mid+1,r);
    }
    if(le==0&&ri==0) {
        printf("B");
        return 0;
    }
    else if(le==1&&ri==1){
        printf("I");
        return 1;
    }
    else{
        printf("F");
        return 2;
    }
    
}
int main(){
    scanf("%d",&n);
    scanf("%s",str+1);
    tree(1,pow(2,n));
}

P3884 二叉树问题(LCA--最近公共祖先,树链剖分)

输入格式

输入文件第一行为一个整数n(1≤n≤100),表示二叉树结点个数。接下来的n-1行,表示从结点x到结点y(约定根结点为1),最后一行两个整数u、v,表示求从结点u到结点v的距离。

输出格式

三个数,每个数占一行,依次表示给定二叉树的深度、宽度及结点u到结点v间距离.

注:结点间距离的定义:由结点向根方向(上行方向)时的边数×2, 与由根向叶结点方向(下行方向)时的边数之和。

这个是非常经典的树的问题:

#include<stdio.h>
#include<algorithm>
#define N 105
int father[N],depth[N],width[N],son[N],parent[N];
int n;
int x,y;
int find_father(int x,int y){
    if(x==y) return x;
    if(depth[x]==depth[y]) return find_father(parent[x], parent[y]);
    else if(depth[x]<depth[y]) return find_father(x, parent[y]);
    else return find_father(parent[x], y);
}
int main(){
    depth[1]=1;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d %d",&father[i],&son[i]);
        parent[son[i]]=father[i];
        depth[son[i]]=depth[father[i]]+1;
    }
    scanf("%d %d",&x,&y);
    //depth
    int max_depth=0;
    for(int i=1;i<=n;i++){
        max_depth=std::max(max_depth,depth[i]);
        width[depth[i]]++;
    }
    printf("%d\n",max_depth);
    int max_width=0;
    for(int i=1;i<=n;i++){
        max_width=std::max(max_width,width[i]);
    }
    printf("%d\n",max_width);
    int fa=find_father(x,y);
    printf("%d\n",(depth[x]-depth[fa])*2+(depth[y]-depth[fa]));
}

第一个问题就是求深度,由于保证输入的时候按照序号顺序输入的,所以说可以用上面的方法.如果乱序的话还是要遍历一遍树的.求深度的时候用depth[i]表示i结点的深度是depth[i],然后再把每个深度有多少个结点保存起来,这样求宽度也求好了.

最关键的就是求两个点的距离了.求两个点的距离就是要找到最近的公共祖先,假设祖先为z,首先要从x往上走找到公共祖先,然后再从公共祖先往下走即可,走的步数可以直接用深度差表示.公共祖先找法是,先保持深度一样.然后再往上找,直到父亲是一样的为止.

P4913 二叉树深度

求二叉树的深度

#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
#define N 1000005
struct BiTree{
    int l;
    int r;
};
struct BiTree tr[N];
int n;

int se(int root){
    if(tr[root].l==0&&tr[root].r==0){
        return 1;
    }
    int l=0,r=0;
    if(tr[root].l)
        l = se(tr[root].l)+1;
    if(tr[root].r)
        r = se(tr[root].r)+1;
    return max(l,r);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&tr[i].l,&tr[i].r);
    }
    int s = se(1);
    printf("%d",s);
}

用数组来模拟二叉树.Br[l]代表结点号为l的二叉树,成员中l为左子树结点,r为右子树结点.那就是经典前序遍历,检查本结点,遍历左子树和右子树,然后找最大值即可.

P5318 查找文献(BFS和DFS)

给定一个图,寻找DFS和BFS序列.

在搜索之前我们先排序,因为对于图来说,优先输出数字比较小的元素,将比较小的元素放前面也有助我们排序.然后就是构建一个边的集合,在构建一个链接表,链接表LinkNodes[i]存储着所有起点为i的边的边号.

接着就是DFS和BFS了,对于BFS,就是维护一个队列,每一次都把没有遍历过且链接的东东入队,做完后取一个出队.DFS就是维护一个栈,栈的表示就是递归,搜索没有遍历过且链接的东东,找到就立刻跳转.对新结点进行搜索.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct edg{
    int u;
    int v;
};
vector<edg> edgs;
vector<int> LinkNodes[100005];
queue<int> q;
int n,m;
bool cmp(edg x,edg y){
    if(x.v==y.v) return x.u<y.u;
    else return x.v<y.v;
}
bool dfs_OK[100005],bfs_OK[100005];
void bfs(int x){
    q.push(x);
    printf("%d ",x);
    bfs_OK[x]=true;
    while(1){
        int k=q.front();
        for(auto&i:LinkNodes[k]){
            if(!bfs_OK[edgs[i].v]){
                q.push(edgs[i].v);
                printf("%d ",edgs[i].v);
                bfs_OK[edgs[i].v]=true;
            }
        }
        q.pop();
        if(q.empty()) break;
    }
}
void dfs(int x){
    dfs_OK[x]=true;
    printf("%d ",x);
    for(auto&i:LinkNodes[x]){
        if(!dfs_OK[edgs[i].v]) dfs(edgs[i].v);
    }
    return;
}
int main(){
    scanf("%d %d",&n,&m);
    int x,y;
    int k=m;
    while(k--){
        scanf("%d %d",&x,&y);
        edgs.push_back((edg){x,y});
    }
    sort(edgs.begin(),edgs.end(),cmp);
    for(int i=0;i<m;i++)
        LinkNodes[edgs[i].u].push_back(i);
    dfs(1);
    printf("\n");
    bfs(1);
}

P3371 单元最短路径(邻接表版本)

主要的思路就是先从一个点开始,然后计算从A到每个点的距离,找到最小的,假设为,把它标记.,然后再把与x相接的边(注意,边的另一边没有被标记)做一次松弛操作,选出最小的标记,以此类推...

  • 选出最小的
  • 标记
  • 松弛
#include <stdio.h>
#include <cstring>
#define N 500005
struct edge{
    int to;
    int weight;
    int next;
}edges[N];
int cnt;
int ans[N];
bool vised[N];
int head[N];
void add(int x,int y,int w){
    edges[++cnt].to=y;
    edges[cnt].weight=w;
    edges[cnt].next=head[x];
    head[x]=cnt;
}
bool songchi(int x,int y,int z){
    return x+y<z;
}
int main(){
    int m,n,s;
    int x,y,w;
    scanf("%d %d %d",&m,&n,&s);
    for(int i=1;i<=m;i++){
        ans[i]=2147483647;
    }
    ans[s]=0;
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&x,&y,&w);
        add(x, y, w);
    }
    int pos=s;
    while(!vised[pos]){
        long long minn = 1145141919810;
        vised[pos]=1;
        for(int i=head[pos];i!=0;i=edges[i].next){
            if(!vised[edges[i].to]&&ans[edges[i].to]>ans[pos]+edges[i].weight){
                ans[edges[i].to]=ans[pos]+edges[i].weight;
            }
        }
        for(int i=1;i<=m;i++){
            if(!vised[i]&&ans[i]<minn){
                pos=i;
                minn=ans[i];
            }
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d ",ans[i]);
    }
    
}

P2910 双倍经验(邻接矩阵版本)

#include<stdio.h>
#include<cstring>
#define N 101
#define M 10005
int a[N][N];
int ans[N];
bool vised[N];
int weizhi[M];
int n,m,w;
int dj(int x,int y){
    int pos=x;
    ans[pos]=0;
    while(!vised[pos]){
        long long minn = 1145141919810;
        vised[pos]=1;
        for(int i=1;i<=n;i++){
            if(vised[i]) continue;
            if(ans[pos]+a[pos][i]<ans[i]){
                ans[i]=ans[pos]+a[pos][i];
            }
        }
        for(int i=1;i<=n;i++){
            if(!vised[i]&&ans[i]<minn){
                pos=i;
                minn=ans[i];
            }
        }
    }
    return ans[y];
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&weizhi[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&w);
            a[i][j]=w;
        }
    }
    int res=0;
    for(int i=2;i<=m;i++){
        memset(vised,false,sizeof(vised));
        for (int i=1;i<=n;i++) {
            ans[i]=1145141919;
        }
        res+=dj(weizhi[i-1],weizhi[i]);
    }
    printf("%d",res);
}

这个版本是进行了多次查找的,其实也差不多...

P3367 并查集(往上搜索的树)

就是对于N个元素,一开始有N个集合,你需要完成若干次集合的合并和判断操作.

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
int temp[10000];
int find(int x){
    while(x!=temp[x]) x=temp[x]=temp[temp[x]];
    return x;
}
int main(){
    int N,M;
    scanf("%d %d",&N,&M);
    int i=1;
    while(i<=N){
        temp[i]=i;
        i++;
    }
    int op,num1,num2;
    while(M--){
        scanf("%d %d %d",&op,&num1,&num2);
        int fa_a=find(num1),fa_b=find(num2);
        if(op==1){
            temp[fa_a]=fa_b;
        }
        else{
            if(fa_a==fa_b){
                printf("Y\n");
            }
            else if(fa_a!=fa_b){
                printf("N\n");
            }
        }
    }
}

我们用temp[x]来表示树的父亲,如果temp[x]=自己的话就代表自己是根,对于若干个集合就相当于若干个树,判断是不是在同一个集合就看属于自己的树是不是根就好了,集合的合并也就是确立父子关系而已,这个相当于把两个树合并在一块.

P3366 最小生成树

Prim算法:每一次选择权值最小的边,然后标记边的终点.并且保证终点是没有被搜索过的.

#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
il int read()
{
    re int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}//快读,不理解的同学用cin代替即可
#define inf 123456789
#define maxn 5005
#define maxm 200005
struct edge
{
	int v,w,next;
}e[maxm<<1];
//注意是无向图,开两倍数组
int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans;
//已经加入最小生成树的的点到没有加入的点的最短距离,比如说1和2号节点已经加入了最小生成树,那么dis[3]就等于min(1->3,2->3)
bool vis[maxn];
//链式前向星加边
il void add(int u,int v,int w)
{
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
//读入数据
il void init()
{
    n=read(),m=read();
    for(re int i=1,u,v,w;i<=m;++i)
    {
        u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);
    }
}
il int prim()
{
	//先把dis数组附为极大值
	for(re int i=2;i<=n;++i)
	{
		dis[i]=inf;
	}
    //这里要注意重边,所以要用到min
	for(re int i=head[1];i;i=e[i].next)
	{
		dis[e[i].v]=min(dis[e[i].v],e[i].w);
	}
    while(++tot<n)//最小生成树边数等于点数-1
    {
        re int minn=inf;//把minn置为极大值
        vis[now]=1;//标记点已经走过
        //枚举每一个没有使用的点
        //找出最小值作为新边
        //注意这里不是枚举now点的所有连边,而是1~n
        for(re int i=1;i<=n;++i)
        {
            if(!vis[i]&&minn>dis[i])
            {
                minn=dis[i];
				now=i;
            }
        }
        ans+=minn;
        //枚举now的所有连边,更新dis数组
        for(re int i=head[now];i;i=e[i].next)
        {
        	re int v=e[i].v;
        	if(dis[v]>e[i].w&&!vis[v])
        	{
        		dis[v]=e[i].w;
        	}
		}
    }
    return ans;
}
int main()
{
    init();
    printf("%d",prim());
    return 0;
}

P3370 字符串哈希

直接使用set<string>就好了,这样就可以保证哈希了

#include<bits/stdc++.h>
using namespace std;
set<string> a;
int main()
{
    string p;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        //输入string只能用cin...
        cin>>p;
        a.insert(p);
    }
    printf("%d",a.size());
}

这样做会不会有点阴啊...

所以说我们可以使用哈希查找:就是把字符串转化成一个整数,然后对整数排序,看看有没有相等的两个数就好了.(代码略)

P1908 逆序对(归并排序)

求一个数组的逆序对数:

这里是用归并的方式:判断左边的逆序对数,右边的逆序对数和跨过两边逆序对数.

为了方便,顺便把左右两边的归并排序也做了(方便统计) 归并排序就是左边归并右边归并,然后归并左右两边(使用双指针,哪边小保存哪边).这个时候可以统计逆序对,只要左边>右边,我们就认为这是一个逆序对.(因为左右已经排好序,我们可以使用线性时间做完).

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define N 1000000
int a[N];
int t[N];
long long ans = 0;
void merge(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,i=l,k=l,j=mid+1;
    merge(l,mid),merge(mid+1,r);
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]){
            t[k++]=a[i++];
        }
        else{
            t[k++]=a[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid)t[k++]=a[i++];
    while(j<=r)t[k++]=a[j++];
    for(int i=l;i<=r;++i)a[i]=t[i];
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    merge(0,n-1);
    printf("%lld",ans);
}

P1309 (双倍经验) 逆序对

N 名编号为 1∼2N 的选手共进行R 轮比赛。每轮比赛开始前,以及所有比赛结束后,都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的,约定编号较小的选手排名靠前。每轮比赛的对阵安排与该轮比赛开始前的排名有关:第1名和第2名、第 3名和第 4名、……、第2K−1名和第2K名、…… 、第2N−1名和第2N名,各进行一场比赛。每场比赛胜者得1分,负者得 0分。也就是说除了首轮以外,其它轮比赛的安排均不能事先确定,而是要取决于选手在之前比赛中的表现。现给定每个选手的初始分数及其实力值,试计算在R 轮比赛过后,排名第Q 的选手编号是多少。我们假设选手的实力值两两不同,且每场比赛中实力值较高的总能获胜。

这个时候我们就可以使用归并排序了.首先将选手进行排序,然后进行比拼.比拼的时候记录胜者和败者.在这个时候由于胜者都+1分,败者都不加分,所以说记录的胜者和败者都是有序的.有序的前提就是方便我们的归并.归并的方式和我们之前做的事一样的.

#include <stdio.h>
#include <algorithm>
#define N 200005
int n,m;
int win[N];
int lose[N];
int s[N];
int a[N];
int p[N];
int R,Q;
bool cmp(int x,int y){
    if(s[x]==s[y]) return x<y;
    else return s[x]>s[y];
}
void merge(){
    int i=1;//the position of win
    int j=1;//the position of lose
    int k=1;
    //我们把win的那一部分和lose的那一部分给归并了,因为我们知道赢的那一部分和输的那一部分是有序的
    while(i<=n/2&&j<=n/2){
        if(cmp(win[i],lose[j])){
            a[k++]=win[i++];
        }
        else{
            a[k++]=lose[j++];
        }
    }
    while(i<=n/2) a[k++]=win[i++];
    while(j<=n/2) a[k++]=lose[j++];
}
int main(){
    scanf("%d %d %d",&n,&R,&Q);
    n*=2;
    for(int i=1;i<=n;i++){
        a[i]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
    }
    std::sort(a+1, a+n+1, cmp);
    while(R--){
        for(int i=1;i<=n;i+=2){
            if(p[a[i]]<p[a[i+1]]){
                s[a[i+1]]++;
                win[(i-1)/2+1]=a[i+1];
                lose[(i-1)/2+1]=a[i];
            }
            else{
                s[a[i]]++;
                win[(i-1)/2+1]=a[i];
                lose[(i-1)/2+1]=a[i+1];
            }
        }
        merge();
    }
    printf("%d",a[Q]);
}

P1090 合并果子

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 n-1次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

本来是想打一个区间dp的,但是发现数据样例有一点大,就直接用优先队列了,在这里记录一下优先队列的用法:

#include<stdio.h>
#include<queue>
int n,x,ans;
std::priority_queue<int,std::vector<int>,std::greater<int>> queue;
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d",&x);
        queue.push(x);
    }
    while(queue.size()/2){
        int a1=queue.top();
        queue.pop();
        int a2=queue.top();
        queue.pop();
        ans += (a1+a2);
        queue.push(a1+a2);
    }
    printf("%d",ans);
}

优先队列可以保证入队的时候按照你规定的cmp函数来执行排序.

P1138 最k小整数

这里就回忆一下sort函数的用法吧~.然后从前到后遍历一遍而已

#include <stdio.h>
#include<algorithm>
int a[10005];
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    std::sort(a+1,a+n+1);
    int temp=0;
    for(int i=1;i<=n;i++){
        if(a[i]>a[i-1]) temp++;
        if(temp==k) {
            printf("%d",a[i]);
            break;
        }
    }
    if(temp<k) printf("NO RESULT");
}

P1918 保龄球

给定,现在给定,求.

就可以使用一个map就可以了:

#include<map>
#include<stdio.h>
using namespace std;
map<int,int>maps;
int n,t,q,m;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&t);
        maps[t]=i;
    }
    scanf("%d",&m);
    while(m--){
        scanf("%d",&q);
        printf("%d\n",maps[q]);
    }
}

 

隐藏