最後更新日期 2024 / 01 / 01
https://cses.fi/problemset/task/1069
你有一個由 A、C、G、T 組成的字串
目標是算出同樣的字母最多連續重複幾次
把整個字串從左邊往右掃
用一個
遇到一個字母時
如果跟上個字母不同就把
每次掃過一個字母再用
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
char chr, tmp = 'X';
int maxLen = 1, curLen = 1;
while (cin >> chr) {
if (tmp != 'X' && tmp == chr) {
curLen++;
} else {
curLen = 1;
}
maxLen = max(maxLen, curLen);
tmp = chr;
}
cout << maxLen << endl;
}
給你 n 位客人的進入和離開餐廳的時間 輸出最多同時有幾位客人同時在餐廳- n le 2 times 10^5把每個人加入時間和離開的時間分別看成兩個時間點 並把所有時間點加入陣列後一起排序 然後用一個變數來維護目前餐廳人數 每次遇到加入就增加 反之遇到離開就減少 維護中遇到的最大值就是答案了 時間複雜度：Oncpp using namespace std; signed main { int n; cin n; vectorpii v; for int i = 0; i n; i++ { int s, t; cin s t; v.pushback{s, true}; v.pushback{t, false}; } sortv.begin, v.end; int cur = 0; int ans = 0; for auto e : v { if e.ss == true cur++; else cur--; ans = maxcur, ans; } cout ans endl;}
CSESn 階乘求數字有幾個後綴 0不難發現 後綴幾個 0 就等於乘進去的 10 的個數 而 10 = 5 times 2 所以後綴 0 數量就相當於計算把每個數質因數分解後 5 和 2 的較少的那個的個數 那當然 5 一定會比 2 少 所以我們要做的是就是計算 5 的個數 那要如何計算呢？ 以 30 為例 我們知道要求得 30 階就是要把下面這些數字乘起來 不過我們可以先排除掉質因數分解後裡面沒有 5 的數字 然後把下面的數字都各取走一個質因數分解裡面的 5（相當於除與 5） 並把答案加上 6 因為下面有 6 個數字 變成這樣 可以看到下面的數字剛好就是 6 階乘的子問題 像剛剛的作法一樣 把跟 5 無關的數字排除並把它取走一個 5 的質因數 答案 += 1這樣就完成 30 階的計算了！ 根據上面的操作 可以推出下列遞迴式 fx = flfloor frac nx rfloor + lfloor frac nx rfloor不過寫成程式其實用 while 迴圈就可以了 cppusing namespace std;signed main { int n; cin n; if n % 2 { cout 0 endl; return 0; } int ans = 0; while n = 5 { n = 5; ans += n; } cout ans endl;}
CSES定義 sigmax 為 x 的所有因數之和 給予一個 n 求 sum^n{k=1}sigmak 之值以 12 為例 先看一下這張圖列出了 1 sim 12 的所有因數可以發現每兩個數字就會出現一次 2 每三次數字就會出現一次 3 觀察後可知 對於一個數字 x 它的出現次數會是 lfloor frac{n}{x} rfloor 因為每 x 個數字就會出現一個 x 的倍數 用這個做法枚舉每個數字計算就可以得到一個 On 的算法 但這樣還不夠快到足以處理這題 10^{12} 的資料量如果我們把剛剛那張圖的呈現方式改一下 上面那一橫排代表因數 1 sim 12 下面那一行排代表該因數出現的次數可以發現這張圖內有幾串連續的因數出現次數相同 因為事實上在計算這個的過程中只會出現最多 2 sqrt n 個相異數字 證明上面那張圖每個紅色圈起來代表一塊 如果我們可以塊為單位來計算就可以把時間複雜度降到 Osqrt{n} 了想像一下 如果 n 除以 x 可以剛好整除的話 令 k = lfloor frac{n}{x} rfloor 則 lfloor frac{n}{k} rfloor 必定等於 k 那如果不是剛好整除的呢？ lfloor frac{12}{5} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 再試試看 6 lfloor frac{12}{6} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 觀察後發現 這裡的 6 就是最大的 x 滿足 frac{n}{x} 為 2 於是這樣我們就可以找到最後一個連續出現次數相同的因數 最後只要把每次一塊的第一個數和最後一個數用梯形公式求總和乘上共同的出現次數就可以得到答案了不過這邊要注意的是 因為答案很大所以題目要我們對 10^9 + 7 取模 但梯形公式中又會用到除法 所以我們不能直接除 需要先求出模反元素.modulo-inverse再乘進去才行cppusing namespace std;const int mod = 1e9 + 7;const int inv = 500000004; signed main { int n; cin n; int cur = 1; int ans = 0; while cur = n { int cnt = n cur; int last = n cnt; int sum = last + cur % mod last - cur + 1 % mod % mod inv % mod; ans += sum % mod cnt % mod % mod; cur = last + 1; } cout ans % mod endl;}
CSES