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.

fzu_noip 1032 (无穷数-进位判定)

无穷数

时限:1s内存:32M

★问题描述:

我们生成两个无穷大的数,第一个数是把所有的自然数链接起来组成的数字;第二个数是把所有自然数的平方连接起来组成的数。对这两个数求和,如下:

 123456789101112131415161718192021...

+ 149162536496481100121144169196225...

= 272619325597593231536305887388246...

现在给你一个整数k,问和从左往右数第k位的数码是多少?

★数据输入:

输入数据有多组,每组数据输入一行,有一个数k。对于100%的数据,k<=2147483647

★结果输出:

对于每组数据,输出一个整数N,从左往右数第k位的数码。

输入示例

输出示例

5

6

7

8

1

9

3

2

 
先算出第k位的Ai和Bi,然后相加,考虑是否加过头。
接下来用search_fi(k:longint) 判断第k位是否会令前一位进位,则


const
   a:array[1..19,1..2] of int64=((1,3),(4,9),(10,31),(32,99),(100,316),(317,999),(1000,3162),(3163,9999),(10000,31622),(31623,99999),(100000,316227),(316228,999999),(1000000,3162277),(3162278,9999999),(10000000,31622776),(31622777,99999999),
   (100000000,316227766),(316227767,999999999),(1000000000,2147483647));
var
   k:longint;
function search_ai(k:longint):longint;
var
   i,j,d,k2,g:int64;
begin
   d:=1;i:=9;
   while (true) do
   begin
      if (k-d*i>0) then
      begin
         dec(k,d*i);
         i:=i*10;inc(d);
      end
      else break;
   end;
   k2:=i div 9+(k-1) div d;
   g:=(k-1) mod d+1;
   g:=d-g+1;
   while (g>1) do begin k2:=k2 div 10;dec(g); end;
   exit(k2 mod 10);
end;
{
function search_bi(k:longint):longint;
var
   i,j:int64;
   head:longint;
begin
   head:=1;j:=10; i:=1;
   while (i<=2147483647 ) do
   begin
      if ((i*i) div j>0) then
      begin
         write('(',head,',',i-1,')',',');
         head:=i; j:=j*10;
      end;
      inc(i);
   end;
end;      }


function search_bi(k:longint):longint;
var
   i:longint;
   g,k2:int64;
begin
   i:=1;
   while (k>i*(a[i,2]-a[i,1]+1)) do
   begin
      dec(k,i*(a[i,2]-a[i,1]+1));
      inc(i);
   end;

   k2:=(k-1) div i+1;
   k2:=a[i,1]-1+k2;
   k2:=k2*k2;
   g:=(k-1) mod i+1;
   g:=i-g+1;

   while (g>1) do begin k2:=k2 div 10;dec(g); end;
   exit(k2 mod 10);
end;
function search_fi(k:longint):longint;
var
   i:longint;
begin
   i:=search_ai(k)+search_bi(k);
   if (i<=8) then exit(0)
   else if (i>9) then exit(1)
   else exit(search_fi(k+1));

end;
begin
//   assign(output,'dabiao.out');
//   rewrite(output);

   while not eof do
   begin
      readln(k);
      writeln((search_bi(k)+search_ai(k)+search_fi(k+1)) mod 10);


   end;

//   search_bi(1);
//close(output);
end.

行车(a1*b1+a1*b2+..a1*bn+a2*b1+…an*bn=(a1+..an)(b1+..bn) )

行车
(bicycle.pas/cpp)
题目描述
骑在自行车上,让微风追逐着他衣角,在不经意间捕获着一颗颗芳心,骄阳似乎也没有此时的他耀眼,这便是机房的骄傲——建德!
这是每天都会发生在附中门口的一幕。而为了每天能够领略不同的风景,捕获更多的芳心,建德打算制定n 条线路。为了简化起见,我们把这个世界想象成一个平面直角坐标系,而建德所在的福建师大附中则为原点。由于建德不能绕的太进,他每次路线的目的地都被限制在一个对应的右上角为(x, y),左下角为(-x,-y)的矩形内。
每次建德都会从原点直接沿直线走到目的地。显然,他走过了一个向量,这被数学控的“毛毡”称为这次的路线向量。他为了更好地规划线路,为每条线路定义了一个无聊值,即这次的路线向量和其余所有乊前的线路的向量的点积和【对于向量(x1,y1),(x2,y2),他们的点积和即为x1*x2+y1*y2】。建德希望合理的选择目的地,使得所有线路的无聊值乊和最小。
输入格式
第一行一个正整数n ,表示建德打算制定n 条旅行线路。
接下来 n 行,每行两个整数x , y ,描述一个限制目的地的矩形。
输出格式
一行一个整数,即最小的无聊值,保留 2 位小数。
样例输入
2
1 2
2 1
样例输出
-4.00
数据范围与约定
对于10% 的数据,保证0<n<=5,0<x,y<=5。
对于 30% 的数据,保证0<n<=20,0<x,y<=100。

对于 100% 的数据,保证0<n<=200,0<x,y<=200。

首先 根据公式  n个数和m个数两两相乘的结果为n个数的和与m个数的和的积

而且x和y互不影响

于是套公式-两两相乘/2-交集   结果为 f(n)=  (x1+..+xn)^2+x1^2+..xn^2  )/2

易证  f(n)=(x1+...+xn-1)* xn   + f(n-1)

所以  xn 要么最大,要么最小 才能使 f(n)有最大/最小值

因为不知道 (x1+..x(n-1)的正负 所以只能靠猜( 既考虑最大,也考虑最小)

回到原公式 显然  要是 f(n)有最小值 就要另 (x1+..+xn)有最小值

于是就是分组背包各种做……

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (200+10)
#define MAXV ((40000+100)*2)
#define MAXX (200+10)
#define f(i,j)  f[ (i) ][ (j)+20000   ]
int n;
long long ans=0;
bool f[MAXN][MAXV];
int x[MAXN];
int y[MAXN];
int sqr(int x)
{
	return x*x;
}
int main()
{
	freopen("bicycle.in","r",stdin);
	freopen("bicycle.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
		ans-=(long long)(sqr(x[i]))+sqr(y[i]);
	}
	memset(f,0,sizeof(f));
	f(0,0)=1;

	for (int i=1;i<=n;i++)
		for (int j=-i*200;j<=i*200;j++)
			f(i,j)=f(i-1,j-x[i])||f(i-1,j+x[i]);

	int j=0;

	while (!f(n,j)&&!f(n,-j)) j++;
	ans+=(long long)j*j;

//	cout<<j<<endl;

/*	int j=0;
	for (int i=0;i<=n;i++)
	{
		for (int j=-10;j<=10;j++)
			cout<<f(i,j);
		cout<<endl;
	}
*/
	memset(f,0,sizeof(f));
	f(0,0)=1;

	for (int i=1;i<=n;i++)
		for (int j=-i*200;j<=i*200;j++)
			f(i,j)=f(i-1,j-y[i])||f(i-1,j+y[i]);

	j=0;
	while (!f(n,j)&&!f(n,-j)) j++;

	ans+=(long long)j*j;

	cout.setf(ios::fixed);
	cout.precision(2);
	cout<<double(ans)/2<<endl;


//	while (1);



	return 0;
}

拯救LongMM (递推公式求解)

拯救L o n g M M ( l a n . p a s / c / c p p )
【题目描述】
LongDD 将军为了平息延续数年战乱,决定释放战俘营中所有的俘虏。然而,
LongDD 将军不打算释放敌军的统帅LongMM——因为这个家伙异常聪明,是个难缠的
对手。所以LongDD 将军决定把LongMM 用链子固定到墙上。链子由n 个环组成,每
个环有可能在墙上,也可能不在墙上。
“LongDD 将军,你为什么把我绑在墙上,不让我获得自由”,LongMM 咆哮道。
“但是,LongMM,你并没有被绑在墙上。我很确定你可以自己把链子解开”,
LongDD 将军回答道,“但是请你在天黑之前解开,否则我会因为你制造噪音把你重
新抓起来。”
请帮助LongMM 吧!链子由n 个环组成,编号为1,2,…,n。我们可以把每个环从
墙上取下来或者从新放回墙上,但是需要遵循如下规则:
- 每一步只能取下或者装上一个环
- 编号为1 的环可以随意取下或装上
- 如果编号为1,…,k-1 的环都取下了,并且编号为k 的环在墙上,我们可
以随意取下或者装上第k+1 个环
- 当所有环都取下来之后,LongMM 可以逃脱了
给定每个环的初始状态,请你编写程序计算LongMM 最少需要多少步才能逃脱。
程序名: lan
【输入格式】
* 第 1 行: 有一个整数n,(1<=n<=1000),表示环的个数
* 第 2 行: 有n 个整数,第i 个整数O_i=0,表示第i 个环在初始的时候为摘下的
状态;如果O_i=1,表示第i 个环初始的时候为装在墙上的状态。
【输入样例】
4
1 0 1 0
【输出格式】
* 第 1 行: 只有一个整数,表示最少需要多少步才能让LongMM 逃脱。
【输出样例】
6
【输出解释】

先递推 

然后 找规律 发现从后往前 ans=2^jn-2^j(n-1)+2^j(n-2)+.....   (j[i]表示从左往右第i个1)

Program lan;
type
   arr=record
         len:longint;
         d:array[1..1000] of longint;
       end;
const
    F=1000000;
var
   n,i:longint;
   ans:arr;
   p2:array[1..1000] of arr;
   a:array[1..1001] of longint;
procedure multipy;
var
   i,j,k:longint;
begin
   for k:=2 to 1000 do
   begin
      p2[k].len:=p2[k-1].len;
      for i:=1 to p2[k-1].len do
      begin
         inc(p2[k].d[i],p2[k-1].d[i]*2);
         inc(p2[k].d[i+1],p2[k].d[i] div F);
         p2[k].d[i]:=p2[k].d[i] mod F;
      end;
      if p2[k].d[p2[k].len+1]<>0 then inc(p2[k].len);



   end;
   for k:=1 to 1000 do dec(p2[k].d[1]);




end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
Procedure add(a,b:arr;var c:arr);
var
   i,j:longint;
begin
   fillchar(c,sizeof(c),0);
   c.len:=max(a.len,b.len);
   for i:=1 to c.len do
   begin
      inc(c.d[i],a.d[i]+b.d[i]);
      inc(c.d[i+1],c.d[i] div F);
      c.d[i]:=c.d[i] mod F;
   end;
   if c.d[c.len+1]>0 then inc(c.len);




end;
procedure sub(a,b:arr;var c:arr);
var
   i,j:longint;
begin
   fillchar(c,sizeof(c),0);
   c.len:=max(a.len,b.len);
   for i:=1 to c.len do
   begin
      inc(c.d[i],a.d[i]-b.d[i]);
      if c.d[i]<0 then
      begin
         inc(c.d[i],F);
         dec(c.d[i+1],1);
      end;
   end;
   while (c.len>1) and (c.d[c.len]=0) do dec(c.len);


end;
Procedure work;
var
   i,j:longint;
   flag:boolean;
begin
   i:=n;
   flag:=true;
   while true do
   begin
      while (a[i]=0) and (i>1) do dec(i);
      if a[i]=0 then exit;
      if flag then add(ans,p2[i],ans)
      else sub(ans,p2[i],ans);

      dec(i);
      if i=0 then exit;
      flag:=not(flag);
   end;



end;
Procedure pri;
var
   i:longint;
begin
   write(ans.d[ans.len]);
   for i:=ans.len-1 downto 1 do
   begin
      if ans.d[i]<100000 then write('0');
      if ans.d[i]<10000 then write('0');
      if ans.d[i]<1000 then write('0');
      if ans.d[i]<100 then write('0');
      if ans.d[i]<10 then write('0');
      write(ans.d[i]);
   end;
   writeln;
end;

begin
   assign(input,'lan.in');
   assign(output,'lan.out');
   reset(input);
   rewrite(output);
   read(n);
   for i:=1 to n do read(a[i]);
   fillchar(ans,sizeof(ans),0);
   fillchar(p2,sizeof(p2),0);
   p2[1].len:=1;
   p2[1].d[1]:=2;
   multipy;
   work;
   pri;
   close(input);
   close(output);


end.

 

POJ 1952(最长不下降子序列的个数)

求一个序列的最长不下降子序列的长度,与个数(相同数列算1个)

关键是如何判重。

显然如果之前有一个尾数相同且长度相同的序列,哪么后一个包含前一个所有可能的序列相同的序列,故将前一个序列删除(重复)

Program P1952;
var
   n,i,j,ans:longint;
   a,len,f,path:array[1..5000] of longint;
begin
   read(n);
   for i:=1 to n do read(a[i]);
   for i:=1 to n do
   begin
      len[i]:=1;
      f[i]:=1;
      path[i]:=i;
      for j:=i-1 downto 1 do
         if (a[j]>a[i]) and (len[j]+1>len[i]) then
         begin
            len[i]:=len[j]+1;
            f[i]:=f[j];
         end
         else if (a[j]>a[i]) and (len[j]+1=len[i]) then inc(f[i],f[j]);


      for j:=1 to i-1 do
         if (a[i]=a[j]) and (len[i]=len[j]) then f[j]:=0;



   end;
   j:=0;
   for i:=1 to n do if len[i]>j then j:=len[i];
   ans:=0;
   for i:=1 to n do if len[i]=j then inc(ans,f[i]);

   writeln(j,' ',ans);


end.

POJ 1061(exgcd)

这题是exgcd……

我居然连wa了2天……

至少知道DIV函数的性质了   (-x) div t =-(x div t)    

                           (-x) div (-t) = (x div t)

发现自己数论蒟蒻……

Program p1061;
var
   x,y,n,m,l,t:int64;
   a,b,c,c2:int64;
function exgcd(a,b:int64):int64;
var
   x1,y1:longint;
begin
   if b=0 then
   begin
      x:=1;
      y:=0;
      exit(a);
   end;
   exgcd:=exgcd(b,a mod b);
   x1:=y;
   y1:=x-(a div b)*y;
   x:=x1;
   y:=y1;
end;
begin

   read(x,y,m,n,l);
   a:=n-m;
   c:=x-y;
   b:=l;
   c2:=exgcd(a,b);
   if (c mod c2<>0) then writeln('Impossible')
   else
   begin
      x:=x*(c div c2);
      y:=y*(c div c2);
      t:=b div c2;


      if t<0 then
         while (x<0) do
         begin

            x:=x-t*abs(x div t)-t;
         end;
      if t>0 then while (x<0) do x:=x+t*abs(x div t)+t;

      x:=x mod (b div c2);
      writeln(x);
   end;


end.

POJ 1832(9连环)

格雷码做

0要特判

答案 就是读入的两个数充格雷码转为2进制的差的绝对值的十进制

Program P1832;
Type
   arr=record
       a:array[1..500] of longint;
       len:longint;
       end;
var
   n,m,i:longint;
   a,b,c,d:arr;
   node2:array[1..1000] of arr;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
function compare:boolean;
var
   i,j:longint;
begin
   while (a.len>1) and (a.a[a.len]=0) do dec(a.len);
   while (b.len>1) and (b.a[b.len]=0) do dec(b.len);
   if a.len<b.len then exit(true)
   else if a.len>b.len then exit(false);

   i:=a.len;
   while (i>1) and (a.a[i]=b.a[i]) do
   begin
      dec(i);
   end;
   if (a.a[i]<=b.a[i]) then exit(true) else exit(false);
end;
Procedure Subtract(a,b:arr;var c:arr);
var
   i,j:longint;
   pa:arr;
begin
   if (compare) then
   begin
      pa:=a;
      a:=b;
      b:=pa;
   end;
   fillchar(c,sizeof(c),0);
   for i:=1 to a.len do
   begin
      inc(c.a[i],a.a[i]-b.a[i]);
      if c.a[i]<0 then
      begin
         inc(c.a[i],2);
         dec(c.a[i+1]);
      end;
   end;
   c.len:=a.len;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);
end;
procedure add(a,b:arr;var c:arr);
var
   i,j:longint;
begin
   fillchar(c,sizeof(c),0);
   for i:=1 to max(a.len,b.len) do
   begin
      inc(c.a[i],a.a[i]+b.a[i]);
      inc(c.a[i+1],c.a[i] div 10);
      c.a[i]:=c.a[i] mod 10;
   end;
   c.len:=max(a.len,b.len)+1;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);
end;
begin
   fillchar(node2,sizeof(node2),0);
   node2[1].len:=1;
   node2[1].a[1]:=1;

   for i:=2 to 500 do
   begin
      add(node2[i-1],node2[i-1],node2[i]);
   end;

 {  assign(input,'P1832.in');
   assign(output,'P1832.out');
   reset(input);
   rewrite(output);
  }
   read(m);
   while m>0 do
   begin
      fillchar(a,sizeof(a),0);
      fillchar(b,sizeof(b),0);
      read(n);

      if n=0 then
      begin
         writeln('0');
         dec(m);
         continue;
      end;
      for i:=n downto 1 do read(a.a[i]);
      for i:=n downto 1 do read(b.a[i]);
      for i:=n-1 downto 1 do
      begin
         a.a[i]:=(a.a[i] xor a.a[i+1]);
      end;

      for i:=n-1 downto 1 do
         b.a[i]:=b.a[i] xor b.a[i+1];
      a.len:=n;
      b.len:=n;

      subtract(a,b,c);
//      for i:=n downto 1 do write(c.a[i]);
//      writeln;
      fillchar(d,sizeof(d),0);
      d.len:=1;
      for i:=n downto 1 do
         if c.a[i]>0 then add(node2[i],d,d);

      for i:=d.len downto 1 do write(d.a[i]);


      writeln;
      dec(m);
   end;
{   close(input);
   close(output);
}
end.

POJ 3006(线性筛素数)

线性筛素数……

Program P3006;
const
   maxn=1000000;
var
   prime:array[1..maxn] of boolean;
   p:array[1..maxn] of longint;
   t:longint;
   a,d,n:longint;
Procedure primeing;
var
   i,j:longint;
begin
   fillchar(prime,sizeof(prime),false);
   t:=0;
   prime[1]:=true;
   for i:=2 to maxn do
   begin
      if not(prime[i]) then
      begin
         inc(t);
         p[t]:=i;
      end;
      for j:=1 to t do
      begin
         if p[j]*i>maxn then break;
         prime[p[j]*i]:=true;
         if i mod p[j]=0 then break;
      end;
   end;
end;
begin
   primeing;
   readln(a,d,n);
   while (a+d+n>0) do
   begin
      while (n>0) do
      begin
         if not(prime[a]) then dec(n);
         inc(a,d);
      end;
      writeln(a-d);
      readln(a,d,n);
   end;
end.

POJ 1006(中国剩余定理)

中国剩余定理

若一个数除m1余p1,除m2余p2……,除mn余pn (m1,m2……,mn互质)

则求 k1使k1=m2*……*mn的倍数且除m1余1

……

则这个数为(k1*p1+k2*p2+……kn*pn) mod (m1*m2*……*mn)

Program P1005;
var
   a,b,c,d,i,a1,a2,a3,ans:longint;
begin
   i:=1;
   a1:=28*33;
   a2:=23*33;
   a3:=23*28;
   while (a1 mod 23<>1) do inc(a1,28*33);
   while (a2 mod 28<>1) do inc(a2,23*33);
   while (a3 mod 33<>1) do inc(a3,23*28);

   while (true) do
   begin
      read(a,b,c,d);
      if (a=-1) and (b=-1) and (c=-1) and (d=-1) then break;
      ans:=(a1*a+a2*b+a3*c+21252-d) mod 21252;
      if ans=0 then ans:=21252;
      writeln('Case ',i,': the next triple peak occurs in ',ans,' days.');
      inc(i);
   end;
end.

POJ 2140(数学问题)

问n=a+a+1+a+2+...+a+k 的情况总数

n=(k+1)*a+(k+1)*k/2

 =(k+1)(a+k/2)

n为整数,k+1为整数,(a+k/2)为整数,k为偶数,k+1为奇数

当n和k+1确定时,a为定值

故解为n的奇因子个数

Program P2140;
var
   i,n,ans:longint;
begin
   ans:=0;
   read(n);
   i:=1;
   while (i<=n) do
   begin
      if (n mod i=0) then inc(ans);
      inc(i,2);
   end;
   writeln(ans);
end.