目录
- Part 1:刷题
- Part 2:比赛
- Part 3:文章
- Part 4:数学
- Part 5:我的错题
- Part 6:回首过往，多少奋斗，多少牺牲；展望未来，多少憧憬，多少希望
- 愿，每一个青春都将照亮梦想，每一个梦想都将成就青春
Part 1:刷题
我的洛谷在这一年中一共刷了219题，当然，由于刷题的增多，我固然也从小绿名变更成了橙名
在五、六、七月时，刷题比较低迷，主要是没怎么留时间刷题
今年，苦练最短路（上次普及组考试被最短路坑害了），我最终学会了：Floyd、SPFA、Dijkstra等基础算法外，还有二分图染色、分层图、最小圈、欧拉回路、差分约束、强连通分量等
今年，我A了我的第一道紫题、蓝题，紫题也突破了5题
这一年被坑得最惨的一题：P9748 [CSP-J 2023] 小苹果
我直接暴力枚举，导致普及组没拿奖qwq（真是暴力出奇寄）
Part 2:比赛
首先要说一件很重要的事情
在今年的CSP-S上，斩获二等奖！（这可是我第一次参赛啊！去年这时刚开始学结构体），只是可惜的是，第二题不小心写挂了，与一等奖失之交臂qwq
当然，还有模拟赛
等级分最高：894
达成时间：2023-12-24
所属比赛：【LGR-169-Div.2】洛谷 12 月月赛 II & HCOI R1
排名：231（我还是太菜了，甚至前一百都没进）
Part 3:文章
我写的最好的一篇文章是Loj2537 「PKUWC2018」Minimax 「线段树合并+概率期望」
\[E(X)=\sum_{i=1}^n x_ip_i \]骰子的数学期望：$$E(X)=\dfrac{1}{6}(1+2+3+4+5+6)=3.5$$
Part 4:数学
今年学了一些有趣的东西
众所周知
所以
\[\sqrt{xy}\geqslant\frac{x+y}{2} \]Part 5:我的错题
一、P3831 [SHOI2012] 回家的路
由于题目给出有横向铁路和纵向铁路，而从横向换乘到纵向需要一个时间
于是我们给相邻的两个地铁站建边，若一个地铁站是换乘站（即，既有横向经过，又有纵向经过）我们就向他自己建个边，边权为1（因为换成需要一个时间）
于是，我们可以建两层图，即分层图
但是：一定要开2倍及以上空间（不然会寄，我就是如此）
上代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
const int MAXN=2e5+10;
ll n,m;
ll xs,ys,xe,ye;
ll S,E;
ll t;
bool vis[MAXN];
ll dis[MAXN];
struct node{
int x,y,id;
}p[MAXN];
struct que{
int d,w;
bool operator<(const que &res)const{
return w>res.w;
}
};
struct v{
int to,w;
};
vector<v>g[MAXN];
bool cmp1(node A,node B){
if(A.x == B.x){
return A.y < B.y;
}
return A.x<B.x;
}
bool cmp2(node A,node B){
if(A.y==B.y){
return A.x<B.x;
}
return A.y<B.y;
}
void dij(int start){
priority_queue<que>q;
while(!q.empty())q.pop();
memset(vis,0,sizeof(vis));
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[start]=0;
q.push(que{start,0});
while(!q.empty()){
que now=q.top();
q.pop();
int u=now.d;
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i].to;
int w=g[u][i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(que{v,dis[v]});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m+2;i++){
int xi,yi;
cin>>xi>>yi;
p[++t]={xi,yi,i};
}
sort(p+1,p+1+t,cmp1);
for(int i=2;i<=t;i++){
if(p[i].x==p[i-1].x){
g[p[i-1].id].push_back(v{p[i].id,2*abs(p[i].y-p[i-1].y)});
g[p[i].id].push_back(v{p[i-1].id,2*abs(p[i].y-p[i-1].y)});
// printf("add((%d , %d),(%d , %d))\n" , p[i-1].x , p[i-1].y , p[i].x , p[i].y);
}
}
sort(p+1,p+1+t,cmp2);
for(int i=2;i<=t;i++){
if(p[i].y==p[i-1].y){
g[p[i-1].id+t].push_back(v{p[i].id+t,2*abs(p[i].x-p[i-1].x)});
g[p[i].id+t].push_back(v{p[i-1].id+t,2*abs(p[i].x-p[i-1].x)});
// printf("add((%d , %d),(%d , %d))\n" , p[i-1].x , p[i-1].y , p[i].x , p[i].y);
}
}
for(int i=1;i<=t;i++){
g[i].push_back(v{i+t,1});
g[i+t].push_back(v{i,1});
}
dij(m + 1);
int ans = min(dis[t] , dis[2 * t]);
dij(t + m + 1);
int ans1 = min(dis[t] , dis[2 * t]);
cout << min(ans , ans1);
return 0;
}
二、P2071 座位安排
首先明确题意：我们来化简一下题意，发现，要求的就是一个二分图匹配，但是这里是一把椅子匹配两个人，所以，我们只需要把匹配数组开成二维，如果这个座位有零或一人坐，则匹配成功，否则，匹配失败
上代码
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
const int MAXN=200005;
int n,m;
vector<int>g[MAXN];
bool vis[MAXN];
int res[MAXN][2];
bool dfs(int x){
int u=x;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(!vis[v]){
vis[v]=1;
if(!res[v][0]||dfs(res[v][0])){
res[v][0]=u;
return 1;
}
if(!res[v][1]||dfs(res[v][1])){
res[v][1]=u;
return 1;
}
}
}
return 0;
}
int xiongyali(){
int ans=0;
for(int i=1;i<=n*2;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
return ans;
}
int main(){
cin>>n;m=2*n;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[i].push_back(u);
g[i].push_back(v);
}
cout<<xiongyali();
return 0;
}
三、P1352 没有上司的舞会
读题，发现：可以把两人看成两点，关系即为边，相邻的两点不可都去
所以就有了$$f[当前点][不去]=\max{f[儿子点][去],f[儿子的儿子][去]}$$
代码
#include<iostream>
#include<vector>
using namespace std;
const int MAXN=6e3+10;
int n;
int dis[MAXN];
int vis[MAXN];
int dp[MAXN][3];
vector<int>g[MAXN];
void dfs(int x){
dp[x][0]=0;
dp[x][1]=dis[x];
for(int i=0;i<g[x].size();i++){
int y=g[x][i];
dfs(y);
dp[x][0]+=max(dp[y][0],dp[y][1]);//自己不去，儿子可去可不去
dp[x][1]+=dp[y][0];//自己去，儿子一定不能去
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>dis[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[v].push_back(u);
vis[u]++;
}
int p=0;
for(int i=1;i<=n;i++){
if(vis[i]==0){
dfs(i);
p=i;
break;
}
}
cout<<max(dp[p][0],dp[p][1])<<"\n";
return 0;
}
Part 6:回首过往，多少奋斗，多少牺牲；展望未来，多少憧憬，多少希望
对2024年的展望：
1、A500题
2、拿下第一道黑体
3、csp提高组一等奖，最好是NOIP提高级
4、等级分上1300
5、成为红名巨佬
愿，每一个青春都将照亮梦想，每一个梦想都将成就青春
