CSUST-2018集训队湖南省赛选拔赛

时间:2022-12-20 23:30:44

省赛选拔,打之前觉得好神仙,打之中觉得这些题真tm都不错,打完之后看题解为什么这些傻逼题都没出,QAQ

记录一些值得学习的自我感觉有意义补的题

 

Day1。血崩3题

1001 搬东西 赛后补题(血亏)

给你2N+K个物品,可以选K个放在车上,剩下2N个自己搬,每次搬两个,消耗是两个物品的差的绝对值,求最小消耗

标程:DP。我:贪心+DP,一个(假)结论,应该之前是做过原题的

设dp(i,j)表示前i个物品,j个放在车上的最小消耗,答案是dp(2n+k,k),决策都是放车和不放车

标程给的转移是选相邻两个物品或者间隔一个的物品,不过好像我猜了一下最优解一定是相邻两个一起搬

所以dp方程就变成了:dp[i][j] = min(dp[i-1][j-1]/*表示放*/, dp[i-2][j] + (a[i]-a[i-1])/*表示搬*/)

可能是水过去的AC代码:

CSUST-2018集训队湖南省赛选拔赛CSUST-2018集训队湖南省赛选拔赛
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define INF 0x3f3f3f3f
 6 #define LL long long
 7 #define debug(x) cout << "[" << x << "]" << endl
 8 using namespace std;
 9 
10 const int mx = 1e5+25;
11 LL dp[2*mx][25];
12 int a[2*mx];
13 
14 int main(){
15     int n, k;
16     scanf("%d%d", &n, &k);
17     memset(dp, INF, sizeof dp);
18     for (int i = 1; i <= 2*n+k; i++) scanf("%d", &a[i]);
19     sort(a+1, a+n*2+k+1);
20     for (int i = 0; i <= k; i++) dp[i][i] = 0;
21     for (int i = 2; i <= n*2+k; i++){
22         for (int j = 0; j <= k; j++){
23             if (j) dp[i][j] = min(dp[i-1][j-1], dp[i][j]);
24             dp[i][j] = min(dp[i][j], dp[i-2][j]+a[i]-a[i-1]);
25         }
26     }
27     printf("%lld\n", dp[2*n+k][k]);
28     return 0;
29 }
View Code

 

1003 天气变化 / 1010 气温预测

这两道题居然是一起出的,比赛时放了后面一题,找一个数右边最后一个的比它大的数,前面是找右边第一个比它大的数

1010赛场上是线段树直接先往右子树再往左子树单点查询,1003更好写单调栈一下就行了

1003代码:

咕咕咕

 

1010比赛提交代码:

CSUST-2018集训队湖南省赛选拔赛CSUST-2018集训队湖南省赛选拔赛
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<stack>
 6 #define lid id << 1
 7 #define rid id << 1 | 1
 8 #define LL long long
 9 #define debug(x) cout << "[" << x << "]" << endl
10 using namespace std;
11 
12 const int mx = 1e6+5;
13 struct tree{
14     int l, r, m;
15 }tree[mx<<2];
16 int a[mx];
17 
18 void build(int l, int r, int id){
19     tree[id].l = l;
20     tree[id].r = r;
21     if (l == r){
22         tree[id].m = a[l];
23         return;
24     }
25     int mid = (l+r)>>1;
26     build(l, mid, lid);
27     build(mid+1, r, rid);
28     tree[id].m = max(tree[lid].m, tree[rid].m);
29 }
30 
31 int query(int id, int x, int i){
32     if (tree[id].m <= x) return i;
33     if (tree[id].l == tree[id].r) return tree[id].l;
34     if (x < tree[rid].m) return query(rid, x, i);
35     else return query(lid, x, i);
36 }
37 
38 int main(){
39     int n;
40     scanf("%d", &n);
41     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
42     build (1, n, 1);
43     for (int i = 1; i <= n; i++){
44         int ans = query(1, a[i], i);
45         if (ans <= i) ans = i;
46         if (i == 1) printf("%d", ans-i);
47         else printf(" %d", ans-i);
48     }
49     printf("\n");
50     return 0;
51 }
View Code

 

1009 模和最大

给一个数列a,对每个a[i]找一个j != i,使得(a[i]+a[j])%p最大,输出这个值

数据保证a[i] < p

通过小于p可以知道任意两个数的和不超过2p,二分找加起来小于p的最大值,再取一个最大的值相加,取max一定是正解

需要处理一下边界各种细节,赛场上的代码比较乱,也不改了,能出的快就行

CSUST-2018集训队湖南省赛选拔赛CSUST-2018集训队湖南省赛选拔赛
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define LL long long
 6 #define debug(x) cout << "[" << x << "]" << endl
 7 using namespace std;
 8 
 9 const int mx = 1e6+5;
10 int ans[mx], b[mx];
11 
12 struct node{
13     int id, num;
14     bool operator < (const node& a) const{
15         return num < a.num;
16     }
17 }a[mx];
18 
19 int main(){
20     int n, k;
21     scanf("%d%d", &n, &k);
22     for (int i = 1; i <= n; i++) {
23         scanf("%d", &a[i].num);
24         a[i].id = i;
25     }
26     sort(a+1, a+n+1);
27     for (int i = 1; i <= n; i++) b[i] = a[i].num;
28     for (int i = 1; i <= n; i++){
29         int s = upper_bound(b+1, b+n+1, k-1-b[i])-b;
30         if (b[s] > k-1-b[i]) s--;
31         if (!s) s = n;
32         if (i == s) s--;
33         if (!s) s = n;
34         ans[a[i].id] = (b[i]+b[s])%k;
35         if (i == n) ans[a[i].id] = max(ans[a[i].id], (b[n]+b[n-1])%k);
36         else ans[a[i].id] = max(ans[a[i].id], (b[i]+b[n])%k);
37     }
38     for (int i = 1; i <= n; i++){
39         if (i == 1) printf("%d", ans[i]);
40         else printf(" %d", ans[i]);
41     }
42     printf("\n");
43     return 0;
44 }
View Code

 

Day2 5题 比第一次简单好歹还能抢救一下我

赛前还听说这场全都是神仙题,吓死了QAQ

 

1011 神秘群岛

给一棵树,边是双向的且权值不同,每条边每个方向只能走一次,q次询问u到v能走到的最大边权

n,q 1e5

画个图可以发现除了v到u的简单路径,其它所有的边权都能收集到,跟LCA求链长的区别就是在dfs的时候多算了一条反向边

CSUST-2018集训队湖南省赛选拔赛CSUST-2018集训队湖南省赛选拔赛
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<iostream>
 6 #define INF 0x3f3f3f3f
 7 #define LL long long
 8 #define debug(x) cout << "[" << x << "]" << endl
 9 using namespace std;
10 
11 const int mx = 1e5+5;
12 int d[mx][2], p[mx][30], pa[mx], rk[mx];
13 int n;
14 
15 struct edge{
16     int v, w, b;
17     edge(int v = 0, int w = 0, int b = 0): v(v), w(w), b(b){}
18 };
19 vector<edge> G[mx];
20 
21 void dfs(int u, int fa, int cnt){
22     pa[u] = fa;
23     rk[u] = cnt;
24     int len = G[u].size();
25     for (int i = 0; i < len; i++){
26         int v = G[u][i].v;
27         if (v != fa){
28             d[v][0] = d[u][0]+G[u][i].w;
29             d[v][1] = d[u][1]+G[u][i].b;
30             dfs(v, u, cnt+1);
31         }
32     }
33 }
34 
35 void LCA(){
36     for (int i = 1; i <= n; i++){
37         p[i][0] = pa[i];
38         for (int j = 1; (1<<j) <= n; j++) p[i][j] = -1;
39     }
40     for (int j = 1; (1<<j) <= n; j++)
41         for (int i = 1; i <= n; i++)
42             if (p[i][j-1] != -1) p[i][j] = p[p[i][j-1]][j-1];
43 }
44 
45 int query(int x, int y){
46     if (rk[x] < rk[y]) swap(x, y);
47     int k;
48     for (k = 0; (1<<(k+1)) <= rk[x]; k++);
49     for (int i = k; i >= 0; i--)
50         if (rk[x] - (1<<i) >= rk[y]) x = p[x][i];
51     if (x == y) return x;
52     for (int i = k; i >= 0; i--){
53         if (p[x][i] != -1 && p[x][i] != p[y][i]){
54             x = p[x][i];
55             y = p[y][i];
56         }
57     }
58     return p[x][0];
59 }
60 
61 
62 int main(){
63     int t, q, u, v;
64     scanf("%d", &t);
65     while (t--){
66         int a, b;
67         LL sum = 0;
68         scanf("%d", &n);
69         memset(d, 0, sizeof d);
70         for (int i = 0; i <= n; i++) G[i].clear();
71         for (int i = 1; i < n; i++){
72             scanf("%d%d%d%d", &u, &v, &a, &b);
73             G[u].push_back(edge(v, a, b));
74             G[v].push_back(edge(u, b, a));
75             sum += (a+b);
76         }
77         dfs(1, -1, 0);
78         LCA();
79         scanf("%d", &q);
80         while (q--){
81             scanf("%d%d", &u, &v);
82             int c = query(u, v);
83             printf("%lld\n", sum-(d[u][0]+d[v][1]-d[c][1]-d[c][0]));
84         }
85     }
86     return 0;
87 }
View Code

 

1012 笑脸

一个只有:)(的字符串,:)看做笑脸,现在可以将一个前缀翻转一次,求最多能得到多少个笑脸

跑一遍笑脸和反笑脸【(:】的前缀和,枚举断点,要注意边界情况,WA了好几次。。。

CSUST-2018集训队湖南省赛选拔赛CSUST-2018集训队湖南省赛选拔赛
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define LL long long
 6 #define debug(x) cout << "[" << x << "]" << endl
 7 using namespace std;
 8 
 9 const int mx = 2e5+10;
10 char s[mx];
11 int a[mx], b[mx];
12 
13 int main(){
14     int n;
15     scanf("%d%s", &n, s+1);
16     for (int i = 1; i <= n; i++){
17         if (s[i-1] == ':' && s[i] == ')') a[i] = a[i-1]+1;
18         else a[i] = a[i-1];
19         if (s[i-1] == '(' && s[i] == ':') b[i] = b[i-1]+1;
20         else b[i] = b[i-1];
21     }
22     int ans = a[n];
23     for (int i = n; i >= 0; i--){
24         if (s[i] == ':' && s[1] == ':') {
25             ans = max(ans, a[n]-a[i]+b[i]);
26             continue;
27         }
28         else {
29             if (s[i] == ':' && s[i+1] == ')' && s[1] != ':'){
30                 ans = max(ans, a[n]-a[i]+b[i]-1);
31                 continue;
32             }
33             if (s[i] != ':' && s[1] == ':' && s[i+1] == ')'){
34                 ans = max(ans, a[n]-a[i]+b[i]+1);
35                 continue;
36             }
37         }
38         ans = max(ans, a[n]-a[i]+b[i]);
39     }
40     printf("%d\n", ans);
41     return 0;
42 }
View Code