【HDU 6003】

UNSOLVED

?

?

---

【HDU 6004】

SOLVED

【題目大意】有一DAG圖，n個節點，m次詢問，每次詢問兩個節點，求令兩個節點任意一個和葉節點失去聯通的方法數

【思路】支配樹，沒有聽說過于是被當場爆錘（知道了也是被錘的命QwQ）

?

#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 = 200010; vector<int>G[maxn]; int indegree[maxn]; int nex[maxn][30]; int dis[maxn]; int lca_num[maxn]; int N, M; void init(int n) {for (int j = 1; (1 << j) <= N; j++)nex[n][j] = nex[nex[n][j - 1]][j - 1]; } int lca(int a, int b) {if (b == -1)return a;if (dis[a] < dis[b])swap(a, b);int delta_distance = dis[a] - dis[b];int base = 0;while (delta_distance){if (delta_distance & 1)a = nex[a][base];base++;delta_distance >>= 1;}if (a == b)return a;for (int i = log2(N); i >= 0; i--){if (nex[a][i] != nex[b][i]){a = nex[a][i];b = nex[b][i];}}return nex[a][0]; } int main() {ios_base::sync_with_stdio(false);int T;cin >> T;while (T--){memset(lca_num, -1, sizeof(lca_num));memset(indegree, 0, sizeof(indegree));memset(dis, 0, sizeof(dis));memset(nex, 0, sizeof(nex));cin >> N >> M;for (int i = 0; i <= N; i++)G[i].clear();for (int i = 1; i <= M; i++){int u, v;cin >> u >> v;G[v].push_back(u);indegree[u]++;}queue<int>que;for (int i = 1; i <= N; i++){if (indegree[i] == 0){lca_num[i] = 0;que.push(i);}}while (!que.empty()){int n = que.front();que.pop();nex[n][0] = lca_num[n];dis[n] = dis[lca_num[n]] + 1;init(n);for (int to : G[n]){lca_num[to] = lca(n, lca_num[to]);if (--indegree[to]==0)que.push(to);}}int Q;cin >> Q;for (int i = 1; i <= Q; i++){int a, b;cin >> a >> b;cout << dis[a] + dis[b] - dis[lca(a, b)] << "\n";}} } View Code

---

【HDU 6005】

UNSOLVED

?

?

---

【HDU 6006】

UNSOLVED

?

?

---

【HDU 6007】

UNSOLVED

?

---

【HDU 6008】

SOLVED

【思路】循環節

?

?

#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include <iostream> #include <algorithm> using namespace std; using ll = long long int; ll T, x, n, ans; ll a[]={2, 3, 5, 7, 11, 13, 17, 19};ll pow_mul(ll a, ll b, ll r) {ll ans = 0;while(b){if(b & 1)ans = (ans + a) % r;a = (a + a) % r;b >>= 1;}return ans % r; }ll pow_mod(ll a, ll b, ll r) {ll ans = 1;while(b){if(b & 1) ans = pow_mul(ans, a, r) % r;a = pow_mul(a, a, r) % r;b >>= 1;}return ans % r; }bool test(ll a, ll p, ll d) {if(p % 2 == 0) return false;while(!(d & 1)) d >>= 1;ll t = pow_mod(a, d, p); //得到 a^d % p while(d != p - 1){ll y = pow_mul(t, t, p); // t^2 % pif(y == 1){if(t != 1 && t != p - 1) return false;//不滿足二次探測定理 return true; //滿足的話后面的肯定也滿足了 因為此時y = 1 } t = y; d <<= 1;}return t == 1; //最后一次測試 a^(p - 1) % p = 1 }bool isprime(ll x) {for(int i = 0; i < 8; i ++){if(a[i] == x) return true;if(!test(a[i], x, x - 1))return false;} return true; }ll mul(ll a,ll b,ll mod){ll ret = 0;while (b){if (b & 1)ret = (a + ret) % mod;b >>= 1;a = (a + a) % mod; }return ret;} ll quicmod(ll a,ll b,ll mod){ll ret = 1;while (b){if (b & 1){ret = mul(ret,a,mod);}b >>= 1;a = mul(a,a,mod);}return ret;} int main() {int T;scanf("%d",&T);while (T--){ll p,Q,ret = 0;scanf("%lld",&Q);p = Q - 1;ret = Q - 1;while (isprime(p) == 0)ret = mul(ret,quicmod(p,Q - 2,Q),Q),p--;printf("%lld\n",ret);}return 0; } View Code

---

【HDU 6009】

SOLVED

【題目大意】一個數列，令1<=i<=n，每個wi都有都要滿足到此前綴和小于m，如果大于則需要從前i-1個數中刪除，直到符合條件，輸出每位最少需要刪除的數字個數

【思路】有點類似主席樹，建一顆值域線段樹，每次遍歷動態更新節點，然后保存和，然后二分向下查找

?

#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 = 200010; typedef pair<int, int>P; P arr[maxn]; int rnk[maxn]; struct segment_tree {struct node{int left, right, mid;long long sum, num;};node tree[4 * maxn];void update(int k){tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum;tree[k].num = tree[k << 1].num + tree[k << 1 | 1].num;}void build_tree(int l, int r, int k = 1){tree[k].left = l;tree[k].right = r;tree[k].mid = (r + l) >> 1;if (l == r)return;const int& m = tree[k].mid;build_tree(l, m, k << 1);build_tree(m + 1, r, k << 1 | 1);}void change_interval(int l, int r, int k = 1){if (l <= tree[k].left && tree[k].right <= r){tree[k].sum += arr[tree[k].left].first;tree[k].num++;return;}const int& m = tree[k].mid;if (l <= m)change_interval(l, r, k << 1);if (r > m)change_interval(l, r, k << 1 | 1);update(k);}int query(long long x, int k = 1){if (tree[k].sum <= x)return 0;int ans = 0;if (tree[k].left == tree[k].right)return 1;if (tree[k << 1].sum <= x)ans += query(x - tree[k << 1].sum, k << 1 | 1);else{ans += tree[k << 1 | 1].num;ans += query(x, k << 1);}return ans;} }my_tree; int main() {ios_base::sync_with_stdio(false);int T;cin >> T;while (T--){memset(&my_tree, 0, sizeof(my_tree));int N, K;cin >> N >> K;for (int i = 1; i <= N; i++){cin >> arr[i].first;arr[i].second = i;}sort(arr + 1, arr + N + 1);for (int i = 1; i <= N; i++){rnk[arr[i].second] = i;}my_tree.build_tree(1, N);for (int i = 1; i <= N; i++){cout << my_tree.query(K - arr[rnk[i]].first) << " ";my_tree.change_interval(rnk[i], rnk[i]);}cout << "\n";} } View Code

---

【HDU 6010】

UNSOLVED

?

?

---

【HDU 6011】

UNSOLVED

?

?

---

【HDU 6012】

UNSOLVED

?

?

---

【HDU 6013】

UNSOLVED

?

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

總結

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

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