标签：钉耙 index string int sum 编程 2024 ++ define

时间：07_29

05 多层血条

思路

就是模拟，上层和下层分开表示，如果dmg大于血条长度就全都置0，反之就要从上层开始置 \('.'\)

代码

string blood = "ABCDE";
string str[3];
void solve() {
    cin >> n >> m >> hp >> dmg;
    str[0] = "+" + string(m, '-') + "+";
    str[2] = "+" + string(m, '-') + "+";

    char down_ch = blood[max((hp / m - 1) % 5, 0LL)];
    char up_ch = 'N';
    int up_num = hp % m;

    if (up_num != 0 && hp > m) {
        up_ch = blood[((hp / m - 1) % 5 + 1) % 5];
    }

    str[1] = "|" + (up_ch == 'N' ? string(min(m, hp), down_ch) : string(up_num, up_ch) + string(min(hp, m) - up_num, down_ch));
    if (hp < m)
        str[1] += string(m - hp, ' ');
    str[1] += "|";

    if (dmg >= m) {
        for (int j = 1; j <= min(m, hp); j++) {
            str[1][j] = '.';
        }
    } else {
        if (up_ch == 'N') {
            for (int j = min(hp, m); j > 0 && dmg > 0; j--, dmg--) {
                str[1][j] = '.';
            }
        } else {
            for (int j = up_num; j >= 1 && dmg > 0; j--) {
                str[1][j] = '.';
                dmg--;
            }
            for (int j = m; dmg > 0; j--) {
                str[1][j] = '.';
                dmg--;
            }
        }
    }
    cout << str[0] << endl;
    for (int i = 0; i < n; i++)cout << str[1] << endl;
    cout << str[2] << endl;
}

09 昵称检索

标签：[[字符串]]、[[下标维护]]

题意

给一串小写字母和数字混合字符串 \(S\)

给一些长度在20以内的由小写字母组成的名字 \(name\)

将 \(S\) 删去任意字符最后要变成\(name+XXXX\) ，\(XXXX\) 表示合法的日期，比如0101,0229

输出有多少本质不同的合法串

1到100组数据，\(n,m (1≤n≤10^5, 1≤m≤10^6)\)，分别表示名字的数量以及字符串 \(S\) 的长度。

名字两两不同

\(∑m≤7000000\)，且 \(∑|name|≤7000000\)。

思路

我是先单独考虑名字，比如对一个名字，好像可以暴力处理出所有名字后面的数字

但是名字过多，思考能不能将每个名字的最后一位做标记，在标记后计算合法日期

由于暂时没找到好方法，我先往下一步，在一串数字串中找出合法日期

但是即使KMP也会因数字串过大超时，所以就没出来。。。

首先应该明确怎么样是最优情况

对于一个人名，应该是尽量往左才能有较多的数字供给匹配

同理对于合法数字也应该尽量出现在右边

那么再次考虑标记的操作

可以用 \(index[i][j]\) 存储 \(S\) 串中,从 \(i\) 往后 ， \(j\) 字符出现的最左下标

比如查找 "jack" 这个名字，首先查找 \(index[0]['j']=x\) ，然后查找 \(index[x]['a']\)

类似的，比如查找 "0218" 这个日期

就需要构建新的 \(index[i][j]\) 表示在 \(S\) 串中从前到 \(i\) 的 \(j\) 字符出现的最右下标

从 '8' 开始往前查

由于一年366天，用一个后缀和存储所有本质不同的日期的数量，根据名字的最后位置累加所有结果

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rep(i, j, k) for (i = (j); i < (k); i++)
const int N = 1e6 + 10;
int ii, jj, kk;

int nameNum, sLen;
string S;

int numStrNum = 0;
int mouth_day[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
vector<string> numStrs(366, "");
void buildNumStr() {
    int num = 0;
    for (int a = 0; a <= 1; a++)
        for (int b = 0; b <= 9; b++)
            for (int c = 0; c <= 3; c++)
                for (int d = 0; d <= 9; d++) {
                    int mouth = a * 10 + b;
                    int day = c * 10 + d;
                    if (mouth <= 12 && mouth > 0 && day > 0 && day <= mouth_day[mouth]) {
                        numStrs[num++] = to_string(a) + to_string(b) + to_string(c) + to_string(d);
                    }
                }
}

// 从 i往后  j字符出现的最左下标
// 下标从1开始到sLen
int index_name[N][26];
void build_index_name(string &S, int sLen) {
    for (int i = 0; i < 26; i++)
        index_name[sLen + 1][i] = 1e9;

    // 从后往前构建
    for (int i = sLen - 1; i >= 0; i--) {
        for (int j = 0; j < 26; j++)
            index_name[i + 1][j] = index_name[i + 2][j];

        if (islower(S[i]))
            index_name[i + 1][S[i] - 'a'] = i + 1;
    }
}

// 从前到i,j字符出现的最右下标
// 下标从1开始到sLen
int index_dig[N][10];
void build_index_dig(string &S, int sLen) {
    for (int i = 0; i < 10; i++)
        index_dig[0][i] = -1;

    for (int i = 0; i < sLen; i++) {
        for (int j = 0; j < 10; j++)
            index_dig[i + 1][j] = index_dig[i][j];

        if (isdigit(S[i]))
            index_dig[i + 1][S[i] - '0'] = i + 1;
    }
}

// 根据日期构建后缀和
int aft_sum[N];
void build_aft_sum(string &S, int sLen) {
	for (int i = 0; i <= sLen+1; i++)
        aft_sum[i] = 0;
	//从后往前找就行，如果找不到，也就是-1的情况，跳过这个日期
    for (string &ns : numStrs) {
        int pos4 = index_dig[sLen][ns[3] - '0'];
        if (pos4 == -1)continue;

        int pos3 = index_dig[pos4 - 1][ns[2] - '0'];
        if (pos3 == -1)continue;

        int pos2 = index_dig[pos3 - 1][ns[1] - '0'];
        if (pos2 == -1)continue;

        int pos1 = index_dig[pos2 - 1][ns[0] - '0'];
        if (pos1 == -1)continue;
        
        aft_sum[pos1]++;
    }

    for (int i = sLen - 1; i >= 0; i--)
        aft_sum[i] += aft_sum[i + 1];
}

int solve() {
    cin >> nameNum >> sLen;
    cin >> S;
	// 分别构建名字和数字的下标数组
    build_index_name(S, sLen);
    build_index_dig(S, sLen);

	// 根据已有的数字下标数组生成答案的后缀和
    build_aft_sum(S, sLen);

    string na;
    int ans = 0;
    for (int i = 0; i < nameNum; i++) {
        cin >> na;
        int pre = index_name[1][na[0] - 'a'];
        if (pre == 1e9)
            continue;
        int j;
        for (j = 1; j < na.size(); j++) {
            int now = index_name[pre + 1][na[j] - 'a'];
            if (now == 1e9)
                break;
            pre = now;
        }
        if (j == na.size())
            ans += aft_sum[pre + 1];
    }

    return ans;
}

signed main() {
    IOS;
    // 首先构建一个存储366个合法日期的数组
    buildNumStr();
    
    int t;
    for (cin >> t; t > 0; t--)
        cout << solve() << endl;
    return 0;
}

03 最优K子段

标签：[[前缀和]]、[[二分]]、[[set]]

题意

给定序列a，从中恰好找出k个不相交的连续字段，满足每一段长度都是质数

设每个子段的序列和为 \(s_i\) ，要最大化 \(min(s_1,s_2,...,s_k)\)

思路

二分最小子段和，用前缀和维护

可以用set维护前缀和，比如对于

6 3
-1 -1 -4 -5 -1 -4

维护前缀和，额外加一个0

 0  -1  -2 -6 -9 -10 -14
 -1  0   1  2  3  4   5

比如 \(mid=-2\) ，首先在set中插入{0,-1}，表示存储的前缀和为0，下标是-1，保证有初始值

然后选取{-1,0}，遍历set发现没有差值的大于-2的，将{-1,0}插入

然后选取{-2,1}，遍历发现对于{0,-1}，满足差值大于等于mid并且下标 \(1-(-1)=2\) 长度也是质数

所以将set清空，答案加1，注意无论是否匹配成功要再将{-2,1}插入

对于前缀和从小到大用set维护，二分时也从小到大

因为存在于set中的前缀和都是没被使用过的，并且所有子串不可重复

只要有任意一项能与当前位置匹配上，那么从当前往前的都不再有价值

所以从小到大判断，直到差值小于mid时直接退出当前的比较

代码

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define int long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rep(i, j, k) for (i = (j); i < (k); i++)
#define all(x) x.begin(), x.end()
#define pii pair<int, int>

const int MOD = 1000000007;
const int N = 2e5 + 10;

int n, k;
set<int> primes;
bool vis[N];
void e() {
    for (int i = 0; i < N; i++)
        vis[i] = 0;
    for (int i = 2; i < N; i++) {
        if (!vis[i])
            primes.insert(i);
        for (int j = i * i; j < N; j += i)
            vis[j] = 1;
    }
}

// 如果能找到比大于等于mid的解，就true
struct cmp {
    bool operator()(const pii &a, const pii &b) const { return a.F < b.F; }
};

bool check(int mid, int k, vector<int> &sum) {
    // 每次将前缀和存入数据结构，
    int cnt = k;
    // 存储前缀和和对应的下标
    set<pii, cmp> st;
    // 记得初始化一下
    st.insert({0, -1});
    for (int i = 0; i < sum.size(); i++) {
        if (st.empty()) {
            st.insert({sum[i], i});
            continue;
        }
        bool flag = false;
        for (auto &[s, index] : st) {
            // 如果匹配成功
            if (sum[i] - s >= mid && primes.find(i - index) != primes.end()) {
                st.clear();
                flag = true;
                cnt--;
                break;
            } else if (sum[i] - s < mid)
                break;
        }
        // 如果匹配失败
        st.insert({sum[i], i});
    }
    return cnt <= 0;
}

void solve() {
    cin >> n >> k;

    vector<int> v(n);
    for (auto &i : v) cin >> i;

    vector<int> sum(n);
    sum[0] = v[0];
    for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + v[i];

    // 二分
    int l = -1e9, r = 1e9;
    int ans = 1e10;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid, k, sum)) {
            l = mid + 1;
            ans = mid;
        } else
            r = mid - 1;
    }
    // 如果ans没变
    if (ans == 1e10) cout << "impossible" << endl;
    else cout << ans << endl;
}

signed main() {
    IOS;
    e();
    int t;
    for (cin >> t; t > 0; t--)
        solve();
    return 0;
}

标签：钉耙,index,string,int,sum,编程,2024,++,define
From： https://www.cnblogs.com/lulaalu/p/18340934

2024“钉耙编程”中国大学生算法设计超级联赛（4） 3、5、9

05 多层血条

思路

代码

09 昵称检索

题意

思路

代码

03 最优K子段

题意

思路

代码

相关文章

赞助商

阅读排行