共有回帖数 0 个
-
题目都来自 USACO
Broken Necklace
You have a necklace of N red, white, or blue beads (3=N=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:
1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead
The beads considered first and second in the text that follows have been marked in the picture.
The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .
Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).
Determine the point where the necklace should be broken so that the most number of beads can be collected.
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead
The beads considered first and second in the text that follows have been marked in the picture.
The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .
Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).
Determine the point where the necklace should be broken so that the most number of beads can be collected.
Example
For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.
In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration will include the three symbols r, b and w.
Write a program to determine the largest number of beads that can be collected from a supplied necklace.
PROGRAM NAME: beads
INPUT FORMAT
Line 1: N, the number of beads
Line 2: a string of N characters, each of which is r, b, or w
SAMPLE INPUT (file beads.in)
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
OUTPUT FORMAT
A single line containing the maximum of number of beads that can be collected from the supplied necklace.
SAMPLE OUTPUT (file beads.out)
11
OUTPUT EXPLANATION
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
****** *****
直接枚举是Ο(n^2)，题目数据规模不大，也能过。还有一种Θ(n)的动态规划算法统计从某个位置起，向左或向右能取的红色蓝色珠子数，较为复杂。
下面是另一种Θ(n)的算法：
环形处理起来不方便，可以把字符串复制一份连接起来，就成了链状了。这是一个非常重要的思想……不仅限于这道题。
用 curr 记录连续的白色或当前颜色的珠子数量
w 记录当前连续的白色珠子数量。如果当前珠子不是白色的，则为0，否则就是连续的白色珠子数量。
prev 记录之前颜色（和当前颜色相反）珠子的数量
res 输出的答案
如果当前处理的珠子为白色，++w，++curr；为当前颜色，w=0，++curr；另一种颜色，则连续珠子数为prev+curr，更新结果
如果最后res大于n，则说明所有珠子都可以取出来，输出n
#include stdio.h
#include string.h
char a[701];
int main()
{
freopen("beads.in", "r", stdin);
freopen("beads.out", "w", stdout);
int color = 0, curr = 0, prev = 0, w = 0, n, res = 0;
scanf("%d%*c", &n);
gets(a);
memcpy(a+n, a, n);
for (int i = 0; i n*2 && res n; ++i)
{
if (a == 'w') ++w, ++curr;
else if (a == color) w = 0, ++curr;
else
{
color = a;
if (prev+curr res) res = prev+curr;
prev = curr-w; curr = w+1; w = 0;
}
}
if (prev+curr res) res = prev+curr;
printf("%dn", res n ? res : n);
}
Milking Cows
Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).
Your job is to write a program that will examine a list of beginning and ending times for N (1 = N = 5000) farmers milking N cows and compute (in seconds):
• The longest time interval at least one cow was milked.
• The longest time interval (after milking starts) during which no cows were being milked.
PROGRAM NAME: milk2
INPUT FORMAT
Line 1: The single integer
Lines 2..N+1: Two non-negative integers less than 1000000, the starting and ending time in seconds after 0500
SAMPLE INPUT (file milk2.in)
3
300 1000
700 1200
1500 2100
OUTPUT FORMAT
A single line with two integers that represent the longest continuous time of milking and the longest idle time.
SAMPLE OUTPUT (file milk2.out)
900 300
按区间的起始点把所有区间排序。
先选择第一个区间，从第二个区间开始寻找与第一个区间连通的所有区间的并集（就是把能合并的区间合并），同时求出间隙。这个过程可以在Θ(n)时间内完成。
#include algorithm
#include cstdio
using namespace std;
struct node
{
int bgn, end;
bool operator(const node &rhs) const
{
return bgn rhs.bgn;
}
}a[5000];
int main()
{
freopen("milk2.in", "r", stdin);
freopen("milk2.out", "w", stdout);
int bgn, end, n, res1 = 0, res2 = 0;
scanf("%d", &n);
for (int i = 0; i n; ++i)
scanf("%d%d", &a.bgn, &a.end);
sort(a, a+n);
int left = a[0].bgn, right = a[0].end;
for (int i = 1; ; ++i)
{
for (; i n && a.bgn = right; ++i)
if (a.end right)
right = a.end;
if (right-left res1) res1 = right-left;
if (i == n) break;
if (a.bgn-right res2) res2 = a.bgn-right;
left = a.bgn; right = a.end;
}
printf("%d %dn", res1, res2);
}
Prime Palindromes
The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 = a b = 100,000,000); both a and b are considered to be within the range .
PROGRAM NAME: pprime
INPUT FORMAT
Line 1: Two integers, a and b
SAMPLE INPUT (file pprime.in)
5 500
OUTPUT FORMAT
The list of palindromic primes in numerical order, one per line.
SAMPLE OUTPUT (file pprime.out)
5
7
11
101
131
151
181
191
313
353
373
383
题目的意思是求a、b之间的所有回文素数。对于大于11的含有偶数个数字的数肯定不是素数（它必然能被11整除），大于2的回文素数，它的首位只能是奇数。用到这两个优化的算法速度很快。下面的代码还用了Miller-Rabin算法，进行素性测试
#include algorithm
#include cstdio
#include cstdlib
using namespace std;
int prime[] = {3,5,7,11,13,17,19,23,29};
bool Miller_Rabin(int n)
{
int k, p, q, t;
long long a;
for (q = 0, p = n-1; p % 2 == 0; p /= 2, ++q);
for (k = 1, t = p; t /= 2; k *= 2);
for (int times = 3; times; --times)
{
int i = rand() % (n-2) + 2;
for (a = i % n, t = k; t /= 2; )
{
a = a * a % n;
if (t & p) a = a * i % n;
}
if (a == 1) continue;
for (i = q; i; --i)
{
long long b = a * a % n;
if (b == 1)
{
if (a == n-1) goto L1;
return false;
}
a = b;
}
if (a != 1) return false;
L1:;
}
return true;
}
int main()
{
int bgn, end;
freopen("pprime.in", "r", stdin);
freopen("pprime.out", "w", stdout);
scanf("%d%d", &bgn, &end);
if (bgn = 5 && 5 = end) puts("5");
if (bgn = 7 && 7 = end) puts("7");
if (bgn = 11 && 11 = end) puts("11");
for (int bit = 2, k = 10; bit = 5; ++bit, k *= 10)
for (int front = 1; front = 9; front += 2)
{
if (front * k * k end) goto L3;
for (int rear = 0; rear k; ++rear)
{
int t = front * k + rear, n = t, i = bit - 1;
do n = n * 10 + (t /= 10) % 10;
while (--i);
if (n bgn || n end) continue;
for (int i = 0; i sizeof(prime) / sizeof(prime[0]); ++i)
if (n % prime == 0) goto L2;
if (!Miller_Rabin(n)) goto L2;
printf("%dn", n);
L2:;
}
}
L3:;
}
楼主 2015-12-31 12:57 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
