亦云
1分钟前

第十五届 四川省大学程序设计大赛

J. 余料建造

Cuber QQ 会给定一个初始长度为 n 的字符串 S 与一个初始为空的字符串 T ,你可以进行 n 次操作,每次
操作可以选择从 S 的头部或者尾部取出一个字符,并将其添加到 T 的尾部。
现在 Cuber QQ 想请你构造出字典序最小的 T。
Input
第一行一个整数n(1≤ n ≤ 2 × 1e6),表示字符串的长度。
第二行一个字符串 S,保证 S 中只包含大小写英文字母。
Output
一行一个字符串T,表示答案。
Example

standard input standard output
6
ACDBCB ABCBCD

Note
对于两个字符串 S = s1 s2 … sn 以及 T = t1 t2 … tm,如果在 ST 从左往右第一个出现不同的位置 x

上有 sx < tx,或者 ST 的前缀目 S 的长度小于 T ,那么我们说 S 的字典序小于 T 的字典序。

code:

#include<iostream>

using namespace std;

int main()
{
    int n;
    string s;
    cin >> n >> s;

    for(int i = 0, j = n - 1; i <= j;)
    {
        if(s[i] < s[j])cout << s[i++];
        else if(s[i] > s[j])cout << s[j--];
        else{
            int l = i, r = j;
            char min = s[i];
            while(l <= r && s[l] == s[r] && s[l] <= min){
                min = s[l];
                cout << s[l];
                l++;
                r--;
            }
            if(l > r) i = l;
            else if(s[l] < s[r]) i = l;
            else if(s[l] > s[r]) j = r;
            else{
                int t_l = l, t_r = r;
                while(t_l <= t_r){
                    if(s[t_l] < s[t_r])
                    {
                        i = l;
                        break;
                    }else if(s[t_l] > s[t_r]){
                        j = r;
                        break;
                    }
                    t_l++;
                    t_r--;
                }
                if(t_l > t_r) i = l;
            }
        }
    }
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        char[] s = scan.next().toCharArray();
        int cnt = 0;
        for(int i = 0, j = n - 1; i <= j;){
            if(s[i] < s[j]) System.out.print(s[i++]);
            else if(s[j] < s[i]) System.out.print(s[j--]);
            else {
                int l = i, r = j;
                char min = s[i];
                while (l <= r && s[l] == s[r] && s[l] <= min){
                    min = s[l];
                    System.out.print(s[l]);
                    l++;
                    r--;
                }
                if(l > r) i = l;
                else if(s[l] < s[r]) i = l;
                else if(s[r] < s[l]) j = r;
                else {
                    int tl = l;
                    int tr = r;
                    while(tl <= tr){
                        if(s[tl] < s[tr]){
                            i = l;
                            break;
                        }
                        else if(s[tr] < s[tl]){
                            j = r;
                            break;
                        }
                        tl++;
                        tr--;
                    }
                    if(tl > tr) i = l;
                }
            }
        }
    }
}


新鲜事 原文

Tao_34
8分钟前
AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/150323/



小吴同学
11分钟前

1 分析

  • 题意:给定n个点的带权无向图,点的坐标:0 ~ n-1,求从起点(0)到终点(n-1)的最短Hamilton路径
  • Hamilton路径:从0到n-1,不重不漏地经过每个点,俗称“旅行商问题”
  • “旅行商问题”,是NP完全问题,已被证明目前的做法,无法在一个多项式的时间内求出来,即没有一个多项式级别的算法,只能考虑暴力做法
  • 通过DFS,纯暴力的做法,时间复杂度$O(n * n!)$,数据范围是20,则会超时,所以需要通过剪枝优化:
    • 在已遍历t个点时,前t个点内部的遍历顺序,对于后面n-t个点的Hamilton距离没有影响
    • 在DFS时,只关心现在已用过那些点,以及最后停在哪个点上,不关心已用过点的顺序
  • 所以关键点:
    • 哪些点被用过(用和不用两个状态,一共20个点)
    • 目前停在哪个点上
  • 根据以上的2个关键点,总共的状态量 = $2^{20} * 20 \approx 2 * 10^7$,可以接受的范围
  • 状态(f[state_j][j])表示:当前已用过的点的状态为state_j,且当前停在j这个点上
  • 状态计算:枚举从哪个状态转移到当前状态,假设从k点转移过来,则
    • f[state_j][j] = f[state_k][k] + weight[k][j]
    • state_k = state除掉j之后的集合,且包含k
    • 用20位二进制整数表示state,当某一位为1时,表示存在,0则表示不存在,即“状态压缩”
    • 整个的时间复杂度 = 状态的数量 * 状态转移的复杂度 = $2 * 10^7 * 20$ = $4 * 10^8$。本题时间限制为5秒,可以计算$5 * 10^8$,不会超时

2 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20, M = 1 << 20;

int n;
// 一般将大数组开到全局变量中,而非函数内部,防止爆空间导致错误
int f[M][N], weight[N][N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            cin >> weight[i][j];

    memset(f, 0x3f, sizeof f);
    // 最开始在0号点,所以状态是1,且还没有走过,所以初始化成0
    f[1][0] = 0;
    for (int i = 0; i < 1 << n; i ++)
        for (int j = 0; j < n; j ++)
            // 判断i的二进制表示中,第j位是不是1,若是1则该状态合法,需要计算f[i][j]
            if (i >> j & 1)
                // 枚举所有转移过来的状态
                for (int k = 0; k < n; k ++)
                    // 判断i的二进制表示中,去掉第j位后的第k位是不是1。
                    // 若是,则合法
                    if (i - (1 << j) >> k & 1)  // 减法优先级>位移运算>逻辑运算,所以先计算减法
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + weight[k][j]);

    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}



[蓝桥杯 2022 国 B] 最大数字

题目描述

给定一个正整数 $N$。你可以对 $N$ 的任意一位数字执行任意次以下 2 种操作:

  1. 将该位数字加 $1$。如果该位数字已经是 $9$,加 $1$ 之后变成 $0$。

  2. 将该位数字减 $1$。如果该位数字已经是 $0$,减 $1$ 之后变成 $9$。

你现在总共可以执行 $1$ 号操作不超过 $A$ 次,$2$ 号操作不超过 $B$ 次。

请问你最大可以将 $N$ 变成多少?

输入格式

第一行包含 3 个整数:$N$,$A$,$B$ 。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

123 1 2

样例输出 #1

933

提示

【样例说明】

对百位数字执行 $2$ 次 $2$ 号操作,对十位数字执行 $1$ 次 $1$ 号操作。

【评测用例规模与约定】

对于 $30 \%$ 的数据,$1 \leq N \leq 100 ; 0 \leq A, B \leq 10$

对于 $100 \%$ 的数据, $1 \leq N \leq 10^{17} ; 0 \leq A, B \leq 100$

蓝桥杯 2022 国赛 B 组 D 题。


贪心

要让 $N$ 最大,考虑让其前面的位数尽可能多地为‘9’

1. 能通过+的方式到9
2. 能通过-的方式到9
3. 都不能,则判断+的方式得到的数与-的方式得到的数孰大孰小

由于数据范围只有 $17$ 位,$dfs$ 即可

C++ 代码

#include <iostream>

using namespace std;

typedef long long ll;

string num, str(20, 0);
int n, m;
ll res;

void dfs(int x, int a, int b)
{
    // 边界
    if(x == num.size() + 1) {
        ll sum = 0;
        for(int i = 0; i < num.size(); i ++) 
            sum = 10 * sum + (str[i] - '0'); 

        res = max(res, sum);
        return; 
    }

    str[x - 1] = '9';

    // 无需操作,这处可以不判断
    if(num[x - 1] == '9') 
        dfs(x + 1, a, b);

    // -
    if('9' - num[x - 1] <= a) 
        dfs(x + 1, a - '9' + num[x - 1], b); 
    // +
    if(num[x - 1] - '0' + 1 <= b) 
        dfs(x + 1, a, b - num[x - 1] + '0' - 1); 

    // +/-
    if('9' - num[x - 1] > a && num[x - 1] - '0' + 1 > b)
    {
        str[x - 1] = num[x - 1] + a;
        dfs(x + 1, 0, b);
        str[x - 1] = num[x - 1] - b;
        dfs(x + 1, a, 0);
    }
}

int main()
{
    cin >> num >> n >> m;

    // 记录第几位,a,b 
    dfs(1, n, m);

    cout << res << endl;

    return 0;
}



public static int find(int x){
        if(p[x]!=x){
            p[x]=find(p[x]);
        }
        return p[x];//return x;和这个有什么区别呢
    }



思路: 线段树 (区间更新)

区间更新模板

参考: 题解: AcWing 243. 一个简单的整数问题2 (线段树区间插入)

插入 操作 换成 更新 操作;

代码实现:

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

#define lson rt<<1
#define rson rt<<1|1
#define mid (l+r)>>1

const int N = 1e5 + 10;
int _, n, m;

typedef long long ll;

ll tr[N << 2], lz[N << 2];

void up(int rt) {
    tr[rt] = tr[lson] + tr[rson];
}

void down(int rt, int l, int r) {
    if (lz[rt] != 0) {
        int m = mid;

        lz[lson] = lz[rt];
        tr[lson] = (m - l + 1) * lz[rt];

        lz[rson] = lz[rt];
        tr[rson] = (r - m) * lz[rt];

        lz[rt] = 0;
    }
}

void insert(int rt, int l, int r, int x, int y, ll v) {
    if (l == x && r == y) {
        tr[rt] = (r - l + 1) * v;
        lz[rt] = v;
        return;
    }

    down(rt, l, r);
    int m = mid;

    if (y <= m)
        insert(lson, l, m, x, y, v);
    else if (x > m)
        insert(rson, m + 1, r, x, y, v);
    else
        insert(lson, l, m, x, m, v),
        insert(rson, m + 1, r, m + 1, y, v);
    up(rt);
}

ll calc(int rt, int l, int r, int x, int y) {
    if (x == l && r == y) 
       return tr[rt];

    down(rt, l, r);
    int m = mid;
    if (y <= m)
        return calc(lson, l, m, x, y);
    else if (x > m)
        return calc(rson, m + 1, r, x, y);
    else 
        return calc(lson, l, m, x, m) + calc(rson, m + 1, r, m + 1, y);

}

void solve(int index) {
    memset(tr, 0, sizeof tr);
    memset(lz, 0, sizeof lz);
    cin >> n >> m;
    insert(1, 1, n, 1, n, 1);
    while (m--) {
        int x, y, t;
        cin >> x >> y >> t;
        insert(1, 1, n, x, y, t);
    }

    printf("Case %d: The total value of the hook is %lld.\n", index, calc(1, 1, n, 1, n));
}

int main() {
    cin >> _;
    for (int i = 1; i <= _; i++) 
        solve(i);
    return 0;
}



思路: 线段树 (区间插入, 区间查询)

区间插入板子

还不会线段树的看这里: https://www.bilibili.com/video/BV1qY411n7Qs/?share_source=copy_web&vd_source=fcfe5417126b8b1ac8277353f33dc3e0

线段树节点:

struct Node {
    int L, R;
    ll lazy;    // 懒标记 
    ll val;     // 区间和 
} tr[N << 2];

懒标记的作用: 我们进行区间插入的时候, 比如说我们在 [1, 223] 这个区间插入 5, 那么在线段树中, 这个 [1, 223] 区间可能会被分解成 [1,128], [129, 192], [193, 208], [209, 216], [217, 220], [221, 222], [223, 223] 这样几个区间; 我们递归到 [1, 128] 这个节点时, 当前节点的区间被包含在插入区间 [1, 223] 中, 也就是当前区间的每一位我们都插入一个 5, 我们令当前区间的lazy += 5, 表示当前区间的每一位都插入一个 5, 这样就不需要再往下递归;

insert() 方法, 就是实现上述的逻辑:

// 插入 
void insert(int rt, int x, int y, int v) {
    if (l == x && r == y) {
        tr[rt].lazy += v;
        tr[rt].val += (r - l + 1L) * v;
        return;
    }

    down(rt);
    int m = mid;

    if (y <= m)
        insert(lson, x, y, v);
    else if (x > m)
        insert(rson, x, y, v);
    else 
        insert(lson, x, m, v), 
        insert(rson, m + 1, y, v);

    up(rt);
}

可以发现, 除了上述逻辑, 每到一个节点, 我们都会做一个 down() 的动作:

// push_down(), 父节点懒标记下传 
void down(int rt) {
    // 当前区间有懒标记 
    if (tr[rt].lazy != 0) {
        ll lz = tr[rt].lazy;
        // 下传给左孩子 
        tr[lson].lazy += lz;
        tr[lson].val += (tr[lson].R - tr[lson].L + 1) * lz; 
        // 下传给右孩子 
        tr[rson].lazy += lz;
        tr[rson].val += (tr[rson].R - tr[rson].L + 1) * lz; 
        // 下传完清空当前节点的懒标记 
        tr[rt].lazy = 0;
    }
}

它的作用是把父节点懒标记下传, 通过这样 懒住下传 的操作, 我们才能实现 区间插入 的操作的时间复杂度趋近于 log 级别

完整代码实现:

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define lson rt<<1                  // 左孩子下标 
#define rson rt<<1|1                // 右孩子下标 
#define mid (tr[rt].L+tr[rt].R)>>1  // 区间 [L, R] 的中点 
#define l tr[rt].L                  // 节点区间 [L, R] --> [l, r] , coding 比较方便 
#define r tr[rt].R

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
int _, n, m;

struct Node {
    int L, R;
    ll lazy;    // 懒标记 
    ll val;     // 区间和 
} tr[N << 2];

// 建树 
void build(int rt, int L, int R) {
    tr[rt] = {L, R};
    if (l == r)
        return ;
    int m = mid;
    build(lson, l, m);
    build(rson, m + 1, r);
}

// push_up() 方法, 孩子向父节点传递数据 
void up(int rt) {
    tr[rt].val = tr[lson].val + tr[rson].val;
}

// push_down(), 父节点懒标记下传 
void down(int rt) {
    // 当前区间有懒标记 
    if (tr[rt].lazy != 0) {
        ll lz = tr[rt].lazy;
        // 下传给左孩子 
        tr[lson].lazy += lz;
        tr[lson].val += (tr[lson].R - tr[lson].L + 1) * lz; 
        // 下传给右孩子 
        tr[rson].lazy += lz;
        tr[rson].val += (tr[rson].R - tr[rson].L + 1) * lz; 
        // 下传完清空当前节点的懒标记 
        tr[rt].lazy = 0;
    }
}

// 插入 
void insert(int rt, int x, int y, int v) {
    if (l == x && r == y) {
        tr[rt].lazy += v;
        tr[rt].val += (r - l + 1L) * v;
        return;
    }

    down(rt);
    int m = mid;

    if (y <= m)
        insert(lson, x, y, v);
    else if (x > m)
        insert(rson, x, y, v);
    else 
        insert(lson, x, m, v), 
        insert(rson, m + 1, y, v);

    up(rt);
}

// 查询方法 
ll calc(int rt, int x, int y) {
    if (x == l && y == r)
        return tr[rt].val;
    down(rt);
    int m = mid;
    if (y <= m)
        return calc(lson, x, y);
    else if (x > m)
        return calc(rson, x, y);
    else 
        return calc(lson, x, m) + calc(rson, m + 1, y);
}

void solve() {
    cin >> n >> m;
    build(1, 1, n);
    ll t;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        insert(1, i, i, t);
    }

    while (m--) {
        string op;
        ll x, y, t;
        cin >> op;

        if ("C" == op) {
            cin >> x >> y >> t;
            insert(1, x, y, t);
        } else {
            cin >> x >> y;
            cout << calc(1, x, y) << endl;
        }
    }
}

int main() {
//  IOS
//  cin >> _;
//  for (int i = 1; i <= _; i++)
    solve();
    return 0;
}




FrankieNCU
51分钟前

stack

#include <cstdio>
#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;
stack<char> stk;
unordered_map<char, char> mapping = {
    {'>', '<'}, {')', '('}, {'}', '{'}, {']', '['}
};
bool flag = true;

bool check(char c) {
    if ( c == '<' || c == '(' || c == '{' || c == '[' ) return true;
    return false;
}

int main() {
    string s;
    cin >> s;

    for ( int i = 0; i < s.size(); i++ ) {
        if ( check(s[i]) ) {
            stk.push(s[i]);
        }
        else {
            if ( stk.size() && stk.top() == mapping[s[i]] ) stk.pop();
            else flag = false;
        }
        if ( !flag ) break;
    }
    if ( stk.size() ) flag = false;
    if ( flag ) puts("yes");
    else puts("no");

    return 0;
}



汪汪汪总
52分钟前

题目描述

筛质数


算法1

埃氏筛法

Python 代码

# 埃氏筛选
# n = int(input())
# st = [False] * (n + 1)  # st[i]有没有被筛过
# primes = []
# cnt = 0  # 第几个质数
# for i in range(2, n + 1):
#     if not st[i]:  # 第i个没有被筛掉,说明ta是质数
#         primes.append(i)
#         cnt += 1
#     j = 2
#     while j * i <= n:
#         st[j * i] = True
#         j += 1
# print(cnt)

# 优化
n = int(input())
st = [False] * (n + 1)  # st[i]有没有被筛过
cnt = 0  # 第几个质数
for i in range(2, n + 1):
    if not st[i]:  # 第i个没有被筛掉,说明ta是质数
        cnt += 1
        # 优化:将这个循环放进来
        # 只用将质数的j倍筛掉
        j = 2
        while j * i <= n:
            st[j * i] = True
            j += 1
print(cnt)

算法2

线性筛法

Python 代码

# 埃氏筛选
n = int(input())
# n = 36
st = [False] * (n + 1)  # st[i]有没有被筛过
primes = []
cnt = 0  # 第几个质数
for i in range(2, n + 1):
    if not st[i]:  # 第i个没有被筛掉,说明ta是质数
        cnt += 1
        primes.append(i)

    j = 0
    while primes[j] <= n // i:
        st[primes[j] * i] = True
        # print(i, j, primes[j], primes[j] * i)
        if i % primes[j] == 0:
            break
        j += 1

print(cnt)
# print(primes)
"""
和埃氏筛法的区别在于
埃氏筛法里有些数字会被筛多次,
比如14,质数选到2的时候会被筛一次,选到7的时候又会被筛一次
而线性筛法就会避免掉这种情况,保证每个合数都是被它最小的质因子筛掉
比如14,只会在i=7,然后primes[j]是2的时候被筛掉
也就是每一次都是拿i去遍历乘primes中的质数,筛掉数字 st[primes[j] * i] = True
i % primes[j] == 0:成立,说明primes[j] 的质因子,
再向后遍历到primes[j+1]得到的 primes[j+1] * i 的最小质因子就不是primes[j+1]了
比如,primes[j] =2,i = 6,primes[j] * i = 12
primes[j + 1] * i = 3 * 6 = 18,
3不是18的最小质因子,因为 i=6里面有2了
"""



FrankieNCU
1小时前

二分+字符串哈希

#include <cstdio>
#include <iostream>

using namespace std;
typedef unsigned long long ULL;
const int N = 110, P = 13331;
ULL h1[2*N], h2[2*N], p[2*N];
string s1, s2, res;


ULL get_hash(int l, int r, int target) {
    if ( target == 1 ) {
        return h1[r] - h1[l - 1] * p[r - l + 1];
    }
    else if ( target == 2 ) {
        return h2[r] - h2[l - 1] * p[r - l + 1];
    }
    else {
        puts("Error target number");
        system("pause");
    }
}

bool check(int mid) {
    for ( int i = 1; i < s1.size() - mid + 1; i++ ) {
        for ( int j = 1; j < s2.size() - mid + 1; j++ ) {
            if ( get_hash(i, i + mid - 1, 1) == get_hash(j, j + mid - 1, 2) ) return true;
        }
    }
    return false;
}

int main() {

    cin >> s1 >> s2;
    p[0] = 1;
    for ( int i = 1; i <= N; i++ ) {
        h1[i] = h1[i - 1] * P + s1[i - 1];
        h2[i] = h2[i - 1] * P + s2[i - 1];
        p[i] = p[i - 1] * P;
    }
    int l = 0, r = min(s1.size(), s2.size());
    while ( l < r ) {
        int mid = l + r + 1 >> 1;
        if ( check(mid) ) l = mid;
        else r = mid - 1;
    }
    for ( int i = 1; i < s1.size() - r + 1; i++ ) 
        for ( int j = 1; j < s2.size() - r + 1; j++ )  
            if ( get_hash(i, i + r - 1, 1) == get_hash(j, j + r - 1, 2) )
                res = s1.substr(i - 1, r);

    cout << r << endl << res << endl;

    return 0;
}