Codeforces Round 944(Div.4)

A.My First Sorting Problem(模拟)

题意

给定x和y，要求升序输出答案.

Code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int x, y;cin >> x >> y;
        if(x > y)
            swap(x, y);
        cout << x << ' ' << y << endl;
    }
    return 0;
}

B.Different String(模拟)

题意

给定字符串s,要求重排该字符串，使得新字符串与原字符串s不相等，若有解，则输出“YES”并换行输出新字符串，反之，输出“NO”即可.

Code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        string s;cin >> s;
        bool ok = 1;
        for (int i = 1; i < s.length();i++)
            if(s[i]!=s[i-1])
                ok = 0;
        if(ok){
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        //先输出s[1~s.size()-1]，最后输出s[0]
        for (int i = 1; i < s.length();i++)
            cout << s[i];
        cout << s[0] << endl;
    }
    return 0;
}

C.Clock and Strings(思维)

这题因为一直没想到正解的简单思路，赛时被卡了太久

题意

有一个时钟，点数为1-12，现在在时钟上系两条绳子（红、蓝绳），现在输入不同的四个整数a,b,c,d,其中a,b表示的是红绳系的两个点数，c,d表示是蓝绳系的两个点数。请问这两根线是否相交？

思路

以红绳系住的两点为参照点，假设a < b，则从a遍历到b并从b遍历到a（记得转完一圈后要进行模12的操作），如果两种遍历里有一种情况同时包含了c和d，则说明一定没相交，反之就相交.

Code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
int a[5];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        cin >> a[1] >> a[2] >> a[3] >> a[4];
        sort(a + 1, a + 3);
        sort(a + 3, a + 5);
        int cnt = 0;
        for (int i = a[1] +1; i < a[2];i++){
            if(i==a[3])cnt++;
            if(i==a[4])cnt++;
        }
        if(cnt==2){
            cout << "NO" << endl;
            continue;
        }
        cnt = 0;
        for (int i = a[2]+1; i < 12 + a[1];i++){
            if(i%12==a[3]||i==12&&a[3]==12)cnt++;
            if (i % 12 == a[4] || i == 12 && a[4] == 12)cnt++;
        }
        if (cnt == 2){
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
    }
    return 0;
}

D.Binary Cut(思维)

题意

给定一个二进制字符串，将这些二进制分割成若干连续段，使得这些连续块按照一定顺序排列后字符串成功升序（只有一个字符或前半段全为‘0’后半段全为‘1’）。求分割后的最小块数.

思路

    首先进行特判，如果字符串只有一个字符，那么块数一定为1;如果字符串本身就有序，那么块数也为1;如果字符串有两个字符，那么块数至少为2.
    我们可以把所有连续相同字符的段进行分割，这样一定能够重排成升序序列;然后不难发现，如果原字符串只要存在相邻不同的子串，那么这两个连续子段间可以满足升序的条件，恰好可以少分割一次.

Code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
char s[505];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int cnt = 0;
        cin >> s;
        int num = strlen(s);
        bool ok = 1;
        for (int i = 1; i < num;i++)
            if(s[i]=='0'&&s[i-1]=='1')
                ok = 0;
        if(ok){
            cout << "1" << endl;
            continue;
        }
        for (int i = 1; i < num;i++)
            if(s[i]!=s[i-1])
                cnt++;
        cout << max(cnt,2LL) << endl;
    }
    return 0;
}

E.Find the Car(二分)
这题浮点数极容易被hack,当时我用了floor，运气好没被人为hack掉，估计重测完会会被叉.

题意

    数轴上含有0，1，2，…，k个标志，汽车将在bi时刻经过位置a[i],已知任意两个标志间的速度恒定，列车从0时刻正式出发，保证a[k] = n .
    现有m次查询，每次输入一个d，表示经过位置d时是多少分钟（四舍五入向下取整）

数据范围

• ,
• ,

• 思路

      由题意知，当d处于a[x]与a[x+1]之间时，速度大小 v = (a[x+1] - a[x]) / (b[x+1] - b[x]),时间显然为 b[x] + (d - a[x]) / v,所以说问题就转化为了如何快速找到标志x.
      很容易想到二分查找，这边推荐使用二分查找的函数lower_bound(<起点>,<终点>,值)，其中起点和终点满足”左闭右开“，代码记得不要带浮点数，会产生精度问题.

  #include<bits/stdc++.h>
  #define int long long
  #define endl '\n' 
  #define INF 1e15
  using namespace std;
  typedef pair<int,int>pii;
  int a[100010], b[100010];
  signed main(){
      std::ios::sync_with_stdio(false);cin.tie(0);
      int t;cin >> t;
      while(t--){
          int n, k, q;cin >> n >> k >> q;
          for (int i = 1; i <= k;i++)cin >> a[i];
          for (int i = 1; i <= k; i++)cin >> b[i];
          while(q--){
              int d;cin >> d;
              int pos = lower_bound(a, a + k + 1, d) - a;
              //cout << pos << endl;
              if(d==a[pos]){
                  cout << b[pos] << " ";
              }else{
                  int ans = b[pos - 1] + (d - a[pos - 1]) * (b[pos] - b[pos - 1]) / (a[pos] - a[pos - 1]) ;
                  cout << ans << ' ';
              }
          }
          cout << endl;
      }
      return 0;
  }

  F.Circle Perimeter(数学)
  这题只需要枚举x的同时限定y的范围，但我用了dfs爆搜剪枝也确实能过

  题意

  给定一个整数r，找到与原点(0,0)间大于等于r但严格小于r+1的欧几里得距离的整数点数量.

  数据范围

思路

    不难发现，从数形结合的角度看，符合条件的点就是在半径为r与半径为r+1的圆之间的整数点。同时，这些点一定关于原点对称且相邻点之间一定连通。
    我们只需要找到一个象限内所有满足条件的点，数量乘以4就是最终答案。不妨令起始点为(r,0)，对八个方向进行搜索，搜索范围是第一象限内（不包含y轴），再使用一个bool类型的二维结构进行标记是否到达过.

Code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
int dx[] = {1, 1, 1, 0, 0, -1, -1, -1}, dy[] = {0, 1, -1, 1, -1, 1, 0, -1};
map<pii, bool> vis; //因为r的范围是1e5，直接使用数组会超内存
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t, r; cin >> t;
    auto dist = [&](int a, int b) -> double {
        return sqrt(a * a + b * b);
    };
    int cnt;
    auto dfs = [&](auto dfs, int x, int y) -> void {
        if (vis[{x, y}] || dist(x, y) < r || dist(x, y) >= r + 1 || x <= 0 || y < 0)
            return;
        vis[{x, y}] = 1;
        //cout << x << ' ' << y << endl;
        cnt++;
        for (int i = 0; i < 8;i++){
            int xx = x + dx[i], yy = y + dy[i];
            dfs(dfs, xx, yy);
        }
    };
    while(t--){
        cin >> r;
        cnt = 0;
        dfs(dfs, r, 0);
        cout << 4 * cnt << endl;
        vis.clear();
    }
    return 0;
}

G.XOUR(位运算)

题意

给定一个长度为n的非负整数数组a，对于下标< i ,j >，如果,那么可以交换和的位置。求通过任意次交换后字典序最小的序列.

数据范围

思路

    因为涉及到位运算，我们思路依旧是拆位。显然，异或的性质是两者不同取1，相同则取0，最后两位的权值是1和2，从倒数第三位开始只要两者取1，那么异或值一定不小于4。所以要使两者能进行交换，充要条件就是从右往左数的第三位开始的二进制位完全相同！
    不难想到，我们可以将所有第三位起的数状压成一个新的数；如果两个数状压的数相等，则我们将其归为同一组，同一组之间可以任意交换，所以我们将所有数分完组后只需要对同组进行升序排序，最后遍历数组从其组别中依次取数即可.

#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
vector<int> v[200010];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> a(n + 1), s(n + 1), tot(n + 1);
        map<int, int> mp;
        int cnt = 0;
        for (int i = 1; i <= n;i++){
            cin >> a[i];
            int sum = 0;
            for (int j = 31; j >= 2;j--){
                if ((a[i] >> j) & 1)
                    sum += (1LL << j);
            }
            s[i] = sum;
            if(!mp[sum]){
                cnt++;
                mp[sum] = cnt;
                v[cnt].push_back(a[i]);
            }else
                v[mp[sum]].push_back(a[i]);
        }
        for (int i = 1; i <= cnt;i++)
            sort(v[i].begin(), v[i].end());
        for (int i = 1; i <= n;i++){
            int pos = mp[s[i]];
            cout << v[pos][tot[pos]] << ' ';
            tot[pos]++;
        }
        cout << endl;
        for (int i = 1; i <= cnt;i++)
            v[i].clear();
    }
    return 0;
}