고등학생이지만 기초 그룹 문제를 풀어보며 완전 정답을 경험해보았다
T1 최적 분할
문제 링크
T1은 예상대로 간단했다.
홀수인 경우 -1을 출력하고, 짝수인 경우 큰 2의 제곱수부터 탐색한다. n이 해당 수보다 크면 해당 값을 출력하고 n에서 빼고, 해당 값을 반으로 나누어 계속한다.
#include<iostream>
using namespace std;
int inputNumber;
int main() {
cin>>inputNumber;
if(inputNumber&1){
cout<<-1;
return 0;
}
for(int power=(1<<30);power>0;power/=2){
if(inputNumber>=power){
cout<<power<<" ";
inputNumber-=power;
}
}
return 0;
}
최적 분할T2 방송 경품
문제 링크
올해 T2는 다소 까다로웠다. 두 개의 최대 힙을 사용해야 한다.
다음 문제를 참고하자:
로그 P1168 중간값
로그 P1801 검은 상자
이 문제를 풀기 위해 소형 힙의 크기를 계산하고, 지속적으로 삽입 및 삭제 연산을 수행하면 된다.
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int> maxHeap;
priority_queue<int,vector<int>,greater<int> > minHeap;
int n,w,value[100005];
int main(){
cin>>n>>w;
for(int i=1;i<=n;i++) cin>>value[i];
for(int i=1;i<=n;i++){
int k=max(1,i*w/100);
if(minHeap.empty()||minHeap.top()<=value[i]) minHeap.push(value[i]);
else maxHeap.push(value[i]);
while(!minHeap.empty()&&minHeap.size()>k){
maxHeap.push(minHeap.top());
minHeap.pop();
}
while(minHeap.empty()||minHeap.size()<k){
minHeap.push(maxHeap.top());
maxHeap.pop();
}
cout<<minHeap.top()<<" ";
}
return 0;
}
방송 경품T3 수식
문제 링크
이 문제는 상당히 복잡하다. 코드량이 많고, 규칙이 명확하지 않다.
후위 표기식은 스택으로 처리하며, 관련 코드는 P1449 후위 표기식 참고.
먼저 원래 상태로 O(n) 계산한 후, 쿼리가 들어올 때마다 재계산하지 않고 패턴을 찾는다.
각 연산자에 대해 결과는 0 또는 1이 되며, 이 연산자의 결과가 다음 단계에 미치는 영향을 추적해야 한다.
구조체에 저장하며, 인덱스는 단계 번호, id는 연산자 유형, to는 다음 단계 번호, value는 해당 단계 값, x1, x2는 두 피연산자를 나타낸다.
쿼리 시 메모이제이션 방식으로 재귀적으로 분석하여 영향 여부를 확인한다.
나는 초기에 string 처리를 매우 복잡하게 구현했다.
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000005;
struct node{
int type;
int next;
int result;
int op1,op2;
}nodes[maxn*2];
int data[maxn],n,q;
stack<int> s;
string expr;
int cnt=1000000;
int vis[maxn*2],answer;
int strToInt(string ss){
int num=0;
for(int i=1;i<ss.length();i++) num+=(pow(10,ss.length()-i-1)*(ss[i]-'0'));
return num;
}
int strToInt2(string ss){
int num=0;
for(int i=0;i<ss.length();i++) num+=(pow(10,ss.length()-i-1)*(ss[i]-'0'));
return num;
}
int dfs(int num){
if(nodes[num].type==0) return nodes[num].result=data[num];
if(nodes[num].type==1){
int x=dfs(nodes[num].op1),y=dfs(nodes[num].op2);
if(x==1&&y==1) return nodes[num].result=1;
else return nodes[num].result=0;
}
if(nodes[num].type==2){
int x=dfs(nodes[num].op1),y=dfs(nodes[num].op2);
if(x==0&&y==0) return nodes[num].result=0;
else return nodes[num].result=1;
}
if(nodes[num].type==3){
int x=dfs(nodes[num].op1);
if(x==0) return nodes[num].result=1;
else return nodes[num].result=0;
}
}
bool check(int num){
if(vis[num]==1) return 1;
if(vis[num]==2) return 0;
int target=nodes[num].next;
int x=nodes[target].op1,y=nodes[target].op2;
if(x==num) x=y;
if(nodes[num].result==0){
if(nodes[target].type==1&&nodes[x].result==1){
check(target)?vis[num]=1:vis[num]=2;
return vis[num]==1?1:0;
}
if(nodes[target].type==1&&nodes[x].result!=1) return vis[num]=1;
if(nodes[target].type==2&&nodes[target].result==0){
check(target)?vis[num]=1:vis[num]=2;
return vis[num]==1?1:0;
}
if(nodes[target].type==2&&nodes[target].result==1) return vis[num]=1;
if(nodes[target].type==3){
check(target)?vis[num]=1:vis[num]=2;
return vis[num]==1?1:0;
}
}
if(nodes[num].result==1){
if(nodes[target].type==1&&nodes[x].result==1){
check(target)?vis[num]=1:vis[num]=2;
return vis[num]==1?1:0;
}
if(nodes[target].type==1&&nodes[x].result!=1) return vis[num]=1;
if(nodes[target].type==2&&nodes[x].result==0){
check(target)?vis[num]=1:vis[num]=2;
return vis[num]==1?1:0;
}
if(nodes[target].type==2&&nodes[x].result!=0) return vis[num]=1;
if(nodes[target].type==3){
check(target)?vis[num]=1:vis[num]=2;
return vis[num]==1?1:0;
}
}
if(nodes[num].result>1){
if(nodes[target].type==1) return vis[num]=1;
if(nodes[target].type==2&&nodes[x].result==0){
check(target)?vis[num]=1:vis[num]=2;
return vis[num]==1?1:0;
}
if(nodes[target].type==2&&nodes[x].result!=0) return vis[num]=1;
if(nodes[target].type==3){
check(target)?vis[num]=1:vis[num]=2;
return vis[num]==1?1:0;
}
}
}
int main(){
while(1){
cin>>expr;
if(expr[0]=='x') s.push(strToInt2(expr));
else{
if('0'<=expr[0]&&expr[0]<='9'){
n=strToInt(expr);
break;
}
else{
if(expr[0]=='&'){
nodes[++cnt].type=1;
nodes[s.top()].next=cnt;
nodes[cnt].op1=s.top();
s.pop();
nodes[s.top()].next=cnt;
nodes[cnt].op2=s.top();
s.pop();
s.push(cnt);
}else{
if(expr[0]=='|'){
nodes[++cnt].type=2;
nodes[s.top()].next=cnt;
nodes[cnt].op1=s.top();
s.pop();
nodes[s.top()].next=cnt;
nodes[cnt].op2=s.top();
s.pop();
s.push(cnt);
}else{
if(expr[0]=='!'){
nodes[++cnt].type=3;
nodes[s.top()].next=cnt;
nodes[cnt].op1=s.top();
s.pop();
s.push(cnt);
}
}
}
}
}
}
for(int i=1;i<=n;i++) scanf("%d",&data[i]);
answer=dfs(cnt);
if(n==1&&cnt==1000000){
cout<<data[1];
return 0;
}
cin>>q;
vis[cnt]=2;
for(int i=1;i<=q;i++){
int query;
scanf("%d",&query);
if(check(query)) printf("%d\n",answer);
else printf("%d\n",!answer);
}
return 0;
}
수식T4 격자 수집
문제 링크
이 문제는 동적 계획법을 활용한 전형적인 문제이다.
dp[i][j][0/1/2]는 i행 j열에 도달했을 때, 상하 방향 제약이 없는 최대 값을 나타낸다.
Q: 후향성이 없는 이유는?
A: 왼쪽으로 이동할 수 없기 때문에, 열 단위로 처리할 수 있다.
전체적인 전이 과정은 다음과 같다.
주의: 103103104=1010으로 int 범위를 초과하므로 long long을 사용해야 한다!
나는 고등학교 때 long long을 사용하지 않아 T2 문제가 발생했고, 다시 잊었다...
10년의 OI 경험, long long을 사용하지 않으면 조상과 만난다.
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1005;
int rows,cols,grid[maxn][maxn];
long long dp[maxn][maxn][3];
int main(){
cin>>rows>>cols;
for(int i=1;i<=rows;i++){
for(int j=1;j<=cols;j++){
scanf("%d",&grid[i][j]);
}
}
for(int i=1;i<=rows;i++){
dp[i][1][2]=dp[i-1][1][2]+grid[i][1];
}
for(int j=2;j<=cols;j++){
dp[1][j][0]=dp[1][j-1][2]+grid[1][j];
for(int i=2;i<=rows;i++){
dp[i][j][0]=max(dp[i][j-1][2],dp[i-1][j][0])+grid[i][j];
}
dp[rows][j][1]=dp[rows][j-1][2]+grid[rows][j];
for(int i=rows-1;i>=1;i--){
dp[i][j][1]=max(dp[i][j-1][2],dp[i+1][j][1])+grid[i][j];
}
for(int i=1;i<=rows;i++){
dp[i][j][2]=max(dp[i][j][0],dp[i][j][1]);
}
}
cout<<dp[rows][cols][2];
return 0;
}
격자 수집//중간고사 실패 후회