首页 杂记

洛谷刷题记录(2022)

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

题目描述

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

输入格式

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

1、首先构造差分数组.

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

3、然后合并差分数组.

//这个时候还不会stl,甚至还没有养成用宏来开数组的习惯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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,所以说初始的构造差分数组的步骤可以省略/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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 队列安排(队列模版题,包含队列的添加和删除操作)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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));
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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 后缀表达式(栈的经典问题)

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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进去就好了,因为只用处理乘,剩下的堆栈中存放的就是加法的加数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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 日志分析(模拟栈)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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个元素之后第一个大于的下标,求

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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 滑动窗口/单调队列模版.

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

首先是样例:

1
2
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)如果

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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,建立的映射,这个映射的查找是的,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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 填涂颜色(简单深搜)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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](/Users/xupengzhu/Library/Application Support/typora-user-images/image-20220410195828465.png)

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
# 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了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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 美国血统)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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](/Users/xupengzhu/Library/Application Support/typora-user-images/image-20220410211808841.png)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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， 与由根向叶结点方向（下行方向）时的边数之和。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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 二叉树深度

求二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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就是维护一个栈,栈的表示就是递归,搜索没有遍历过且链接的东东,找到就立刻跳转.对新结点进行搜索.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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相接的边(注意,边的另一边没有被标记)做一次松弛操作,选出最小的标记,以此类推…

  • 选出最小的
  • 标记
  • 松弛
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    #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 双倍经验(邻接矩阵版本)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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个集合,你需要完成若干次集合的合并和判断操作.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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算法:每一次选择权值最小的边,然后标记边的终点.并且保证终点是没有被搜索过的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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>就好了,这样就可以保证哈希了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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 逆序对(归并排序)

求一个数组的逆序对数:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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 (双倍经验) 逆序对

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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的,但是发现数据样例有一点大,就直接用优先队列了,在这里记录一下优先队列的用法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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函数的用法吧~.然后从前到后遍历一遍而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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就可以了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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]);
    }
}

P6510 奶牛排队

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

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

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

  • 首先确定B,B左侧第一个大于B的数位.
  • 然后确定A,A从K+1开始遍历,然后判断A右侧第一个小于A的位置是不是在B右边
  • 计算值B的位置-A的位置+1.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #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…aaa…aaa…a的，化简结果为“”两边a的个数最多的一项，例如aaaaaa=aaa 2、先算带括号的序列，例如(aa)aaa=aaa

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

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

P1185 绘制二叉树

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

首先是初始化的操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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个元素.

1
2
3
4
5
6
7
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(画布的行,画布的列,树的行,树的列,下一个点的类型)

1
2
3
4
5
6
7
8
9
10
11
12
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是计算左儿子和右儿子在模拟数组中的值.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);
    }
}

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

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

P3956 棋盘

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

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

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

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

  • 遍历所有带颜色的点,如果两个点相邻,这两个点之间的距离就是0和1.
  • 如果这两个点只差了一格,那么距离就是2+0或者1.
  • 假如说终点是没有颜色的,加上所有点到终点的边.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    #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的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）,现在给定了若干个停靠的关系,现在求最多有几级?

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

首先是建图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 神经网络

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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，若最左边的单词不想背，或后文已出现就更新，把长度去最短即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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);
}

P1002 [NOIP2002 普及组] 过河卒

dp方程:因为小兵只能往下或者右走,我们设一个二维dp数组dp[i][j]表示从起点到坐标为(i,j)的路径数,如果这个点能被马能吃掉的,那就dp[i][j]=0,这个可以告诉它下面和右边的点,我这是不能到达的.然后输出dp[N][M]就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include&lt;stdio.h>
#include&lt;iostream>
#include&lt;algorithm>
#include&lt;vector>
#include&lt;stack>
#include &lt;math.h>
using namespace std;
#define N 40
int t[N];
int a[N][N];
long long dp[N][N];
bool beimalanzhu[N][N]; //判断这个点有没有马拦住
const int madex[] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int madey[] = {1, 2, 2, 1, -1, -2, -2, -1};
int c,n;
//long long count(long long a,long long b,long long p){
//    if(b==0) return 1;
//    if(b==1) return a%p;
//    long long c = count(a,b/2,p)%p;
//    return ((b%2==0?1:a)\*c\*c)%p;
//}

int main(){
    int ma_x,ma_y;
    int b_x,b_y;
    scanf("%d %d %d %d",&amp;b_x,&amp;b_y,&amp;ma_x,&amp;ma_y);
    ma_x+=2;
    ma_y+=2;
    b_x+=2;
    b_y+=2;
    
    dp[2][1]=1;
    for(int i=0;i&lt;8;i++){
        beimalanzhu[ma_x+madex[i]][ma_y+madey[i]]=true;
    }
    //忘记讨论马自己了
    beimalanzhu[ma_x][ma_y] = true;
    for(int i=2;i&lt;=b_x;i++){
        for(int j=2;j&lt;=b_y;j++){
            if(beimalanzhu[i][j]) continue;
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    printf("%lld",dp[b_x][b_y]);
}

P1095 [NOIP2007 普及组] 守望者的逃离

这个其实我们都知道,根据中学物理的知识都知道我们瞬移最好,但是有这么一种情况,就是你瞬移没蓝了,但是终点离你不远,这时候还不如直接开跑,等在这里等蓝还不如直接run
这个时候就有个最优选择了:维护一个一维的dp数组dp[T]来表示到t时间最远能run多远,那我们假设一个dp[t],dp[1,….t-1]都是已知的了,那就可以维护了dp[t]=max[dp[t-1]+17,r[t]],r[t]就代表一直瞬移的距离,如果这个时候一直瞬移还不如现在直接跑来得快,那就选跑

对于这位可怜的人,一直闪现肯定是最优解,但是这里dp其实判断的是,对于这个时刻,没有蓝了,是停在原地回蓝好还是直接撒腿就跑好,是判断这俩的选择的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include&lt;stdio.h&gt;
#define N 300005
int dp[N];
int main(){
    int M,S,T;
    scanf("%d %d %d",&amp;M,&amp;S,&amp;T);
    dp[0]=0;
    int run;
    int flash;
    for(int i=1;i&lt;=T;i++){
        if(M&gt;=10) {
            dp[i]=dp[i-1]+60;
            M-=10;
        }
        else{
            dp[i]=dp[i-1];
            M+=4;
        }
        
    }
    for(int i=1;i&lt;=T;i++){
        if(dp[i]&lt;dp[i-1]+17) dp[i]=dp[i-1]+17;
        if(dp[i]&gt;S){
            printf("Yes\\n%d",i);
            return 0;
        }
    }
    printf("No\\n%d",dp[T]);
    
}

背包

P1048 [NOIP2005 普及组] 采药

动态规划方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include "iostream"
#include "stdio.h"
using namespace std;
int  weigth[105],value[105];
//dp[i][j]代表处理第i个,背包容量还剩下j个
int dp[105][1005];
int total,m;

int main(){
    scanf("%d %d",&amp;total,&amp;m);
    for(int i=1;i&lt;=m;i++){
        scanf("%d %d",&amp;weigth[i],&amp;value[i]);
    }
    for(int i=1;i&lt;=m;i++){
        for(int j=total;j&gt;=0;j--){
            //表示这个元素可以选入
            if(j&gt;=weigth[i]){
                dp[i][j]=max(dp[i-1][j-weigth[i]]+value[i],dp[i-1][j]);
            }
            //不可以
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    printf("%d",dp[m][total]);
}

P1616 疯狂的采药

一维dp数组,dp[m]代表用m的背包就可以获得的最大元素,还是两层循环,外循环是对物品种类进行讨论,内循环对dp方程进行处理,看看对于一个重量$j$,我要不要选择第$i$号元素放入背包中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>;
#include<iostream&gt;
#include<algorithm&gt;
using namespace std;
const int M = 1e7+5;
long long  weigth[M],value[10005];
//dp[i][j]代表处理第i个,背包容量还剩下j个
long long dp[M];
long long total,m;

int main(){
    scanf("%lld %lld",&amp;total,&amp;m);
    for(int i=1;i&lt;=m;i++){
        scanf("%lld %lld",&amp;weigth[i],&amp;value[i]);
    }
    for(int i=1;i&lt;=m;i++){
        for(int j=weigth[i];j&lt;=total;j++){
            dp[j]=max(dp[j],dp[j-weigth[i]]+value[i]);
        }
    }
    printf("%lld",dp[total]);
}

线性

P1091 [NOIP2004 提高组] 合唱队形

这是一个脑筋急转弯类型的题目,第一步就是计算[1,i]的最长上升子序列的长度,记在dp[i][0]中,第二步就是计算[i,n]的最长下降子序列的长度,记在dp[i][1].但是有一点就是这个最长上升子序列长度是要包括自己的.
记dp1[i]=dp[i][0]+dp[i][1]
最后的结果就是需要找到一个点使得dp1[i]最大,这样就代表这个点左右更加光滑.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include&lt;stdio.h&gt;
#define N 105
int a[N];
int dp[N][2];
int res[N];
//dp数组,dp[i][0]
int main(){
    int n;
    scanf("%d",&amp;n);
    for(int i=1;i&lt;=n;i++){
        scanf("%d",&amp;a[i]);
        
    }
    //从左到右扫描
    for(int i=2;i&lt;=n;i++){
        for(int j=1;j&lt;i;j++){
            if(a[i]&gt;a[j]&amp;&amp;dp[i][0]&lt;=dp[j][0]+1){
                dp[i][0]=dp[j][0]+1;
            }
        }
    }
    for(int i=n-1;i&gt;=1;i--){
        for(int j=i+1;j&lt;=n;j++){
            if(a[i]&gt;a[j]&amp;&amp;dp[i][1]&lt;=dp[j][1]+1){
                dp[i][1]=dp[j][1]+1;
            }
        }
    }
    int result=0;
    for(int i=1;i&lt;=n;i++){
        res[i]=dp[i][0]+dp[i][1]+1;
        if(res[i]&gt;result) result=res[i];
    }
    printf("%d",n-result);
}

P1439 【模板】最长公共子序列

排列中没有重复元素，俩排列置换后 (重命名) 的 LCS 长度不变:不妨用置换$\sigma$将排列$P_1$$\to$[1:n].

这个时候我们可以将排列$P_1$变成[1,2,3,….,n]然后排列$P_2$映射成与$P_1$相匹配的形式.排列$P_2$中第$i$个元素存储的就是原来的元素在$P_1$中的位置 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include&lt;stdio.h&gt;
#include&lt;algorithm&gt;
#define N 100005
using namespace std;
int a[N],b[N],c[N],found[N];
int main(){
    int n;
    scanf("%d",&amp;n);
    for(int i=1;i&lt;=n;i++){
        scanf("%d",&amp;a[i]);
        c[a[i]]=i;
    }
    for(int i=1;i&lt;=n;i++){
        scanf("%d",&amp;b[i]);
        found[i]=114514;
    }
    int LCS_length=0;
    for (int i=1; i&lt;=n; i++) {
        int l=0,r=LCS_length,mid;
        //如果大于:直接放在后面
        if(c[b[i]]&gt;found[LCS_length]){
            found[++LCS_length]=c[b[i]];
        }
        //如果小于二分查找
        else{
            while (l&lt;r) {
                mid=(l+r)/2;
                if(found[mid]&gt;c[b[i]]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            found[l]=min(c[b[i]],found[l]);
        }
    }
    printf("%d\\n",LCS_length);
}

P1880 [NOI1995] 石子合并

让dp[i][j]代表第i堆到第j堆的合并分数,我们要做的事$dp[i][i+n-1]$最大(小),只需要在区间[i][j]中找到一个最佳的分划k,让i-k,k+1,j这两个区域内部得分和合并这两个区域的得分最大(小),即$max(a[i][k]+a[k+1][j]+d(i,j))$分别代表两个区域的分划和合并两部分的得分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
#include<algorithm>
#define N 205
int mins[N][N];
int maxs[N][N];
int stones[N];
int sums[N];//前缀和
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&stones[i]);
        sums[i]=sums[i-1]+stones[i];
        stones[i+n]=stones[i];
    }
    for(int i=n+1;i<=2\*n;i++){
        sums[i]=sums[i-1]+stones[i];
    }
    for(int length=1;length<n;length++){
        for(int i=1,j=i+length;j<2\*n&&i<2\*n;i++,j=length+i){
            mins[i][j]=1145141919;
            for(int k=i;k<j;k++){
                maxs[i][j]=std::max(maxs[i][j],maxs[i][k]+maxs[k+1][j]+sums[j]-sums[i-1]);
                mins[i][j]=std::min(mins[i][j],mins[i][k]+mins[k+1][j]+sums[j]-sums[i-1]);
            }
        }
    }
    int min_res=114514;
    int max_res=0;
    for(int i=1;i<=n;i++){
        max_res=std::max(max_res,maxs[i][i+n-1]);
        min_res=std::min(min_res,mins[i][i+n-1]);
    }
    printf("%d\\n%d",min_res,max_res);
}

5.6 解码异或后的数组

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        int n=encoded.size()+1;
        vector<int> arr(n);
        arr[0]=first;
        for (int i=1; i<n; i++) {
            arr[i]=arr[i-1]^encoded[i-1];
        }
        return arr;
    }
};

异或是满足交换律和结合律的,就是x和y异或=z,已知x和z,y是能求出来的!

5.7 数组的异或操作:这个不想说了,太简单了

5.8 完成工作的最短时间
这道题我犯了四个很低级的错误:
1.二分查找的时候没有更新mid
2.传参数没有传引用,导致所有的结果都没变
3.判断能否完成的时候没有考虑刚好完成所带来
4.工作时间加了之后,如果判断不行没减回去
给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1：
输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题是一道搜索类型的题目,是一道直接搜索答案的题目,总的思路就两点
1.主函数做二分搜索
2.子函数验证这个结果对不对,来帮助主函数做二分搜索

这道题要注意一点,要不然时间这一块把握不住
1.建议使用贪心算法,就是把大的任务先安排下去
2.在任务已经明确不能完成或者说是一定能够完成的情况下自动退出

判断的方法也稍微提一下:就是给每个工人分配任务,分配任务的形式就是更改一个数组,这个数组存放了每个工人工作的总时间,分配就是依据每个总时间进行分配的,分配的方式就是递归,有一步出现问题就返回报错,到达叶节点(分配完成)就返回OK

如果有思路,写出代码来还是很简单的,这一种题真的和滑动窗口很像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        sort(jobs.begin(), jobs.end(), greater<int>());
        int first = jobs[0], total = accumulate(jobs.begin(), jobs.end(), 0);
        //没有达到最优解
        while(first<total){
            //检查一下mid行不行
            int mid = (first+total)/2;
            if(ok(jobs,k,mid)){
                total=mid;
            }
            else{
                first=mid+1;
            }
        }
        return first;
    }
    bool ok(vector<int>& jobs, int k, int value){
        vector<int> workers(k,0);
        return check(jobs,workers,0,value);
    }
    //递归寻找
    bool check (vector<int>& jobs,vector<int> workers, int now,int value){
        if(jobs.size()<=now){
            return true;
        }
        else{
            int cur=jobs[now];
            for (auto& workload : workers) {
                if (workload+cur<=value) {
                    workload+=cur;
                    if (check(jobs,workers,now+1,value)) {
                        return true;
                    }
                    workload-=cur;
                }
                if (workload==0workload+cur==value) {
                    break;
                }
            }
            return false;
        }
        
    }
};

5.9 制作花束的最少天数
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

示例 1：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, , , , ] // 只能制作 1 束花
2 天后：[x, , , , x] // 只能制作 2 束花 3 天后：[x, , x, _, x] // 可以制作 3 束花，答案为 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题的思路和昨天的其实很像,就说说判断在某一天之内能否生产那么多花束的思路:其实就是一个遍历+模拟就可以完成的,就是假设这一天已经来到,看看有哪些花盛开了.就取哪些花,有连续的几朵就可以组成一个花束,这么简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if(bloomDay.size()<m\*k){
            return -1;
        }
        int high=0,low=INT_MAX;
        for (int i = 0; i < bloomDay.size(); i++) {
            low=min(low, bloomDay[i]);
            high=max(high, bloomDay[i]);
        }
        
        while(high>low){
            int mid=(high+low)/2;
            if(check(bloomDay,m,k,mid)){
                high=mid;
            }
            else{
                low=mid+1;
            }
        }
        return low;
    }
    bool check(vector<int>& bloomDay, int m, int k,int days){
        int hua=0,huashu=0;
        for(int i=0;i<bloomDay.size()&&huashu<m;i++){
            if(bloomDay[i]<=days){
                hua++;
                if(hua==k){
                    huashu++;
                    hua=0;
                }
            }
            else{
                    hua=0;
            }
        }
        return huashu>=m;
    }   
};

上面两题向我们展示了一个利用二分搜索搜索答案的思路:
1.主函数二分搜索
2.子函数验证
众所周知,求解比验证难许多

5.10 叶子相似的树

前序遍历就可以了.前序遍历能保证叶子是从左到右被遍历到的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool leafSimilar(TreeNode\* root1, TreeNode\* root2) {
        vector<int> a1;
        vector<int> a2;
        if(root1) forwardTraverse(root1,a1);
        if(root2) forwardTraverse(root2,a2);
        return a1==a2;
    }
    void forwardTraverse(TreeNode\* root,vector<int>&list){
        if(!(root->left)&&!(root->right)){
            list.push_back(root->val);
            return;
        }
        if(root->left) forwardTraverse(root->left,list);
        if(root->right) forwardTraverse(root->right,list);
        return;
    }
};

5.11 解码异或后的排列
给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。
它被加密成另一个长度为 n – 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。
给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。
示例 1：
输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
示例 2：

之前我们就做过异或之后的数组怎么解码:最重要的就是寻找到那个first元素,这里我们也可以寻找到first元素

我们知道x\lxor x=0,那我们寻找到第一个元素,就是(x_0\oplus x_1\oplus x_2...\oplus x_n)\oplus (x_1 \oplus x_2\oplus x_3....x_n)=x1

我们还知道encode[2k+1]=a[2k]\oplus a[2k+1]刚好对所有奇数元素的数列一异或就可以把上述式子异或符号右边的元素求出来

注意,原来的数据是从1-n的排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> decode(vector<int>& encode) {
        int n=encode.size()+1;
        vector<int> decode(n,0);
        int total=0;
        int except_0=0;
        for(int i=0;i<=n;i++){
            total=total^i;
        }
        for(int i=1;i<n;i+=2){
            except_0=except_0^encode[i];
        }
        decode[0]=except_0^total;
        for(int i=1;i<n;i++){
            decode[i]=decode[i-1]^encode[i-1];
        }
        return decode;
    }
};

5.12 字数组异或查询
有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。
对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。
并返回一个包含给定查询 queries 所有结果的数组。
示例 1：
输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
数组中元素的二进制表示形式是：
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xor-queries-of-a-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一个式子就可以明白:这里截取官方题解了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> result;
        vector<int> xors(arr.size()+1);
        for (int i=0;i<arr.size();i++) {
            xors[i+1]=xors[i]^arr[i];
        }
        for(vector<int>temp:queries){
            int total=0;
            total=xors[temp[0]]^xors[temp[1]+1];
            result.push_back(total);
        }
        return result;
    }
};

5.13 停在原地的方案数
有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。
每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。
由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。
示例 1
输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    const int MODULO = 1000000007;
    int numWays(int steps, int arrLen) {
        int maxc=min(arrLen-1,steps/2);
        vector<vector<int>> dp(steps+1, vector<int>(maxc+1));
        dp[0][0]=1;
        for(int i=1;i<=steps;i++){
            for(int j=0;j<=maxc;j++){
                dp[i][j]=dp[i-1][j];
                if(j-1>=0){
                    dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MODULO;
                }
                if(j+1<=maxc){
                    dp[i][j]=(dp[i][j]+dp[i-1][j+1])%MODULO;
                }
                
            }
        }
        return dp[steps][0];
    }
};

动态规划:dp[行动的步数][获得的这个结果]=走的方案数
官方题解还可以优化,比如说压缩到一维动态规划
动态规划最重要的就是:初态+状态转移,这里的初态:
dp[0][0]=1,dp[0][i]=0,状态转移:来源于三个操作:一个是向左,一个是向右,一个是不动:dp[i][j]=dp[i-1][j]+dp[i-1][j+1]+dp[i-1][j-1](if j+1,j-1 exists)

5.14 整数转罗马数字
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

变相的数位转换罢了,注意的是1000-900-500-400-100-90-50-40-10-9-5-4-1这套转化法则,一开始就是没反应过来23333

5.15 罗马数字转整数

还是一样的,读取罗马数字,如果下一个罗马数字对应的值比我这个大,那么说明应该是IX之类的问题,就要减去这个罗马数字对应的值如果小,就加这个罗马数字对应的值就行

5.16 数组中最大的异或值

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

这个代码是题解里面的

第一种方法是贪心算法,就是我们已经知道x=a_i \oplus a_j所以说我们就假设x,然后找有没有适合的a_i和a_j就好了,我们按位查找,从高位到低位查找:
首先看最高位有没有a_i\oplus a_j=x有的话就取1:就是2x+1没有的话就取0,就是2x,以此类推

第二种方法就是字典法:

这个是一个字典树,每个元素从高位到低位按照0和1的顺序建立树
当检查x的最大性的时候的做法:
因为要让异或最大,那就读取一个数,从高位到低位判断,如果这个位为0,那就看看这个位有没有位1的数,反之亦然.有的话异或的值就可以2x+1,没有的话就是2x

这里需要说明一下二进制的求值方法:从高位到低位扫描,扫描到1的话2y+1,扫描到0的时候就为2y

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
struct Trie {
    // 左子树指向表示 0 的子节点
    Trie\* left = nullptr;
    // 右子树指向表示 1 的子节点
    Trie\* right = nullptr;

    Trie() {}
};

class Solution {
private:
    // 字典树的根节点
    Trie\* root = new Trie();
    // 最高位的二进制位编号为 30
    static constexpr int HIGH_BIT = 30;

public:
    void add(int num) {
        Trie\* cur = root;
        for (int k = HIGH_BIT; k >= 0; --k) {
            int bit = (num >> k) & 1;
            if (bit == 0) {
                if (!cur->left) {
                    cur->left = new Trie();
                }
                cur = cur->left;
            }
            else {
                if (!cur->right) {
                    cur->right = new Trie();
                }
                cur = cur->right;
            }
        }
    }

    int check(int num) {
        Trie\* cur = root;
        int x = 0;
        for (int k = HIGH_BIT; k >= 0; --k) {
            int bit = (num >> k) & 1;
            if (bit == 0) {
                // a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
                if (cur->right) {
                    cur = cur->right;
                    x = x \* 2 + 1;
                }
                else {
                    cur = cur->left;
                    x = x \* 2;
                }
            }
            else {
                // a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
                if (cur->left) {
                    cur = cur->left;
                    x = x \* 2 + 1;
                }
                else {
                    cur = cur->right;
                    x = x \* 2;
                }
            }
        }
        return x;
    }

    int findMaximumXOR(vector<int>& nums) {
        int n = nums.size();
        int x = 0;
        for (int i = 1; i < n; ++i) {
            // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
            add(nums[i - 1]);
        }
        for (int i = 1; i < n; ++i){
            // 将 nums[i] 看作 ai，找出最大的 x 更新答案
            x = max(x, check(nums[i]));
        }
        return x;
    }
};

5.17 二叉树的堂兄弟节点

这个东西就是做一遍二叉树的遍历,找到:层数+父节点,比较就行了.传参数比较麻烦的话就开全局变量就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {
public:
    // x 的信息
    int x;
    TreeNode\* x_parent;
    int x_depth;

    // y 的信息
    int y;
    TreeNode\* y_parent;
    int y_depth;

    void level1(TreeNode\* root,int x,int k){
        if(!root){
            return;
        }
        if(root->val==x){
            x_depth=k;
        }
        if(root->left){
            level1(root->left,x,k+1);
        }
        if(root->right){
            level1(root->right,x,k+1);
        }
        return;
    }
    void level2(TreeNode\* root,int y,int k){
        if(!root){
            return;
        }
        if(root->val==y){
            y_depth=k;
        }
        if(root->left){
            level2(root->left,y,k+1);
        }
        if(root->right){
            level2(root->right,y,k+1);
        }
        return;
    }
    void parent2(TreeNode\* root,int y){
        if(!root){
            return;
        }
        if(root->right&&root->right->val==y){
            y_parent=root;
        }
        if(root->left&&root->left->val==y){
            y_parent=root;
        }
        if(root->left){
            parent2(root->left,y);
        }
        if(root->right){
            parent2(root->right,y);
        }
        return;
    }
    void parent1(TreeNode\* root,int x){
        if(!root){
            return;
        }
        if(root->right&&root->right->val==x){
            x_parent=root;
        }
        if(root->left&&root->left->val==x){
            x_parent=root;
        }
        if(root->left){
            parent1(root->left,x);
        }
        if(root->right){
            parent1(root->right,x);
        }
        return;
    }
    bool isCousins(TreeNode\* root, int x, int y) {
        parent1(root,x);
        parent2(root,y);
        level1(root,x,0);
        level2(root,y,0);
        return (x_depth==y_depth)&&(x_parent!=y_parent);
    }
};

5.18 形成两个异或相等的三元组数目

给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

还是那张图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int ans=0;
        int count=arr.size();
        vector<int> abab(count+1);
        for(int i=0;i<count;i++){
            abab[i+1]=abab[i]^arr[i];
        }
        for(int i=0;i<count;i++){
            for(int j=i+1;j<count;j++){
                for(int k=j;k<count;k++){
                    if(abab[i]==abab[k+1]){
                        ++ans;
                    }
                }
            }
        }
        return ans;
    }
};

5.19 找出第K大的异或坐标值

最近力扣是和这个公式杠上了么…,这道题就是一个模拟就行的了,但是我们可以建表来记录(m,k)之内的元素异或的和,这三项刚好可以表示

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
示例 1：
输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

更新于

请我喝[茶]~(￣▽￣)~*

Sukuna 微信支付

微信支付

Sukuna 支付宝

支付宝