Codeforces Round \ # 187 (Div. 2) 총결산

A 문 제 는 매우 빠르게 한 번 보 았 지만 이해 하지 못 하고 또 한 번 보 았 다. 약간 급 한 느낌 이 들 어서 잘 알 았 다. 그래서 과감하게 B 문제 에 뛰 어 들 었 다. B 문 제 는 제목 의 뜻 이 너무 명확 해서 나 는 많은 사람들 이 바로 나무 모양 의 배열 을 선택 하여 풀 수 있다 는 것 을 알 았 다.사실 하나의 배열 과 하나의 변수 만 유지 하면 됩 니 다.돌아 와 서 A 문 제 를 풀 고 바로 pretest 를 해서 C 문 제 를 봤 어 요. 레이), C 문 제 를 삐 뚤 게 생각 했 어 요. 처음에 봤 을 때 A 가 없 었 어 요. 어 려 운 줄 알 고 복잡 하 게 생각 했 어 요. 그리고 예전 에 사용 하지 않 았 던 vector 도 썼어 요.나중에 하 는 사람 이 많아 져 서 마음 을 가 라 앉 혔 습 니 다. 원래는 한 번 만 들 면 되 었 습 니 다. 급 하 게 두 드 렸 습 니 다. 작은 디 테 일 로 인해 wa 4 발 후에 A 가 되 었 습 니 다. 이번 에는 큰 교훈 입 니 다!역경 속 에서 서둘러 성공 을 추구 해 서 는 안 되 고, 더욱 마음 을 가 라 앉 히 고 냉정 하 게 코드 를 세 심하게 두 드 려 야 한다!!코드 가 다른 사람 보다 얼마나 빨리 두 드 리 는 지 바라 지 않 고 코드 가 완벽 하 게 두 드 려 서 디 테 일 한 오류 가 없 기 를 바 랍 니 다!
A 문제: Sereja and Bottles

#include <stdio.h>
#include <string.h>
bool vis[111];
int a[111],b[111];
int main()
{
    memset(vis,1,sizeof(vis));
    int i,j,n;
    scanf("%d", &n);
    for(i = 0;i < n; i++)
        scanf("%d%d", &a[i], &b[i]);
    for(i = 0;i < n; i++)
        for(j = 0;j < n ; j++)
            if(i != j && b[i]==a[j])
                vis[j] = 0;
    int ans = 0;
    for(i = 0;i < n; i++)
        if(vis[i])
            ans++;
    printf("%d
", ans);
    return 0;
}

B 문제: Sereja and Array
a [] 배열 이 a [x] 의 현재 값 을 유지 하 는 데 만 필요 합 니 다. sum 은 모든 요소 에 sum 을 추가 한 것 을 표시 합 니 다. 첫 번 째 작업 은 a [x] 를 y 로 바 꾸 려 면 a [x] = y - sum 만 있 으 면 됩 니 다.
C 문제: Sereja and Contest
a1, a2, a3, a4, a5
a3 의 d3 = a2 - 2 * 2 * a3
a4 의 d4 = a2 + 2 * a3 - 3 * 1a 4
a5 의 d5 = a2 + 2 * a3 + 3 * a4 - 0
이 법칙 을 찾 은 후에 한 번 매 거 하면 된다.

#include <stdio.h>
#define LL __int64
const int maxn = 100005 ;
LL a[maxn];
int main()
{
    int n,m,i,x,y,z;
    scanf("%d%d", &n ,&m);
    for(i = 1;i <= n; i++)
        scanf("%d", &a[i]);
    LL sum = 0;
    while(m--)
    {
        scanf("%d%d", &x, &y);
        if(x == 1)
        {
            scanf("%d", &z);
            a[y] = z-sum;   //  a[y]  z
        }
        else if(x == 2)
            sum += y;
        else
            printf("%I64d
", a[y] + sum);
    }
    return 0;
}

D 문제: Sereja and Periods
시합 후에 자신 이 생각해 낸 것 인 데, 이렇게 물 문 제 는 시합 에서 왜 감히 생각 하지 못 할 까? 다음 에는 결코 이런 상태 가 될 수 없다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <math.h>
using namespace std;
#define LL __int64
#define max(a,b)  (a>b?a:b)
#define min(a,b)  (a>b?b:a)
#define lowbit(x) ((x)&(-x))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

LL a[200005];
int main()
{
    int n,i;
    LL k;
    scanf("%d%I64d", &n, &k);
    for(i = 1;i <= n; i++)
        scanf("%I64d", &a[i]);
    int pre = 1;
    LL prex = 0;
    LL sum = 1;
    LL tot = n;
    for(i = 2;i <= n; i++)
    {
        LL now;
        if(sum != 1)
            now = prex  - sum*(tot-sum-1)*a[i];
        else
            now =  - sum*(tot-sum-1)*a[i];
//      printf("%d %I64d %I64d
", i,now,prex);
        if(now < k)
            printf("%d
", i),tot--;
        else
        {
            sum++;
            pre = i;
        //  printf("%I64d %I64d %d
", prex,a[i],sum);
            prex = prex + (sum-1)*a[i];
        //  printf("%I64d %I64d %d
", prex,a[i],sum);
        }
    }
}

E 문제: Sereja and Subsequences
E 문제 도 원래 물 문 제 였 어 요. 경기 후에 시작 할 때 문제 의 뜻 이 틀 렸 어 요. 잘못된 생각 을 오래 했 어 요. 진정한 경기 때 와 경기 후에 문 제 를 푸 는 느낌 이 전혀 달라 요. 언제 경 기 를 진정 으로 통제 할 수 있 는 느낌 이 들 었 으 면 좋 겠 어 요!
트 리 배열 or 선분 트 리

#include <stdio.h>
#include <string.h>
#define LL __int64

char a[111], c[111] ;
int cnt[111], next[111];
int main()
{
    int b,d,i,j;
    scanf("%d%d%s%s", &b, &d, a, c) ;
    int len1 = strlen(a);
    int len2 = strlen(c);
    for(i = 0;i < len2; i++)
    {
        int cur = i;
        cnt[i] = 0;
        for(j = 0;j < len1; j++)
            if(c[cur] == a[j])
            {
                cur++;
                if(cur == len2)
                    cnt[i] ++ , cur = 0;
            }
        next[i] = cur;
    }
    int cur = 0;
    LL ans = 0;
    for(i = 0;i < b; i++)
    {
        ans += cnt[cur];
        cur = next[cur];
    }
    printf("%I64d
", ans/d);
    return 0;
}