LA 5916(GCD Guessing Game-质数分组)

现在有一个数x,1 ≤ x≤ n,告诉你n,每次你可以猜一个数y,如果x==y则结束,否则返回gcd(x,y),问最少只要几次就可以保证猜出答案。

Input 

The input file contains several test cases, each of them as described below.

The input contains one integer n2$ \le$n$ \le$10000.

Output

For each test case, write to the output on a line by itself.

Output one integer -- the number of guesses Andrew will need to make in the worst case.

 

Sample Input

6

 

Sample Output

2

首先把所有n以内素分组,每次询问一组素数的积——根据Gcd的性质确定这个数

每次贪心拿一个大质数与一堆小质数配(最右*最左)

 

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (10000)
#define eps (1e-9)
#define For(i,n) for(int i=1;i< =n;i++) #define ForD(i,n) for(int i=n;i;i--) #define Fork(i,k,n) for(int i=k;i<=n;i++) int n,a[MAXN],size=0; bool b[MAXN]; int main() { memset(b,0,sizeof(b));b[1]=1; Fork(i,2,MAXN) { if (!b[i]) b[i]=1,a[++size]=i; For(j,size) { if (i*a[j]>MAXN) break;
b[i*a[j]]=1;
if (!i%a[j]) break;
}
}
// For(i,100) cout< >n)
{
int i=0,head=1,tail=size;
while (a[tail]>n) tail--;
while (head< =tail) { int p=a[tail]; while (p*a[head]<=n) p*=a[head++]; tail--;i++; } cout<

 

CH Adera 3(ZZB的数学作业-构造法初讲)

描述

把一个正整数M分成P个不超过K的正整数的和,满足分成的数不是N的倍数,并且P也不是N的倍数,求这样的P最小是多少?”

输入格式

一个测试点不超过10组数据,每行三个整数N、M、K代表一组数据,以EOF结尾。

输出格式

对于每组数据输出一行,一个整数,即最小的P。

样例输入

3 11 6
2 12 47

样例输出

4
-1

数据范围与约定

对于20%的数据,1<=N,M,K<=20。
对于60%的数据,1<=N,K<=10000。
对于另20%的数据,1<=K<=2。
对于100%的数据,1<=N,M,K<=10^9。

特判 

n=1 m%n肯定不行

n=2 m是偶数 奇数个奇数和≠偶数 不行

否则找最小的k

现在开始维护p,各种特判

由于最后多出来的一部分=k-1是不能合并 所以必须拆

最后维护p

#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;
}

CF 286C(Main Sequence-贪心括号匹配)

C. Main Sequence
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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| = pixqj < 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;
}

UVA 11729(Commando War-按执行时间贪心)




G

Commando War

Input: Standard Input

Output: Standard Output

 

 

“Waiting for orders we held in the wood, word from the front never came

By evening the sound of the gunfire was miles away

Ah softly we moved through the shadows, slip away through the trees

Crossing their lines in the mists in the fields on our hands and our knees

And all that I ever, was able to see

The fire in the air, glowing red, silhouetting the smoke on the breeze”

 

There is a war and it doesn't look very promising for your country. Now it's time to act. You have a commando squad at your disposal and planning an ambush on an important enemy camp located nearby. You have soldiers in your squad. In
your master-plan, every single soldier has a unique responsibility and you don't want any of your soldier to know the plan for other soldiers so that everyone can focus on his task only. In order to enforce this, you brief every individual soldier about his
tasks separately and just before sending him to the battlefield. You know that every single soldier needs a certain amount of time to execute his job. You also know very clearly how much time you need to brief every single soldier. Being anxious to finish
the total operation as soon as possible, you need to find an order of briefing your soldiers that will minimize the time necessary for all the soldiers to complete their tasks. You may assume that, no soldier has a plan that depends on the tasks of his fellows.
In other words, once a soldier  begins a task, he can finish it without the necessity of pausing in between.

 

Input

 

There will be multiple test cases in the input file. Every test case starts with an integer N (1<=N<=1000), denoting the number of soldiers. Each of the following N lines describe a soldier with two integers B (1<=B<=10000) J
(1<=J<=10000)
seconds are needed to brief the soldier while completing his job needs seconds. The end of input will be denoted by a case with N =0 . This case should not be processed.

 

Output

 

For each test case, print a line in the format, “Case X: Y”, where X is the case number & Y is the total number of seconds counted from the start of your first briefing till the completion of all jobs.

 

Sample Input                                               Output for Sample Input

3

2 5

3 2

2 1

3

3 3

4 4

5 5

0

Case 1: 8

Case 2: 15

 


Problem Setter: Mohammad Mahmudur Rahman, Special Thanks: Manzurur Rahman Khan


按照执行时间排序,贪心

可以画图验证。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (1000+10)
#define MAXBi (10000+10)
#define MAXJi (10000+10)
struct arr
{
	int a,b;
	friend bool operator<(arr a,arr b){return a.b>b.b;	}
}a[MAXN];
int n;
int main()
{
	int t=1;
	while (scanf("%d",&n)!=EOF&&n)
	{
		for (int i=1;i<=n;i++) scanf("%d%d",&a[i].a,&a[i].b);
		sort(a+1,a+n+1);
		int p=0,ans=0;
		for (int i=1;i<=n;i++)
		{
			p+=a[i].a;
			ans=max(ans,p+a[i].b);
		}
		printf("Case %d: %dn",t++,ans);
	}
	return 0;
}

UVA 11292(Dragon of Loowater-勇者斗恶龙)

Problem C: The Dragon of Loowater

Once upon a time, in the Kingdom of Loowater, a minor nuisance turned into a major problem.

The shores of Rellau Creek in central Loowater had always been a prime breeding ground for geese. Due to the lack of predators, the geese population was out of control. The people of Loowater mostly kept clear of
the geese. Occasionally, a goose would attack one of the people, and perhaps bite off a finger or two, but in general, the people tolerated the geese as a minor nuisance.

One day, a freak mutation occurred, and one of the geese spawned a multi-headed fire-breathing dragon. When the dragon grew up, he threatened to burn the Kingdom of Loowater to a crisp. Loowater had a major problem.
The king was alarmed, and called on his knights to slay the dragon and save the kingdom.

The knights explained: "To slay the dragon, we must chop off all its heads. Each knight can chop off one of the dragon's heads. The heads of the dragon are of different sizes. In order to chop off a head, a knight
must be at least as tall as the diameter of the head. The knights' union demands that for chopping off a head, a knight must be paid a wage equal to one gold coin for each centimetre of the knight's height."

Would there be enough knights to defeat the dragon? The king called on his advisors to help him decide how many and which knights to hire. After having lost a lot of money building Mir Park, the king wanted to minimize
the expense of slaying the dragon. As one of the advisors, your job was to help the king. You took it very seriously: if you failed, you and the whole kingdom would be burnt to a crisp!

Input Specification:

The input contains several test cases. The first line of each test case contains two integers between 1 and 20000 inclusive, indicating the number n of heads that the dragon has, and the number m of
knights in the kingdom. The next n lines each contain an integer, and give the diameters of the dragon's heads, in centimetres. The following m lines each contain an integer, and specify the heights of the knights of Loowater, also in centimetres.

The last test case is followed by a line containing:

0 0

Output Specification:

For each test case, output a line containing the minimum number of gold coins that the king needs to pay to slay the dragon. If it is not possible for the knights of Loowater to slay the dragon, output the line:

Loowater is doomed!

Sample Input:

2 3
5
4
7
8
4
2 1
5
5
10
0 0

Output for Sample Input:

11
Loowater is doomed!

让最差的骑士优先杀最差的,

否则这个骑士不取。

可以证明这样取最优。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (20000+10)
int n,m,a[MAXN],b[MAXN];
int main()
{
	while (scanf("%d%d",&n,&m)&&n&&m)
	{
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		for (int i=1;i<=m;i++) scanf("%d",&b[i]);
		sort(a+1,a+n+1);sort(b+1,b+m+1);
		int i=1,j=1,cost=0;
		for (;i<=n&&j<=m;i++,j++)
		{
			if (b[j]>=a[i]) cost+=b[j];
			else i--;
		}
		if (i>n) cout<<cost<<endl;
		else cout<<"Loowater is doomed!n";
	}
	return 0;
}

BZOJ 1034([ZJOI2008]泡泡堂BNB-田忌赛马)

1034: [ZJOI2008]泡泡堂BNB

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 682  Solved: 321
[Submit][Status][Discuss]

Description

 第XXXX届NOI期间,为了加强各省选手之间的交流,组委会决定组织一场省际电子竞技大赛,每一个省的代表队由n名选手组成,比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前,对阵双方的教练向组委会提交一份参赛选手的名单,决定了选手上场的顺序,一经确定,不得修改。比赛中,双方的一号选手,二号选手……,n号选手捉对厮杀,共进行n场比赛。每胜一场比赛得2分,平一场得1分,输一场不得分。最终将双方的单场得分相加得出总分,总分高的队伍晋级(总分相同抽签决定)。
作为浙江队的领队,你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚,并将其用一个实力值来衡量。为简化问题,我们假定选手在游戏中完全不受任何外界因素干扰,即实力强的选手一定可以战胜实力弱的选手,而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序,所以所有的队伍都采取了这样一种策略,就是完全随机决定出场顺序。 当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下,浙江队最终分别能得到多少分。

Input

输入的第一行为一个整数n,表示每支代表队的人数。 接下来n行,每行一个整数,描述了n位浙江队的选手的实力值。 接下来n行,每行一个整数,描述了你的对手的n位选手的实力值。 20%的数据中,1<=n<=10; 40%的数据中,1<=n<=100; 60%的数据中,1<=n<=1000; 100%的数据中,1<=n<=100000,且所有选手的实力值在0到10000000之间。

Output

包括两个用空格隔开的整数,分别表示浙江队在最好与最坏的情况下分别能得多少分。不要在行末输出多余的空白字符。

Sample Input

2

1

3

2

4

Sample Output

2 0

样例说明

我们分别称4位选手为A,B,C,D。则可能出现以下4种对战方式,最好情况下可得2分,最坏情况下得0分。

一 二 三 四

浙江 ??? 结果 浙江 ??? 结果 浙江 ??? 结果 浙江 ??? 结果

一号选手 A C 负 A D 负 B C 胜 B D 负

二号选手 B D 负 B C 胜 A D 负 A C 负

总得分 0 2 2 0



田忌赛马加强版。

尽可能让最弱的赢,最强的赢,都不行则最弱打最强

错误的贪心:

让最弱的能赢/平则赢/平,否则让其与最强的打

反例:

2

1 2 6 7

1 2 4 7

 ans1=6

反例ans1=5


最差情况:

容易发现2个队伍的总分一定(2-0,1-1,0-2)

 所以ans2=2n-B队最高分

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXN (100000+10)
int n,a[MAXN],b[MAXN];
int calc()
{
	int i=1,j=1,k=n,l=n,ans=0;
	while (i<=k)
	{
		if (a[i]>b[j]) ans+=2,i++,j++;
		else if(a[k]>b[l]) ans+=2,k--,l--;
		else ans+=(a[i]==b[l]),i++,l--;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
	sort(a+1,a+1+n);sort(b+1,b+1+n);
	cout<<calc()<<' ';
	swap(a,b);
	cout<<2*n-calc()<<endl;
	return 0;
}

fzu_noip 1033 (作业问题-拼最大的2,3,5倍数)

作业问题

时限:1s内存:32M

★问题描述:

小T很喜欢数学,每天老师刚布置完作业,他就开始思考,今天他遇到了困难。

现在有很多的数字,你的任务是找出由这些数字组成的最大的数,并且这个数必须能被2,3,5整除。你可以只用其中一部分的数,但不允许出现前导0。

★数据输入:

输入数据的第一行为一个整数N。(1<=N<=1000)表示给出N个数字,每个数字范围是0—9。接下来一行有N个数,数字由空格隔开。

★结果输出:

输出你找出的最大的数,如果不存在这样的数就输出-1。

输入示例

输出示例

1

0

0

11

3 4 5 4 5 3 5 3 4 4 0

5554443330

8

3 2 5 1 5 2 2 3

-1

 

裸裸的贪心。

满足能被2,5整除,当且仅当数中有0且放在末尾

满足能被3整除,要让sum%3=0.

显然要取尽可能多的位数,先判断是否能全取。

用a[i]表示数字i有几个,b[i]表示%3=i的数字有几个.

若全取后%3=1,则删1个%3=1或2个%3=2.优先删删除数字少的,次优先删数字尽量小的。

若无法全取,也不够删,则无解.

同理%3=2.

若有合法解,数字必从大到小排列。

由于不能有前导0,需特判0,0,0,0……的情况。

var
   a:array[0..9] of longint;
   b:array[0..2] of longint;
   n,i,j,p:longint;
procedure decrease(k:longint);
begin
   if (a[k]>0) then dec(a[k])
   else if (a[k+3]>0) then dec(a[k+3])
   else if (a[k+6]>0) then dec(a[k+6]);
end;
begin
   read(n);
   fillchar(a,sizeof(a),0);
   for i:=1 to n do
   begin
      read(j);
      inc(a[j]);  inc(b[j mod 3]);
   end;
   if (a[0]=0) then
   begin
      writeln('-1');
      halt;
   end;

   p:=b[1] mod 3+(b[2]*2) mod 3;
   if (p=1) then
   begin
      if (b[1]>0) then decrease(1)
      else if (b[2]>1) then begin decrease(2);decrease(2); end
      else
      begin
         writeln('-1');
         halt;
      end;
   end;
   if (p=2) then
   begin
      if (b[2]>0) then decrease(2)
      else if (b[1]>1) then begin decrease(1);decrease(1); end
      else
      begin
         writeln('-1');
         halt;
      end;
   end;

   p:=0;
   for i:=1 to 9 do inc(p,a[i]);
   if (p=0) then
   begin
      writeln('0');
      halt;
   end;


   for i:=9 downto 0 do
      for j:=1 to a[i] do write(i);
   writeln;







end.

CF 253C(找中转行)

C. 光标移动
time limit per test

1 second

memory limit per test

256 megabytes

input

input.txt

output

output.txt

文本编辑器有n行,每行k个字符(显然光标有k+1个位置,标记为1..k+1.

有4个操作:

  • "Up": 光标将向上移1行,列不变。如果上一行字符太少,则光标跑到行末。

  • "Down":
    光标将向下移1行,列不变。如果上一行字符太少,则光标跑到行末。

  • "Right": 光标向右移1格,操作不能在行末进行。

  • "Left":
    光标向左移1格,操作不能在行首进行。

    求出把光标从 (r1, c1) 移向(r2, c2)最小步数.

  • Input

    第一行一个整数 n (1 ≤ n ≤ 100) . 第二行 n个整数a1, a2, ..., an (0 ≤ ai ≤ 105),
    表示每行字符数. 第三行4个整数 r1, c1, r2, c2 (1 ≤ r1, r2 ≤ n, 1 ≤ c1 ≤ ar1 + 1, 1 ≤ c2 ≤ ar2 + 1).

    Output

    输出最小步数

    Sample test(s)
    input
    4
    2 1 6 4
    3 4 4 2
    
    output
    3
    
    input
    4
    10 5 6 4
    1 11 4 2
    
    output
    6
    
    input
    3
    10 1 10
    1 10 1 1
    
    output
    3
    
    Note

    第一组数据若为

    123

    12

    123s567

    1t345

    则最小操作为 "Left", "Down", "Left".

    显然除了直接移(先行后列)外,

    唯一减少操作数的方法便是向中间以外的行数移,以求降低列的移动数。

    一定要注意不是挪到每行直接取abs(行尾-c2)的,因为可能会有往返行尾的路上有更小的,直接取行尾可能拉近它和c2的距离,但是这种操作是不可行的。

    #include<cstdio>
    #include<functional>
    #include<algorithm>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    using namespace std;
    #define MAXN (10000+100)
    int a[MAXN],n;
    int abs2(int a,int b)
    {
    	if (a<b) return b-a;
    	else return a-b;
    }
    int main()
    {
    	freopen("input.txt","r",stdin);
    	freopen("output.txt","w",stdout);
    	scanf("%d",&n);
    	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    	int r1,c1,r2,c2;
    	scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
    	int mi=c1,ans=0,tans=1000000000;
    	if (r1<r2)
    	{
    		ans=r2-r1;
    		for (int i=r1+1;i<=r2;i++) mi=min(mi,a[i]+1);
    		tans=min(tans,ans+abs(mi-c2));
    		for (int i=r1-1,cost=2,mii=mi;i>=1;i--,cost+=2)
    		{
    			mii=min(mii,a[i]+1);
    			tans=min(tans,ans+cost+abs(mii-c2));
    		}
    		for (int i=r2+1,cost=2,mii=mi;i<=n;i++,cost+=2)
    		{
    			mii=min(mii,a[i]+1);
    			tans=min(tans,ans+cost+abs(mii-c2));
    		}
    	}
    	else
    	{
    		ans=r1-r2;
    		for (int i=r1-1;i>=r2;i--) mi=min(mi,a[i]+1);
    		tans=min(tans,ans+abs(mi-c2));
    		for (int i=r2-1,cost=2,mii=mi;i>=1;i--,cost+=2)
    		{
    			mii=min(mii,a[i]+1);
    			tans=min(tans,ans+cost+abs(mii-c2));
    		}
    		for (int i=r1+1,cost=2,mii=mi;i<=n;i++,cost+=2)
    		{
    			mii=min(mii,a[i]+1);
    			tans=min(tans,ans+cost+abs(mii-c2));
    		}
    	}
    	cout<<tans<<endl;
    	return 0;
    }

    POJ 3298(用unique离散化优化zkw线段树)

    Language:
    Antimonotonicity
    Time Limit: 2000MS   Memory Limit: 65536K
    Total Submissions: 2753   Accepted: 1175

    Description

    Mary数列是指在一个长度为n的序列(元素大小不超过n)中找到如下的子序列:

    Mary0 > Mary1 < Mary2 > Mary3 < ...

    请求出它的最长序列大小。

    Input

    第一行为数据数 T ≤ 50

    接下来T行,每行第一个数n( 30000)表示原序列大小,接下来n个数为给定序列

    Output

    对每组数据输出一行为Mary数列最长长度。

    Sample Input

    4
    5 1 2 3 4 5
    5 5 4 3 2 1
    5 5 1 4 2 3
    5 2 4 1 3 5

    Sample Output

    1
    2
    5
    3

    Source

    这题和LIS有异曲同工之妙,都是在给定区间找最大值

    显然可以建立两棵线段树(并互相传递值),表示(...?<a[i]) 中使得“..”长度最长的大小,

    由于用Unique(指针头,指针尾+1)离散了序列,用-INF和INF表示边界(特别注意离散Hash-map<int,int> Hpos一定要开在Struct外,否则反复建会超时(平衡树用来干这个……)

    于是t.t[i][j] 表示第ith线段树的端点值。

    i=0表示(1,3,5... 即除1外前面跟了<号的)的数

    i=1表示(2,4,6... 即前面跟>的)数


    于是本题转化为维护(..?<)的最长长度。

    同理建立(..?>),注意特判序列开头那个数(第二个序列的长度必须超过1,表示其并非开头)


    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<cctype>
    #include<functional>
    #include<algorithm>
    #include<iostream>
    #include<map>
    using namespace std;
    #define MAXN (30000+10)
    #define INF (2139062143)
    #define NDEBUG
    map<int,int> hpos;
    struct SegMentTree  //t[0]->'?<' t[1]->'?>'
    {
    	int n,M,t[2][MAXN*5],a[MAXN],a_sort[MAXN],size;
    	SegMentTree(){}
    	SegMentTree(int _n):n(_n)
    	{
    		M=1;while (M-2<n) M<<=1;
    		memset(t,0,sizeof(t));
    		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    		memcpy(a_sort,a,sizeof(a));
    		sort(a_sort+1,a_sort+n+1);
    		#ifndef NDEBUG
    		for (int i=1;i<=n;i++) cout<<a_sort[i]<<' ';
    		cout<<endl;
    		#endif
    		size=unique(a_sort+1,a_sort+n+1)-(a_sort+1);
    		#ifndef NDEBUG
    		for (int i=1;i<=size;i++) cout<<a_sort[i]<<' ';
    		cout<<endl;
    		cout<<size;
    		#endif
    		for (int i=1;i<=size;i++) hpos[a_sort[i]]=i;
    		hpos[-INF]=0;hpos[INF]=size+1;
    	}
    	void update(int x,int type)
    	{
    		for (x>>=1;x;x>>=1) t[type][x]=max(t[type][x<<1],t[type][(x<<1)^1]);
    	}
    	void insert(int x,int c,int type)
    	{
    		x=hpos[x]+M;
    		if (t[type][x]<c)
    		{
    			t[type][x]=c;
    			update(x,type);
    		}
    	}
    	int find(int l,int r,int type)
    	{
    		l=hpos[l];r=hpos[r];
    //		if (type) l++; else r--;
    		#ifndef NDEBUG
    		cout<<l<<' '<<r<<';'<<endl;
    		#endif
    
    		l+=M;r+=M;
    		int ans=0;
    		if (l>=r-1) return 0;
    		for (;l^r^1;l>>=1,r>>=1)
    		{
    			if (~l&1) ans=max(ans,t[type][l+1]);
    			if (r&1) ans=max(ans,t[type][r-1]);
    		}
    		return ans;
    	}
    
    }t;
    int tt,n,ans;
    int main()
    {
    	#ifndef NDEBUG
    	freopen("poj3298.in","r",stdin);
    	#endif
    	scanf("%d",&tt);
    	while (tt--)
    	{
    		ans=0;
    		scanf("%d",&n);
    		t=SegMentTree(n);
    		for (int i=1;i<=n;i++)
    		{
    			int value=t.a[i];
    			int value1=t.find(-INF,value,0)+1;
    			int value2=t.find(value,INF,1)+1;
    			t.insert(value,value1,1);
    			ans=max(ans,value1);
    			#ifndef NDEBUG
    			cout<<"Add?> "<<value<<" f[i]="<<value1<<endl;
    			#endif
    			if (value2==1) continue;
    			t.insert(value,value2,0);
    			ans=max(ans,value2);
    			#ifndef NDEBUG
    			cout<<"Add?< "<<value<<" f[i]="<<value2<<endl;
    			#endif
    		}
    		cout<<ans<<endl;
    		#ifndef NDEBUG
    		for (int i=1;i<=t.M*2;i++) if (t.t[0][i]) cout<<i<<':'<<t.t[0][i]<<' ';
    		cout<<endl;
    		#endif
    	}
    
    	return 0;
    }

    其实这题有更Easy的解法……贪心!

    如果我们把原序列看成一条直线,且另a[0]和a[n+1]=-INF

    那么如图所示


    显然当最后的折现向下时:


    显然解为凸点数*2

    而当最后的折线向上时:



    解为凸点数*2-1

    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
    #define MAXN (30000+10)
    int tt,n,a[MAXN];
    int main()
    {
    	scanf("%d",&tt);
    	while (tt--)
    	{
    		scanf("%d",&n);
    		int ans=0;
    		a[0]=a[n+1]=-0xfffffff;
    		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    		for (int i=1;i<=n;i++) if (a[i-1]<a[i]&&a[i]>a[i+1]) ans++;
    		ans*=2;
    		if (a[n-1]<a[n]) ans--;
    		cout<<ans<<endl;
    	}
    
    	return 0;
    }



    Tyvj Q1028(调整法)

    Q1028 - Unit7 - 堆积木

    From Admin    Normal (OI)
    总时限:10s    内存限制:128MB    代码长度限制:64KB

    描述 Description

    现在有N块积木,每块积木都有自重Weight和正常状态下的承重能力Force,现在要把这N块积木垂直的垒在一起,但是有可能某块积木的负重超过了它在正常状态下的承重能力,那么这块积木就有被压坏的危险,请问应该如何堆这N块积木使得N块积木中最大的压力指数最小。

    这里定义压力指数为该积木的负重与其在正常状态下的承重能力的差值。

    输入格式 InputFormat

    第一行为一个正整数N,表示有N块积木。
    第二行到第 N+1 行,每行两个整数数,分别是第i个积木的Weight和Force

    输出格式 OutputFormat

    输出共一行,表示最大压力指数的最小值。

    样例输入 SampleInput [复制数据]

    2
    100 0
    1000 100
    

    样例输出 SampleOutput [复制数据]

    0

    数据范围和注释 Hint

    样例解释:
    把Weight为100的积木放在Weight为1000的积木上,下面积木的压力指数为100 - 100 = 0,另外一块积木的压力指数和它的相等。

    对于30% 的数据,1 <= N <= 3
    对于60% 的数据,1 <= N <= 1000
    对于100%的数据,1 <= N <= 50000
    对于100%的数据,1 <= Weight <= 10000,1 <= Force <= 10^9

    时间限制 TimeLimitation

    1s

    来源 Source

    tjz


    对于最优方案:

    因为F(N)-(w1+w2+..wn-1)<F(1)-(w2+...+wn-1+wn)

    化简得  F(n)+wn<F1+w1

    调整ing。。。

    也就是说对于最优方案有 Fi+wi<Fi-1+wi-1


    Program block;
    uses math;
    const
       maxn=50000;
    var
       n,i,j,ans,totw:longint;
       w,f:array[1..maxn] of longint;
    
    procedure qsort(l,r:longint);
    var
       i,j,m,p:longint;
    begin
       i:=l;
       j:=r;
       m:=w[(i+j) div 2]+f[(i+j) div 2];
       repeat
          while (w[i]+f[i]<m) do inc(i);
          while (w[j]+f[j]>m) do dec(j);
          if i<=j then
          begin
             p:=w[i];w[i]:=w[j];w[j]:=p;
             p:=f[i];f[i]:=f[j];f[j]:=p;
             inc(i);dec(j);
          end;
       until i>j;
       if (l<j) then qsort(l,j);
       if (i<r) then qsort(i,r);
    end;
    begin
       read(n);
       for i:=1 to n do
       begin
          read(w[i],f[i]);
       end;
       qsort(1,n);
       ans:=-f[1];
       totw:=0;
       for i:=1 to n do
       begin
          ans:=max(ans,totw-f[i]);
          inc(totw,w[i]);
    
       end;
       writeln(ans);
    
    end.