ABC197 되돌아 가기 메모 (D 문제까지)
결과
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;
}
Reference
이 문제에 관하여(ABC197 되돌아 가기 메모 (D 문제까지)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/greed_1998/items/290a8d60c32e88bfeb87
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
개요
세 문자 문자열 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;
}
Reference
이 문제에 관하여(ABC197 되돌아 가기 메모 (D 문제까지)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/greed_1998/items/290a8d60c32e88bfeb87
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#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;
}
개요
약어
정책
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;
}
Reference
이 문제에 관하여(ABC197 되돌아 가기 메모 (D 문제까지)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/greed_1998/items/290a8d60c32e88bfeb87
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#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;
}
Reference
이 문제에 관하여(ABC197 되돌아 가기 메모 (D 문제까지)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/greed_1998/items/290a8d60c32e88bfeb87텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)