2011-06-28 14:53:55Morris
d017. AB Circle
內容 ：
這裡有一個圓，它是由 A 和 B 所組成，我們給它一個名字叫做AB Circle，你可以看到圖中從圓中找出兩個端點切開，我們可以得到兩個字串，仔細觀察，聰明的你應該發現了，其中一個字串中 A 的數量等於另一個字串中 B 的數量。
找出一個這樣的切法很簡單，可是每個圓的切法可能不只一種，而你現在的工作就是要找出一個圓中所有的切法。
輸入說明
：
1.每一筆的輸入長度介於2到1000以內
2.輸入只會有'a'和'b'兩個字元
3.每個字串內都會包含'a'
4.每個字串內都會包含'b'
輸出說明
：
1.在輸出答案前，請先輸出"AB Circle #n:"，其中 n 代表第n筆
2.輸入可能會超過200筆測試資料，對於每一筆案例，請輸出符合條件的各種切法的兩個端點，中間以 ',' 分開
3.所有輸出的答案，必需經過排序，請參考範例輸出
4.對於長度n的輸入，輸出的端點介於0到n-1之間
5.對於每一筆案例所得到的輸出間，請空一行，可參考範例輸出
範例輸入 ：
ab baa
範例輸出 ：
AB Circle #1: 0,1 AB Circle #2: 0,1 0,2 1,2
提示
：
背景知識：
DP
為了讓你更清楚題意，解釋第二筆案例的輸出 輸入 : baa 從 0,1 切開 : 得到了 b 和 aa 兩個字串 "b"字串中'a'的數量剛好等於"aa"字串中'b'的數量，也就是 0 從 0,2 切開 : 得到了 ba 和 a 兩個字串 "ba"字串中'b'的數量剛好等於"a"字串中'a'的數量，也就是 1 從 1,2 切開 : 得到了 a 和 ab 兩個字串 "a"字串中'a'的數量剛好等於"ab"字串中'b'的數量，也就是 1 請注意 : 輸出的結果可能會很龐大.
為了讓你更清楚題意，解釋第二筆案例的輸出 輸入 : baa 從 0,1 切開 : 得到了 b 和 aa 兩個字串 "b"字串中'a'的數量剛好等於"aa"字串中'b'的數量，也就是 0 從 0,2 切開 : 得到了 ba 和 a 兩個字串 "ba"字串中'b'的數量剛好等於"a"字串中'a'的數量，也就是 1 從 1,2 切開 : 得到了 a 和 ab 兩個字串 "a"字串中'a'的數量剛好等於"ab"字串中'b'的數量，也就是 1 請注意 : 輸出的結果可能會很龐大.
出處
：
以下是新版
只要知道A的個數，以及B的個數即可
假設起始點是i，那麼它CUT的就是i+min(CA,CB) or i+max(CA,CB)
i~j有x個A以及j-i+1-x個B，以外則有CA-x個A以及CB-j+i-1+x個B
1. x=CB-j+i-1+x => j=CB+i-1;
2. j-i+1-x=CA-x => j=CA+i-1;
決定小或大的先後吧
/**********************************************************************************/
/* Problem: d017 "AB Circle" from ZHENG, Jianqiang */
/* Language: C */
/* Result: AC (42ms, 252KB) on ZeroJudge */
/* Author: morris1028 at 2010-11-08 16:08:24 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Max(int x, int y)
{
if(x>y) return x;
else return y;
}
int Min(int x, int y)
{
if(x<y)return x;
else return y;
}
main()
{
char S[1001], t=0;
while(scanf("%s",&S)==1)
{
printf("AB Circle #%d:\n",++t);
int CA=0, CB=0, a, L;
for(a=0;S[a];a++)
if(S[a]=='a') CA++;
else CB++;
for(L=a, a=0;a+Min(CA,CB)<L;a++)
{
if(CA!=CB)
{
printf("%d,%d\n",a,a+Min(CA,CB));
if(a+Max(CA,CB)<L)
printf("%d,%d\n",a,a+Max(CA,CB));
}
else printf("%d,%d\n",a,a+CA);
}
}
return 0;
}
上一篇：d816. 不要再晃啦！
下一篇：a164. 區間最大連續和