2024年四川省大学生程序设计竞赛 补题记录

Problem A. 逆序对染色（思维+树状数组）

• 难似我了
  

#include <bits/stdc++.h>using namespace std;#define int long longstruct BIT
{const int n;vector<int> tree;BIT(int n) : n(n), tree(n + 1) {};// 询问前x个数的和int Query(int x){int res = 0;for (int i = x; i > 0; i -= (i & -i)) res += tree[i];return res;}// 第l个位置+zvoid Modify(int l, int z){if (l <= 0) return;for (int i = l; i <= n; i += (i & -i)) tree[i] += z;}// 区间求和int rangeQuery(int l, int r){return Query(min(n, r)) - Query(max(0ll, l - 1));}
};void solve()
{int n; cin >> n;vector<int> a(n + 1), pos(n + 1);for (int i = 1; i <= n; i ++ ){cin >> a[i];pos[a[i]] = i;}vector<vector<int>> mem(n + 1);vector<bool> st(n + 1);for (int i = 1; i <= n; i ++ ){int t = pos[a[i] - 1] + 1;if (i >= t){mem[t].push_back(i);st[a[i]] = true;}}BIT bit(n);int ans = 0;for (int i = 1; i <= n; i ++ ){for (auto t : mem[i]) bit.Modify(a[t], 1);if (st[a[i]]) bit.Modify(a[i], -1);if (a[i - 1] + 1 <= a[i] - 1) ans += bit.rangeQuery(a[i - 1] + 1, a[i] - 1);}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

Problem B. 连接召唤（贪心）

• 贪心，优先1-5,2-4,3-3匹配，我的代码里单独考虑了出现23的情况，题解好像简单一些，但是能a的代码就是好代码 我就不重写了（

#include <bits/stdc++.h>using namespace std;#define int long longtypedef pair<int, int> PII;void solve()
{vector<int> cnt(6);for (int i = 1; i <= 5; i ++ ) cin >> cnt[i];int ans = 0;int minn = min(cnt[1], cnt[5]);ans += minn;cnt[1] -= minn; cnt[5] -= minn;minn = min(cnt[2], cnt[4]);ans += minn;cnt[2] -= minn; cnt[4] -= minn;ans += cnt[3] / 2;cnt[3] %= 2;auto cal = [&](int id){int need = 6 - id;int nw = 0;for (int i = 1; i < id; i ++ ){if (!cnt[i]) continue;int minn = min((nw + cnt[i]) / need, cnt[id]);cnt[i] -= (minn * need - nw); cnt[id] -= minn; for (int j = 1; j < i; j ++ ) cnt[j] = 0;ans += minn;nw = cnt[i];}if (nw != 0 && cnt[id]){int need = 6 - nw;int c = need / id;if (cnt[id] >= c){need -= c * id;if (need == 0){cnt[id] -= c;ans ++ ;for (int i = 1; i < id; i ++ ) cnt[i] = 0;}else{if (cnt[id] >= need){cnt[id] -= need;ans ++ ;for (int i = 1; i < id; i ++ ) cnt[i] = 0;}}}}if (id == 5) ans += cnt[id] / 2;else if (id == 4 || id == 2) ans += cnt[id] / 3;else if (id == 1) ans += cnt[id] / 6;cnt[id] = 0;};if (cnt[1] && cnt[2] && cnt[3]){cnt[1] -= 1; cnt[2] -= 1; cnt[3] -= 1;ans ++ ;if (cnt[2]) cal(2);if (cnt[1]) cal(1);}else if (cnt[2] && cnt[3] && cnt[5]){cnt[5] -- ; cnt[3] -- ;ans ++ ;if (cnt[5]) cal(5);if (cnt[2]) cal(2);}else if (cnt[2] && cnt[3]){if (cnt[2] >= 2){cnt[2] -= 2; cnt[3] -- ;ans ++ ;}if (cnt[2]) cal(2);}else{for (int i = 5; i >= 1; i -- ){if (cnt[i]) cal(i);}}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

Problem E. L 型覆盖检查器（模拟）

#include <bits/stdc++.h>
using namespace std;
#define int long longstring g[510];
pair<int, int> dx[] = {{-1, 0}, {0, 1}, {0, -1}, {-1, 0}};
pair<int, int> dy[] = {{0,1}, {1,0}, {1,0}, {0,-1}};
char fx[] = {'D', 'L', 'R', 'D'};
char fy[] = {'L', 'U', 'U', 'R'};void solve()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> g[i];g[i] = " " + g[i];}if (g[1][m] != '.') {cout << "No" << endl;return;}vector<pair<int, int>> cc;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (g[i][j] == 'C')cc.push_back({i, j});}}vector<vector<int>> st(n + 1, vector<int>(m + 1, 0));for (int i = 0; i < cc.size(); i++) {int a = cc[i].x, b = cc[i].y;st[a][b] = i + 1;for (int j = 0; j < 4; j++) {int x1 = a + dx[j].x, y1 = b + dx[j].y;int x2 = a + dy[j].x, y2 = b + dy[j].y;if (x1 < 1 || x1 > n || x2 < 1 || x2 > n)continue;if (y1 < 1 || y1 > m || y2 < 1 || y2 > m)continue;if (st[x1][y1] != 0) continue;if (st[x2][y2] != 0) continue;if (g[x1][y1] == fx[j] && g[x2][y2] == fy[j]) {st[x1][y1] = i + 1, st[x2][y2] = i + 1;}}}bool flag = 0;map<int, int> jk;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (i == 1 && j == m) continue;if (st[i][j] == 0){cout << "No" << endl;return;}jk[st[i][j]]++;}}for (auto bb : jk) {if (bb.y != 3) {cout << "No" << endl;return;}}cout << "Yes" << endl;
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

Problem F. 小球进洞：平面版（几何）

• 待补

Problem G. 函数查询

• 待补

Problem H. GG 和 YY 的石子游戏（签到）

#include<bits/stdc++.h>
using namespace std;
int t,m,ans;
long long n,a;
int main()
{scanf("%d",&t);for(int i=1;i<=t;i++){cin>>n;ans=0;if(n%3==0){ans=1;}a=(n/3)+n%3;cout<<ans<<" "<<a<<"\n";}return 0;
}

Problem L. 毛肚下清汤？（签到）

#include <bits/stdc++.h>using namespace std;#define int long longtypedef pair<int, int> PII;void solve()
{int n; cin >> n;priority_queue<PII, vector<PII>, greater<PII>> red, green;for (int i = 1; i <= n; i ++ ){int a, b, c, d; cin >> a >> b >> c >> d;if (c == 0 && d == 0) continue;else if (c == 1 && d == 0) red.push({a, i});else if (c == 0 && d == 1) green.push({b, i});else{if (a > b) green.push({b, i});else red.push({a, i});}}cout << red.size() << ' ';while (red.size()){auto t = red.top();red.pop();cout << t.second << ' ';}cout << '\n';cout << green.size() << ' ';while (green.size()){auto t = green.top();green.pop();cout << t.second << ' ';}cout << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}