2021百度之星初賽二（1001 – 1003）

1001
題意：
給 a,b，每次 a,b會(huì)變?yōu)?a+b,a-b，問(wèn) k 次之后變成了哪兩個(gè)數(shù)，對(duì) 998244353998244353 取模，多組數(shù)據(jù)。
題解：
首先觀察前幾次變化，
0 -------- a b 1 -------- a - b a + b
2 -------- 2a 2b 3 -------- 2a - 2b 2a + 2b
……
不難發(fā)現(xiàn)
對(duì)于k為偶數(shù)，答案是 a * pow(2,k/2) b * pow(2,k/2);
對(duì)于k為奇數(shù)，答案是 (a-b) * pow(2,(k-1)/2) (a+b) * pow(2,(k-1)/2);
ps:由于k可以達(dá)到1e9，因此使用快速冪。

#include <vector> #include <string> #include <cstdio> #include <cmath> #include <iostream> #include <algorithm> #include <stack> #include <cstring> #include <map> #define INF 0x3f3f3f3f #define ll long long const double pi = acos(-1.0); using namespace std; const ll mod = 998244353;ll qpow(ll a, ll b) {ll ans = 1;while (b) {if (b & 1) {ans = (ans * a) % mod;}b >>= 1;a = (a * a) % mod;}return ans; } int main() {int t; cin >> t;while (t--) {ll a, b, c, d;cin >> a >> b;c = (a + b) % mod;d = (a - b + mod) % mod;//這里的mod一定要加，像我不加卡半小時(shí)ll k; cin >> k;ll s = k / 2;ll e = k % 2;ll pre = qpow(2, s);ll ans1, ans2;if (e & 1) {ans1 = (c * pre) % mod;ans2 = (d * pre) % mod;}else {ans1 = (a * pre) % mod;ans2 = (b * pre) % mod;}cout << ans1 << " " << ans2 << endl;} }

1002
題意：

題解：
根據(jù)題意，可以發(fā)現(xiàn)a[n]的排列順序?qū)Υ鸢甘遣粫?huì)產(chǎn)生影響的
比如 a={ 2, 3 },k = 1, 那么一種構(gòu)造為b={1, 2},x=2;
現(xiàn)在改變a的順序?yàn)閧3,2}，那么相應(yīng)的b={2,1},x=2;
因此，不妨把a(bǔ)變?yōu)橐粋€(gè)升序序列，為了使b的數(shù)字種類夠多，可以在構(gòu)造b時(shí)，往小處取值，并保證數(shù)字種類的不同。這樣構(gòu)造出來(lái)的b也是一個(gè)升序序列。
這里可以使用map，用于表示對(duì)于某種數(shù)字，當(dāng)前可以使用的最小值。

#include <vector> #include <string> #include <cstdio> #include <cmath> #include <iostream> #include <algorithm> #include <stack> #include <map> #include <set> #define INF 0x3f3f3f3f #define ll long long const double pi = acos(-1.0); using namespace std; const ll mod = 998244353; ll a[100005]; map<ll, ll> pos; int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t; cin >> t;while (t--) {int n; cin >> n;ll k; cin >> k;pos.clear();for (int i = 0; i < n; i++) {cin >> a[i];pos[a[i]] = a[i] - k;//該數(shù)字初始可使用的最小值一定是 數(shù)字-k}ll ans = 0;sort(a, a + n);//a[0] = pos[a[0]];pos[a[0]]++;//第一位的最小值選定，可選最小值加1ans++;for (int i = 1; i < n; i++) {//如果當(dāng)前數(shù)字的可選最小值比上個(gè)數(shù)字小，表明當(dāng)前最小值不符合條件，必然和之前數(shù)字有重復(fù)//因此要進(jìn)行更新if (pos[a[i]] < pos[a[i - 1]])pos[a[i]] = pos[a[i - 1]];//在沒(méi)超過(guò)k的范圍內(nèi)，數(shù)字種類可增加，并更新可選最小值if (pos[a[i]] <= a[i] + k) {pos[a[i]]++;//a[i] = pos[a[i]] - 1;ans++; }else {//a[i] = pos[a[i]] - 1;}}cout << ans << "\n";} }

1003
題意：
給一張無(wú)向完全圖，每條邊有一個(gè)顏色，為黑色或者白色。你初始在點(diǎn) s 上，你每次可以從當(dāng)前的點(diǎn)經(jīng)過(guò)一條邊走到另一個(gè)點(diǎn)上，并將走過(guò)的邊的顏色翻轉(zhuǎn)。你想要把圖中所有的邊全都變?yōu)楹谏?#xff0c;要求最小化走過(guò)的邊的條數(shù)，求這個(gè)最小值，或者判斷無(wú)解。
題解：
首先，題中所給的圖是完全圖，則必然是簡(jiǎn)單圖，且每?jī)牲c(diǎn)之間都有邊相連。
要把所有白邊變?yōu)楹谶?#xff0c;白邊要經(jīng)過(guò)奇數(shù)次，黑邊變?yōu)楹谶?#xff0c;黑邊要經(jīng)過(guò)偶數(shù)次。為了使次數(shù)減少，那么原題可變?yōu)樗邪走叾冀?jīng)過(guò)1次并且借助最少的黑邊的方案。
我們可以先把所有白邊單獨(dú)構(gòu)圖，作為一個(gè)白邊子圖。這樣你會(huì)得到幾個(gè)僅有白邊的連通分量。為了使所有白邊能經(jīng)過(guò)，每?jī)蓚€(gè)連通分量間用黑邊連接。由于是完全圖，這樣的黑邊是必然存在的。
黑邊要經(jīng)過(guò)兩次，因此加入到白邊圖中就等價(jià)于一對(duì)白色重邊。
這樣其實(shí)就構(gòu)造好了一張連通的白邊子圖，這張子圖的總邊數(shù)就是我們要的答案。
但這個(gè)子圖不一定是能達(dá)到要求的。子圖所有邊都是要不重復(fù)經(jīng)過(guò)一次的，那就要用歐拉定理來(lái)判斷。
這里說(shuō)明一下，之前加黑邊的操作是為了更好理解。判斷是否為歐拉圖/半圖，初始的白邊圖就行。因?yàn)楹谶呏粫?huì)給節(jié)點(diǎn)的度數(shù)加2，這不影響節(jié)點(diǎn)的奇偶性。
如果這不是歐拉圖/半圖，可以判為不可行。如果是歐拉圖，那一定要判斷起點(diǎn)是否為孤立節(jié)點(diǎn)，如果孤立，則必須與白邊子圖間用黑邊連接。如果是歐拉半圖，要是起點(diǎn)的度數(shù)不是奇數(shù)，則判為不可行。
圖利用并查集儲(chǔ)存。

#include <vector> #include <string> #include <cstdio> #include <cmath> #include <iostream> #include <algorithm> #include <stack> #include <map> #include <set> #include <cstring> #define INF 0x3f3f3f3f #define ll long long const double pi = acos(-1.0); using namespace std; const ll mod = 998244353; int degree[1005]; //========================================== int net1[100010]; int afind1(int i) {if (net1[i] == i)return i;else return net1[i] = afind1(net1[i]); } void u1(int x, int y) {if (afind1(x) != afind1(y))net1[afind1(x)] = afind1(y);else return; } //============================================== int net2[100010]; int afind2(int i) {if (net2[i] == i)return i;else return net2[i] = afind2(net2[i]); } void u2(int x, int y) {if (afind2(x) != afind2(y))net2[afind2(x)] = afind2(y);else return; } //==============================================int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t; cin >> t;while (t--) {int n; cin >> n;int str; cin >> str;memset(degree, 0, sizeof degree);for (int i = 0; i <= n; i++) {net1[i] = net2[i] = i;}int whi = 0;for (int i = 2; i <= n; i++) {string a; cin >> a;for (int j = 0; j < a.length(); j++) {if (a[j] == '0') {u1(i, j + 1);//構(gòu)造白邊子圖。whi++;//白邊加1degree[i]++; degree[j + 1]++;//對(duì)應(yīng)節(jié)點(diǎn)度數(shù)加1}else {u2(i, j + 1);//構(gòu)造黑邊子圖，這個(gè)應(yīng)該不需要，請(qǐng)忽略。}}}bool f = 1; int jie = 0;for (int i = 1; i <= n; i++) {if (degree[i] & 1)jie++;}if (!(jie == 0 || jie == 2))f = 0;//判斷是否為歐拉圖/半圖if (f) {if (jie == 2) {if (!(degree[str] & 1))f = 0;//半圖且起點(diǎn)度數(shù)不為奇數(shù)，不可行}}//cout << degree[1] << degree[2] << endl;if (f) {bool che[1005] = { 0 };for (int i = 1; i <= n; i++) {if (degree[i])che[afind1(i)] = 1;//孤立節(jié)點(diǎn)不判斷為一個(gè)連通分量}int cnt = 0;for (int i = 1; i <= n; i++) {if (che[i])cnt++;//連通分量計(jì)數(shù)}if (degree[str] == 0)cnt++;//如果起點(diǎn)孤立，起點(diǎn)也作為一個(gè)連通分量//cout << whi << " :" << cnt << endl;if (whi)whi += 2 * (cnt - 1);//白邊數(shù)加所需的黑邊數(shù)的兩倍cout << whi << "\n";}else {cout << -1 << "\n";}}}

the end。

總結(jié)

以上是生活随笔為你收集整理的2021百度之星初赛二（1001 -- 1003）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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