CF 训练2

avatar
作者
筋斗云
阅读量:0

688 div2 C Balanced Bitstring

思路:首先对于区间问题 , 我们可以先思考让它滑动滑动。对于[l,r],向后滑动一位后 ,[l+1 , r+1],因为两次的区间中 , [l+1 ,r]中所有数都是相同的 , 所以 可以得到s[l] = s[r+1] , 那么再向后滑动 , 就有 l+1 = r+2 , 一次类推 , 在1 ~ k中 , 每个数每次 +k , s[x] = s[x+k]的。那么我们就可以对于每个k的区间来进行处理 , 观察它们是否相同。但是对于 ? 的话 ,我们可以先不管他,最后看
1和0的个数是否都 <= k/2 就行了

void solve(){   cin>>n>>k;   string s;cin>>s;   s = '#' + s;   for(int i =1;i<=k;++i)str[i] = 0;   for(int i=1;i<=k;++i){     for(int j =i;j<=n;j +=k){       if(s[j] == '?')continue;       if(str[i] == 0)str[i] = s[j];       else if(str[i] != s[j]){         cout<<"NO"<<endl;         return;       }     }   }    int cnt1 = 0 , cnt0 = 0;   for(int i =1;i<=k;++i){     if(str[i] == '1')cnt1++;     else if(str[i] == '0')cnt0++;   }   if(cnt1 <=k/2 && cnt0 <= k/2){     cout<<"YES"<<endl;     return;   }   cout<<"NO"<<endl; }

688 div2 D Tree Tag

思路:首先如果一开始 a和b的距离小于 da , 那么爱丽丝赢 。 如果b被追到了死角 , 那么必须db > 2*da 。 最后需要树有一段很长的距离,足够b来躲掉a,也就是树的直径 > 2a,bob才有可能赢

void dfs(int u , int fa){    for(auto to : g[u]){     if(vis[to] || to == fa)continue;     dis[to] = dis[u] + 1;     vis[to] = 1;     dfs(to , u);   } }   void solve(){   cin>>n>>a>>b>>da>>db;      for(int i =1;i<=n;++i)g[i].clear();   for(int i =1;i<n;++i){     int u ,v;cin>>u>>v;     g[u].push_back(v);     g[v].push_back(u);    }    for(int i =1;i<=n;++i)vis[i] = 0 , dis[i] =  0;    dis[a] = 0;   dfs(a , 0);     if(dis[b] <= da){     cout<<"Alice"<<endl;     return;   }      int ma = -1 , Q = 0;   for(int i =1;i<=n;++i){     if(dis[i] > ma)ma = dis[i] , Q =i;   }    for(int i =1;i<=n;++i)vis[i] = 0 , dis[i] =  0;   dfs(Q , 0);    ma = -1;   for(int i =1;i<=n;++i){     if(dis[i] > ma)ma = dis[i];   }         if(2 * da >= db){     cout<<"Alice"<<endl;     return;   }   cout<<"Bob"<<endl;   }

962 div3 E Decode

思路 :还是区间01的问题 , 我们可以把0当作-1 , 1当作 1,如果区间中0和1的数量相等 , 那么就说明区间和为 0 ,对于一个区间为0的区间,我们思考它对答案的贡献。

假设区间为[l,r]的这样一段区间,它对答案的贡献是多少 , 首先左边的贡献是 l , 右边的贡献是 n-r+1 , 根据乘法原理 , 贡献为l*(n-r+1)。 

如何找区间 ,根据前缀和思想 , pre[r] - pre[l-1] = 0 -> pre[l-1] = pre[r]。那么接下来,可以用一个map进行优化 , 时间复杂度就应该是 Onlogn

void solve(){   cin>>s;   int n = s.size();   s = '#' + s;   for(int i =1;i<=n;++i)pre[i] = pre[i-1] + (s[i]=='1' ?1 : -1 );   map<int,int>mp;   int ans = 0;   mp[0] =1;  for(int i =1;i<=n;++i){     ans +=(mp[pre[i]])*(n-i+1);     mp[pre[i]] += (i+1);      mp[pre[i]]%= mod;     ans %= mod;   }   cout<<ans<<endl; }

962 div3 F Bomb

思路: 观察到数据非常大 , k 是1e9 , 那么k次的优先队列询问肯定是不行了。这题其实是个很典的题,我们可以二分出来最后每个数的最大值,也就是说,每个数最后肯定会减到 那个最大值或者大于最大值。
那么对于如何二分,我们思考到 , 二分出来的x 越大 ,我们所需要减少的次数cnt 就越少,cnt <= k的话,x就有一个最小值 , 所以是在分界线的右边  ,当我们的cnt >= k 的话就需要 l  = mid , 否则
r = mid -1;
对于每个数可以用掉的次数为 cnt = (ai - x) / bi + 1,那么构成一个等差数列,其中的和也很容易算出来。

还有一个细节就是最后我们用掉的次数可能小于k ,那么多出来的这几次 直接×二分出来的x即可

void solve(){   cin>>n>>k;   for(int i =1;i<=n;++i)cin>>a[i];   for(int i =1;i<=n;++i)cin>>b[i];    auto check =[&](int x){     int cnt = 0;     for(int i =1;i<=n;++i){       if(a[i] >= x){         cnt += (a[i]-x)/b[i] + 1;       }     }     return cnt >= k;   };    int l=0 ,r = 2e10;   while(l < r){     int mid = (l+r+1)>>1;     if(check(mid))l =mid;     else r = mid -1;   }   int cnt = 0;   int sum = 0;      for(int i= 1;i<=n;++i){     if(a[i] >= l){       int m =(a[i]-l)/b[i] + 1;       sum += a[i]*m - m*(m-1)*b[i]/2;       cnt += m;     }     }   cout<<sum + l*(k - cnt)<<endl; }

很细节的一道题 , 多多思考🤔。

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!