2022湖南科技大學(xué) 新生快樂(lè)賽

按當(dāng)時(shí)的過(guò)題人數(shù)降序?qū)懸幌骂}解吧
新生可以根據(jù)一些不懂的地方學(xué)下一下
大佬自行繞路

(本題解都是用C++寫(xiě)的 ，由于 懶得寫(xiě)兩份 C++是競(jìng)賽常用語(yǔ)言，所以如果有看不懂的就去學(xué)一下C++的語(yǔ)法吧，反正以后用的著 )

tips: 要是有些題目感覺(jué)我說(shuō)的不清楚可以找一下 @ jeazim 的博客（你們的張志學(xué)長(zhǎng) 他還寫(xiě)了c版本的題解）

H 歡迎來(lái)到泰拉瑞亞，你準(zhǔn)備好了嗎？

題意：輸入一個(gè)字符串，判斷是否字符串中是否存在給定的字符串(不區(qū)分大小寫(xiě))

簽到題。直接模擬即可 可以二重循環(huán)一個(gè)個(gè)判斷

• 建議：由于不區(qū)分大小寫(xiě)，可以將所有字符都轉(zhuǎn)化為小寫(xiě)的

#include <bits/stdc++.h> using namespace std;int main(){int n;string s;string t = "terraria";cin >> n >> s;for (auto &x : s){x = tolower(x);}if(s.find(t)!=string::npos) cout <<"Yes\n";else cout <<"No\n";return 0; }

B 卷王日記

題意：輸入一個(gè)字符串 X則燈關(guān)上，Q則燈狀態(tài)改變
原來(lái)弄的題是可以3Q 也可以Q2Q這種，那就是直接模擬，后來(lái)改了只能3Q這種形式，那么X和Q一定是交叉出現(xiàn)的 所以只要分類討論一下最后面出現(xiàn)的字符就可以了 (這里有個(gè)疑惑，是否X至少會(huì)出現(xiàn)一次 從題面里的描述可以說(shuō)明是這樣的 故可以默認(rèn)燈至少會(huì)被關(guān)上一次)

#include <bits/stdc++.h> using namespace std;typedef long long ll;int main() {int n;string s;cin >> n >> s;if(s[n-1]=='Q'){if(s[n-2]=='X'||(s[n-2]-'0')&1 )cout << "yes\n";//若最后出現(xiàn)了奇數(shù)次Q else cout <<"no\n";}else cout <<"no\n";return 0; }

A 周小美大人是會(huì)長(zhǎng)

題目大意：n個(gè)字符任選兩個(gè)下標(biāo)為 i , j ，可以重復(fù)選 ，i,j中有任意一個(gè)不相等就算不同方案。求滿足s[i]==s[j]的方案數(shù)
思路： char類型ASCLL碼最多到128 直接開(kāi)個(gè)數(shù)組映射，記錄每個(gè)字符出現(xiàn)的次數(shù)

能記錄下來(lái)，就比較簡(jiǎn)單了 ，計(jì)算方法有很多種，我這份代碼可以理解為：
i和j相等的時(shí)候肯定是答案 +n
對(duì)于每個(gè)字符 s[i] ,在i之前出現(xiàn)的字符下標(biāo)都可以作為j
所以加上之前出現(xiàn)過(guò)的次數(shù) 由于是排列 所以i和j互換乘以2

#include <bits/stdc++.h> using namespace std;typedef long long ll;int cnt[129];int main() {ll n , res = 0;string s;cin >> n >> s;for (int i=0; i<n; ++i){res += cnt[s[i]]++;}cout << 2*res + n <<"\n";return 0; }

D: 心之鋼？心之鋼！

題意：技能對(duì)每個(gè)敵人的CD30s（獨(dú)立計(jì)算CD）,每次使用可以增加自身一定生命值
模擬即可 ，細(xì)節(jié)見(jiàn)代碼

#include <bits/stdc++.h> using namespace std;typedef long long ll;int main() {double a,b;int t , res = 0;cin >> a >> b >> t;a += 800;for (int i=1; i<=b; ++i){int x;cin >> x;if(x<=t){res += 1 + (t-x)/30;}}for (int i=1; i<=res; ++i){a = a + 12.5 + a*0.004;}printf("%d %.2f\n", res,a);return 0; }

C 卷王日記（二）

題意 給定一個(gè)地圖，求初始點(diǎn)到有效點(diǎn)的最短曼哈頓距離

（曼哈頓距離——兩點(diǎn)在南北方向上的距離加上在東西方向上的距離，即d(i,j)=|xi-xj|+|yi-yj|）

這題最開(kāi)始數(shù)據(jù)是1e4 時(shí)限1s 有點(diǎn)卡常 后面放開(kāi)了

分析：可以把中間的走廊也看成一列 然后走廊右邊的列坐標(biāo)都加一 那么你自己就也有一個(gè)坐標(biāo)啦！
大概長(zhǎng)這個(gè)樣子 =》畫(huà)了個(gè)什么破爛圖 看懂就行

這時(shí)候你只要遍歷所有點(diǎn)，然后記錄最小的曼哈頓距離就ok了
代碼：

#include <bits/stdc++.h> using namespace std;struct node {int cnt;int res; };int main() {ios::sync_with_stdio(false),cin.tie(nullptr);cout.tie(nullptr);int n,m;char ch;cin >> n >> m;int cnt = 0;int stx = 0,sty = m/2+1;//你自己站的位置node ans = {0,(int)1e9}; //初始化為無(wú)窮 表示沒(méi)有有效位置 for(int i=1; i<=n; ++i){for(int j=1; j<=m/2; ++j){cnt++;cin >> ch;if(ch=='F'){int t = abs(stx-i)+abs(sty-j);if(t<ans.res)ans = {cnt,t};}}for(int j=m/2+2; j<=m+1; ++j){cnt++;cin >> ch;if(ch =='F'){int t = abs(stx-i)+abs(sty-j);if(t<ans.res)ans = {cnt,t};}}}if(ans.res==1e9){cout <<"0 0\n";return 0;}cout << ans.res <<" " << ans.cnt <<"\n"; }

I 神，不懼死亡！

題目大意： 有一個(gè)數(shù)組 f[N]
f[1] = a ,f[2] = b,f[i] = f[i-1] + f[i-2] (i>=3)
當(dāng)前你有x個(gè)宇宙錠，你可以支付 T個(gè)(T<=x)宇宙錠來(lái)獲得 f[T] 的價(jià)值。
q個(gè)詢問(wèn)，告訴你當(dāng)前你有的宇宙錠的數(shù)量，問(wèn)獲得的價(jià)值的最大值。答案對(duì)998244353取模
場(chǎng)外看的時(shí)候一直不知道為啥這題沒(méi)人做？？ 后來(lái)想了一下，可能對(duì)取模這個(gè)概念還不是很了解？？或者還有一些我看了是忽略了 x等于2的時(shí)候可以支付一個(gè)也可以支付兩個(gè) 沒(méi)有比較a和b的大小。
本題要用到的公式：

(a + b) % p = (a % p + b % p) % p

以及，這個(gè)公式可以推廣到n個(gè)數(shù)字相加，只要每次都取個(gè)模就行了。
還有其他的取模公式自行百度，這里不介紹了。 思路和下一題差不多，打表預(yù)處理。

由于每個(gè)貢獻(xiàn)都是正的 故對(duì)所有大于等于3的都是嚴(yán)格單調(diào)遞增的，直接宇宙錠全給了就是答案，x等于2就是 max(a,b) .

#include <bits/stdc++.h> using namespace std;const int mod = 998244353; const int Maxn = 2000001;int v[Maxn];int main(){int q ,a,b;cin >> a >> b >> q;v[1] = a;v[2] = b;for (int i=3; i<Maxn; ++i)v[i] = (v[i-1] + v[i-2]) % mod;while (q--) {int x;cin >> x;if(x==2)cout << max(a,b) <<"\n";else cout << v[x] << "\n";}return 0; }

F 一起去旅行

題意：可以往前走x步，往后走y 步 (y<x) q個(gè)詢問(wèn)問(wèn)哪些位置可以走到

題意說(shuō)一開(kāi)始一定往前走x,而且每次后退了y以后，下一步一定是走x 。其實(shí)就是告訴我們y和x是綁定的，因?yàn)?strong>只要出現(xiàn)一次y，那么事先一定有一次x 。于是問(wèn)題可以轉(zhuǎn)化為：可以往前走a步或者b步 (b=x-y ,a = x , a>0 ,b >0 ，a>b).
我們可以發(fā)現(xiàn)能否到達(dá)X的充要條件是，到達(dá)X-a或者X-b 換句話說(shuō)，X的狀態(tài)取決于X-a和X-b的狀態(tài) 。那么X-a能不能到呢？ 似乎就取決于X-a-a和X-a-b？那么直接用一個(gè)dp數(shù)組存儲(chǔ)，dp為1表示可以到這個(gè)地方，dp為0表示不能 ，那么如何轉(zhuǎn)移呢？事實(shí)上，我們發(fā)現(xiàn)計(jì)算x所需要的狀態(tài)都是小于x的！也就是說(shuō)，每一個(gè)地方計(jì)算的狀態(tài)都可以由前面的一個(gè)或幾個(gè)狀態(tài)推出來(lái)。 故我們只要 for循環(huán)從小到大 順序計(jì)算所有需要的狀態(tài)即可。

即：

dp[i] = dp[i-x]||dp[i-x+y];

完整代碼：

#include <bits/stdc++.h> using namespace std; const int N = 1e7+50;int dp[N];signed main() {ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int n,x,y;cin >> n >> x >> y;dp[x] = 1;dp[x-y] = 1;for(int i=x+1; i<=1e7+1; ++i)dp[i] = dp[i-x]||dp[i-x+y];while(n--){int c;cin >> c;if(dp[c])cout <<"yes\n";else cout<<"no\n";}return 0; }

G 破碎的音符

感覺(jué)和某谷 合并果子有點(diǎn)類似，感興趣可以去某谷做一下 題號(hào) P1090
思路：
將拼圖分為 中間和左右 三部分
由題意可知 越先合并的 累加的次數(shù)越多
對(duì)答案的貢獻(xiàn)就越大 由于求最小答案
故每次貪心取最小的兩個(gè)合并即可
求最小的可以用優(yōu)先隊(duì)列，也可以暴力寫(xiě)

細(xì)節(jié)在代碼和注釋里了

#include <bits/stdc++.h> using namespace std;#define int long longvoid solve() {int n,l,r;cin >> n >> l;// 優(yōu)先隊(duì)列 原理是堆排序 可以logn時(shí)間取出堆中最小元素 logn時(shí)間插入元素// 沒(méi)了解的可以直接O(n)暴力 遍歷所有元素找最小 也能通過(guò)priority_queue<int, vector<int>, greater<int> > q;for (int i = 2; i < n; ++i) {//中間部分加入優(yōu)先隊(duì)列int x;cin >> x;q.push(x);//加入優(yōu)先隊(duì)列}cin >> r;int res = 0;if (q.size() == 0)res = l + r ;else {//每次貪心從三部分中選兩個(gè)元素合并//注意 中間部分元素可以多個(gè) 左右只有一個(gè)元素 模擬這個(gè)過(guò)程即可while (q.size()) {if (q.size() == 1) {if (l + q.top() < r + q.top()) {//判斷如何合并是最優(yōu)l += q.top();res += l;} else {r += q.top();res += r;}q.pop();}else {int a = q.top();q.pop();int b = q.top();q.pop();//避免分類討論，直接swap保證a<=bif (a > b)swap(a, b);if (a + b < a + l && a + b < a + r) {//判斷如何合并是最優(yōu)res += a + b;q.push(a + b);}else {if (l + a < r + a) {//判斷如何合并是最優(yōu)l += a;res += l;} else {r += a;res += r;}q.push(b);}}}res += l + r;//最后將所有部分合成一個(gè)}cout << res << "\n"; }signed main() {ios::sync_with_stdio(false), cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;while (t--) {solve();}return 0; }

I 神，不懼死亡！

防AK
其實(shí)是個(gè) 線性基純模板題。
原理我 也不會(huì) 就不說(shuō)了，網(wǎng)上可以找到各種題解 我就不當(dāng)小丑了

代碼：

#include <iostream> #include <algorithm> using namespace std;const int MAX = 1e5+5; typedef long long ll; ll arr[MAX]; ll p[MAX];void Get_LB(ll x){for(int i = 62; i >= 0; --i){if(!(x >> (ll)i))continue;if(!p[i]){p[i] = x;break;}x ^= p[i];} } int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int n; cin >> n;for(int i = 0; i < n; ++i){cin >> arr[i];Get_LB(arr[i]);}long long ans = 0;for(int i = 62; i >= 0; --i){if( (ans ^ p[i]) > ans)ans ^= p[i];}cout << ans << endl;return 0; }

J 旅行者的涂色游戲

防AK
進(jìn)階博弈論題
前置知識(shí)：SG函數(shù)、公平組合游戲、SG定理、必?cái)B(tài)和必勝態(tài)。
由于全部介紹篇幅較長(zhǎng)，有興趣的可以自行百度。

題意： 二人對(duì)弈，初始一個(gè)1×n的方格 可以涂紅色也可以涂藍(lán)色，但是相同顏色不能相鄰。 初始時(shí)有m個(gè)位置已經(jīng)涂上了顏色，數(shù)據(jù)保證初始位置不會(huì)出現(xiàn)相同顏色相鄰的問(wèn)題 。 輪流涂色，當(dāng)有一人無(wú)法繼續(xù)涂色時(shí)，游戲結(jié)束，無(wú)法涂色的人判負(fù)。 問(wèn)：在兩人都是最優(yōu)策略的情況下，誰(shuí)是勝者？

這是一個(gè)公平游戲，兩人的博弈目標(biāo)都是相同的，并且我們發(fā)現(xiàn)涂色部分可以把方格分割成若干段。那么每一段空白棋盤(pán)的sg函數(shù)的異或和是否為0可以 判斷先手是否必勝。

現(xiàn)在的問(wèn)題就是如何求每一段的SG函數(shù)：

我們發(fā)現(xiàn)可以為以下四種情況：
Case 1：
所有地方初始都沒(méi)有涂上顏色。
這時(shí)勝負(fù)取決于n的奇偶性，若n為奇數(shù)，先手可以對(duì)中間的方格涂色，此時(shí)棋盤(pán)分為兩個(gè)對(duì)稱的部分，接下來(lái)無(wú)論對(duì)方怎么涂色，我們都可以構(gòu)造出一個(gè)相同顏色對(duì)稱的局面。
如圖：第一次涂色在8這個(gè)位置 ，則對(duì)方無(wú)論涂在哪個(gè)位置，若對(duì)方合法，關(guān)于8這個(gè)點(diǎn)的對(duì)稱位置也合法，故最終一定是先手勝利。

反之，若n為偶數(shù)，則后手可以根據(jù)中間點(diǎn)來(lái)構(gòu)造一個(gè)相反顏色對(duì)稱的局面，最終一定是先手無(wú)法操作。

即：這種情況的SG函數(shù)為 n%2 ，而在本題中，若出現(xiàn)這種情況，則只劃分了一個(gè)區(qū)域，也就是只有一個(gè)SG函數(shù) 故n的奇偶直接決定最后的勝者。

Case 2：
一端涂上了顏色，而另外一端沒(méi)有

對(duì)于這種情況，顯然一端的顏色是紅是藍(lán)不會(huì)影響其結(jié)果，這里先給出結(jié)論：這種情況下的sg函數(shù)等于空白的長(zhǎng)度，因?yàn)橥茖?dǎo)這個(gè)結(jié)論需要結(jié)合Case 3和Case 4推導(dǎo)。

Case 3
兩端的被同一種顏色覆蓋

顯然兩端的方格是紅是藍(lán)我們也不需要考慮，我們直接假設(shè)都為紅色。此時(shí)顯然的條件是：當(dāng)長(zhǎng)度為奇數(shù)時(shí)候，先手一定可以構(gòu)造一個(gè)對(duì)稱局面(相當(dāng)于case1的奇數(shù)情況)，**我們?cè)谡虚g下一個(gè)棋，接下來(lái)就是模仿對(duì)手，顯然是必勝的，**其sg函數(shù)恒為1。但是對(duì)于偶數(shù)情況，我們還不得知。后續(xù)推導(dǎo)

Case 4
兩端的被不同種顏色覆蓋

不妨設(shè)兩端棋子一端是紅一端是藍(lán)，當(dāng)空白長(zhǎng)度為偶數(shù)的時(shí)候，后手可以構(gòu)造一個(gè)相反對(duì)稱棋盤(pán)類似Case1的后手對(duì)稱，其sg函數(shù)為0(相當(dāng)于case1的偶數(shù)情況)。但是對(duì)于奇數(shù)情況，我們也不得而知。

我們發(fā)現(xiàn)，這幾種還未推出來(lái)的情況本身也可以看做一個(gè)新的對(duì)弈。可以分成幾部分

對(duì)于Case 3長(zhǎng)度為偶數(shù)的情況，也就是兩端都是相同顏色，中間的長(zhǎng)度為偶數(shù)。我們可以在最左端(或者最右端)的隔開(kāi)一個(gè)格子的位置上涂上一個(gè)不同顏色，那么隔開(kāi)的這個(gè)位置不能填任何棋子了，而另一邊就形成了Case4的必?cái)B(tài)，那么Case3不管奇偶都是必勝態(tài)，其sg函數(shù)為1。

對(duì)于Case 4長(zhǎng)度為奇數(shù)的情況，也就是一端為紅一端為藍(lán)，此時(shí)先手不管怎么下這個(gè)棋，一定會(huì)產(chǎn)生兩端顏色一樣的必勝態(tài)，而另一端就還是不同顏色的局面，先手無(wú)論如何無(wú)法打破這個(gè)局面，直到左邊這段下不了。因此，Case 4永遠(yuǎn)是先手必?cái)?#xff0c;其sg函數(shù)為0。

我們現(xiàn)在還有Case 2的sg函數(shù)沒(méi)有分析，不管我們?cè)趺聪?#xff0c;一定會(huì)產(chǎn)生一端Case3或者Case4，然后和另一段Case 2繼續(xù)異或，那么對(duì)于一個(gè)長(zhǎng)度為n的空白段，可以轉(zhuǎn)移到0, 1, 2, 3, 4…n - 1，也就是說(shuō)其sg函數(shù)等于長(zhǎng)度n。

至此，我們只要把m個(gè)初始顏色劃分的段逐個(gè)求出對(duì)應(yīng)的SG函數(shù)，然后求他們的異或和即可。時(shí)間復(fù)雜度 O(m)

代碼:

#include <iostream> using namespace std;#define int long long #define endl "\n" const int N = 2e5+50;int n, m; int X[N], Y[N];signed main() {cin >> n >> m;for (int i = 1; i <= m; i++) {char ch;cin >> X[i] >> ch;if(ch=='R')Y[i] = 0;else Y[i] = 1;}X[0] = 0;Y[0] = 2;X[m + 1] = n + 1;Y[m + 1] = 2;if (m == 0) {if (n % 2 == 1) cout << "Aether" << "\n";else cout << "Lumine" << endl;return 0;}int res = 0;for (int i = 0; i <= m; i++) {if (Y[i] == 2 || Y[i + 1] == 2) res ^= (X[i + 1] - X[i] - 1);else if (Y[i] == Y[i + 1]) res ^= 1;else res ^= 0;}if (res == 0) cout << "Lumine" << endl;else cout << "Aether" << endl;return 0; }

希望這個(gè)題解能給到一定幫助，祝各位學(xué)弟新生賽取得好成績(jī)！！ 不要像我一樣太混了，當(dāng)時(shí)新生賽的時(shí)候甚至不知道ACM賽制是什么 （逃~

總結(jié)

以上是生活随笔為你收集整理的2022湖南科技大学 新生快乐赛 题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。