C-LCS

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

　　让你构造三个长度为 ​ 的字符串。要求 ​ 与 ​ 相同的字符数量为 ​，​ 与 ​ 相同的字符数量为 ​， ​ 与 ​ 相同的字符数量为 ​。

　　将 ​、​、​​从小到大排序，将长度为最小值的 'a' 串推入三个字符串，再向第二小的数所对应的两个字符串推入数量为 第二小的数减去最小数 的 'b' 串，最大同理(推入 'c' 串)。最后将长度不足 的串进行补充，每个串补充的部分必不相同，如果碰到长度已经超过 的串，则判定为不可能。

代码: 

#include<bits/stdc++.h>

using namespace std; 
using ld=long double; using ll=long long; using ull=unsigned long long; using pii=std::pair<int, int>; using pll=std::pair<long long, long long>; using pil=std::pair<int, long long>; using pli=std::pair<long long, int>; 

int main() { 
    ios::sync_with_stdio(false); cin.tie(0); 
    string s[3]; 
    pii li[3]; 
    int n, cnt=1; 
    cin>>li[0].first>>li[1].first>>li[2].first>>n; li[0].second=0, li[1].second=1, li[2].second=2; 

    sort(li, li+3); 

    for(int j=0; j<3; j++) for(int i=1; i<=li[0].first; i++) s[j]+='a'; 
    for(int i=1; i<3; i++) { 
        int a=li[i].second, b=(a+1)%3; 
        for(int j=1; j<=li[i].first-li[0].first; j++) s[a]+=('a'+i), s[b]+=('a'+i); 
    } 
    for(int i=0; i<3; i++) { 
        int j=s[i].length(); 
        if(j>n) { 
            puts("NO"); 
            return 0; 
        } 
        while(j<n) s[i]+=('c'+cnt), j++; 
        cnt++; 
    } 
    for(int i=0; i<3; i++) cout<<s[i]<<endl; 

    return 0; 
}

F-Just a joke

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

　　轮流操作，每人每次可删除一条边或一组点和边，要求这组点内任意两点间有通路，且每个点的入/出度不能超过 2，先删完所有点和边的人获胜。

　　队友打表发现，无论如何操作，当且仅当 为奇数时，先手能获胜。

　　于是判断 ​ 是否为奇数即可。

　　代码: 

#include<bits/stdc++.h>

using namespace std; 

int main() { 
    int n, m; cin>>n>>m; 
    for(int i=1, a, b; i<=m; i++) scanf("%d%d", &a, &b); 
    puts((n+m)&1? "Alice" : "Bob"); 
    return 0; 
}

I-Inverse Pair

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

　　允许你选择数组 a 中若干个元素加上一，得到数组 c。求 c 的最小逆序对数量。

　　只要观察就可以发现，若第 ​ 大的数加上了 1，那么第 ​ 大的数就没有加上一的必要，且可以让 大的数加一以再减小逆序对的数量​。

　　于是将数组从大到小排序，从第二个数开始遍历。设立标记变量，记录当前数是否加一。遍历到下一个数时，若标记为 0，则该数加之。然后将新数组跑一遍归并排序即可。

　　代码: 

#include<bits/stdc++.h>

using namespace std; 
using ld=long double; using ll=long long; using ull=unsigned long long; using pii=std::pair<int, int>; using pll=std::pair<long long, long long>; using pil=std::pair<int, long long>; using pli=std::pair<long long, int>;

template<typename _tp> bool wi(_tp &_va){ _va=0; long double va=0.0, vd=0.1; bool _neg=0; auto _rd=getchar(); while(_rd<'0' || _rd>'9') { if(_rd=='-'){_neg=1; }else if(_rd==-1){return 0; } _rd=getchar(); } { while(_rd>='0' && _rd<='9') _va=_va*10 + (_tp)_rd-48, _rd=getchar(); } { if(_rd=='.') while(_rd=getchar(), '0'<=_rd && _rd<='9') va=va+((_tp)_rd-48)*vd, vd/=10; } _va=(1-_neg*2)*(_va+(_tp)va); return 1; } 

const int maxn=2e5; 

int li[maxn|1], pos[maxn|1]; 

ll lt[maxn|1]; 
template<typename var> ll merge(int l, int r, var *a) {
    if(r-l<=1) return 0; 
    int mid=l+(r-l)/2; 
    ll res=merge(l, mid, a)+merge(mid, r, a); 
    int p1=l, p2=mid, t=l; 
    while(t<r) { 
        if(p1>=mid || (p2<r && a[p1]>a[p2])) lt[t++]=a[p2++], res+=mid-p1; 
        else lt[t++]=a[p1++]; 
    } 
    for(int i=l; i<r; i++) a[i]=lt[i]; 
    return res; 
}

int main() {  
    int n; cin>>n; 
    for(int i=1; i<=n; i++) wi(li[i]), pos[li[i]]=i; 

    for(int i=n-1, flg=0; i>0; i--) { 
        if(pos[i]>pos[i+1] && !flg) { 
            li[pos[i]]++; 
            flg=1; 
        } 
        else flg=0; 
    } 

    cout<<merge(1, n+1, li)<<endl; 

    return 0; 
}

J-Average

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

　　可以拆分成求两个数组的区间最大平均值之和。

　　代码: 

#include<bits/stdc++.h>

using namespace std; 
using ld=long double; using ll=long long; using ull=unsigned long long; using pii=std::pair<int, int>; using pll=std::pair<long long, long long>; using pil=std::pair<int, long long>; using pli=std::pair<long long, int>; 
#define all(_tmp) _tmp.begin(),_tmp.end()

const double eps=1e-10; 
const int mod=1e9+7; 
const int maxn=1e5; 
const int inf=0x3f3f3f3f; 

ld la[maxn|1], lb[maxn|1]; 

template<typename var> var rmxavg(var *a, int siz, int len, var mx) { 
    var l=0, r=mx; 
    while(r-l>eps) { 
        var mid=(l+r)/2, mi=0, suml=0, sumr=0; 
        bool flag=0; 
        for(int i=1; i<len; i++) sumr+=a[i]-mid; 
        for(int i=len; i<=siz; i++) { 
            sumr+=a[i]-mid; if(i>len) suml+=a[i-len]-mid; 
            if(suml<mi) mi=suml; 
            if(sumr-mi>=0) { flag=1; break; } 
        } 
        flag? l=mid : r=mid; 
    } 
    return l; 
} 

int main() { 
    int n, m, x, y; cin>>n>>m>>x>>y; 
    ld mxa=-1, mxb=-1; 
    for(int i=1, a; i<=n; i++) scanf("%d", &a), la[i]=a, mxa=la[i]>mxa? la[i] : mxa; 
    for(int i=1, b; i<=m; i++) scanf("%d", &b), lb[i]=b, mxb=lb[i]>mxb? lb[i] : mxb; 

    printf("%.10Lf\n", rmxavg(la, n, x, mxa)+rmxavg(lb, m, y, mxb)); 

    return 0; 
}