2024tysc1046

UID: 13313, 注册于 2024-6-14 13:23:37, 最后登录于 2025-11-28 18:43:14, 目前离线.

解决了 956 道题目，RP: 289.59 (No. 8)

♂

个人简介

每一粒星光，都曾在黑暗中淬炼。

<details>
<summary>细节标题</summary>
细节内容
</details>

代码模板

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	return 0;
}

LaTeX数学公式大全

https://www.luogu.com.cn/article/1gxob6zc

一些模版

前向星

/*
链式前向星，数组模拟静态链表 
优点：访问效率高，空间小，方便删边  
缺点：代码复杂 
*/
#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v,next;
}a[10005];
int head[10005],n,m,u,v,vis[10005],tot;
void addedge(int u,int v){
	a[++tot].u=u;
	a[tot].v=v;
	a[tot].next=head[u];
	head[u]=tot;
}
void dfs(int u){
	cout<<u<<' ';
	vis[u]=1;
	for(int i=head[u];i!=-1;i=a[i].next){
		int v=a[i].v;
		if(!vis[v])dfs(v);
	}
}
void bfs(int s){
	queue<int>q;
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		cout<<u<<' ';
		for(int i=head[u];i!=-1;i=a[i].next){
			int v=a[i].v;
			if(!vis[v]){
				q.push(v);
				vis[v]=1;
			}
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		addedge(u,v);
		addedge(u,v);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
//			dfs(i);
			bfs(i);
		}
	}
	return 0; 
}

链表存图

/*
优点：空间小，访问快 
缺点：不利于删边，路径跟踪不方便 
*/
#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v;
};
vector<edge>a[1005];
int n,m,u,v,vis[1005];
void dfs(int u){
	cout<<u<<' ';
	vis[u]=1;
	for(int i=0;i<a[u].size();i++){
		int v=a[u][i].v;
		if(!vis[v])dfs(v); 
	}
}
void bfs(int s){
	queue<int>q;
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		cout<<u<<' ';
		for(int i=0;i<a[u].size();i++){
			int v=a[u][i].v;
			if(!vis[v]){
				q.push(v);
				vis[v]=1;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		a[u].push_back((edge){u,v});
		a[v].push_back((edge){u,v});
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			bfs(i);
//			dfs(i);
		}
	} 
	return 0;
}

矩阵存图

/*
优点：访问快，删边方便
缺点：空间浪费多 
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10005][10005],x,y,vis[10005];
void dfs(int u){
	cout<<u<<' ';
	vis[u]=1;
	for(int i=1;i<=n;i++){
		if(a[u][i]&&!vis[i])dfs(i);
	}
}
void bfs(int s){
	queue<int>q;
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		cout<<u<<' ';
		for(int i=1;i<=n;i++){
			if(a[u][i]&&!vis[i]){
				q.push(i);
				vis[i]=1;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		a[x][y]=1;
		a[y][x]=1;//无向图的存储 
	}
	//可以dfs或bfs
	memset(vis,0,sizeof(0));
	for(int i=1;i<=m;i++){
	 	if(!vis[i]){
	 		bfs(i);
//	 		dfs(i);	
	 	}
	}
	
	return 0;
}
/*
8 8
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
8 7
*/

欧拉筛（线性筛）

#include<iostream>
using namespace std;
int n,len=0,p[100005],f[100005]={1,1};
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		// 若i未被标记为合数（f[i] == 0），则i是质数，加入质数数组p
		if(f[i]==0)p[++len]=i;
		for(int j=1;j<=len;j++){
			// 用当前已找到的质数p[j]，标记“p[j] × i”为合数
			if(p[j]*i<=n)f[p[j]*i]=1;
        // 标记该合数为非质数
			else break;
			 // 关键：若p[j]是i的因数，则跳出循环，避免重复标记
			if(i%p[j]==0)break;
		}
	}
	//打印1到n的质数
	for(int i=1;i<=len;i++)cout<<p[i]<<' ';
	return 0;
}

dijkstra

struct node{
	int dis,id;
	bool operator<(node x) const{
		return dis>x.dis;
	}
};
priority_queue<node>q;
bool vis[10005];
void Dijkstra(){
	memset(d,127,sizeof(d));
	d[1]=0;
	q.push((node){0,1});
	while(!q.empty()){
		int u=q.top().num;
		q.pop();
		vis[u]=1;
		for(int i=0;i<(int)g[u].size();i++){
			int v=g[u][i].v,w=g[u][i].w;
			if(vis[v])continue;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				q.push((node){d[v],v});
			}
		}
	}
}

spfa（关于spfa，它已经死了）

void spfa(int s){
	memset(d,127,sizeof(d));
	memset(inque,0,sizeof(inque));
	inque[s]=1;
	d[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		inque[u]=0;
		q.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].v,w=g[u][i].w;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				if(!inque[v]){
					inque[v]=1;
					q.push(v);
				}
			}
		}
	}
}

floyd

for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        if(i!=j&&j!=k){
          f[i][j]=min(max(f[i][k],f[k][j]),f[i][j]);
      }
    }
  }
}

强连通分量

void tarjan(int u){
	d[u]=l[u]=++ind;
	ins[u]=1;
	s.push(u);
	int v=t[u];
	if(d[v]==-1){//未访问 
		tarjan(v);
		l[u]=min(l[u],l[v]);
	}else{//已访问 
		if(ins[v]==1)l[u]=min(l[u],d[v]); 
	}
	if(d[u]==l[u]){
		int v=-1,sum=0;
		do{
			v=s.top();
			s.pop();
			ins[v]=0;
			sum++;
		}while(u!=v);
		if(sum>1) minn=min(minn,sum);
	}
}

割点与桥

void fcp(int u,int fa){
	d[u]=l[u]=++ind;
	int c=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa) continue;
		if(!d[v]){
			c++;
			fcp(v,u);
			l[u]=min(l[u],l[v]);
			if(l[v]>=d[u]) vis[u]=1;
		}else{
			l[u]=min(l[u],d[v]);
		}
	}
	if(fa==-1&&c==1) vis[u]=0;
}

临时草稿

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MX=3005,Cty=114514>>114,UN=114;
const int xx[]={0,1,0,-1},yy[]={-1,0,1,0};
struct node{
	int x,y,s;
};
queue<node>q;
int n,m,k,x,yq;
int g[MX][MX];
vector<int>f[MX][MX];
signed main(){
//	freopen("boundary.in","r",stdin);
//	freopen("boundary.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++){
		cin>>x>>y;
		g[x][y]=Cty;
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>x>>y;
		g[x][y]=UN;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(g[i][j]==UN)continue;
			
		}
	}
	return 0;
}

$codeforces$ CF5B Center Alignment 因为洛谷爆了，所以先存这里。

#include<bits/stdc++.h>
using namespace std;
string str,s[1005],ans[1005];
int maxl,num,len;
bool lorr;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(getline(cin,str)){
        s[++len]=str;
    }
    for(int i=1;i<=len;i++){
        ans[i]+="*";
        int sx=s[i].size();
        int k,k2;
        if((maxl-sx)%2==0)k=((maxl-sx)>>1);
        else{
            if(lorr)k=((maxl-sx)>>1)+1;
            else ((maxl-sx)>>1);
            lorr=!lorr;
        }
        k2=maxl-k-sx;
        for(int i=1;i<=k;i++)ans[i]+=" ";
        ans[i]+=s[i];
        for(int i=1;i<=k2;i++)ans[i]+=" ";
        ans[i]+="*";
    }
    for(int i=1;i<=len;i++)maxl=max(maxl,(int)ans[i].size());
    for(int i=1;i<=maxl;i++)cout<<"*";
    cout<<"\n";
    for(int i=1;i<=len;i++)cout<<ans[i]<<"\n";
    for(int i=1;i<=maxl;i++)cout<<"*";
    return 0;
}

比赛T3 90

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int T,n,k,a[N],b[N];
double pre[N];
bool check(double x){
	pre[0]=0;
	for(int i=1;i<=n;i++)pre[i]=pre[i-1]+(b[i]-x*a[i]);
	int cnt=0,l=0;
	for(int r=1;r<=n;r++){
		if(cnt==k-1)break;
		if(pre[r]-pre[l]<=0){
			l=r;
			cnt++;
		}
	}
	if(cnt==k-1&&pre[n]<=pre[l])return 1;
	return 0;
}
signed main(){
	freopen("pancake.in","r",stdin);
	freopen("pancake.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>k;
		for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
		double l=0.0,r=1.0;
		for(int i=1;i<=50;i++){
			double mid=(l+r)/2.0;
			if(check(mid))r=mid;
			else l=mid;
		}
		printf("%.10lF\n",l);
	}
	return 0;
}

mythware_super_password

最近活动
Stat
Rating

2024tysc1046

个人简介

每一粒星光，都曾在黑暗中淬炼。

最近活动

Stat

Rating

状态

开发

支持

关于