模拟三

模拟赛三补题报告

日期：\(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);
    }
  }
}

本栏目推荐文章
• spring与设计模式之三代理模式
• 聊一聊如何整合Microsoft.Extensions.DependencyInjection和Castle.Core(三)
• NUS CS1101S：SICP JavaScript 描述：三、模块化、对象和状态
• Ubuntu下运行LVGL模拟器
• 初中信息奥赛模拟测试
• 正则表达式复习三——修饰符
• STM32F103CB CAN启动失败 问题总结三
• 2023年第三届全国刑事技术技能大赛取证
• NES 模拟器中音画同步问题
• 聊一聊如何整合Microsoft.Extensions.DependencyInjection和Castle.Core(三)