【HDU 6014】

SOLVED

【題目大意】給定N個節點，兩點之間距離是節點編號的與，在這樣的前提下，求最小生成樹，輸出代價和路徑

【思路】通過lowbit求第一個0的位置，然后令此位為1的值就是最優解

【總結】1.與或非都要先考慮拆分后二進制的特性

? ? ? ? ? ? ? ?2.檢驗算法正確性時，驗證數據要是自己驗證能力的最大值

? ? ? ? ? ? ? （就是多驗）? ? ? ??

?

#include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<string> #include<cstring> #include<climits> #include<cmath> #include<map> #include<set> #include<deque> using namespace std; const int maxn = 2e5 + 10; int arr[maxn]; int lowbit(int x) {return x & -x; } int main() {ios_base::sync_with_stdio(false);int T;cin >> T;while (T--){int N;cin >> N;int cal = 0;for (int i = 2; i <= N; i++){if ((i & 1) == 0)arr[i] = 1;else{int t =lowbit((i + lowbit(i)));if (t <= N)arr[i] = t;else{arr[i] = 1;cal++;}}}cout << cal << "\n";for (int i = 2; i <= N; i++){cout << arr[i];if (i != N)cout << ' ';}cout << "\n";} } View Code

---

【HDU 6015】

UNSOLVED

?

---

【HDU 6016】

SOLVED

【題目大意】給數字N，要求將數字1~N分成k堆，每一堆的總和都相等，如果能則輸出“yes”，并輸出方案，如果不行輸出“no”

【解題思路】

分類討論

一種是n/k是偶數的，直接取頭取尾然后分配就行，

一種是奇數，取前3k個，然后對后面剩余的取頭取尾分配

?

（此處應有取前3k個可行的證明）

?

然后就是幾個特判（程序要優美就不應該有特判）

當k==1時，輸出全部

當1~N的總和不能整除k時，輸出no

當k==n時輸出no

?

?

#include<cstdio> #include<iostream> #include<vector> #define ll long long using namespace std; const int MAXN = 100010; vector<int> ans[MAXN]; ll n, k; void solve() {if ((n*(n + 1) / 2) % k != 0 || (k == n&&k!=1)){printf("no\n");return;}ll d = n / k;printf("yes\n");if (k == 1){for (int i = 1; i <= n; i++){printf("%d", i);if (i != n)printf(" ");elseprintf("\n");}return;}if (d & 1){ll sum =( (1 + 3*k)*3 / 2);//printf("sum == %lld \n", sum);for (int i = 1; i <= k; i++){ans[i].push_back(i);}int tot = k + 1;for (int i = k; i > 0; i -= 2){ans[i].push_back(tot), tot++;}for (int i = k - 1; i > 0; i -= 2){ans[i].push_back(tot), tot++;}for (int i = 1; i <= k; i++){ans[i].push_back(sum - ans[i][0] - ans[i][1]);}tot = 1;ll d = ((n-3*k) / k)/2;for (int i = 1; i <= k; i++){for (int j = 1; j <= d; j++)ans[i].push_back(3 * k + tot),ans[i].push_back(n + 1 - tot),tot++;}for (int i = 1; i <= k; i++){for (int j = 0; j < ans[i].size(); j++){printf("%d", ans[i][j]);if (j == ans[i].size() - 1)printf("\n");elseprintf(" ");}}for (int i = 1; i <= k; i++)ans[i].clear();}else{int cnt = 1;for (int i = 1; i <= k; i++){for (int j = 0; j <d/2; j++){printf("%d %d", cnt, n + 1 - cnt);if( j == (d / 2) - 1 )printf("\n");elseprintf(" ");cnt++;}}}return; } int main() {int T;scanf("%d", &T);while (T--){scanf("%lld%lld", &n,&k);solve();}return 0; } View Code

---

【HDU 6017】

UNSOLVED

?

---

【HDU 6018】

UNSOLVED

?

---

【HDU 6019】

UNSOLVED

?

?

---

【HDU 6020】

SOLVED

【題目大意】給一個4*4的數字謎題，能否恢復到指定形狀

【思路】數字謎題的結論

?

#include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<string> #include<cstring> #include<climits> #include<cmath> #include<map> #include<set> #include<deque> #include<unordered_map> using namespace std; struct node {int arr[5][5];bool operator<(const node& a)const{for (int i = 1; i <= 4; i++){for (int j = 1; j <= 4; j++){if (arr[i][j] >= a.arr[i][j])return false;}}return true;}node() {};node(const int a[][5]){for (int i = 1; i <= 5; i++){for (int j = 1; j <= 5; j++){arr[i][j] = a[i][j];}}} }; map<node, int>mp; int arr[16]; const int mx[4] = { 0,-1,0,1 }; const int my[4] = { 1,0,-1,0 }; int main() {ios_base::sync_with_stdio(false);int T;cin >> T;while (T--){int cal = 0;int px;for (int i = 1; i <= 16; i++){int n;cin >> n;if (n == 0){px = (i - 1) / 4 + 1;continue;}arr[++cal] = n;}int cnt = 0;for (int i = 1; i <= 15; i++){for (int j = i + 1; j <= 15; j++){if (arr[i] > arr[j])cnt++;}}if ((cnt + 4 - px) % 2 == 0)cout << "Yes\n";elsecout << "No\n";} } View Code

---

【HDU 6021】

UNSOLVED

?

?

---

【HDU 6022】

UNSOLVED

?

?

---

【HDU 6023】

SOLVED

【題目大意】

【思路】對素數進行特殊處理，先求N^1/5，于是剩下的素數的冪次最高只能是4了，可以二分開根迅速求解

?

#include<cstdio> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll pri[10001]; int vis[10001]; int cntp; void init() {for (ll i = 2; i < 10000; i++){if (!vis[i]){cntp++;pri[cntp] = i;}for (int j = 1; j <= cntp&&pri[j]*i<10000; j++){vis[i*pri[j]] = 1;if (i%pri[j] == 0){break;}}} } ll sqrt(ll num,int d) {ll l = 1, r = num;while (l <= r){ll mid = (l+r) / 2;ll tmp = LLONG_MAX;if(d==3){tmp = tmp / mid;}if (d == 4){tmp = tmp / mid;tmp /= mid;}if (tmp / mid < mid){r = mid - 1;continue;}tmp = 1;for (int i = 1; i <= d; i++)tmp *= mid;if (tmp == num)return mid;if (tmp > num)r = mid - 1;elsel = mid + 1;}return 0; } int main() {init();int T;scanf("%d", &T);while (T--){ll n;scanf("%lld", &n);int ans = INT_MAX;for (int i = 1; i <= cntp; i++){if (pri[i] > n)break;int cnt = 0;while (n%pri[i] == 0){cnt++;n/= pri[i];}//if (cnt)// printf("cnt %d pri %lld\n", cnt, pri[i]);if (cnt < ans && cnt)ans = cnt;}int res = INT_MAX;if (n>1){if (sqrt(n, 4))res = min(res, 4);else{if (sqrt(n, 2))res = min(res, 2);}if (sqrt(n, 3))res = min(res, 3);if (res == INT_MAX && n > 4500)res = 1;}printf("%d\n", min(ans,res));} //printf("1000000000000000000 %lld %lld\n", sqrt(1000000000000000000, 3), sqrt(1000000000000000000, 2));return 0; } View Code

?

轉載于:https://www.cnblogs.com/rentu/p/11297739.html

總結

以上是生活随笔為你收集整理的杭电多校（四）2019.7.31--暑假集训的全部內容，希望文章能夠幫你解決所遇到的問題。

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