The 2022 ICPC Asia Xian Regional Contest

The 2022 ICPC Asia Xian Regional Contest

J. Strange Sum

题意：给定n个数，选定最多不超过两个数字的和的最大值

思路：签到

void solve(){
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    ll ans = 0;
    sort(a.begin() + 1, a.end(), greater<ll>());
    if(ans + a[1] > ans) ans += a[1];
    if(ans + a[2] > ans) ans += a[2];
    cout << ans << '\n';
}

F. Hotel

题意：给定n只队伍，每个队伍三人，同时单人间/双人间的售价分别是c1,c2，来自同一支队伍并且相同性别的可以住一间房，求最小花费

思路：要考虑双人间比单人间还便宜的情况

void solve(){
    ll n, c1, c2;
    cin >> n >> c1 >> c2;
    ll sum1 = 0, sum2 = 0;
    for(int i = 1; i <= n; i ++){
        string s;
        cin >> s;
        if(s[0] == s[1] || s[0] == s[2] || s[1] == s[2]){
            sum1 ++;
            sum2 ++;
        }
        else sum2 += 3;
    }
    ll ans = min(n * 3 * c1, n * 3 * c2);
    ans = min(ans, sum1 * c2 + sum2 * min(c1, c2));
    cout << ans << '\n';
}

C. Clone Ranran

题意：初始有一个人，可以花费a的时间把当前所有人都复制一遍，也就是人数翻倍，每个人造一道题目的花费是b时间，求造出c道题目花费的最少的时间

思路：枚举复制次数即可，O(logc)的复杂度，记得两种特殊情况，分别是不进行复制，直接一个人造c道题目，还有是复制到人数大于等于题数一次性造完所有题目

void solve(){
    ll a, b, c;
    cin >> a >> b >> c;
    ll sum = 1, ans = b * c, idx = 0;
    while(sum < c){
        sum *= 2;
        idx ++;
        ll res = c / sum + (c % sum != 0);
        res *= b;
        res += a * idx;
        ans = min(ans, res);
    }
    ll res = a * idx + b;
    ans = min(ans, res);
    cout << ans << '\n';
}

G. Perfect Word

题意：给定n个字符串，求最长完美单词的长度，完美单词的定义：它的所有非空子串都在整体的单词集合中出现过

思路：感觉很有意思的题目，可以发现，每一个完美单词的所有子串也肯定是完美单词，那么从小开始判断该单词是不是完美单词，直到找出最长的完美单词，等于是由小的完美单词推出大的完美单词，只要从小开始判断去掉第一个或者最后一个字母的单词是不是完美单词即可，不要忘了首先排个序，长度为1的特判，用map维护一个完美单词集合

bool cmp(string & s1, string & s2){
    return s1.size() < s2.size();
}

void solve(){
    int n;
    cin >> n;
    vector<string> v(n + 1);
    map<string, int> mp;
    for(int i = 1; i <= n; i ++) cin >> v[i];
    sort(v.begin() + 1, v.end(), cmp);
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        string s = v[i];
        if(s.size() == 1){
            mp[s] = 1;
            continue;
        }
        string s1 = s.substr(0, s.size() - 1);
        string s2 = s.substr(1, s.size() - 1);
        if(mp.count(s1) && mp.count(s2)){
            mp[s] = 1;
            int len = s.size();
            ans = max(ans, len);
        }
    }
    cout << ans << '\n';
}

pending。。。。。。