Daily Archives: 15 11 月, 2012

POJ 2190(模拟策略）

Posted on by
Language:
ISBN
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 13962   Accepted: 4898

Description

ISBN码满足：(10*A1+9*A2+..+1*A10) mod 11=0
A10是效验码，若它为10，则以X代替，其它位都为0..9的数字
 现在给你一个效验码，但是其中一位看不清，请求出这一位。

Input

1行ISBN码，‘?'表示看不清

Output

输出那一位，无解输-1.

Sample Input

15688?111X

Sample Output

1

Source

USACO 2003 Fall Orange

这题就是模拟，模拟最重要的是细节，本题值得注意的细节：

1.某1位为0的情况.

2.其它位的乘积和是11的倍数.

3.某1位为X的情况.

4.无解.

5.其它位的乘积和包含'X'.

Program ISBN;
const
   n=10;
   F=11;
var
   s:string;
   i,p,ans:longint;
begin
   ans:=0;
   readln(s);
   if s[n]='X' then s[n]:=char(58);

   p:=pos('?',s);

   for i:=1 to n do
      if i<>p then inc(ans,(ord(s[i])-48)*(10-i+1));
   // ans +p*? mod 11 =0
   ans:=ans mod F;
   ans:=(F-ans) mod F;

   for i:=0 to n do
   begin
      if ((11-p)*i) mod F=ans then
      begin
         if (p=n) and (i=10) then begin writeln('X'); halt; end;
         if (i<10) then begin writeln(i);   halt; end;
      end;
   end;

   writeln('-1');

end.



POJ 1226(最长公共子串含逆序）

Posted on by
Language:
Substrings
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 9639   Accepted: 3319

Description

请找出一些串的最长‘正/逆‘子串，使它为所有的串的子串（即使是逆序也认为包含）.

Input

第一行为数据数t，(1 <= t <= 10),
对每组数据而言:第一行为字符串个数 n (1 <= n <= 100)，接下来n行为字符串（长度不超过100） .

Output

每行一个数，表示最长'正/逆‘子串的长度。

Sample Input

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

Sample Output

2
2

Source

Tehran 2002 Preliminary

还是KMP，先在第一个串中枚举串，之后考察它是否是其它串的'正/逆'子串。


Program P1226;
const
   maxn=100;
   maxt=10;
var
   tt,n,m,i,j,k,ans:longint;
   flag:boolean;
   a:array[1..maxn] of string;
   p:string;
   next:array[1..maxn] of longint;

function kmp(a,b:string):boolean;
var
   i,j,n,m:longint;
begin
   i:=1;j:=0;next[1]:=0;
   n:=length(a); m:=length(b);
   while (i<m) do
   begin
      if (j=0) or (b[i]=b[j]) then
      begin
         inc(i);inc(j);
         if (b[i]<>b[j]) then next[i]:=j else next[i]:=next[j];
      end else j:=next[j];
   end;

   i:=0;j:=0;
   while (i<=n) and (j<=m) do
   begin
      if (j=0) or (a[i]=b[j]) then
      begin
         inc(i);inc(j);
      end else j:=next[j];
   end;
   if (j>m) then exit(true);
   exit(false);
end;
function ob_s(a:string):string;
var
   i,j,n:longint;
begin

   ob_s:=''; n:=length(a);
   for i:=n downto 1 do ob_s:=ob_s+a[i];
end;
function compare(a,b:string):boolean;
var
   n,m:longint;
begin
   n:=length(a);m:=length(b);
   if (n<>m) then exit(n<m);
   for i:=1 to n do
      if a[i]<>b[i] then exit(a[i]<b[i]);
   exit(false);
end;


begin
   readln(tt);
   while (tt>0) do
   begin
      ans:=0;
      readln(n);
      for i:=1 to n do readln(a[i]);

      for i:=1 to length(a[1]) do
         for j:=i to length(a[1]) do
         begin
            p:=copy(a[1],i,j-i+1);
            flag:=true;
            for k:=2 to n do
            begin
               if not((kmp(a[k],p) or kmp(a[k],ob_s(p)))) then
               begin
                  flag:=false; break;
               end;
            end;
            if flag and (length(p)>ans) then ans:=length(p);


         end;

      writeln(ans);
      dec(tt);
   end;
end.


POJ 2185(最大平铺矩阵）

Posted on by
Language:
Milking Grid
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 4346   Accepted: 1780

Description

给定R(1 <= R <= 10,000) *C (1 <= C <= 75) 的矩阵，求它的最大平铺矩阵,不够的地方可部分平铺，但不可重叠。

Input

第一行：R和C.
第2-R+1行每行C个大写字母，表示矩阵.

Output

最大的平铺矩阵面积

Sample Input

2 5
ABABA
ABABA

Sample Output

2

Hint

The entire milking grid can be constructed from repetitions of the pattern 'AB'.

Source

USACO 2003 Fall

显然这个矩阵必然从左上角开始

由于C比较少，先找出每列最大的平铺线段（行行不影响）

再考虑每行共有且最小的重复部分（可以证明增加重复部分对行的大小无影响）

在考虑行R≤10000，必须用Kmp，不凡假设句末有若干'????'

则对于字符串的P

AEICCCAEICCCAEI C  C  ?   ?   ?  ...

000000123456789 10 11 12  13  14 ...

显然？后的P递增+1，又因答案为Max（i-p[i])（i≥n）

所以(n-p[n])=Max（i-p[i])


Program grid;
const
   maxn=10000;
   maxm=75;
var
   n,m,i,j,k:longint;
   a:array[1..maxn] of string;
   f:array[1..maxm] of longint;
   flag:boolean;
   p:array[1..maxn] of longint;
begin
   fillchar(f,sizeof(f),0);
   readln(n,m);
   for i:=1 to n do
   begin
      readln(a[i]);
      for j:=1 to m do
      begin
         flag:=true;
         for k:=j+1 to m do
            if a[i][k]<>a[i][k-j] then begin flag:=false; break; end;
            if flag then inc(f[j]);
      end;
   end;
   for i:=1 to m do if f[i]=n then break;
   m:=i;

   for i:=1 to n do delete(a[i],m+1,maxlongint);

   j:=0;p[1]:=0;
   for i:=2 to n do
   begin
      while (j>0) and (a[i]<>a[j+1]) do j:=p[j];
      if (a[i]=a[j+1]) then inc(j);
      p[i]:=j;
   end;

   n:=n-p[n];
   writeln(m*n);





end.







POJ 3461(模式匹配数&覆盖函数）

Posted on by
Language:
Oulipo
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 14051   Accepted: 5667

Description

给出两个字符串W和T，求T中有几个W子串。

Input

第一行为数据数.

每组数据有两行W和T，表示模式串和原始串.

Output

对每组数据，每行一个数，表示匹配数.

Sample Input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output

1
3
0

Source

BAPC 2006 Qualification


这题用到了KMP中的覆盖函数——P

P和Next的区别是P是指包括当前点的最长覆盖长度，Next是指匹配到i，若不满足条件，将其挪到Next[i]，(P[i]<>P[next[i]],P表模式串）

证明：



之后进行查找，若查到(j=m),则j=P[j]（为了下一次查找）


Program Poj3461;
const
   maxm=10000;
   maxn=1000000;
var
   tt,n,m,i,j:longint;
   a,b:ansistring;
   P:array[1..maxn] of longint;
function kmp:longint;
var
   n,m,i,j:longint;
begin
   kmp:=0;

   n:=length(a);m:=length(b);
   P[1]:=0;j:=0;
   for i:=2 to m do
   begin
      while (j>0) and (b[j+1]<>b[i]) do j:=p[j];
      if (b[j+1]=b[i]) then inc(j);
      p[i]:=j;
   end;

   j:=0;
   for i:=1 to n do
   begin
      while (j>0) and (b[j+1]<>a[i]) do j:=p[j];
      if (b[j+1]=a[i]) then inc(j);
      if j=m then
      begin
         inc(kmp);
         j:=p[j];
      end;

   end;


end;
begin
   readln(tt);
   while (tt>0) do
   begin
     readln(b);
     readln(a);

     writeln(kmp);

     dec(tt);
   end;

end.