模拟赛三补题报告
日期：\(2023\)—\(10\)—\(4\) 学号：\(S11390\)
一、总分：
\(T1\) 数字对应:\(100\)分
\(T2\) 技能学习:\(100\)分
\(T3\) 等于:\(0\)分
\(T4\) 最小方差:\(10\)分
共：\(210\) 分
二、比赛过程
-
在第一题中，数据范围较大，因此要用 \(map\) 映射来进行做题，我也想到了这种方法，成功 \(AC\)。
-
在第二题中，本题也是个模拟加上贪心的思想，我也是想到了正解，但是在调试代码的时候，耗费了挺长时间检查，在接着调试也没有调试成功，但在最后，花了一个小时，也是做了出来，成功 \(AC\)。
-
在第三题中，看到题后，没有啥思路，也是接着读了几遍，也没有啥思路，就准备骗分，但最后也没有骗着分，就得了 \(0\) 分。
-
在第四题中，看到题后，一想怎么这么简单？又读了几遍后，发现不是这么简单，但是一时也没有好的思路。就顺着思路做了一下，就是根据树的深度来做的，最终就骗了 \(10\) 分。
三、题目分析
\(T1\) 数字对应
本题就是用桶记录的思想来进行做的，只要在 \(a_i\) 和 \(b_i\) 都没有出现过的话，那就输出，否则的话，一直将 \(cnt++\)，直到这个数没有在 \(a_i\) 和 \(b_i\) 中出现，那么就输出。
-
若把 \(a_i\) 解释为 \(b_i\) 那么 \(a_i\) 必须永远对应 \(b_i\) 的数字，反过来也遵循规律。
-
但因为数据范围 \(a_i\) 太大，所以应该用 \(map\) 容器进行统计。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int n;
int a[N];
map<int ,int > mp,s;
int cnt=1;
signed main()
{
// freopen("digit.in","r",stdin);
// freopen("digit.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mp[a[i]]++;
}
for(int i=1;i<=n;i++)
{
if(s[a[i]]!=0)
{
cout<<s[a[i]]<<" ";
}
else
{
while(mp[cnt]!=0)
cnt++;
s[a[i]]=cnt;
mp[cnt]=1;
cout<<cnt<<" ";
}
}
cout<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T2\) 技能学习
一共有 \(n\) 个人，\(m\) 个人，如果在一个人的手中超过 \(k\) 个的话，那么就增加 \(k\) 个技能点，但注意一个人最多学 \(Q\) 个技能点，此时就要尽量的给别人技能点。我们要求 \(res_{max}\)。\(res_{max}\)就为最大值。
本题就是一个纯纯的编程题数学题，我们要先保证有同学得到的技能点数 \(>=k\)，此时就要舍去一些同学——min(n,m/k)。但是书会有剩余。因此我们要分情况讨论。
- 如果剩余的能平均分，那么就将剩下的分给人。
min((k+m/n)*t,Q)*n
- 如果剩余的不能平均分，那么就将剩下的一本一本的分，这个也有两种情况。
1. 能分到多余的
min((k+m/n+1)*t,Q)*cnt1
\(cnt1\) 表示能分到多余技能点的人数。
2. 不能分到多余的
min((k+m/n)*t,Q)*cnt2
\(cnt2\) 表示不能分到多余技能点的人数。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int n,m,k,q,t;
int res1,res2;
int cnt1,cnt2;
int minn,minx;
signed main()
{
freopen("skill.in","r",stdin);
freopen("skill.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k>>q>>t;
if(m<k)
{
cout<<0<<endl;
return 0;
}
// 一共所需的学习资料数量
if(n*k>m) //人数 * 需要学习资料数量 > 拥有的学习资料
{
n=m/k; //只让 m/n 个人学
//取出的最大值
}
m-=n*k; //减去消耗的数量 , 为剩下的数量
//cout<<"m "<<m<<endl;
if(m%n) //如果剩下的不能消耗完
{
res1=k+m/n+1; //还能够有剩余的学习资料数量 向上取整
cnt1=m%n; //此时为不能消耗完的人数
}
//如果剩下的能消耗完
//cout<<"m "<<m<<endl;
//cout<<"n "<<n<<endl;
//cout<<"m/n "<<m/n<<endl;
res2=k+m/n; //剩余的学习资料数量;
cnt2=n-cnt1; //此时为能消耗完的人数
//不能消耗完
//cout<<res1<<" "<<cnt1<<" "<<res2<<" "<<cnt2<<endl;
int p=res1*t; //能够增加技能点的数量 , 与最大 技能点 q 比较
minn=min(p,q)*cnt1;
//能消耗完
int e=res2*t; //能够增加技能点的数量 , 与最大 技能点 q 比较
minx=min(e,q)*cnt2;
cout<<minn+minx<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
\(T3\) 等于
第三题的思路也是很迷茫啊，本题就是通过模拟。本题有几种情况。
- 标记 \(1,-1,2,-2\) 出现的最后一次位置，通过等差数列算出数量。
$\frac{x\times (x+1)}{x} $
- 求序列 \(1,-1\) 和 \(2,-2\) 的情况
- \(2,-2\) 的情况，从第一次出现 \(2\) 或 \(-2\) 的最大值一直到最后都是，直接进行加和。
- \(1,-1\) 的情况，从第一次出现 \(1\) 或 \(-1\) 的最小值一直到第一次出现 \(2\) 或 \(-2\) 的最小值都是，进行加和。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
#define inf 0x3f3f3f3f
const int N = 1e6 + 10;
int n;
int a[N];
int nxt[N][5];
int ans;
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
memset(nxt,0x3f,sizeof nxt);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
//res表示相同数的数量
//lst表示此时数是啥
int res=1,lst=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]==lst)
{
res++;
}
else
{
//计算能够的相同数的数量
ans+=res*(res+1)/2;
//初始化为 1
res=1;
//此时数为 a[i]
lst=a[i];
}
}
//最后在算一下此时数的数量
ans+=res*(res+1)/2;
for(int i=n;i>=1;i--)
{
for(int j=0;j<=4;j++)
{
nxt[i][j]=nxt[i+1][j];
}
nxt[i][a[i]+2]=i;
}
for(int i=1;i<=n;i++)
{
int x1=nxt[i][-1+2];
int x2=nxt[i][1+2];
int x3=nxt[i][-2+2];
int x4=nxt[i][2+2];
int start1=max(x1,x2); //求以 -1 和 1 为起点的最大值
int end1=min(min(x3,x4),n+1);
//求以 -1 和 1 为终点
//求 2 和 -2 出现的最小值，在与序列最后 n+1 ，进行比较
if(start1!=inf&&start1<end1)
{
ans+=end1-start1;
}
int start2=max(x3,x4); //求以 -2 和 2 为起点的最大值
int end2=n+1;
// 求以 -2 和 2 为起点的终点就为序列的最后
if(start2!=inf&&start2<end2)
{
ans+=end2-start2;
}
}
cout<<ans<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T4\) 最小方差
第四题看到题目后，我进行套上了树的深度这个模板，发现这样做的话，只能得出根节点为 \(1\) 的这一种情况，其他的如果这样求的话，需要很高的时间复杂度，所以我就没有了什么好的思路，但是，也过了几组样例，也骗了 \(10\) 分。这正解我也不会，就摆上代码了哈……
正解——我也不明白
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int maxn = 1e5 + 10;
ll sum2[maxn], sum1[maxn], sz[maxn], n, res;
vector<int> G[maxn];
void dfs1(int u, int f) {
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == f)
continue;
dfs1(v, u);
sz[u] += sz[v];
sum1[u] += sum1[v];
sum2[u] += sum2[v];
}
sum2[u] += sz[u] + 2 * sum1[u];
sum1[u] += sz[u];
sz[u] += 1;
return;
}
void dfs2(int u, int f, ll s1, ll s2) {
res = min(res, n * (s2 + sum2[u]) - (sum1[u] + s1) * (sum1[u] + s1));
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == f)
continue;
ll ret1 = sum1[u] - (sum1[v] + sz[v]) + s1;
ll ret2 = sum2[u] - (sum2[v] + 2 * sum1[v] + sz[v]) + s2;
ll szu = n - sz[v];
dfs2(v, u, ret1 + szu, ret2 + 2 * ret1 + szu);
}
return;
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) {
G[i].clear();
sum1[i] = sum2[i] = sz[i] = 0;
}
for (int i = 1; i <= n - 1; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
res = LONG_LONG_MAX;
dfs1(1, 0);
dfs2(1, 0, 0, 0);
cout << res << endl;
}
return 0;
}
\(dfs\) 深度优先搜索
既然 \(T4\) 不会，那么我们就来水一个 \(dfs\) 的报告吧。
定义
\(dfs\) 能够遍历图和树的算法，俗称不撞南墙不回头，按照一定的规则排序，先扩展一步得到新状态，再继续递归扩展下去……如果无法扩展，则进行回退，如此搜索，直到找到目标。
过程
\(dfs\) 最显著的特征在于其递归调用自身。同时与 \(bfs\) 类似，\(dfs\) 会对其访问过的点做上标记，在遍历图时跳过已打过标记的点，以确保每个点仅访问一次。符合以上两条规则的函数，便是广义上的 \(dfs\)。
性质
该算法通常的时间复杂度为 \(O(n+m)\)，空间复杂度为 \(O(n)\)，其中 \(n\) 表示点数，\(m\) 表示边数。注意空间复杂度包含了栈空间，栈空间的空间复杂度是 \(O(n)\) 的。在平均 \(O(1)\) 遍历一条边的条件下才能达到此时间复杂度，例如用前向星或邻接表存储图；如果用邻接矩阵则不一定能达到此复杂度。
伪代码—大致结构
DFS(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。
在 v 上打访问标记
for u in v 的相邻节点
if u 没有打过访问标记 then
DFS(u)
end
end
end
伪代码—链式前向星遍历
void dfs(int u) {
vis[u] = 1;
for (int i = head[u]; i; i = e[i].x) {
if (!vis[e[i].t]) {
dfs(v);
}
}
}