A – PENTA KILL!

题目描述：

问你是否存在一个区间内，满足一个人杀了五个不同的人，这之间无论其他人杀了什么人，或者这个人死了多少次，都不影响，会影响的是重复杀了之前杀过的人，比如杀的顺序是ABCAD，杀了两次A，所以不是五杀

思路：

枚举五杀区间的起点，模拟就行

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
struct ran{
    string s, t;
}tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i].s >> tr[i].t;
    for(int i = 1; i <= n; ++i){
        set<string>s;
        bool p = 0;
        for(int j = i; j <= n; ++j){
            if(tr[i].s != tr[j].s)continue;
            if(s.count(tr[j].t)){
                break;
            }
            else s.insert(tr[j].t);
            if(s.size() == 5){
                p = 1;
                break;
            }
        }
        if(p){
            cout << "PENTA KILL!\n";
            return;
        }
    }
    cout << "SAD:(\n";
}


int main(){
    io;
    work();
    return 0;
}

C – Jump and Treasure

题目描述：

给定一个长度为n的数组代表i位置的物品价值，给出一步所能跳的最远的距离k，

进行q次询问，每次询问都告诉你一个最小跳跃距离x，问你从0开始怎么跳到终点后到价值最大

思路：

对于一个x，我们可以算出来1-n中是x的倍数的点，这些点是可以走的，还可以计算出一次最远可以走k/x个点，显然可以用dp来做，每个点可以由前面的k/x个点转移过来

但是q次询问,暴力转移的复杂度是O(TLE),我们需要考虑进行优化

可以发现我们只需要知道从i-1往前的k/x个dp中的最大值就行，我们可以用单调队列来维护

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define int long long
#define MAX 1000000 + 50
int n, m, p, x;
int tr[MAX];
int dp[MAX];
int ar[MAX];
int ans[MAX];
int fuck(int x){
    if(ans[x])return ans[x];
    int tot = 0;
    for(int i = x; i <= n; i += x){
        ar[++tot] = tr[i];
    }
    int k = p  / x;
    dp[0] = 0;
    deque<int>q;q.push_back(0);
    for(int i = 1; i <= tot; ++i){
        while(!q.empty() && i - q.front() > k)q.pop_front();
        dp[i] = dp[q.front()] + ar[i];
        while(!q.empty() && dp[i] > dp[q.back()])q.pop_back();
        q.push_back(i);
    }
    if(!q.empty() && n + 1 - q.front() * x > p)q.pop_front();
    ans[x] = dp[q.front()];
    return ans[x];
}

void work(){
    cin >> n >> m >> p;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
    }
    while(m--){
        cin >> x;
        if(x > p)cout << "Noob\n";
        else cout << fuck(x) << endl;
    }
}

signed main(){
    io;
    work();
    return 0;
}

I – Cutting Suffix

题目描述：

给定一个字符串，你需要构造两个下标的集合T1,T2，使得每个字符的下标都只属于其中的一个组合，对于每个下标i，记f[i]是i-n的字符串,v(i,j)为f[i]和f[j]的最长公共前缀 ，现在需要计算 $\sum_{i∈T1}\sum_{j∈T2}$的最小值

思路：

题意写的很牛，但是仔细想想就能发现，我们可以自己构造集合，所以可以让所有的相同的某种字符都放在T1里面，其他的全放在T2,这样能保证第一个字符永远不相同，就保证答案是0

但是如果只存在一种字符，那答案就是n-1，因为我们可以只在T1中放一个字符，其他的字符全放在T2,这样答案就是n-1,一定是最小的

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
string s;

void work(){
    cin >> s;
    set<char>se;
    for(auto x : s)se.insert(x);
    if(se.size() > 1)cout << 0 << endl;
    else cout << (int)s.size() - 1 << endl;
}


int main(){
    io;
    work();
    return 0;
}

J – Balanced Tree

题目描述：

给你n个点，你要造出n个点的二叉树，而且必须满足每个节点他的两个子树的节点的数量差小于等于1，问存在多少种方式

思路：

用记忆化达打表找规律以后可以发现 $2^i-1$的答案一定是1，他往上和往下的若干个数字的答案不是0，其他的都是0，而且数字越大，周围不是0的答案的数量越少，所以预处理出来所有有答案的就行

还有就是这个题要对$2^{64}$取模，我们可以直接用unsigned long long

用-1赋值给ull的变量，就能得到 $2^{64}-1$

注意给0的答案赋值为1

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef unsigned long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n;

map<ll, ll>mp;
ll dfs(ll x){
    if(mp.count(x))return mp[x];
    if(x % 2 == 1)mp[x] = dfs(x/2) * dfs(x/2);
    else mp[x] = dfs(x/2) * dfs(x/2-1) * 2ll;
    return mp[x];
}

void work(){
    mp[0] = 1;
    mp[1] = 1;mp[2] = 2;mp[3] = 1;
    for(ll i = 1; i < 64; ++i){
        ll p = (1ll << i)-1;
        mp[p] = 1;
        --p;
        while(p >= 1 && dfs(p) != 0)--p;
        p = (1ll << i);
        while(dfs(p) != 0)++p;
    }
    ll p = -1;
    while(dfs(p))--p;
    int t;cin>>t;
    while(t--){
        cin >> n;
        if(mp.count(n))cout << mp[n] << endl;
        else cout << 0 << endl;
        
    }
}


int main(){
    io;
    work();
    return 0;
}

K – aaaaaaaaaaA heH heH nuN

题目描述：

一个字符串的前半部分是nunhehheh,后半部分是长度不为0的全为a的串被认为是符合要求的，你需要构造一个字符串，使得它存在n个子序列是符合要求的

思路：

首先肯定得有nunhehheh，在这基础上，我们可以通过在后面加h和a来构造，在满足前面有nunhehe的后面的每个h，假设它后面有p个a，则能贡献 $2^p-1$个答案

也就是说我们可以通过利用$2^i-1$来构造，不足的我们可以用多个1来补足，即在最后类似用hhhhhha这样的来构造需要的数字

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    int num = 0;
    cin >> n;
    vector<int>v;
    for(int i = 30; i >= 2 && n; --i){
        if(n >= (1<<i)-1){
            n -= (1<<i)-1;
            v.push_back(i);
        }
    }
    reverse(v.begin(), v.end());
    string ans = "";
    num = 0;
    if(n){
        ans.push_back('a');
        num = 1;
        if(v.size())while(n--)ans.push_back('h');
        else{
            --n;
            while(n--)ans.push_back('h');
        }
    }
    for(int i = 0; i < v.size(); ++i){
        x = v[i];
        while(num < x){
            ans.push_back('a');
            ++num;
        }
        if(i != (int)v.size() - 1)ans.push_back('h');
    }
    reverse(ans.begin(), ans.end());
    ans = "nunhehheh" + ans;
    cout << ans << endl;
}

int main(){
    io;
    int t;cin>>t;while(t--)
    work();
    return 0;
}

L – Collecting Diamonds

题目描述：

给你一个只有ABC三种字符组成的字符串，对于每个相连的ABC字符，如果A的字符的下标是奇数，则可以删掉对应的A和C，否是会删掉B

问最多能进行多少次删除操作

思路：

显然，我们需要把字符串分成若干个小的字符串，形如AAAABCCCC这样的

我们可以发现：

• 删除AC不会改变前面和后面的下标的奇偶性质，只会改变B的下标的奇偶性，而改变了奇偶性后就不能连续删AC
• 删除B则会改变后面的奇偶性，而且删除B后这一段就不能再删了

所以一个比较好的策略是我们能先删AC就先删AC，最后一步能删B就删B，而每次删完AC后如果想再删AC就需要改变一下奇偶性，即删一次前面的B,我们只需要计算前面最多能删多少个B，已经当前B前面的A的数量进行一些比较就可以计算出该段的可以产生的答案是多少，即min(num + (i%2==0)+1, len)，num是前面可以删除的B的数量，i是B的下标，len是B前面的连续的A和后面的连续的 C的数量最小值

我们不用管最大的答案是怎样产生的，只需要知道能通过删B来进行改变奇偶性即可

最开始能删除的B的数量是0，每次遇到B的时候我们进行判断：

• 如果num是0，我们就去判断一下当前的B的下标，

  • 如果是奇数，则只能删B，我们给ans++，num++，

  • 如果是偶数，则只能删AC,

    • 如果len等于1的话，就只能删一次AC，给ans++，
    • 如果len>1，由于前面没有能删的B，我们最多只能删两次，一次AC，一次B,所以ans+=2,num++

• 对于num!=0的时候

  • 我们直接计算min(num + (i%2==0)+1, len)即可

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    string s;
    cin >> s;
    n = (int)s.size();
    s = " " + s;
    vector<pii>v;
    for(int i = 1; i <= n; ++i){
        if(s[i] != 'B')continue;
        int l = i, r = i;
        while(l - 1 >= 1 && s[l-1] == 'A')--l;
        while(r + 1 <= n && s[r + 1] == 'C')++r;
        if(min(i-l, r-i))v.push_back(m_p(min(i-l, r-i), i%2));
        i = r;
    }
    int ans = 0, num = 0;
    for(auto [x, y] : v){
        if(num == 0){
            if(y == 0){
                if(x == 1)++ans;
                else {
                    ans += 2;
                    ++num;
                }
            }
            else {
                ++ans;
                ++num;
            }
        }
        else{
            ans += min(x, (y == 0) + num + 1);
            ++num;
        }
    }
    cout << ans << endl;
}

int main(){
    io;
    work();
    return 0;
}