CSP-J 第二轮 模拟赛三补题报告

日期:2023年10月3日 星期二

学号：s07246

姓名：江守栋

目录

·  比赛概况        

·  比赛过程

·  题目分析

T1 【数字对应 digit】

1、题目大意

2、比赛中的思考

3、解题思路

4、AC代码

T2【技能学习 skill 】

1、题目大意

2、比赛中的思考

3、解题思路

4、AC代码

T3【等于 equal】

1、题目大意

2、比赛中的思考

3、解题思路

4、AC代码

T4 【最小方差 variance】

1、题目大意

2、比赛中的思考

3、解题思路

4、AC代码

· 赛后总结

---

·  比赛概况        

        总分：210分

        T1 【数字对应 digit】100

        T2 【技能学习 skill】 100

        T3 【等于 equal】10

        T4 【最小方差 variance】0

·  比赛过程

 今天的比赛吸取了昨天的经验，按照顺序做的

T1 最开始想用桶去做，但是看了眼数据感觉会爆，所以改变思路，AC了

T2 看到题就感觉应该是贪心，认真读题后发现其实是一道数学题，肝了30分钟后也成功AC

T3 发现好像很难的样子，尝试DP后发现写不出来，就拿了数据范围里的特殊部分分

T4 我这个小蒟蒻根本读不懂题，直接输出的样例

·  题目分析

T1 【数字对应 digit】

1、题目大意

        给定一个长度为  的序列 ，让序列  的每个数字对应一个正整数，组成序列 。

         序列 里的数字不能在序列  里出现过，序列  中的第  个整数与序列  中的第  个数对

        应，对应关系可随意指定，但是必须一一对应

        输出字典序最小的序列

2、比赛中的思考

        刚开始看到 可随意指定 时以为比较难做，后来发现其实很简单，一开始想用桶去做题，但

        数据量太大，桶会炸，我陷入了沉思...

        就在这时，我想到了Y1学到的STL库中的 map ，将桶换成map,直接AC

3、解题思路

        定义两个 map 一个用来存原数组中的元素出现的次数，一个用来存第 i 个位置对应的元素。

        边输入边桶标记，然后循环处理，如果该位置被更新过则直接输出，否则从前往后找第一个

        没有出现的元素，并将其标记为已出现，输出即可。

4、AC代码

        

#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
map<int,int> b,t;
int main()
{freopen("digit.in","r",stdin);freopen("digit.out","w",stdout);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];t[a[i]]++;}int x=1;for(int i=1;i<=n;i++){if(b[a[i]]){cout<<b[a[i]]<<' ';}else{while(t[x]!=0) x++;t[x]=1;b[a[i]]=x;cout<<b[a[i]]<<' ';}}fclose(stdin);fclose(stdout);return 0;
}

        

T2【技能学习 skill 】

1、题目大意

        n个同学学习新技能。
        有m份资料，可以随意分给每位同学。
        同学的资料不足k分将无法学习。
        同学拿到p份资料，每分钟增长p个技能点，
        但上限为q。
        共有t分钟，求同学们的技能点数之和最大值。

2、比赛中的思考

        看到数据范围后就觉得此题非常之不对劲，研究样例后发现其实就是一道数学题，也是直接

        AC

        鬼知道我调了多久

3、解题思路

        因为数据很大，所以我没有想别的，当成一道数学题来做的，直接一手阳寿算法，时

        间复杂度，告别超时，分类讨论所有情况

        1.每人分 k 份足够分，有剩余

           此时每人分 k 份之后将剩余的平均分给每个人

        2.每人分 k 份不够分

           舍弃不够分的人，每人分 k 份，将不够 k 份的平均分给那些已经有 k 份资料的人

        3.每人分 k 份足够分，无剩余

           正好每个人分 k 份，实现共同富裕

4、AC代码

        

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,q,t,x,y;
int main()
{freopen("skill.in","r",stdin);freopen("skill.out","w",stdout);cin>>n>>m>>k>>q>>t;if(n*k>m){n=m/k;m%=k;x=k+m/n;y=m%n;}if(n*k==m){x=k;	}if(n*k<m){m=m-n*k;x=k+(m/n);y=m%n;}if(x*t>=q){cout<<n*q;}else if(x*t<q && (x+1)*t>=q){cout<<y*q+(n-y)*x*t;}else{cout<<n*x*t+y*t;}fclose(stdin);fclose(stdout);return 0;
}

T3【等于 equal】

1、题目大意

        给定一个长度为n的序列，序列里每个元素属于-2，-1，1，2中的一个。
        请问多少个子数组满足最大值的绝对值等于最小值的绝对值。

2、比赛中的思考

        完全没有思路，一开始想用二维dp拿部分分的，但是有点难写，后来尝试另一个特殊情况

另有 10% 数据：所有数字的绝对值相等 

         直接判断的上面这个情况，拿了十分，但是赛后发现其实还可以再拿下面这个情况的十分

另有 10% 数据：所有数字均为正整数

        如果加上判断，这十分应该也可以拿到 （白丢10分 QwQ）

3、解题思路

        赛后听了老师的讲解，逐渐有了写头绪，大体可以分为三种情况：

        1.   子数组的数字完全相同

        2.   最小值-1，最大值1

        3.   最小值-2，最大值2

        统计这三种情况分别有多少子序列，输出即可

        

4、AC代码

#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=5e5+10;
const int inf=0x3f3f3f3f;
int n;
ll ans,num[maxn];
int nxt[maxn][5];
ll startpos,endpos;
int main(){cin>>n;memset(nxt,0x3f,sizeof nxt);for(int i=1;i<=n;i++){cin>>num[i];}ll cnt=1,lst=num[1];for(int i=2;i<=n;i++){if(num[i]==lst){++cnt;}else{ans+=cnt*(cnt+1)/2;cnt=1;lst=num[i];}}ans+=cnt*(cnt+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][num[i]+2]=i;int maxpos1=nxt[i][1+2];int maxpos2=nxt[i][2+2];int minpos1=nxt[i][-1+2];int minpos2=nxt[i][-2+2];startpos=max(maxpos2,minpos2);endpos=n+1;if(startpos!=inf&&startpos<endpos){ans+=endpos-startpos;}startpos=max(maxpos1,minpos1);endpos=min(min(maxpos2,minpos2),n+1);if(startpos!=inf&&startpos<endpos){ans+=endpos-startpos;}}cout<<ans;return 0;
}

T4 【最小方差 variance】

1、题目大意

        给定一个无根树T。
        T含有N个点，N-1条边，边权全部为1。
        在T中找一个树根root。
        树根确定后计算出每个点到root的距离，得到一个长度为n的序列a。
        请让序列a的方差最小。
        输出的方差乘以n方。

2、比赛中的思考

        不会，直接输出样例    （题都读不懂的啊喂）

3、解题思路

        使用 vector 存储每个点的邻接点，然后从1作为根开始 DFS。

        当某一个结点作为根时，方差的答案有两个贡献，一个是该结点作为根所在的子树的贡献

         一个是当前点上方的祖先结点的贡献，所以需要 DFS 两次

4、AC代码

#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;}
}

· 赛后总结

        今天的题目相比昨天，难度其实差不多

        第一题，用桶标记会炸，但我想到了 map ,所以有时候做题不要在一种方法上死磕，要及时

        尝试转变思路，说不定就找到了正确的解法。

        第二题，是一道纯数学题，我一开始对着样例想了好久，但思路依旧很乱，但后来我拿出了

        草稿纸和笔，在纸上演算了几遍，不一会就找到了正确的思路

        当你没有思路的时候，就不要再凭空想象了，这个时候，纸笔就是你最好的战友。

        第三题，这种难题我并不是奔着100分去的，而是瞄准了部分分，但是赛时我只专门想了一种

        情况，只得了10分，但其实还有一类特殊数据我可以拿到分，我完全可以在输入时判断一下

        ，分为两种不同的情况，再去采用不同的骗分、暴力策略。所以即使是暴力求解，也要看清

        楚数据范围，说不定就漏掉了哪一类明明可以拿到分的数据呢，这种时候，因为粗心丢掉的

        10分20分很可能就决定了你是一等奖还是二等奖

        第四题我压根看不懂题，只能输出样例，可奈何这是多组样例，一分也没骗到（悲）

        今天的比赛让我收获了很多，我一定会继续巩固提升自己，在考试时把自己的思路打开，

        利用好草稿纸这件法宝。明天的比赛，我定会再接再厉，考出自己理想的分数！