SMU Summer 2023 Contest Round 2

A. Treasure Hunt

当\(x1 - x2\)的差值与\(y1-y2\)的差值都能被\(x,y\)整除时,且商之和为2的倍数就一定可以到达

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define  inf 0x3f3f3f3f

using namespace std;

const int N = 2e5 + 10, mod = 1e18;
int n,m,t,k;
void solve(){
    int x1,y1,x2,y2,x,y;
    cin >> x1 >> y1 >> x2 >> y2 >> x >> y;

    int dx = x2 - x1, dy = y2 - y1;

    if(dx % x == 0 && dy % y == 0 && ((dx / x + dy / y) % 2 == 0)){
        cout << "YES" << endl;
    }else
        cout << "NO" << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
//    cin >> Ke_scholar;
    while(Ke_scholar--)
        solve();
    return 0;
}
/*
 */

B. Makes And The Product

对数组排序,显然前三个的积一定是最小的.

取前三个值为\(a1,a2,a3\),因为三种结果都只看\(a3\)的关系,记\(sum\)为\(a3\)的数量.

结果分三种情况 (实际上应该是四种,不过有两组重复了​:

1. \(a1 = a2 = a3\) 时,说明三个是一样的,只需要在\(sum\)中任取三个即可,即\(C_{sum}^{3}\),也可以用公式\(\frac{sum * (sum - 1) * (sum - 2)}{6}\).
2. \(a1 = a2 < a3\) 或者 $a1 < a2 < a3 $ 时,这两种都是一样的,因为前两个都是必须选,然后再从 \(sum\) 中选一个,答案就是 \(sum\) .
3. \(a1 < a2 = a3\)时,则\(a1\)必选,然后\(a2,a3\)再从\(sum\)中任选两个即可,即\(C_{sum} ^ {2}\),也可以用公式\(\frac{sum * (sum - 1)}{2}\).

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define  inf 0x3f3f3f3f

using namespace std;

const int N = 2e5 + 10, mod = 1e18;
map<int, int > mp;
int n,m,t,k;
void solve(){
   cin >> n;
   vector<int> a(n);
   for(auto &i : a)
       cin >> i;
   sort(a.begin(), a.end());
   int a1 = a[0],a2 = a[1],a3 = a[2];
   int sum = 0;
   for(int i = 0;i < n;i ++){
       sum += (a[i] == a3);
   }
   int ans = 0;
   if(a1 == a2 && a2 == a3){
       ans = sum * (sum - 1) * (sum - 2) / 6;
   }else if(a1 == a2 && a2 < a3 || a1< a2 && a2 < a3){
       ans = sum;
   }else if(a1 < a2 && a2 == a3){
       ans = sum * (sum - 1)/ 2;
   }
   cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
//    cin >> Ke_scholar;
    while(Ke_scholar--)
        solve();
    return 0;
}
/*
 */

C. Really Big Numbers

由于给定的大数在答案中是单调递增的,所以我们可以对答案进行二分,二分的左边界就是满足条件的最小的大数,这个数到\(n\)之间的都算大数,若左边界大于了n说明没有满足条件的

#include<bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

int n,m,t,k;
void solve(){
  int s;
  cin >> n >> s;

  auto get = [&](int x){
      int res = 0;
      while(x){
          res += x % 10;
          x /= 10;
      }
      return res;
  };

  int ans = 0, l = 1, r = 1e18;
  while(l <= r){
      int mid = (l + r) >> 1;
      if(mid - get(mid) >= s){
          r = mid - 1;
//          cout << mid << endl;
      }else l = mid + 1;
  }
  cout << (l > n ? 0 : n - l + 1) << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
//    cin >> Ke_scholar;
    while(Ke_scholar--)
        solve();
    return 0;
}
/*
 */