#西安理工大学2022年程序设计竞赛#

个人题解仅供参考
A
签到直接输出 2022XAUT

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout << "2022XAUT";
  return 0;
}

B
模拟计算正确率时转成 double

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    vector<vector<int>> a(2, vector<int>(2));
    cin >> n;
    for (int i = 0; i < n; i++) {
      string s, d;
      int x, y, z;
      int f = 0;
      cin >> s >> d >> x >> y >> z;
      int ans1 = 0, ans2 = 0;
      for (auto x1 : s) {
        ans1 += x1 - '0';
      }
      for (auto x2 : d) {
        if (x2 != '.') {
          ans2 += x2 - '0';
        }
      }
      int w = y / x;
      if (ans1 % 2 == 1) f++;
      if (ans2 >= 10) f++;
      if (w >= 7) f++;
      if (f >= 2 && z == 1) a[0][0]++;
      if (f >= 2 && z == 0) a[1][0]++;
      if (f < 2 && z == 1) a[0][1]++;
      if (f < 2 && z == 0) a[1][1]++;
    }
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        cout << a[i][j] << ' ';
      }
      cout << '\n';
    }
    if ((double)(a[0][0] + a[1][1]) / (double)(a[0][0] + a[0][1] + a[1][1] + a[1][0]) >= 0.8) {
      cout << "yes" << '\n';
    }
    else {
      cout << "no" << '\n';
    }
  }
  return 0;
}

C
分解质因数
set 套 set

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n);
  set<set<int>> s;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    set<int> t;
    for (int j = 2; j <= (int) sqrt(a[i]); j++) {
      if (a[i] % j == 0) {
        t.insert(j);
        while (a[i] % j == 0) {
          a[i] /= j;
        }
      }
    }
    if (a[i] != 1) {
      t.insert(a[i]);
    }
    s.insert(t);
  }
  cout << (int) s.size();
  return 0;
}

D
数据结构
st表 + 双指针

#include <bits/stdc++.h>

using namespace std;

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  F func;
  vector<vector<T>> st;
  SparseTable(const int& n, const F& f) : n(n), func(f) { st.resize(n, vector<T>(32 - __builtin_clz(n))); }
  template <typename M>
  inline void build(vector<M> a) {
    for (int i = 0; i < n; i++) {
      st[i][0] = a[i];
    }
    for (int j = 1; j < 32 - __builtin_clz(n); j++) {
      for (int i = 0; i < n - (1 << j) + 1; i++) {
        st[i][j] = func(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
      }
    }    
  }
  inline T get(int l, int r) {
    int lg = 32 - __builtin_clz(r - l + 1) - 1;
    return func(st[l][lg], st[r - (1 << lg) + 1][lg]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n);
  unordered_map<int, vector<int>> mp;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    mp[a[i]].push_back(i);
  }
  SparseTable<int> mn(n, [&](auto a, auto b) { return min(a, b); });
  mn.build(a);
  int ans = 0;
  for (auto [u, v] : mp) {
    int j = -1;  
    for (int i = 0; i < (int) v.size(); i++) {
      while (j + 1 < (int) v.size() && mn.get(v[i], v[j + 1]) >= a[v[i]]) {
        ++j;
      }
      if (i <= j) {
        ans = max(ans, v[j] - v[i] + 1);
      }
      j = max(j, i);
    }
  }
  cout << ans;
  return 0;
}

E
前缀和，二分

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
typedef long long LL;
#define debug(x) cout << "debug : " << x << endl;
 
//#define int long long
 
//#define LOCAL
 
int a[805][805];
int s[805][805];
int n, k;
bool check(int x) {
    int flag = k * k - (k * k / 2);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i][j] <= x);
        }
    }
 
    for (int i = k; i <= n; ++i) {
        for (int j = k; j <= n; ++j) {
            int t = s[i][j] - s[i - k][j] - s[i][j - k] + s[i - k][j - k];
            if (t >= flag) return true;
        }
    }
    return false;
}
 
void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }
 
    int l = 0, r = 1e9, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) {
            r  = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << l << endl;
//    cout << r << endl;
}
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T = 1;
//	cin >> T;
//	scanf("%d", &T);
	while (T--) {
		solve();
	}
 
}

F
二分
朋友可以重复选，选朋友朋友的心情要大于游戏的权重

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  while (m--) {
    int x, y;
    cin >> x >> y;
    if (x > y && a.back() > x) {
      auto p = upper_bound(a.begin(), a.end(), x);
      if (*p > x)  cout << *p << '\n';
      else p++, cout << *p << '\n';
    } else {
      cout << -1 << '\n';
    }
  }
  return 0;
}

G
动态规划

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

constexpr int mod = 1000000007;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  string s, t;
  cin >> s;
  t = "diplvebj";
  vector<i64> f(8);
  for (auto x : s) {
    if (x == t[0]) f[0]++;
    if (x == t[1]) f[1] = (f[0] + f[1]) % mod;
    if (x == t[2]) f[2] = (f[1] + f[2]) % mod;
    if (x == t[3]) f[3] = (f[2] + f[3]) % mod;
    if (x == t[4]) f[4] = (f[3] + f[4]) % mod;
    if (x == t[5]) f[5] = (f[4] + f[5]) % mod;
    if (x == t[6]) f[6] = (f[5] + f[6]) % mod;
    if (x == t[7]) f[7] = (f[6] + f[7]) % mod;
  }
  cout << f[7];
  return 0;
}

H
拓扑排序

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> g[n + 1];
  vector<int> in(n + 1);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    in[v]++;
  }
  priority_queue<int, vector<int>, greater<int>> q;
  for (int i = 1; i <= n; i++) {
    if (in[i] == 0) q.push(i);
  }
  vector<int> ans;
  while (!q.empty()) {
    int u = q.top();
    q.pop();
    ans.push_back(u);
    for (auto x : g[u]) {
      if (--in[x] == 0) q.push(x);
    }
  }
  if ((int) ans.size() == n) {
    for (int i = 0; i < n; i++) {
      cout << ans[i] << ' ';
    }     
  } else {
    cout << -1;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n + 1);
  function<void(int)> build = [&](int i) {
    if (i > n) return;
    cin >> a[i];
    build(i * 2);
    build(i * 2 + 1);
  };
  build(1);
  for (int i = 1; i <= n; i++) {
    cout << a[i] << ' ';
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
  for (int i = 0; i < n; i++) {
    char *p = (char *)&a[i];
    char *q = (char *)&a[i] + 1;
    char *t = (char *)&b[i];
    if (*p == *q)
      continue;
    if (*p == *t) {
      cout << "Little-Endian";
    } else {
      cout << "Big-Endian";
    }
    return 0;
  }
  cout << '?';
  return 0;
}

L
用 priority_queue 和 set 模拟即可

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, k;
  cin >> n >> k;
  set<int> s;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    s.insert(x);
  }
  priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<tuple<int, int, int, int>>> q;
  int ans = 0;
  for (auto it = s.begin(); it != prev(s.end()); it++) {
    q.push({*next(it) - *it, *next(it) + *it, *it, *next(it)});
  };  
  while ((int) s.size() > 1) {    
    auto [a, b, c, d] = q.top();
    q.pop();   
    auto itc = s.find(c);
    auto itd = s.find(d);
    if (itc == s.end() || itd == s.end()) {
      continue;
    }
    if (itc != s.begin() && next(itd) != s.end()) {
      q.push({*next(itd) - *prev(itc), *next(itd) + *prev(itc), *prev(itc), *next(itd)});
    }
    s.erase(*itc);
    s.erase(*itd);
    if (s.find(b % k) == s.end()) {
      s.insert(b % k);
      auto itnew = s.find(b % k);
      set<int>::iterator nextnew, prevnew;
      if (itnew != prev(s.end())) {
        nextnew = next(itnew);  
        q.push({*nextnew - *itnew, *nextnew + *itnew, *itnew, *nextnew});
      }
      if (itnew != s.begin()) {
        prevnew = prev(itnew); 
        q.push({*itnew - *prevnew, *prevnew + *itnew, *prevnew, *itnew});
      }
    }
    ans++;
  }
  cout << ans << '\n' << *s.begin() << '\n';
  return 0;
}