題目大意(跟BZOJ上的不一樣!!!):
這是一道互動題!
記憶體限制為32MB!
先給你一個整數K(K<=1000000),然後按順序給你未知個整數a1~an(n<=15000000,n不輸入)
要求你求出一個長度為K的字典序最大的子序列!
這是一道非常厲害,非常有想法的互動題!
但是BZOJ不支援互動,是以就變成了一個可以上來把所有數讀進來再做的SB題
樸素的做法是維護一個單調遞減的棧,開始的n-k個直接推入棧中,最後k個每推進去一個元素就把棧底輸出并删掉(其實像是單調隊列?)
這個做法在BZOJ上就可以直接AC了
但是我們要追求本真,做POI題的目的就是拓展思維
我們考慮32MB怎麼做
這種記憶體限制下不能開O(N)的數組但是可以開O(K)的數組啊
我們可以想到,由于最後讓輸出長度為K的子序列,是以任何時刻隻要加入這個元素之後棧中元素超過K個,這個元素就不用加入了
這樣我們就得到了一種空間O(K)的做法
但是我們又面臨着一個問題,在沒讀入完之前,我們并不知道N是多少,我們也就不知道在什麼時候需要輸出棧底
這裡我們可以用一個小技巧,延遲K個處理,即先讀入K個數,當讀入第i+K個數時,我們處理讀入第i個數時應該幹的事情
這樣我們在讀入N個數後,其實隻做了前N-K個數要做的事情
這些數要做的事情沒有差別,都是直接扔進帶空間限制的單調棧裡
當我們讀入完成,我們就可以處理最後K個數了,這時每次加入都輸出棧底并彈出就可以了
附BZOJ上的AC代碼,其實下面主函數部分就是POI官網上能AC的代碼
/*************************************************************************}
{* *}
{* XVI Olimpiada Informatyczna *}
{* *}
{* Zadanie: Architekci (ARC) *}
{* Plik: carclib.c *}
{* Autor: Bartosz Gorski *}
{* Opis: Biblioteka do wczytywania danych wejsciowych i wypisywania *}
{* wyniku *}
{* *}
{*************************************************************************/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define MAGIC_BEGIN -435634223
#define MAGIC_END -324556462
#define MIN_K 1
#define MAX_K 1000000
#define MAX_N 15000000
#define MIN_A 1
#define MAX_A 1000000000
#define MIN_TYP 1
#define MAX_TYP 3
#define MIN_PAR 0
#define MAX_PAR 1000000000
#define ERROR 0
#define CORRECT 1
#define unlikely(x) __builtin_expect(!!(x), 0)
static int init = 0; // czy zostala juz wywolana funkcja inicjuj()
static int lib_n; // ile biblioteka podala juz liczb
static int con_k; // ile zawodnik podal liczb
static int N, K, A, TYP, PAR; // parametry testu wczytywane z pliku
static int bre, len_sub, bou, is_end; // zmienne pomocnicze
static int rand2_status = 198402041;
static inline int rand2(int a, int b){
rand2_status = rand2_status * 1103515245 + 12345;
int x = rand2_status;
if (x < 0) x = -x; // -2^31 sie nie zdarza :D
x >>= 1;
x = a + x % (b - a + 1);
return x;
}
/* test losowy */
static inline int random_test()
{
return rand2(1, A);
}
/* test z dlugim podciagiem nierosnacym */
static inline int decreasing_test()
{
int tmp;
if(bre == 0) {
bre = rand2(0, (N - lib_n + 1 - len_sub));
tmp = A;
A -= rand2(0, (A - 1) / len_sub);
len_sub--;
}
else {
bre--;
tmp = rand2(1, A);
}
return tmp;
}
/* test z dlugim podciagiem niemalejacym */
static inline int increasing_test()
{
return bou - decreasing_test();
}
static void finish(int res, char *com)
{
if(res == ERROR)
printf("%s\n", com);
exit(0);
}
/* Inicjuje dane wejsciowe i zwraca liczbe projektow */
int inicjuj()
{
if(init == 1)
finish(ERROR, "Program zawodnika moze wywolac funkcje inicjuj tylko raz!!!");
init = 1;
scanf("%d", &K);
if (K > 0){
TYP = 0;
N = MAX_N + 2;
return K;
}
int magic_begin, magic_end;
scanf("%d%d", &magic_begin, &TYP);
if(magic_begin != MAGIC_BEGIN || TYP < MIN_TYP || TYP > MAX_TYP)
finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
scanf("%d%d%d%d", &N, &K, &A, &PAR);
if(N < 1 || N > MAX_N || N < K || K > MAX_K || A < MIN_A || A > MAX_A
|| PAR < MIN_PAR || PAR > MAX_PAR)
finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
scanf("%d", &magic_end);
if(magic_end != MAGIC_END)
finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
con_k = 0;
lib_n = 0;
is_end = 0;
if(TYP == 2 || TYP == 3) {
len_sub = PAR;
bre = 0;
}
if(TYP == 2)
bou = A--;
return K;
}
/* Sluzy do wczytania ciagu reprezentujacego jakosci projektow */
int wczytaj()
{
if(unlikely(init == 0))
finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
if(unlikely(lib_n > N || is_end == 1))
finish(ERROR, "Program zawodnika wywolal funkcje wczytaj po otrzymaniu informacji o koncu ciagu!!!");
if(unlikely(lib_n == N))
return 0;
lib_n++;
switch (TYP) {
case 0:
scanf("%d", &A);
if(A == 0)
is_end = 1;
return A;
break;
case 1: return random_test(); break;
case 2: return increasing_test(); break;
case 3: return decreasing_test(); break;
default:
finish(ERROR, "Nieznany typ testu");
}
return -1;
}
/* Sluzy do wypisania wyznaczonego podciagu */
void wypisz(int jakoscProjektu)
{
if(init == 0)
finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
printf("%d\n", jakoscProjektu);
if(++con_k == K)
finish(CORRECT, "");
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000010
using namespace std;
int a[N],s[N],h=1,t,k;
void push(int x)
{
while(h<=t&&s[t]<x) t--;
if(t==k) return;
t++;s[t]=x;
}
int main()
{
k=inicjuj();
int i,j,x,y;
for(i=1;i<=k;i++)
a[i]=wczytaj();
int now=1;
while(x=wczytaj())
{
push(a[now]);
a[now]=x;
now++;
if(now==k+1) now=1;
}
j=now;
do
{
push(a[j]);
printf("%d\n",s[h]);
h++;
j++;
if(j==k+1) j=1;
}while(j!=now);
}