ABC197 되돌아 가기 메모 (D 문제까지)

15887 단어 C++AtCoder

결과



ABD의 3완으로, 레이트 변화는 704→729(+25)

A 문제 (Rotate)



개요



세 문자 문자열 S의 첫 번째 문자를 끝에 가져올 때 사용할 수있는 문자열을 출력하십시오.

정책



문제처럼.
범용 솔루션은 rotate 함수를 사용하는 것입니다.

C++의 구현 예는 다음과 같습니다.

a.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    cout << S[1] << S[2] << S[0] << endl;
    return 0;
} 

B 문제(Visibility)



개요



장애물이있는 2 차원 평면에서 주어진 위치의 상하 좌우 방향으로 장애물 (또는 벽)까지의 거리의 합을 구합니다.

정책



상하좌우, 모든 방향에 대해 장애물까지의 거리를 세면 된다.
비슷한 작업을 네 번 수행하지 않아도 좋다고 생각하면 아래와 같은 구현이됩니다.

b.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

ll dx[] = {-1, 0, 1, 0};
ll dy[] = {0, -1, 0, 1};

int main() {
    ll H, W, X, Y;
    cin >> H >> W >> X >> Y;
    vector<string> S(H);
    rep(i, H) cin >> S[i];
    X--; Y--;
    ll ans = 1;
    rep(i, 4) {
        ll x = X;
        ll y = Y;
        while (1) {
            x += dx[i];
            y += dy[i];
            if (x >= H || y >= W || x < 0 || y < 0) break;
            if (S[x][y] == '#') break;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
} 

C 문제(ORXOR)



개요



약어

정책



N 개의 요소 사이에 구분 기호를 놓을지 여부를 완전히 탐색합니다.
N 개의 요소 사이에는 N - 1 개가 있으므로 모두 2 ^ (N - 1)만큼 탐색해야합니다.
2의 거듭 제곱대로 탐색하는 경우 비트 전체 검색을 수행하는 것이 좋습니다.
그런 다음 파티션을 넣을 때 XOR을 업데이트합니다.
마지막으로 XOR을 업데이트하는 것을 잊지 마십시오.

C++의 구현 예는 다음과 같습니다.

c.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

const ll LINF = (1LL << 60) - 1;

int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    ll ans = LINF;
    for (ll bit = 0; bit < (1 << n-1); bit++) {
        ll now = 0;
        ll o = 0;
        for (ll i = 0; i < n; i++) {
            o |= a[i];
            if (bit & (1 << i)) {
                now ^= o;
                o = 0;
            }
        }
        now ^= o;
        ans = min(ans, now);
    }
    cout << ans << endl;
    return 0;
} 

D 문제 ( Opposite )



개요



양의 n 각형 정점 중 하나 (p.0)의 좌표와 그 반대편의 정점 (p.2/n)의 좌표가 주어지므로 p1의 좌표를 계산합니다.

정책



복소수를 사용하여 계산하는 것은 간단합니다.
다음 그림과 같이 중점에 해당하는 복소수를 mid로하면 mid + (p0 - mid) * (cos (2π/n), sin (2π/n))을 계산하면 좋다.


C++의 구현 예는 다음과 같습니다.

d.dpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

using C = complex<double>; // 追加
const double PI = acos(-1);

int main() {
    ll n; cin >> n;
    double x, y, x_, y_;
    cin >> x >> y >> x_ >> y_;
    C s = C(x, y);
    C t = C(x_, y_);
    C mid = (s + t) / 2.0;
    double rad = 2 * PI / n;
    C r(cos(rad), sin(rad));
    C ans = mid + (s - mid) * r;
    cout << fixed << std::setprecision(15) << ans.real() << endl;
    cout << fixed << std::setprecision(15) << ans.imag() << endl;
    return 0;
}

좋은 웹페이지 즐겨찾기