XP05-01 D01 分析
2025-08-12 21:24:59
发布于：浙江
上午大概进行了一些知识点的复习。
从普及组到提高组都有。我对一些可能不熟悉的知识点进行了记录：
普及组知识点：
素数相关：埃氏筛，欧拉筛，唯一分解定理。
树相关：树形DP，换根DP，最小生成树（KRUSKAL,PRIM）.
拓扑排序。
并且发现自己对XP04的各种摸板虽然会背，但是仅限于“看到题目会默”。
经常分不清树上查分，LCA,并查集，最小生成树等各种各样需要使用二进制进行优化的算法。
以上提到的这些点如果今天有时间就解决，实在不行XP05的集训结束后也必须解决。
接下来是下午的考试。
为自己的未来感到担忧。
今天的考试内容大概是这样组成的：模版+2题难度小于J组二题+1题难度小于S组二题+1题难度小于等于S组二题。
模版部分的问题刚刚已经提过。
后四题问题更多：这些题做大大小小只拿了，170...
170的构成：100+60+10+0
感觉问题大概是这样：首先我模版写完，还剩，完全不存在“时间不够”的问题，但是就是不想写，太颓废了（经过分析觉得可能是因为XP04燃尽了）。
然后就开摆了....
每一题就只想写暴力，第一题是后来发呆的时候碰巧想的，不然分会更难看。
第二题觉得如果想一想可能也能做，毕竟结论不难猜。
第三题数星星是能力问题，这样想更可怕。
第四题最后20分钟的时候以及慢的速度写了一个貌似能拿20分的代码，但样例没过，也没时间调了。
接下来详细分析：
T1：存在一些失误花了将近35分钟才写出来。主要原因是一直试图判断是否可以存入。
下次再遇到这类题可以更敏锐一些，肯定不是直接相乘的话，就从其他角度入手。
最终的方法是记录2的个数。
T2：快来数一数
这一题满分有两种方法：
1.哈希硬做
2.分析神秘规律
这里从分析神秘规律进行切入：
先看60pts做法：使用一些神秘STL（比如说,）
我当时考场上使用了拿了60，并尝试了哈希，但未果。
但发现同班同学似乎都在使用。但我不知道，所以现在就来补一下：
的作用是排序+去重。
定义：set<int>st
添加元素：st.insert(1)
删除元素：st.erase(2)
查找元素：st.find(1)(返回地址）
便利：
#include<bits/stdc++.h>
using namespace std;
set<int>se;
int main(){
se.insert(1);
se.insert(2);
se.insert(3);
se.insert(2);
se.insert(1);
for (auto it = se.begin (); it != se.end(); it ++) cout << *it << ' ';
cout << endl;
return 0;
}
然后就是做法：
比如说有一个这样的字符串：aaabbbccc
然后就可以试着分析一下：在哪种情况下，删除两个相邻的元素后，现有的字符串前面已经出现过。
挨个删除后，字符串大概是这样（部分）：
abbbccc
abbbccc（同）
aabbccc
aaabccc
aaabccc（同）
经过一些奇妙的观察过后发现规律：当时，删除和，就会与前面的重复。
但是这个猜测听起来不太可靠，所以就可以使用分段法（即判断的大小，能暴力的就直接暴力，不能暴力的就用一些不太靠谱的猜测或者更高级的算法，这样至少确保你能在赛制下拿到暴力分数，不会太惨）。
T3：数星星 这一题我在做的时候判断失误了，使用了一个中的神秘方向数组，并荣获，但是暴力解法实际上是能拿的。
现在先介绍一下的做法：对于每一个和，只要判断是否等于即可。
但是，这种做法不进行优化的话，是的，会超时，所以要思考如何优化。
做法：这种优化其实很常见：即找一对符合要求的数时要降低时间复杂度。
可以尝试两种方法：1. 2.二分（小于等于什么的要求）
这道题就是要用优化。
大概代码是这样：
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>ax[i]>>ay[i];
map<ll,ll>mp1,mp2,mp3,mp4;
for(int i=1;i<=n;i++){
mp1[ax[i]]++;
mp2[ay[i]]++;
mp3[ax[i]+ay[i]]++;
mp4[ax[i]-ay[i]]++;
}
long long ans=0;
for(int i=1;i<=n;i++){
ans+=mp1[ax[i]]+mp2[ay[i]]+mp3[ax[i]+ay[i]]+mp4[ax[i]-ay[i]]-4;
}
创建四个分别存储后判断即可。
但是需要注意很多数对的方案数是要考的。
T4：一张特别大的图
这道题听完讲解之后，我的收益还是比较大的。
让我对一些难题有了新的认知。
我个人的想法是在往后的CSP-S中的第二到三题，可能会去进行一些更深的挖掘。
大概流程是这样的：首先从一些特殊的测试点入手，去分析这个测试点这么出的意义，然后再从意义入手，想得分更高的写法。
因为我以前一直认为特殊测试点和正解没什么关系或是说有很大的区别，但是这道题（或是说之前的很多道题累加）让我产生了新的看法。
写的又点多了，直接开始看题吧：
首先测试点一到四可以使用明智的暴力枚举。
然后发现测试点九到十疑似是菊花图，菊花图大概长这样：
然后就可以分析一下它的性质：
在的时候，连通块的数量是1.
在的时候，连通块的数量是2.
在的时候，连通块的数量是9.（如图）
然后就都是9了。
再次研究测试点五到六，发现是一条线，大概长这样：
经过一些分析后发现一个点是否能对连通块数量做出贡献取决于其与其他点的最长距离。
然后联想到树的直径相关的知识，就可以开始写正解了。
正解大概就是3次DFS+前缀和/二分/双指针。
不过二分的时间复杂度会比前缀和高一点就是了。
代码是这样的：
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5;
vector<int>v[N];
int mm,max_mm;
int dis[N];
void dfs(int x,int c,int f){
dis[x]=max(c,dis[x]);
for(int i=0;i<v[x].size();i++){
if(v[x][i]==f)continue;
dfs(v[x][i],c+1,x);
}
if(c>max_mm){
max_mm=c;
mm=x;
}
return;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<n;i++){
int u,y;
cin>>u>>y;
v[u].push_back(y);
v[y].push_back(u);
}
dis[0]=-1;
dfs(1,0,0);
max_mm=0;
dfs(mm,0,0);
max_mm=0;
dfs(mm,0,0);
sort(dis+1,dis+1+n);
for(int i=1;i<=n;i++){
int k=upper_bound(dis+1,dis+1+n,i-1)-dis;
cout<<min(n,k)<<" ";
}
}
int main(){
solve();
return 0;
}
一个拓扑排序的复习：
拓扑排序是一个有向无环图上的应用。对DAG（有向无环图）上的每一个顶点进行排序，使得对于图中的每一条边（u->v），都存在节点u排在节点v前面。
例题：充满希望的课程安排
今日总结：
怎么说呢，压力挺大的吧，毕竟我一直想证明自己就算没有天赋也可以在OI上走的很远（一个想要参加校队两次被拒，数学似乎不怎么样，逻辑差的一批的唐比如是说）。虽然说今天小测验的结果似乎不错，但事实上这只是因为模版占了大半分数，我又刚从XP04出来的缘故。后面新的四道题目同上分析，我做的很差，我今年就是冲着S-1去的，但是居然连J-2的题都做不出来。真的很令人失望。
我从XP04出来的时候，我的同一寝室同班的同学都说我是有天赋的，说相信我在XP05也一样能拿好成绩。
但是说实话，我只是一个会死记硬背模版的人罢了，我的死记硬背，临时抱佛脚；在别人的日积月累的努力下漏洞百出了。
但觉得还是可以不断进步的。
这里空空如也
有帮助，赞一个