CF 254C(易位构字法）

Posted on 9 12 月, 2012 by nike0good

异位构字就是把一个字符串的顺序改变，可以得到另一个字符串.

对字符串 s 和 t ,至少修改 s 多少位，能使 s 和 t 易位构字？如果有很多方法，输出 s 易位后字典序最小的。

Input

两行 s, t. 长度不超过 10⁵ ，只有大写字母。

Output

第一行输出最小修改次数，第二行输出 s 修改后字典序最小的字符串。

Sample test(s)

input
ABA
CBA

output
1
ABC

input
CDBABC
ADCABD

output
2
ADBADC

Note

第二个数据，s 可改成: "ADBADC", "ADDABC",
"CDAABD", "CDBAAD", "CDBADA",
"CDDABA", "DDAABC", "DDBAAC".
字典序最小的是 "ADBADC".

直接处理字符串。

program word;
const
   maxn=100000;
var
   s,t:ansistring;//->ansistring
   n,i,j,ans,size,head:longint;
   pass,a1,a2,deln:array['A'..'Z'] of longint;
   add:array[1..26] of char;
   addn:array[1..26] of longint;
   ic:char;
begin
   assign(input,'input.txt');
   assign(output,'output.txt');
   reset(input);
   rewrite(output);
   fillchar(a1,sizeof(a1),0);
   fillchar(a2,sizeof(a2),0);
   fillchar(pass,sizeof(pass),0);
   fillchar(deln,sizeof(deln),0);
   readln(s);
   readln(t);
   n:=length(s);
   for i:=1 to n do inc(a1[s[i]]);
   for i:=1 to n do inc(a2[t[i]]);

   size:=0;
   ans:=0;
   for ic:='A' to 'Z' do
      if a2[ic]>a1[ic] then
      begin
         inc(size);
         add[size]:=ic;
         addn[size]:=a2[ic]-a1[ic];
         inc(ans,addn[size]);
      end
      else if a2[ic]<a1[ic] then
      begin
         deln[ic]:=a1[ic]-a2[ic];
      end;

   writeln(ans);
   head:=1;
   for i:=1 to n do
   begin
      inc(pass[s[i]]);
      if deln[s[i]]>0 then
      begin
         if (add[head]<s[i]) or (deln[s[i]]>a1[s[i]]-pass[s[i]]) then
         begin
            dec(deln[s[i]]);
            s[i]:=add[head];
            dec(addn[head]);
            if addn[head]=0 then inc(head);
         end;
      end;
   end;
   writeln(s);
   close(input);
   close(output);
end.

幸运字符串(ansistring)

Posted on 9 11 月, 2012 by nike0good

幸运字符串(string)

【问题描述】

对于一个只包含0和1的字符串，如果A是幸运的，B也是幸运的，那么1AB1也是一个幸运的串。现在定义”0”是一个幸运字符串，请判断给定的字符串S是否是幸运的。

【输入格式】

第一行一个数字T，表示数据组数。

接下来T组数据，第一行字符串长度n，接下来一行一个只含01的字符串。

【输出格式】

T行，第i个串如果是幸运字符串那么输出”YES”，否则输出”NO”。

【样例输入】

1001

1100101

0110011

【样例输出】

YES

【数据范围】

30%的数据满足n<=100；

50%的数据满足n<=300；

100%的数据满足n<=800，T<=10

未1A的原因，又没改ansistring

//string
var
   n,tt,i,j,now:longint;
   s:ansistring;
function sort(i,j:longint):boolean;
var
   k:longint;
begin







   if (i=j) then
   begin
      if s[i]='0' then exit(true)
      else exit(false);
   end;
 {
   if (s[i]='1') and (s[j]='1') then
   begin
      for k:=i+1 to j-2 do
         if (sort(i+1,k)) and (sort(k+1,j-1)) then exit(true);

   end;
 }
   exit(false);


end;
begin
   assign(input,'string.in');
   assign(output,'string.out');
   reset(input);
   rewrite(output);
   readln(tt);
   while (tt>0) do
   begin
      readln(n);
      readln(s);
      while (true) do
      begin
         i:=pos('1001',s);
         if (i=0) then break;
         delete(s,i,2);
         delete(s,i+1,1);
         dec(n,3);
      end;





      if (sort(1,n)) then writeln('YES')
      else writeln('NO');

      dec(tt);
   end;
   close(input);
   close(output);
end.

传纸条(看清题目）

Posted on 9 11 月, 2012 by nike0good

传纸条(message)

【题目描述】

小N和小A上课喜欢传纸条。

传纸条是有风险的，为了在老师发现的时候不知道他们在讨论什么内容，他们发明了一系列的加密方式。

其中有一种是这样的：一个数字由两个字符串a和b表达，这个数字就是b在a中匹配的位置。比如，a=”abcd”，b=”c”，那么这个数字就是3。

但是这样会出现一个问题，a和b能够表达两个不同的数字：比如，a=“ababa”，b=”aba”时，那个数字可以是1也可以是3。

他们对这种现象很好奇，现在给定一个字符串a，求一个整数x使得对于任意一个长度大于x的串b，这一问题都不会出现。

【输入数据】

一个仅由小写字母组成的字符串a

【输出数据】

一行一个整数，表示x的最小值

【样例输入】

ababa

【样例输出】

【数据范围】

对于50%的数据，a的长度≤10,

对于100%的数据，a的长度≤100.

Program message;
var
   n,i,j,k,l,ans:longint;
   s:string;
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
   assign(input,'message.in');
   assign(output,'message.out');
   reset(input);
   rewrite(output);


   readln(s);
   n:=length(s);
   ans:=0;
   for i:=1 to n do
      for j:=i+1 to n do
      begin
         k:=i;
         l:=j;
         while ((s[k]=s[l]) and (l<=n)) do
         begin
            inc(k);
            inc(l);
            if (l>n) then break;
         end;


         ans:=max(ans,k-i);

      end;
   writeln(ans);

   close(input);
   close(output);

end.

POJ 2271(HTML)

Posted on 29 9 月, 2012 by nike0good

这题字符串处理

注意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 1951（空串特判）

Posted on 15 9 月, 2012 by nike0good

这题的教训是要特判空串

Program P1951;
var
   s:string;
   len,i,j:longint;
   b:array[0..10000] of boolean;
function isdight(x:longint):boolean;
begin
   if (x>=65) and (x<=90) then exit(false);
   if (x>=97) and (x<=122) then exit(false);
   exit(true);

end;
begin
   readln(s);
   fillchar(b,sizeof(b),false);
   b[ord('a')]:=true;
   b[ord('e')]:=true;
   b[ord('i')]:=true;
   b[ord('o')]:=true;
   b[ord('u')]:=true;
   b[ord('A')]:=true;
   b[ord('E')]:=true;
   b[ord('I')]:=true;
   b[ord('O')]:=true;
   b[ord('U')]:=true;

   i:=1;
   while i<=length(s) do
   begin
      if b[ord(s[i])] and not(isdight(ord(s[i]))) then delete(s,i,1)
      else
      begin
         b[ord(s[i])]:=true;
         inc(i);

      end;
   end;


   while (s[1]=' ') and (length(s)>=1) do delete(s,1,1);
   while (s[length(s)]=' ') and (length(s)>=1) do delete(s,length(s),1);
   i:=pos('  ',s);
   while i<>0 do
   begin
      delete(s,i,1);
      i:=pos('  ',s);
   end;
   i:=pos(' .',s);
   while i<>0 do
   begin
      delete(s,i,1);
      i:=pos(' .',s);
   end;
   i:=pos(' ,',s);
   while i<>0 do
   begin
      delete(s,i,1);
      i:=pos(' ,',s);
   end;
   i:=pos(' ?',s);
   while i<>0 do
   begin
      delete(s,i,1);
      i:=pos(' ?',s);
   end;



   writeln(s);

end.

POJ 1002（字符串处理）

Posted on 7 8 月, 2012 by nike0good

这题就是字符串处理

Program P1002;
Type
   phone=record
         num,s:longint;
         end;
var
   n,i,j,p:Longint;
   b:boolean;
   s:ansistring;
   a:array[0..9999999] of longint;
// f:array[1..100000] of phone;
   ch:array['A'..'Z'] of longint=(2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,-1,7,7,8,8,8,9,9,9,-1);
function isdight(c:char):longint;
var
   i,j,p:longint;
begin
   p:=ord(c);
   if (48<=p) and (p<58) then exit(p-48);
   if (65<=p) and (p<=90) then
   begin
      if ch[c]<>-1 then exit(ch[c]);
   end;
   exit(-1);

end;
function hash:longint;
var
   i,j,p:longint;
begin
   j:=0;
   hash:=0;
   for i:=1 to length(s) do
   begin
      if s[i]='-' then continue;
      p:=isdight(s[i]);
      if (p=-1) or ((p<>-1) and (j=7)) then exit(-1);
      hash:=hash*10+p;
      inc(j);
   end;
   if j<>7 then exit(-1);
end;
procedure pri(p:longint);
var
   i,j:longint;
begin
   b:=true;
   i:=p div 10000;
   j:=p mod 10000;
   if i<100 then write('0');
   if i<10 then write('0');
   write(i,'-');
   if j<1000 then write('0');
   if j<100 then write('0');
   if j<10 then write('0');
   writeln(j,' ',a[p]);
end;
Begin
   b:=false;
   readln(n);
   fillchar(a,sizeof(a),0);
   for i:=1 to n do
   begin
      readln(s);
      p:=hash;
      if p=-1 then continue
      else inc(a[p]);
   end;
   for i:=0 to 9999999 do
      if a[i]>1 then pri(i);
   if not(b) then writeln('No duplicates.');


End.

nike0good

有所作为是人生的最高境界

Tag Archives: 字符串处理