Codeforces 라운드 #854 편집
| 회의 | 2023-02-28 |
|---|---|
| 해결하다 | 3/9 |
| 생각 | 다시 블루로.. |
A. 최근 활동 문제 – A – 코드 힘
- 대기열 구조로 n+1과 n+m 사이의 값이 항상 앞에 추가되므로 부울 변수로 시뮬레이션할 수 있습니다.
정답은 마지막 것부터 오름차순으로 결정됩니다.
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <list>
#include <assert.h>
#define debug(x) printf("(%s): %d", #x, x)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>0?(a):-(a))
#define rep(x, start, end) for(int x=start;i < end; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#include <bitset>
#include <complex>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;
const long long inf = 1e9;
typedef complex<double> compx;
const double pi = 3.14159265358979;
const int MAX_ID = 101010;
int A(100005);
int answer(100005);
int n, m;
void solve() {
cin >> n >> m;
memset(A, 0, sizeof(A));
memset(answer, -1, sizeof(answer));
int k = n;
int t = 1;
for (int i = 0; i < m; i++) {
int v;
cin >> v;
A(v)++;
if (A(v) == 1) {
answer(k--) = i+1;
}
}
for (int i = 1; i <= n; i++) cout << answer(i) << " ";
cout << "\n";
}
int main() {
fastio;
int testCase = 1;
cin >> testCase;
for (int i = 1; i <= testCase; i++) {
solve();
}
}B. 나누기로 균등화 문제 – B – 코드 힘
문제 – B – 코드 힘
codeforces.com
push it go 문제 풀이 시 다음 정보만으로 풀었습니다.
1) 숫자가 모두 같을 경우 0번 가능
2) 1이 거짓이면 1이 있으면 절대 불가능
3) 2개가 있으면 무조건이다. (어떤 수라도 2로 만들 수 있음)
문제의 제약에서 연산은 30n까지 가능하지만 최대값은 거의 2^30에 걸쳐 있다는 내용이 있다.
4) 나머지는 더 작게 나누어서 2개가 나오는지, 모두 같은지 확인합니다.
그것은 내가 좋아하지 않는 해결책이었습니다.
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <list>
#include <assert.h>
#define debug(x) printf("(%s): %d", #x, x)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>0?(a):-(a))
#define rep(x, start, end) for(int x=start;i < end; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#include <bitset>
#include <complex>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;
const long long inf = 1e9;
typedef complex<double> compx;
const double pi = 3.14159265358979;
const int MAX_ID = 101010;
pair<ll,int> A(100005);
int n;
void proc(vector<pair<int,int>> & q, int a) {
while (A(a).first != 2) {
A(a).first = (A(a).first + 1) / 2;
q.push_back({ A(a).second, A(0).second });
}
}
void solve() {
vector<pair<int, int>> q;
cin >> n;
int oneNum = 0;
for (int i = 0; i < n; i++) {
cin >> A(i).first;
A(i).second = i + 1;
if (A(i).first == 1) oneNum++;
}
bool allSame = true;
for (int i = 0; i < n; i++) {
if (A(i).first != A(0).first) allSame = false;
}
if (oneNum == n || n==1 || allSame) {
cout << 0 << "\n";
return;
}
else if (oneNum > 0) {
cout << -1 << "\n";
return;
}
auto run = ()(vector<pair<int,int>>& q, int a, int b) {
if (A(a).first == A(b).first) return;
A(b).first = (A(b).first + A(a).first - 1) / A(a).first;
q.push_back({ A(b).second, A(a).second });
};
int c = 0;
sort(A, A + n);
while (A(0).first != 2 && c < 30) {
for (int i = 1; i < n; i++) {
run(q, 0, i);
}
sort(A, A + n);
c++;
}
if (A(0).first == 2) {
for (int i = 1; i < n; i++) proc(q, i);
}
else {
bool allSame = true;
for (int i = 0; i < n; i++) {
if (A(i).first != A(0).first) allSame = false;
}
if (allSame == false) {
cout << -1 << "\n";
return;
}
}
cout << q.size() << "\n";
for(auto x : q) cout << x.first << " " << x.second << "\n";
}
int main() {
fastio;
int testCase = 1;
cin >> testCase;
for (int i = 1; i <= testCase; i++) {
solve();
}
}용해
편집 내용을 참조하십시오.
1) 시작 번호가 모두 같으면 아무것도 하지 않는다.
2) 그 외의 경우 1이라는 값이 있으면 답이 존재하지 않는다(모든 값을 1로 설정할 수는 없다).
3) 모든 값이 2보다 크면 답은 항상 존재합니다.
모든 값이 2보다 크면 다음과 같은 방법으로 항상 정답에 도달할 수 있습니다.
1) 가장 큰 값과 가장 작은 값으로 연산을 수행합니다.
2) 가장 큰 값과 가장 작은 값이 같을 때까지 반복합니다.
위의 연산을 최대값과 최소값에 사용하면 항상 2보다 큽니다. (10,000이 최소값보다 크면 2입니다!)
최소값과 최대값이 같지 않으면 연산 결과가 항상 2보다 크기 때문입니다. 최종 값도 2보다 커야 합니다.
C. 이중 사전 최소 문제 – C – 코드 힘
문제 – C – 코드 힘
codeforces.com
push it loose 이 시점에서 당신은 밀고 떼기의 달인입니다.
1) 왼쪽 값과 오른쪽 값을 내림차순으로 정렬합니다.
2) 왼쪽과 오른쪽에 값을 입력할 때 다른 값이 있는 즉시 다음 분기가 발생합니다.
3) b를 다른 두 값 중 더 큰 값으로 설정합니다. 나머지 문자가 모두 b이면 작은 문자가 가운데에 완벽하게 맞습니다.
예를 들어 (a)bbb(b)와 함께 작은 값이 중간에 맞아야 합니다. 바브.
4) b 외에 다른 문자가 남아 있으면 나머지 문자를 정렬하여 가운데에 놓습니다.
예를 들어 a(b)feb(a)a를 사용하면 중간 문자가 정렬되고 삽입됩니다. 아베파.
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <list>
#include <assert.h>
#define debug(x) printf("(%s): %d", #x, x)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>0?(a):-(a))
#define rep(x, start, end) for(int x=start;i < end; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#include <bitset>
#include <complex>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;
const long long inf = 1e9;
typedef complex<double> compx;
const double pi = 3.14159265358979;
const int MAX_ID = 101010;
pair<ll, int> A(100005);
int n;
int histo(26);
void solve() {
string s;
cin >> s;
int n = s.size();
memset(histo, 0, sizeof(histo));
for (int i = 0; i < n; i++) histo(s(i) - 'a')++;
string t = s;
sort(s.begin(), s.end());
int left = 0;
int right = n - 1;
int c = 0;
for (int i = 0; i < n / 2; i++) {
t(right--) = s(c++);
t(left++) = s(c++);
if (t(left - 1) != t(right + 1)) break;
}
if (c < n) {
vector<char> alls;
bool allSame = true;
char base = -1;
if (left - 1 >= 0 && right + 1 < n) {
base = max(t(left - 1), t(right + 1));
}
while (c < n) {
alls.push_back(s(c++));
if (alls.back() != base) allSame = false;
}
string v = t;
reverse(v.begin(), v.end());
sort(alls.begin(), alls.end());
int mid = (left + right + 1) / 2;
int curLast = right + 1;
for (int i = 0; i < alls.size(); i++) {
t(left) = alls(i);
v(left++) = alls(i);
}
if (allSame) {
swap(t(mid), t(curLast));
v = t;
}
if (t < v) cout << v << "\n";
else cout << t << "\n";
}
else {
string v = t;
reverse(t.begin(), t.end());
if (t < v) cout << v << "\n";
else cout << t << "\n";
}
}
int main() {
fastio;
int testCase = 1;
cin >> testCase;
for (int i = 1; i <= testCase; i++) {
solve();
}
}
용해
편집 > 내 솔루션과 동일하지만 구조화할 수 없습니다.