Author Archives: nike0good

POJ 3748(C++的16进制读法 %x）

Posted on by

P党写几小时的程序 C++才几行……

首先P的位运算有上限2^30 此时 即便是 int64也会因为补码坑死人的

到1 shl 31时   int64 是负数 故 这个时候 不能shr 为多出好多位

造成以上结果的真正原因是 shl 和 shr 只支持到1 shl 30 （Longint）所以在int64或qword会出错 要自己写


C党读入方法 %x 表示 二进制

#include<cstdio>
using namespace std;
int r,x,y;
int main()
{
	scanf("%x,%d,%d",&r,&x,&y);
	r=r&(~(1<<x));
	r=r&(~(1<<y-2));
	r=r|(1<<(y-1))|(1<<(y));
	printf("%xn",r);


}

P党取到30的做法：

Program P3748;
const
// ordA=65;
   orda=97;
   ord0=48;
var
   s:string;
   r:qword;
   x,y:longint;
function turn2(c:char):longint;
begin
   if ord(c)>=orda then begin exit(ord(c)-orda+10); end
   else exit(ord(c)-ord0);
end;
function turn16(x:qword):longint;
begin
   if (x<>0) then
   begin
      turn16:=x and 15;
      x:=x shr 4;
      turn16(x);
      if turn16<=10 then write(turn16) else write(chr(turn16-10+orda));
   end;
end;
function cin:longint;
var
   i:longint;
   s1:string;
begin
   i:=1;
   while s[i]<>',' do inc(i);
   s1:=copy(s,1,i-1);
   val(s1,cin);
   delete(s,1,i);


end;

function cin16:qword;
var
   i,j:longint;
   s1:string;
begin
   i:=1;
   while s[i]<>',' do inc(i);
   s1:=copy(s,1,i-1);
   cin16:=0;
   for j:=1 to i-1 do
      cin16:=cin16 shl 4+turn2(s1[j]);
   delete(s,1,i);
end;


begin
   readln(s);
   r:=cin16;x:=cin;val(s,y);


   r:=r and (not (1 shl x));

   r:=r and (not (1 shl (y-2)));
   r:=r or (1 shl (y-1));
   r:=r or (1 shl y);
   turn16(r);
   writeln;

end.

更正AC版：

Program P3748;
const
// ordA=65;
   orda=97;
   ord0=48;
var
   s:string;
   r,k:qword;
   x,y,i:longint;
function turn2(c:char):longint;
begin
   if ord(c)>=orda then begin exit(ord(c)-orda+10); end
   else exit(ord(c)-ord0);
end;
function turn16(x:qword):longint;
begin
   if (x<>0) then
   begin
      turn16:=x and 15;
      x:=x div 16;
      turn16(x);
      if turn16<=10 then write(turn16) else write(chr(turn16-10+orda));
   end;
end;
function cin:longint;
var
   i:longint;
   s1:string;
begin
   i:=1;
   while s[i]<>',' do inc(i);
   s1:=copy(s,1,i-1);
   val(s1,cin);
   delete(s,1,i);
end;
function cin16:qword;
var
   i,j:longint;
   s1:string;
begin
   i:=1;
   while s[i]<>',' do inc(i);
   s1:=copy(s,1,i-1);
   cin16:=0;
   for j:=1 to i-1 do
      cin16:=cin16 shl 4+turn2(s1[j]);
   delete(s,1,i);
end;

function shl2(x:longint):qword;
var
   i:longint;
begin
   shl2:=1;
   for i:=1 to x do shl2:=shl2*2;

end;
begin
   readln(s);
   r:=cin16;x:=cin;val(s,y);


  r:=r and (not (shl2(x)));


   r:=r and (not (shl2(y-2)));

   r:=r or (shl2(y-1));
   r:=r or (shl2(y));
   turn16(r);
   writeln;

end.

附：

    功能              |           示例            |    位运算
----------------------+---------------------------+--------------------
去掉最后一位          | (101101->10110)           | x shr 1
在最后加一个0         | (101101->1011010)         | x shl 1
在最后加一个1         | (101101->1011011)         | x shl 1+1
把最后一位变成1       | (101100->101101)          | x or 1
把最后一位变成0       | (101101->101100)          | x or 1-1
最后一位取反          | (101101->101100)          | x xor 1
把右数第k位变成1      | (101001->101101,k=3)      | x or (1 shl (k-1))
把右数第k位变成0      | (101101->101001,k=3)      | x and not (1 shl (k-1))
右数第k位取反         | (101001->101101,k=3)      | x xor (1 shl (k-1))
取末三位              | (1101101->101)            | x and 7
取末k位               | (1101101->1101,k=5)       | x and (1 shl k-1)
取右数第k位           | (1101101->1,k=4)          | x shr (k-1) and 1
把末k位变成1          | (101001->101111,k=4)      | x or (1 shl k-1)
末k位取反             | (101001->100110,k=4)      | x xor (1 shl k-1)
把右边连续的1变成0    | (100101111->100100000)    | x and (x+1)
把右起第一个0变成1    | (100101111->100111111)    | x or (x+1)
把右边连续的0变成1    | (11011000->11011111)      | x or (x-1)
取右边连续的1         | (100101111->1111)         | (x xor (x+1)) shr 1
去掉右起第一个1的左边 | (100101000->1000)         | x and (x xor (x-1))

POJ 3264(STRMQ)

Posted on by

for j:=1 to ln(n)/ln(2)

    for i:=1 to n-(1 shl j)+1 do

       f[i,j]:=min(f[i,j-1],f[i+(1 shl (j-1),j-1];


f[l,r]:=min(f[l,j],f[r-(1 shl j)+1,j]; j=ln(r-l+1)/ln(2);


ln(n)/ln(2)=log(2,n);

Program lineup;
const
   maxn=50000;
   maxq=200000;
   maxh=1000000;
var
   n,q,i,j,l,r,k:longint;
   a:array[1..maxh] of longint;
   f,h:array[1..maxh,0..16] of longint;//f mintall h hightall
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

begin
   read(n,q);
   for i:=1 to n do
   begin
      read(a[i]);
      f[i,0]:=a[i];
      h[i,0]:=a[i];
   end;
   for j:=1 to trunc(ln(n)/ln(2)) do   //f[i,j]:=min(f[i,j-1],f[i+2^(j-1),j-1] i<=n-2^j
      for i:=1 to n-(1 shl j)+1 do
      begin
         f[i,j]:=min(f[i,j-1],f[i+1 shl (j-1),j-1]);
         h[i,j]:=max(h[i,j-1],h[i+1 shl (j-1),j-1]);
      end;

   for i:=1 to q do
   begin
      read(l,r);
      j:=(r-l+1);
      j:=trunc(ln(j)/ln(2));
      writeln(max(h[l,j],h[r-1 shl j +1,j])-min(f[l,j],f[r-1 shl j +1,j]));
   end;
end.

RQNOJ 38(串的计数）

Posted on by

一个长度为3N字符串满足：由N个A，N个B，N个C组成，对于它的任意前缀，满足A的个数>=B的个数>=C的个数。求满足这样条件的字符串的个数。


看到这题第一反应：打表！第二反应三个字：高精度

这题动态转移方程为f[i,j,k]=f[i-1,j,k]+f[i,j-1,k]+f[i,j,k-1]  i,j,k表示A,B,C的个数，考察是否可行

高精啊高精……

Program str;
type
   arr=record
           len:longint;
           d:array[1..15] of longint;
       end;
var
   n,i,j,k:longint;
   f:array[0..60,0..60,0..60] of arr;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
procedure sum(a,b:arr;var c:arr);
var
   i,j:longint;
const
   F=100000000;

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

   while (c.len>0) and (c.d[c.len]=0) do dec(c.len);


end;
Procedure print(a:arr);
var
   i,p:longint;
begin
   write(a.d[a.len]);
   for i:=a.len-1 downto 1 do
   begin
      p:=a.d[i];
      if p<10000000 then write('0');
      if p<1000000 then write('0');
      if p<100000 then write('0');
      if p<10000 then write('0');
      if p<1000 then write('0');
      if p<100 then write('0');
      if p<10 then write('0');
      write(p);
   end;
   writeln;
end;
begin
   read(n);
   fillchar(f,sizeof(f),0);
   f[0,0,0].len:=1;
   f[0,0,0].d[1]:=1;
   for i:=1 to n do
      for j:=0 to i do
         for k:=0 to j do
         begin
            if k>0 then
            begin
               sum(f[i,j,k],f[i,j,k-1],f[i,j,k]);
            end;
            if i>j then sum(f[i,j,k],f[i-1,j,k],f[i,j,k]);
            if j>k then sum(f[i,j,k],f[i,j-1,k],f[i,j,k]);
         end;

   print(f[n,n,n]);
end.

POJ 1611(并查集）

Posted on by

唯一的WA

是把0的父亲当成祖先

father[x]和getfather(x)差别巨大啊

Program p1611;
const
   maxn=30010;
   maxm=500;
var
   n,m,i,j,k,p1,p2,ans,f0:longint;
   father:array[0..maxn] of longint;
function getfather(x:longint):longint;
begin
   if father[x]=x then exit(x);
   father[x]:=getfather(father[x]);
   exit(father[x]);
end;
procedure union(x,y:longint);
begin
   if getfather(x)<>getfather(y) then
      father[father[x]]:=father[father[y]];
end;
begin
   read(n,m);
   while (n+m>0) do
   begin
      for i:=0 to n-1 do father[i]:=i;
      for i:=1 to m do
      begin
         read(k);
         if k>0 then read(p1);
         if k>1 then
            for j:=2 to k do
            begin
               read(p2);
               union(p1,p2);
            end;
      end;
      ans:=1;
      f0:=getfather(0);
      for i:=1 to n-1 do if getfather(i)=f0 then inc(ans);
      writeln(ans);
      read(n,m);
   end;
end.

POJ 2271(HTML)

Posted on by

这题字符串处理

注意Seekeof会自动把后面的空格吃掉（有时遇到回车，后面会漏一个空格……貌似有时没空格也会读到，字符串处理时慎用）

另外 空格的Ascii码是32，31及以下都是不可输入字符

program P2271;
var
   s:string;
procedure cin;
var
   c:char;
   i,len:longint;
begin
   s:='';
   c:=' ';
   i:=0;
   while not(seekeof) do
   begin
      read(c);
      while (ord(c)<=32) and not(eof) do read(c);
      if ord(c)<=32 then break;
      repeat
         s:=s+c;
         if eof then break;
         read(c);
      until (ord(c)<=32);

      len:=length(s);
      if s='<br>' then begin writeln; i:=0; end
      else
      if s='<hr>' then
      begin
         if i>0 then writeln;
         for i:=1 to 80 do write('-');
         writeln;
         i:=0;
      end
      else
      begin
         if (i=0) then
         begin
            if len<80 then
            begin
               write(s);
               i:=len;
            end;
         end
         else
         begin
            if (i+1+len<=80) then
            begin
               write(' ',s);
               i:=i+1+len;
            end
            else
            begin
               writeln;
               write(s);
               i:=len;

            end;
         end;



      end;



      s:='';
   end;






end;
begin
{   assign(input,'p2271.in');
   assign(output,'p2271.out');
   reset(input);
   rewrite(output);
 }  cin;
   writeln;
  { close(input);
   close(output);}
end.

POJ 1700(过河问题）

Posted on by

玩过《雷顿》就知道这题可以贪心

小等于2人：1,2->

3人时：

1,3->

1<-

1,2->

1<-

否则：

1，2->

2<-

max1,max2->

1<-

OR：

1,max1->

1<-

2,max2->

2<-

于是数据规模-2

Program P1700;
var
   t,n,i,j:longint;
   l,r:longint;
   a:array[1..1000] of longint;
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;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
function min(a,b:longint):longint;
begin
   if a>b then exit(b) else exit(a);
end;

function ww(x:longint):longint;
var
   i,j:longint;
begin
   if x=1 then exit(a[1]);
   if x=2 then exit(a[2]);
   if x=3 then exit(a[1]+a[2]+a[3]);
   i:=2*a[1]+a[x]+a[x-1];
   j:=2*a[2]+a[1]+a[x];
   exit(ww(x-2)+min(i,j));
                           //1,2-> 1< r1,r2-> 2<=
end;
begin
   read(t);
   while (t>0) do
   begin
      read(n);
      for i:=1 to n do read(a[i]);
      qsort(1,n);
      l:=1;r:=n;

      writeln(ww(n));

      dec(t);
   end;
end.

POJ 1125(Floyd）

Posted on by

裸Floyd

Program P1125;
const
   maxn=100;
   maxedge=10;
   NULL=-2139062144;
var
   n,i,j,k,m,v,t,ans:longint;
   f:array[1..maxn,1..maxn] of longint;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
begin
   read(n);
   while (n<>0) do
   begin
      fillchar(f,sizeof(f),128);
      for i:=1 to n do
      begin
         f[i,i]:=0;
         read(m);
         for j:=1 to m do
         begin
            read(v,t);
            f[i,v]:=t;
         end;
      end;

      for k:=1 to n do
         for i:=1 to n do
            for j:=1 to n do
               if (f[i,k]<>NULL) and (f[k,j]<>NULL) then
                  if (f[i,k]+f[k,j]<f[i,j]) or (f[i,j]=NULL) then f[i,j]:=f[i,k]+f[k,j];
      ans:=maxlongint;

      v:=0;
      for i:=1 to n do
      begin
         t:=f[i,1];
         for j:=1 to n do
         begin
            if f[i,j]=NULL then break else t:=max(f[i,j],t);
         end;
         if f[i,j]=NULL then continue;
         if t<ans then begin v:=i; ans:=t; end;

      end;
      if (ans=maxlongint) then writeln('disjoint') else writeln(v,' ',ans);



      read(n);
   end;
end.

POJ 3842(质数判断）

Posted on by

7！=5040

所以这题直接求质数比打一千万的表都快

这提高诉我们阶乘其实不算大&看（算）清数据规模


Program cc;
var
   n,t,len,i,j,ans:longint;
   s:string;
   b:array[0..9] of longint;
procedure dfs(p,l:longint);
var
   i:longint;
begin
   if l=len then
   begin
      if p=1 then exit;
      for i:=2 to trunc(sqrt(p)) do if (p mod i=0) then exit;
      inc(ans);
      exit;
   end;
   for i:=0 to 9 do
   if b[i]>0 then
   begin
      if (i=0) and (l=0) then continue;
      dec(b[i]);
      dfs(p*10+i,l+1);
      inc(b[i]);
   end;

end;
begin
   readln(t);
   while (t>0) do
   begin
      readln(s);
      len:=length(s);
      fillchar(b,sizeof(b),0);
      for i:=1 to len do inc(b[ord(s[i])-48]);
      ans:=0;
      for i:=1 to len do
      begin
         dfs(0,0);
         dec(len);
      end;
      writeln(ans);


      dec(t);
   end;
end.

CF 187A(从后取数的重排数列）

Posted on by

题目大意：一串数，每次把最后那个数挪到前面任意位置，就最少挪动次数

显然一个数最多挪一次（只能从后取的话，插2次的一定能变成1次）

因此找最后挪动的数即可，最后挪动的数即由于与下序列的连线与之前的交叉，其它数无论怎么挪都无法影响到它）

Program DD;
const
   maxn=200000;
var
   n,i,j,l,r:longint;
   a,b,hposa,hposb:array[1..maxn] of longint;
begin
   read(n);
   for i:=1 to n do
   begin
      read(a[i]);
      hposa[a[i]]:=i;
   end;
   for i:=1 to n do
   begin
      read(b[i]);
      hposb[b[i]]:=i;
   end;
   r:=0;
   for i:=1 to n do
   begin
       if r<hposb[a[i]] then r:=hposb[a[i]]
       else break;
   end;
   if (r=hposb[a[i]]) then writeln('0') else
   writeln(n-i+1);

end.

POJ 2588(解析几何+并查集）

Posted on by

题目就是早从左到右的路

注意输入的实数

这题图画好就行，别像我一开始把图弄反就成

从上开始找，若找到一个与下边界相邻的就无解，找到与左边相邻的记圆与左边界相交的下边的点（相当于左上角挖去一块），右边同理。

Program snake;
const
   maxn=1000;
var
   n,i,j:longint;
   x,y,r,lc,rc:array[1..maxn] of double;
   maxl,maxr:double;
   father:array[1..maxn] of longint;
   b,up,down,left,right:array[1..maxn] of boolean;
function getfather(x:longint):longint;
begin
   if father[x]=x then exit(x);
   father[x]:=getfather(father[x]);
   exit(father[x]);
end;
Procedure union(x,y:longint);
begin
   father[father[x]]:=father[father[y]];
end;
function distance(i,j:longint):double;
begin
   exit(sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])));
end;
function dis(x1,y1,x2,y2:double):double;
begin
   exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
end;

begin
   fillchar(b,sizeof(b),false);
   fillchar(up,sizeof(up),false);
   fillchar(down,sizeof(down),false);
   fillchar(left,sizeof(left),false);
   fillchar(right,sizeof(right),false);
   fillchar(lc,sizeof(lc),0);
   fillchar(rc,sizeof(rc),0);
   maxl:=1000;maxr:=1000;

   read(n);
   for i:=1 to n do
   begin
      read(x[i],y[i],r[i]);
      father[i]:=i;
      for j:=1 to i-1 do
         if distance(i,j)<r[i]+r[j] then
            if getfather(i)<>getfather(j) then
               union(i,j);
      if (y[i]<r[i]) then down[i]:=true;
      if (y[i]+r[i]>1000) then up[i]:=true;
      if (x[i]<r[i]) then
      begin
         left[i]:=true;
         lc[i]:=y[i]-sqrt(sqr(r[i])-sqr(x[i]));
      end;
      if (x[i]+r[i]>1000) then
      begin
         right[i]:=true;
         rc[i]:=y[i]-sqrt(sqr(r[i])-sqr(1000-x[i]));
      end;

   end;
   for i:=1 to n do
      if (up[i]) and not(b[i]) then
      begin
         for j:=1 to n do
            if father[i]=father[j] then
            begin
               b[j]:=true;
               if (down[j]) then
               begin
                  writeln('Bill will be bitten.');
                  halt;
               end;
               if left[j] then
               begin
                  if lc[j]<maxl then maxl:=lc[j];

               end;
               if right[j] then
               begin
                  if rc[j]<maxr then maxr:=rc[j];
               end;


            end;
      end;
   writeln('Bill enters at (0.00, ',maxl:2:2,') and leaves at (1000.00, ',maxr:2:2,').');




end.