目錄
- T1 [Daimayuan] 一半相等（C++，數學）
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 資料規模
- 解題思路
- T2 [Daimayuan] 兔紙（C++，二分）
- 題目背景
- 題目描述
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 資料范圍
- 附加說明
- 解題思路
- T3 [Daimayuan] 添加括號（C++，數學）
- 輸入格式
- 輸出格式
- 資料范圍
- 輸入樣例
- 輸出樣例
- 解題思路
- T4 [Daimayuan] 貪就是了（C++，BFS）
- 題目描述
- 輸入描述
- 輸出描述
- 樣例輸入1
- 樣例輸出1
- 樣例輸入2
- 樣例輸出2
- 資料范圍
- 解題思路
- T5 [Daimayuan] 算的我頭都大啦（C++，數學）
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 解題思路
- T6 [Daimayuan] 全部相等（C++，數學）
- 資料規模
- 輸入格式
- 輸出格式
- 樣例 1 輸入
- 樣例 1 輸出
- 樣例 2 輸入
- 樣例 2 輸出
- 樣例 3 輸入
- 樣例 3 輸出
- 解題思路
- T7 [Daimayuan] 分段求和（C++，二分）
- 輸入格式
- 資料范圍
- 輸出格式
- 輸入樣例
- 輸出樣例
- 解題思路
- T8 [Daimayuan] nice party（C++，二分，貪心）
- 輸入描述
- 輸出描述
- 樣例輸入
- 樣例輸出
- 解題思路
- T9 [Daimayuan] Gene（C++，字串）
- 題目描述
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 樣例說明
- 資料范圍
- 解題思路
- T10 [Daimayuan] 贏救瓜瓜（C++，字串哈希）
- 題目描述
- 輸入描述
- 輸出描述
- 樣例輸入
- 樣例輸出
- 說明
- 解題思路
T1 [Daimayuan] 一半相等（C++，數學）
給定 \(n\) （\(n\) 為偶數）個整數陣列 \(a_1,a_2,…,a_n\)
考慮這樣的一個 \(k\)，每次操作選定一個 \(i\)，將 \(a_i\) 減少 \(k\)，執行多次（可能 \(0\) 次）后使得陣列中至少有一半的元素相等，求最大的 \(k\)，如果這樣的 \(k\) 為無窮大，輸出 \(?1\)
輸入格式
輸入包含兩行，第一行為一個正整數 \(n\)，表示陣列大小，第二行為 \(n\) 個整數 \(a_1,a_2,…,a_n\)
輸出格式
輸出題意中的 \(k\)
樣例輸入
8
-1 0 1 -1 0 1 -1 0
樣例輸出
2
資料規模
\(4≤n≤100\)，資料保證 \(n\) 為偶數
\(?10^6≤a_i≤10^6\)
解題思路
既然有一半的元素能夠在相同的\(k\)的作用下達到相等即達到一個共同的值，
那么這一半的元素到這個共同值的距離可以被\(k\)整除，而要求\(k\)盡可能的大，故類似于最大公約數，
（當陣列中已經有就有一半的元素相等，那么可以直接輸出\(-1\)，）
但是我們要求哪一半元素？又是要求到誰的距離呢？
（注意是距離，也就是差值的絕對值，因為轉化是雙向的，如\(1-2=-1,-1-(-2)=1\)）
因為存在這樣一種情形：一半的元素到\(x\)的距離的gcd，大于到\(y\)的距離的gcd，
例如：\(2,5\)到\(0\)的距離的最大公約數是\(1\)，而到\(-1\)的距離的最大公約數是\(3\)，
所以選擇的目標位置會對最終的結果產生影響，
但是我們可以證明目標位置一定在給定的陣列中：
直觀起見，以下面這個陣列為例，應該選擇的一半元素是\(2,5,8,8\)，
2 5 3 3 8 8
對此，我們可以選擇\(-1\)作為目標位置，拿到最大公約數\(3\)，
但是我們同樣也可以選擇\(2\)作為目標位置，拿到最大公約數\(3\)，
我們想不出一種比較好的演算法來解決以上的兩個問題，所以采用暴力搜索（畢竟\(n\le100\)）：
1）嘗試將每一個數作為目標位置；
2）計算其他所有數到目標位置的距離；
3）求出距離的所有的因子并統計其出現的頻率；
4）保留最大的因子，
最后，AC代碼如下：
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
const int max_n = 100;
int arr[max_n];
map<int, int>freqs;
void division(int x) {
int i;
for (i = 1; i * i < x; i++) {
if (x % i == 0) {
freqs[i]++;
freqs[x / i]++;
}
}
if (i * i == x) freqs[i]++;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
const int temp = arr[i];
int cnt = 0;
for (int j = 0; j < n; j++) {
if (temp == arr[j]) cnt++;
else division(abs(temp - arr[j]));
}
if (cnt >= n / 2) {
cout << -1 << endl;
return 0;
}
for (auto iter : freqs)
if (iter.second + cnt >= n / 2)
ans = max(ans, iter.first);
freqs.clear();
}
cout << ans << endl;
return 0;
}
T2 [Daimayuan] 兔紙（C++，二分）
題目背景
鶸尛鱻養了許多兔紙，
題目描述
眾所周知，兔紙是一種神奇的生物，它有許多種毛色，
鶸尛鱻一共有 \(n\) 只兔紙，它們從左到右排成一排，第 \(i\) 只兔紙的毛色為 \(col_i\)，
兔紙們十分活躍，時常會與旁邊的兔紙交換位置，
五顏六色的兔紙弄得鶸尛鱻眼花繚亂，他想統計區間 \([l,r]\) 內兔紙的顏色，但他的數學很差，你可以幫幫他嗎？
輸入格式
第 \(1\) 行兩個正整數 \(n,m\) 分別表示兔紙數量和操作次數，
第 \(2\) 行 \(n\) 個正整數 \(col_1,col_2,…,col_n\)，表示初始狀態下從左到右每只兔紙的顏色，
此后 \(m\) 行，每行輸入格式為 1 x 或 2 l r c，其中 \(\{1/2\}\) 表示操作型別，
操作 \(1\) 為 交換 操作，表示第 \(x\) 只兔紙和第 \(x+1\) 只兔紙交換位置，
操作 \(2\) 為 查詢 操作，詢問當前區間 $[l,r] $內有多少只顏色為 \(c\) 的兔紙，
輸出格式
對于每個操作 \(2\)，你需要輸出一行一個自然數作為答案，
樣例輸入
7 9
8 7 6 6 7 8 3
1 5
1 4
2 1 7 7
1 6
1 4
2 3 6 8
2 1 3 7
2 1 2 6
2 2 5 7
樣例輸出
2
1
1
0
1
資料范圍
對于全部測驗資料，滿足 \(2≤n≤3×10^5\)，\(1≤m,col_i,c≤3×10^5\)，且保證 \(1≤x<n\)，\(1≤l<r≤n\)，
附加說明
原題：P3939 數顏色
解題思路
最開始看到題目描述的時候，第一反應是用可持久化線段樹來實作，
但是還有另外一種更簡單快速的方法：二分（lower_bound()和upper_bound()），
這里只介紹代碼的邏輯（因為演算法比較emm神奇，很難說怎么想出來的）：
采用vector容器，為每一種顏色維護一個容器，
每一個容器中維護著所有該種顏色兔紙的位置，
這樣每一只兔紙都有兩個標識：1）在佇列中的位置；2）在容器中的索引，
交換操作就是將兔紙\(x\)位置++，將兔紙\(x+1\)位置--，
如果要交換的兩個兔紙位置相同則不進行任何操作，這樣可以保證vector容器中的元素始終具有單調性，
查詢操作是整個演算法最巧妙的地方：
使用lower_bound()和upper_bound()獲取指定范圍\([l,r]\)內最左邊兔紙的索引和最右邊兔紙的索引，
兩個索引的差值\(+1\)即為答案，
最后，AC代碼如下：
#include <iostream>
#include <vector>
using namespace std;
const int max_n = 3e5;
const int max_c = 3e5;
int rabbits[max_n + 1];
vector<int>pos[max_c + 1];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> rabbits[i];
pos[rabbits[i]].push_back(i);
}
int select, x, l, r, c;
while (m--) {
cin >> select;
if (select == 1) {
cin >> x;
if (rabbits[x] == rabbits[x + 1]) continue;
int col_1 = rabbits[x], col_2 = rabbits[x + 1];
swap(rabbits[x], rabbits[x + 1]);
int ret_1 = lower_bound(pos[col_1].begin(), pos[col_1].end(), x) - pos[col_1].begin();
pos[col_1][ret_1]++;
int ret_2 = lower_bound(pos[col_2].begin(), pos[col_2].end(), x + 1) - pos[col_2].begin();
pos[col_2][ret_2]--;
}
else {
cin >> l >> r >> c;
int ret_1 = lower_bound(pos[c].begin(), pos[c].end(), l) - pos[c].begin();
int ret_2 = upper_bound(pos[c].begin(), pos[c].end(), r) - pos[c].begin() - 1;
if (ret_1 > ret_2) cout << 0 << endl;
else cout << ret_2 - ret_1 + 1 << endl;
}
}
return 0;
}
T3 [Daimayuan] 添加括號（C++，數學）
現在給出一個運算式，形如 \(a_1/a_2/a_3/.../a_n\)，
如果直接計算，就是一個個除過去，比如 \(1/2/1/4=1/8\)，
然而小 \(A\) 看到一個分數感覺很不舒服，希望通過添加一些括號使其變成一個整數，一種可行的辦法是 \((1/2)/(1/4)=2\)，
現在給出這個運算式，求問是否可以通過添加一些括號改變運算順序使其成為一個整數，
輸入格式
一個測驗點中會有多個運算式，
第一行 \(t\) ，表示運算式數量，
對于每個運算式，第一行是 \(n\)，第二行 \(n\) 個數，第 \(i\) 個數表示 \(a_i\)
輸出格式
輸出 \(t\) 行，
對于每個運算式，如果可以通過添加括號改變順序使其變成整數，那么輸出 \(Yes\)，否則輸出 \(No\)，
資料范圍
\(2≤n≤10000\),\(1≤t≤100\),\(1≤a_i≤2^{31}?1\)
輸入樣例
2
4
1 2 1 4
5
6 5 7 9 12
輸出樣例
Yes
No
解題思路
通過不同的加括號方法，可以發現以下幾個規律：
（1）第一個數必定是分子；
（2）第二個數必然是分母；
（3）從第三個數開始，任意數都可以成為分子，且互不影響，
同時，很容易知道：分子越多，分母越少，越容易形成整數，
那么我們的演算法實作就很簡單了：用其他所有數的乘積去嘗試整除第二個數，
最后，AC代碼如下：
#include <iostream>
using namespace std;
int main() {
int t, n;
long long a1, a2, sum;
bool flag;
cin >> t;
for (int i = 0; i < t; i++) {
cin >> n;
a1 = a2 = -1;
sum = 1;
flag = false;
for (int i = 0; i < n; i++) {
if (i == 1) {
cin >> a2;
}
else {
cin >> a1;
sum *= a1;
}
if (a2 != -1) {
sum %= a2;
if (sum == 0) {
flag = true;
}
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
T4 [Daimayuan] 貪就是了（C++，BFS）
題目描述
給你一個序列 \(a\)，我們定義
\(S_{(l,r)}=∑_{i=l}^{i=r}{a_i}\)
顯然易見我們會有\(n?(n+1)/2\)個不同的\(S_{(l,r)}\)，請你輸出其中前 \(k\)大的\(S_{(l,r)}\)
輸入描述
第一行輸入兩個整數 \(n,k\) 第二行輸入 \(n\)個整數代表序列 \(a\)
輸出描述
輸出一行包含 \(k\)個整數代表答案
樣例輸入1
6 8
1 1 4 5 1 4
樣例輸出1
16 15 14 12 11 11 10 10
樣例輸入2
7 8
1 9 1 9 8 1 0
樣例輸出2
29 29 28 28 28 27 20 19
資料范圍
\(0≤a_i≤10^9,1≤n≤10^5,1≤k≤min(10^5,n?(n+1)/2)\)
解題思路
根據題目，好像應該采用貪心演算法，所以我們先來嘗試一下，
對于序列1 2 100 3 100 4 5 6，我們嘗試找出最大的\(k\)個數：
第一大的是\(sum=221\)毫無疑問；
第二大的是\(sum-1=220\)；
第三大的是\(sum-1-2=218\)；
第四大的是\(sum-6=215\)，它并沒有在第三大的基礎上繼續更新；
第五大的是\(sum-1-2-6=212\)，它并沒有再次減去新的元素；
模擬到這里我們應該發現了，并沒有貪心演算法可以采用，我們只能搜索每一種可能的情況，然后找出top_k，
這里采用bfs的演算法：
void bfs() {
//初始化
while () {//終止條件
//bfs主體
}
}
然后我們來實作具體的bfs代碼，
首先明確bfs的功能是搜索并輸出top_k：
void bfs(int k) {
//初始化
while (k--) {//終止條件
//bfs主體
}
}
嘗試每一種可能的情況，實際上就是嘗試每一個區間\([l,r]\)，
為了快速找出top_k，我們采用優先佇列維護已搜索到的結果，
我們將區間\([l,r]\)加和用作比較的鍵值key，
priority_queue<pair<pair<int, int>, int>>pq;//默認大根堆
void bfs(int k) {
//初始化
pq.push({{ arr[n],1 },n })
int sum, l, r;
while (k--) {//終止條件
//bfs主體
sum = pq.top().first.first;
l = pq.top().first.second;
r = pq.top().second;
pq.pop();
cout << sum << ' ';
...
}
}
最后是最重要的部分，每一步需要做什么：
1）嘗試區間\([l+1,r]\)；
2）嘗試區間\([l,r-1]\)，
priority_queue<pair<pair<int, int>, int>>pq;//默認大根堆
void bfs(int k) {
//初始化
pq.push({{ arr[n],1 },n })
int sum, l, r;
while (k--) {//終止條件
//bfs主體
sum = pq.top().first.first;
l = pq.top().first.second;
r = pq.top().second;
pq.pop();
cout << sum << ' ';
pq.push({{ arr[r]-arr[l],l+1 },r });
pq.push({{ arr[r-1]-arr[l-1],l },r-1 });
}
}
但是這樣會產生對同一區間的重復搜索，所以我們加上一個去重判斷，
priority_queue<pair<pair<int, int>, int>>pq;//默認大根堆
void bfs(int k) {
//初始化
pq.push({{ arr[n],1 },n })
int sum, l, r;
while (k--) {//終止條件
//bfs主體
sum = pq.top().first.first;
l = pq.top().first.second;
r = pq.top().second;
pq.pop();
cout << sum << ' ';
pq.push({{ arr[r]-arr[l],l+1 },r });
if (l == 1) pq.push({{ arr[r-1]-arr[l-1],l },r-1 });
}
}
最后，AC代碼如下：
#include <iostream>
#include <queue>
using namespace std;
const int max_n = 1e5;
priority_queue<pair<pair<long long, int>, int>>pq;//默認大根堆
long long arr[max_n + 1], n;
void bfs(int k) {
//初始化
pq.push({ { arr[n],1 },n });
long long sum, l, r;
while (k--) {//終止條件
//bfs主體
sum = pq.top().first.first;
l = pq.top().first.second;
r = pq.top().second;
pq.pop();
cout << sum << ' ';
pq.push({ { arr[r] - arr[l],l + 1 },r });
if (l == 1) pq.push({ { arr[r - 1] - arr[l - 1],l },r - 1 });
}
}
int main() {
int k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
arr[i] += arr[i - 1];
}
bfs(k);
return 0;
}
可能會有人對為什么能直接輸出pq.top().first.first以及if (l == 1)有疑問，所以在最后的最后做一下解釋：
在每一輪bfs，我們首先取出隊首，然后在此基礎上嘗試兩種不同的縮短區間方法，
區間縮短，所以新的結果一定小于隊首，可以保證直接輸出的結果是我們想要的結果，
但是新的結果仍然可能大于其他舊的結果，所以我們簡單的采用if (l == 1)的去重方式是否過于草率？
試著假設我們沒有嘗試的區間\([l,r-1]\)之和大于其他舊的結果，
我們已知兩個條件：1）這個區間會被重復搜索；2）新的結果一定小于隊首，
很容易推出已知條件與假設矛盾，所以沒有被嘗試的區間不會對結果正確性產生影響，
T5 [Daimayuan] 算的我頭都大啦（C++，數學）
愛數學的小明又回來辣！看了上次大家解決問題的方法后覺得自己實在是太笨了，同時引來了同是數學愛好者的小紅的嘲笑，自尊心極強的小明氣不過，便和小紅打個賭，讓小紅出一道數學題給小明寫，如果小明能在一周內寫出來，小紅就請他吃下個星期的瘋狂星期四，如果做不出來就要小明請她瘋狂星期四，
但是這道題實在是太難啦，小明把自己關在房間里想了一周也沒能想出來，明天就是賭約的截止日期了，小明非常想吃KFC，于是他想到了再次向你求助，并承諾只要幫他寫出這道題就把小紅請的KFC分你一半，
小紅設立了兩個函式 \(f(x)\)和\(g(x,m)\) ,\(f(x)\)的定義如下：
\(f(x)=∏_{i=1}^{x的位數}{(x\ mod\ 10^i)}\ mod\ (x+1)\)
比如：\(f(2013)=(2013?13?13?3)\ mod\ 2014\)
\(g(x,m)\)的定義如下：
\[g(x,m)= \begin{cases} f(g(x,m-1)),\quad m>1 \\[1ex] f(x), \quad m=1 \end{cases} \]比如\(g(x,2)=f(f(x))\) 現在，要你求出 \(∑^m_{i=1}{g(x,i)}\)的值，
為了KFC，拼了！
輸入格式
第一行有一個數\(T\) (\(1≤T≤20\))，代表一共有\(T\)組資料， 接下來\(T\)行有兩個數\(x,m\)(\(1≤x,m≤10^9\)),代表\(g(x,m)\)的兩個引數
輸出格式
對于每行測驗例輸出一個數字，
樣例輸入
2
3 4
4102 642
樣例輸出
12
21262
解題思路
把題中所述的函式實作出來，直接模擬程序即可，
AC代碼如下：
#include <iostream>
using namespace std;
long long f(long long x) {
long long sum = 1, t = 1;
do {
t *= 10;
sum = (sum * (x % t)) % (x + 1);
} while (x % t != x);
return sum;
}
long long g(long long x, long long m) {
if (m > 1) return f(g(x, m - 1));
else return f(x);
}
int main() {
long long t, x, m, sum, last;
cin >> t;
while (t--) {
cin >> x >> m;
sum = 0; last = x;
for (int i = 1; i <= m; i++) {
last = f(last);//唯一一個需要優化的地方，快取上次計算結果，防止重復計算
sum += last;
}
cout << sum << endl;
}
return 0;
}
T6 [Daimayuan] 全部相等（C++，數學）
* 注：題名的靈感來自 代碼源 #914: 一半相等
給定長度為 \(n\) 的陣列 \({A}\)，
派派非常喜歡 所有元素出現頻率相同 的陣列，但這樣的陣列卻不常有，派派很傷心 (;′??Д??`)，不過聰明的你，發現總能從 \({A}\) 中挑選一個子序列滿足上述條件，問此子序列最長為多長？
資料規模
- \(1≤n≤2×10^5\)
- \(A_i∈[1,10^9]\)
輸入格式
輸入包含兩行，第一行有一個整數 \(n\)，表示 \({A}\) 的大小，
接下來一行包含 \(n\) 個用空格分隔的整數，依次表示 \(A_1,A_2,?,A_n\)，
輸出格式
輸出答案，
樣例 1 輸入
6
1 3 2 1 4 2
樣例 1 輸出
4
解釋：
[1,3,2,1,4,2] 滿足條件且最長，
樣例 2 輸入
4
100 100 4 100
樣例 2 輸出
3
樣例 3 輸入
8
1 2 3 3 3 2 6 6
樣例 3 輸出
6
解題思路
根據題意，我們有這樣一種直覺：
所選擇的公共詞頻過低的時候，會有很多元素，但是每個元素出現的次數很少；
所選擇的公共詞頻過高的時候，會有很少的元素，但是每個元素出現的次數很多，
類似于下面這個簡單的函式：
\[y=-x^2 \]所以我們知道答案在區間的中間位置，但是應該如何搜索？
因為答案不具有單調性，所以不能二分搜索，
所以我們直接放棄思考開始爆搜，
在統計詞頻程序中，由于取值范圍過大，使用map容器進行離散化，
然后將資料轉移到vector容器中進行排序，方便后續操作，
最后是本題的關鍵，搜索代碼部分：
while (temp_freq) {
while (iter != arr.end() && temp_freq <= iter->first) {
cnt++;
iter++;
}
ans = max(ans, temp_freq * cnt);//每次統計結束后更新答案（ans=所選詞頻*元素數量）
temp_freq--;
}
對于每一個鍵值對，我們以詞頻作為鍵值，然后根據鍵值降序排序，
從高頻開始嘗試，這樣可以不斷拓展元素的數量，而不是每次都要重新計算，
AC代碼如下：
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
const int max_n = 2e5;
const int max_a = 1e9;
int n;
map<int, int>freq;
vector<pair<int, int>>arr;
int main() {
cin >> n;
int temp;
for (int i = 0; i < n; i++) {
cin >> temp;
freq[temp]++;
}
for (auto iter : freq) arr.push_back({iter.second,iter.first});
sort(arr.begin(), arr.end(), [](pair<int, int>p1, pair<int, int>p2) {
return p1.first > p2.first;
});
int temp_freq = arr.begin()->first, cnt = 0;
int ans = 0;
vector<pair<int, int>>::iterator iter = arr.begin();
while (temp_freq) {
while (iter != arr.end() && temp_freq <= iter->first) {
cnt++;
iter++;
}
ans = max(ans, temp_freq * cnt);
temp_freq--;
}
cout << ans << endl;
return 0;
}
T7 [Daimayuan] 分段求和（C++，二分）
對于給定的一個長度為 \(N\) 的正整數數列 \(A_{1?N}\)，現要將其分成 \(M(M≤N)\) 段，并要求每段連續，且每段和的最大值最小，
關于最大值最小：
例如一數列 \(4,2,4,5,1\) 要分成 \(3\) 段，
將其如下分段：\([4,2][4,5][1]\)， 第一段和為 \(6\)，第 \(2\) 段和為 \(9\)，第 \(3\) 段和為 \(1\)，和最大值為 \(9\)，
將其如下分段：\([4][2,4][5,1]\)，第一段和為 \(4\)，第 \(2\) 段和為 \(6\)，第 \(3\) 段和為 \(6\)，和最大值為 \(6\)，
并且無論如何分段，最大值不會小于 \(6\)，
所以可以得到要將數列 \(4,2,4,5,1\) 要分成 \(3\) 段，每段和的最大值最小為 \(6\)，
輸入格式
第 \(1\) 行包含兩個正整數 \(N,M\)，
第 \(2\) 行包含 \(N\) 個空格隔開的非負整數 \(A_i\)，含義如題目所述，
資料范圍
\(1≤N≤10^5,M≤N,A_i≤10^8\)
輸出格式
一個正整數，即每段和最大值最小為多少，
輸入樣例
5 3
4 2 4 5 1
輸出樣例
6
解題思路
沒有一套標準的演算法用于此題，只能進行搜索，
暴力搜索直接\(T\)飛，考慮到題中要求是最小的最大值，所以采用二分搜索法，
二分答案：限制分段和的最大值越小，分段越多；反之，分段越少，
判斷函式如下：
bool judge(long long x) {
int l = 0, cnt = 0;
for (int r = 1; r <= n; r++) {
if (arr[r] - arr[l] > x) {
l = r - 1;
cnt++;
}
}
return ++cnt <= m;//分段數越多，越容易符合題中要求的分段數
}
不斷拓展區間，區間和小于上限則繼續，大于上限則累計分段數，然后進行下個區間的計算，
二分主體如下：
long long bin_search() {
long long l = max_num - 1, r = arr[n] + 1, mid;
while (l + 1 != r) {
mid = l + r >> 1;
if (judge(mid)) r = mid;
else l = mid;
}
return r;//符合題意的最小限制值
}
通過l = nax_num - 1來限制每段中至少含有一個元素，\([0,l]\)是不符合題意的限制值，\([r,arr[n]]\)是符合題意的限制值，
最后，AC代碼如下：
#include <iostream>
using namespace std;
const int max_n = 1e5;
const int max_a = 1e8;
const int max_m = max_n;
long long arr[max_n + 1], max_num = 0;
int n, m;
bool judge(long long x) {
int l = 0, cnt = 0;
for (int r = 1; r <= n; r++) {
if (arr[r] - arr[l] > x) {
l = r - 1;
cnt++;
}
}
return ++cnt <= m;
}
long long bin_search() {
long long l = max_num - 1, r = arr[n] + 1, mid;
while (l + 1 != r) {
mid = l + r >> 1;
if (judge(mid)) r = mid;
else l = mid;
}
return r;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
max_num = max(max_num, arr[i]);
arr[i] += arr[i - 1];//陣列前綴和
}
cout << bin_search() << endl;
return 0;
}
T8 [Daimayuan] nice party（C++，二分，貪心）
cc準備舉辦一場派對，他希望邀請他的朋友們過來參加，并且每個人都能玩得開心
cc有 \(n\) 位朋友，第 \(i\) 位的身價為 \(i\)
如果第 \(i\) 位朋友參加派對，并且玩得開心，當且僅當派對上至多有 \(X_i\) 個人比他身價嚴格大于他，至多有 \(Y_i\) 個人身價嚴格小于他
cc想知道，他最多能邀請來多少人，并且他們每個人都玩得開心
輸入描述
第 \(1\) 行給出一個數 \(T\) ，表示有 \(T\)，(\(1≤T≤10^4\)) 組資料
對于每一組資料
第 \(1\) 行給出一個數 \(n\)，(\(1≤∑n≤2×10^5\))，表示有 \(n\) 個朋友
接下來 \(n\) 行，每一行給出兩個數 \(X_i\)，\(Y_i\)，(\(0≤X_i,Y_i<n\))
輸出描述
輸出一個數，表示cc所能邀請的最多的人的人數
樣例輸入
3
3
1 2
2 1
1 1
2
0 0
0 1
2
1 0
0 1
樣例輸出
2
1
2
解題思路
根據題意，我們有這樣一種直覺：
所想邀請的人數越多，越不容易成功；
所想邀請的人數越少，越容易成功，
所以我們采用二分搜索：
int bin_search() {
int l = 0, r = n + 1, mid;
while (l + 1 != r) {
mid = l + r >> 1;
if (judge(mid)) l = mid;
else r = mid;
}
return l;
}
但是如何judge(mid)是否符合題意呢？
考慮一種通常的情況：
我們遍歷每一個人，現在遍歷到第i個，
對于他，我們已知其前面已選擇了cnt個人，
1）如果這個人不能來參加聚會，那么就簡單跳過即可；
2）如果這個人能夠參加聚會，且mid是符合題意的，那么在其之后至少還會再選擇mid-cnt-1個人，
bool judge(int x) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (cnt <= ys[i] && x - cnt - 1 <= xs[i]) cnt++;
}
return x <= cnt;
}
然后我們來解決兩個可能存在的疑問：
1）按照如上的統計方式，我們最后得到的cnt可能大于x，這會導致之前判斷條件mid-cnt-1失去意義，
這個問題對結果沒有影響，把多余的人刪去就可以了，
2）按照如上的貪心演算法，我們的統計結果不一定是最大的cnt，因為可能前面選擇的人數過多，導致更多的人不再符合條件cnt <= ys[i]，
進行貪心證明：
假設存在組合，使得在不選前面cnt個人的情況下，所選的人數能夠變為cnt+k，
那么根據已知條件，我們選擇cnt+k個人中靠前的cnt個人，顯然把他們替換為之前的cnt個人后仍然能夠符合題意，
所以假設不成立，
最后，AC代碼如下：
#include <iostream>
using namespace std;
const int max_n = 2e5;
int xs[max_n + 1], ys[max_n + 1];
int n;
bool judge(int x) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (cnt <= ys[i] && x - cnt - 1 <= xs[i]) cnt++;
}
return x <= cnt;
}
int bin_search() {
int l = 0, r = n + 1, mid;
while (l + 1 != r) {
mid = l + r >> 1;
if (judge(mid)) l = mid;
else r = mid;
}
return l;
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> xs[i] >> ys[i];
cout << bin_search() << endl;
}
return 0;
}
T9 [Daimayuan] Gene（C++，字串）
題目描述
高中生物中提到，酶切位點 是基因序列上一段特定的堿基序列，而 限制性核酸內切酶 能夠識別出這個序列并在對應的切割位置將基因序列切成兩段，
現有一種名為 \(EcoRI\) 的限制酶，其識別序列為 GAATTC，切割位置在 G 和 A 之間，（本題只考慮 5'->3' 單鏈）
給出一段長度為 \(n\) 的基因序列（僅由 A/T/G/C 組成的字串），請你判斷使用 \(EcoRI\) 在理想條件下能將此序列切成幾個部分，并輸出每個切割位置 左側 堿基的下標，
定義該基因序列的下標從左到右分別為 \(1,2,3,…,n\)，
輸入格式
第 \(1\) 行一個正整數 \(n\) 表示基因序列長度，
第 \(2\) 行一個長度為 \(n\) 的字串表示基因序列，保證只出現 A/T/G/C 四種字符，
輸出格式
第 \(1\) 行輸出一個正整數 \(x\)，表示 \(EcoRI\) 在理想條件下能將給出序列切成 \(x\) 個部分，
第 \(2\) 行從小到大輸出 \(x?1\) 個正整數，表示每個切割位置 左側 堿基的下標，
樣例輸入
15
GATCGGAATTCTTCA
樣例輸出
2
6
樣例說明
顯然，對于此樣例，容易找到 \(EcoRI\) 的識別序列和切割位點：\(GATCGG↓AATTCTTCA\)，
所以，可以將原基因序列切割成 \(2\) 部分，切割位置左側堿基 G 的下標為 \(6\)，
資料范圍
\(6≤n≤10^7\)
解題思路
利用string提供的find方法匹配GAATTC字串；
利用vector存盤答案并統計數量，
最后，AC代碼如下：
#include <iostream>
#include <vector>
using namespace std;
vector<int>ans;
int main() {
int n;
string str;
cin >> n >> str;
string target = "GAATTC";
int ret = 0;
while (true) {
ret = str.find(target, ret);
if (ret != -1) ans.push_back(ret++);
else break;
}
cout << ans.size() + 1 << endl;
for (auto iter : ans) {
cout << iter + 1 << ' ';
}
return 0;
}
T10 [Daimayuan] 贏救瓜瓜（C++，字串哈希）
題目描述
瓜瓜特工接到了一個新任務——保護CB直到畢業， 于是瓜瓜就裝作實驗室的集訓隊員潛伏在集訓隊，同時暗中保護CB的安全，并裝弱讓CB不要對ACM喪失信心， 某天早上，瓜瓜發現CB不在實驗室，便打了個電話， 電話接通了，但是電話那頭傳來了陌生男人的聲音， “CB現在在我們手上，嘿嘿嘿♂ ……”，電話那頭說完這句話就掛斷了， “CB！！！”瓜瓜大喊， 冷靜下來的瓜瓜，發現了 CB 留下的紙條，上面的答案就是 CB 所在位置（聰明的 CB 自然不可能白白被抓走）， rbq("wobeihuairenzhuazoulewwwkuailaijiuwoguagua") 這個rbq(string) 之前跟瓜瓜講過 LSP 庫里的一個函式，
這個函式的引數是一個字串，回傳的是 string中子串的最大回圈次數，
CB 為了不讓壞人發現，把這個字串用很多無用的字符填充了起來，但是字串太長了，瓜瓜根本無法肉眼看出來，
于是瓜瓜找到了你，希望你能寫個程式告訴他 CB 所在位置，
輸入描述
第一行包含一個整數 \(T\)，代表總共有 \(T(1≤T≤10^3)\)組字串，
接下來 \(T\)行，每行包含一個長度小于 \(5?10^3\)的字串，字串僅包含大小寫字母與數字，資料保證\(∑|string|≤5?10^3\)
輸出描述
每一組輸出一個整數，代表rbq(str)
樣例輸入
2
psdababab2345
avabcdad
樣例輸出
3
1
說明
rbq(psdababab2345)=3 因為子串 ababab有回圈節 ab，并且回圈了 3次，所以答案為 3，
rbq(avabcdad)=1, 因為任何一個子串都沒有回圈次數超過 1的回圈節，所以答案為 1，
解題思路
思路很容易想到：
三重回圈：1）嘗試每一種長度；2）嘗試每一個起始位置；3）回圈匹配，
for (int i = 1; i <= (len + 1 >> 1); i++) {
for (int j = 1; j <= len - i + 1; j++) {
/* 獲取子串 */;
int temp = 1, k = j + i;
while (k <= len - i + 1 && /* 回圈匹配 */) {
temp++;
k += i;
}
ans = max(ans, temp);
}
}
（沒錯就是這么簡單粗暴，沒有高級的演算法）
很明顯我們需要多次訪問字串，采用正常的方式會產生很大的開銷，所以我們采用字串哈希，
哈希演算法就是將一個元素用一個索引來表示，字串哈希也是如此，將每一個子串用一個索引表示，
這里推薦一篇博客，來自CSDN博主FoLiaGe丶：字串哈希【演算法】（絕對不是因為我懶得寫一遍）
AC代碼如下：
#include <iostream>
using namespace std;
const unsigned long long base = 13131;
const int max_len = 5e3;
unsigned long long arr[max_len + 1], power[max_len + 1];
unsigned long long get_hash(int l, int r) {
return arr[r] - arr[l - 1] * power[r - l + 1];
}
int main() {
power[0] = 1;
for (int i = 1; i <= max_len; i++) {
power[i] = power[i - 1] * base;
}
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
int len = str.size();
for (int i = 1; i <= len; i++) {
arr[i] = arr[i - 1] * base + (unsigned long long)(str[i - 1]);
}
int ans = 1;
for (int i = 1; i <= (len + 1 >> 1); i++) {
for (int j = 1; j <= len - i + 1; j++) {
unsigned long long hash = get_hash(j, j + i - 1);
int temp = 1, k = j + i;
while (k <= len - i + 1 && hash == get_hash(k, k + i - 1)) {
temp++;
k += i;
}
ans = max(ans, temp);
}
}
cout << ans << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/555356.html
標籤：其他
上一篇：STL-string(ACM)
下一篇：返回列表