正文
題目1
題目鏈接
題目大意：
有n個(gè)糖果衣盾，分給兩個(gè)人A和B，要求：
兩個(gè)人都有分配到糖果；
糖果不能拆分，必須全部分分完；
A的糖果數(shù)量比B的要多遇骑；
問(wèn)，最終有多少種分配方案揖曾。
輸入：
第一行落萎，整數(shù)??表示有t個(gè)樣例數(shù)量 (1≤??≤1000)
接下來(lái)每個(gè)樣例一行，整數(shù)?? (1≤??≤2?1e9)
輸出：
每個(gè)樣例一行炭剪，輸出存在分配方案练链，不存在則輸出0；
Examples
input
6
7
1
2
3
2000000000
763243547
output
3
0
0
1
999999999
381621773
樣例解釋?zhuān)?br>
樣例1：
7個(gè)糖果念祭，有下面3個(gè)方案：
??=6, ??=1;
??=5, ??=2;
??=4, ??=3.
題目解析：
分糖條件寫(xiě)的很清楚兑宇，兩個(gè)整數(shù)a和b，要求a<b粱坤；
對(duì)于數(shù)字n來(lái)說(shuō)隶糕，如果n是偶數(shù)，那么有n/2-1種可能站玄；
如果n是奇數(shù)枚驻，那么有n/2種可能；
利用計(jì)算機(jī)整除的特性株旷，可以表述為(n-1)/2再登；
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << (n - 1) / 2 << endl;
}
return 0;
}
題目2
題目鏈接
題目大意：
有三個(gè)正整數(shù)n尔邓，a，b锉矢，現(xiàn)在需要構(gòu)造一個(gè)字符串s梯嗽，長(zhǎng)度為n，只包含小寫(xiě)字母沽损，并且滿足要求：
字符串s中灯节，任何長(zhǎng)度為a的子串要包含b個(gè)不同的字符。
輸入：
第一行绵估，整數(shù)??表示有t個(gè)樣例數(shù)量 (1≤??≤2000)
接下來(lái)每個(gè)樣例一行炎疆，四個(gè)整數(shù) ??, ?? and ?? (1≤??≤??≤2000,1≤??≤min(26,??))
輸出：
每個(gè)樣例一行，輸出滿足要求的字符串国裳；（題目保證答案一定存在）
Examples
input
4
7 5 3
6 1 1
6 6 1
5 2 2
output
tleelte
qwerty
vvvvvv
abcde
題目解析：
題目的要求是形入，長(zhǎng)度為a的子串中，有b個(gè)不同的字符缝左；
那么將b個(gè)字符構(gòu)成的字符串不斷重復(fù)亿遂，即可滿足題目要求；
比如說(shuō)題目樣例 7 5 3
b=3盒使，則用abc不斷循環(huán)崩掘，得到abcabca
樣例 5 2 2
b=2七嫌，則用ab不斷循環(huán)少办，得到ababa
實(shí)現(xiàn)較為簡(jiǎn)單。
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n, a, b;
cin >> n >> a >> b;
int k = 0;
for (int i = 0; i < n; ++i) {
putchar('a' + k);
k = (k + 1) % b;
}
puts("");
}
return 0;
}
題目3
題目鏈接
題目大意：
有n個(gè)整數(shù)a[i]诵原，現(xiàn)在需要從中選擇兩組數(shù)字英妓，要求：
1、兩組數(shù)字的數(shù)量一樣绍赛，每個(gè)整數(shù)只能劃分到一個(gè)組內(nèi)蔓纠；
2、第一組的數(shù)字各不相同吗蚌，第二組的數(shù)字完全相同腿倚；
現(xiàn)在希望兩組數(shù)字盡可能的多，問(wèn)最多一組能有幾個(gè)整數(shù)蚯妇。
輸入：
第一行敷燎，整數(shù)??表示有t個(gè)樣例數(shù)量 (1≤??≤10000)
接下來(lái)每個(gè)樣例兩行，第一行整數(shù)?? (1≤??≤2?1e5)
第二行n個(gè)整數(shù) ??1,??2,…,???? (1≤????≤??),
輸出：
每個(gè)樣例一行箩言，整數(shù)x硬贯，表示一組最多能夠有x個(gè)整數(shù)。
Examples
input
4
7
4 2 4 1 4 3 4
5
2 1 5 4 3
1
1
4
1 1 1 3
?output
?3
?1
?0
?2
題目解析：
假如沒(méi)有要求2陨收，那么直接平分饭豹，x最大值就是n/2；
單獨(dú)考慮不同數(shù)字的情況，直接算出數(shù)組中有k個(gè)不同的整數(shù)q拄衰，再算出數(shù)組中最多重復(fù)的整數(shù)w;
大多數(shù)情況下它褪，min(q, w)就是答案了。
但是存在q和w會(huì)公用一個(gè)整數(shù)翘悉，比如說(shuō)1.2.3,3,3這種情況列赎，或者1.2.3.4.5.2.2情況。
當(dāng)w<=q-1的時(shí)候镐确，重復(fù)的數(shù)字比較少包吝，所以答案就是w；
如果w>q-1的時(shí)候源葫，重復(fù)的數(shù)字比較多诗越，那么優(yōu)先把重復(fù)的數(shù)字分配到第一組，答案就是min(w-1,q)息堂；
int a[N];
map<int, int> hmap;
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
hmap.clear();
int maxCount = 0;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
++hmap[k];
maxCount = max(maxCount, hmap[k]);
}
if (hmap.size() <= maxCount - 1) {
cout << hmap.size() << endl;
}
else {
cout << min((int)hmap.size() - 1, maxCount) << endl;
}
}
return 0;
}
題目4
題目鏈接
題目大意：
長(zhǎng)度為n的字符串嚷狞，一共有三種字符，'B', 'R', '?'荣堰；
'?'的字符需要填充為'B'或者'R'床未；
現(xiàn)在小明不喜歡相連兩個(gè)字符是一樣的， 現(xiàn)在需要知道怎么填充使得最終相連兩個(gè)字符相同的情況盡可能少振坚？
比如說(shuō)"BRRRBBR"就有3個(gè)相連的字符相同薇搁，"BB"出現(xiàn)一次，"RR"出現(xiàn)兩次渡八；
輸入：
第一行啃洋，整數(shù)??表示有t個(gè)樣例數(shù)量 (1≤??≤100)
接下來(lái)每個(gè)樣例兩行，第一行整數(shù)?? (1≤??≤100)
第二行長(zhǎng)度為n的字符串s
輸出：
每個(gè)樣例一行屎鳍，輸出由'B'和'R'字符串構(gòu)成的字符串宏娄。
Examples
input
5
7
?R???BR
7
???R???
1
?
1
B
10
?R??RB??B?
output
BRRBRBR
BRBRBRB
B
B
BRRBRBBRBR
題目解析：
方案1，動(dòng)態(tài)規(guī)劃逮壁，dp[i][2]表示前i個(gè)字符孵坚，第i個(gè)字符為B、R的最小重復(fù)次數(shù)窥淆；
初始化的時(shí)候卖宠，如果第1個(gè)字符是？則dp[1][0]=dp[1][1]=0祖乳；
第1個(gè)字符是B逗堵，則dp[1][0]=0，dp[1][1]=n;（n是極大值眷昆，表示dp[1][1]不可妊殉印）
第1個(gè)字符是R汁咏，則dp[1][1]=0，dp[1][0]=n;（n是極大值作媚，表示dp[1][0]不可热撂病）
狀態(tài)轉(zhuǎn)移的時(shí)候，dp[i]可以由dp[i-1]來(lái)進(jìn)行計(jì)算纸泡；
如果a[i]==B漂问，則dp[i][0] = min(dp[i-1][0]+1, dp[i-1][1])； dp[i][1]=n;
如果a[i]==R女揭，則dp[i][1] = min(dp[i-1][1]+1, dp[i-1][0])蚤假； dp[i][1]=n;
這樣看最終dp[n]的最小值即可。
方案2吧兔，找到第一個(gè)不為?的字符磷仰，從這個(gè)位置分別向左右開(kāi)始填充，每次優(yōu)先選擇相鄰字符不相同的方案境蔼；
??R??
RBRBR
方案3灶平，通過(guò)數(shù)學(xué)直接計(jì)算；
從左到右箍土，如果第i個(gè)字符串前面??沒(méi)有確定字符逢享，則這段?不會(huì)產(chǎn)生特殊字符；若吴藻？瞒爬？前面有確定字符k，則根據(jù)a[i]和a[k]以及(i-k)可以直接計(jì)算出來(lái)有多少個(gè)相同字符调缨；（0或者1）
考慮到題目要輸出結(jié)果疮鲫，還是方案2比較簡(jiǎn)單吆你。
思考??：
如果是要連續(xù)3個(gè)字符串不一樣呢弦叶？
class Solution {
static const int N = 200010;
string str;
char ans[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> str;
int pos = n;
for (int i = 0; i < n; ++i) {
if (str[i] != '?') {
pos = i;
break;
}
}
ans[n] = '\0';
if (pos == n) {
for (int i = 0; i < n; ++i) {
ans[i] = i % 2 ? 'B' : 'R';
}
}
else {
ans[pos] = str[pos];
for (int i = pos - 1; i >= 0; --i) {
if (str[i] == '?') {
ans[i] = 'B' + 'R' - ans[i + 1];
}
else {
ans[i] = str[i];
}
}
for (int i = pos + 1; i < n; ++i) {
if (str[i] == '?') {
ans[i] = 'B' + 'R' - ans[i - 1];
}
else {
ans[i] = str[i];
}
}
}
printf("%s\n", ans);
}
}
}
ac;
題目5
題目鏈接
題目大意：
從n個(gè)整數(shù)的數(shù)組中，找到(i, j) 要求 l ≤ a[i]+a[j] ≤ r妇多，問(wèn)有多少(i, j)符合要求伤哺；
輸入：
第一行是整數(shù)t，表示有t個(gè)樣例 (1≤??≤10000 ).
每個(gè)樣例第一行是整數(shù)??,??,?? (1≤??≤2?1e5, 1≤??≤??≤1e9)
第二行是n個(gè)整數(shù)??1,??2,…,???? (1≤????≤109).
輸出：
(??,??)的數(shù)量者祖，要求是 (??<??) 并且 ??≤????+????≤??.
Examples
input
4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1
output
yes
2
7
0
1
題目解析：
題目要求的是任意a[i]和a[j]立莉，那么數(shù)組的順序沒(méi)有意義，可以直接將數(shù)組進(jìn)行排序七问；
如果不考慮復(fù)雜度蜓耻，我們可以枚舉pair(i, j)是否滿足要求，這樣復(fù)雜度是N*N械巡；
由于排序完之后刹淌，數(shù)組是有序的饶氏，我們?cè)诿杜epair(i, j)的時(shí)候，可以采用下面的策略：
從小到大枚舉i有勾，假設(shè)已經(jīng)先取了數(shù)字a[i]并且i<j疹启，要求是找到l<=a[i]+a[j]<=r，那么就是在區(qū)間[i+1, n]里面找到l-a[i]作為起點(diǎn)蔼卡，r-a[i]作為終點(diǎn)的區(qū)間喊崖；
我們可以采用二分查找來(lái)，也可以使用快捷方法lower_bound雇逞。
class Solution {
static const int N = 200010;
public:
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, l, r;
cin >> n >> l >> r;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
lld sum = 0;
for (int i = 0; i + 1 < n; ++i) {
int left = l - a[i];
int right = r - a[i] + 1;
// 從i+1開(kāi)始荤懂，找到第一個(gè)大于等于left的數(shù)字作為起點(diǎn)x
int x = lower_bound(a + i + 1, a + n, left) - a;
if (x >= n) {
continue;;
}
// 新x開(kāi)始，找到第一個(gè)大于right的數(shù)字作為終點(diǎn)y
int y = lower_bound(a + x, a + n, right) - a;
sum += y - x;
}
cout << sum << endl;
}
}
}
ac;
