2020-2021:teams:wangzai_milk:codeforce_1392部分题解
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:codeforce_1392部分题解 [2020/09/03 19:06] infinity37 [1392E] |
2020-2021:teams:wangzai_milk:codeforce_1392部分题解 [2020/09/03 19:34] (当前版本) infinity37 [1392H] |
||
|---|---|---|---|
| 行 51: | 行 51: | ||
| ==== 1392F ==== | ==== 1392F ==== | ||
| ===题意=== | ===题意=== | ||
| + | 给一个单调递增的数组，如果相邻两个元素$a_i<a_{i+1}+1$，那么就令$a_i$加一，令$a_{i+1}$减一。问最后状态如何。 | ||
| ===题解=== | ===题解=== | ||
| + | 可以确定的是最后的状态一定是相邻相差一，最多有一对相邻是相等的值。于是我们只需要求和然后直接模拟即可。 | ||
| ===代码=== | ===代码=== | ||
| + | <hidden><code c++> | ||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | const int N = 1e6+5; | ||
| + | ll h[N]; | ||
| + | struct Node { | ||
| + | ll x,y; | ||
| + | }; | ||
| + | vector<Node> vec; | ||
| + | int main() { | ||
| + | int n; | ||
| + | scanf("%d",&n); | ||
| + | for (int i = 1;i<= n;i++) | ||
| + | { | ||
| + | scanf("%lld",&h[i]); | ||
| + | h[i]-=i; | ||
| + | } | ||
| + | vec.push_back({h[1],1}); | ||
| + | for (int i = 2;i<= n;i++) { | ||
| + | if (h[i] < vec.back().x) { | ||
| + | vec.push_back({h[i],i}); | ||
| + | continue; | ||
| + | } | ||
| + | if (h[i] == vec.back().x) continue; | ||
| + | while (vec.size() > 1 && h[i]-vec.back().x > i - vec.back().y) { | ||
| + | h[i]-=i-vec.back().y; | ||
| + | vec.pop_back(); | ||
| + | } | ||
| + | if (vec.size() == 1) { | ||
| + | ll tmp = (h[i] - vec.back().x) / i; | ||
| + | h[i] -= tmp*(i-1); | ||
| + | vec.back().x += tmp; | ||
| + | } | ||
| + | if (h[i] == vec.back().x) continue; | ||
| + | ll d = h[i] - vec.back().x; | ||
| + | Node tmpk = vec.back(); | ||
| + | if (vec.size() == 1) | ||
| + | vec.back().x++; | ||
| + | else | ||
| + | vec.pop_back(); | ||
| + | vec.push_back({tmpk.x,tmpk.y + d}); | ||
| + | } | ||
| + | vec.push_back({0,n*10}); | ||
| + | int p = 0; | ||
| + | for (int i = 1;i<= n;i++) { | ||
| + | if (vec[p+1].y == i)p++; | ||
| + | printf("%lld ",vec[p].x+i); | ||
| + | } | ||
| + | printf("\n"); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| \\ | \\ | ||
| ==== 1392G ==== | ==== 1392G ==== | ||
| ===题意=== | ===题意=== | ||
| + | 有$k$个位置，每个位置可以放0或1，有$n$个人，第$i$个人可以把$a_i$位置和$b_i$位置交换一次。给出初始位置的01和最终位置的01，要选一段人使得操作后位置相同个数最大。 | ||
| ===题解=== | ===题解=== | ||
| + | 考虑这个序列，其实交换$(l,r)$相对于对初始序列的$(1,l-1)$和最终序列的$(1,r)$做反向交换然后互相比较。预处理好然后计算更新答案就行。 | ||
| ===代码=== | ===代码=== | ||
| + | <hidden><code c++> | ||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | const int N = 2e6+5; | ||
| + | const int inf = 1e9; | ||
| + | int a[N],b[N],p[30],L[N],R[N]; | ||
| + | string ss,tt,s[N],t[N]; | ||
| + | int calc(string str) { | ||
| + | int ans = 0; | ||
| + | for (int i = 0;i <= str.size()-1;i++) | ||
| + | if (str[i]=='1')ans |= (1 << i); | ||
| + | return ans; | ||
| + | } | ||
| + | int getone(int x) { | ||
| + | int cnt = 0; | ||
| + | while (x) { | ||
| + | if (x&1)cnt++; | ||
| + | x>>=1; | ||
| + | } | ||
| + | return cnt; | ||
| + | } | ||
| + | int main() { | ||
| + | int n,m,k; | ||
| + | scanf("%d%d%d",&n,&m,&k); | ||
| + | cin >> ss >> tt; | ||
| + | s[0] = ss; | ||
| + | t[0] = tt; | ||
| + | for (int i = 1;i<= n;i++) | ||
| + | scanf("%d%d",&a[i],&b[i]),a[i]--,b[i]--; | ||
| + | for (int i = 0;i<= k;i++)p[i] = i; | ||
| + | for (int i = 0;i < (1<< k);i++) | ||
| + | L[i] = inf,R[i] = -inf; | ||
| + | for (int i = 1;i<= n;i++) { | ||
| + | s[i] = t[i] = string(k,'0'); | ||
| + | swap(p[a[i]],p[b[i]]); | ||
| + | for (int j = 0;j < k;j++) { | ||
| + | s[i][p[j]] = ss[j]; | ||
| + | t[i][p[j]] = tt[j]; | ||
| + | } | ||
| + | } | ||
| + | for (int i = 0;i<= n;i++) { | ||
| + | L[calc(s[i])] = min(L[calc(s[i])],i); | ||
| + | R[calc(t[i])] = max(R[calc(t[i])],i); | ||
| + | } | ||
| + | for (int i = (1<<k)-1;i >= 0;i--) | ||
| + | for (int j = 0;j < k;j++) | ||
| + | if ((1<<j)&i) { | ||
| + | L[i^(1<<j)] = min(L[i^(1<<j)],L[i]); | ||
| + | R[i^(1<<j)] = max(R[i^(1<<j)],R[i]); | ||
| + | } | ||
| + | int ans = 0,l = 1,r = 1; | ||
| + | for (int i = 0;i < (1<<k);i++) | ||
| + | if (R[i]-L[i]>=m && getone(i)>ans) { | ||
| + | ans = getone(i); | ||
| + | l = L[i]+1,r = R[i]; | ||
| + | } | ||
| + | printf("%d \n%d %d",k+2*ans-count(ss.begin(),ss.end(),'1')-count(tt.begin(),tt.end(),'1'),l,r); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| \\ | \\ | ||
| ==== 1392H ==== | ==== 1392H ==== | ||
| ===题意=== | ===题意=== | ||
| + | 给你$n$张数字牌和$m-n$张特殊牌河一个数字集合。进行如下操作： | ||
| + | |||
| + | 拿出最上面的那张卡片，如果卡片是数字牌，那么把这个数字放进集合。 | ||
| + | |||
| + | 其他情况下把所有卡片重新打乱。检验集合是否包含了所有数字，如果包含了结束游戏。 | ||
| + | |||
| + | 问期望操作次数。 | ||
| ===题解=== | ===题解=== | ||
| + | 期望操作次数是期望游戏轮数乘以期望每一轮次数。 | ||
| - | ===代码=== | + | 可以发现如果在游戏中摸到特殊牌那么一轮就会结束，那么我们算出所有排列中第一张特殊牌之前的牌数，然后+1除以排列数目就是每轮游戏操作次数的期望。这个的答案是$\frac{n}{m+1}+1$。 |
| + | 然后另一个部分则是$m\sum_{i=1}^n\frac{1}{i}+1$，最终答案就是这两者相乘。 | ||
| + | |||
| + | ===代码=== | ||
| + | <hidden><code c++> | ||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | const int mod = 998244353; | ||
| + | ll quick_pow(ll x,ll y) { | ||
| + | ll ans = 1; | ||
| + | while (y) { | ||
| + | if (y&1) ans = ans*x%mod; | ||
| + | x = x*x%mod; | ||
| + | y >>= 1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int main() { | ||
| + | int n,m; | ||
| + | scanf("%d%d",&n,&m); | ||
| + | ll ans1 = (1ll*n*quick_pow(m+1,mod-2)%mod+1)%mod; | ||
| + | ll ans2 = 0; | ||
| + | for (int i = 1;i<= n;i++) | ||
| + | ans2 = (ans2+quick_pow(i,mod-2))%mod; | ||
| + | ans2 = (ans2*m+1)%mod; | ||
| + | printf("%lld\n",ans1*ans2%mod); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| \\ | \\ | ||
2020-2021/teams/wangzai_milk/codeforce_1392部分题解.1599131178.txt.gz · 最后更改: 2020/09/03 19:06 由 infinity37
