2021 CCPC 桂林 ADEGIK
https://codeforces.com/gym/103409
女队vp。就做了四道比较签到的题，后续补了两题，感觉比较考察思维。本身的代码不难写。其中，D题要能明白那个贪心的思想，尽量把大的放在前面，并且要知道怎么才能把大的放在前面！！！K题非常神奇，想了半天但其实是直接在边权为1的最短路的基础上dfs每一条路求最小值。
A Hero Named Magnus （签到）
签到，记得开long long
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve () {
ll n;
cin >> n;
cout << 2ll * n - 1 << endl;
}
int main () {
int t;
cin >> t;
while (t--) solve ();
}
D. Assumption is All You Need （贪心）
我的丑丑示意图：
其实就是贪心思想，想要把大的数尽可能留在前面，所以就要按照左边吧的策略来交换，这样大的数最多会后移一位，不会对后面的交换造成更大影响。否则直接把大的一步换过去只会更劣。
个人觉得还是思维量不够，其实放cf上并不是一个多难的题，还是要多训！！
(这题cincout会超时)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int, int> pii;
const int N = 2025;
int n, a[N], b[N];
void solve () {
vector<pii> v;
scanf ("%d", &n);
for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf ("%d", &b[i]);
for (int i = 1; i <= n; i++) {
if (a[i] == b[i]) continue;
if (a[i] < b[i]) {
printf ("-1\n");
return ;
}
while (a[i] != b[i]) {
for (int j = i + 1; j <= n; j++) {
if (a[j] < a[i] && a[j] >= b[i]) {
swap (a[i], a[j]);
v.push_back ({i, j});
}
}
}
}
printf ("%d\n", v.size ());
for (auto i : v) printf ("%d %d\n", i.first, i.second);
}
signed main() {
int t;
scanf ("%d", &t);
while (t--) solve ();
}
E. Buy and Delete （求最小环）
如果一条边也选不了就0步。
否则就是找最小的环，如果能构造出来就两步，否则一步
求最小环的方法，每个点出发求一遍最短路，然后在回到起点的时候记录环的长度，综合求一个最小值。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int, int> pii;
const int N = 2005, M = 5005;
int h[N], e[M], ne[M], w[M], idx;
int dis[N], n, m, k, minn = 1e6;
bool vis[N];
void add (int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int dijkstra(int st) {
memset (dis, 0x3f, sizeof dis);
memset (vis, false, sizeof vis);
dis[1] = 0;
priority_queue<pii, vector<pii>, greater<pii>>q;
q.push({0, st});//dis num
int sum = 1e9 + 5;
while (!q.empty()){
auto t = q.top();
q.pop();
int num = t.second, distance = t.first;
if (vis[num]) continue;//pass
vis[num] = true;
for (int i = h[num]; i != -1; i = ne[i]){
int j = e[i];
if (j == st) sum = min (sum, distance + w[i]);
if (dis[j] > distance + w[i]){
dis[j] = distance + w[i];
q.push({dis[j], j});
}
}
}
return sum;
}
int main () {
memset (h, -1, sizeof h);
scanf ("%d%d%d", &n, &m, &k);
while (m--) {
int a, b, c;
scanf ("%d%d%d", &a, &b, &c);
add (a, b, c);
minn = min (minn, c);
}
if (minn > k) {
printf ("0");
return 0;
}
int sum = 1e9 + 5;
for (int i = 1; i <= n; i++) {
//if (vis[i]) continue;
sum = min (sum, dijkstra (i));
}
//cout << sum << endl;
if (sum <= k) printf ("2");
else printf ("1");
}
G. Occupy the Cities （二分）
这是我想的，二分最少时间
check的方法就是：假设当前要 check \(x\)，用变量 \(l\) 来记录碰到 \(1\) 之前的连续 \(0\) 个数，如果再碰到 \(1\) 之前 \(l > x\)，则 return false
在遇到 \(1\) 时又分为两种情况，一种是之前已经有一个 \(1\) （能影响左边的 \(l\) 个 \(0\) 了），那么可以把 \(l\) 清空。若之前没有 \(1\)，那么表示之前是 \(0...01\) 的形式，标记一下已经遇到了一个 \(1\)，这里用 \(find=1\) 表示遇到了 \(1\)。接着往后统计碰到 \(1\) 之后的连续 \(0\) 的数量 \(r\)。
\(r==x-1\) 时：若 \(l==x\)，这一段 \(1\) 就需要 \(x\) 天才能把左右的 \(0\) 给覆盖，从这开始断开，接着统计下一段
\(r==x\) 时：若 \(l<x\) 这一段 \(1\) 就需要 \(x\) 天才能把左右的 \(0\) 给覆盖，从这开始断开，接着统计下一段；否则 \(l==x\)，那么 这个 \(1\) 需要 \(x+1\) 天才能把左右长都为 \(x\) 的 \(0\) 给覆盖掉（其实这个会在 \(r==x-1\) 的情况中给判掉）
就按照上述去 \(check\)，如果最后还剩下 \(0\) 没消掉，那么就是不合法的。注意中间变量置 \(0\) 的小细节。
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int n;
string s;
bool check (int x) {
//cout << x << endl;
int l = 0, r = 0, find = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == '0') {
if (find) r++;
else l++;
}
else {
if (find) l = r = 0;
else find = 1;
}
if (l > x) return false;
if (find && r == x - 1) {
if (l == x) l = r = find = 0;
}
if (find && r == x) {
if (l < x) l = r = find = 0;
else return false;
}
//cout << l << ' ' << r <<' ' <<find <<endl;
}
if (l && !find) return false;
return true;
}
void solve () {
cin >> n >> s;
int cnt = 0;
for (int i = 0; i <n; i++) cnt += (s[i] == '0');
if (cnt == 0) {
cout << "0\n";
return ;
}
s = ' ' + s;
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (check (mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve ();
}
}
/*
5
15
010000010000010
8
10000100
9
100001000
10
1000010000
11
00010001000
*/
I. PTSD （贪心）
小贪心。从后往前用0，1来抵，如果当前数后面有多余的0，1就可选，否则选不上。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
string s;
void solve () {
cin >> n >> s;
s = ' ' + s;
ll c1 = 0, c0 = 0, ans = 0;
for (int i = n; i >= 1; i--) {
if (s[i] == '0') c0++;
else {
if (c0) ans += i, c0--;
else if (c1) ans += i, c1--;
else c1++;
}
}
cout << ans << endl;
}
int main () {
int t;
cin >> t;
while (t--) solve ();
}
K. Tax （bfs + dfs）
神秘题，本质就是大暴力，在边权为1的图上跑最短路，这样保证了不会绕路（走重复的某条边），即走这样的路一定是最优的，然后在最短路的基础上dfs每一条边算最短路即可，复杂度不会算，总之很神奇。
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 55, M = N * N;
int h[N], e[M], ne[M], w[M], idx;
int n, m, v[M], dis[N], ans[N], cnt[M];
bool vis[N];
void add (int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void dijkstra(){
memset (dis, 0x3f, sizeof dis);
dis[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>>q;
q.push({0, 1});//dis num
while (!q.empty()){
auto t = q.top();
q.pop();
int num = t.second, distance = t.first;
if (vis[num]) continue;//pass
vis[num] = true;
for (int i = h[num]; ~i; i = ne[i]){
int j = e[i];
if (dis[j] > distance + 1){ //视作边权为1
dis[j] = distance + 1;
q.push({dis[j], j});
}
}
}
}
void dfs (int u, int sum) {
ans[u] = min (ans[u], sum);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (dis[j] == dis[u] + 1) {
cnt[w[i]]++;
dfs (j, sum + cnt[w[i]] * v[w[i]]);
cnt[w[i]]--;
}
}
}
signed main () {
memset (h, -1, sizeof h);
scanf ("%lld%lld", &n, &m);
for (int i = 1; i <= m; i++) scanf ("%lld", &v[i]);
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf ("%lld%lld%lld", &a, &b, &c);
add (a, b, c), add (b, a, c);
}
dijkstra ();
//for (int i = 2; i <= n; i++) printf ("%d\n", dis[i]);
memset (ans, 0x3f, sizeof ans);
dfs (1, 0);
for (int i = 2; i <= n; i++) printf ("%lld\n", ans[i]);
}
B题set维护不太会写，J后缀树也不会www
