CF EDU 40 C, D, G 문제 풀이 [사고, 도 론, 이분]

전송 문 C: 제목: 해당 사람의 여행 노선 을 알 고 있 습 니 다. 번호 의 규칙 은 Ai,   j   =   y (i   -   1)   +   j 입 니 다. 특정한 행렬 의 만족 노선 이 존재 하 는 지, 모 르 는 것 은 다음 사례 1 을 볼 수 있 습 니 다.
사고방식: 인접 한 두 수 사이 의 간격 은 반드시 1 또는 y 이다. 그래서 우 리 는 y 만 신경 쓰 고 x 를 신경 쓰 지 않 는 다. 그러면 우 리 는 모든 간격 이 y 인지 아 닌 지 를 직접 체크 하면 된다. 하나의 구덩이 점 은 y = = 3 이 라면 3, 4 는 문제 의 뜻 에 부합 되 지 않 는 다 는 것 이다. 즉, 우리 가 y 를 계산 한 후에 for check 을 해서 이런 상황 을 만들어 야 한 다 는 것 이다.
AC Code

const int maxn = 2e5+5;
int a[maxn];
void solve()
{
    int n; 
    while(cin >> n) {
        int flag = 1, y = 1;
        for (int i = 1 ; i <= n ; i ++) {
            cin >> a[i];
            if (i == 1) continue;
            if (a[i] == a[i-1]) flag = 0;
            if (abs(a[i] - a[i-1]) != 1) y = abs(a[i] - a[i-1]);
        }
        if (!flag) {
            cout << "NO" << endl;
            continue;
        }
        for (int i = 2 ; i <= n ; i ++) {
            if (abs(a[i] - a[i-1]) != 1 && abs(a[i] - a[i-1]) != y) {
                flag = 0;
                break;
            }
            if (a[i] - a[i-1] == 1 && a[i] % y == 1) {
                flag = 0;
                break;
            }
            if (a[i] - a[i-1] == -1 && a[i] % y == 0 && y != 1) {
                flag = 0;
                break;
            }
        }
        if (!flag) cout << "NO" << endl;
        else {
            cout << "YES" << endl;
            cout << 1000000000 << ' ' << y << endl;
        }
    }
}

D: 제목: 한 폭 (n, m) 의 그림 을 정 하고 길 이 는 모두 1 입 니 다. 주어진 s, t 는 몇 개의 변 을 더 해서 s 와 t 사이 의 거 리 를 짧 게 할 수 있 습 니까?
사고: n 은 1000 밖 에 없 기 때문에 n ^ 2 의 알고리즘 은 자 연 스 럽 게 생각 했 습 니 다. s, t 에 대해 각각 bfs 를 한 번 씩 진행 하여 다른 점 의 최 단 거 리 를 구 한 다음 에 n ^ 2 는 임 의 두 점 사 이 를 매 거 할 수 있 는 지, i, j 가 추가 할 수 있 는 조건 은 d [s] [i] + d [t] [j] + 1 > = d [s] [t] 입 니 다. 주의 하 는 것 은 매 거 된 순서 원인 때 문 입 니 다. 그래서 s, t 와 이 두 점 사이 의 최 단 거 리 는 min 을 가 져 야 합 니 다.구체 적 으로 코드 실현 을 보십시오.
AC Code

const int maxn = 1e3+5;
int n, m;
int d[2][maxn], mapp[maxn][maxn];
bool vis[maxn];
vector<int>g[maxn];
void bfs(int st, int f) {
    queueq; Fill(vis, 0);
    q.push({st, 0}); vis[st] = 1;
    while(!q.empty()) {
        pii u = q.front();
        q.pop();

        for (int i  = 0 ; i < sz(g[u.fi]) ; ++ i) {
            int to = g[u.fi][i];
            if (vis[to]) continue;
            vis[to] = 1;
            d[f][to] = u.se + 1;
            q.push({to, u.se+1});
        }
    }
}

void solve()
{
    int s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1 ; i <= m ; i ++) {
        int u, v;
        scanf("%d%d", &u, &v);
        mapp[u][v] = mapp[v][u] = 1;
        g[u].pb(v);
        g[v].pb(u);
    }
    bfs(s, 0); bfs(t, 1); int ans = 0;
    for (int i = 1 ; i <= n ; ++ i) {
        for (int j = 1 ; j <= n ; ++ j) {
            if (i == j || mapp[i][j]) continue;
            if (min(d[0][j] + d[1][i], d[0][i] + d[1][j]) + 1 >= d[0][t]) {
                ++ ans;
            }
        }
    }
    printf("%d
", ans/2);
}

G: 제목: n 조 벽 이 있 고 벽 에 궁수 가 있 으 며 그들 이 사격 할 수 있 는 범 위 를 제시 한 다음 에 준비 한 k 개 궁수 가 있 습 니 다. 이 n 조 벽의 최소 방어 치가 얼마 인지 물 어보 세 요. 방어 치 는 벽의 궁수 수량 으로 정의 되 고 모든 n 조 벽 에 있 는 궁수 가 min 을 취 하 는 것 이 바로 이 n 조 벽의 최소 방어 치 입 니 다.
사고: 물론 2 분 의 답 입 니 다. 그러면 어 려 운 점 은 check 입 니 다. 하나의 사례 를 내 면 주로 해결 하 는 문 제 를 알 수 있 습 니 다. 3, 1, 1000, 00 이라는 답 은 1000 입 니 다. 1000 명의 궁수 들 을 모두 두 번 째 벽 에 놓 아야 합 니 다. 그래서 이 예 를 통 해 우 리 는 추 가 된 궁수 들 을 최대한 경계 맨 오른쪽 에 두 어야 한 다 는 것 을 알 수 있 습 니 다.그래서 우 리 는 한 구간 r 의 합 을 지 키 고 매번 우리 의 2 분 의 답 과 현재 벽 에 있 는 궁수 의 수량 관 계 를 계산 한 다음 에 2 분 의 답 에 도달 해 야 하 는 추가 궁수 를 판단 한 다음 에 k 와 의 관 계 를 판단 하면 된다. 하 나 는 틀림없이 이 숫자 가 매우 클 것 이 고 롱 롱 롱 롱 이 터 지면 마이너스 가 될 것 이다.판단 에 영향 을 줄 수 있 습 니 다. k 최대 1e 18 이기 때문에 추가 궁수 수가 1e 18 을 초과 하면 1e 18 + 5 와 min 을 취하 면 불가능 함 을 표시 합 니 다. 구체 적 인 세부 사항 은 코드 를 보십시오.
AC Code

const int maxn = 5e5+5;
ll a[maxn], tmp[maxn];
ll n, len, k;
ll ok(ll u) {
    memcpy(tmp, a, sizeof(a));
    ll now = 0, s = 0;
    for (int i = 1 ; i <= len ; i ++) now += a[i];  
    for (int i = 1 ; i <= n ; i ++) {
        now += i+len>n?0:tmp[i+len];
        now -= i-len-1<0?0:tmp[i-len-1];
        if (now < u) {
            tmp[min(n, i+len)] += u - now;
            s = min(s + u - now, INF+5);
            now = u;
        }
    }
    return s;
} 
void solve()
{
    while(~scanf("%lld%lld%lld", &n, &len, &k)) {
        for (int i = 1 ; i <= n ; i ++) {
            scanf("%lld", &a[i]);
        }
        ll l = 0, r = (1ll<<60), mid, ans = 0;
        while(l <= r) {
            mid = (l + r) >> 1;
            if (ok(mid) <= k) {
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        printf("%lld
", ans);
    }
}