Codeforces Round 976 (Div. 2) and Divide By Zero 9.0（A~E）

A - Find Minimum Operations

思路

对

     n 
    
   
  
    n 
   
  
n进行 
 
  
   
   
     m 
    
   
  
    m 
   
  
m进制分解，所有位上相加就是答案（参考 
 
  
   
   
     m 
    
   
     = 
    
   
     2 
    
   
  
    m=2 
   
  
m=2时）

代码

// Problem: A. Find Minimum Operations// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0// URL: https://codeforces.com/contest/2020/problem/0// Memory Limit: 256 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>usingnamespace std;#defineLLlonglong#definepbpush_back#definexfirst#defineysecond #defineendl'\n'const LL maxn =4e05+7;const LL N =5e05+10;const LL mod =1e09+7;constint inf =0x3f3f3f3f;const LL llinf =5e18;typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL>>mi;//小根堆
priority_queue<LL> ma;//大根堆intcalc(int n ,int m){int cnt =0;if(m ==1){return n;}while(n){
        cnt += n % m;
        n /= m;}return cnt;}voidsolve(){int n , m;
    cin >> n >> m;
    cout <<calc(n , m)<< endl;}intmain(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);int t=1;
    cin>>t;while(t--){solve();}return0;}

B - Brightness Begins

思路

经典关灯，第

     x 
    
   
  
    x 
   
  
x位置的灯会被 
 
  
   
   
     x 
    
   
  
    x 
   
  
x的所有因数操作，因此当且仅当 
 
  
   
   
     x 
    
   
  
    x 
   
  
x为完全平方数时会被关闭，考虑二分答案，找到 
 
  
   
   
     m 
    
   
     i 
    
   
     d 
    
   
  
    mid 
   
  
mid之前有多少个完全平方数就能算出最终有多少个灯是关着的，可以直接用 
 
  
   
   
     s 
    
   
     q 
    
   
     r 
    
   
     t 
    
   
  
    sqrt 
   
  
sqrt函数近似的找到最接近 
 
  
   
   
     m 
    
   
     i 
    
   
     d 
    
   
  
    mid 
   
  
mid的完全平方数，然后左右探测一下就能找到有多少个完全平方数小于等于 
 
  
   
   
     m 
    
   
     i 
    
   
     d 
    
   
  
    mid 
   
  
mid.

代码

// Problem: B. Brightness Begins// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0// URL: https://codeforces.com/contest/2020/problem/B// Memory Limit: 256 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>usingnamespace std;#defineLLlonglong#definepbpush_back#definexfirst#defineysecond #defineendl'\n'#defineintlonglongconst LL maxn =4e05+7;const LL N =5e05+10;const LL mod =1e09+7;constint inf =0x3f3f3f3f;const LL llinf =5e18;typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL>>mi;//小根堆
priority_queue<LL> ma;//大根堆voidsolve(){int n;
    cin >> n;int l = n , r =2e18;while(l < r){int mid =(l + r)>>1;//[1 - mid]中有几个完全平方数int t =sqrt(mid);while(t * t > mid){
            t--;}while((t +1)*(t +1)<= mid){
            t++;}if(mid - t >= n){
            r = mid;}else{
            l = mid +1;}}    
    cout << l << endl;}signedmain(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);int t=1;
    cin>>t;while(t--){solve();}return0;}

C - Bitwise Balancing

思路

拆位，对每一位进行分析，

     [ 
    
   
     b 
    
   
     , 
    
   
     c 
    
   
     , 
    
   
     d 
    
   
     ] 
    
   
  
    [b,c,d] 
   
  
[b,c,d]在某一位上的组合只有 
 
  
   
   
     8 
    
   
  
    8 
   
  
8种，对每种分类讨论 
 
  
   
   
     a 
    
   
  
    a 
   
  
a的取值

代码

// Problem: C. Bitwise Balancing// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0// URL: https://codeforces.com/contest/2020/problem/C// Memory Limit: 256 MB// Time Limit: 2000 ms// // Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>usingnamespace std;#defineLLlonglong#definepbpush_back#definexfirst#defineysecond #defineendl'\n'#defineintlonglongconst LL maxn =4e05+7;const LL N =5e05+10;const LL mod =1e09+7;constint inf =0x3f3f3f3f;const LL llinf =5e18;typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL>>mi;//小根堆
priority_queue<LL> ma;//大根堆voidsolve(){//如果d的这一位是0，int b , c , d;
    cin >> b >> c >> d;int a =0;for(int i =63; i >=0; i --){if(d >> i &1LL){if(c >> i &1LL){if(b >> i &1LL){continue;}else{
                    cout <<-1<< endl;return;}}else{
                a |=(1LL<< i);}}else{if(b >> i &1LL){if(c >> i &1LL){
                    a |=(1LL<< i);}else{
                    cout <<-1<< endl;return;}}else{continue;}}}
    cout << a <<endl;}signedmain(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);int t=1;
    cin>>t;while(t--){solve();}return0;}

D - Connect the Dots

思路

注意到

     d 
    
   
  
    d 
   
  
d很小，因此如果我们只需要知道某一位置上能否跟前面 
 
  
   
   
     d 
    
   
  
    d 
   
  
d个数相连，就能把最终的图连出来。

用数组

     c 
    
   
     n 
    
   
     t 
    
   
     [ 
    
   
     i 
    
   
     ] 
    
   
     [ 
    
   
     j 
    
   
     ] 
    
   
  
    cnt[i][j] 
   
  
cnt[i][j]来表示 
 
  
   
    
    
      a 
     
    
      i 
     
    
   
  
    a_i 
   
  
ai​能否跟 
 
  
   
    
    
      a 
     
     
     
       i 
      
     
       − 
      
     
       j 
      
     
    
   
  
    a_{i - j} 
   
  
ai−j​相连，用差分来维护 
 
  
   
   
     c 
    
   
     n 
    
   
     t 
    
   
  
    cnt 
   
  
cnt数组即可。

代码

// Problem: D. Connect the Dots// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0// URL: https://codeforces.com/contest/2020/problem/D// Memory Limit: 512 MB// Time Limit: 2000 ms// // Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>usingnamespace std;#defineLLlonglong#definepbpush_back#definexfirst#defineysecond #defineendl'\n'const LL maxn =4e05+7;const LL N =5e05+10;const LL mod =1e09+7;constint inf =0x3f3f3f3f;const LL llinf =5e18;typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL>>mi;//小根堆
priority_queue<LL> ma;//大根堆structDSU{
    std::vector<int> f, siz;DSU(){}DSU(int n){init(n);}voidinit(int n){
        f.resize(n);
        std::iota(f.begin(), f.end(),0);
        siz.assign(n,1);}intfind(int x){while(x != f[x]){
            x = f[x]= f[f[x]];}return x;}boolsame(int x,int y){returnfind(x)==find(y);}boolmerge(int x,int y){
        x =find(x);
        y =find(y);if(x == y){returnfalse;}
        siz[x]+= siz[y];
        f[y]= x;returntrue;}intsize(int x){return siz[find(x)];}};voidsolve(){//注意到D很小int n , m;
    cin >> n >> m;int vis[n +100][20];int cnt[n +100][20];memset(vis ,0,sizeof vis);memset(cnt ,0,sizeof cnt);
    DSU dsu(n +5);for(int i =0; i < m ; i ++){int a , d , k;
        cin >> a >> d >> k;int l = a , r = a + k * d;
        cnt[l + d][d]++;
        cnt[r + d][d]--;}for(int i =1; i <= n ; i ++){int tot =0;for(int j =1; j <=min(10, i); j ++){
            cnt[i][j]+= cnt[i - j][j];}}for(int i =2; i <= n ; i ++){for(int j =1; j <=min(i -1,10); j ++){if(cnt[i][j]){
                dsu.merge(i , i - j);}}}int ans =0;for(int i =1; i <= n ; i ++){
        ans +=(dsu.f[i]== i);}
    cout << ans << endl;}intmain(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);int t=1;
    cin>>t;while(t--){solve();}return0;}

E - Expected Power

思路

观察到

     a 
    
   
  
    a 
   
  
a数组取值很小，考虑 
 
  
   
   
     d 
    
   
     p 
    
   
  
    dp 
   
  
dp解决问题。用 
 
  
   
   
     d 
    
   
     p 
    
   
     [ 
    
   
     i 
    
   
     ] 
    
   
  
    dp[i] 
   
  
dp[i]来代表取到当前取到 
 
  
   
   
     i 
    
   
  
    i 
   
  
i的概率，那么对于每个 
 
  
   
    
    
      a 
     
    
      i 
     
    
   
  
    a_{i} 
   
  
ai​,我们枚举 
 
  
   
   
     x 
    
   
     ( 
    
   
     0 
    
   
     ≤ 
    
   
     x 
    
   
     ≤ 
    
   
     1023 
    
   
     ) 
    
   
  
    x(0 \leq x \leq 1023) 
   
  
x(0≤x≤1023) ,  
 
  
   
   
     d 
    
   
     p 
    
   
     [ 
    
   
     x 
    
   
     ⊕ 
    
    
    
      a 
     
    
      i 
     
    
   
     ] 
    
   
     = 
    
   
     d 
    
   
     p 
    
   
     [ 
    
   
     x 
    
   
     ] 
    
   
     ∗ 
    
   
     p 
    
   
     , 
    
   
     d 
    
   
     p 
    
   
     [ 
    
   
     x 
    
   
     ] 
    
   
     = 
    
   
     d 
    
   
     p 
    
   
     [ 
    
   
     x 
    
   
     ] 
    
   
     ∗ 
    
   
     ( 
    
   
     1 
    
   
     − 
    
   
     p 
    
   
     ) 
    
   
  
    dp[x \oplus a_{i}] = dp[x] * p , dp[x] = dp[x] * (1 - p) 
   
  
dp[x⊕ai​]=dp[x]∗p,dp[x]=dp[x]∗(1−p)，总体复杂度为 
 
  
   
   
     O 
    
   
     ( 
    
   
     1024 
    
   
     ∗ 
    
   
     N 
    
   
     ) 
    
   
  
    O(1024*N) 
   
  
O(1024∗N)能通过此题

代码

// Problem: E. Expected Power// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0// URL: https://codeforces.com/contest/2020/problem/E// Memory Limit: 256 MB// Time Limit: 4000 ms// // Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>usingnamespace std;#defineLLlonglong#definepbpush_back#definexfirst#defineysecond #defineendl'\n'const LL maxn =4e05+7;const LL N =5e05+10;const LL mod =1e09+7;#defineintlonglongconstint inf =0x3f3f3f3f;const LL llinf =5e18;typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL>>mi;//小根堆
priority_queue<LL> ma;//大根堆
LL qpow(LL a , LL b)//快速幂{
    LL sum=1;while(b){if(b&1){
            sum=sum*a%mod;}
        a=a*a%mod;
        b>>=1;}return sum;}voidsolve(){int t =qpow(10000, mod -2);int dp[1030][2];//取到i的概率memset(dp ,0,sizeof dp);
    dp[0][0]=1;int n;
    cin >> n;int a[n];for(int i =0; i < n ; i ++){
        cin >> a[i];}for(int i =0; i < n ; i ++){int p;
        cin >> p;for(int j =0; j <1024; j ++){int k = j ^ a[i];
            dp[k][1]+= dp[j][0]*((p * t)% mod);
            dp[k][1]%= mod;        
            dp[j][1]+= dp[j][0]*(((10000- p)* t)% mod);
            dp[j][1]%= mod;}for(int j =0; j <1024; j++){
            dp[j][0]= dp[j][1];
            dp[j][1]=0;}}int ans =0;for(int i =1; i <1024; i ++){
        ans += dp[i][0]* i * i;
        ans %= mod;}
    cout << ans << endl;}signedmain(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);int t=1;
    cin>>t;while(t--){solve();}return0;}