1R/2016 10 08 - Revision history

Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:15Z

Repair pages found by live-compare batch 0001

175.124.46.11 at 16:05, 7 October 2016

2016-10-07T16:05:59Z

← Older revision		Revision as of 16:05, 7 October 2016
Line 220:		Line 220:
	= 아이디어 =		= 아이디어 =
	== 15이원준 ==		== 15이원준 ==
	* Binary Indexed Tree를 사용했습니다.		* 구간합은 Binary Indexed Tree를 사용했습니다.
			* 자두나무는 dp로 풀었습니다.(냅색을 약간 응용했습니다.)
	== 박인서 ==		== 박인서 ==

	== 곽정흠 ==		== 곽정흠 ==

175.124.46.11 at 16:05, 7 October 2016

2016-10-07T16:05:24Z

← Older revision		Revision as of 16:05, 7 October 2016
Line 180:		Line 180:
	}		}

			=== 자두나무 ===
			#include<iostream>
			#include<algorithm>

			using namespace std;

			int arr[32][1001] = {0,};
			int ina[1001] = {0,};
			int main(){
			int n, m;
			cin>>n>>m;
			for(int i = 1; i<=n; i++){
			scanf("%d", &ina[i]);
			}
			int place = 1;
			for(int i = 1; i<=m+1; i++){
			for(int j = 1; j<=n; j++){
			int tmp = arr[i][j-1];
			if(ina[j] == place){
			tmp++;
			}
			arr[i][j] = max(tmp, arr[i-1][j]);
			}
			if(i%2){
			place = 2;
			}
			else{
			place = 1;
			}
			}

			cout<<arr[m+1][n];

			}
	== 박인서 ==		== 박인서 ==

175.124.46.11 at 16:04, 7 October 2016

2016-10-07T16:04:52Z

← Older revision		Revision as of 16:04, 7 October 2016
Line 4:		Line 4:
	* [https://www.acmicpc.net/problem/11659\|구간 합 구하기 4]		* [https://www.acmicpc.net/problem/11659\|구간 합 구하기 4]
	* [https://www.acmicpc.net/problem/2042\|구간 합 구하기]		* [https://www.acmicpc.net/problem/2042\|구간 합 구하기]
			* [https://www.acmicpc.net/problem/2240\|자두나무]
	= 참가자 =		= 참가자 =
	* 15이원준		* 15이원준

175.124.46.11 at 15:27, 7 October 2016

2016-10-07T15:27:40Z

← Older revision		Revision as of 15:27, 7 October 2016
Line 186:		Line 186:
	= 아이디어 =		= 아이디어 =
	== 15이원준 ==		== 15이원준 ==
			* Binary Indexed Tree를 사용했습니다.
	== 박인서 ==		== 박인서 ==

	== 곽정흠 ==		== 곽정흠 ==

175.124.46.11: {CREATE}

2016-10-07T15:26:25Z

{CREATE}

New page

__TOC__

= 오늘의 문제 =
* [https://www.acmicpc.net/problem/11659|구간 합 구하기 4]
* [https://www.acmicpc.net/problem/2042|구간 합 구하기]

= 참가자 =
* 15이원준

= 코드 =
== 15이원준 ==
=== 구간 합 구하기 4 ===
#include<iostream>

using namespace std;

long long int arr[4000000] = { 0, };
int start = 1;

int sort(int n){
while(n){
int p = (n-1) / 2;
if(n%2){
arr[p] = arr[n] + arr[(p+1)*2];
}
else{
arr[p] = arr[n] + arr[(p+1)*2 - 1];
}
n = p;
}
}
long long int initSort(int n){
if(n >= start){
return arr[n];
}
if(arr[n]){
if(arr[n] == -1){
return 0;
}
return arr[n];
}
long long int tmp1 = initSort((n+1)*2);
long long int tmp2 = initSort((n+1)*2 -1);
long long int tmp = tmp1 + tmp2;
if(tmp == 0){
arr[n] = -1;
return 0;
}
return arr[n] = tmp;
}
long long int sum(int s, int e){
long long int ans = 0;
while(s < e){
if(s%2){
s = (s-1)/2;
}
else{
ans += arr[s];
s = s/2;
}
if(e%2){
ans += arr[e];
e = (e-2)/2;
}
else{
e = (e-1)/2;
}
}
if(s == e){
ans += arr[s];
}
return ans;
}

int main(){
int n,m,k;
cin>>n>>m;
while(n > start){
start *= 2;
}
start -= 1;
for(int i = 0; i<n; i++){
scanf("%d",&arr[start + i]);
}
initSort(0);
for(int i = 0; i< m; i++){
int tmp1, tmp2;
scanf("%d %d", &tmp1, &tmp2);
printf("%lld\n", sum(start-1 + tmp1, start-1+tmp2));
}
}

=== 구간 합 구하기 ===
#include<iostream>

using namespace std;

long long int arr[4000000] = { 0, };
int start = 1;

void sort(int n){
while(n){
int p = (n-1) / 2;
if(n%2){
arr[p] = arr[n] + arr[n+1];
}
else{
arr[p] = arr[n] + arr[n-1];
}
n = p;
}
}
long long int initSort(int n){
if(n >= start){
return arr[n];
}
if(arr[n]){
if(arr[n] == -1){
return 0;
}
return arr[n];
}
long long int tmp1 = initSort((n+1)*2);
long long int tmp2 = initSort((n+1)*2 -1);
long long int tmp = tmp1 + tmp2;
if(tmp == 0){
arr[n] = -1;
return 0;
}
return arr[n] = tmp;
}
long long int sum(int s, int e){
long long int ans = 0;
while(s < e){
if(s%2){
s = (s-1)/2;
}
else{
ans += arr[s];
s = s/2;
}
if(e%2){
ans += arr[e];
e = (e-2)/2;
}
else{
e = (e-1)/2;
}
}
if(s == e){
ans += arr[s];
}
return ans;
}

int main(){
int n,m,k;
cin>>n>>m>>k;
while(n > start){
start *= 2;
}
start -= 1;
for(int i = 0; i<n; i++){
scanf("%d",&arr[start + i]);
}
initSort(0);

for(int i = 0; i< m+k; i++){
int tmp1, tmp2, tmp3;
scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
if(tmp1 == 1){
arr[start + tmp2 -1] = tmp3;
sort(start + tmp2 -1);
}
else{
printf("%lld\n", sum(start-1 + tmp2, start-1+tmp3));
}
}
}

== 박인서 ==

== 곽정흠 ==

= 아이디어 =
== 15이원준 ==

== 박인서 ==

== 곽정흠 ==