'쇼 피 컵' E 기 프로 그래 밍 및 무한대학 2020 년 대학생 프로 그래 밍 대회 (인터넷 예선) 문제 풀이 보고서

경기 주소: "Shopee 컵" e 일어나 프로 그래 밍 및 무한대학 2020 년 대학생 프로 그래 밍 대회 (인터넷 예선) 전체 경기 체험 이 매우 엉망 이 었 습 니 다. 영어 로 저 를 죽 였 습 니 다.
E-Yu is a Brutal Creature
제목
0 ∼ n 0 \ \ sim n 0 ∼ n 사이 의 모든 만족 (n + 1) 8739 ° (n 2 + 1) (n + 1) | (n ^ 2 + 1) (n + 1) 8739 ° (n2 + 1) 의 자연수 찾기
문제 풀이 의 사고 방향.
제곱 차 공식 에 따 르 면 n 2 - 1 = (n + 1) (n - 1) n ^ 2 - 1 = (n + 1) (n + 1) n2 - 1 = (n + 1) (n - 1) 을 알 수 있다.따라서 알 수 있 듯 이 (n 2 + 1) - (n 2 - 1) = 2 (n ^ 2 + 1) - (n ^ 2 - 1) = 2 (n2 + 1) - (n2 - 1) = 2 도 n + 1 n + 1 n + 1 의 배수 가 되 어야 한다.조건 에 맞 는 수 는 0, 00, 11 밖 에 없다.그래서 n = 0 n = 0 n = 0 n = 0 일 때 는 0 0 0, n > 0 n > 0 n > 0 일 때 는 n - 1 n - 1 n - 1 이다.

#include 
using namespace std;
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%d
", n ? (n - 1) : n);
    }
    return 0;   
}

B-Best Match
제목
하나의 배열 을 정 하고 몇 개의 수 대 ai ai​ , a j a_j aj, i ≠ j i eq j i  = j 만족 a i + a j = = 0 ai + a_j == 0 ai​+aj​==0。
문제 풀이 의 사고 방향.
배열 의 모든 가중치 의 출현 횟수 를 기록 하고 배열 의 가중치 i i 의 출현 횟수 는 c n t i cnct 입 니 다.i cnti​ 。그렇다면 정 답 은:
$\sum\limits_{i=1}^{max(a)} cnt_i \times cnt_{-i} + cnt_0 \times (cnt_0 - 1)/2$

#include
using namespace std;
int read(){
    int c=0,nx,sign=1;
    while(!isdigit(nx = getchar()))
        if(nx=='-')
            sign=-1;
    while(isdigit(nx))
        c=c*10+nx-'0',nx=getchar();
    return sign*c;
}
const int N = 5e5 + 20;
long long cnt[100];
int main(){
    int n = read();
    for(int i=1;i<=n;i++)
        cnt[read() + 20]++;
    long long ans = cnt[20] * (cnt[20] - 1) / 2;
    for(int i=1;i<=20;i++)
        if(cnt[i + 20] and cnt[20 - i])
            ans += cnt[i + 20]  * cnt[20 - i];
    printf("%lld",ans);
}

A-A Monument For Heroes
제목
몇 개의 문자열 을 드 리 겠 습 니 다. 이니셜 과 같은 방식 으로 몇 개 를 연결 할 수 있 는 지, 그리고 제목 에 입력 한 순서대로 연결 해 야 합 니 다. 즉, 먼저 나타 난 문자열 은 반드시 앞 에 연결 해 야 합 니 다.
문제 풀이 의 사고 방향.
DP 를 사용 하여 실현, 기록 d p [i] [j] dp [i] [j] dp [i] [j] 는 i i 로 시작 하고 j j j 로 끝 나 는 연결 의 최 장 길 이 를 나타 낸다.그 다음 에 모든 문자열 을 차례대로 매 거 했 습 니 다. 문자열 s s 의 시작 이 c 1 c 라 고 가정 합 니 다.1 c1, 끝 은 c 2 c2 c2, 그러면 모든 d p [i] [c 2] dp [i] [c 2] dp [i] [c2] 를 업데이트 합 니 다. 업데이트 방식 은 d p [i] [c 2] = m a x (d p [i] [c 2], d p [i] [c 1] + 8739 ° s 8739 ° s) dp [i] = max (dp [i] [c 2], dp [i] [c 1] + | s | dp [i] [c2] = max (dp [i] [c2], dp [c1] + 8739 ° s 8739) 입 니 다.

#include
#define inf 1<<29
#define maxn 1000010
typedef long long ll;
using namespace std;
int n,mp[210][210],ans;
char str[110];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%s",str);
        int len=strlen(str);
        char s=str[0],t=str[len-1];
        for(int j='a';j<='z';++j){
            if(mp[j][s]){
                mp[j][t]=max(mp[j][t],mp[j][s]+len);
            }
             
        }
        mp[s][t]=max(mp[s][t],len);
    }
    for(int i='a';i<='z';++i) ans=max(ans,mp[i][i]);
    cout<

D-DIY Masks at Home
제목
대문자 로 구 성 된 2 차원 행렬 을 드 리 려 면 가장 큰 정사각형 을 찾 아서 이 정사각형 안에 알파벳 만 포함 시 켜 야 합 니 다.
문제 풀이 의 사고 방향.
본 문 제 는 실제 적 으로 여러 가지 통과 방법 이 있 는데 다음 에 두 가지 참고 방법 을 소개 한다.

(폭력 해시) 는 원 행렬 의 모든 자 모 를 하나의 소수 로 바 꾼 다음 에 이 행렬 의 2 차원 접두사 적 (대소 수 에 대해 모델 링) 을 계산한다.그러면 2 분 길이 k 를 정 하 는 전제 에서 우 리 는 매번 사각형 의 왼쪽 상단 (i, j) (i, j) (i, j) (i, j) 을 매 거 할 수 있 고 역 원 을 이용 하여 이런 사각형 의 적 을 계산 한 다음 에 이런 자모의 순 k * 8727 ° k * 8727 ° k * 8727 ° k * 8727 ° k 정사각형 에 대응 하 는 해시 값 과 비교 할 수 있다.충돌 이 걱정 된다 면, 더 블 해시 로 바 꾸 면 된다.총 복잡 도 는 상수 가 좀 큰 O (n m l o g (n) O (nmlog (n) O (nmlog (n))) O (nmlog (n)) 이다.

만약 에 우리 가 원 매트릭스 F 를 바탕 으로 새로운 매트릭스 G G G 를 미리 처리 하면 i i 행 j j 열 값 의 의 미 는 이 값 이 이 줄 앞 에 몇 개의 연속 적 인 숫자 가 그것 과 같 습 니까 (자신 포함).그 다음 에 우 리 는 각 열 을 위 에서 아래로 옮 겨 다 녔 다. 만약 에 한 변 길이 가 k k k 이 고 오른쪽 아래 각 이 (i, j) (i, j) (i, j) (i, j) (i, j) 의 사각형 이 존재 한다 면 반드시 만족 할 것 이다: min * 8289i i i - k < t ≤ i {G [t]] [j]} ≥ k {\ min \ \ lims {i - k < t \ leq i} \ \ {G [t] [t] [j] \ \ \ \ \ \ \ \ \ g [t] \ \ \ \ \ geq k k k} i - k < t < t {G [t]] [j]]]} \ \ \ \ k < t \ \ \ \ \ \ \ \ q [t] [t] \ \ \ \ \ \ \ \ \ 의 오른쪽 아래,오른쪽 상단 도 단조 로 움 을 가지 고 있 기 때문에 우 리 는 2 분 + 각 열 에 대해 R M Q RMQ 배열 을 유지 하 는 방법 으로 O (n m l o g (n) O (nmlog (n) O (nmlog (n)) O (nmlog (n) 를 얻 을 수 있 습 니 다.

#include
#define inf 1<<29
#define maxn 1000010
typedef long long ll;
using namespace std;
int n,mp[210][210],ans;
char str[110];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%s",str);
        int len=strlen(str);
        char s=str[0],t=str[len-1];
        for(int j='a';j<='z';++j){
            if(mp[j][s]){
                mp[j][t]=max(mp[j][t],mp[j][s]+len);
            }
        }
        mp[s][t]=max(mp[s][t],len);
    }
    for(int i='a';i<='z';++i) ans=max(ans,mp[i][i]);
    cout<

C-Can You Help ZSGW
제목
하나의 배열 이 있 습 니 다. 우 리 는 이 배열 에 대해 단조 로 운 스 택 알고리즘 을 실행 하 는 과정 에서 모든 위치 에 옮 겨 다 닌 후에 단조 로 운 스 택 의 크기 를 알 고 있 습 니 다. 어떤 위치 가 부족 하면 임 의적 으로 할 수 있 습 니 다.이러한 상황 을 만족 시 키 는 사전 순서 가 가장 작은 배열 을 구하 다.
문제 풀이 의 사고 방향.
우선 우리 가 해 야 할 일 은 이 단조 로 운 스 택 배열 b b b 를 보완 하 는 것 이다.단조 로 운 스 택 배열 은 단조 로 운 스 택 알고리즘 의 특징 으로 인해 반드시 이런 몇 가지 특징 을 만족 시 킬 것 이다.

b [ 1 ] = 1 b[1] = 1 b[1]=1

b [i] > b [i - 1] b [i] > b [i - 1] b [i] > b [i - 1], b [i] = b [i - 1] + 1 b [i] = b [i - 1] + 1 b [i] = b [i] > a [i - 1] a [i] > a [i - 1] a

b [i] < = b [i - 1] b [i] < = b [i - 1] b [i] < = b [i - 1], a [i - 1] a [i] < a [i - 1] a [i] a

우 리 는 왼쪽 에서 오른쪽으로 각각 - 1 - 1 - 1 - 1 의 칸 을 차례대로 보완 한다. 그러면 전략 은:

만약 i = 1 i = 1 i = 1, b [i] = 1 b [i] = 1 b [i] = 1.

그렇지 않 으 면 우리 가 b [i - 1] b [i - 1] b [i - 1] 보다 작은 수 를 채 우 면 나중에 보완 할 때 a [i - 1] > a [i] a [i - 1] > a [i] a [i - 1] > a [i] a [i - 1] > a [i - 1] 를 의미 하 며 사전 순서 에 서 는 좋 은 생각 이 되 지 않 을 것 이다.그래서 b [i - 1] + 1 b [i - 1] + 1 b [i - 1] + 1 을 채 워 야 합 니 다.

배열 을 보완 한 후에 규칙 은 다음 과 같다. 먼저 우 리 는 모든 11.1 의 위치 가 11.1 로 끝 나 는 내림차 순 서 를 구성 한 것 을 발견 할 수 있다.그리고 각각 11 로 분 단 된 하위 구간 에 대해 서도 22 는 비슷 한 규칙 을 충족 시킨다.그리고 222 를 더 나 눈 하위 구간 333 에 대해 서도 마찬가지다.그래서 우 리 는 가중치 가 증가 하 는 순서에 따라 차례대로 각 수 를 채 운 다음 에 재 귀적 으로 서브 구간 을 작성 한다.표준 거리의 복잡 도 는 O (n l o g (n) O (nlog (n) O (nlog (n))) 로 실제 적 으로 분할 구간 의 단조 성 을 이용 하여 O (n) O (n) O (n) O (n) O (n) 로 최적화 할 수 있다.

#include 
using namespace std;
 
int T, n;
int p[200005];
int lst[200005], tail;
int pre[200005];
int nxt[200005];
int s[200005];
 
int main() {
    scanf("%d", &T);
    for(int k = 0; k < T; ++k) {
        scanf("%d", &n);
        for(int i = 0; i <= n; ++i) nxt[i] = pre[i] = 0;
        tail = 0;
        for(int i = 1; i <= n; ++i) scanf("%d", &p[i]);
        p[1] = 1;
        for(int i = 2; i <= n; ++i) if(p[i] == -1) {
            if(p[i + 1] - p[i - 1] == 2) p[i] = p[i - 1] + 1;
            else p[i] = p[i - 1] + 1;
        }
        for(int i = 1; i <= n; ++i) {
            if(p[i] > p[i - 1]) {
                nxt[tail] = i;
                pre[i] = tail;
                tail = i;
            } else {
                int x = lst[p[i]];
                nxt[pre[x]] = i;
                pre[i] = pre[x];
                nxt[i] = x;
                pre[x] = i;
            }
            lst[p[i]] = i;
        }
        for(int i = 1, j = nxt[0]; i <= n; ++i, j = nxt[j]) s[j] = i;
        for(int i = 1; i <= n; ++i) printf("%d ", s[i]);
        printf("
");
    }
    return 0;
}