Educational Codeforces Round 92

后发现自己是zz的补题

D. Segment Intersections

题意：

这题大概的意思就是说给两个区间，这两个区间分别有$n$个，记为$a_n$和$b_n$，每一次可以对其中一个区间进行左端-1和右端+1的操作，每次操作$+1cost$，记区间长度为$r-l$，问最少需要多少次操作，使$\displaystyle \sum_{i=1}^{n}len(a_i \cap b_i)\ge k$。

题解：

不难看出俩区间只有两种情况，相交和不相交。

$\bullet$相交的时候，将所有的区间弥合成$max(r1,r2)-min(l1,l2)$，剩下的再每次操作2次增加1。

$\bullet$不相交的时候，我们要考虑的是让多少个区间先弥合，然后用2换1，$O(n)$暴力枚举即可。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;


signed main() {
  //ifstream cin("E:\\acm dream\\in.in");
  //ofstream cout("E:\\acm dream\\out.out");
  FIO;
  #ifdef err
  double be = clock();
  #endif

  string s;
  int T;cin>>T;
  while(T--){
    ll ans =0;
    ll n,k;cin>>n>>k;
    ll kk=k;
    ll l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
    if(l1>l2||(l1==l2&&r1>r2))swap(l1,l2),swap(r1,r2);
    if(r1>=l2){
      ll in=min(r1,r2)-l2,one=max(r1,r2)-l1-in;
      if(in*n>=k)ans=0;
      else{
        k-=in*n;
        if(one*n>=k)ans=k;
        else k-=one*n,ans=one*n+2*k;
      }
    }else{
      ll c=l2-r1,one=r2-l1;
      ans=LLONG_MAX;
      _for(i,1,n+1){
        ll t=i*c;
        kk=k;
        if(one*i>=kk)t+=kk;
        else t+=one*i,kk-=one*i,t+=kk*2;
        ans=min(t,ans);
      }
    }
    cout<<ans<<endl;
  }

  #ifdef err
  double en = clock();
  cout<<"time: "<<fixed<<setprecision(8)<<en-be;
  #endif
  return 0;
}

E. Calendar Ambiguity

题意：

有一个奇怪的日历，一年有$m$个月，一个月有$d$天，一周有$w$天，定义一个数对$(x<y)$是模糊不清的，当$x$月$y$日和$y$月$x$日对一周来说是同一天，问有多少个数对满足。

题解：

$x$月$y$日可转化为一周中的第$(xd+y)\%w$，则问题可转化为求满足$(xd+y)\equiv(yd+x)(\mod w)$的数对$\{x,y\}$，化简一下公式可以得到$(y-x)(d-1)\equiv0(\mod w)$，即$(y-x)(d-1)=kw$，而$d-1$是一个常数，则$kw$能将$d-1$吸收掉，即化简为$y-x=k\frac{w}{gcd(w,d-1)}$，规律很容易就能找出。

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }


signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    ll m,d,w;cin>>m>>d>>w;
    int g=gcd(d-1,w);
    w/=g;
    m=min(m,d)-1;
    ll n = m/w;
    ll ans=0;
    if(n>0){
      ans=n*(n-1)/2*w+(m-n*w+1)*n;
    }
    cout<<ans<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/09/11/Educational-Codeforces-Round-92/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！