Codeforces Round #562 (Div. 2)

• 题意：
• 给出n组数字，每组有俩个数，问你是否能找到俩个数，使得这n组数，至少有一个数属于这俩个数。
• 题解：
• 思维题，你可以试着找到(1,2),(3,4) 这样俩组完全不同的数，如果找不到，直接输出YES
• 那么你可以遍历一下数组，如果(1,3) (1,4) (2,3) (2,4)这四组数都不满足的话，输出NO，否则输出YES
• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  #define ll long long
  const int maxx = 3e5+5;
  int a[maxx],b[maxx];
  int main()
  {
    int n,m;
    int k1,k2,k3,k4,flag = 0;
    scanf("%d%d",&n,&m);
    scanf("%d%d",&a[1],&b[1]);
    k1 = a[1],k2 = b[1];
    for(int i=2;i<=m;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        if(k1 != a[i] && k2 != b[i] && k1 != b[i] && k2 != a[i]){
            k3 = a[i],k4 = b[i],flag = 1;
        }
    }
    //cout<<k3<<" "<<k4<<" "<<flag<<endl;
    if(!flag)
    {
        cout<<"YES"<<endl;
        return 0;
    }
    int x,y;
    for(int j=1;j<=4;j++)
    {
        if(j == 1)
            x = k1,y = k3;
        else if(j == 2)
            x = k1,y = k4;
        else if(j == 3)
            x = k2,y = k3;
        else
            x = k2,y = k4;
        int cnt = 0;
        for(int i=1;i<=m;i++)
        {
            if(a[i] == x || a[i] == y || b[i] == x || b[i] == y){
                cnt++;
            }
        }
        if(cnt == m){
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
    return 0;
  }

• 题意：
• 给出n个数，每次可以将若干数+1对k取模，问你最少进行多少次操作可以让这个序列变成非递减序列，输出最小次数
• 题解：
• 二分答案
• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  #define ll long long 
  const int maxx = 3e5+10;
  int n,m;
  int a[maxx];
  bool solve(int x)
  {
    int pre = 0;
    for(int i=1;i<=n;i++){
        if(a[i] + x < pre)
            return false;
        if(a[i] <= pre || (a[i] + x >= m && (a[i]+x)%m >= pre))
            continue;
        pre = a[i];
    }
    return true;
  } 
  int main()
  {
    int ans;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    } 
    int  l = 0, r = m;
    while(l <= r)
    {
        int mid = (l+r)>>1;
        if(solve(mid)){
            ans = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    printf("%d\n",ans);
    return 0;
  }
  

```