Daily Archives: 9 12 月, 2012

CF 254C(易位构字法）

Posted on by
C. 易位构字法
time limit per test

1 second

memory limit per test

256 megabytes

input

input.txt

output

output.txt

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

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

Input

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

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.

CF 254B(日期)

Posted on by
B. 评委会
time limit per test

1 second

memory limit per test

256 megabytes

input

input.txt

output

output.txt

2013年要举办 n 场比赛，编号1 到 n. 每场比赛需要人准备（在开幕的前 ti 天(不包括开幕当天））

如果准备时间重复，一个人一天只能为一场比赛准备，请问最少需要雇多少人准备？

Input

第一行一个整数 n  (1 ≤ n ≤ 100). 接下来 n 行每行为mi, di, pi 和 ti —
开幕的月份，日期，每天需要的人数，准备天数 (1 ≤ mi ≤ 12, di ≥ 1, 1 ≤ pi, ti ≤ 100),输入顺序任意，一天可能有同时多场比赛开幕。

非润年，二月28天. 可能需要在2012年某天开始准备.

Output

输出最小人数。

Sample test(s)
input
2
5 23 1 2
3 13 2 3
output
2
input
3
12 9 2 1
12 8 1 3
12 8 2 2
output
3
input
1
1 10 1 13
output
1

直接模拟，注意日期换算。


Program jury;
var
   n,i,j,m,d,p,t,ans:longint;
   month:array[1..12] of longint=(31,28,31,30,31,30,31,31,30,31,30,31);
   a:array[-1000..1000] of longint;
begin
   assign(input,'input.txt');
   assign(output,'output.txt');
   reset(input);
   rewrite(output);
   read(n);
   fillchar(a,sizeof(a),0);
   for i:=1 to n do
   begin
      read(m,d,p,t);
      for j:=1 to m-1 do inc(d,month[j]);
      for j:=d-1 downto d-t do
         inc(a[j],p);
   end;
   ans:=0;
   for i:=-1000 to 1000 do
      if ans<a[i] then ans:=a[i];
   writeln(ans);

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

CF 254A(重复的数)

Posted on by
A. 数字卡片
time limit per test

1 second

memory limit per test

256 megabytes

input

input.txt

output

output.txt

有2n张卡片编号为1 .. 2n.卡片数字相同可凑成一对，能否凑完？

Input

第一行1个整数n (1 ≤ n ≤ 3·105).
第二行有2n个整数a1, a2, ..., a2n (1 ≤ ai ≤ 5000)
表示第i张卡片的数字。

Output

如果凑不完，请输出 -1.否则输出 n 行，每行一对对整数，表示第i张卡片与第j张凑成一对。

输出任意方案。

Sample test(s)
input
3
20 30 10 30 20 10
output
4 2
1 5
6 3
input
1
1 2
output
-1

直接用数组记录出现次数，每遇到一对，就扔入解中。

Program Cards;
const
   maxn=300000;
var
   n,i,p,size:longint;
   a:array[1..5000] of longint;
   q1,q2:array[1..maxn] of longint;
begin
   assign(input,'input.txt');
   assign(output,'output.txt');
   reset(input);
   rewrite(output);

   read(n);
   fillchar(a,sizeof(a),0);
   size:=1;
   for i:=1 to 2*n do
   begin
      read(p);
      if a[p]>0 then
      begin
         q1[size]:=a[p];q2[size]:=i;
         inc(size);
         a[p]:=0;
      end
      else a[p]:=i;
   end;
   if size<>n+1 then writeln('-1')
   else for i:=1 to n do writeln(q1[i],' ',q2[i]);

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