526互联

2023年度总结

发布时间 2023-12-31 17:10:52作者: liu_ruoyu

目录

Part 1:刷题

image
我的洛谷在这一年中一共刷了219题，当然，由于刷题的增多，我固然也从小绿名变更成了橙名

\[\sum\limits_{i=January}^{December}{Total \ number \ of \ practice \ questions=219} \]

在五、六、七月时，刷题比较低迷，主要是没怎么留时间刷题
今年，苦练最短路（上次普及组考试被最短路坑害了），我最终学会了：Floyd、SPFA、Dijkstra等基础算法外，还有二分图染色、分层图、最小圈、欧拉回路、差分约束、强连通分量等
今年，我A了我的第一道紫题、蓝题，紫题也突破了5题

这一年被坑得最惨的一题：P9748 [CSP-J 2023] 小苹果

我直接暴力枚举，导致普及组没拿奖qwq（真是暴力出奇寄）

Part 2:比赛

首先要说一件很重要的事情

在今年的CSP-S上，斩获二等奖！（这可是我第一次参赛啊！去年这时刚开始学结构体），只是可惜的是，第二题不小心写挂了，与一等奖失之交臂qwq
当然，还有模拟赛
image
等级分最高：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:数学

今年学了一些有趣的东西
image
众所周知

\[（\sqrt{x}-\sqrt{y})^2\geqslant 0 \]

所以

\[\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、成为红名巨佬

愿，每一个青春都将照亮梦想，每一个梦想都将成就青春

image