Codeforces 글로벌 라운드 7 (말 라 차)

Codeforces Global Round 7

D1 Prefix-Suffix Palindrome(EASY)

D2 Prefix-Suffix Palindrome(HARD)

A Bad Ugly Numbers

B Maximums

C Permutation Partitions

Codeforces Global Round 7
D1 Prefix-Suffix Palindrome(EASY)
제목: 주어진 문자열 s 는 s 에서 접두사 a, 접두사 b 를 가 져 옵 니 다. a + b 에 게 답장 문자열 t (a, b 는 빈 문자열 일 수 있 습 니 다) 를 구성 하 라 고 요구 하 며 t 의 길 이 는 s 를 초과 할 수 없습니다.최대 길이 의 t 를 구하 고 출력 합 니 다.단순 버 전의 s 길이 1e5
: 처음에는 머리 가 좋 지 않 아 직접 폭력 을 행사 하 다가 n3 직접 tle.어수룩 하 다.
사고: t 는 접두사 와 접두사 로 만 구성 할 수 있 도록 규정 되 어 있 기 때문에 a 의 시작 점 아래 표 지 는 반드시 0 이 고 b 의 끝 점 아래 표 지 는 반드시 len 이다.a 와 b 순서 가 연결 되 어 있 기 때문에 양쪽 에서 대칭 의 최대 치 를 찾 아 a 에 직접 추가 합 니 다. 이 부분 은 고정 적 인 (앞 접미사) 입 니 다.그리고 남 은 중간 부분 에서 앞 접미사 의 최대 답장 문자열 을 찾 습 니 다.(폭력)
잘 생각 나 지 않 으 면 샘플 중의 두 번 째 것 을 볼 수 있다.
abc 중간: dfdce
코드 중간 while (1) 는 전혀 쓸모 가 없습니다. sbbb 의 결과 물 입 니 다.

int check(string ss){
    int l=-1,r=ss.length();
    while(ss[l+1]==ss[r-1]&&l+1<=r-1){
        l++;
        r--;
    }
    if(l==r||l+1==r)
        return 1;
    else
        return 0;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string s,a,ans;
        cin>>s;
        s.insert(0,"0");
        s+='0';
        int l,r;
        while(1){
            int len=s.length()-2;
            //cout<
            l=0,r=len+1;
            while(s[l+1]==s[r-1]&&l+1<r-1){
                l++;
                r--;
            }
            if(l==0){
                for(int i=len;i>=1;i--){
                    string tt,rtt;
                    tt+=s.substr(1,i);
                    rtt+=s.substr(len+1-i,i);
                    //cout<
                    if(check(tt)){
                        string b;
                        b+=a;
                        reverse(b.begin(),b.end());
                        ans=a+tt+b;
                        break;
                    }
                    if(check(rtt)){
                        string b;
                        b+=a;
                        reverse(b.begin(),b.end());
                        ans=a+rtt+b;
                        break;
                    }
                }
                break;
            }
            a+=s.substr(1,l);
            if(len-2*l==0){
                string b;
                b+=a;
                reverse(b.begin(),b.end());
                ans=a+b;
                break;
            }
            string temp;
            swap(temp,s);
            s+='0';
            s+=temp.substr(l+1,len-2*l);
            s+='0';
        }
        cout<<ans<<endl;
    }
    return 0;
}

D2 Prefix-Suffix Palindrome(HARD)
제목: easy 버 전과 같 지만 문자열 의 데이터 범 위 는 1e6 로 확대 되 었 고 폭력 탐색 답문 열 은 기본적으로 폭발 했다.
사고: 중간 부분의 회 문 꼬치 판단 을 최적화 시 키 고 o (n2) 를 o (n) 로 낮 춥 니 다. manacher 이것 은 성숙 하지 않 은 연결 입 니 다.
한밤중 에 cf 가 갑자기 이 코드 를 판정 하지 못 해서 나 는 몰 랐 다.

int cnt[maxn*2];
char ts[maxn*2];
void manacher(string s,int len){
    int l=0;
    ts[l++]='$';
    ts[l++]='#';
    for(int i=0;i<len;i++){
        ts[l++]=s[i];
        ts[l++]='#';
    }
    ts[l]=0;
    int maxr=0,flag=0;
    for(int i=0;i<l;i++){
        cnt[i]=maxr>i?min(cnt[2*flag-i],maxr-i):1;
        while(ts[i+cnt[i]]==ts[i-cnt[i]])
            cnt[i]++;
        if(i+cnt[i]>maxr){
            maxr=i+cnt[i];
            flag=i;
        }
    }
    return;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string s,a,ans;
        cin>>s;
        s.insert(0,"0");
        s+='0';
        int l,r;
        while(1){
            int len=s.length()-2;
            //cout<
            l=0,r=len+1;
            while(s[l+1]==s[r-1]&&l+1<r-1){
                l++;
                r--;
            }
            if(l==0){
                string tt=s.substr(1,len);
                manacher(tt,len);
                int maxxp=0,maxxn=0;
                for(int i=1;i<=2*len;i++){
                    if(cnt[i]==i){
                        maxxp=max(maxxp,cnt[i]-1);
                    }
                    if(i+(cnt[i]-1)==2*len+1){
                        maxxn=max(maxxn,cnt[i]-1);
                    }
                }
                string b;
                b+=a;
                reverse(b.begin(),b.end());
                if(maxxp>maxxn)
                    ans=a+tt.substr(0,maxxp)+b;
                else ans=a+tt.substr(len-maxxn,maxxn)+b;
                break;
            }
            a+=s.substr(1,l);
            if(len-2*l==0){
                string b;
                b+=a;
                reverse(b.begin(),b.end());
                ans=a+b;
                break;
            }
            string temp;
            swap(temp,s);
            s+='0';
            s+=temp.substr(l+1,len-2*l);
            s+='0';
        }
        cout<<ans<<endl;
    }
    return 0;
}

A Bad Ugly Numbers
제목: n 을 출력 숫자의 길이 로 지정 하고 출력 을 요구 하 는 숫자 는 그 안에 나타 난 숫자 에 의 해 정 리 될 수 없습니다.
ex：6（×）6 으로 12 로 나 눌 수 있다 (×）1, 2 로 나 눌 수 있어 요.
사고: 간단 한 구조 문제, A. 제 가 생각 하 는 것 은 5 와 4 로 끝 나 는 것 입 니 다. 4 로 끝 나 는 것 은 5 로 나 누 지 않 는 다 는 것 입 니 다. 4 앞 에 5 를 더 하면 4 로 나 누 지 않 는 다 는 것 입 니 다. B 는 다른 코드 를 보면 2 와 3 이 있 습 니 다. 첫 번 째 2 는 모두 3 이 고 기이 성 을 확보 하 는 동시에 3 으로 나 누 지 않 습 니 다.

int main(){
    int t=ird();
    while(t--){
        int n=ird();
        if(n==1){
            cout<<-1<<endl;
            continue;
        }
        if(n%2==0){
            for(int i=1;i<=n/2;i++)
                cout<<"54";
            cout<<endl;
        }
        else
        {
            for(int i=1;i<=n/2;i++)
                cout<<"45";
            cout<<"4"<<endl;
        }
    }
    return 0;
}
 

B Maximums
요 나라 고 말 하고 싶 지 않 아 요. 졸 려 요.

int a[maxn],b[maxn];
int main(){
    int n=ird();
    for(int i=1;i<=n;i++){
        b[i]=ird();
    }
    int maxx=0;
    for(int i=1;i<=n;i++){
        maxx=max(maxx,a[i-1]);
        a[i]=b[i]+maxx;
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

C Permutation Partitions
제목: 1 - n 의 배열 을 정 하고 k 개의 교차 하지 않 는 구간 을 가 져 옵 니 다. 모든 구간 의 최대 치 를 최대 로 하고 출력 최대 치 와 서로 다른 구역 의 수량 을 가 져 옵 니 다.
사고: 조합 수학. 취 하 는 구간 의 최대 숫자 는 n ~ n - k + 1 이다. 첫 번 째 답 은 등차 수열 의 합 이다. 지금 문 제 는 선택 한 숫자 를 배열 에 넣 었 는데 어떻게 구분 합 니까? 아래 표 와 숫자 크기 를 기록 하고 숫자 크기 에 따라 배열 합 니 다. 분 구 수 는 중간 숫자 개수 의 곱 입 니 다. (손 으로 밀 면 됩 니 다)

struct node{
    LL num;
    LL id;
}a[maxn];
bool cmp(node aa,node ab){
    return aa.num>ab.num;
}
int main(){
    LL n=lrd(),k=lrd();
    for(int i=1;i<=n;i++){
        a[i].num=lrd();
        a[i].id=1ll*i;
    }
    sort(a+1,a+1+n,cmp);
    vector<LL> v;
    LL ans=1,co=0;
    for(int i=1;i<=k;i++){
        co+=a[i].num;
        v.push_back(a[i].id);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<k-1;i++)
        ans=(ans*(v[i+1]-v[i]))%MOD;
    cout<<co<<" "<<ans<<endl;
    return 0;
}