mkh (美术猫映画)

UID: 3118, 注册于 2023-3-19 14:13:37, 最后登录于 2024-11-27 11:09:23, 目前离线.

解决了 117 道题目，RP: 230.97 (No. 197)

♂

个人简介

#坤坤

hahahahahahahahahahahahahaah

学校：重庆第一双语学校

班级：7年级11班

CSP考点

1.排序算法

2.计算机单位

‌位（bit）‌：位是计算机中最小的存储单位，每一个位存储一个二进制码，即0或1。

‌‌字节（Byte）‌：字节由8个位组成，是计算机的基本存储单位。一个字节可以表示256个不同的值（0000 0000到1111 1111），通常用于表示一个字符。

‌字（‌Word）‌：字通常由16、32或64个位组成，用于表示更大的数据块。

‌‌千字节（KB）‌：1千字节等于1024字节。

‌‌兆字节（MB）‌：1兆字节等于1024千字节。

‌‌吉字节（GB）‌：1吉字节等于1024兆字节。

‌‌太字节（TB）‌：1太字节等于1024吉字节。

计算机进制转换

二转八：三位一组转十进制

二转十六：四位一组转十进制

N转十进制：及你太美

N进制小数

数据结构

常用的线性结构有：线性表，栈，队列，双队列，串(一维数组)。

关于广义表、数组(高维)，是一种非线性的数据结构。

常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图

肾上腺素飙升

大美女

小忙果最爱了↓

重庆第一双语学校7年级3班刘艾灵↑

阿米诺斯↓

快读快写

inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

基数排序

/*在女同学面前装X：基数排序，时间复杂度o(n+k),空间复杂度o(n)*/
#include<bits/stdc++.h>
using namespace std;
int mkc[114514];
int main(){
	int n,LAL;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&LAL);
		mkc[LAL]++;
	}
	for(int i=1;i<=114514;++i){
		if(mkc[i]){
			while(mkc[i]--) printf("%d ",i);
		}
	}
	return 0;
}

递归：快速幂

//装逼哥：快速幂
#include<bits/stdc++.h>
using namespace std;
int p;
long long a,b;
long long mkc(long long a,long long b){
	if(b==0) return 1;
	if(b%2==0) return mkc(a*a%p,b/2)%p;
	else{
		return a*mkc(a,b-1)%p;
	}
}
int main(){
	cin>>a>>b>>p;
	cout<<a<<"^"<<b<<" mod "<<p<<"="<<mkc(a,b);
}

DFS

//深度优先搜索
//我是傻逼(mkh)来装逼了
#include<bits/stdc++.h>
using namespace std;
char mat[505][505];
int vis[505][505];
int n,m,flag=0;;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){
    vis[x][y]=1;
    if(mat[x][y]=='g'){
        flag=1;
        return;
    }
    for(int i=0;i<4;++i){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(mat[tx][ty]=='#') continue;
        if(tx>n||ty>m||tx<1||ty<1) continue;
        if(vis[tx][ty]==1) continue;
        dfs(tx,ty);
    }
}
int main(){
    int a,b;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>mat[i][j];
            if(mat[i][j]=='s'){
                a=i;b=j;
            }
        }
    }
    dfs(a,b);
    if(flag) cout<<"Yes";
    else cout<<"No";
}

smallgame

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
int Count=0;
int Question_Answer(int cnt){
	int Ua;
	if(cnt){
		printf("=============================================\n");
		printf("           嗨，我的朋友，好久不见\n");
		printf("=============================================\n");
		Sleep(3000);
		system("cls");
	}
	printf("=============================================\n");
	printf("          想玩游戏吗？\n");
	printf("        你可以说出你的需求：\n");
	Sleep(500);
	printf("        1:猜数字\n");
	Sleep(500);
	printf("        2:博弈\n");
	Sleep(500);
	printf("        3:走迷宫\n");
	Sleep(500);
	printf("        4:生日\n");
	Sleep(500);
	printf("        5:排序\n");
	Sleep(500);
	printf("=============================================\n");
	printf("请输入：");
	scanf("%d",&Ua);
	printf("\n");
	return Ua;
}
int main(){
	Count=1;
	while(1){
		int G_Answer=Question_Answer(Count);
		Count=0;
		system("cls");
		printf("好的，请稍等");
		int CNT=0;
		for(int i=1;i<=9;++i){
			CNT++;
			printf(".");
			Sleep(1000);
			if(CNT==3){
				system("cls");
				printf("好的，请稍等.");
				Sleep(1000);
				CNT=1;
			}
		}
		system("cls");
		/*switch(G_Answer){
			case 1
				break;
			case 2
				break;
			case 3
				break;
			case 4
				break;
			case 5
				break;
		}*/
	}
}

人机集训

输入

cin 慢 50万以下用

用scanf/关流:ios::sync_with_stdio(flase)

cin,tie(0);

cout,tie(0);

警告:关流情况下，不能混用cin和scanf

并查集

#include<bits/stdc++.h>
using namespace std;
int x[20],y[20],vis[20];
int n;
double dis(int s,int e){
    return sqrt((x[s]-x[e])*(x[s]-x[e])+(y[s]-y[e])*(y[s]-y[e]));
}
double ans=1e9;
void dfs(int x,double s,int y){
    for(int i=1;i<=n;++i){
        if(x>n){
            ans=min(ans,s);
            return;
        }
        if(s>ans) return;
        if(vis[i]==1) continue;
        vis[i]=1;
        dfs(x+1,s+dis(y,i),i);
        vis[i]=0;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d %d",&x[i],&y[i]);
    }
    dfs(1,0,0);
    printf("%.2lF",ans);
}

//并查集
#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[100010];
int find(int x){
	if(x!=p[x]) p[x]=find(p[x]);
	return p[x];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) p[i]=i;
	for(int i=1;i<=m;++i){
		int x,y,z;
		cin>>z>>x>>y;
		if(z==1){
			int px=find(x),py=find(y);
			p[px]=py;
		}
		else{
			int px=find(x),py=find(y);
			if(px==py) cout<<"Y\n";
			else cout<<"N\n";
		}
	}
        return 0;
}

//代数并查集
#include<bits/stdc++.h>
using namespace std;
int m;
int siz[30010],d[30010],p[30010];
int find(int x){
	if(x!=p[x]){
		int tmp=find(p[x]);
		d[x]+=d[p[x]];
		p[x]=tmp;
	}
	return p[x];
}
int main(){
	for(int i=1;i<=30000;++i){
		siz[i]=1;
		p[i]=i;
	}
	cin>>m;
	for(int i=1;i<=m;++i){
		char op;
		int a,b;
		scanf(" %c %d %d",&op,&a,&b);
		if(op=='M'){
			int pa=find(a),pb=find(b);
			d[pa]=siz[pb];
			p[pa]=pb;
			siz[pb]+=siz[pa];
		}
		else{
			int pa=find(a),pb=find(b);
			if(pa==pb) cout<<abs(d[a]-d[b])-1<<"\n";
			else cout<<-1<<"\n";
		}
	}
        return 0;
}

区间最值RMQ

//st表
#include<bits/stdc++.h>
using namespace std;
int st[100010][20];
int n,m;
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&st[i][0]);
	for(int i=1;i<=16;++i){
		for(int j=1;j+(1<<i)-1<=n;++j){
			st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);
		}
	}
	for(int i=1;i<=m;++i){
		int l,r;
		scanf("%d %d",&l,&r);
		int t=__lg(r-l+1);
		printf("%d\n",max(st[l][t],st[r-(1<<t)+1][t]));
    }
}

差分

//差分
#include<bits/stdc++.h>
using namespace std;
int c[100010];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;++i) cin>>c[i];
	for(int i=n;i>=2;--i) c[i]-=c[i-1];
}
//修改 c[l]+=d c[r]-=d

前缀和

//前缀和
#include<bits/stdc++.h>
using namespace std;
int n;
int lowbit(int x){
	return x&-x;
}
long long tr[100005];
long long sum(int x){
	long long res=0;
	for(int i=x;i;i-=lowbit(i)) res+=tr[i];
	return res;
}
void add(int d,int x){
	for(int i=d;i<=n;i+=lowbit(i)) tr[i]+=x;
}
int main(){
	int q;
	cin>>n>>q;
	for(int i=1;i<=n;++i){
		int x;
		cin>>x;
		add(i,x);
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<sum(r)-sum(l-1)<<endl;
	}
    return 0;
}

BFS

//我是傻逼(mkh)来装逼了
#include<bits/stdc++.h>
using namespace std;
char mtr[505][505];
int vis[505][505];
int dx[5]={0,1,0,-1};
int dy[5]={1,0,-1,0};
int n,m;
struct p{
	int x,y;
};
int bfs(int a,int b){
	queue<p> que;
    que.push({a,b});
	vis[a][b]=1;
	while(!que.empty()){
		p now=que.front();
        que.pop();
        if(mtr[now.x][now.y]=='T'){
            return vis[now.x][now.y];
        }
        for(int i=0;i<4;++i){
            int tx=now.x+dx[i];
            int ty=now.y+dy[i];
            if(mtr[tx][ty]=='X') continue;
            if(tx>n||ty>m||tx<1||ty<1) continue;
            if(vis[tx][ty]>=1) continue;
            vis[tx][ty]=vis[now.x][now.y]+1;
            que.push({tx,ty});
        }
	}
    return 0;
}
int main(){
	cin>>n>>m;
	int a,b;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>mtr[i][j];
			if(mtr[i][j]=='S'){
				a=i;b=j;
			}
		}
	}
    int u=bfs(a,b);
    if(u) cout<<u;
    else cout<<-1;
}

逆序对

//逆序对
#include<bits/stdc++.h>
using namespace std;
int n;
int lowbit(int x){
return x&-x;
}
long long tr[1000005];
int sum(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=tr[i];
return res;
}
void add(int d,int x){
for(int i=d;i<=1000000;i+=lowbit(i)) tr[i]+=x;
return;
}
int main(){
long long ans=0;
cin>>n;
for(int i=1;i<=n;++i){
int x;
cin>>x;
ans+=sum(1000000)-sum(x);
add(x,1);
}
cout<<ans;

#include<bits/stdc++.h>
using namespace std;
char mat[505][505];
int vis[505][505];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int n,m;
struct point{
	int x,y;
};
void bfs(int sx,int sy){
	queue<point> que;
	vis[sx][sy]=1; //起点标记
	que.push({sx,sy}); //起点打包入队
	while(!que.empty()){
		point p=que.front(); //获取队首元素
		que.pop();
		if(mat[p.x][p.y] == 'T'){
			cout<<vis[p.x][p.y]; //找到终点输出终点的步数 
			return;
		} 
		for(int i=0;i<4;i++){
			int tx=p.x+dx[i];
			int ty=p.y+dy[i];
			if(tx>n||tx<1||ty>m||ty<1) continue;
			if(mat[tx][ty]=='X') continue;
			if(vis[tx][ty]!=0) continue;
			que.push({tx,ty}); //将新的点加入队列，等着后面走 
			vis[tx][ty]=vis[p.x][p.y]+1;
			//新的点步数 是 来源点步数+1 
		} 
	} 
	cout<<-1; 
} 
int main(){
	cin>>n>>m;
	int sx,sy;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mat[i][j];
			if(mat[i][j]=='S'){
				sx=i;
				sy=j;
			}
		}
	}
	bfs(sx,sy);
	return 0;
}

通过的题目
P1

P2

P3

P4

P5

P6

P7

P8

P9

P10

P13

P14

P15

P16

P17

P18

P19

P21

P22

P23

P24

P25

P32

P33

P34

P40

P44

P45

P47
P49

P57

P62

P67

P72

P73

P74

P76

P77

P78

P79

P91

P92

P93

P96

P136

P152

P156

P185

P271

P276

P300

P315

P316

P331

P332

P335

P337

P339
P341

P384

P585

P735

P783

P784

P827

P832

P853

P901

P918

P924

P951

P960

P962

P964

P1013

P1014

P1015

P1607

P1068

P1069

P1111

T106

T130

T137

T155

T160

T19
T2

T299

T397

pig003

P2165

P2169

P2015

P2016

P2194

Z40

Z44

Z42

Z41

P2237

P2315

P2318

P2321

P2375

P2376

P2377

P2392

P2394

Y21

Y22

Y23

Y24

P2511

P2671
最近活动

初窥门径: 45
顺序结构: 31
分支结构: 13
略有小成: 10
驾轻就熟: 10
排序: 9
一本通编程启蒙: 9
循环结构: 7
模拟: 6
蓝桥杯: 5
其他: 5
月赛语法: 4
一维数组: 3
融会贯通: 3
图论: 3
循环嵌套: 2
字符串: 2
计数排序: 2
DFS: 2
搜索: 2

mkh (美术猫映画)

个人简介

#坤坤

学校：重庆第一双语学校

班级：7年级11班

CSP考点

1.排序算法

2.计算机单位

计算机进制转换

数据结构

肾上腺素飙升

大美女

小忙果最爱了↓

重庆第一双语学校7年级3班刘艾灵↑

阿米诺斯↓

快读快写

基数排序

递归：快速幂

DFS

smallgame

人机集训

输入

并查集

区间最值RMQ

差分

前缀和

BFS

逆序对

通过的题目

最近活动

题目标签

状态

开发

支持

mkh (美术猫映画)

个人简介

#坤坤

学校：重庆第一双语学校

班级：7年级11班

CSP考点

1.排序算法

2.计算机单位

计算机进制转换

数据结构

肾上腺素飙升

大美女

小忙果最爱了↓

重庆第一双语学校7年级3班刘艾灵↑

阿米诺斯↓

快读快写

基数排序

递归：快速幂

DFS

smallgame

人机集训

输入

并查集

区间最值RMQ

差分

前缀和

BFS

逆序对

通过的题目

最近活动

题目标签

状态

开发

支持

还没有账户？

登录