J. Strange Sum

题意

给定序列 $a_1, a_2,\cdots,a_n$ 。

我们需要选择若干元素（可以不选），满足如果选择了 $a_i$ ，那么序列中所有长度为 $i$ 的区间中都最多只有两个元素被选择。

最大化选择的元素的和。

Solution

显然，考虑到假设我们选择的编号最大的元素为 $a_p$ ，那么区间 $[1, p]$ 中也应该最多两个元素。

所以，整个序列中我们最多选择两个元素。

因此，假设序列中最大、次大的两个数分别为 $b, c$ ，那么答案就是 $\max\{0, b,b + c\}$ 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int ans=0;
    ans+=max((long long)0,a[n-1]);
    ans+=max((long long)0,a[n]);
    cout<<ans<<'\n';
    return 0;
}

F - Hotel

现在酒店中有单人间和双人间，价格分别是c1，c2，现在有n个队，每队三个人，性别分别用字母表示，当两个人性别相同且在同一个队时，他们可以住在双人间中。求最少需要多少钱使得n个队住下。

#include <iostream>
#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve(){

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,c1,c2;
    cin>>n>>c1>>c2;
    int ans=0;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        sort(s.begin(),s.end());
        if(s[0]==s[1]&&s[0]!=s[2]){
            ans+=min(c1,c2);
            ans+=min(2*c1,c2);
        }
        else if(s[1]==s[2]&&s[0]!=s[1]){
            ans += min(c1,c2);
            ans += min(2 * c1, c2);
        }
        else if(s[0]==s[1]&&s[0]==s[2]){
            ans += min({3 * c1, 2*c2,c1+c2,2*c1+c2});
        }
        else if(s[0]!=s[1]&&s[1]!=s[2]){
            ans+=min(3*c1,3*c2);
        }
    }
    cout<<ans<<"\n";
    return 0;
}

C - Clone Ranran

有个人要准备c道题，他可以进行如下两种操作：花费a分钟克隆一个自己；花费b分钟准备一道题目。问准备c道题最少需要多长时间。

思路：最优选择一定是先尽可能快的克隆自己，然后最后一起花b分钟准备一道题，得到的计算式是 $a\times x+\lceil \frac{c}{2^x} \rceil \times b$ ， $x$ 是克隆的次数。

#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
    int a,b,c;
    cin>>a>>b>>c;
    int ans=b*c;
    for(int i=0;(1ll<<i)<2*c;i++){
        int t=i*a+((c+(1<<i)-1)/(1<<i))*b;
        ans=min(ans,t);
    }
    cout<<ans<<"\n";
    return ;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

E - Find Maximum

We define a function $f(x)$ over all non-negative integer $x$ as follows:

$f(x) = \begin{cases} 1 & (x = 0) \\ f(\frac{x}{3}) + 1 & (x > 0\land x\bmod3 = 0) \\ f(x - 1) + 1 & (x > 0\land x\bmod 3\neq 0) \end{cases}$
Calculate $\max_{x = l} ^ r f(x)$ .

You need to answer $T$ queries independently.

#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int,int> mp;
int f(int x){
    if(x==0) return 1;
    else if(x%3==0) return f(x/3)+1;
    else return f(x-1)+1;
}
vector<int> cal(int x){
    vector<int> res;
    while(x){
        res.push_back(x%3);
        x/=3;
    }
    if(res.size()==0) res.push_back(0);
    else reverse(res.begin(),res.end());
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int l,r;
        cin>>l>>r;
        vector<int> vr;
        vr=cal(r);
        int ans=max(f(l),f(r));
        int lenr=vr.size();
        int res=0;
        for(int i=0;i<lenr;i++){
            int res=0;
            if(vr[i]==0) continue ;
            for(int j=0;j<i;j++){
                res=res*3+vr[j];
            }
            res=res*3+vr[i]-1;
            for(int j=i+1;j<lenr;j++) res=res*3+2;
            if(res>=l) ans=max(ans,f(res));
        }
        cout<<ans<<'\n';
    }
    return 0;
}

G - Perfect Word

给出n个字符串，对于一个字符串，若它的所有子串都出现在了这n个字符串中，则称这个字符串是good的，则最大的good串的长度是多少。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5+5;
const int BASE = 131;
const int MOD = 1e9+7;

int n;

string s[MAXN];

struct node{
    int val,val1,val2;
    int len;
};
node nums[MAXN];
// bool ok[MAXN];
map<int,int>mp;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

bool cmp(node a,node b){
    return a.len<b.len;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        nums[i].len=s[i].length();
        // 计算整个字符串的哈希值
        int val=0;
        for(int j=0;j<nums[i].len;j++){
            val=(val*BASE+(s[i][j]-'a'+1))%MOD;
        }
        nums[i].val=val;
        // 计算去掉最后一个字符的哈希值（val1）
        val=0;
        for(int j=0;j<nums[i].len-1;j++){
            val=(val*BASE+(s[i][j]-'a'+1))%MOD;
        }
        nums[i].val1=val;
        // 计算去掉第一个字符的哈希值（val2）  
        val=0;
        for(int j=1;j<nums[i].len;j++){
            val=(val*BASE+(s[i][j]-'a'+1))%MOD;
        }
        nums[i].val2=val;
    }
    sort(nums+1,nums+n+1,cmp);

    int ans=0;
    for(int i=1;i<=n;i++){
        if(nums[i].len==1){
            mp[nums[i].val]=i; // 长度为1的字符串总是可构建
            ans=max(ans,nums[i].len);
        }
        else{
            int id1=mp[nums[i].val1];
            int id2=mp[nums[i].val2];
            if(id1&&id2&&(nums[id1].len==(nums[i].len-1))&&(nums[id2].len==(nums[i].len-1))){
                mp[nums[i].val]=i;
                ans=max(ans,nums[i].len);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

2022 ICPC 亚洲区域赛西安站