2021暑假模拟赛1

A[CF1028A(800)]

发现矩阵中心可以用一些较为简单的方式表示，这里求出左上角和右下角即可算出中心。

#include <bits/stdc++.h>
using namespace std;
const int INF = numeric_limits<int> :: max() / 2;
int main() {
  int N, M;
  cin >> N >> M;
  vector<string> S(N);
  for (int i = 0; i < N; ++i) {
    cin >> S[i];
  }
  int A = INF;
  int B = INF;
  int C = -INF;
  int D = -INF;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      if (S[i][j] == 'B') {
        A = min(A, i);
        B = min(B, j);
        C = max(C, i);
        D = max(D, j);
      }
    }
  }
  cout << (A + C) / 2 + 1 << ' ' << (B + D) / 2 + 1 << '
';
}

View Code

B[ARC065C(930)]

这个问题比较动态，所以考虑利用$dp$去做，设dp[i]表示是否能构成S[1...i]，那么转移是把题目中给的串拼接在后面，判断即可。

当然也可以使用贪心去做，本质上可以理解为将给出的串建立AC自动机然后在上面匹配，不过相比于$dp$稍微麻烦一些。

$dp$解法

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int n = s.size();

    vector<int> dp;
    dp.assign(n + 1, 0);

    vector<string> S = {"dream", "dreamer", "erase", "eraser"};
    
    dp[0] = 1;

    for(int i = 0; i < n; ++i) {
        for(auto& t : S) {
            int len = t.size();
            if(s.substr(i, len) == t) {
                dp[i + len] |= dp[i];
            }
        }
    }

    if(dp[n]) {
        cout << "YES" << '
';
    } else {
        cout << "NO" << '
';
    }
    return 0;
}

View Code

C[CF1368D(1700)]

用到了一个较为常用的结论:(X|Y)+(X&Y)=X+Y，于是发现操作本质上是把某一个二进制上的位从一个数传给另一个数。考虑最优情况，根据高中数学可以得知，平方数的和最大，肯定是将值尽量集中，也就是尽量先造出大的数，于是贪心解决即可，详见代码。这个结论也可以通过打表或手动构造发现，所以遇见一些题目的时候可以考虑打表。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> cnt(22);

    for(long long i : a) {
        for(int j = 0; j < 22; ++j) {
            if(i >> j & 1) {
                cnt[j] += 1;
            }
        }
    }

    long long ans = 0;

    for(int i = 0; i < n; ++i) {
        long long x = 0;
        for(int j = 21; j >= 0; --j) {
            if(cnt[j] > 0) {
                x += (1 << j);
                cnt[j] -= 1;
            }
        }
        ans += x * x;
    }

    cout << ans << '
';

    return 0;
}

View Code

D[1205B(1900)]

由于$N$比较大，所以直接做比较困难。但是仔细观察或手玩可以发现，如果存在三个数两两$and$不为$0$，那么答案就是$3$，这个条件转化一下也就是存在一个二进制位出现在$3$个数上。那么如果上面的条件不成立，可以推出一个二进制位只出现两次，那么就可以根据二进制位去建图和连边，问题转化为求一张$128$个点的图的最小环。关于最小环，利用$floyd$直接求出即可，具体详见$oiwiki$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, f, cnt;
int mp[maxn], d[155][155], s[155][155];
ll a[maxn];
void floyd() {
    memset(s, 0x3f3f, sizeof(s));
    for(int i = 1; i <= cnt; ++i)
        for(int j = 1; j <= cnt; ++j)
            s[i][j] = d[i][j]; 
    for(int k = 1; k <= cnt; ++k) 
        for(int i = 1; i <= cnt; ++i) 
            for(int j = 1; j <= cnt; ++j) 
                s[i][j] = min(s[i][j], s[i][k] + s[k][j]);
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    memset(d, 0x3f3f, sizeof(d));
    for(int t = 0; t <= 62; ++t) {
        int tot = 0, x = 0, y = 0;
        for(int i = 1; i <= n; ++i) if(a[i] & (1LL << t)) {
            ++tot;
            if(!x) x = i;
            else if(!y) y = i;
        }
        if(tot >= 3) {
            printf("%d
", 3);
            return 0;
        }
        if(tot < 2) continue;
        if(!mp[x]) mp[x] = ++cnt;
        if(!mp[y]) mp[y] = ++cnt;
        d[mp[x]][mp[y]] = d[mp[y]][mp[x]] = 1;
//        printf("%d <--> %d
", mp[x], mp[y]);
    }
    int ans = maxn;
    for(int x = 1; x <= cnt; ++x)
        for(int y = 1; y <= cnt; ++y) if(d[x][y] == 1) {
            d[x][y] = d[y][x] = 0x3f3f3f3f;
            floyd();
            ans = min(ans, s[x][y] + 1);
            d[x][y] = d[y][x] = 1;
        }
    printf("%d
", ans > n ? -1 : ans);
    return 0;
}

View Code