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

CF 286A(Lucky Permutation-数列找规律)

A. Lucky Permutation
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A permutation p of size n is the sequence p1, p2, ..., pn,
consisting of n distinct integers, each of them is from 1 to n (1 ≤ pi ≤ n).

A lucky permutation is such permutation p, that any integer i (1 ≤ i ≤ n) meets
this condition ppi = n - i + 1.

You have integer n. Find some lucky permutation p of
size n.

Input

The first line contains integer n (1 ≤ n ≤ 105)
— the required permutation size.

Output

Print "-1" (without the quotes) if the lucky permutation p of size n doesn't
exist.

Otherwise, print n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) after
a space — the required permutation.

If there are multiple answers, you can print any of them.

Sample test(s)
input
1
output
1
input
2
output
-1
input
4
output
2 4 1 3
input
5
output
2 5 3 1 4 

找规律

如图所示



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
using namespace std;
int n;
int main()
{
	cin>>n;
	if (n%4>1)
	{
		cout<<"-1n";
		return 0;
	}
	for (int i=1;i<=n/2;i++)
	{
		if (i%2) cout<<i+1<<' ';
		else cout<<(n-i+2)<<' ';
	}
	int m=n/2;
	if (n%4==1)
	{
		cout<<m+1;
		if (m+1<n) cout<<' ';
		m++;
	}
	for (int i=m+1;i<n;i++)
	{
		if ((i-m)%2) cout<<n-i<<' ';
		else cout<<i-1<<' ';
	}
	if (m+1<n) cout<<(n-1);
	cout<<endl;
	return 0;
}

POJ 1631(O(nlogn)LIS的2种做法)

Language:
Bridging signals
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 8574   Accepted: 4635

Description

对于一个二分图的完全匹配,请找出最多的边使其两两不相交。

Input

第一行为测试数据数t,
对于每组数据,第一行为匹配数 p < 40000,
接下来p行,每行1个数a[i],表示左边第i个端点与右边第a[i]个端点相连

Output

对每组数据,输出一行ans,表示最大不相交匹配数

Sample Input

4
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
8
8
7
6
5
4
3
2
1
9
5
8
9
2
3
1
7
4
6

Sample Output

3
9
1
4

Source

这题显然可以转化为a[i]的LIS

LIS的一般做法如下:

f[i]表示以i为最后一个元素的最长序列数,

f[i]=f[j]+1(a[j]<a[i],j<i)

nLogn 算法1:

显然上面的方程有1维n是用来求‘小于a[i]且在a[i]前面的,最大的数‘

单从这个定义考虑,

于是问题转化成-维护序列max(f[i]),每一次增加1个点的值,求[1,value_i)的最大值(若无值则为0)

不妨用一个zkw线段树维护(本题max(f[i])的长度=n,若没有这个条件时间会退化到O(nLogT)(T为a[i]的最大值),那么请把原序列排序O(nLogn)+离散化O(n),这样复杂度就有O(nLogT)降至O(nLogn)    ).

程序1如下:

#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.




HDU 1865(高精斐波那契)

高精斐波那契

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<string>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (200+10)
#define F (1000)
struct bign
{
	int len;
	int a[1000];
	bign operator+(const bign& b)
	{
		bign c;
		memset(c.a,0,sizeof(c.a));
		c.len=max(len,b.len)+1;
		for (int i=1;i<=c.len;i++)
		{
			c.a[i]+=a[i]+b.a[i];
			c.a[i+1]+=c.a[i]/F;
			c.a[i]=c.a[i]%F;
		}
		if (c.a[c.len]==0&&c.len>1) c.len--;
		return c;
	}
	bign operator= (int num)
	{
		memset(a,0,sizeof(a));
		a[1]=num;
		len=1;
		return *this;
	}


};







bign f[MAXN];
int n;
int main()
{
	cin>>n;
	f[1]=1;f[2]=2;


	for (int i=3;i<=200;i++)
		f[i]=f[i-1]+f[i-2];

	for (int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		int j=s.length();
		cout<<f[j].a[f[j].len];
		for (int k=f[j].len-1;k>=1;k--)
		{
			if (f[j].a[k]<100) cout<<"0";
			if (f[j].a[k]<10) cout<<"0";
			printf("%d",f[j].a[k]);
		}
		cout<<"n";



	}
//	for (int i=1;i<=200;i++) cout<<f[i].len;

	/*
	for (int j=1;j<=200;j++)
	{
		cout<<f[j].a[f[j].len];
		for (int k=f[j].len-1;k>=1;k--)
		{
			if (f[j].a[k]<100) cout<<"0";
			if (f[j].a[k]<10) cout<<"0";
			printf("%d",f[j].a[k]);
		}
		cout<<"n";

	}*/
	return 0;
}

ZOJ 2527(最长等差数列)

随便给一串数列,求最长等差数列

3方水过,回头附n^2logn算法 (dp[i][j][k]=dp[i][k]+1)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (10000+10)
int n,a[MAXN];
int main()
{
	while (scanf("%d",&n)!=EOF)
	{
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		sort(a+1,a+1+n);
		int ans=2;
		for (int i=1;i<=n;i++)
			for (int j=i+1;j<=n;j++)
			{
				int dd=a[j]-a[i],now=j,tot=2;
				for (int k=j+1;k<=n;k++)
				{
					if (a[k]-a[now]==dd)
					{
						tot++;
						now=k;
					}
				}
				ans=max(ans,tot);

			}
		cout<<ans<<endl;

	}



	return 0;
}

艾呀喵啊 (特判与大数)

题目描述:

艾星人和喵星人开战了!

但是CWY发现,这只是大宇宙意志的一场“阴谋”,旨在控制艾星和喵星的人口数量。

战争最后的结果无非就是两败俱伤,人口锐减。

但是CWY想知道是艾星和喵星的人口总数是多少,以此预知战争的伤亡情况。

艾星和喵星人口总数为n,分别标号1到n,其中艾星人的标号是1到n中属于给定的等差数列或等比数列的数字。

给定等差数列的首项a,公差b,等比数列的首项c,公比d,你的任务是求出艾星人的个数。

输入格式:

一行,5个整数,分别是a,b,c,d,n。

(1≤a,b,c,n≤1012,  1≤d≤105。)

对于80%的数据,1≤n≤1000000。

输出格式:

一个整数,表示艾星人个数。

输入输出样例:

输入样例

1  1  1  2  1000

3  3  1  2  1000

452  24  4  5  600

输出样例

1000

343

10

样例解释

产生的等差数列是:1,2,3,4,….

产生的等比数列是:1,2,4,8,….

所以【1,1000】范围内所有标号都是艾星人的。

 

艾星人的10个数分别是: 4,20,100,452,476,500,524,548,572,596

 

 

今天不知道为什么调试器暴走……

而且把a>n的特判给打反

这题就是先算出等比的,再算等差(指数函数很快,记得用int64) ,再特判

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.

POJ 3270(Cow Sorting)

这题主要是交换时要求代价最小

先找到环   相同数字 与   同列 相连

1  第一行为起始序列   第二行为目标序列

   1 4 2 5

   1 2
3 4 5

把一个环中最小的那个与指向的数交换

   1 3
2 4 5

   1 2
3 4 5

最后交换3 2

   1 2
3 4 5

   1 2
3 4 5

或则调来序列中最小的那个数与环中最小数替换(乘船问题?)

这样就能得到最优解

ans+=min(  (sizi-2)*mini+sumi, 

    (sizi+1)*minn+mini+sumi

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (10000+10)
#define MAXAI (100000+10)
int n,a[MAXN],a2[MAXN],hpos[MAXAI],ans=0;
bool b[MAXN];

int main()
{
//	freopen("cowsorting.in","r",stdin);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	memcpy(a2,a,sizeof(a));
	sort(a2+1,a2+1+n,less<int>());
	int minn=a2[1];
	memset(b,false,sizeof(b));
	for (int i=1;i<=n;i++)
		hpos[a[i]]=i;


	for (int i=1;i<=n;i++)
	{
//		cout<<a2[i]<<' '<<a[i]<<endl;
		if (!b[i]&&a2[i]!=a[i])
		{
			b[i]=1;
			int mini=a[i],start=i,sizi=1,sumi=a[i];
			int now=hpos[a2[i]];
			while (now!=start)
			{
				b[now]=1;
				sizi++;
				sumi+=a[now];
				mini=min(mini,a[now]);
				now=hpos[a2[now]];
			}
			ans+=min((sizi-2)*mini+sumi,(sizi+1)*minn+mini+sumi);

		}
	}





///000
//	for (int i=1;i<=n;i++) printf("%d ",a2[i]);
///000
	printf("%dn",ans);

//	while (1);
	return 0;
}