首页 > 代码库 > BestCoder Round #11 题解集合

BestCoder Round #11 题解集合

2024-07-24 22:22:58   218人阅读

1001.Alice and Bob

签到题*1，只要x * 2 == n && y * 2 == m就满足条件。

1 var2   m, n, x, y : int64;3   4 begin5   while not eof do begin6     readln(m, n, x, y);7     if (m = 2 * x) and (n = 2 * y) then writeln(‘YES‘) else writeln(‘NO‘);8   end;9 end.
View Code

 

1002.Bob and math problem

我真是WA的不行，但是很明显我的算法没有问题啊。。。

我的算法：统计0到9的个数，然后找出最小的奇数放到末尾，接着从9到0输出，最后输出选出的那个奇数。

中间要判断输出-1的情况：没有奇数；找出一个奇数以后只剩下0了。

 1 var 2   num : array[0..9] of longint; 3   n, ch, i, j, x : longint; 4  5 function find : boolean; 6 var 7   i : longint; 8   flag : boolean; 9 10 begin11   flag := true;12   for i := 1 to 9 do13     if num[i] > 0 then flag := false;14   find := flag and (n <> 1);15 end;16 17 begin18   while not eof do begin19     readln(n);20     fillchar(num, sizeof(num), 0);21     for i := 1 to n do begin22       read(x);23       inc(num[x]);24     end;25     ch := 0;26     for i := 1 to 5 do begin27       j := i * 2 - 1;28       if num[j] > 0 then begin29         ch := j;30         dec(num[j]);31         break;32       end;33     end;34     if (ch = 0) or find then begin35       writeln(-1);36       continue;37     end;38     for i := 9 downto 0 do39       while num[i] > 0 do begin40         write(i);41         dec(num[i]);42       end;43     writeln(ch);44   end;45 end.
View Code

 

1003.Boring count

这道题看了数据范围就知道要O(n)的算法，因为O(nlogn)的算法有点不大科学。。。

于是我来统计以每个字符s[j]为结尾的满足要求的字符串的个数，不妨设suff[i, j]表示s[i]到s[j]的子串。

又很明显如果suff[i, j]不满足条件了，则suff[i - 1, j]也不满足条件，若令f[j]表示以字符s[j]结尾的最左边满足条件的位置，则f[j]关于j是单调增的。

于是每次枚举j然后查找f[j], ans += j - f[j] +１即可。

 1 var 2   i, x, k, len, left, t1 : longint; 3   first, next, num, last : array[0..150000] of longint; 4   s : ansistring; 5   T : longint; 6   ans : int64; 7  8 begin 9   readln(T);10   while T > 0 do begin11     dec(T);12     ans := 0;13     readln(s);14     readln(k);15     len := length(s);16     left := 0;17     fillchar(first, sizeof(first), 0);18     fillchar(last, sizeof(last), 0);19     fillchar(num, sizeof(num), 0);20 21     for i := 1 to len do begin22       x := ord(s[i]);23       if first[x] = 0 then first[x] := i;24       inc(num[x]);25       next[last[x]] := i;26       last[x] := i;27       if num[x] > k then begin28         dec(num[x]);29         t1 := first[x];30         first[x] := next[first[x]];31         if t1 > left then left := t1;32       end;33       inc(ans, i - left);34     end;35     writeln(ans);36   end;37 end.
View Code


1004.Argestes and Sequence

还没搞定啊。。 

 

BestCoder Round #11 题解集合


联系
我们