2024竞赛笔记合集

本文最后更新于：2 天前

2024/1/15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//Luogu P1706 全排列问题
//By OIWIKI 2024/1/15
#include <iomanip>
#include <iostream>
using namespace std;
int n;
bool vis[50];  // 访问标记数组
int a[50];     // 排列数组，按顺序储存当前搜索结果

void dfs(int step) {
  if (step == n + 1) {  // 边界
    for (int i = 1; i <= n; i++) {
      cout << setw(5) << a[i];  // 保留5个场宽
    }
    cout << endl;
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i] == 0) {  // 判断数字i是否在正在进行的全排列中
      vis[i] = 1;
      a[step] = i;
      dfs(step + 1);
      vis[i] = 0;  // 这一步不使用该数 置0后允许下一步使用
    }
  }
  return;
}

int main() {
  cin >> n;
  dfs(1);
  return 0;
}



DFS-Deep First Search-深度优先搜索（转）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//n皇后问题
#include<bits/stdc++.h>
using namespace std;
int a[10001];//保存皇后的位置
int b[10001],c[10001],d[10001];//标记同列和对角线
int sum;//方案总数
void print()
{
	sum++;
	for(int i=1;i<=8;i++)
	{
		cout<<a[i];
		if(i!=8) cout<<" ";
		else cout<<endl;
	}
} 
void s(int i)
{
	for(int j=1;j<=8;j++)//试探八个位置
	{
		if(!b[j] && !c[i+j] && !d[i-j+7])//下标不为负，+7
		{
			a[i]=j;
			b[j]=1;//j列被占用
			c[i+j]=1;//对角线被占用
			d[i-j+7]=1;
			if(i==8) print();//放完
			else s(i+1);
			b[j]=0;//回溯
			c[i+j]=0;
			d[i-j+7]=0; 
		 } 
	 } 
}
int main()
{
	s(1);
	cout<<sum<<endl;
}

pFFKw0e.jpg

image

image

2024/1/17

广度优先搜索 BFS 学习笔记 - XiaoQuQu

深度优先搜索 DFS 学习笔记 - XiaoQuQu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//P2392 kkksc03考前临时抱佛脚
#include<bits/stdc++.h>
using namespace std;
int a[5000][10000];
int sum,ans,lft,rght;
int s[5000];
void dfs(int x,int dep)//x表示第几个科目,dep表示第几题
{
	if(dep>s[x])
	{
		sum=min(sum,max(lft,rght));
		return;
	}
	lft+=a[x][dep];//左脑尝试
	dfs(x,dep+1);
	lft-=a[x][dep];//回溯
	rght+=a[x][dep];//右脑
	dfs(x,dep+1);
	rght-=a[x][dep];//回溯 
 } 
int main()
{
	for(int i=1;i<=4;i++)
		cin>>s[i];
	for(int i=1;i<=4;i++)//科目
	{
		sum=INT_MAX;
		for(int j=1;j<=s[i];j++)//题目
			cin>>a[i][j];//每题耗时
		dfs(i,1);
		ans+=sum;//sum有该科目完成的最小耗时，统计进ans
		 
	 } 
	 cout<<ans<<endl;
	 return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//P1025 [NOIP2001 提高组] 数的划分--递归做法 
#include<bits/stdc++.h>
using namespace std;
int l,k;
int se(int n,int k,int min){
	if(k==1) return n>=k;
	else 
	{
		int s=0;
		for(int i=min;i<=n/k;i++)
		{
			s+=se(n-i,k-1,i);
		}
		return s;
	}
}
int main(){
	cin>>l>>k;
	cout<<se(l,k,1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//P2404	自然数的拆分问题
#include<bits/stdc++.h>
using namespace std;
int a[10001]={1},n,total;
void print(int t)
{

	for(int i=1;i<=t;i++)//拆分方案 
	{
		if(i!=t) cout<<a[i]<<"+";
		else cout<<a[i]<<endl;
	}

}
void se(int s,int t)
{
	for(int i=a[t-1];i<=s;i++)
	{
		if(i<n){//i要大于等于前一位数,且不超过n
			a[t]=i;//保存结果
			s-=i;//继续拆分
			if(s==0) print(t) ;//拆分结束，输出
			else se(s,t+1);//继续搜索
			s+=i;//回溯：加上拆分的数 
		}
	}
}
int main()
{
	cin>>n;
	se(n,1);
}

2024/1/18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//P1596 [USACO10OCT] Lake Counting S
#include<bits/stdc++.h>
using namespace std;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};//各个方向
int a[1001][1001];//保存地图
int n,m,ans;
void dfs(int x,int y)
{
	for(int i=0;i<=7;i++)//向8个方向枚举
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(a[xx][yy]==1)//只要找到联通得水坑就标记为0 
		{
			a[xx][yy]=0;
			dfs(xx,yy);
		}	
	} 
	return;
} 

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='.') a[i][j]=0;//1为水坑，0为旱地 
			else a[i][j]=1; //判断出界
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){//枚举每一个点
			if(a[i][j]==1){
				ans++;
				dfs(i,j);
			} 
		}
	} 
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//P1025 [NOIP2001 提高组] 数的划分 
//DFS做法
#include<bits/stdc++.h>
using namespace std;
int n,k,sum;
void dfs(int s,int t,int l)//last表示前一个状态 
{
	if(s>k)
	{
		if(t==n) sum++;
		return;
	}
	for(int i=l;i<=n-t;i++)//剪枝优化，因为当前格子可选数最大只有n-t 
	{
		dfs(s+1,t+i,i);
	}
}
signed main()
{
	cin>>n>>k;
	dfs(1,0,1);
	cout<<sum;
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//P2036 [COCI 2008/2009 #2] PERKET
#include<bits/stdc++.h>
using namespace std;
int n,a[1001],b[1001],ans=0x3f3f3f3f;//ans初始化，此处约等于INT_MAX
void dfs(int i,int x,int y) //i是第几种配料，x,y代表酸,苦度
{
	if(i>n){
		if(x==1 && y==0) return;
		ans=min(abs(x-y),ans);//取绝对值与当前答案进行比较 
		return;
	} 
	dfs(i+1,x*a[i],y+b[i]);//添加第i种配料 ,总的酸度为每一种配料的酸度总乘积
	dfs(i+1,x,y); //不添加第i中配料
} 

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	dfs(1,1,0);//配料编号，酸度(乘法默认初值为1)，苦度（默认初值为0）
	cout<<ans<<endl;
	return 0; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//P1784 数独
#include<bits/stdc++.h>
using namespace std;
int g[9][9];
int cell[3][3][10],row[9][10],col[9][10];//保存数独信息
bool dfs(int x,int y)
{
	if(y==9) x++,y=0;
	if(x==9) return true;
	if(g[x][y]) return dfs(x,y+1);
	else
	{
		for(int i=1;i<=9;i++)//开始判断行、列、宫
		{
			if(cell[x/3][y/3][i] || row[x][i] || col[y][i]) continue;
			g[x][y]=i;//保存
			cell[x/3][y/3][i]=row[x][i]=col[y][i]=true;
			if(dfs(x,y+1)) return true;
			g[x][y]=0;//回溯
			cell[x/3][y/3][i]=row[x][i]=col[y][i]=false;
		} 
	}
	return false;
	/*
	while(false)
	{
		cout<<"renjiheinu"<<endl;
	}
	*/
} 

signed main()
{
	for(int i=0;i<9;i++)//输入数独 
	{
		for(int j=0;j<9;j++)
		{
			cin>>g[i][j];
			if(g[i][j])//如果已经有数
			{
				int x=g[i][j];	
				cell[i/3][j/3][x]=row[i][x]=col[j][x]=true;
			} 
		}
	}
	//初始化 
	dfs(0,0);
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++) cout<<g[i][j]<<' ';
		cout<<endl;
	}
	return 0;
}

P1238 走迷宫

P1605 迷宫

【初一算法基础】深搜与回溯

BFS（图论）-OI Wiki

2024/1/19

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//T172312 走迷宫
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x;
	int y;
	int s;//步数 
} que[10001];
int head,tail,r,s,p,q;
char c[1001][1001];//保存地图
bool flag;//标记是否达到目标点，0未到，1已到
int a[4]={-1,1,0,0},b[4]={0,0,-1,1};//可走的组合
bool f[1001][1001];//记录已走的点
void bfs()
{
	while(head<tail)//队列不为空时操作
	{
		for(int i=0;i<=3;i++)//枚举四个方向
		{
			int xx=que[head].x+a[i];
			int yy=que[head].y+b[i];
			if(xx>=1&&xx<=r&&yy>=1&&yy<=s&&c[xx][yy]=='.'&&!f[xx][yy])//判断x,y下一步是否可走且是否走过
			{
				f[xx][yy]=1;//标记已走
				que[tail].x=xx;
				que[tail].y=yy; //更新xx和yy的值
				que[tail].s=que[head].s+1;//步数是父亲的步数+1
				tail++; 
			}
			if(xx==p&&yy==q)//如果找到目标点
			{
				flag=1;//标记已完成
				break;//退出	
			} 
		} 
		if(flag==1) break;
		head++;//head++才能对后面的点进行二次扩展 
	} 
} 
int main()
{
	cin>>r>>s;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=s;j++)
		{
			cin>>c[i][j];
		}
	}
	p=r;q=s;//终点坐标
	head=1;tail=2;
	que[tail].x=1; que[tail].y=1; que[tail].s=0+1;
	tail++;
	f[1][1]=1;
	flag=0;
	//初始化
	bfs();
	cout<<que[tail-1].s<<endl;
	return 0;
}
//禁止直接抄袭！打击这种行为！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//B3625 迷宫寻路
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x;
	int y;
	int s;//步数 
} que[10001];
int head,tail,r,s,p,q;
char c[1001][1001];//保存地图
bool flag;//标记是否达到目标点，0未到，1已到
int a[4]={-1,1,0,0},b[4]={0,0,-1,1};//可走的组合
bool f[1001][1001];//记录已走的点
void bfs()
{
	while(head<tail)//队列不为空时操作
	{
		for(int i=0;i<=3;i++)//枚举四个方向
		{
			int xx=que[head].x+a[i];
			int yy=que[head].y+b[i];
			if(xx>=1&&xx<=r&&yy>=1&&yy<=s&&c[xx][yy]=='.'&&!f[xx][yy])//判断x,y下一步是否可走且是否走过
			{
				f[xx][yy]=1;//标记已走
				que[tail].x=xx;
				que[tail].y=yy; //更新xx和yy的值
				que[tail].s=que[head].s+1;//步数是父亲的步数+1
				tail++; 
			}
			if(xx==p&&yy==q)//如果找到目标点
			{
				flag=1;//标记已完成
				break;//退出	
			} 
		} 
		if(flag==1) break;
		head++;//head++才能对后面的点进行二次扩展 
	} 
} 
int main()
{
	cin>>r>>s;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=s;j++)
		{
			cin>>c[i][j];
		}
	}
	p=r;q=s;//终点坐标
	head=1;tail=2;
	que[tail].x=1; que[tail].y=1; que[tail].s=0+1;
	tail++;
	f[1][1]=1;
	flag=0;
	//初始化
	bfs();
	if(flag==1) cout<<"Yes";
	else cout<<"No"; 
	return 0;
}
//禁止直接抄袭！打击这种行为！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//P1451 求细胞数量
#include<bits/stdc++.h>
using namespace std;
int n,m,dx[4]={0,1,0,-1},dy[4]={-1,0,1,0},a[100][100];//保存地图，枚举方向 
int sum,q[10000][4],h,t;//模拟BFS的数组 
void fun(int x,int y)
{
	h=1,t=1;
	q[h][1]=x;
	q[h][2]=y;//初始化 
	while(h<=t)//队列不为空 
	{
		for(int i=0;i<4;i++)//枚举方向 
		{
			int xx=q[h][1]+dx[i];
			int yy=q[h][2]+dy[i];
			if(a[xx][yy]!=0&&xx>=1&&xx<=n&&yy>=1&&yy<=m)//如果满足移动条件 
			{
				t++;//尾部++ 
				q[t][1]=xx;
				q[t][2]=yy;
				a[xx][yy]=0;//地图中标记为0 
			}
		}
		h++;//继续循环，head++ 
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%1d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]!=0)//是其他数字时 
			{
				fun(i,j);
				sum++;
			}
		}
	}
	cout<<sum;
	return 0;
}
//禁止直接抄袭！打击这种行为！


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//B3626 跳跃机器人
#include<bits/stdc++.h>
using namespace std;
int n;
queue<int> q;
int s[1000010];//记录步数
void bfs(){
	memset(s,-1,sizeof(s));//初始化数组
	q.push(1);//bot原位
	s[1]=0;//七点不需要步数
	while(!q.empty()){//队列不为空
		int t=q.front();
		q.pop();//提前出队第一元素
		if(t==n){//到达n
			cout<<s[n];
			return; 
		} 
		if(t-1>=1&&t-1<=n&&s[t-1]==-1){//x-1
			q.push(t-1);
			s[t-1]=s[t]+1;
		}
		if(t+1>=1&&t+1<=n&&s[t+1]==-1){//x+1
			q.push(t+1);
			s[t+1]=s[t]+1;
		}
		if(2*t>=1&&2*t<=n&&s[t*2]==-1){//2x
			q.push(t*2);
			s[t*2]=s[t]+1;
		}		
	} 
	return;
} 
signed main()
{
	cin>>n;
	bfs();
	return 0;
}

【初一算法基础】宽搜

2024/1/22

拯救oibh总部

奇怪的电梯

DFS

BFS

马的遍历

P2895

未写完暂存(写完自动销毁)

2024/1/23

【初一算法基础】高精度


a

P2437 蜜蜂路线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//P2437
//看了一下题解才知道可以用递归c 
#include<iostream>
using namespace std;
int f[10005][20010];//处理每个方格 
int m,n;
int len=1;//计数器计算总和位数 
void did(int k){//k指阶数
	int isBigten=0;//处理进位 
	for (int i=1;i<=len;i++) //开始高精度加法
	{
		f[k][i]=f[k-1][i]+f[k-2][i]+isBigten;//递推(只是多了一个加进位) 
		isBigten=f[k][i]/10;//获取进位值
		f[k][i]%=10;//得到进位后获取当前位的值
	}
	if(isBigten>0) //最后一位可能会进位
	{
		len++;//位数+1 
		f[k][len]+=isBigten;//进位加入总和 
	}
}
signed main() {
	cin>>m>>n;
	f[0][1]=0;
	f[1][1]=1;
	f[2][1]=1;//递推边界 
	for(int i=2;i<=n-m+1;i++)//循环n-m+1次（因为i=2） 
	{
		did(i);//一个个方格（阶数）开始递推 
	}
	for (int i=len;i>=1;i--)
	{
		cout<<f[n-m+1][i];//输出结果 
	}
	
}

P1601 A+B高精

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//P1601 A+B高精
#include<bits/stdc++.h>
using namespace std;
int a[600],b[600],c[600],k1,k2,k3,maxn;//处理位数和存储 
string a1,b1;//存储两个加数
signed main()
{
	cin>>a1>>b1;
	for(int i=a1.size()-1;i>=0;i--)//字符串a1转到数组a存储 
	{
		a[++k1]=a1[i]-'0';//把高位放在数组的最后 
	}
	for(int i=b1.size()-1;i>=0;i--)//字符串b1转到数组b存储 
	{
		b[++k2]=b1[i]-'0';//把高位放在数组的最后 
	}
	maxn=max(k1,k2);//最大数的数位 
	k3=maxn+1;//初始化结果的数位 
	for(int i=1;i<=maxn;i++)
	{
		c[i]=a[i]+b[i];
	}	
	for(int i=1;i<=maxn+1;i++)//处理加法进位 
	{
		if(c[i]>=10)//如果有进位 
		{
			c[i+1]+=c[i]/10;//加上进位值 
			c[i]%=10;//得到进位后当前位的值 
		}
	}
	while(c[k3]==0)
		k3--;//慢慢消掉结果的位数 
	for(int i=max(k3,1);i>=1;i--)
		printf("%d",c[i]);//输出 
}

P2142 高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//P2142 高精度减法
#include<bits/stdc++.h>
using namespace std;
int a[100000]={0},b[100000]={0},c[100000]={0};//初始化数组 
int i,j,k,l,m,n,flag;
string a1,b1,c1;//存储被减数，减数和差 
void did(){
    int i=0;
    while(i<=a[0]){
        i++;
        if(a[i]<b[i]){//被减数比减数小 
            a[i+1]--;//前一位-- 
			a[i]+=10;//当前数位++ 
        }
        c[i]=a[i]-b[i];//相应数值相减 
        c[0]++;//位数++
    }
}
int main(){
    cin>>a1>>b1;
    a[0]=a1.length();//取长度 
    b[0]=b1.length();
    if(a[0]<b[0] || (a[0]==b[0] && a1<b1)){//比较大小，如果被减数小于减数就交换 
        c1=b1;b1=a1;a1=c1;
        swap(a[0],b[0]);//交换两数的位数 
        cout<<"-";//因为交换了，输出“-”
    }
    for(i=1;i<=a[0];i++) {//字符串a1转到数组a存储
    	a[i]=a1[a[0]-i]-'0';//最高位放到末尾 
	}
    for(i=1;i<=b[0];i++){//字符串b1转到数组b存储
	    b[i]=b1[b[0]-i]-'0';//最高位放到末尾 
	}
    did();//减法运算 
    while(c[c[0]]==0&&c[0]>1) c[0]--;//判断0是否有用,因为使用 “c[0]>1”减会减多，从而使c[0]=0
    for(i=c[0];i>=1;i--) {
	    cout<<c[i];//倒序输出
	}
    return 0;
}

高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//P1303
#include<iostream>
#include<cstring>
using namespace std;
char a1[2000],b1[2000];
int a[20005]={0},b[20005]={0},c[40010]={0};//保存数子的数组 
int main()
{
	int la,lb,lc=0;
	cin>>a1>>b1;
	la=strlen(a1);//取位数 
	lb=strlen(b1);
	for(int i=0;i<=la;i++)//a1保存到数组a 
	{
		a[la-i]=a1[i]-'0';//最高为防末尾 
	}
	for(int i=0;i<lb;i++)//b1保存到数组b
	{
		b[lb-i]=b1[i]-'0';//最高为防末尾 
	}		
	for(int i=1;i<=la;i++)
	{
		for(int j=1;j<=lb;j++)
		{
			c[i+j-1]=a[i]*b[j]+c[i+j-1];
			if(c[i+j-1]>=10)//如果有进位 
			{
				c[i+j]+=c[i+j-1]/10;//加上进位的值 
				c[i+j-1]=c[i+j-1]%10;//更新当前位的值 
			}
		}
	}	
	lc=la+lb;//加 
	while(c[lc]==0 && lc>1)//毁灭积的位数 
	{
		lc--;
	}
	for(int i=lc;i>=1;i--)
	{
		cout<<c[i];//输出 
	}
	return 0;
}

P1009 阶乘之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
int n,a[1000],b[1000],len;//保存阶乘过程中的数字数组 
void jiechenghe()
{
	int x=0;//进位 
	for(int i=0; i<1000; i++)
	{
		b[i]=b[i]+a[i]+x;//加上所有阶乘并处理进位 
		x=b[i]/10;//取进位 
		b[i]%=10;//得到进位后获取当前位的值
	}
}
void jiecheng(int y)
{
	int x=0;//进位 
	for(int i=0; i<1000; i++){
		a[i]=a[i]*y+x;//阶乘 
		x=a[i]/10;//取进位 
		a[i]%=10;//得到进位后获取当前位的值
	}
}

signed main(){
	cin>>n;
	a[0]=1;//1!为1 
	for(int i=1;i<=n;i++){//阶乘解决 
		jiecheng(i);//每一步都计算并相加 
		jiechenghe();
	}
	len=1000;//一个定值，为去掉0做准备 
	while(b[len]==0){
		len--;//去掉多余的0 
	}	
	for(int i=len;i>=0;i--)
		cout<<b[i];//逆向输出 
	return 0;
}

2024/1/24

C++七大经典排序算法详解（代码实现+解析）转

经典排序算法详解(OI WIKI)


2024/1/25

P1781 宇宙总统

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
char a[10001],t[10001];//因为数字会比较大 
char b[10001];
int lenx,leny,n,m=1;
int main(){
	cin>>n;
	cin>>a;
	for(int i=1;i<n;i++){
	    memset(b,0,sizeof(b));//初始化 
		cin>>b;
		lenx=strlen(a);//取数位 
		leny=strlen(b);
		if((lenx<leny)||(lenx==leny&&strcmp(a,b)<0)){//进行交换（排序） 
		   	strcpy(t,a);
			strcpy(a,b);
			strcpy(b,t);
			m=i+1;//序号也要一起变化 
	    }
	}
	lenx=strlen(a);
	cout<<m<<endl;
	for(int i=0;i<lenx;i++){
		cout<<a[i];
	}
	return 0;
}

P1059 [NOIP2006 普及组] 明明的随机数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int a[114514];
signed main(){
	int n,s,t=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		if(a[s]) continue;//桶排序
		a[s]++;
		t++; 
	}
	cout<<t<<endl;
	for(int i=1;i<=1001;i++)
	{
		if(a[i]) cout<<i<<" ";
	}
	return 0;
}

P1068 [NOIP2009 普及组] 分数线划定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct player{
	int id;
	int score;
};
signed main(){
	cin>>n>>m;
	player a[n];//定义a[n]
	for(int i=0;i<n;i++) cin>>a[i].id>>a[i].score;
	for(int i=0;i<n;i++){//选择排序
		int k=i;
		for(int j=i+1;j<n;j++){
			if(a[j].score>a[k].score) k=j;
			if((a[j].score==a[k].score)&&(a[j].id<a[k].id)) k=j;
		} 
		player temp=a[i];
		a[i]=a[k];
		a[k]=temp;
	} 
	int b=m*1.5-1;//排名为m*150%的学生在数组位置下标
	int line=a[b].score;//分数线
	int count=0;
	for(int i=0;i<n;i++){
		if(a[i].score>=line) count++;
	} 
	cout<<line<<' '<<count<<endl;
	for(int i=0;i<count;i++) cout<<a[i].id<<" "<<a[i].score<<endl;
	return 0;
}

P1116 车厢重组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main()
{
	int n,sum = 0;
	cin >> n;
	for(int i = 1 ; i <= n ; i ++)
		cin >> a[i];
	for(int i = 1 ; i <= n ; i ++)
		for(int j = n ; j > 1 ; j --)
			if(a[j] < a[j - 1])//冒泡排序
			{
				swap(a[j],a[j-1]);
				sum ++;//交换次数++
			}
	cout << sum;
	return 0;
}

P1583 魔法照片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
int e[114514],n,k;
struct people{
	int w;//权值
	int num;//编号
	int d;//类别 
}p[1919810];
int cmp(const people &a,const people &b){//自定义结构体排序 
	if(a.w!=b.w) return a.w>b.w;//从大到小 
	return a.num<b.num;//序号小的优先 
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=10;i++) cin>>e[i];
	for(int j=1;j<=n;j++){
		cin>>p[j].w;//权值
		p[j].num=j;//编号 
	}
	sort(p+1,p+1+n,cmp);//第一次排序
	for(int i=1;i<=n;i++){
		p[i].d=(i-1)%10+1;//分类
		p[i].w+=e[p[i].d];//加上e[i]
	} 
	sort(p+1,p+1+n,cmp);//第二次排序
	for(int i=1;i<=k;i++) cout<<p[i].num<<" ";
	return 0;
}

本页面最后更新：2024/1/25 12:08:39

编程
#C++ #信息竞赛 #2024
2024竞赛笔记合集
https://sepiatruck34735.github.io/2024/01/30/2024竞赛笔记合集/
作者
Minecraft-Sep & Minecraft-Nul.All rights reversed.
发布于
2024年1月30日
更新于
2024年2月1日
许可协议