PAT算法笔记
2020-02-07 本文已影响0人
Elis0913
*****************************************
//优先队列定义
priority_queue<int,vector<int>,greater<int>> q;
*****************************************
//并查集
int father[maxn];
int findFather(int x){
int demo=x;//记录当前的x
while(x!=father[x])//第一遍扫描
x=father[x];
while(demo!=father[demo]){//第二遍把所有结点指向根节点
int a=demo;//记录当前demo
demo=father[demo];//下一层
father[a]=x;//回溯
}
return x;
}
int findfather(int x){
if(x==father[x]) return x;
else{
int v=findfather(father[x]);
father[x]=v;
return v;
}
}
void Union(int a,int b){
int x=findFather(a);
int y=findFather(b);
if(x!=y)
father[y]=x;
}
*****************************************
//AVL
#include <iostream>
using namespace std;
struct node {
int val;
struct node *left, *right;
};
node *rotateLeft(node *root) {
node *t = root->right;
root->right = t->left;
t->left = root;
return t;
}
node *rotateRight(node *root) {
node *t = root->left;
root->left = t->right;
t->right = root;
return t;
}
node *rotateLeftRight(node *root) {
root->left = rotateLeft(root->left);
return rotateRight(root);
}
node *rotateRightLeft(node *root) {
root->right = rotateRight(root->right);
return rotateLeft(root);
}
int getHeight(node *root) {
if(root == NULL) return 0;
return max(getHeight(root->left), getHeight(root->right)) + 1;
}
node *insert(node *root, int val) {
if(root == NULL) {
root = new node();
root->val = val;
root->left = root->right = NULL;
} else if(val < root->val) {
root->left = insert(root->left, val);
if(getHeight(root->left) - getHeight(root->right) == 2)
root = val < root->left->val ? rotateRight(root) : rotateLeftRight(root);
} else {
root->right = insert(root->right, val);
if(getHeight(root->left) - getHeight(root->right) == -2)
root = val > root->right->val ? rotateLeft(root) : rotateRightLeft(root);
}
return root;
}
int main() {
int n, val;
scanf("%d", &n);
node *root = NULL;
for(int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
printf("%d", root->val);
return 0;
}
*****************************************
//二叉树
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<string>
#include<time.h>
#include<sstream>
#define ll long long
using namespace std;
int pre[100],in[100],post[100];
struct node {
int data;
int layer;
node* l;
node* r;
};
node* root=NULL;
//生成新节点
node* newNode(int v) {
node* Node=new node;
Node->data=v;
Node->l=Node->r=NULL;
return Node;
}
//二叉树的替换
void replace(node* root,int x,int newdata) {
if(root==NULL)
return;
if(root->data==x)
root->data=newdata;
replace(root->l,x,newdata);
replace(root->r,x,newdata);
}
//二叉树的插入
void insert(node* &root,int x) {
if(root==NULL) {
root=newNode(x);
return ;
}
if(1) {
insert(root->l,x);
} else
insert(root->r,x);
}
node* Create(int data[],int n) {
node* root = NULL;
for(int i=0; i<n; i++) {
insert(root,data[i]);
}
return root;
}
void preorder(node* root) {
if(root==NULL) {
return ;
}
printf("%d",root->data);
preorder(root->l);
preorder(root->r);
}
void inorder(node* root) {
if(root==NULL) {
return ;
}
inorder(root->l);
printf("%d",root->data);
inorder(root->r);
}
void pastorder(node* root) {
if(root==NULL) {
return ;
}
pastorder(root->l);
pastorder(root->r);
printf("%d",root->data);
}
void layerorder(node* root) {
queue<node*> q;
root->layer=1;
q.push(root);
while(!q.empty()) {
node* now=q.front();
q.pop();
printf("%d",now->data);
if(now->l!=NULL||!q.empty()||now->r!=NULL)
cout<<" ";
if(now->l!=NULL) {
now->l->layer=now->layer+1;
q.push(now->l);
}
if(now->r!=NULL) {
now->r->layer=now->layer+1;
q.push(now->r);
}
}
}
void layerO(node* root){
if(root==NULL) return;
cout<<root->data;
}
node* tree(int pl,int pr,int inl,int inr){
if(pl>pr)
return NULL;
node *root=new node;
root->data=post[pr];
int k;
for(k =inl;k<inr;k++){
if(in[k]==post[pr])
break;
}
root->l=tree(pl,pl+k-inl-1,inl,k-1);
root->r=tree(pl+k-inl,pr-1,k+1,inr);
return root;
}
int main() {
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>post[i];
for(int i=0;i<n;i++) cin>>in[i];
node* root=tree(0,n-1,0,n-1);
layerorder(root);
}
*****************************************
//BFS
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<string>
#include<time.h>
#include<sstream>
#define ll long long
using namespace std;
const int maxn=100;
struct node{
int x,y;
}Node;
int n,m;
int matrix[maxn][maxn];
bool inq[maxn][maxn]={false};
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
bool judge(int x,int y){//判断坐标（x,y）是否需要访问
if(x>=n||x<0||y>=m||y<0) return false;
if(matrix[x][y]==0||inq[x][y]==true) return false;
return true;
}
void BFS(int x,int y){
queue<node> Q;
Node.x=x,Node.y=y;
Q.push(Node);
inq[x][y]=true;
while(!Q.empty()){
node top=Q.front();
Q.pop();
for(int i=0;i<4;i++){
int newx=top.x+X[i];
int newy=top.y+Y[i];
if(judge(newx,newy)){
Node.x=newx,Node.y=newy;
Q.push(Node);
inq[newx][newy]=true;
}
}
}
}
int main() {
cin>>n>>m;
for(int x=0;x<n;x++){
for(int y=0;y<m;y++)
cin>>matrix[x][y];
}
int ans=0;
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
if(matrix[x][y]==1&&inq[x][y]==false){
ans++;
BFS(x,y);
}
}
}
cout<<ans;
}
//6 7
//0 1 1 1 0 0 1
//0 0 1 0 0 0 0
//0 0 0 0 1 0 0
//0 0 0 1 1 1 0
//1 1 1 0 1 0 0
//1 1 1 1 0 0 0
*****************************************
//背包客问题
const int maxn=30;
int n,v,maxValue=0;//物品件数n，背包容量v，最大价值maxValue
int w[maxn],c[maxn];//w[i]c[i]为每件物品的重量和价值
//DFS，index为当前处理的物品编号
//sumW和sumC为当前总重量和总价值
void DFS(int index,int sumW,int sumC) {
if(index==n) {
return ;//死胡同
}
DFS(index+1,sumW,sumC);//不选第index件物品
if(sumW+w[index]<=v) {//不超过背包容量才能继续
if(sumC+c[index]>maxValue)//更新maxValue
maxValue=sumC+c[index];
DFS(index+1,sumW+w[index],sumC+c[index]);//选第index件物品
}
}
int main() {
cin>>n>>v;
for(int i=0;i<n;i++) cin>>w[i];
for(int i=0;i<n;i++) cin>>c[i];
DFS(0,0,0);
cout<<maxValue;
}
*****************************************
//最大公约数gcd
int gcd(int a,int b) {
if(b==0) return a;
else
return gcd(b,a%b);
}
//最大公倍数lcm
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
*****************************************
//进制转换
#include <iostream>
using namespace std;
//输入A、B，转换为D进制
int main() {
while(1) {
int mode;
printf("\n选择模式\n1：10转n\n2：n转10\n");
scanf("%d",&mode);
if(mode==1) {
int sum,d;
printf("输入要转化的10进制数和想转换的进制\n");
scanf("%d%d",&sum,&d);
int ans[31],num=0;//ans存D进制的每一位
do {//进制转换
ans[num++]=sum%d;
sum/=d;
} while(sum!=0);
for(int i=num-1; i>=0; i--) { //从高位往低位输出
printf("%d",ans[i]);
}
printf("\n");
} else {
int x,p;
printf("输入要转换的数字和它的进制\n");
scanf("%d%d",&x,&p);
int y=0,product=1;
while(x!=0) {
y+=(x%10)*product;
x/=10;
product*=p;
}
printf("%d\n",y);
}
}
}
*****************************************
//int字符串互转
#include <iostream>
using namespace std;
int main() {
int a;
char aa[425]="12345678900";
//注意有&符号!!!
sscanf(aa,"%lld",&a);//注意有&符号!!!
sprintf(aa,"%d",a);
cout<<a;
}
*****************************************
//全排列
#include<iostream>
#include<algorithm>
using namespace std;
//全排列递归算法
void Perm(int list[] , int k ,int m) {
//list 数组存放排列的数，K表示层,代表第几个数，m表示数组的长度
if(k==m) {
//K==m 表示到达最后一个数，不能再交换，最终的排列的数需要输出；
for(int i=0 ; i<=m ; i++)
cout<<list[i];
cout<<endl;
} else {
for(int i=k; i<=m; i++) {
swap(list[i],list[k]);
Perm(list,k+1,m);
swap(list[i] , list[k]);
}
}
}
int main() {
int a[]= {1,2,3,4};
int len=sizeof(a)/sizeof(int);
Perm(a,0,len-1);
}
//全排列函数用法
int permutation[100];
void get_permutation(int n) {
for(int i=0; i<n; i++) {
permutation[i]=i+1;
printf("%d",permutation[i]);
}
printf("\n");
while(next_permutation(permutation,permutation+n)) {
for(int i=0; i<n; i++)
printf("%d",permutation[i]);
printf("\n");
}
return;
}
*****************************************
//质数欧拉筛
int prime[100005], total=0;
bool check[100005];
void get_primes(int n){//筛出[1,n]之间的素数
for (int i = 2; i <= n; ++i) {
if (!check[i]) prime[total++] = i;
for (int j = 0; j < total && i * prime[j] <= n; ++j) {
check[i*prime[j]] = 1;
if (i % prime[j] == 0) break;//保证每个数被他最小的质因数约去
}
}
}
*****************************************
//计算n！中有多少个质因子p
int cal(int n,int p){
if(n<p) return 0;
return n/p+cal(n/p,p);
}
*****************************************
//组合数
//(时间慢)
long long res[1010][1010]={0};
ll cal(ll m,ll n){
if(m==0||n==m) return 1;
if(res[n][m]!=0) return res[n][m];
return res[n][m]=cal(m,n-1)+cal(m-1,n-1);
// return res[n][m]=(cal(m,n-1,p)+cal(m-1,n-1,p))%p;
// 全部改int型
}
//(乘法可能会溢出)
ll cal2(ll m,ll n){
ll ans=1;
for(ll i=1;i<=m;i++){
ans=ans*(n-m+i)/i;
}
return ans;
}
*****************************************
