Educational Codeforces Round 91 (Rated for Div. 2)
Educational Codeforces Round 91 (Rated for Div. 2)
보충 을 기다리다
1. 제목 분석
A. Three Indices
제목: t 개의 사례 를 정 하고 모든 사례 는 n 을 정 한 다음 에 n 개의 숫자 를 제시 합 니 다. 3 개의 숫자 ai, aj, ak 가 존재 하 는 지 판단 하고 i < j < k, 그리고 aj > ai, aj > ak 를 만족 시 킵 니 다.출력 YES 가 존재 하면 i, j, k 를 출력 합 니 다.출력 NO 가 존재 하지 않 습 니 다.T ~ 200, n ~ 1000 문제 풀이: 먼저 한 번 훑 어보 고 현재 숫자 앞에서 가장 작은 숫자 아래 표 시 를 판단 합 니 다.다시 한 번 거꾸로 훑 어 현재 숫자 를 판단 한 후 가장 큰 숫자의 아래 표 시 를 한다.그 다음 에 현재 숫자 앞 에 그것 보다 작은 숫자 가 있 는 지, 현재 숫자 뒤에 그것 보다 큰 숫자 가 있 는 지 를 한 번 훑 어보 면 된다.O (n) 코드:
#include
using namespace std;
int const N = 1e3 + 10;
int a[N], n, T, le[N], ri[N];
int main() {
cin >> T;
while (T--) {
memset(ri, -1, sizeof ri);
memset(le, -1, sizeof le);
cin >> n;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
int minv1 = 1e9 + 10, minv2 = 1e9 + 10, minid1 = -1, minid2 = -1;
for (int i = 1; i <= n; ++i) {
if (minv1 < a[i]) le[i] = minid1;
if (a[i] < minv1) {
minv1 = a[i];
minid1 = i;
}
}
for (int i = n; i >= 1; --i) {
if (minv2 < a[i]) ri[i] = minid2;
if (a[i] < minv2) {
minv2 = a[i];
minid2 = i;
}
}
int flg = 0;
for (int i = 2; i <= n; ++i) {
if (le[i] != -1 && ri[i] != -1) {
cout << "YES
";
cout << le[i] << " " << i << " " << ri[i] << endl;
flg = 1;
break;
}
}
if (flg == 1) continue;
cout << "NO
";
}
return 0;
}
B. Universal Solution
제목: 이제 로봇 과 가위 바위 보 를 하려 고 하 는데 로봇 의 주먹 내 는 방식 은 이미 알 고 있다.사람의 주먹 을 내 는 방식 은 확정 해 야 하 는 동시에 언제 주먹 을 내 는 지 확인 해 야 한다. 주먹 을 내 는 방식 을 찾 아서 사람 이 언제 주먹 을 내 든 승리 할 확률 이 가장 크다.t 개의 테스트 사례 를 제시 하고 모든 테스트 사례 는 n 길이 의 문자열 을 제시 하여 로봇 의 주먹 을 내 는 방식 을 나타 낸다.t ~ 1000, n ~ 2e5 코드 문제 풀이: 언제 주먹 을 내 든 승 률 이 가장 높 아야 하기 때문에 현재 로봇 이 주먹 을 가장 많이 내 는 것 이 무엇 인지 통계 하면 되 고 매번 가장 많이 이 기 는 것 만 통계 하면 된다.코드:
#include
using namespace std;
int T;
int main() {
int R = 0, S = 0, P = 0;
cin >> T;
string s;
while (T--) {
cin >> s;
R = 0, S = 0, P = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == 'R' ) R++;
else if (s[i] == 'S') S++;
else if (s[i] == 'P') P++;
}
int maxv = max(R, max(S, P));
if (R == maxv) {
for (int i = 0; i < s.size(); ++i)
cout << 'P';
}
else if (S == maxv) {
for (int i = 0; i < s.size(); ++i)
cout << 'R';
}
else if (P == maxv) {
for (int i = 0; i < s.size(); ++i)
cout << 'S';
}
cout << endl;
}
return 0;
}
C. Make It Good
제목: 현재 n 명의 학생 이 있 습 니 다. 이 n 명의 학생 을 많은 비 어 있 는 팀 으로 나 누고 싶 습 니 다. 각 팀 의 능력 치 = 팀 에서 능력 치가 가장 낮은 학생 의 능력 치 * 팀 의 인원 은 이런 팀 을 구성 할 수 있 는 지 물 어보 십시오.t 개의 테스트 사례 를 지정 하고 모든 테스트 사례 는 n 과 k 를 제시 하 며 n 은 n 명의 친구 가 있 음 을 나타 내 고 k 는 팀 의 최소 능력 치 를 나타 낸다.그 다음 에 n 개의 숫자 를 제시 하여 모든 학우 의 능력 치 를 나타 낸다.문제 풀이: 욕심 처 리 를 고려 하여 먼저 학생 들 을 능력 치 에 따라 어 릴 때 부터 어른 까지 순 위 를 매 긴 다.그 다음 에 큰 것 부터 작은 스 캔 까지 현재 학생 들 의 능력 치가 k 보다 크 면 단독으로 팀 을 구성 할 수 있다.k 보다 작 으 면 팀 의 인원 을 늘 리 는 것 을 고려 합 니 다.O (n) 스 캔 하면 코드:
#include
using namespace std;
int const N = 2e5 + 10;
int T, a[N], n, x;
int main() {
cin >> T;
while (T--) {
cin >> n >> x;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n);
int res = 0, mul = 1e9, cnt = 0;
for (int i = n; i >= 1; --i) {
if (a[i] >= x) {
res ++;
// cout << "i:" << i << endl;
continue;
}
else {
mul = a[i];
cnt++;
if (mul * cnt >= x) {
res ++;
// cout << "i:" << i << endl;
cnt = 0;
}
}
}
cout << res << endl;
}
return 0;
}
D. Berserk And Fireball
제목: 현재 두 줄 의 전사 가 있 습 니 다. 첫 번 째 줄 의 전 사 는 n 개 입 니 다. 첫 번 째 줄 의 전 사 를 일정 수량 처치 하면 두 번 째 줄 의 전사 가 됩 니 다.전 사 를 처치 하 는 방식 은 두 가지 가 있 습 니 다. 첫 번 째 는 연속 k 개 전 사 를 선택 하여 처치 하 는 것 입 니 다. 이것 은 x 원 을 소모 합 니 다.두 번 째 는 인접 한 두 명의 전 사 를 선택 하여 그 중의 작은 전 사 를 처치 하 는 것 이다. 이것 은 Y 원 을 소모 할 것 이다.첫 번 째 줄 은 n 과 k 를 정 하고 두 번 째 줄 은 x, k 와 y 를 정 하 며 세 번 째 줄 은 첫 번 째 줄 의 전사 번 호 를 주 고 네 번 째 줄 은 두 번 째 줄 의 전사 번 호 를 준다.최소 비용 보다 많 으 면 출력 - 1 문제 풀이 가 존재 하지 않 습 니 다. 문 제 는 두 번 째 줄 의 전사 에 게 주 었 습 니 다. 모든 것 은 두 번 째 줄 의 전사 의 마지막 결과 에 따라 첫 번 째 줄 의 전사 와 일치 하면 많은 분 단 을 얻 을 수 있 습 니 다. 그리고 이 분 단 을 삭제 할 수 있 는 지 계산 할 수 있 습 니 다. 삭제 할 수 있다 면 최소 비용 을 구하 면 분류 토론 이 필요 합 니 다.시퀀스 b 에서 요소 의 출현 순서 가 a 와 일치 하지 않 으 면 풀 리 지 않 습 니 다.그렇지 않 으 면 b 에 따라 a 를 하나의 구간 으로 나 누 어 각 구간 을 단독으로 조작 합 니 다.k 보다 길이 가 작은 구간:
코드:
#include
using ll = long long;
using namespace std;
int main() {
ll n, m, x, k, y; cin >> n >> m >> x >> k >> y;
int a[n] = {};
int pos[n] = {};
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
pos[a[i]] = i;
}
int b[m] = {};
int mx_pos = 0;
bool skip[n] = {}; // a
for (int i = 0; i < m; i++) {
cin >> b[i];
--b[i];
if (pos[b[i]] < mx_pos) {
cout << -1 << "
";
return 0;
} else mx_pos = pos[b[i]];
skip[b[i]] = true;
}
vector> v; //
vector> border; //
vector t; //
int l = -1, r = -1; //
for (int i = 0; i < n; i++) {
if (skip[a[i]]) { //
if (l == -1 and r == -1) { //
r = a[i];
} else { //
l = r;
r = a[i];
}
if (t.size() > 0) {
v.push_back(t);
border.emplace_back(l, r);
t.clear();
}
continue;
}
t.push_back(a[i]);
}
if (t.size() > 0) {
l = r;
v.push_back(t);
border.emplace_back(l, -1);
t.clear();
}
ll ans = 0;
for (int i = 0; i < v.size(); i++) {
bool seg_mx = *max_element(v[i].begin(), v[i].end()) > max(border[i].first, border[i].second);
if (v[i].size() < k) {
if (seg_mx) {
cout << -1 << "
";
return 0;
}
ans += v[i].size() * y;
} else {
if (seg_mx)
ans += min(x + (v[i].size() - k) * y, v[i].size() / k * x + v[i].size() % k * y);
else
ans += min(v[i].size() * y, v[i].size() / k * x + v[i].size() % k * y);
}
}
cout << ans << "
";
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
