比赛链接:The 2023 Guangdong Provincial Collegiate Programming Contest
文章目录
A. Programming Contest(签到)
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
void solve()
{
int x1, x2;
cin >> x1;
int x; cin >> x;
vector<int> a(x);
for (int i = 0; i < x; i ++ ) cin >> a[i];
cin >> x2;
int ans = x2 - x1 + 1;
for (auto t : a)
{
if (t >= x1 && t <= x2) ans -- ;
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
B. Base Station Construction(单调队列优化dp)
设计状态 dp[i]
表示前 i 个位置满足条件,且第 i 个位置必选的最小代价,转移方程即为:
d
p
[
i
]
=
min
d
p
[
j
]
+
a
[
i
]
dp[i]=\min{dp[j]}+a[i]
dp[i]=mindp[j]+a[i],j 需要满足的条件是,
[
j
,
i
−
1
]
[j,\ i-1]
[j, i−1] 没有完整的区间限制
所以我们先在存储限制的时候记录下每个右端点对应的左端点,之后用单调队列更新当前能取的最大的 j
我们可以将 a[n + 1]
赋值为 0,这样最终答案即为 dp[n + 1]
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
const int N = 5e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
void solve()
{
int n; cin >> n;
vector<int> a(n + 2);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
a[n + 1] = 0;
vector<int> dp(n + 2);
int m; cin >> m;
vector<int> lt(n + 2);
for (int i = 1; i <= m; i ++ )
{
int l, r; cin >> l >> r;
lt[r] = max(l, lt[r]);
}
deque<int> dq;
dq.push_back(0);
for (int i = 1; i <= n + 1; i ++ )
{
dp[i] = dp[dq.front()] + a[i];
while (!dq.empty() && dp[dq.back()] > dp[i]) dq.pop_back();
dq.push_back(i);
while (!dq.empty() && dq.front() < lt[i]) dq.pop_front();
}
cout << dp[n + 1] << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
C. Trading(排序)
排序即可,便宜的买,贵的卖
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
void solve()
{
int n;
cin >> n;
vector<PII> a(n);
for (int i = 0; i < n; i ++ ) cin >> a[i].first >> a[i].second;
sort(a.begin(), a.end());
int sum = 0;
for (auto t : a) sum += t.second;
int cnt = sum / 2;
int sum1 = 0, sum2 = 0;
for (auto t : a)
{
if (t.second <= cnt)
{
sum1 += t.first * t.second;
cnt -= t.second;
}
else if (cnt > 0)
{
sum1 += cnt * t.first;
cnt = 0;
break;
}
else if (cnt <= 0) break;
}
cnt = sum / 2;
for (int i = n - 1; i >= 0; i -- )
{
if (a[i].second <= cnt)
{
sum2 += a[i].first * a[i].second;
cnt -= a[i].second;
}
else if (cnt > 0)
{
sum2 += cnt * a[i].first;
cnt = 0;
break;
}
else if (cnt <= 0) break;
}
cout << sum2 - sum1 << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
D. New Houses(枚举+排序)
根据二者的差值排序,然后枚举多少人没有邻居就可以了
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
void solve()
{
int n, m;
cin >> n >> m;
vector<PII> a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i].first >> a[i].second;
auto cmp = [&](PII a, PII b)
{
return a.second - a.first > b.second - b.first;
};
sort(a.begin() + 1, a.end(), cmp);
vector<int> pre1(n + 1), pre2(n + 1);
for (int i = 1; i <= n; i ++ )
{
pre1[i] = pre1[i - 1] + a[i].first;
pre2[i] = pre2[i - 1] + a[i].second;
}
int ans = 0;
for (int i = 0; i <= n; i ++ )
{
int j = n - i;
if (j == 1) continue;
if (j == 0 && (i - 1) * 2 + 1 > m) continue;
else if (j != 0 && i * 2 + j > m) continue;
int res = pre2[i] + pre1[n] - pre1[i];
ans = max(ans, res);
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
E. New but Nostalgic Problem(字典树)
从左到右确定答案的每一位,假设我们已经确定了前三位 abc
,开始枚举第四位,假设枚举到第四位为 g
,那么我们的取值是怎样的呢?
首先 abc[a-g]
随便取,因为他们的公共前缀对最终答案不造成影响,然后 abc[h-z]
每种情况只能取一个,因为只要取了两个,就不能保证最终公共前缀是 abcg
了
如果这样可以选择大于等于 k
个字符串,那么答案的前缀确定是 abcg
,如果不能,就要继续枚举第四个字符是其他的情况
前四位确定之后我们要看是不是只有四位呢?
如果答案只有四位的话,abcg[a-z]
每种情况最多取一个,看这样能不能取大于等于 k 个字符串,如果可以的话答案就是 abcg
,不能的话再继续枚举第五位
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
int idx, cnt[N], st[N], tr[N][26];
int newNode()
{
idx++;
st[idx] = cnt[idx] = 0;
memset(tr[idx], 0, sizeof(tr[idx]));
return idx;
}
void add(string s)
{
int p = 1;
// cnt[p] ++ ;
for (auto t : s)
{
int c = t - 'a';
if (!tr[p][c]) tr[p][c] = newNode();
p = tr[p][c];
cnt[p] ++ ;
}
st[p] ++ ;
}
void solve()
{
idx = 0;
newNode();
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i ++ )
{
string s;
cin >> s;
add(s);
}
int p = 1;
while (1)
{
int tmp = st[p];
for (int i = 0; i < 26; i ++ )
if (cnt[tr[p][i]]) tmp ++ ;
if (tmp >= k)
{
if (p == 1) cout << "EMPTY";
cout << '\n';
return;
}
for (int i = 0; i < 26; i ++ )
{
if (cnt[tr[p][i]])
{
tmp += cnt[tr[p][i]] - 1;
if (tmp >= k)
{
k -= tmp - cnt[tr[p][i]];
p = tr[p][i];
cout << (char)(i + 'a');
break;
}
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
F. Traveling in Cells(线段树+树状数组+二分)
首先看查询操作,很容易想到,就是要找包含起始点的最长子段,子段的左端点和右端点都可以通过二分找到
二分的check函数怎么写呢?以左端点为例,如果 [mid, x]
在集合内的颜色数是 x - mid + 1
个,说明这一段都是满足条件的,mid 可以继续往左搜索,否则往右搜索
现在我们需要的就是,查找 [l, r]
之间第 i
个颜色的出现次数,再把集合内的颜色累加一下得到答案,但是直接加会mle的很惨,所以考虑一下怎么优化
我们可以把所有颜色捡到一棵树上,用动态开点线段树,然后再存储一下每个颜色的树根结点,每次从这个颜色的根节点往下找就可以
最后用树状数组维护一下区间的权值和
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
const int N = 3e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n;
int c[N], v[N];
int rt[N], idx;
struct node
{
int ls, rs, sum;
} tr[N * 10];
void modify(int &u, int l, int r, int pos, int val)
{
if (!u) u = ++ idx;
if (l == r)
{
tr[u].sum += val;
return;
}
int mid = l + r >> 1;
if (pos <= mid) modify(tr[u].ls, l, mid, pos, val);
else modify(tr[u].rs, mid + 1, r, pos, val);
tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
}
int query(int u, int l, int r, int ql, int qr)
{
if (!u) return 0;
if (l >= ql && r <= qr) return tr[u].sum;
int mid = l + r >> 1;
int res = 0;
if (ql <= mid) res += query(tr[u].ls, l, mid, ql, qr);
if (qr > mid) res += query(tr[u].rs, mid + 1, r, ql, qr);
return res;
}
int ttr[N];
int lowbit(int x)
{
return x & -x;
}
void add(int pos, int val)
{
for (int i = pos; i <= n; i += lowbit(i))
ttr[i] += val;
}
int get_sum(int pos)
{
int res = 0;
for (int i = pos; i > 0; i -= lowbit(i)) res += ttr[i];
return res;
}
int get_sum(int l, int r)
{
return get_sum(r) - get_sum(l - 1);
}
vector<int> cq;
bool check(int l, int r, int cnt)
{
int res = 0;
for (auto t : cq)
res += query(rt[t], 1, n, l, r);
return res == cnt;
}
void get_ans()
{
int st, k;
cin >> st >> k;
cq.clear();
for (int i = 1; i <= k; i ++ )
{
int xx; cin >> xx;
cq.push_back(xx);
}
sort(cq.begin(), cq.end());
cq.erase(unique(cq.begin(), cq.end()), cq.end());
int l = 1, r = n;
int lr = st, rl = st;
while (l < lr)
{
int mid = l + lr >> 1;
if (check(mid, st, st - mid + 1)) lr = mid;
else l = mid + 1;
}
while (rl < r)
{
int mid = rl + r + 1 >> 1;
if (check(st, mid, mid - st + 1)) rl = mid;
else r = mid - 1;
}
cout << get_sum(l, r) << '\n';
}
void clear()
{
for (int i = 0; i <= idx; i++)
tr[i] = {0, 0, 0};
for (int i = 1; i <= n; i++)
rt[i] = ttr[i] = 0;
idx = 0;
}
void solve()
{
clear();
int q;
cin >> n >> q;
for (int i = 1; i <= n; i ++ )
{
cin >> c[i];
modify(rt[c[i]], 1, n, i, 1);
}
for (int i = 1; i <= n; i ++ )
{
cin >> v[i];
add(i, v[i]);
}
while (q -- )
{
int op, pos, x;
cin >> op;
if (op == 1)
{
cin >> pos >> x;
modify(rt[c[pos]], 1, n, pos, -1);
c[pos] = x;
modify(rt[c[pos]], 1, n, pos, 1);
}
else if (op == 2)
{
cin >> pos >> x;
add(pos, x - v[pos]);
v[pos] = x;
}
else get_ans();
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
I. Path Planning(二分)
输入的时候存储每一个数字所在的位置,然后二分,把路径存储下来,按 x 排序,判断 y 有没有不合理的地方即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
void solve()
{
int n, m;
cin >> n >> m;
vector<PII> pos(n * m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
int x; cin >> x;
pos[x] = {i, j};
}
auto check = [&](int x)
{
vector<PII> v;
for (int i = 0; i < x; i ++ )
{
v.push_back(pos[i]);
}
sort(v.begin(), v.end());
int tmp = v[0].second;
for (int i = 1; i < v.size(); i ++ )
{
if (v[i].second < tmp) return false;
tmp = v[i].second;
}
return true;
};
int l = 0, r = n * m;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << r << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
K. Peg Solitaire(DFS)
数据范围特别小,所以直接打暴力即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
void solve()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> g(n + 1, vector<int>(m + 1));
vector<vector<int>> st(n + 1, vector<int>(m + 1, -1));
for (int i = 0; i < k; i ++ )
{
int x, y;
cin >> x >> y;
g[x][y] = 1;
}
int res = 0;
int ans = 0;
function<void(int, int)> dfs = [&](int x, int y)
{
for (int i = 0; i < 4; i ++ )
{
int nx = x + dx[i], ny = y + dy[i];
int nnx = nx + dx[i], nny = ny + dy[i];
if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
if (nnx <= 0 || nny <= 0 || nnx > n || nny > m) continue;
if (g[nx][ny] == 1 && g[nnx][nny] == 0)
{
g[x][y] = 0;
g[nx][ny] = 0;
g[nnx][nny] = 1;
res ++ ;
ans = max(ans, res);
for (int ii = 1; ii <= n; ii ++ )
{
for (int jj = 1; jj <= m; jj ++ )
{
if (g[ii][jj] == 1) dfs(ii, jj);
}
}
g[x][y] = 1;
g[nx][ny] = 1;
g[nnx][nny] = 0;
res -- ;
}
}
};
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (g[i][j] == 1) dfs(i, j);
cout << k - ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}