7月21号模拟赛赛后总结
\[7月 \ 21号 \ 模拟赛 \ \ 赛后总结 \\ 2024年7月21日 \\ by \ \ \ hcy \]一、做题情况
-
第一题比赛 \(10pts\) ，赛后\(AC\)
-
第二题比赛 \(0pts\) ，赛后\(AC\)
-
第三题比赛 \(30pts\) ，赛后\(AC\)
-
第四题比赛 \(0pts\) ，赛后\(AC\)
-
比赛得分 \(40pts\) ，赛后补题 \(400/400 \ pts\)
二、比赛概况
T1 ：一眼暴力，先写好暴力，发现数据会 \(TLE\)，想到可以前缀和，理想：\(100pts\)，实际：不知道为什么RE了，赛后重打了一遍 \(AC\) 了，用时30 min。
T3 ：T2看了一点，看了5 min没看懂，先做T3。T3正解当时没想出（
分组背包没学过，悲），看到前部分数据能得\(30pts\)，就打了爆搜。 理想：\(30pts\) ，实际：\(30pts\) ，用时 1h。T4：不能用拓扑和dp，更别说什么DAG了。高斯消元是下午搞懂的，这题正好是高斯消元，不会，偏分。 理想：\(10pts\) （
骗分应该能骗10分吧） 实际：\(0pts\) 用时：20minT2：这道题光用搞懂题意就用了15 min，自己想不出用什么做，想了一些非正解，打了好久······ 理想：\(20pts\) ，实际：\(0pts\) ，用时：90 min
剩下40 min，检查用了30 min，剩下10 min自己交卷了。
三、题解报告
T1：
做法：
记\(s_i=(a_1+···+a_i) \ mod \ k\)
如果对于\(i,j\)，满足\(s_i=s_j\),那么子序列\(i+1···j\)是合法的。
从左往右求解即可。附：AC代码
#include <bits/stdc++.h> #define int long long #pragma G++ optimize (2) #pragma G++ optimize (3) using namespace std ; int T , k , n , ans , a [10000010] , f [10000010] ; main () { ios::sync_with_stdio (false) ; cin.tie (NULL) ; cout.tie (NULL) ; cin >> T ; while (T --) { cin >> k >> n ; ans = 0 ; memset (f , 0 , sizeof (f)) ; for (int i = 1 ; i <= n ; i ++) { cin >> a [i] ; a [i] += a [i - 1] ; f [a [i] % k] ++ ; } for (int i = 0 ; i < k ; i ++) ans += f [i] * (f [i] - 1) / 2 ; cout << ans + f [0] << "\n" ; } return 0 ; }T2：
做法：
考虑对一组特定的最终点权 \(a_i\) ，如何计算最小操作数。
对于叶子结点，一定可以一次操作将 \(0\) 变为 \(a_i\) 。将过一个点 \(i\) 的所有操作整合起来，满足加上的数之和等于 \(a_i\) ，且其父亲加上的数为 \([0,a_i]\) 中的一个整数值。
对于一个点 \(i\) ，设其子结点为 \(son\) ，若有 \(ai>∑a_{son}\) ，则必须有一次操作以该点为终点，反之可以从以其子孙为终点的操作中将该点点权减为 \(0\) 。
接下来是确定最终点权的最优值 \(a_i\) 。应用贪心思想，对于子结点，我们希望其 \(a_i\) 尽量大，这样其父亲更不容易占用一次操作。从叶子向根，对叶子结点 \(i\) ，我们将其点权赋值为 \(r_i\) ；对非叶子结点 \(x\) ，若 \(∑a_{son}>l_x\) ，则将该点赋值为 \(max{rx,∑a_{son}}\) ，不会增加操作且对后续影响最优；若 \(∑a_{son}≤l_x\) ，则该点必将占用一次操作，将点权赋值为 \(r_x\) ，后续最优。
时间复杂度 \(O(n)\) 。
附：AC代码
#include <bits/stdc++.h> #define int long long #pragma GCC optimize (2) #pragma GCC optimize (3) using namespace std ; const int N = 2e5 + 10 ; int n , a [N] , l [N] , r [N] , fa [N] , ans ; vector <int> f [N] , e [N] ; int dfs (int x) { int sum = 0 ; for (int i = 0 ; i < f [x].size () ; i ++) sum += dfs (f [x][i]) ; if (r [x] < sum) return r [x] ; if (l [x] > sum) { ans ++ ; return r [x] ; } return sum ; } signed main () { ios::sync_with_stdio (false) ; cin.tie (0) ; cout.tie (0) ; cin >> n ; for (int i = 2 ; i <= n ; i ++) { cin >> a [i] ; f [a [i]].push_back (i) ; } for (int i = 1 ; i <= n ; i ++) cin >> l [i] >> r [i] ; dfs (1) ; cout << ans ; return 0 ; }T3：
做法：
附：AC代码
#include <bits/stdc++.h> #define int long long #pragma G++ optimize (2) #pragma G++ optimize (3) using namespace std ; int n , m , k , a [5010] , b [5010] , x , lim [5010] , p [5010] , dp [5010] [5010] , ans [5010] [5010] ; vector <int> f [5010] ; signed main () { ios::sync_with_stdio (false) ; cin.tie (NULL) ; cout.tie (NULL) ; cin >> n >> m >> k ; for (int i = 1 ; i <= n ; i ++) { cin >> a [i] >> b [i] >> x ; f [x].push_back (i) ; p [x] += b [i] ; } for (int i = 1 ; i <= k ; i ++) cin >> lim [i] ; for (int i = 1 ; i <= k ; i ++) for (int j = 0 ; j < f [i].size () ; j ++) for (int k = min (p [i] , lim [i]) ; k >= b [f [i] [j]] ; k --) dp [i] [k] = max (dp [i] [k] , dp [i] [k - b [f [i] [j]]] + a [f [i] [j]]) ; for (int i = 1 ; i <= k ; i ++) for (int j = 0 ; j <= min (p [i] , lim [i]) ; j ++) for (int k = m ; k >= j ; k --) ans [i] [k] = max (max (ans [i - 1] [k] , ans [i] [k]) ,ans [i - 1] [k - j] + dp [i] [j]) ; cout << ans [k] [m] ; return 0 ; }
### T4：
#### 做法：
#### 附：AC代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[(int)1e6+6];
long long inv[(int)1e7+8],mod=19260817,ans;
bool cmp(int a,int b){
return a>b;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1,cmp);
inv[1]=(long long)1;
for(int i=2;i<=a[1];i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;i++)
for(int j=a[i];j>a[i+1];j--)
ans=(ans+a[i]*inv[a[1]-j+1])%mod;
cout<<ans;
return 0;
}
四、赛后总结
这把不行，要继续练习。
标签：5010,AC,21,int,long,ans,赛后,模拟 From： https://www.cnblogs.com/uhw177po/p/18314771