BZOJ 2241([SDOI2011]打地鼠-二分判断+贪心)

Description

打地鼠是这样的一个游戏:地面上有一些地鼠洞,地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时,用锤子砸其头部,砸到的地鼠越多分数也就越高。

游戏中的锤子每次只能打一只地鼠,如果多只地鼠同时探出头,玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了,所以你改装了锤子,增加了锤子与地面的接触面积,使其每次可以击打一片区域。如果我们把地面看做M*N的方阵,其每个元素都代表一个地鼠洞,那么锤子可以覆盖R*C区域内的所有地鼠洞。但是改装后的锤子有一个缺点:每次挥舞锤子时,对于这R*C的区域中的所有地洞,锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中,每个地洞必须至少有1只地鼠,且如果某个地洞中地鼠的个数大于1,那么这个地洞只会有1只地鼠被打掉,因此每次挥舞锤子时,恰好有R*C只地鼠被打掉。由于锤子的内部结构过于精密,因此在游戏过程中你不能旋转锤子(即不能互换RC)。

你可以任意更改锤子的规格(即你可以任意规定RC的大小),但是改装锤子的工作只能在打地鼠前进行(即你不可以打掉一部分地鼠后,再改变锤子的规格)。你的任务是求出要想打掉所有的地鼠,至少需要挥舞锤子的次数。

Hint:由于你可以把锤子的大小设置为1*1,因此本题总是有解的。

Input

 第一行包含两个正整数MN

下面M行每行N个正整数描述地图,每个数字表示相应位置的地洞中地鼠的数量。

Output

输出一个整数,表示最少的挥舞次数。

Sample Input

3 3



1 2 1



2 4 2



1 2 1



Sample Output



4



【样例说明】



使用2*2的锤子,分别在左上、左下、右上、右下挥舞一次。



【数据规模和约定】





对于100%的数据,1<=M,N<=100,其他数据不小于0,不大于10^5

二分判断+贪心

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#define MAXN (100+10)
#define INF (1000000000)
#define For(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n,m,a[MAXN][MAXN],a2[MAXN][MAXN];
int is_ok(int l,int r)
{
	memcpy(a2,a,sizeof(a));
	int sum=0;
	For(i,n-l+1) For(j,m-r+1)
		if(a2[i][j])
		{
			int delta=a2[i][j];sum+=delta;
			for (int k=i;k<=i+l-1;k++)
				for (int k2=j;k2<=j+r-1;k2++)
					if (a2[k][k2]<delta) return 0;
					else a2[k][k2]-=delta;
		}
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	int cnt=0,ans=0;
	For(i,n) For(j,m) {scanf("%d",&a[i][j]);cnt+=a[i][j];}
	For(i,n) For(j,m)
	{
		if (i*j<ans) continue;
		if (!(cnt%(i*j))&&is_ok(i,j)*i*j==cnt)
		{
			ans=i*j;
		}
	}
	cout<<cnt/ans<<endl;
	return 0;
}

CF 287B(Pipeline-二分)

B. Pipeline
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vova, the Ultimate Thule new shaman, wants to build a pipeline. As there are exactly n houses in Ultimate Thule, Vova wants the city to have exactly n pipes,
each such pipe should be connected to the water supply. A pipe can be connected to the water supply if there's water flowing out of it. Initially Vova has only one pipe with flowing water. Besides, Vova has several splitters.

A splitter is a construction that consists of one input (it can be connected to a water pipe) and x output pipes. When a splitter is connected to a water
pipe, water flows from each output pipe. You can assume that the output pipes are ordinary pipes. For example, you can connect water supply to such pipe if there's water flowing out from it. At most one splitter can be connected to any water pipe.


The figure shows a 4-output splitter

Vova has one splitter of each kind: with 234,
..., k outputs. Help Vova use the minimum number of splitters to build the required pipeline or otherwise state that it's impossible.

Vova needs the pipeline to have exactly n pipes with flowing out water. Note that some of those pipes can be the output pipes of the splitters.

Input

The first line contains two space-separated integers n and k (1 ≤ n ≤ 10182 ≤ k ≤ 109).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cincout streams
or the %I64dspecifier.

Output

Print a single integer — the minimum number of splitters needed to build the pipeline. If it is impossible to build a pipeline with the given splitters, print -1.

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

这题显然优先找大的

直到找不下去了,判断无解或者拿个与需要的分水器相等的(显然有)

因为一个k的分水器只能增加k-1条通道

所以列方程


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXN (1000000000000000000)
#define MAXK (1000000000)
long long n,k;
long long bin_s(long long l,long long r)
{
	if (n==1) return 0;
	while (r-l>1)
	{
		long long  m=(l+r)/2;
		if ((m+k-1)*(k-m)>2*(n-1)) l=m;
		else r=m;
	}
	if ((l+k-1)*(k-l)>2*(n-1)) l=r;
	if ((l+k-1)*(k-l)<2*(n-1)) l--;

	if (l==0) return -1;
	return k-l;
}
int main()
{
	cin>>n>>k;
	cout<<bin_s(1,k-1)<<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.




分割矩阵 (二分范围[L,R))

   分割矩阵

                   (browine.c/cpp/pas)

【问题描述】

    有N*M的一个非负整数矩阵。现在要把矩阵分成A*B块。矩阵先水平地切A-1刀,把矩阵划分成A块。然后再把剩下来的每一块独立地切竖着B-1刀。每块的价值为块上的数字和。求一种方案,使得最小价值块的价值最大。

【输入格式】

    第一行四个整数N,M,A,B。

    接下来N行,每行M个非负整数。代表这个矩阵

【输出格式】

    一个数字。最小价值块的价值。

【样例输入】

5 4 4 2

1 2 21

3 1 1 1

2 0 1 3

1 1 1 1

1 1 11

【样例输出】

    3

 

样例解释见图片

【数据规模】

   1<=A<=N<=500

   1<=B<=M<=500

    其他数字小于4000。

 

 二分的同志请注意了

m=(l+r)/2 <-----这句是永远也枚不到L与R的

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (500+10)
#define MAXM (500+10)
#define MAXT (2000000+10)
int n,m,t1,t2,a[MAXN][MAXM],sum[MAXN][MAXM]={0};
bool is_ok(int l,int r,int _m)
{
	int tot=0,p=0;
	for (int i=1;i<=m;i++)
	{
		tot+=sum[r][i]-sum[l-1][i];
		if (tot>=_m) {tot=0;p++;}
	}
	if (p>=t2) return 1;
	else return 0;
}
bool is_ok_(int _m)
{
	int p=0,l=1;
	for (int i=1;i<=n;i++)
	{
		if (is_ok(l,i,_m)) {l=i+1;p++;}
	}
	if (p>=t1) return 1;
	else return 0;
}
int main()
{
	freopen("browine.in","r",stdin);
	freopen("browine.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&t1,&t2);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			sum[i][j]=sum[i-1][j]+a[i][j];
		}
	/*
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			printf("%d ",sum[i][j]);
		}
	*/
//	cout<<(is_ok_(4));
	int l=1,r=1,ans=0;
	for (int j=1;j<=m;j++) r+=sum[n][j];

	for (int i=1;i<=60;i++)
	{
		int m_=(l+r)/2;
		if (is_ok_(m_)) {l=ans=m_;}
		else r=m_;
	}
	printf("%dn",ans);

//	while (1);
	return 0;
}

 

CF 237C (质数区间)

给定区间[a,b] 求l的最小值使[a,b]中任意长度为l的一段包含至少k个Prime

二分l

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (1000000+10)
int a[MAXN],tot=0,x,y,k;
bool b[MAXN]={0};
void work()
{
	b[1]=1;
	for (int i=2;i<=y;i++)
	{
		if (!b[i])
		{
			tot++;
			a[tot]=i;
		}
		for (int j=1;j<=tot;j++)
		{
			if (a[j]*i>y) break;
			b[a[j]*i]=1;
			if (!i%a[j]) break;
		}
	}
}
bool is_ok(int l)
{
	int tot=0;
	for (int i=x;i<=x+l-1;i++)
		if (!b[i]) tot++;
	if (tot<k) return false;
	for (int j=x+l;j<=y;j++)
	{
		tot=tot+(!b[j])-(!b[j-l]);
		if (tot<k) return false;
	}
	return true;
}

int main()
{
	scanf("%d%d%d",&x,&y,&k);
	work();
	int l=k,r=y-x+1;
	if (l>r||!is_ok(r))
	{
		printf("-1n");
		return 0;
	}
	for (int i=1;i<=60;i++)
	{
		if (l==r) break;
		int m=(l+r)>>1;
//		if (r-l==1) m++;
		if (is_ok(m)) r=m;
		else l=m+1;
	}
	printf("%dn",l);
//	while (1);
	return 0;
}

POJ 2456(二分哲学)

这题普通的二分会T…………

法一:只循环60遍,用ans记录答案(见标程)

法二:进行特判,若l+1==r 则 m=(l+r+1) shl 1 否则 m=(l+r) shl 1

Program P2456;
const
   maxd=1000000000;
   maxn=100000;
var
   n,c,i,j,k:longint;
   a:array[1..maxn] of longint;
procedure sort(l,r:longint);
var
   m,i,k,head,tot,ans:longint;
begin
   for k:=1 to 60 do
   begin
      m:=(l+r) shr 1;
      head:=1;tot:=0;
      for i:=2 to n do
      begin
         if a[i]-a[head]>=m then
         begin
            inc(tot);
            head:=i;
         end;
      end;
      if tot>=c-1 then begin ans:=m; l:=m+1 end else r:=m-1;
   end;
   writeln(ans);

end;
procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;
   j:=r;
   m:=a[(l+r) shr 1];
   repeat
      while a[i]<m do inc(i);
      while a[j]>m do dec(j);
      if i<=j then
      begin
         p:=a[i];a[i]:=a[j];a[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,c);
   for i:=1 to n do read(a[i]);
   qsort(1,n);
   sort(1,maxd);

end.

POJ 3575(计算几何与二分-无尽的小数处理)

这题 写了将近半个月……总是在D各种Bug

总的说来-这题最难应该是在精度处理上

1

1

0 0 1

这组数据过了就说明精度处理差不多了……

Program kingdom;
const
   maxn=100;
   maxm=100;
   le=0.000000001;
type
   circle=record
            x,y,r:double;
          end;
var
   s:array[1..maxn,1..1000] of circle;
   n,i,j,k:longint;
   m:array[1..maxn] of longint;
   ans:array[1..maxn,1..4] of double;
   wanted:array[1..maxn] of double;
   b:array[1..maxn] of boolean;
   l,r:double;
function arccos(cosa:double):double;
var
   sina,tana:double;
begin
   if cosa=0 then exit(pi/2);

   sina:=sqrt(1-sqr(cosa));
   tana:=sina/cosa;
   exit(arctan(tana));

end;
function min(a,b:double):double;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:double):double;
begin
   if a>b then exit(a) else exit(b);
end;

function sector(a,r:double):double;
begin
   exit(a*r*r/2);
end;
function triangle(a,r:double):double;
begin
   exit(sin(a)*r*r/2);
end;
function inlside(s:circle;l:double):boolean;
begin
   if (s.x-s.r>l) or (abs(s.x-s.r-l)<le) then exit(true) else exit(false);
end;
function inrside(s:circle;r:double):boolean;
begin
   if (s.x+s.r<r) or (abs(s.x+s.r-r)<le) then exit(true) else exit(false);
end;


function intarea(s:circle;l,r:double):double;
var
   i,j:longint;
   a,a2,s1,s2,s3,s4:double;
   bl,br:boolean;
begin
   if (r<s.x-s.r) or (s.x+s.r<l) then exit(0);
   if (s.x<=l) then
   begin
      a:=arccos((l-s.x)/s.r)*2;
      if (abs(s.x-l)<le) then s1:=0
      else s1:=triangle(a,s.r);
      s2:=sector(a,s.r);


      if s.x+s.r>r then
      begin
         a:=arccos((r-s.x)/s.r)*2;
         s3:=sector(a,s.r);
         s4:=triangle(a,s.r);
         s2:=s2-(s3-s4);

      end;
      exit(s2-s1);
   end
   else
   if (s.x>=r) then
   begin
      a:=arccos((s.x-r)/s.r)*2;
      if (abs(s.x-r)<le) then s1:=0
      else s1:=triangle(a,s.r);
      s2:=sector(a,s.r);

      if s.x-s.r<l then
      begin
         a:=arccos((s.x-l)/s.r)*2;
         s3:=sector(a,s.r);
         s4:=triangle(a,s.r);
         s2:=s2-(s3-s4);


      end;
      exit(s2-s1);

   end
   else
   begin
      bl:=inlside(s,l);
      br:=inrside(s,r);
      if bl and br then exit(pi*s.r*s.r);
      if bl and not(br) then
      begin
         a:=arccos((r-s.x)/s.r)*2;
         s3:=sector(a,s.r)-triangle(a,s.r);
         exit(pi*s.r*s.r-s3);
      end;
      if not(bl) and br then
      begin
         a:=arccos((s.x-l)/s.r)*2;
         s3:=sector(a,s.r)-triangle(a,s.r);
         exit(pi*s.r*s.r-s3);
      end;



      a:=arccos((s.x-l)/s.r)*2;

      a2:=arccos((r-s.x)/s.r)*2;
      s1:=sector(2*pi-a-a2,s.r);
      s2:=triangle(a,s.r)+triangle(a2,s.r);
      exit(s1+s2);



   end;



end;
function place(k:longint;l,r:double):boolean;
var
   tot:double;
   i,j:longint;
begin
   tot:=0;
   for j:=1 to m[k] do
   begin
         tot:=tot+intarea(s[k,j],l,r);
   end;
//   writeln(tot*n,' ',wanted[k]*pi);

   if (abs(tot*n-wanted[k]*pi)<le) then exit(true);
   if (tot*n<(wanted[k]*pi)) then exit(false) else exit(true);
end;
function bsearch(r1,r2:double):double;
var
   m:double;
   i,j,k,num:longint;
   flag:boolean;
begin
   for k:=1 to 60 do
   begin
      flag:=false;
      m:=(r1+r2)/2;
      for i:=1 to n do
         if not b[i] then
         begin
            flag:=flag or place(i,l,m);
            if flag then
            begin
               num:=i;
               break;
            end;
         end;
      if flag then r2:=m else r1:=m;
   end;

   b[num]:=true;
   ans[num,1]:=l;
   ans[num,2]:=r1;

   exit(r1);


end;
begin
  { assign(input,'kingdom.in');
   reset(input);
  } r:=-10000;
   l:=10000;
   read(n);
   fillchar(b,sizeof(b),false);
   fillchar(wanted,sizeof(wanted),0);
   for i:=1 to n do
   begin
      read(m[i]);
      for j:=1 to m[i] do
      begin
         read(s[i,j].x,s[i,j].y,s[i,j].r);
 //        writeln(s[i,j].x,s[i,j].y,s[i,j].r);

         r:=max(r,s[i,j].x+s[i,j].r);
         l:=min(l,s[i,j].x-s[i,j].r);
         wanted[i]:=wanted[i]+sqr(s[i,j].r);

      end;
   end;
   r:=r+1;

   for i:=1 to n do
      l:=bsearch(l,r);

   for i:=1 to n do
   begin
      writeln('4');
      writeln(ans[i,1]:7:7,' 3000');
      writeln(ans[i,1]:7:7,' -3000');
      writeln(ans[i,2]:7:7,' -3000');
      writeln(ans[i,2]:7:7,' 3000');
   end;




//   close(input);
end.