August 5 CSP-S Mock Trial Post-Game Wrap-Up
I. Doing the Questions
-
First Question Contest\(100pts\) Post-game\(AC\)
-
Second Question Contest\(20pts\) Post-game\(AC\)
-
Question 3 of the competition\(0(40)pts\) Post-game\(AC\)
-
Fourth Question Contest\(0(50)pts\) Post-game\(AC\)
-
Match Score\(120(210)/400 \ pts\) Post-game supplemental questions\(400 / 400 \ pts\)
II. Overview of the competition
Wait a minute to say why I added the parentheses.
The keyboard didn't feel very comfortable this time.
Unzip the big data, open the pdf file, overview once again, T1 surprisingly once no ideas, and then look at T2, T3, T4, more no ideas. Had to do T1, look carefully, simulated once, suddenly thought of ideas, this is not the two-way merger, immediately done!\(AC\)T2 was mixed up in his head and the simulation didn't write it, cheating on a score, expected\(20pts\)T3 couldn't figure it out for a long time, so I had to cheat on the points.\(40pts\)（Some of the scores are pretty high.), T4 took 20 min to read the question, was a bit of a misread, and ended up simulating a sample read and writing a viola that\(50pts\) The perfect ending.
(Now for the reason for the brackets, the first 15 mins after the game were getting ready to wrap up and unfortunately XX got the files mixed up, resulting in T3, T4)\(0pts\) sadness）
III. Problem solving reports
August 5 Mock Match Questions
T1：
Practice:
As stated above, it ismerge of two roads, which is really just a simulation, simulate the results.
Attachment: AC Code
#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) ;
(NULL) ; (NULL) ;
freopen ("" , "r" , stdin) ;
freopen ("" , "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 ;
}
/*
Practice if you can.
f**k €€￡
€€£Pearly Horse4(modal particle intensifying preceding clause)
5 3
1 4 2
5 3
1 2 5
3 4
1 2 3 4 5
*/
T2：
Practice:
I didn't realize it was also simulation. Just get yourself a stack, determine if it's ' (' or ')', do the simulation, and you're done.
Attachment: AC Code
#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) ;
(NULL) ; (NULL) ;
freopen ("" , "r" , stdin) ;
freopen ("" , "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：
Practice:
This one is.rucksacks A little more.greedpress\(p_i\) Arrangement, and then a backpack.
Attachment: AC Code
#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 > ;
}
signed main () {
ios::sync_with_stdio (false) ;
(NULL) ; (NULL) ;
freopen ("" , "r" , stdin) ;
freopen ("" , "w" , stdout) ;
/*
fu*k €€£,€€£Pearly Horse4(modal particle intensifying preceding clause),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：
Practice:
Observe that the structure that makes the answer non-zero must be such that there are some points hanging outside of a cluster, and then the points outside of the cluster are almost between
There are no sides.
Consider first solving for this cluster in the figure.
Delete the point with the smallest degree each time\(x\), just until the remaining points are all of the same degree, which can be done by using thesetMaintenance.
Attachment: AC Code
#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("", "r", stdin);
freopen("", "w", stdout);
ios::sync_with_stdio(0), (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++)
({tp[i] = deg[i], i});
while (()->first != prev(())->first)
{
int u = ()->second;
vis[u] = true;
(());
for (auto v : g[u])
{
if (vis[v])
cout << 0, exit(0);
({tp[v], v});
tp[v]--;
({tp[v], v});
}
}
int ans = 1;
for (auto v : s)
{
if (deg[] == (int)() - 1)
ans++;
int u = ;
for (auto vv : g[u])
{
if (!vis[vv])
continue;
if (deg[vv] == ())
ans++;
}
for (int i = 1; i <= n; i++)
{
if (vis[i])
if (deg[i] == deg[u])
ans++;
}
}
cout << ans;
}
IV. Post-competition summary
This one is still more satisfying, knowing that violence works wonders, and that it's important to hold steady and get the highest score possible in those times.
(Last Night, Sacrifice)