红蓝牌

最新推荐文章于 2021-07-25 10:49:14 发布

masterwater

最新推荐文章于 2021-07-25 10:49:14 发布

阅读量354

点赞数

分类专栏：神奇的解法

本文链接：https://blog.csdn.net/masterwater/article/details/69641778

版权

神奇的解法专栏收录该内容

10 篇文章

订阅专栏

2012年佛山市GDOI选拔赛题红蓝牌

Time Limit:20000MS Memory Limit:256000K
Total Submit:21 Accepted:12
Case Time Limit:1000MS

Description

明明有N张牌，正面按编号写有数字1到N（每个数字只出现一次）。每张牌的反面根据正面的数字涂上两种颜色。如果正面的数字是质数，则为红色，反之为蓝色。
明明的老师从这N张牌里选出了一些，按数字从小到大排序后全部反面向上放成一行。他要明明判断这些牌上的数字。

Input

第一行：一个正整数N, 1 <= N <= 1000.
第二行：一个字符串，长度 K 在 1 到 50 之间。字符串中只有'R'和'B'，'R'表示红色，'B'表示蓝色。

Output

一行，有K个整数，每个整数代表相应位置上的牌的正面数字。如果某张牌不能确定上面的数字，否则输出-1.

Sample Input

样例1
5
RRR

样例2
7
BBB

样例3
6
RBR

Sample Output

Hint

数据范围：
对于10%数据 1 ≤ n ≤ 20
对于50%数据 1 ≤ n ≤ 200
对于所有数据 1 ≤ n ≤ 1000

题解：正着做一次，倒着做一次，不同的就是不确定的

const
  maxn=2000;
var
  f,a,b:array[0..maxn]of longint;
  n,i,j:longint;
  st:string;

procedure init;
var
  i,j:longint;
begin
  readln(n);
  f[1]:=1;
  for i:=2 to trunc(sqrt(n)) do
    for j:=2 to n div i do
      f[i*j]:=1;
   readln(st);
end;

begin
  init;
  j:=0;
  for i:=1 to length(st) do
  begin
    if st[i]='R' then
    begin
      inc(j);
      while f[j]=1 do inc(j);
      inc(a[0]);a[a[0]]:=j;
    end;
    if st[i]='B' then
    begin
      inc(j);
      while f[j]=0 do inc(j);
      inc(a[0]);a[a[0]]:=j;
    end;
  end;
  j:=n+1;
  b[0]:=length(st)+1;
  for i:=length(st) downto 1 do
  begin
    if st[i]='R' then
    begin
      dec(j);
      while f[j]=1  do dec(j);
      dec(b[0]);b[b[0]]:=j;
    end;
    if st[i]='B' then
    begin
      dec(j);
      while f[j]=0 do dec(j);
      dec(b[0]);b[b[0]]:=j;
    end;
  end;
  for i:=1 to a[0] do
    if a[i]<>b[i] then write(-1,' ') else write(a[i],' ');
end.