8月5日CSP-S模拟赛赛后总结
\[8月5日 \ \ CSP-S模拟赛 \ \ 赛后总结 \\ 2024年8月5日 \\ by \ \ \ uhw177po \]一、做题情况
-
第一题比赛 \(100pts\) ，赛后 \(AC\)
-
第二题比赛 \(20pts\) ，赛后 \(AC\)
-
第三题比赛 \(0(40)pts\) ，赛后 \(AC\)
-
第四题比赛 \(0(50)pts\) ，赛后 \(AC\)
-
比赛得分 \(120(210)/400 \ pts\) ，赛后补题 \(400 / 400 \ pts\)
二、比赛概况
等一下说一说我为什么要加括号。
这次键盘感觉不太舒服。
把大数据解压后，打开 pdf 文件，总览一遍，T1竟然一遍没思路，再看T2、T3、T4，更没思路了。只好做T1，仔细看，模拟了一遍，突然想到思路了，这不就是二路归并吗，马上做完 \(AC\)。T2当时脑子混了，模拟没写出，骗了个分，预期 \(20pts\)。T3想了好久也不会，只好骗分 \(40pts\)（部分分给得挺高），T4花了20 min读题，有点读不懂，最终还是模拟样例读懂，写了个暴力，\(50pts\) 完美收场。
（现在说加括号的原因，赛后前15 min正准备收场，结果不幸被 XX 给把文件搞混了，导致T3、T4 \(0pts\) 悲）
三、题解报告
T1：
做法：
上文说了，是 二路归并，其实就是模拟，模拟一下结果就出来了。
附：AC代码
#include <bits/stdc++.h>
#define int long long
using namespace std ;
int n , m , l , r , a [100010] , mp [100010] , b [100010] , c [100010] , tot , cnt ;
signed main () {
ios::sync_with_stdio (false) ;
cin.tie (NULL) ; cout.tie (NULL) ;
freopen ("seq.in" , "r" , stdin) ;
freopen ("seq.out" , "w" , stdout) ;
cin >> n >> m ;
for (int i = 1 ; i <= m ; i ++) cin >> a [i] , mp [a [i]] ++ ;
for (int i = 1 ; i <= n ; i ++)
if (! mp [i]) b [++ tot] = i ;
l = r = 1 ;
while (l <= m && r <= tot) {
while (a [l] < b [r] && l <= m) {
c [++ cnt] = a [l] ;
l ++ ;
}
c [++ cnt] = b [r] ; r ++ ;
}
while (l <= m) c [++ cnt] = a [l ++] ;
while (r <= tot) c [++ cnt] = b [r ++] ;
for (int i = 1 ; i <= cnt ; i ++) cout << c [i] << "\n" ;
return 0 ;
}
/*
菜就多练
f**k €€￡
€€£梨马4了
5 3
1 4 2
5 3
1 2 5
3 4
1 2 3 4 5
*/
T2：
做法：
没想到也是模拟。自己弄一个栈，判断是' (' 还是 ')' ，进行模拟，就行了。
附：AC代码
#include <bits/stdc++.h>
#define int long long
#pragma G++ optimize (2)
#pragma G++ optimize (3)
using namespace std ;
int n , k , ans , t ;
char a [1000010] ;
signed main () {
ios::sync_with_stdio (false) ;
cin.tie (NULL) ; cout.tie (NULL) ;
freopen ("bracket.in" , "r" , stdin) ;
freopen ("bracket.out" , "w" , stdout) ;
cin >> n >> k >> a + 1 ;
for (int i = 1 ; i <= n ; i ++) {
if (a [i] == '(') {
if (t == k) t -- , ans ++ ;
else t ++ ;
}
else {
if (t == 0) t ++ , ans ++ ;
else t -- ;
}
}
cout << ans ;
return 0 ;
}
T3：
做法：
这道就是 背包 再加一点 贪心，按 \(p_i\) 排列，然后就是一道 背包 了。
附：AC代码
#include <bits/stdc++.h>
#define int long long
#pragma G++ optimize (2)
#pragma G++ optimize (3)
using namespace std ;
const int N = 1e5 + 10 ;
int n , k , ans , dp [N] ;
struct node {
int x , y ;
} a [N] ;
bool cmp (node q , node h) {
return q.y > h.y ;
}
signed main () {
ios::sync_with_stdio (false) ;
cin.tie (NULL) ; cout.tie (NULL) ;
freopen ("work.in" , "r" , stdin) ;
freopen ("work.out" , "w" , stdout) ;
/*
fu*k €€£,€€£梨马4了,money++
*/
cin >> n >> k ;
for (int i = 1 ; i <= n ; i ++) cin >> a [i].x ;
for (int i = 1 ; i <= n ; i ++) cin >> a [i].y ;
sort (a + 1 , a + 1 + n , cmp) ;
memset (dp , 31 , sizeof (dp)) ; dp [0] = 0 ;
for (int i = 1 ; i <= n ; i ++)
for (int j = 2e3 ; j >= 1 ; j --)
dp [j] = min (dp [j] , dp [j - 1] + a [i].x + a [i].y * (j - 1)) ;
for (int i = 2e3 ; i >= 1 ; i --)
if (dp [i] <= k) {
cout << i ; break ;
}
return 0 ;
}
T4：
做法：
观察发现，使得答案非零的结构一定是，一个团外面挂一些点，然后团外的点之间几乎
没有边。
考虑先求出图中的这个团。
每次删度数最小的点 \(x\)，直到剩下的点度数都相同即可，可以用set维护。
附：AC代码
#include <bits/stdc++.h>
using namespace std;
int n, deg[200005], tp[200005], m;
bool vis[200005];
vector<int> g[200005];
set<pair<int, int>> s;
signed main()
{
freopen("clique.in", "r", stdin);
freopen("clique.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(nullptr);
cin >> n >> m;
for (int i = 1, k, t; i <= m; i++)
{
cin >> k >> t;
g[k].push_back(t);
deg[k]++, deg[t]++;
g[t].push_back(k);
}
for (int i = 1; i <= n; i++)
s.insert({tp[i] = deg[i], i});
while (s.begin()->first != prev(s.end())->first)
{
int u = s.begin()->second;
vis[u] = true;
s.erase(s.begin());
for (auto v : g[u])
{
if (vis[v])
cout << 0, exit(0);
s.erase({tp[v], v});
tp[v]--;
s.insert({tp[v], v});
}
}
int ans = 1;
for (auto v : s)
{
if (deg[v.second] == (int)s.size() - 1)
ans++;
int u = v.second;
for (auto vv : g[u])
{
if (!vis[vv])
continue;
if (deg[vv] == s.size())
ans++;
}
for (int i = 1; i <= n; i++)
{
if (vis[i])
if (deg[i] == deg[u])
ans++;
}
}
cout << ans;
}
四、赛后总结
这把还是比较满意的，知道了暴力出奇迹，要拿稳，在这些时间内拿最高的分。
（最后一个晚上，祭）