比賽鏈接
A代碼#include using namespace std;using ll = long long;bool solve() { int n; cin >> n; int cnt = 0; for (int i = 1;i <= n;i++) { int a, b; cin >> a >> b; if (a > b) cnt++; } cout << cnt << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;}
B代碼#include using namespace std;using ll = long long;char dt[4][4];bool solve() { for (int i = 1;i <= 3;i++) for (int j = 1;j <= 3;j++) cin >> dt[i][j]; for (int i = 1;i <= 3;i++) { if (dt[i][1] == ".") continue; bool ok = 1; for (int j = 1;j <= 3;j++) ok &= dt[i][1] == dt[i][j]; if (ok) { cout << dt[i][1] << "\n"; return true; } } for (int j = 1;j <= 3;j++) { if (dt[1][j] == ".") continue; bool ok = 1; for (int i = 1;i <= 3;i++) ok &= dt[1][j] == dt[i][j]; if (ok) { cout << dt[1][j] << "\n"; return true; } } if (dt[1][1] != ".") { bool ok = 1; for (int i = 1;i <= 3;i++) ok &= dt[1][1] == dt[i][i]; if (ok) { cout << dt[1][1] << "\n"; return true; } } if (dt[1][3] != ".") { bool ok = 1; for (int i = 1;i <= 3;i++) ok &= dt[1][3] == dt[i][3 - i + 1]; if (ok) { cout << dt[1][3] << "\n"; return true; } } return false;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "DRAW" << "\n"; } return 0;}
C代碼#include using namespace std;using ll = long long;pair res[200007];bool solve() { int n, m, h; cin >> n >> m >> h; for (int i = 1;i <= n;i++) { priority_queue, greater> pq; for (int j = 1;j <= m;j++) { int x; cin >> x; pq.push(x); } int sum = 0; int point = 0; ll penalty = 0; while (pq.size()) { int t = pq.top(); pq.pop(); if (sum + t > h) break; sum += t; point++; penalty += sum; } res[i] = { point,penalty }; } auto tar = res[1]; auto cmp = [&](pair a, pair b) {return a.first == b.first ? a.secondb.first;}; sort(res + 1, res + n + 1, cmp); int id = lower_bound(res + 1, res + n + 1, tar, cmp) - res; cout << id << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;}
D代碼#include using namespace std;using ll = long long;int y[200007] = { (int)2e9 };bool solve() { int n; double d, h; cin >> n >> d >> h; for (int i = 1;i <= n;i++) cin >> y[i]; sort(y + 1, y + n + 1, greater()); double ans = 0; for (int i = 1;i <= n;i++) { double delta = min(h, 0.0 + y[i - 1] - y[i]); ans += (2 - delta / h) * d * delta / 2; } cout << fixed << setprecision(6) << ans << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;}
E題意給定一個(gè) \(n\) ,問(wèn)是否存在 \(k \geq 2 ,s \geq 2\) ,使得 \(\displaystyle n = \sum_{i=0}^s k^i\) 。
題解方法一知識(shí)點(diǎn):數(shù)學(xué),枚舉。
(資料圖片僅供參考)
實(shí)際上,\(\displaystyle k^s < \sum_{i=0}^s k^i < (k+1)^{s}\) ,因此一定有 \(\displaystyle\left\lfloor \sqrt[s]{\sum_{i=0}^s k^i} \right\rfloor = k\) 。
因此,我們枚舉 \(s\) ,令 \(k = \left\lfloor \sqrt[s]{n} \right\rfloor\) ,然后驗(yàn)證這一對(duì) \(s,k\) 。若 \(n\) 可行,那么一定有 \(\displaystyle \sum_{i=0}^s k^i = n\) 。
其中開(kāi)根號(hào)用的是 pow
,這個(gè)函數(shù)精度很差,但是這里是沒(méi)有問(wèn)題的,因?yàn)樯舷陆缍茧x得很遠(yuǎn)。
時(shí)間復(fù)雜度 \(O(60)\)
空間復(fù)雜度 \(O(1)\)
方法二知識(shí)點(diǎn):數(shù)學(xué),二分,枚舉。
注意到, \(s\) 不會(huì)太大,最大只可能 \(60\) ,考慮枚舉 \(s\) 。
對(duì)于一個(gè) \(s\) ,由于 \(\displaystyle \sum_{i=0}^s k^i\) 是關(guān)于 \(k\) 單調(diào)的,我們可以二分 \(k\) ,找到使得 \(\displaystyle \sum_{i=0}^s k^i\) 小于等于 \(n\) 的最后一個(gè) \(k\) ,隨后驗(yàn)證這個(gè) \(k\) 是否是答案即可。
注意到, \(k\) 也不會(huì)超過(guò) \(10^9\) ,這個(gè)結(jié)論能降低常數(shù)。
時(shí)間復(fù)雜度 \(O(60 \times \log 10^9)\)
空間復(fù)雜度 \(O(1)\)
方法三知識(shí)點(diǎn):數(shù)學(xué),二分,枚舉。
對(duì)于 \(s \geq 3\) 的情況, \(k\) 不會(huì)超過(guò) \(10^6\) ,因此可以枚舉 \(k \leq 10^6\) ,對(duì)每個(gè) \(k\) 預(yù)處理出 \(s \in[3,60]\) 的所有答案。
對(duì)于 \(s = 2\) 的情況,和方法一一樣直接二分即可。
時(shí)間復(fù)雜度 \(\displaystyle O\left( \left(\sum_{k=2}^{10^6}\log_k 10^{18}\right) \cdot \log \left(\sum_{k=2}^{10^6}\log_k 10^{18}\right) + \log 10^9 \right)\)
空間復(fù)雜度 \(\displaystyle O\left(\sum_{k=2}^{10^6}\log_k 10^{18}\right)\)
代碼方法一#include using namespace std;using ll = long long;using i128 = __int128_t;i128 qpow(i128 a, ll k) { i128 ans = 1; while (k) { if (k & 1) ans *= a; k >>= 1; a *= a; } return ans;}bool solve() { ll n; cin >> n; for (int i = 2, k;(k = pow(n, 1.0 / i)) >= 2;i++) { i128 res = (1 - qpow(k, i + 1)) / (1 - k); if (res == n) { cout << "YES" << "\n"; return true; } } return false;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << "\n"; } return 0;}
方法二#include using namespace std;using ll = long long;const ll INF = 2e18;ll calc(int x, int s) { ll sum = 0; __int128_t mul = 1; for (int i = 0;i <= s;i++) { if (sum + mul > INF) return INF; sum += mul; mul *= x; } return sum;}bool solve() { ll n; cin >> n; for (int i = 2;i <= 60;i++) { int l = 2, r = 1e9; while (l <= r) { int mid = l + r >> 1; if (calc(mid, i) <= n) l = mid + 1; else r = mid - 1; } if (r >= 2 && calc(r, i) == n) { cout << "YES" << "\n"; return true; } } return false;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << "\n"; } return 0;}
方法三#include using namespace std;using ll = long long;const ll INF = 1e18;set st;void init() { for (int i = 2;i <= 1000000;i++) { ll sum = 1 + i + 1LL * i * i; while (1 + (__int128_t)sum * i <= INF) { sum = 1 + sum * i; st.insert(sum); } }}ll calc(int x) { return 1 + x + 1LL * x * x;}bool solve() { ll n; cin >> n; if (st.count(n)) { cout << "YES" << "\n"; return true; } int l = 2, r = 1e9; while (l <= r) { int mid = l + r >> 1; if (calc(mid) <= n) l = mid + 1; else r = mid - 1; } if (r >= 2 && calc(r) == n) { cout << "YES" << "\n"; return true; } return false;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; init(); while (t--) { if (!solve()) cout << "NO" << "\n"; } return 0;}
F題意房間里有 \(n\) 個(gè)物品,每個(gè)物品的種類(lèi)為 \(a_i\) 。這些物品中,有一個(gè)是模仿者偽裝的。
現(xiàn)在可以進(jìn)行一場(chǎng)最多 \(5\) 輪的實(shí)驗(yàn)去找出它,每一輪按順序發(fā)生如下事件:
記錄當(dāng)前房間內(nèi)的所有物品的種類(lèi)??芍赋鲆粋€(gè)物品確定是偽裝的,則試驗(yàn)結(jié)束。但這個(gè)操作只能執(zhí)行一次,若不確定,則要做下一步操作。選出一些物品移出房間(可以不選,但模仿者始終不會(huì)被移出房間)并離開(kāi)房間。隨后房間里的物品會(huì)被打亂,模仿者也可以轉(zhuǎn)換成別的物品(即使房間里不存在的物品)。進(jìn)入房間,繼續(xù)下一輪。模仿者可能不轉(zhuǎn)變,但最多保持兩輪是同一個(gè)類(lèi)型的物品。給出操作,找到模仿者。
題解知識(shí)點(diǎn):枚舉。
一開(kāi)始可以不移出物品,這樣若模仿者發(fā)生變化,則最多兩輪一定有一個(gè)類(lèi)型的物品多了一個(gè)。
移出除了多出來(lái)物品的類(lèi)型以外類(lèi)型的所有物品。
剩下的一定是包括模仿者的同一類(lèi)型的物品,再最多不超過(guò)一輪,一定會(huì)出現(xiàn)一個(gè)不同類(lèi)型的物品,就是模仿者。
時(shí)間復(fù)雜度 \(O(n)\)
空間復(fù)雜度 \(O(n)\)
代碼#include using namespace std;using ll = long long;int n;int a[207];int cnt1[10], cnt2[10];void query(const vector &del) { cout << "- " << del.size() << " "; for (auto x : del) cout << x << " "; cout << endl; n -= del.size(); for (int i = 1;i <= n;i++) cin >> a[i];}void answer(int x) { cout << "! " << x << endl;}bool solve() { for (int i = 1;i <= 9;i++) cnt1[i] = cnt2[i] = 0; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i], cnt1[a[i]]++; query({}); for (int i = 1;i <= n;i++) cnt2[a[i]]++; int type = 0; for (int i = 1;i <= 9;i++) { if (cnt1[i] < cnt2[i]) { type = i; break; } } if (!type) { for (int i = 1;i <= 9;i++) cnt2[i] = 0; query({}); for (int i = 1;i <= n;i++) cnt2[a[i]]++; for (int i = 1;i <= 9;i++) { if (cnt1[i] < cnt2[i]) { type = i; break; } } } vector del; for (int i = 1;i <= n;i++) if (a[i] != type) del.push_back(i); query(del); bool ok = 0; for (int i = 1;i <= n;i++) { if (a[i] != type) { answer(i); ok = 1; break; } } if (!ok) { query({}); for (int i = 1;i <= n;i++) { if (a[i] != type) { answer(i); ok = 1; break; } } } return true;}int main() { //std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;}
G題意有 \(n\) 種癥狀和 \(m\) 個(gè)藥品,癥狀的情況通過(guò)一個(gè)長(zhǎng)為 \(n\) 的 \(01\) 串給出。
每種藥品治療效果是可以使特定的一些癥狀消失,但副作用是使得特定的癥狀出現(xiàn)。
每種藥有一個(gè)療程 \(d\) ,療程之內(nèi)不允許使用其他藥。
現(xiàn)在給出初始癥狀情況,問(wèn)最少需要多少天才能使得癥狀全部消失。
題解知識(shí)點(diǎn):最短路,狀壓dp,拓?fù)湫騞p。
考慮狀壓,將癥狀壓縮為一個(gè)整數(shù)。
隨后,我們將 \(2^n\) 種癥狀情況看作點(diǎn), \(m\) 種藥看作邊。顯然,每個(gè)點(diǎn)都可以有 \(m\) 條出邊。
假設(shè)當(dāng)前的癥狀是 \(st\) ,將要使用的藥品的效果是 \(e\) ,副作用是 \(se\) ,那么使用后的癥狀為 (st & ~e) | se
,這樣就構(gòu)建了一條邊,權(quán)值為療程時(shí)間。
問(wèn)題就變成,從初始狀態(tài)到 \(0\) 狀態(tài)的最短路,直接跑最短路即可。
求最短路的本質(zhì)就是在最短路圖這個(gè)DAG上進(jìn)行拓?fù)湫騞p,因此一些dp可以考慮抽象成圖的形式跑最短路。
時(shí)間復(fù)雜度 \(O(m2^n \log (m2^n))\)
空間復(fù)雜度 \(O(2^n + m)\)
代碼#include using namespace std;using ll = long long;int n, m;int d[1007], e[1007], se[1007];bool vis[1 << 10 + 1];int dis[1 << 10 + 1];struct node { int v, w; friend bool operator<(const node &a, const node &b) { return a.w > b.w; }};priority_queue pq;void dijkstra(int st) { for (int i = 0;i < (1 << n);i++) dis[i] = 1e9, vis[i] = 0; dis[st] = 0; pq.push({ st,0 }); while (!pq.empty()) { int u = pq.top().v; pq.pop(); if (vis[u]) continue; vis[u] = 1; for (int i = 1;i <= m;i++) { int v = (u & ~e[i]) | se[i]; int w = d[i]; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pq.push({ v,dis[v] }); } } }}bool solve() { cin >> n >> m; int st = 0; for (int i = 0;i < n;i++) { char ch; cin >> ch; st |= (ch == "1") << i; } for (int i = 1;i <= m;i++) { cin >> d[i]; e[i] = 0, se[i] = 0; for (int j = 0;j < n;j++) { char ch; cin >> ch; e[i] |= (ch == "1") << j; } for (int j = 0;j < n;j++) { char ch; cin >> ch; se[i] |= (ch == "1") << j; } } dijkstra(st); cout << (dis[0] >= 1e9 ? -1 : dis[0]) << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;}
關(guān)鍵詞:
凡注有"環(huán)球傳媒網(wǎng)"或電頭為"環(huán)球傳媒網(wǎng)"的稿件,均為環(huán)球傳媒網(wǎng)獨(dú)家版權(quán)所有,未經(jīng)許可不得轉(zhuǎn)載或鏡像;授權(quán)轉(zhuǎn)載必須注明來(lái)源為"環(huán)球傳媒網(wǎng)",并保留"環(huán)球傳媒網(wǎng)"的電頭。
- iPhone13系列機(jī)型如何強(qiáng)制重啟?蘋(píng)果13怎么打開(kāi)手電筒?
- 【當(dāng)前熱聞】存款偏離度是什么意思?存款偏離度的影響因素是什么?
- 網(wǎng)頁(yè)自動(dòng)翻譯如何實(shí)現(xiàn)?網(wǎng)頁(yè)如何翻譯成中文? 世界時(shí)快訊
- 全球百事通!廣發(fā)證券開(kāi)戶傭金多少?廣發(fā)證券開(kāi)戶有什么風(fēng)險(xiǎn)?
- 什么是寬基指數(shù)?寬基指數(shù)代表性基金是什么?
- 榮耀平板分屏方法是什么? 榮耀怎么開(kāi)啟兩個(gè)系統(tǒng)?
- 關(guān)燈吃面什么意思?關(guān)燈吃面的典故說(shuō)的是哪只股票?
- 劉昊然私下是個(gè)什么樣的人?劉昊然為什么很少參加活動(dòng)?
- 蘋(píng)果手機(jī)熱點(diǎn)怎么一直開(kāi)著 ?iphone個(gè)人熱點(diǎn)老是自動(dòng)打開(kāi)怎么回事?
- 毛利潤(rùn)怎么算?純利潤(rùn)與毛利潤(rùn)的區(qū)別是什么 信息
資訊
- Codeforces Round #883 (Div. 3) A-G
- 隊(duì)報(bào):加拉塔薩雷將1000萬(wàn)歐簽下伊卡爾迪,正和巴黎談最終細(xì)節(jié)
- 阿膠膏怎樣制做(阿膠膏的做法簡(jiǎn)介介紹)
- 18k金回收多少錢(qián)一克 18k金是什么意思
- 張一山關(guān)曉彤范丞丞攜手話青春 電視劇《曾少年》定檔7月10日|天天頭條
- 塔瑞斯世界好玩嗎(塔瑞斯世界玩法介紹)
- 海底兩萬(wàn)里讀后感50字初中 海底兩萬(wàn)里讀后感50字
- 高溫橙色預(yù)警!了解這些知識(shí),夏夜睡個(gè)好覺(jué)
- 【詩(shī)詞鑒賞】炎炎盛夏,詩(shī)中納涼,十首納涼的詩(shī)詞,在炎夏里,尋一縷清涼!
- 上半年全國(guó)鐵路發(fā)送旅客17.7億人次!接近2019年同期水平
焦點(diǎn)
- 世界訊息:豬流感疫苗有必要接種嗎?豬流感疫苗后遺癥
- 銀耳湯怎么做才能補(bǔ)膠原蛋白?吃魚(yú)補(bǔ)膠原蛋白嗎?
- 世界消息!彈力素怎么用?彈力素的作用和功效
- 石板龜是不是草龜?石板龜壽命一般有多少年? 每日消息
- 天天速讀:民事案件審理期限最長(zhǎng)多久?民事案件追訴期多長(zhǎng)?
- 平安信用卡過(guò)期了里面還有欠款怎么辦?平安信用卡卡片過(guò)期了怎么辦? 環(huán)球熱資訊
- 信陽(yáng)中院開(kāi)展制止餐飲浪費(fèi)、培養(yǎng)節(jié)約習(xí)慣專(zhuān)項(xiàng)活動(dòng)-天天新消息
- 要聞:股票選購(gòu)技巧都有哪些技巧推薦?新手適合投資股票嗎?
- 環(huán)球看熱訊:助學(xué)貸款是每個(gè)月還是一年還一次?助學(xué)貸款按月還還是按年還啊?
- 熱門(mén):梅蘭竹菊指的哪四個(gè)人 梅蘭竹菊象征著什么人生追求?