头像

delicacy




离线:9天前



delicacy
30天前

830. 单调栈

给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。

输入格式
第一行包含整数 N,表示数列长度。

第二行包含 N 个整数,表示整数数列。

输出格式
共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 −1。

数据范围
1≤N≤105
1≤数列中元素≤109
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2

在这里插入图片描述

 3 4  2 7 9
-1 3 -1 2 7
const int N = 1e5 + 10;
int stk[N], tt;

int n;
int main() {
    scanf("%d", &n);
    while (n--) {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) {
            tt--; // 如果栈顶元素大于当前待入栈元素,则出栈
        }
        if (!tt) { // 如果栈空,则没有比该元素小的值。
            printf("-1 ");
        } else {
            printf("%d ", stk[tt]); // 栈顶元素就是左侧第一个比它小的元素。
        }
        ++tt;
        stk[tt] = x; // 入栈
    }
    return 0;
}



delicacy
1个月前

排队打水

有 n 个人排队到 1 个水龙头处打水,第 i 个人装满水桶所需的时间是 ti,请问如何安排他们的打水顺序才能使所有人的等待时间之和最小?

输入格式
第一行包含整数 n。

第二行包含 n 个整数,其中第 i 个整数表示第 i 个人装满水桶所花费的时间 ti。

输出格式
输出一个整数,表示最小的等待时间之和。

数据范围
1≤n≤105,
1≤ti≤104
输入样例:
7
3 6 1 4 2 5 7
输出样例:
56
肯定是快得在前面接水
typedef long long ll;

const int N = 1e7 + 5;

int t[N];
ll res;
ll tmp;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &t[i]);
    }
    sort(t, t + n);
    for (int i = 0; i < n; ++i) {
        res += tmp; // 第一次不用等
        tmp += t[i];
    }   
    printf("%lld\n", res);
    return 0;
}



delicacy
1个月前

AcWing 843. n-皇后问题

1_597ec77c49-8-queens.png

于同一行、同一列或同一斜线上。

1_597ec77c49-8-queens.png

现在给定整数 n,请你输出所有的满足条件的棋子摆法。

输入格式
共一行,包含整数 n。

输出格式
每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后,输出一个空行。

注意:行末不能有多余空格。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围
1≤n≤9
输入样例:
4
输出样例:
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

image-20210407194331056

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 50;

int n;
char g[N][N];
bool col[N], dg[N], udg[N]; // 列,对角线,反对角线

void dfs(int idx) {
    if (idx == n) { // 输出了
        for (int i = 0; i < n; ++i) {
            printf("%s\n", g[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (!col[i] && !dg[idx + i] && !udg[n - idx + i]) {
            g[idx][i] = 'Q';
            col[i] = dg[idx + i] = udg[n - idx + i] = true;
            dfs(idx + 1);
            col[i] = dg[idx + i] = udg[n - idx + i] = false; // 恢复现场 这步很关键
            g[idx][i] = '.';
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0 ; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i][j] = '.';
        }
    }
    dfs(0);
    return 0;
}



delicacy
1个月前

AcWing 842. 排列数字

给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。

现在,请你按照字典序将所有的排列方法输出。

输入格式
共一行,包含一个整数 n。

输出格式
按字典序输出所有排列方案,每个方案占一行。

数据范围
1≤n≤7
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include <iostream>
#include <cstdio>

using namespace std;

int n;
int a[15];
int vis[15];

void dfs(int idx) {
    if (idx == n + 1) { // 输出
        for (int i = 1; i <= n; ++i) {
            printf("%d ", a[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; ++i) {
        // 没有被访问过的话
        if (!vis[i]) {
            a[idx] = i; // 第idx 个数为i
            vis[i] = 1;
            dfs(idx + 1);
            vis[i] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(1);
    return 0;
}



delicacy
1个月前

区间合并

AcWing 803. 区间合并 pair排序

给定 n 个区间 [li,ri],要求合并所有有交集的区间。

注意如果在端点处相交,也算有交集。

输出合并完成后的区间个数。

例如:[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式
第一行包含整数 n。

接下来 n 行,每行包含两个整数 l 和 r。

输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。

数据范围
1≤n≤100000,
−109≤li≤ri≤109
输入样例:
5
1 2
2 4
5 6
7 8
7 9
输出样例:
3
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

vector<PII> input_vector;
vector<PII> output_vector;

int n; // 组数

void merge(vector<PII> segs) {
    sort(segs.begin(), segs.end()); // 从小到大了
    int l = -2e9, r = -2e9; // 缩放为左端的1个点
    vector<PII>::iterator it = segs.begin();
    for (it; it != segs.end(); ++it) {
        if (it->first > r) { // 不重合 新的区间左端点大于 r 
            // 插入大的
            l = it->first;
            r = it->second;
            output_vector.push_back(make_pair(it->first, it->second));
        } else { // 重合
            r = max(r, it->second);
        }
    }
}

int main() {
    scanf("%d", &n);

    while (n--) {
        int l, r;
        scanf("%d%d", &l, &r);
        input_vector.push_back(make_pair(l, r));
    }
    merge(input_vector);
    printf("%d\n", output_vector.size());
    return 0;
}



delicacy
1个月前

AcWing 801. 二进制中1的个数

给定一个长度为 n 的数列,请你求出数列中每个数的二进制表示中 1 的个数。

输入格式
第一行包含整数 n。

第二行包含 n 个整数,表示整个数列。

输出格式
共一行,包含 n 个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围
1≤n≤100000,
0≤数列中元素的值≤109
输入样例:
5
1 2 3 4 5
输出样例:
1 1 2 1 2
利用lowbix(x) {
    return x & (-x)
}
#include <iostream>
#include <cstdio>

using namespace std;

// 获取最低位的1 在哪里
// 2 & (-2) = 2
//          010
// (-2)补码 111
// =>       010

int lowbit(int x) {
    return x & (-x);
}

int n;
int x; // 要计算的数
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &x);
        int res = 0; // 结果
        while (x) {
            x -= lowbit(x);
            ++res;
        }
        printf("%d ", res);
    }
    return 0;
}


活动打卡代码 AcWing 1227. 分巧克力

delicacy
1个月前
#include<iostream>
#include<cstdio>

using namespace std;

const int N = 100010; 

int n, k;
int h[N], w[N];
int check(int mid) {
    int res = 0;
    for (int i = 0; i < n; ++i) {
        res += (h[i] / mid) * (w[i] / mid);
        if (res >= k) {
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &h[i], &w[i]);
    }
    int l = 1, r = 1e5;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    printf("%d\n", r);
    return 0;
}




delicacy
1个月前
#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1e5 + 10;

int n;
int h[N];

int check(int e) {
    for (int i = 1; i <= n; ++i) {
        e = e * 2 - h[i];
        if (e >= 1e5) {
            return 1;
        }
        if (e < 0) {
            return 0;
        }
    }
    return 1;
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &h[i]);
    }   
    int l = 0, r = 1e5;
    while(l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n", r);
    return 0;
}



活动打卡代码 AcWing 796. 子矩阵的和

delicacy
1个月前

796. 子矩阵的和

输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式
第一行包含三个整数n,m,q。

接下来n行,每行包含m个整数,表示整数矩阵。

接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。

输出格式
共q行,每行输出一个询问的结果。

数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例:
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例:
17
27
21
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1000 + 10;

int n, m, q;
int a[N][N], s[N][N];

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    while (q--) {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}



delicacy
2个月前

G_回文日期

【问题描述】
2020 年春节期间,有一个特殊的日期引起了大家的注意:2020 年 2 月 2
日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202,
恰好是一个回文数。我们称这样的日期是回文日期。
有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同,因为
不到 2 年之后就是下一个回文日期:20211202 即 2021 年 12 月 2 日。
也有人表示 20200202 并不仅仅是一个回文日期,还是一个 ABABBABA
型的回文日期。对此小明也不认同,因为大约 100 年后就能遇到下一个
ABABBABA 型的回文日期:21211212 即 2121 年 12 月 12 日。算不上 “千
年一遇”,顶多算 “千年两遇”。
给定一个 8 位数的日期,请你计算该日期之后下一个回文日期和下一个
ABABBABA 型的回文日期各是哪一天。
【输入格式】
输入包含一个八位整数 N,表示日期。
【输出格式】
输出两行,每行 1 个八位数。第一行表示下一个回文日期,第二行表示下
一个 ABABBABA 型的回文日期。

【样例输入】
20200202
【样例输出】
20211202
21211212

【评测用例规模与约定】
对于所有评测用例,10000101 ≤ N ≤ 89991231,保证 N 是一个合法日期的
8 位数表示。
测试数据
输入
10000101

输出
10000111
10100101
标准答案
10011001
10100101

正确做法

#include <time.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;


int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// 20211202
int check_huiwen(int x) {
    string str = "";
    while (x) {
        char ch = x % 10 + '0';
        str = str + ch;
        x /= 10;
    }
    if (str[0] == str[7] && str[1] == str[6] && str[2] == str[5] && str[3] == str[4]) {
        return 1;
    } else {
        return 0;
    }
}

int check_ABAB(int x) {
    string str = "";
    while (x) {
        char ch = x % 10 + '0';
        str = str + ch;
        x /= 10;
    }
    // ABABBABA
    if (str[0] == str[2] && str[0] == str[5] && str[0] == str[7] && str[1] == str[3] &&
        str[1] == str[4] && str[1] == str[6] && str[0] != str[1]) {
        return 1;
    } else {
        return 0;
    }
}
bool check_valid(int year, int month, int day) {
    if (month < 1 || month > 13) {
        return 0;
    }
    if (day < 1 || day > 31) {
        return 0;
    }
    if (month != 2) {
        if (day > days[month]) {
            return 0;
        }
    }
    // 闰年特判
    else {
        int leap = (year % 100 && year % 4 == 0) || (year % 400 == 0);
        if (day > 28 + leap) {
            return 0;
        }
        return 1;
    }
}
int main() {
    int num;
    cin >> num;
    // clock_t startTime, endTime;
    // startTime = clock();
    int huiwen_flag = 0;
    int ABAB_flag = 0;
    int huiwen = 0;
    int ABAB = 0;
    // 89991231
    // 100000000
    for (int i = num + 1; i <= 100000000; ++i) {
        int year = i / 10000;
        int month = i / 100 % 100;
        int day = i % 100;
        if (check_valid(year, month, day) == 0) {
            continue;
        }
        if (check_huiwen(i) && huiwen_flag == 0) {
            huiwen = i;
            huiwen_flag = 1;
        }
        if (check_ABAB(i) && ABAB_flag == 0) {
            ABAB = i;
            ABAB_flag = 1;
        }
        if (huiwen_flag == 1 && ABAB_flag == 1) {
            break;
        }
    }

    printf("%d\n", huiwen);
    printf("%d\n", ABAB);
    // endTime = clock();
    // cout << "Totle Time : " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
    // cout << CLOCKS_PER_SEC << endl;

    return 0;
}