網址：Contest Problem List (hdu.edu.cn)

1001	簽到題	對于文中的坑點，取模后不能為負數，導致遲遲未AC掉，簽到題WA掉3次， 浪費了多次罰時
1002	簽到題	一次遍歷貪心解決即可， 1A
1003	使用并查集解決歐拉路的問題	該問題可以轉換為歐拉路的問題，同時使用并查集將整個圖分為多個連通圖，判斷每個連通圖是否為歐拉路，若均為歐拉圖，則將每個圖的度數以及各個圖的聯通加和即可，其中單個點的連通圖未做單獨處理導致遲遲不能AC，最終WA掉5次
1004	貪心題（需要將多種情況枚舉清楚）	對于問題中的情況，需要對多種情況做出枚舉，第一次和第二次遍歷情況較為特殊，第三次即以后的情況一樣，對不同情況做出區分并加以判斷即可，比賽中WA掉3次
1005-1008	1005數學博弈題，1007好像是樹形DP	1005-1008比賽時讀過問題后放棄解決

?由于很久未做算法題以及未寫C++代碼，并且多次WA掉，導致思路極為混亂，代碼寫的極為丑陋。由于昨日參加了初賽一，今日狀態較昨日有所提升。繼昨日之后再次于簽到題WA掉3次，出師不利。AC三道， 罰時6次

1001

該題即為一個求2的n次方的問題，由于數字較大，使用快速冪取模即可，簽到。?

?AC代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll mod = 998244353;ll pow_(ll x, ll y, ll mod) {ll ans = 1;ll base = x % mod;while(y){if(y & 1 != 0)ans = ((ans%mod) * (base %mod))%mod;y = y >> 1;base = ((base%mod) * (base % mod) )%mod;}return ans % mod; }int main() {int T;scanf("%d", &T);while(T--){ll a, b, k;scanf("%lld%lld%lld", &a, &b, &k);ll num = k / 2;ll add_ = k % 2;ll ansa = a;ll ansb = b;if(k > 0){ansa = ((a%mod) * (pow_(2, num, mod)%mod)) % mod;ansb = ((b%mod) * (pow_(2, num, mod)%mod)) % mod;}if(add_ == 0){cout << (ansa + mod)%mod << " " << (ansb + mod)%mod << endl;}else{cout << (ansa + ansb + mod)%mod << " " << (ansa - ansb + mod)%mod << endl;}}return 0; }

1002

?使用sort對數組進行一次排序，再使用一次遍歷按照最優的規則即可，簽到。

?AC代碼：

#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int T; int a[maxn];int main() {scanf("%d", &T);while(T--){int n, k;memset(a, 0, sizeof(a));scanf("%d%d", &n, &k);for(int i=0; i<n; i++){scanf("%d", &a[i]);}sort(a, a+n);int count_ = 0;int min_ = -1e9;for(int i=0; i<n; i++){int l = a[i] - k;int r = a[i] + k;if(min_ < l){min_ = l;count_++;}else if(min_ >= r){continue;}else if(min_ >= l && min_ < r){min_ += 1;count_ ++;}}printf("%d\n", count_);}return 0; }

1003

?將圖中的連通圖使用并查集進行分塊操作，判斷圖中結點個數大于2的連通圖的數量， 再進行判斷每個連通圖是否為歐拉圖，進行上述兩種操作后，對每個連通圖的路徑個數以及不同聯通圖的相加即獲得正確答案。

?AC代碼：

#include<bits/stdc++.h> using namespace std; const int maxn = 1005;int val[maxn][maxn]; char str[maxn]; int du[maxn]; int vis[maxn];int par[maxn]; //父親 int high[maxn]; //樹的高度void init(int n) {for(int i=0; i<n; i++){par[i] = i;high[i] = 0;} }int Find(int x) {return par[x] == x ? x : par[x] = Find(par[x]); }void unit(int x,int y) {x = Find(x);y = Find(y);if(x==y) return ;if(high[x]<high[y])par[x] = y;else{par[y] = x;if(high[x]==high[y])high[x] ++;} }int main() {int T;scanf("%d", &T);while(T--){int s, n;scanf("%d%d", &s, &n);n = n - 1;memset(val, 0, sizeof(val));memset(du, 0, sizeof(du));memset(vis, 0, sizeof(vis));init(s);for(int i=0; i<s - 1; i++){scanf("%s", str);int len = strlen(str);for(int j=0; j<len; j++){if(str[j] == '0'){val[i+1][j] = 1;val[j][i+1] = 1;}}} /*for(int i=0; i<s; i++){for(int j=0; j<s; j++){printf("%d ", val[i][j]);}printf("\n");} */for(int i=0; i<s; i++){int count_ = 0;for(int j=0; j<s; j++){if(val[i][j] == 1){count_++;unit(i, j);}}du[i] = count_;}int ANS = 0; //幾個連通塊for(int i=0; i<s; i++){vis[Find(i)]++;}for(int i=0; i<s; i++){if(vis[i] >= 2){ANS++;}} /*for(int i=0; i<s; i++){printf("%d ", vis[i]);}printf("\n");for(int i=0; i<s; i++){printf("%d ", du[i]);}printf("\n"); */int s_set = Find(n); //起點的連通集合if(vis[s_set] == 1){ANS++;}int s_du = du[n]; //起點的度int count_all = 0;int ans_all = 0;if(s_du % 2 == 1){for(int i=0; i<s; i++){if(du[i] % 2 == 1){if(Find(i) == s_set){ans_all += du[i];count_all++;if(count_all >= 3){ANS = -1;break;}}if(Find(i) != s_set){ANS = -1;break;}}else if(du[i] % 2 == 0){ans_all += du[i];}}}else{for(int i=0; i<s; i++){if(du[i] % 2 == 1){ANS = -1;break;}else if(du[i] % 2 == 0){ans_all += du[i];}}}if(ANS == -1)cout << ANS << endl;elsecout << (ANS - 1) * 2 + ans_all /2 << endl;}return 0; }

1004

?貪心算法，使用兩種不同的前綴和進行求和計算，計算第一輪遍歷后的最大值以及最終值。使用第二種前綴和的方法計算第二次遍歷后的最大值以及最終值。第三次及其以后的情況相同。最后分情況討論即可，比賽過程中WA掉3次，浪費大量時間。

AC代碼：?

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn = 100000 + 10;ll a[maxn]; ll sum[maxn]; ll all[maxn];int main() {int T;scanf("%d", &T);while(T--){ll n, m;ll max_ = 0, final_ = 0, sub_ = 0;ll max_all = -1e9 - 10;scanf("%lld%lld", &n, &m);memset(a, 0, sizeof(a));memset(sum, 0, sizeof(sum));memset(all, 0, sizeof(all));for(ll i=0; i<n; i++){scanf("%lld", &a[i]);}if(a[0] < 0){sum[0] = 0;}elsesum[0] = a[0];if(sum[0] > max_){max_ = sum[0];}all[0] = a[0];if(all[0] > max_all){max_all = all[0];}for(ll i=1; i<n; i++){all[i] = all[i-1] + a[i];if(all[i] > max_all){max_all = all[i];}if(all[i] < 0){if(all[i] * (-1) > sub_){sub_ = all[i] * (-1);}}sum[i] = sum[i-1] + a[i];if(sum[i] < 0)sum[i] = 0;if(sum[i] > max_){max_ = sum[i];}}final_ = sum[n-1]; /*//max_all 最大//max_ 最大// final_ 一輪終止// sub_ 回撤cout << max_all << endl;cout << max_ << endl;cout << final_ << endl;cout << sub_ << endl; */if(final_ == 0){if(max_ >= m){cout << "1" << endl;}else{cout << "-1" << endl;}}else if(final_ > 0){if(final_ > sub_){if(max_ >= m){cout << "1" << endl;}else{if(final_ + max_all >= m){cout << "2" << endl;}else{ll ans = 0;m = m - max_all;m = m - final_;ll num = m / (final_ - sub_);ll k =m % (final_ - sub_);ans = 2 + num;if(k > 0)ans++;cout << ans << endl;}}}else if(final_ <= sub_){if(max_ >= m){cout << "1" << endl;}else{if(final_ + max_all >= m){cout << "2" << endl;}else if(final_ + max_all < m){cout << "-1" << endl;}}}}}return 0; }/* 5 5 1 -3 3 2 -2 */

總結

以上是生活随笔為你收集整理的2021 年百度之星·程序设计大赛 - 初赛二的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。