杂题记录

部分解题思路源自好友：therainisme

2021.4.25 dfs

判断是否为相同的树

image-20210425084822276

解题思路：采用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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
       if(p == nullptr && q == nullptr)
           return ture;
       else if(p == nullptr || q == nullptr)
           return false;
       else if(p->val != q->val)
           return false;
        else{
            return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
        }
    }
};

货物摆放(暴力)

image-20210429084516138

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import math
n = 2021041820210418
res = []
for i in range(1,int(math.sqrt(n)+1)):
    if n%i == 0:
        res.append(int(i))
        res.append(int(n/i))
res = set(res)
ans = 0
for i in res:
    for j in res:
        for k in res:
            if i*k*j == n:
                ans+=1
                # print(i," ",j," ",k)
print(ans)

毕竟是填空题，思路也是暴力，就是因数组合法，python永远滴神

结果为2430

Dijkstra求最短路径

题目描述：

​ Dijkstra求最短路 I

image-20210501102812583

解题思路：

变量定义：

1
2
3
int g[a][b] 表示从a到b的距离
int dist[i]  表示从1到i的最短距离
bool st[i]   表示从1到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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
// 存储图的邻接矩阵
int g[N][N];
// 起点到n的最短路径
int dist[N];
// 第n个点是否已经有最短路径
bool st[N];
// 终点和边的数量
int n,m;
void d(){
    // 给dist的初值最大化
    memset(dist,0x3f,sizeof dist);
    // 初始化起点到自己的最短距离
    int now = 1;
    dist[now] = 0;
    st[now] = true;
    // 遍历n-1次
    for(int i =1;i<n;i++){
        for(int j= 1;j<=n;j++){
            // 比较上一个节点到这个节点的距离是否比局部最小距离小
            dist[j] = min(dist[j],dist[now]+g[now][j]);
        }
        // 选出最小距离点
        now = -1;
        for(int j = 1;j<=n;j++){
            // 当前点还没有1最小距离，但是必须有一个，当前的点是不是比第j个节点大
            if(st[j] == false &&(now == -1 || dist[now] > dist[j]))
                now = j;
        }
        // 已经找到了最小距离，做个标记
        st[now] = true;
    }
}
int main(){
    cin>>n>>m;
    // 给图赋最大化初值
    memset(g,0x3f,sizeof g);
    // 输入边进入邻接矩阵中
    for(int i =0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        // 有重边就选择最小的那一条，没有就选择输入的
        // 自环的话仍然是无穷大
        g[a][b] = min(g[a][b],c);
    }
   	// 开始Dijkstran算法
    d();
    // 当前的值最大的话，就输出-1
    if(dist[n] == 0x3f3f3f3f)
        cout<<"-1";
   // 否则输出最小距离
    else
        cout<<dist[n];
}

网络延迟问题

主要思想是floyd算法

网路延迟问题

问题描述：

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

解题思路：

根据题目要求，即需要求出任意一个点到所有点的最短路径中的最大值，如果到不了全部的点就返回-1。

从这题上看，可以才用dijkstra算法和floyd算法，本次才用floyd解法，

floyd使用的图

1
g[i][j] = c 表示从i到j的最短距离为c

floyd核心思想就是对于一条路径a->b，长度为d1，是否存在一条路径a->c->b，长度为d2，使得d1>d2。

这里算法的时间复杂度为O(n3)O(n^3),空间复杂度为O(n2)O(n^2)

AC代码：

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
class Solution {
public:
   	// 定义最大值
    static const int INF = 1e9;
    // 定义图的最大顶点数
    static const int N = 130;
    // 声明图的邻接矩阵
    int g[N][N];
    // floyd算法：是否存在中间点使得这条路径的权值比直接到达的路径短
    void floyd(int n){
        // 先遍历外层节点，即中间节点
        for(int t = 1;t<=n;t++){
            // 然后随机选两个点
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=n;j++){
                    // 选出直达或过中间点最小的那个路径
                    g[i][j] = min(g[i][j],g[i][t]+g[t][j]);
                }
            }
        }
    }
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // 对图进行初始化
       for(int i =1;i<=n;i++){
           for(int j = 1;j<=n;j++){
               // 自己到自己为0否则为无穷大
               if(i==j)
                    g[i][j] = 0;
                else
                    g[i][j] = INF;
           }
       }
       // 给图输入数据
       for(vector i: times){
           // 避免重边和自环
           // 重边选择的是最小的那一条边
           g[i[0]][i[1]] = min(g[i[0]][i[1]],i[2]);
       }
       // 使用floyd算法
       floyd(n);
        // 用于记录最大时长
        int max_time = -1;
        // g[i][j]表示的是从i点到j点的最短路径长度
        // 所以只用n遍历第k行的数据即可
        for(int i = 1;i<=n;i++){
           if(g[k][i] > max_time)
            max_time = g[k][i];
       }
        // 权值可能存在负边，没有边的情况不一定是INF,所以y除以2避免漏洞。
       if(max_time > INF/2)
            return -1;
        else
            return max_time;
    }
};

链接所有点最小费用

最小生成树的应用，这里采用的是kruskal

链接所有点最小费用

题目描述:

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

1
2
输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20

解题思路：

首先要给任意两点之间计算距离构造图，这个图是无向图

对所有边按照权值进行排序

每次取出一条边

使用并交集确认两个点是否能构成回路

如果不构成回路就作为生成树的一条边，并添加权值。

否则

就跳过

ps:效率有点拉跨，主要是为了熟悉kruskal这题力推Prime

AC代码：

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
class Solution {
public:
    static const int N = 500555;
    // 选中的边数，和当前的权值
    int cnt,res;
    // 寻找父节点
    int father[N];
    // 边的数量
    int count;
    // 点的数量
    int l;
    struct Edge{
        // 起点，终点，权值
        int a,b,w;
        // 重新定义比较符号，因为后面要进行排序
        bool operator < (const Edge &e) const{
            return w < e.w;
        }
    }edges[N];
    // 计算他们的曼哈顿距离
    int caculate_distance(vector<int> a,vector<int> b){
        return abs(a[0] - b[0]) + abs(a[1]-b[1]);
    }
    // 并查集模板
    int find(int x){
        if(father[x] != x)
            return find(father[x]);
        return father[x];
    }
    // kruskal
    int kruskal(){
        // 对所有边进行排序
        sort(edges,edges+count);
        // 初始化并查集
        for(int i =0;i<l;i++){
            father[i] = i;
        }
        // kruskal
        for(int i =0;i<count;i++){
            int a = edges[i].a;
            int b = edges[i].b;
            // 找出他们属于哪个集合
            a = find(a);
            b = find(b);
            // 如果他们没有n形成回路就加上去
            if(a != b){
                res+= edges[i].w;
                cnt++;
                if(cnt == l-1)
                    return res;
                father[a] = b;
            }
        }
        return res;
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        l = points.size();
        // 找出所有的边
        for(int i =0;i<l;i++){
            for(int j = i+1;j<l;j++){
                if(i != j)
                    // 找出所有的边
                    edges[count++] ={i,j,caculate_distance(points[i],points[j])};
            }
        }
        // kurukal计算
        res = kruskal();
        return res;
    }
};

small-k问题：选择第k小的数

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 <stdio.h>

int select(int *a, int l, int r,int k) {
    /*  a数组，l左索引，r右索引，找第k小的数
     * 借助快排的思想
     *  取出第一个数字，使得他左边的数字都比他小，右边的数字都比他大
     *  递归出口：
     *  计算index=当前他左边的数字个数+1（他自己是第几大）
     *  1. 如果等于k，直接返回这个数字
     *  2. 如果k大于index，选择他右边的部分进行递归
     *  3. 如果k小于index,选择他左边的部分进行递归
     */
    int i, j, temp;
//    把选中的数放入中间
    temp = a[l];
    i = l;
    j = r;
    while (i < j) {
        while (i < j && a[j] > temp)
            j--;
        if (i < j)
            a[i++] = a[j];
        while (i < j && a[i] < temp)
            i++;
        if (i < j)
            a[j--] = a[i];
    }
    a[i] = temp;
//    自己是第几大
    int index = i+1;
//    开始递归
    if(index == k)
        return a[i];
    else if(index < k)
        select(a, i+1,r,k);
    else
        select(a, l, i-1,k);
}

int main(){
    int S[] = {1,9,4,6,7,3,0,10,2,8};
    int n = 10;
    printf("%d",select(S,0,n-1,5));
    return 0;
};

计算有多少条直线（暴力）

问：x方向上有20个点，y方向上有21个点。即x是0到19之间的整数，y是0到20之间的整数。这些点一共确定了多少条不同的直线？

  1. 斜率和截距各不相同的线为不同的直线
  2. 有斜率不存在的情况
  3. 只要∣k1−k2∣>1e−8|k1 - k2|>1e-8则默认其不同
  4. 答案：40257

实现代码

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 <bits/stdc++.h>
using namespace std;
const int N = 200000;
// 存放线的斜率与截距
pair<double, double> lines[N];
// 定义网格
int x = 20, y = 21;
// 当前有的线条数
int n;
int main()
{
    // 遍历任意两个点
    for (int x1 = 0; x1 < x; x1++)
        for (int y1 = 0; y1 < y; y1++)
            for (int x2 = 0; x2 < x; x2++)
                for (int y2 = 0; y2 < y; y2++)
                {	// 如果斜率存在
                    if (x1 != x2)
                    {
                        double k = (double)(y2 - y1) / (x2 - x1);
                        double b = k * x1 - y1;
                        lines[n++] = {k, b};
                    }
                }
    // 因为每次都会进行两条线比较，如果不同，则应该有2条线，所以初值应该默认至少有一条
    int res = 1;
    sort(lines, lines + n);
    for (int i = 0; i < n - 1; i++)
    {
        // 如果斜率或截距不相同就++
        if (abs(lines[i].first - lines[i + 1].first) > 1e-8 || abs(lines[i].second - lines[i + 1].second) > 1e-8)
            res++;
    }
    // 别忘了还有斜率不存在的情况
    cout << res + x << endl;
}

路径

一个图有2021个结点构成，依次编号1至2021。如果两个结点的绝对值之差大于21，则它们之间没有边相连。否则存在一条权值为它们最小公倍数的无向边。

现在问你，结点1和结点2021之间的最短路径长度是多少？

  1. 暴力floyd简单，就是算得久
  2. 答案：10266837

代码：

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 <bits/stdc++.h>
using namespace std;
const int N = 3000;
// 图，g[i][j]表示i->j的最小距离
int g[N][N];
int n = 2021;
// 最大公约数
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
// floyd算法
void floyd()
{
    for (int t = 1; t <= n; t++)
    {
        cout << t << endl; // 防止自己怀疑人生
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                g[i][j] = min(g[i][j], g[i][t] + g[t][j]);
            }
        }
    }
}

int main()
{
    // 初始化图
    memset(g, 0x3f, sizeof g);
    // 计算边
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j && abs(i - j) <= 21)
            {
                int w = i * j / gcd(i, j);
                g[i][j] = min(g[i][j], w);
            }
        }
    }
    floyd();
    cout << g[1][n];
    return 0;
}

砝码称重问题

image-20210506114733659

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
#include <bits/stdc++.h>
using namespace std;
const int N = 200020,M =110;
// dp[i][j]表示，前i个砝码中是否能凑出重量为j的结果，对应的值1为可以，0为不可以
int dp[M][N];
// 物品的重量
int w[M];
// 砝码数量，最大质量，方案数
int n, m, cnt;
int main()
{
    cin >> n;
    // 在输入的同时记录，能称的物品的最大重量
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        m += w[i];
    }
    // 当0个砝码装0的质量时a显然可行
    dp[0][0] = 1;
    // 每次选前i个砝码，遍历所有质量判断是否能够凑出来
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            /*
                （1）dp[i-1][j]          表示不用这个砝码也能凑出来
                （2）dp[i-1][w[i]+j]     当前i-1个砝码提供的质量，大于第i个砝码时，前i-1个砝码和第i个砝码不在同一侧
                （3）dp[i-1][w[i]-j]     当前i-1个砝码提供的质量，小于第i个砝码时，前i-1个砝码和第i个砝码不在同一侧
                （4）dp[i-1][j-w[i]]     前i-1个砝码和第i个砝码在同一侧
                因为减法会出现负数的情况，所以把(3)(4)的情况统合成dp[i-1][abs(j-w[i])]即可
            */
            dp[i][j] = dp[i - 1][j] || dp[i - 1][w[i] + j] || dp[i - 1][abs(j - w[i])];
        }
    for (int i = 1; i <= m; i++)
    {
        if (dp[n][i])
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

只出现一次的数字

只出现一次的数字

image-20210506162834206

这题简单的，我们都知道任意两个相同的数做异或都会变成0，而且与进行异或计算的位置无关，但是这个相同的数字出现的次数必须是偶数次,奇数次会出问题。

所以我们对所有的数字都进行异或操作就能找出孤儿的那个数字了。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i =0;i<nums.size();i++){
            res = res^nums[i];
        }
        return res;
    }
};

不同的二叉搜索树(dfs)

不同的二叉搜索数

image-20210507094949148

才用dfs的思想，先找出任意一个节点下，左树的所有可能，和右树的所有可能，然后对左右子树进行结合生成二叉搜索树，然后选择下一个节点进行左右树的查找。

因为二叉搜索树左边小，右边大，可以利用类似与二分的思想划分左树和右树

AC代码：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> dfs(int low,int high){
        // 定义递归出口，左边索引比右边索引大
        if(low>high){
            return {nullptr};
        }
        // 定义最终所有树的接收向量
        vector<TreeNode*> alltree;
        for(int mid = low;mid<=high;mid++){
            // 寻找当前值下所有的左树
            vector<TreeNode*> lt = dfs(low,mid-1);
            // 寻找当前值下所有的右树
            vector<TreeNode*> rt = dfs(mid+1,high);
            // 遍历左树和右树，生成不同的二叉搜索树
            for(TreeNode* left : lt)
                for(TreeNode* right:rt){
                    alltree.push_back(new TreeNode(mid,left,right));
                }
        }
        // 返回所有的二叉搜索树
        return alltree;
    }
    vector<TreeNode*> generateTrees(int n) {
        return dfs(1,n);
    }
};

完全背包问题解法(动态规划)

完全背包问题

题目简介：

image-20210507185353257

和01背包问题的差别在于货物的使用次数是无限次,直接从代码讲解会轻松一些

思路来源

给出最初的代码

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 <bits/stdc++.h>
using namepsace std;
const int N  = 1024;
// 动归表
int dp[N][N];
// 货物数和背包体积
int n,m;
// 货物体积和货物价值
int V[N],W[N];
int main(){
    // 正常输入
    cin>>n>>m;
    for(int i =1;i<=n;i++)
        cint>>V[i]>>W[i];
	// 物品
   	for(int i = 1;i<=n;i++)
        // 体积
        for(int j = 0;j<=m;j++)
            // 物品使用个数
            for(int k = 0;k*V[i] <= j;k++){
                dp[i][j] = max(dp[i][j],dp[i-1][j-k*V[i]]+k*W[i]);
            }
    cout<<dp[n][m];
    return 0;
}

对比一下

1
2
3
4
5
6
dp[i][j] = max(dp[i-1][j],	dp[i-1][j-v[i]]+W[i],	dp[i-1][j-v[i]*2]+W[i]*2,	....)
dp[i][j-v[i]] = max(		dp[i-1][j-v[i]],		dp[i-1][j-v[i]*2]+W[i],		....)
从两个式子中可以看出来，dp[i][j]从第二项开始n往后，就是比dp[i][j-v[i]]多了个W[i]
    所以我们可以写成dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]]+W[i]);
	有没有觉得这式子很眼熟，对没错很像01背包问题，但是01背包问题是dp[i][j] = max(dp[i-1][j],dp[i-1][j-V[i]]+W[i]);
	区别在于max函数内的第二项的索引不同。

经过上面优化可以获得最终的代码为：

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 <bits/stdc++.h>
using namespace std;
const int N = 1024;
int dp[N][N];
int n, v;
int V[N], W[N];
int main()
{
    cin >> n >> v;
    for (int i = 1; i <= n; i++)
    {
        cin >> V[i] >> W[i];
    }
    // 物品
    for (int i = 1; i <= n; i++)
    {
        // 体积
        for (int j = 1; j <= v; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= V[i])
                dp[i][j] = max(dp[i-1][j],dp[i][j-V[i]]+W[i]);
        }
    }
    cout << dp[n][v];
    return 0;
}

来一题蓝桥杯的奇怪题目（位运算）

image-20210507195907465

其实是一个简单为运算，只用获取前8为的数据，前8位i为1的地方输出就行了，注意的是一行有两个字节，就是16位。

获取a的第i位数据的方法：cout<<((a>>i)&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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[11][100] = {
        {4, 0, 4, 0, 4, 0, 4, 32, -1, -16, 4, 32, 4, 32, 4, 32, 4, 32, 4, 32, 8, 32, 8, 32, 16, 34, 16, 34, 32, 30, -64, 0},
        {16, 64, 16, 64, 34, 68, 127, 126, 66, -124, 67, 4, 66, 4, 66, -124, 126, 100, 66, 36, 66, 4, 66, 4, 66, 4, 126, 4, 66, 40, 0, 16},
        {4, 0, 4, 0, 4, 0, 4, 32, -1, -16, 4, 32, 4, 32, 4, 32, 4, 32, 4, 32, 8, 32, 8, 32, 16, 34, 16, 34, 32, 30, -64, 0},
        {0, -128, 64, -128, 48, -128, 17, 8, 1, -4, 2, 8, 8, 80, 16, 64, 32, 64, -32, 64, 32, -96, 32, -96, 33, 16, 34, 8, 36, 14, 40, 4},
        {4, 0, 3, 0, 1, 0, 0, 4, -1, -2, 4, 0, 4, 16, 7, -8, 4, 16, 4, 16, 4, 16, 8, 16, 8, 16, 16, 16, 32, -96, 64, 64},
        {16, 64, 20, 72, 62, -4, 73, 32, 5, 16, 1, 0, 63, -8, 1, 0, -1, -2, 0, 64, 0, 80, 63, -8, 8, 64, 4, 64, 1, 64, 0, -128},
        {0, 16, 63, -8, 1, 0, 1, 0, 1, 0, 1, 4, -1, -2, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 5, 0, 2, 0},
        {2, 0, 2, 0, 7, -16, 8, 32, 24, 64, 37, -128, 2, -128, 12, -128, 113, -4, 2, 8, 12, 16, 18, 32, 33, -64, 1, 0, 14, 0, 112, 0},
        {1, 0, 1, 0, 1, 0, 9, 32, 9, 16, 17, 12, 17, 4, 33, 16, 65, 16, 1, 32, 1, 64, 0, -128, 1, 0, 2, 0, 12, 0, 112, 0},
        {0, 0, 0, 0, 7, -16, 24, 24, 48, 12, 56, 12, 0, 56, 0, -32, 0, -64, 0, -128, 0, 0, 0, 0, 1, -128, 3, -64, 1, -128, 0, 0},
    };
    int n = 32;
    int m = 10;
    for (int k = 0; k < m; k++)
    {
        for (int j = 0; j < n; j += 2)
        {
            for (int i = 7; i >= 0; i--)
            {
                int t = ((a[k][j] >> i) & 1);
                if (t)
                    cout << t;
                else
                    cout << " ";
            }
            for (int i = 7; i >= 0; i--)
            {
                int t = ((a[k][1 + j] >> i) & 1);
                if (t)
                    cout << t;
                else
                    cout << " ";
            }
            printf("\n");
        }
        printf("\n");
    }
    // 9的9次方是多少
    return 0;
}

/*
125
*/

今天来一个DP题，数字三角形

数字三角形

解题思路

我们把这个三角形转化成输入样例的样子，我们就可以发现，这个三角形其实是可以使用一个二维数组进行存储的。

要求从第一层到最后一层的数值最大，那么我们dp表示就表示数字和最大，dp[i][j]表示到i，j这个位置的最大值为多少，当i = j = 1时，重量为w[1][1]

当前这个点的a最大值，可以由上方和左上方的数字得来，转化成递推方程就是

dp[i][j]=max{dp[i−1][j],dp[i−1][j−1]}+g[i][j]dp[i][j] = max\{dp[i-1][j],dp[i-1][j-1]\}+g[i][j]

计算完dp之后，再遍历最后一行找出最大值就可以了

AC代码

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
#include <bits/stdc++.h>
using namespace std;
const int N =510;
// g表示三角形的存储，dp表示动规结果
int g[N][N],dp[N][N];
int n;
int main(){
    cin>>n;
    // 输入
    for(int i =1;i<=n;i++)
        for(int j = 1;j<=i;j++)
            cin>>g[i][j];
   	// dp初始化
    memset(dp,-0x3f,sizeof dp);
    // 初值
    dp[1][1] = g[1][1];
    for(int i =2;i<=n;i++)
        for(int j =1;j<=i;j++)
            // 递推方程
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])+g[i][j];
   	// 找出最后一行最大的那个数
    int res = -0x3f3f3f3f;
    for(int i =1;i<=n;i++){
        res = max(res,dp[n][i]);
    }
    cout<<res<<endl;
    return 0;
}

石子合并问题

石子合并

解题思路

在这题中，我们可以枚举这个区间的长度，然后在这个区间中寻找一个分位点，通过使用该点使得该区间合并的结果最小。

使用dp[l][r]表示合并l到r的区间最小的代价。我们可以将lr区间，分成，[l,k],[k+1,r],最后这两个区间的合并代价w应该为从l一直加到r的结果

于是我们有递推方程

dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+w)dp[l][r] = min(dp[l][r],dp[l][k]+dp[k+1][r]+w)

AC代码

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 <bits/stdc++.h>
using namespace std;
const int N = 310;
// 前缀和数组
int s[N];
int dp[N][N];
int n;
int main(){
    cin>>n;
    // 算前缀和
    for(int i =1;i<=n;i++){
        cin>>s[i];
        s[i] += s[i-1];
    }
    // 枚举每个区间长度
    for(int i = 2;i<=n;i++){
        // 枚举当前区间长度下,每个区间的起点
        for(int l = 1;l<=n-i+1;l++)
        {
            int r = l+i-1;
            // 初始化当前层合并的代价很大
            dp[l][r] = 1e8;
            // 遍历中转节点
            for(int k = l;k<r;k++){
                // 合并[l,r]所需要的代价
                int w = s[r]-s[l-1];
                dp[l][r] = min(dp[l][r],dp[l][k]+dp[k+1][r]+w);
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}

记忆化搜索——滑雪

滑雪

解题思路

从题中可以看出，我们要从四个方向去寻找下一个可以i前进的方向，使其可以达到滑雪路径最长。这种描述是一种典型的搜索问题。因为要求最大值，通常是采用DFS，但是在这题下，如果采用DFS，过大的数据量很有可能会爆栈或超时，因此需要引入一个记忆化搜索矩阵dp[x][y]，用于记录（x,y）这个点的最长滑雪路径，在我们到(x2,y,2)这个点时，只需要看一下，他四个方向可不可走，可走，就更新当前位置的值。

AC代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
// 滑雪场g，记忆矩阵dp
int g[N][N],dp[N][N];
// 向四个方向玩
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
// 行列
int a,b;
// 寻找当前这个点的最长滑雪距离
int dfs(int x,int y){
    // 如果已经算过了，就直接返回原值
    if(dp[x][y] != -1)return dp[x][y];
    // 否则，就先初始化为1，自己也算一个。
    dp[x][y]=1;
    // 遍历四个方向
    for(int i =0;i<4;i++){
        int tx = x+dx[i],ty = y+dy[i];
        // 在滑雪场中，别且满足滑雪条件的方向
        if(tx >0&&tx<=a&&ty>0&&ty<=b&&g[tx][ty]<g[x][y])
            // 上一个点过来的最大值
            dp[x][y] = max(dp[x][y],dfs(tx,ty)+1);
    }
    return dp[x][y];
}

int main(){
    cin>>a>>b;
	// 正经输入
    for(int i=1;i<=a;i++)
        for(int j = 1;j<=b;j++)
            cin>>g[i][j];
    // 初始化记忆矩阵
    memset(dp,-1,sizeof dp);
    // h初始化最大路径的值
    int res  = -1;
    // 找到当前这个点的最长滑雪距离，然后和res比较
    for(int i = 1;i<=a;i++)
        for(int j = 1;j<=b;j++){
            res = max(res,dfs(i,j));
        }
    cout<<res<<endl;
    return 0;
}

杨辉三角(蓝桥)

3418. 杨辉三角形 - AcWing题库

image-20220218161729008

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 <bits/stdc++.h>
using namespace std;

typedef long long LL;
// 要找的数
int n;

// 计算C_a^b
LL C(int a,int b){
    LL res = 1;
    for(int i = a,j = 1;j<=b;i--,j++){
        res = res * i/j;
        // 如果大于了，说明不在这个斜行，就不用算下去了
        if(res >n)return res;
    }
    return res;
}

// 根据斜行找到目标数对应的行，输入的参数就是目标的斜行数
bool check(int k){
    // 二分查找其行数，他在第n行肯定能找到，2k是从当前斜行所在行开始找
    // 通常2k<n,但是当n=1时就会出问题，所以l不能比r大
    int l = k*2,r = max(n,l);
    // 开始二分
    while(l<r){
        LL mid = l+r>>1;
        if(C(mid,k)>=n)r=mid;
        else l = mid+1;
    }
    // 对应的行号为r，算一下其C_r^k是否等于n，不是的话说明不在这一斜行
    if(C(r,k)!=n)return false;
    // 我们知道第一层有1个，第二层有2个，所以是一个等差数列
    // 第1~n层有(n+1)*n/2个数字
    cout<<1ll*r*(r+1)/2+k+1<<endl;
    return true;
}

int main(){
    cin>>n;
    for(int k=16;;k--){
        if(check(k))
            break;
    }
    return 0;
}

错误票据(蓝桥)

找出断片和重复的两个数字即可，这个方法应该是O(n)O(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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int f[N];
int n;

int main(){
    cin>>n;
    int max_n = -1,min_n = 0x3f3f3f3f;
    int num;
    // cin确保了读到文件末尾
    while(cin>>num){
        if(max_n<num)max_n = num;
        if(min_n>num)min_n=  num;
        f[num]++;
    }
    int res1,res2;
    for(int i = min_n+1;i<max_n;i++){
        if(f[i]==0)res1=i;
        if(f[i]==2)res2=i;
    }
    cout<<res1<<" "<<res2;
    return 0;
}

买不到的数目(蓝桥)

1205. 买不到的数目 - AcWing题库

这个是一个结论题，题目解释一下给一个n和m，求出n和m在不同数量组合的情况下不能组合出来的最大数字

假设我们是4,6然后不管怎么组合都不可能组合出奇数，所以比不可能有这种情况，因为题目有解

所以这里用到的结论是

对任意互质的两个数字n和m，他们最大的，不能组合出来的数为(n−1)∗(m−1)−1(n-1)*(m-1)-1

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    cout<<(n-1)*(m-1)-1;
    return 0;
}

笨拙的手指

2058. 笨拙的手指 - AcWing题库

暴力枚举就行

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
#include <bits/stdc++.h>
using namespace std;

// 将任意进制的字符串，转化成10进制的数字
int get(string a, int b)
{
	int res = 0;
	for (auto c : a)
	{
		res = res * b + c - '0';
	}
	return res;
}


int main()
{
	//freopen("1.txt", "r", stdin);
	string a, b;
	cin >> a >> b;
	// 存储2进制数字所有可能的集合
	unordered_set<int> s;
	// 修改字符串中某一位置的值
	for (auto &c : a)
	{
		// 用&表示在a上进行修改
		c ^= 1;
		// 0字符和1字符的ascii码相差1，所以直接异或就能得到彼此
		// 转换后存入到集合中
		s.insert(get(a, 2));
		// 还原成原来的字符串
		c ^= 1;
	}
	// 修改三进制的数字
	for (auto &c : b)
	{
		// 先记录原来的值
		char t = c;
		// 遍历所有可能的变化
		for (int i = 0; i < 3; i++)
		{
			// 如果和原来不一样
			if (i + '0' != t)
			{
				// 进行转换
				c = i + '0';
				// 计算这个值
				int tmp = get(b, 3);
				// 这个值在不在之前的集合中，在的话直接输出，因为结果唯一
				if (s.count(tmp))
				{
					cout << tmp << endl;
					return 0;
				}
			}
		}
		// 还原成原来的字符
		c = t;
	}
	return 0;
}

干草堆

2041. 干草堆 - AcWing题库

解法1：经典差分问题，但是要输出中间结果，那就排个序，时间复杂度大概O(nlog(n))O(nlog(n))，数据量106,nlog(n)=106∗log(106)10^6,nlog(n) = 10^6*log(10^6)不会超过10710^7差不多，可以这么解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int a[N], b[N];
int n, k;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= k; ++ i) {
        int l, r; cin >> l >>r;
        a[l] += 1;
        a[r + 1] -= 1;
    }
    for (int i = 1; i <= n; ++i) {
        b[i] = b[i-1] + a[i];
    }
    sort(b + 1, b + n +1);
    cout << b[n / 2 + 1];
    
    return 0;
}

研究生机试题

3683. 长方形中的正方形 - AcWing题库

暴力模拟

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 <bits/stdc++.h>

using namespace std;

int a, b;

int main()
{
	// freopen("1.txt","r",stdin);
	// 输出长宽
	cin >> a >> b;
	int cnt = 1;
	// 还能撕
	while (a > 0 && b > 0)
	{
		// 以短边为基准撕
		if (a > b)
			a -= b;
		else
			b -= a;
		// 能撕才撕
		if (a > 0 && b > 0)
			cnt++;
	}
	cout << cnt << endl;
	return 0;
}

3684. a与b得到c - AcWing题库

暴力模拟

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 <bits/stdc++.h>

using namespace std;

double a, b, c;

bool check()
{
	if (a + b == c)
		return true;
	else if (a - b == c)
		return true;
	else if (b - a == c)
		return true;
	else if (a * b == c)
		return true;
	else if (b && a / b == c)
		return true;
	else if (a && b / a == c)
		return true;
	return false;
}

int main()
{
	// freopen("1.txt","r",stdin);
	while (cin >> a >> b >> c)
	{
		if (check())
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}

3685. 求众数 - AcWing题库

哈希表一存，遍历一遍，结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;

int n, x;
map<int, int> mp;

int main()
{
	// freopen("1.txt", "r", stdin);
	cin >> n;
	while (n--)
	{
		cin >> x;
		mp[x]++;
	}
	int max_data = 0, res = -1;
	for (auto tmp = mp.begin(); tmp != mp.end(); tmp++)
		if (tmp->second > max_data)
			res = tmp->first, max_data = tmp->second;
	cout << res << endl;
	return 0;
}

3687. 骨牌 - AcWing题库

类似走楼梯，一次可以空出两个位置或者只空一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int dp[N];
int n;
int main()
{
	// freopen("1.txt", "r", stdin);
	cin >> n;
	dp[1] = 1, dp[2] = 2;
	for (int i = 3; i <= n; i++)
		dp[i] = (dp[i - 1] + dp[i - 2]) % 999983;
	cout << dp[n] << endl;
	return 0;
}

3701. 非素数个数 - AcWing题库

这个考察两个知识点，质数筛和前缀和

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 <bits/stdc++.h>

using namespace std;

const int N = 1e7 + 10;
int a, b;

// 1~n中的质因数
int primes[N], cnt; // primes[]存储所有素数
bool st[N];			// st[x]存储x是否被筛掉
int res[N];			// 前缀和数组

void get_primes(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i])
			primes[cnt++] = i;
		for (int j = 0; primes[j] <= n / i; j++)
		{
			st[primes[j] * i] = true;
			if (i % primes[j] == 0)
				break;
		}
	}
}
int main()
{
	get_primes(N);
	for (int i = 1; i < N; i++)
		res[i] = res[i - 1] + st[i];
	while (cin >> a >> b)
		cout << res[b] - res[a - 1] << endl;
	return 0;
}

3557. 分段函数 - AcWing题库

有手就行

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
#include <bits/stdc++.h>

using namespace std;

int n;
double x;

double f(double x)
{
	if (0 <= x and x < 2)
		return -1 * x + 2.5;
	else if (2 <= x and x < 4)
		return 2 - 1.5 * (x - 3) * (x - 3);
	return x / 2.0 - 1.5;
}

int main()
{
	cin >> n;
	while (n--)
	{
		cin >> x;
		printf("y=%.1lf\n", f(x));
	}
	return 0;
}

3558. 整数和 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>

using namespace std;
int n, x;

int main()
{
	cin >> n;
	while (n--)
	{
		cin >> x;
		cout << (x + 2 * x) * (abs(x) + 1) / 2 << endl;
	}
	return 0;
}

3559. 围圈报数 - AcWing题库

我是笨蛋，这么简单，用个循环队列模拟不就行了，我还在想怎么用数组模拟哦，我是笨蛋

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 <bits/stdc++.h>

using namespace std;

int main()
{
	int n, t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		queue<int> q;
        // 把数据全部放进队列
		for (int i = 1; i <= n; i++)
			q.push(i);
		int now = 0;
		while (q.size())
		{
			int tmp = q.front();
			now++;
			q.pop(); // 取出一个数字
			if (now == 3)// 如果这个数字是3，就输出
			{
				cout << tmp << " ";
				now = 0; // 重置编号
				continue;
			}
			q.push(tmp); // 不然就重新塞回队列
		}
		puts("");
	}
	return 0;
}

3560. 阶乘 - AcWing题库

有手就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

int n, m;
long long a[23];

int main()
{
	a[0] = 1;
	for (int i = 1; i <= 20; i++)
	{
		a[i] = a[i - 1] * i;
	}
	cin >> n;
	while (n--)
	{
		cin >> m;
		cout << a[m] << endl;
	}
	return 0;
}

3562. 重载运算符 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

using namespace std;

int n, a, b;

int main()
{
	cin >> n;
	while (n--)
	{
		cin >> a >> b;
		double angle = (a - b) * 1.0 / 180 * 3.1415926;
		printf("%.2lf\n", sin(angle));
	}
	return 0;
}

3563. 多项式的值 - AcWing题库

map模拟多项式好用的

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 <bits/stdc++.h>
using namespace std;

int main()
{
	int n, t, x;
	cin >> t;
	while (t--)
	{
		cin >> n;
		map<int, int> mp;
		for (int i = 0; i <= n; i++)
		{
			cin >> x;
			mp[i + 1] = x;
		}
		cin >> x;
		int res = 0;
		for (auto it = mp.begin(); it != mp.end(); it++)
			res = res + it->second * pow(x, it->first - 1);
		cout << res << endl;
	}
	return 0;
}

3566. 复数加法 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n, a, b, c, d;
	cin >> n;
	while (n--)
	{
		cin >> a >> b >> c >> d;
		a = a + c;
		b = b + d;
		cout << a;
		if (b > 0)
			cout << "+";
		cout << b << "i" << endl;
	}
	return 0;
}

3567. 判断数字位置 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n;
	string a;
	cin >> n;
	while (n--)
	{
		cin >> a;
		for (int i = 0; i < a.size(); i++)
			if ('0' <= a[i] && a[i] <= '9')
				cout << i + 1 << " ";
		puts("");
	}
	return 0;
}

3568. 整型存储 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

int main()
{
	string x;
	int cnt = 0;
	while (cin >> x)
	{
		if (x == "0")
			break;
		cout << x << " ";
		reverse(x.begin(), x.end());
		int res = atoi(x.c_str());
		cout << res << endl;
		cnt++;
		if (cnt >= 10)
			break;
	}
	return 0;
}

3569. 三角形相加 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int x, y, a = 0, b = 0;
	while (cin >> x >> y)
		a += x, b += y;
	printf("A(0,%d),B(0,0),C(%d,0)", a, b);
	return 0;
}

3570. 弹地小球 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;
int t, n;
double h;

int main()
{
	cin >> t;
	while (t--)
	{
		cin >> h >> n;
		double res = 0;
		while (n--)
		{
			res += (h + h/2.0);
			h/=2;
		}
		res -= h;
		printf("%.2lf\n",res);
	}
	return 0;
}

3571. 点的距离 - AcWing题库

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 <bits/stdc++.h>

using namespace std;

class ppp
{
public:
	ppp() { x = 0, y = 0, l = 0; }
	ppp(double a, double b) { x = a, y = b, l = 0; }
	ppp operator - (ppp & A)
	{
		ppp tmp;
		tmp.l = sqrt(pow(x - A.x, 2) + pow(y - A.y, 2));
		return tmp;
	}
	void print()
	{
		printf("%.2lf\n", l);
	}

private:
	double x, y, l;
};

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		double a, b, c, d;
		cin >> a >> b >> c >> d;
		ppp p1(a, b), p2(c, d);
		ppp res = p1 - p2;
		res.print();
	}
	return 0;
}

3572. 直角三角形 - AcWing题库

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 <bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		double a, b, c, d, e, f;
		cin >> a >> b >> c >> d >> e >> f;
		double x, y, z;
		x = pow(a - c, 2) + pow(b - d, 2);
		y = pow(a - e, 2) + pow(b - f, 2);
		z = pow(c - e, 2) + pow(d - f, 2);
		if (x + y == z || x + z == y || y + z == x)
			puts("Yes");
		else
			puts("No");
		printf("%.2lf\n", sqrt(x) + sqrt(y) + sqrt(z));
	}
	return 0;
}

3573. 日期累加 - AcWing题库

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 <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;
const ULL DAY = 24 * 60 * 60;

// 标准时间转时间戳
time_t standard_to_stamp(char *str_time)
{
    struct tm stm;
    ULL iY, iM, iD;

    memset(&stm, 0, sizeof(stm));
    iY = atoi(str_time);
    iM = atoi(str_time + 5);
    iD = atoi(str_time + 8);

    stm.tm_year = iY - 1900;
    stm.tm_mon = iM - 1;
    stm.tm_mday = iD;
    return (time_t)mktime(&stm);
}

// 时间戳转标准时间
string stamp_to_standard(time_t a)
{
    char tmp[32] = {NULL};
    strftime(tmp, sizeof(tmp), "%Y-%m-%d", localtime(&a));
    string data(tmp);
    return data;
}

int main()
{
    ULL t;
    cin >> t;
    while (t--)
    {
        ULL a, b, c, d;
        cin >> a >> b >> c >> d;
        // 格式化输入日期
        char buffer[32];
        snprintf(buffer, 32, "%d-%02d-%02d", a, b, c);
        // 转化成时间戳，然后加上对应天数的时间戳
        time_t r = standard_to_stamp(buffer) + d * DAY;
        // 时间戳转化成标准时间
        cout << stamp_to_standard(r) << endl;
    }
    return 0;
}

3575. 编排字符串 - AcWing题库

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
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin >> t;
	queue<string> q; // 记录已经存储的字符串
	while (t--)
	{
		string tmp;
		cin >> tmp;
		cout << "1=" << tmp;			 // 先输出目前输入的
		int n = q.size();				 // 记录当前队列中的数据数量
		q.push(tmp);					 // 插入数据
		for (int i = 2; i <= n + 1; i++) // 然后遍历n次队列
		{
			string now = q.front(); // 取出数据
			q.pop();
			if (i > 4)
				continue;					// 如果存储超过四个就直接出栈就行
			q.push(now);					// 不然重新加回去
			cout << " " << i << "=" << now; // 输出当前取出的数据
		}
		puts("");
	}
	return 0;
}

##3576. 分组统计 - AcWing题库

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
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin >> t; // 测试数据组数
	while (t--)
	{
		int n;
		cin >> n;					// 给定的n个整数
		vector<int> a(n);			// 存储整数
		set<int> data;				// 去重，即题目中m个不同的数值
		for (int i = 0; i < n; i++) // 正常输入和去重
		{
			cin >> a[i];
			data.insert(a[i]);
		}
		// 分组统计，第一个key是组，第二个key是这组中的某个值，最后一个values是这个值在组中的数量
		map<int, map<int, int>> mp;
		for (int i = 0; i < n; i++) // 获取这组输入
		{
			int x;
			cin >> x;	   // 这个数字是第几组
			mp[x][a[i]]++; // 这个数字的次数加一
		}
		// 遍历每一个组，first是组名，second是组的内容
		for (auto it = mp.begin(); it != mp.end(); it++)
		{
			cout << it->first << "={";
			bool flag = true; // 输出格式化
			// 从小到大遍历每一个可能出现的值
			for (auto itt = data.begin(); itt != data.end(); itt++)
			{
				if (flag) // 第一次不输出逗号
				{
					flag = false;
					// 在second中寻找*itt值出现的次数
					cout << *itt << "=" << it->second[*itt];
				}
				else
					cout << "," << *itt << "=" << it->second[*itt];
			}
			cout << "}" << endl;
		}
	}
	return 0;
}

3581. 单词识别 - AcWing题库

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
#include <bits/stdc++.h>

using namespace std;

int main()
{
	string str;
	getline(cin, str);					   // 接收一行字符串
	str = str + ".";					   //避免不以非字母结束的情况
	int pos = 0;						   // 记录当前单词的起始位置
	map<string, int> mp;				   // 用于存储单词出现的次数
	for (int i = 0; i < str.length(); i++) // 遍历字符串的字符
	{
		if ('A' <= str[i] && str[i] <= 'Z') // 大写变小写
			str[i] = str[i] - 'A' + 'a';
		else if ('a' <= str[i] && str[i] <= 'z') // 小写不处理
			continue;
		else // 非字母
		{
			string tmp = str.substr(pos, i - pos); // 提取单词
			mp[tmp]++;							   // 单词出现次数+1
			pos = i + 1;						   // 更新单词的起始位置
			// 位置不能超过字符串长度，并且必须为字母
			while (pos < str.length() && (str[pos] == '.' || str[pos] == ',' || str[pos] == ' '))
				pos++;
			// 更新下一个i的位置，从pos开始的话可以把大写字母变成小写
			i = pos - 1;
		}
	}
	// 遍历统计结果
	for (auto it = mp.begin(); it != mp.end(); it++)
		cout << it->first << ":" << it->second << endl;
	return 0;
}

3582. 身份证校验 - AcWing题库

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 <bits/stdc++.h>

using namespace std;

// 对应17位的权重
int weight[] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
// 余数与校验位的对应
map<int, char> mp = {{0, '1'}, {1, '0'}, {2, 'X'}, {3, '9'}, {4, '8'}, {5, '7'}, {6, '6'}, {7, '5'}, {8, '4'}, {9, '3'}, {10, '2'}};

bool check(string &str)
{
	int data = 0;
	// 计算加权和
	for (int i = 0; i < 17; i++)
		data += (str[i] - '0') * weight[i];
	// 取模
	data = data % 11;
	// 检验
	return str[17] == mp[data];
}

int main()
{
	string str;
	while (cin >> str)
	{
		if (str.length() != 18)
			puts("ID Wrong");
		else
		{
			if (check(str))
				puts("ID Corrent");
			else
				puts("ID Wrong");
		}
	}
	return 0;
}

994. 腐烂的橘子 - 力扣（LeetCode）

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
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 120;
int g[N][N]; // 网格
int good = 0, n, m, t = 0; // good是白纸，n,m,t分别表示矩阵n,m和时间t
queue<PII> q; // 队列，存储墨水的坐标
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};// 遍历墨水的四个方向

bool check(int x, int y)// 检查四个方向上的坐标是否越界
{
	return x >= 0 && y >= 0 && x < n && y < m;
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> g[i][j];
			if (g[i][j] == 1) // 如果是白纸
				good++;
			else if (g[i][j] == 2) // 如果是墨水就加入队列，并标记
				q.push({i, j});
		}
	if (good)
	{
		q.push({-1, -1}); // 表示当前时间点结束
		while (q.size())
		{
			PII tmp = q.front(); // 取出第一个墨点
			q.pop();
			if (tmp.first == -1) // 如果当前时间段的墨点没遍历完了
			{
				t++; // 时间+1
				if (q.size()) // 看看下一时间还有没有可以用的墨点
					q.push({-1, -1});
				if (!good) // 白纸是不是染完了
					break;
			}
			else
			{
				for (int i = 0; i < 4; i++) // 遍历墨点的四个方向
				{
					int x = tmp.first + dx[i], y = tmp.second + dy[i];
					if (check(x, y) && g[x][y] == 1 ) // 检查是否越界，是否为白纸，
					{
						good--; // 白纸数量-1
						g[x][y] = 2; // 将白纸侵染
						q.push({x, y}); // 将当前墨水的位置加入队列
					}
				}
			}
		}
	}
	// 如果白点没能侵染完
	if (good)
		puts("FALSE");
	else // 如果白点侵染完了
		cout << t;
	return 0;
}

二分数据查找

Question:
显示出如下数组中的所有元素，并使用二分查找法在数组中查找元素。
int a[]={-90,-32,12,16,24,36,45,59,98,120};
输入输出示例
-90 -32 12 16 24 36 45 59 98 120
请输入所要查找的元素：24
输出：第5个元素为24，比较次数为1
请输入所要查找的元素：120
输出：第10个元素，比较次数为4
请输入所要查找的元素：6
输出：查找失败 比较次数为3 
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
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n, x;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	while (cin >> x)
	{
		int cnt = 0;		  // 存储查找次数
		int l = 0, r = n - 1; // 初始化边界
		while (l <= r)
		{
			cnt++;				  //查找次数+1
			int mid = l + r >> 1; //取中间
			if (a[mid] > x)		  // 如果目标在中间的左边
				r = mid - 1;
			else if (a[mid] == x) // 正好是目标
			{
				cout << mid + 1 << " " << cnt << endl;
				break;
			}
			else // 目标在中间的右边
				l = mid + 1;
		}
		if (l > r)
			cout << -1 << " " << cnt << endl;
	}
	return 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
26
27
28
#include <bits/stdc++.h>

using namespace std;

string find(string mid, string back)
{
	if (back == "" || mid == "")
		return "";
	int i;
	string res;
	// 找到根节点在中序序列的位置
	for (i = 0; i < mid.length() && mid[i] != back[back.length() - 1]; i++)
		;
	res.push_back(mid[i]); // 根节点
	// 左子树前序遍历
	string left = find(string(mid.begin(), mid.begin() + i), string(back.begin(), back.begin() + i));
	// 右子树前序遍历
	string right = find(string(mid.begin() + i + 1, mid.end()), string(back.begin() + i, back.begin() + back.length() - 1));
	return res + left + right;
}

int main()
{
	string mid, back;
	cin >> mid >> back;
	cout << find(mid, back);
	return 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
26
27
#include <bits/stdc++.h>

using namespace std;

string a;
bool check(int i, int j)
{
	while (i <= j)
		if (a[i++] != a[j--]) // 第一个和最后一个是否相同
			return false;
	return true;
}
int main()
{
	cin >> a;
	transform(a.begin(), a.end(), a.begin(), ::tolower); // 大写变小写
	int len = 0, cnt = 0;
	for (int i = 0; i < a.length(); i++)							  // 遍历每个字符
		for (int j = a.length() - 1; j >= i && j - i + 1 >= len; j--) // 从后向前，不超过i并且距离还能超过目前最大值
			if (check(i, j))										  // 看看i到j是不是回文
				if (j - i + 1 == len)								  // 如果是回文，且长度相等数量+1
					cnt++;
				else // 如果是回文，但是长度变长了，记录信值，并初始化数量
					len = j - i + 1, cnt = 1;
	cout << len << " " << cnt;
	return 0;
}

通过字符串的层次接口，查找某个节点的父亲们

输入：

(aaa(bbb(ccc,ddd),eee(fff),ggg(h,i),j(k,l(m,n))))
n

输出：

aaa>j>l>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
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
#include <bits/stdc++.h>

using namespace std;

stack<string> stt;				  //存放目标值的父节点
map<string, vector<string>> tree; //树（邻接表的结构）
bool dfs(string &a, string &root)
{
	if (root == a) //如果这个节点就是要找的直接入栈，返回true
	{
		stt.push(a);
		return true;
	}
	if (tree[root].empty()) //没有子节点又不是目标值了直接返回false
		return false;
	for (int i = 0; i < tree[root].size(); i++) // 遍历他的孩子
	{
		string tmp = tree[root][i]; // 取出孩子
		if (dfs(a, tmp))			//再次查找。如果是目标的父亲
		{
			stt.push(root); //就将这个节点入栈
			return true;	// 然后返回真
		}
	}
	return false; //不然返回假
}

int main()
{
	string str, q;
	cin >> str;				// 表示树的字符串
	str.erase(str.begin()); //去除第一个和最后一个括号
	str.erase(str.begin() + str.length() - 1);
	stack<string> st;					   //存储节点
	for (int i = 0; i < str.length(); i++) // 遍历字符串
	{
		if (str[i] == '(') // 是左括号就直接加入
			st.push("(");
		else if (str[i] == ',') // 逗号跳过
			continue;
		else if (str[i] == ')') // 右括号开始生成树
		{
			vector<string> tmp;		// 用来表示当前最近的根节点的邻接表
			while (st.top() != "(") // 直到遇到左括号
			{
				tmp.push_back(st.top()); //  直接把节点塞进去
				st.pop();				 // 然后出栈
			}
			st.pop();			  // 把左括号出了
			tree[st.top()] = tmp; //邻接表与父节点链接
		}
		else
		{
			int pos = i;											//记录起始位置
			string tmp;												// 这个节点的符号表示
			while (str[i] != '(' && str[i] != ',' && str[i] != ')') //是字母就直接加入，并且更新结束位置
				tmp += str[i], i++;
			st.push(tmp); //直接将这个节点入栈
			i--;		  // 回退到这个节点字符串的末尾
		}
	}
	cin >> q;		   //输入要查询的节点
	dfs(q, st.top());  //第一参数是要查询的节点，第二个参数是树的根节点，目的是将目标点的父节点存储在stt中
	while (stt.size()) // 输出其父节点
	{
		cout << stt.top();
		stt.pop();
		if (stt.size())
			cout << ">";
	}
	return 0;
}

求广义表的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

int main()
{
	string a;
	cin >> a;
	stack<char> st;
	int res = 0;
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] == '(')
			st.push(a[i]), res = max(res, (int)st.size());
		else if (a[i] == ')')
			st.pop();
	}
	cout << res << endl;
	return 0;
}

最小公倍数与最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;
// 经典辗转相除法求最大公约数
int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	int a, b;
	while (cin >> a >> b)
	{
		int t = gcd(a, b); // 这个是求最大公约数
		cout << a * b / t << endl; // 这个是求最大公倍数
	}
	return 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
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

typedef pair<string, int> PSI;

bool cmp(PSI &a, PSI &b)
{
	return a.second > b.second;
}

int main()
{
	string str;
	map<string, int> mp;
	getline(cin, str);
	int pos = 0;
	// 我们默认句子最后肯定有符号表示结束，并且开头一定以单词开头
	for (int i = 0; i < str.length(); i++)
	{
		string s;
		while (i < str.length() && (('a' <= str[i] && str[i] <= 'z') || ('A' <= str[i] && str[i] <= 'Z'))) // 获取当前单词的结尾
			s += str[i], i++;
		mp[s]++;																							// 记录这个单词出现的次数
		while (i < str.length() && !(('a' <= str[i] && str[i] <= 'z') || ('A' <= str[i] && str[i] <= 'Z'))) // 获取下一个单词的开头
			i++;
		pos = i;
		i--;
	}
	vector<PSI> res(mp.begin(), mp.end()); // 将其放入到vector中方便排序
	sort(res.begin(), res.end(), cmp);
	for (auto it : res)
		cout << it.first << " " << it.second << endl;
	return 0;
}

3721. 求30的倍数 - AcWing题库

满足两个条件，这个输入的数字中有一位是0，并且所有位的数字加起来的和可以被3整除即可

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 <bits/stdc++.h>

using namespace std;
int n;
vector<int> v;
int main()
{
	cin >> n;
	int res = 0;
	while (n) // 取出每一位数字
	{
		v.push_back(n % 10);
		res += v.back(); // 计算每一位数字的和
		n /= 10;
	}
	sort(v.begin(), v.end()); // 对数字进行排序
	if (res % 3 == 0 && v.front() == 0 && v.back() != 0)// 和能被3整除，有0，且不只有0
	{
		for (int i = v.size() - 1; i >= 0; i--)// 从大到小进行输出
			cout << v[i];
	}
	else
		puts("-1");
	return 0;
}

3722. 骑车路线 - AcWing题库

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int a[N];
int n;
int main()
{
	// 循环输入
	while (cin >> n)
	{
		int res = 0, s = 0; // res是要输出的结果，s表示上升区间的起点值
		for (int i = 0; i < n; i++)
			cin >> a[i];
		s = a[0];					// 初值为第一个元素
		for (int i = 1; i < n; i++) // 循环遍历
		{
			if (a[i] >= a[i - 1]) // 如果当前这个满足上升条件就跳过
				continue;
			else // 不满足的时候
			{
				// 说明a[i-1]是前一段上升区间的最后一个元素
				// 计算一下前一段上升区间的高度差
				res = max(res, a[i - 1] - s);
				s = a[i]; // 更新s值
			}
		}
		if (a[n - 1] > s) // 如果到末尾还是上升的就再算一次
			res = max(res, a[n - 1] - s);
		cout << res << endl;
	}
	return 0;
}

3723. 字符串查询 - AcWing题库

前缀和

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 <bits/stdc++.h>

using namespace std;

const int N = 50010;
int p[30][N], a, b, c, d, n;
// p[i][j] 前j个字符中，第‘a’+i字符的个数
string str;

int main()
{
	cin >> str;
	// 用p先记录每个字符的位置
	for (int i = 1; i <= str.size(); i++) 
		p[str[i-1] - 'a'][i] = 1;
	// 然后分别对26个字母求前缀和
	// 即a在这N个字符中出现了多少次，b在这N个字符中出现了多少次
	// 后面的字母同理
	// 总共有26个字母
	for (int i = 0; i < 26; i++)
		for (int j = 1; j <= str.size(); j++)
			p[i][j] += p[i][j - 1];
	cin >> n; 
	while (n--)
	{
		cin >> a >> b >> c >> d;
		bool flag = true;
		for (int i = 0; i < 26; i++) // 求前缀和，看他们每个字母的个数一不一样
			if (p[i][b] - p[i][a - 1] != p[i][d] - p[i][c - 1])
			{
				puts("NE");
				flag = false;
				break;
			}
		if (flag)
			puts("DA");
	}
	return 0;
}

3724. 街灯 - AcWing题库

差分

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
#include <bits/stdc++.h>

using namespace std;
int a[1010];
int main()
{
	// 补充说明，街道的长度从1一直到n
	int n, m, k;
	// 街道长度，灯的数量，灯可以点亮的范围
	while (cin >> n >> m >> k)
	{
		// 初始化差分数组
		memset(a, 0, sizeof a);
		int x;
		for (int i = 0; i < m; i++)
		{
			cin >> x;
			// 开始差分，起点+1，终点的后一个位置-1
			a[max(1, x - k)]++, a[x + k + 1]--;
		}
		// 求前缀和
		for (int i = 1; i <= n; i++)
			a[i] += a[i - 1];

		int res = 0, p = 2 * k + 1;
		for (int i = 1; i <= n; i++) // 遍历前缀和数组
		{
			int len = 0;
			while (!a[i] && i <= n) // 看看0的部分有多少
			{
				len++;
				i++;
			}
			if (len) // 看看需要多少灯来点亮这个区域
				res += ceil((double)len / p);
		}
		cout << res << endl;
	}
	return 0;
}

4269. 校庆 - AcWing题库

先用哈希表存储校友的身份证，然后在来宾中进行条件比较就行

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
#include <bits/stdc++.h>

using namespace std;
int n, m;

bool cmp(string &a, string &b)
{
	return a.substr(6, 8) < b.substr(6, 8);
}

int main()
{
	unordered_map<string, int> record;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		record[str]++;
	}
	cin >> m;
	bool flag = false;
	string res = "";
	int cnt = 0;
	while (m--)
	{
		string str;
		cin >> str;
		if (record[str])
			cnt++;
		if (!flag && record[str]) // 1. 之前还没有校友，但是这个是校友
		{
			flag = true;
			res = str;
			continue;
		}
		if (!res.length()) // 2. 第一个，且第一个不是校友
		{
			res = str;
			continue;
		}
		if (flag && !record[str]) // 3. 之前有校友，但是这个不是校友
			continue;
		// 如果之前有校友，且这个也是校友（与3相反）， 如果之前没有校友，但是这个也不是校友（与1相反）
		if (cmp(str, res))
			res = str;
	}
	cout << cnt << endl;
	cout << res << endl;

	return 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
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
#include <bits/stdc++.h>

using namespace std;
int n, k;
unordered_map<string, int> mp;
string str;

// 是否为质数
bool is_prime(int x)
{
	if (x < 2) return false;
	for (int i = 2; i <= x / i; i ++ )
		if (x % i == 0)
			return false;
	return true;
}

string get_prize(string &str){
	int num = mp[str]; // 获取这个ID的排名
    // -1是已经领过了
	if(num==-1)return "Checked";
    // 0是不存在的ID
	if(num==0) return "Are you kidding?";
    // 标记领过
	mp[str] = -1;
    // 如果是第一名
	if(num==1) return "Mystery Award";
    // 如果是素数排名
	else if(is_prime(num)) return "Minion";
    // 其他
	return "Chocolate";
}

int main()
{
	cin >> n;
    // 记录每个ID的排名
	for (int i = 1; i <= n; i++)
	{
		cin >> str;
		mp[str] = i;
	}
	cin >> k;
	while (k--)
	{
		cin >> str;
		cout << str << ": " << get_prize(str) << endl;
	}
	return 0;
}

1585. 校园内的汽车 - AcWing题库

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
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

struct Record
{
	int time;							  // 记录的时间
	bool isIn;							  // 进还是出
	bool operator<(const Record &b) const // 用于排序
	{
		return time < b.time;
	}
};
unordered_map<string, vector<Record>> car;

int main()
{
	int n, k; // n个记录k个查询
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		char id[8], type[4]; // 车牌和状态
		int hh, mm, ss;		 // 时分秒
		scanf("%s %d:%d:%d %s", id, &hh, &mm, &ss, type);
		int time = hh * 60 * 60 + mm * 60 + ss; // 转化为纯秒
		bool flag = false;						// 默认是出
		if (type[0] == 'i')						// 如果是进，就改为true
		{
			flag = true;
		}
		car[id].push_back({time, flag}); // 插入数据
	}
	int maxTime = 0;
	vector<string> resCar;
	vector<Record> vaild;
	for (auto &item : car) // 遍历这个哈希表
	{
		auto &record = item.second; // 取出value存的数组
		// 根据时间递增排序
		sort(record.begin(), record.end());
		int parkTime = 0;
		// 记录有效记录
		for (int i = 0; i < record.size(); i++)
		{
			if (record[i].isIn) //如果他是进去的记录
			{
				// 他后面还有数据，并且他的后一个是出去
				if (i + 1 < record.size() && record[i + 1].isIn == false)
				{
					// 将这个记录插入有效的数组中
					vaild.push_back(record[i]);
					// 他出去的记录也插入有效的数组中
					vaild.push_back(record[i + 1]);
					// 记录停车时间
					parkTime += record[i + 1].time - record[i].time;
					// 跳过这两个数据
					i++;
				}
			}
		}
		// 更新最长停车时间
		if (parkTime > maxTime) //时间比他大
		{
			// 记录最长等待时间
			maxTime = parkTime;
			// 清空数组
			resCar.clear();
			// 插入当前数据
			resCar.push_back(item.first);
		}
		else if (parkTime == maxTime) // 时间和他相等
		{
			resCar.push_back(item.first); // 这个记录也插入结果中
		}
	}
	// 有效记录根据时间递增排序
	sort(vaild.begin(), vaild.end());
	// 因为查询时间也是递增的，不需要每次重新遍历
	int cnt = 0;				// 记录校园里的车
	int idx = 0;				// 记录当前在valid的哪个位置
	for (int i = 0; i < k; i++) // 遍历每个查询
	{
		int hh, mm, ss;
		scanf("%d:%d:%d", &hh, &mm, &ss);
		int queryTime = hh * 60 * 60 + mm * 60 + ss; // 获取时间
		for (; idx < vaild.size(); idx++)			 // 遍历valid
		{
			if (vaild[idx].time <= queryTime) // 如果查询在实践范围内
			{
				if (vaild[idx].isIn) // 如果记录表示进
					cnt++;			 // 校园车辆数+1
				else
					cnt--; // 否则校园车辆数-1
			}
			else
				break;
		}
		printf("%d\n", cnt); // 输出这个查询的校园车辆数
	}
	// 将停车最久的ID根据字母序排序
	sort(resCar.begin(), resCar.end());
	for (int i = 0; i < resCar.size(); i++)
	{
		printf("%s ", resCar[i].c_str()); // 输出停车最久的车牌
	}
	// 输出时间
	printf("%02d:%02d:%02d\n", maxTime / 3600, maxTime % 3600 / 60, maxTime % 60);
	return 0;
}

1531. 课程学生列表 - AcWing题库

  1. 解法1：每个课程开一个小根堆，然后读取某个人的选课情况的时候，根据小根堆数组索引到对应的堆把名字存进去就行。但是不加输入输出加速的话会TLE，建议直接使用printf
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 <bits/stdc++.h>

using namespace std;
const int K = 2510, N = 40010;
priority_queue<string, vector<string>, greater<string>> heap[K];
int n, k;

int main()
{
    scanf("%d%d",&n,&k);
	char name[8];
	int t, id;
	for (int i = 0; i < n; i++)
	{
		scanf("%s%d",name,&t);
		while (t--)
		{
			scanf("%d",&id);
			heap[id].push(name);
		}
	}
	for (int i = 1; i <= k; i++)
	{
		printf("%d %d\n",i,heap[i].size());
		while (heap[i].size())
		{
			printf("%s\n",heap[i].top().c_str());
			heap[i].pop();
		}
	}
	return 0;
}

1523. 学生课程列表 - AcWing题库

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 <bits/stdc++.h>

using namespace std;
int n,k;
unordered_map<string,vector<int>> mp; //记录每个id的学生选了什么课

int main(){
	scanf("%d%d",&n,&k); //输入要查询的学生和课程的数量
	int a,b;
	char name[8];
	while(k--){ // 遍历每一个课程
		scanf("%d%d",&a,&b); // 输入课程id以及选课人数
		while(b--){
			scanf("%s",name); // 获得选课人
			mp[name].push_back(a); // 把这个课程插入到选课人的课程列表中
		}
	}
	while(n--){ // 遍历每一个查询
		scanf("%s",name);
		printf("%s %d",name,mp[name].size()); // 输出查询人的ID，以及选的课程数
		sort(mp[name].begin(),mp[name].end()); // 排序所有课程
		for(int i = 0 ;i<mp[name].size();i++) // 遍历输出课程
			printf(" %d",mp[name][i]);
		puts("");
	}
	return 0;
}

1502. PAT 排名 - AcWing题库

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
#include <iostream>
#include <algorithm>
using namespace std;
int n, k, c; // 区域数，每个区域的人数，总考生数
struct S
{
	string registration_number; // 考号
	int final_rank;				// 最终排名
	int location_number;		// 地区编号
	int local_rank;				// 地区排名
	int score;					// 成绩
	bool operator<(const S &s) const
	{
		if (score != s.score)								// 如果两个分不一样的话
			return score >= s.score;						// 返回分大的那个
		return registration_number < s.registration_number; // 如果分一样返回考号大的
	}
} s[30010];
void gen_local_rank(S *l, S *r)
{
	int num = 2;	   // 假设现在有两个人
	S *i = l + 1;	   // 取出第二个人
	l->local_rank = 1; // 设置第一个人的区域排名为1
	while (i != r)	   // 如果第二个人不是最后一个（最后一个取不到的）
	{
		if ((i - 1)->score == i->score)			 // 如果他的前一个分数和他相等
			i->local_rank = (i - 1)->local_rank; // 那么他们的排名就相当
		else
			i->local_rank = num; // 不然他们的排名就是现在的这个排名
		num++, i++;				 // 排名和人都向后一个
	}
}
void gen_final_rank(S *l, S *r)
{
	int num = 2;	   // 假设现在有两个人
	S *i = l + 1;	   // 取出第二个人
	l->final_rank = 1; // 设置第一个人的区域排名为1
	while (i != r)	   // 如果第二个人不是最后一个（最后一个取不到的）
	{
		if ((i - 1)->score == i->score)			 // 如果他的前一个分数和他相等
			i->final_rank = (i - 1)->local_rank; // 那么他们的排名就相等
		else
			i->final_rank = num; // 不然他们的排名就是现在的这个排名
		num++, i++;				 // 排名和人都向后一个
	}
}
int main()
{
	cin >> n; // 输入区域数
	for (int i = 1; i <= n; i++)
	{
		cin >> k; // 输入这个区域有多少个选手
		for (int j = 0; j < k; j++)
		{
			string rn;
			int sc;
			cin >> rn >> sc; // 输入考号和分数
			s[c++] = {rn, 0, i, 0, sc};
		}
		sort(s + c - k, s + c);			  // 在区域中排序
		gen_local_rank(s + c - k, s + c); // 设置区域排名
	}
	sort(s, s + c);				// 总排序
	gen_final_rank(s, s + c);	// 设置总排名
	cout << c << endl;			// 输出参赛选手的人数
	for (int i = 0; i < c; i++) // 遍历每个参赛选手，并输出报名号，最终排名，区域号，区域排名
		cout << s[i].registration_number << " " << s[i].final_rank << " " << s[i].location_number << " " << s[i].local_rank << endl;
}

前N个数字加和为D

输入一个正整数数字n和一个d，让你求出将d拆分成n个互不相同的正整数之和，总共有多少种拆分方法。交换顺序视为同一种解法

输入样例：10 2022

输出：379187662194355221

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
	int n, d;
	cin >> n >> d;
	vector<vector<ll>> dp(n + 10, vector<ll>(d + 10, 0)); // dp[i][j]，前i个数的和为j的所有组合
	dp[0][0] = 1;										  // 前0个数的和为0的情况只有一种
	for (int i = 1; i <= d; i++)						  // 假设现在要加入一个数字i
		for (int j = n; j >= 1; j--)					  // 一开始拿j个数字
			for (int k = 1; k <= d; k++)				  // 遍历他的加和
				if (k >= i)								  // 如果加和比当前拿的数字大的话
					// 前j个数字加和为k的情况
					// 当前选择数字i，可由前j-1数字，加和为k-i的情况得到
					dp[j][k] += dp[j - 1][k - i];
	cout << dp[n][d];
	return 0;
}

end