#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (1000000000)
int n,m,k;
int main()
{
while (cin>>n>>m>>k)
{
if (n==1||n==2&&!(m%2))
{
puts("-1");continue;
}
while (!(k%n)) k--;
if (k==1)
{
if (m%n) cout<<m<<endl;
else puts("-1");
continue;
}
int ans=(m-1)/k+1;
if (ans==1&&!(m%n)) ans++;
if (!((k-1)%n)&&m%k==k-1) ans++;
if (!(ans%n)) ans++;
cout<<ans<<endl;
}
return 0;
}
As you know, Vova has recently become a new shaman in the city of Ultima Thule. So, he has received the shaman knowledge about the correct bracket sequences. The shamans of Ultima Thule have been using lots of different types of brackets since prehistoric times.
A bracket type is a positive integer. The shamans define a correct bracket sequence as follows:
An empty sequence is a correct bracket sequence.
If {a1, a2, ..., al} and {b1, b2, ..., bk} are
correct bracket sequences, then sequence {a1, a2, ..., al, b1, b2, ..., bk} (their
concatenation) also is a correct bracket sequence.
If {a1, a2, ..., al} —
is a correct bracket sequence, then sequence also is a correct bracket sequence, where v(v > 0) is
an integer.
For example, sequences {1, 1, - 1, 2, - 2, - 1} and {3, - 3} are
correct bracket sequences, and {2, - 3} is not.
Moreover, after Vova became a shaman, he learned the most important correct bracket sequence {x1, x2, ..., xn},
consisting of nintegers. As sequence x is the most
important, Vova decided to encrypt it just in case.
Encrypting consists of two sequences. The first sequence {p1, p2, ..., pn} contains
types of brackets, that is, pi = |xi| (1 ≤ i ≤ n).
The second sequence {q1, q2, ..., qt} contains t integers
— 这些地方必须取负数{x1, x2, ..., xn}.
Unfortunately, Vova forgot the main sequence. But he was lucky enough to keep the encryption: sequences {p1, p2, ..., pn} and{q1, q2, ..., qt}.
Help Vova restore sequence x by the encryption. If there are multiple sequences that correspond to the encryption, restore any of them. If there are no
such sequences, you should tell so.
Input
The first line of the input contains integer n (1 ≤ n ≤ 106).
The second line contains n integers: p1, p2, ..., pn(1 ≤ pi ≤ 109).
The third line contains integer t (0 ≤ t ≤ n),
followed by t distinct integers q1, q2, ..., qt(1 ≤ qi ≤ n).
The numbers in each line are separated by spaces.
Output
Print a single string "NO" (without the quotes) if Vova is mistaken and a suitable sequence {x1, x2, ..., xn} doesn't
exist.
Otherwise, in the first line print "YES" (without the quotes) and in the second line print n integers x1, x2, ..., xn(|xi| = pi; xqj < 0).
If there are multiple sequences that correspond to the encrypting, you are allowed to print any of them.
Sample test(s)
input
2
1 1
0
output
YES
1 -1
input
4
1 1 1 1
1 3
output
YES
1 1 -1 -1
input
3
1 1 1
0
output
NO
input
4
1 2 2 1
2 3 4
output
YES
1 2 -2 -1
贪心，从后向前做，尽可能取左括号。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
using namespace std;
#define MAXN (1000000+10)
#define MAXP (1000000000+10)
int n,m,a[MAXN],ans[MAXN],tot;
bool b[MAXN];
int s[MAXN],size=0;
int main()
{
memset(b,0,sizeof(b));
scanf("%d",&n);tot=n+1;
if (n%2) {printf("NOn");return 0;}
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int p;
scanf("%d",&p);
b[p]=1;
}
for (int i=n;i;i--)
{
if (size==0||s[size]!=a[i]||b[i])
{
s[++size]=a[i];ans[--tot]=-a[i];
}
else ans[--tot]=s[size--];
}
if (size) printf("NOn");
else
{
printf("YESn");
for (int i=1;i<n;i++) printf("%d ",ans[i]);printf("%dn",ans[n]);
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (40000+10)
#define NDEBUG
int t,n;
struct SegMentTree
{
int a[MAXN*10],n;
int M;
SegMentTree(){}
SegMentTree(int _n):n(_n)
{
M=1;
while (M-2<n) M<<=1;
memset(a,0,sizeof(a));
}
void insert(int _x,int c)
{
_x+=M;
if (a[_x]<c)
{
a[_x]=c;
for (_x>>=1;_x;_x>>=1) a[_x]=max(a[_x<<1],a[(_x<<1)^1]);
}
}
int find(int l,int r)
{
int ans=0;
l--;r++;
l+=M;r+=M;
while (l^r^1)
{
if (~l&1) ans=max(ans,a[l+1]);
if (r&1) ans=max(ans,a[r-1]);
l>>=1;r>>=1;
}
return ans;
}
}a;
int main()
{
#ifndef NDEBUG
freopen("poj1631.in","r",stdin);
#endif
scanf("%d",&t);
while (t--)
{
cin>>n;
a=SegMentTree(n);
for (int i=1;i<=n;i++)
{
int value;
scanf("%d",&value);
a.insert(value,a.find(1,value-1)+1);
}
printf("%dn",a.find(1,n));
}
return 0;
}
算法2：
仔细观察推导序列求最大值部分，发现i总从1开始[1,value_i)
于是可二分查找序列Max[I]'=Max[ F[p] ] (1≤p≤i)
Program LCS;
var
a,d,f:array[1..100000] of longint;
n,i,j,len,test:longint;
function search(k:longint):longint;
var
i,j,m:longint;
begin
i:=1; j:=len;
m:=d[(i+j) div 2];
while (i<=j) do
begin
m:=(i+j) div 2;
if (d[m]<k) and (d[m+1]>=k) then exit(m)
else if (d[m]<k) then i:=m+1
else j:=m-1;
end;
end;
begin
read(test);
while (test>0) do
begin
read(n);
len:=1;
fillchar(d,sizeof(d),0);
for i:=1 to n do read(a[i]);
d[1]:=a[1];
f[1]:=1;
for i:=2 to n do
begin
if (a[i]>d[len]) then
begin
inc(len);
d[len]:=a[i];
f[i]:=len;
end
else if (a[i]<=d[1]) then
begin
d[1]:=a[i];
f[i]:=1;
end
else
begin
j:=search(a[i]);
d[j+1]:=a[i];
f[i]:=j+1;
end;
end;
writeln(len);
dec(test);
end;
end.
Program queue;
var
a,b,c,d,n,ans,i,ii:int64;
function is_ok:boolean;
begin
if (a>n) then exit(false);
if (c-a>=0) then
if ((c-a) mod b=0) then
if ((c-a) div b>=-1) then exit(true);
exit(false);
end;
begin
assign(input,'queue.in');
assign(output,'queue.out');
reset(input);
rewrite(output);
read(a,b,c,d,n);
if (a>n) then ans:=0
else ans:=(n-a) div b+1;
while (c<=n) do
begin
if (not(is_ok) ) then inc(ans);
c:=c*d;
if (d=1) then break;
end;
writeln(ans);
close(input);
close(output);
end.
also is a correct bracket sequence, where 
