模板
liuxiyu 2024/12/28
# 单链表程序模板
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int head,e[N],ne[N],idx;
void init(){
head = -1;
idx = 0;
}
void add_to_head(int x){
e[idx] = x;ne[idx]=head;head=idx++;
}
void del(int k){
ne[k] = ne[ne[k]];
}
void insert(int k,int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
int main(){
freopen("单链表.in","r",stdin);
int m ;cin>>m;
init();
while(m--){
char op;cin>>op;
if(op == 'H'){
int x;cin>>x;
add_to_head(x);
}
else if (op == 'D'){
int k;cin>>k;
if(k == 0) head = ne[head];
del(k-1);
}
else{
int k,x;cin>>k>>x;
insert(k-1,x);
}
}
for(int i = head;i != -1;i=ne[i])cout<<e[i]<<" ";
cout<<endl;
fclose(stdin);
return 0;
}
# 栈程序模板
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int stk[10],tt;
void push(int x){
stk[++tt]=x;
}
void pop(){
tt--;
}
void empty(){
if(tt == 0)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
void query(){
cout<<stk[tt]<<endl;
}
int main(){
freopen("stack.in","r",stdin);
int m;cin>>m;
while(m--){
string op;cin>>op;
if(op == "push"){
int x;cin>>x;
push(x);
}
if(op == "pop")pop();
if(op == "empty")empty();
if(op == "query")query();
}
fclose(stdin);
return 0;
}
# 单调栈模板
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int stk[N],tt;
int main(){
freopen("ddstk.in","r",stdin)
int n;cin>>n;
while(n--){
int x;cin>>x;
while(stk[tt] >= x)tt--;
if(tt == 0)cout<<"-1"<<" ";
else cout<<stk[tt]<<" ";
stk[++tt] =x;
}
cout<<endl;
return 0;
}
# 队列模板
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int qq[N],hh,tt = -1;
void push(int x){
qq[++tt] = x;
}
void pop(){
hh++;
}
void empty(){
if(tt < hh)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
void query(){
cout<<qq[tt]<<endl;
}
int main(){
freopen("queue.in","r",stdin);
int m;cin>>m;
while(m--){
string op;cin>>op;
if(op == "push"){
int x;cin>>x;
push(x);
}
if(op == "pop")pop();
if(op == "empty")empty();
if(op == "query")query();
}
cout<<endl;
}
# 单调队列模板
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N],q[N],hh,tt;
int main(){
freopen("ddque.in","r",stdin);
int n,k;cin>>n>>k;
for(int i = 0;i < n;i++)cin>>a[i];
for(int i = 0;i<n;i++){
if(hh <= tt && i-k+1>q[hh])hh++;
while(hh <= tt&&a[q[tt]]>= a[i])tt--;
q[++tt] = i;
if(i>=k-1)cout<<a[q[hh]]<<" ";
}
cout<<endl;
hh=0;tt=-1;
for(int i = 0;i<n;i++){
if(hh <= tt && i-k+1>q[hh])hh++;
while(hh <= tt&&a[q[tt]]<= a[i])tt--;
q[++tt] = i;
if(i>=k-1)cout<<a[q[hh]]<<" ";
}
}
# 哈希拉链法
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int hashtable[N],e[N],ne[N],idx;
void insert(int x){
int k=(x%N+N)%N;
e[idx] = x;ne[idx] = hashtable[k];hashtable[k] = idx++;
}
void find(int x){
int k=(x%N+N)%N;
for(int i = hashtable[k];i != -1;i=ne[i])if(e[i] == x){
cout<<"Yes"<<endl; return ;
}
cout<<"No"<<endl;
}
int main(){
freopen("hash.in","r",stdin);
memset(hashtable,-1,sizeof hashtable);
int m;cin>>m;
while(m--){
char op;int x;cin>>op>>x;
if(op == 'I')insert(x);
if(op == 'Q')find(x);
}
return 0;
}
# 哈希开放地址法
#include<bits/stdc++.h>
using namespace std;
const int N = 3*(1e5+10);
int hashmap[N];
int find(int x){
int m = (x%N+N)%N;
while(hashmap[m] != 0x3f3f3f3f && hashmap[m] != x){
m++;
if(m == N)m=0;
}
return m;
}
int main(){
memset(hashmap,0x3f,sizeof hashmap);
int m;cin>>m;
while(m--){
char op;int x;cin>>op>>x;
if(op == 'I')hashmap[find(x)] = x;
if(op == 'Q'){
if(hashmap[find(x)] == x)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
# 字符串哈希
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10,P=1331; // P=131
typedef unsigned long long ULL;
int n,m;string s;
ULL h[N],p[N];
ULL calc(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
void setup(){
p[0] = 1;h[0] = 0;
for(int i = 0;i<n;i++){
p[i+1] = p[i] * P;
h[i+1] = h[i] * P + s[i];
}
}
int main(){
cin>>n>>m>>s;
setup();
while(m--){
int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
if(calc(l1,r1) == calc(l2,r2))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
# 试除法素数
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n){
//int srt=sqrt(n);
if(n<2)return false;
for(int i = 2;i /*< n*/ /*<= srt*//* *i<=n */ <= n/i ;i++)if(n % i == 0)return false;
return true;
}
int main(){
int n;cin>>n;
int m;
while(n--){
cin>>m;
if(isPrime(m))cout<<"Yes"<<" ";
else cout<<"No"<<" ";
}
return 0;
}
# 分解质因数
#include<bits/stdc++.h>
using namespace std;
void device(int x){
for(int i = 2;i<=x/i;i++)if(x%i==0){
int s=0;
while(x%i==0){
x/=i;
s++;
}
cout<<i<<" "<<s<<endl;
}
if(x>1)cout<<x<<" "<<1<<endl;
cout<<endl;
}
int main(){
int n;cin>>n;
int m;
while(n--){
cin>>m;
device(m);
}
}
# 筛质数的方法（函数部分）
# 前提条件：
const int N = 1e6+10;
bool st[N];int primes[N],cnt;
# 朴素筛法
void getPrimes(int n){
for(int i = 2;i<=n;i++){
if(!st[i])primes[cnt++] = i;
for(int j=2*i;j<=n;j+=i)st[j] = true;
}
}
# 埃式筛法
void getPrimes(int n){
for(int i = 2;i<=n;i++){
if(!st[i]){
primes[cnt++] = i;
for(int j=2*i;j<=n;j+=i)st[j] = true;
}
}
}
# 欧拉筛法
void getPrimes(int n){
for(int i = 2;i<=n;i++){
if(!st[i])primes[cnt++] = i;
for(int j=0;primes[j]<=n/i;j++){
st[i*primes[j]] = true;
if(i%primes[j] == 0) break;
}
}
}
# 试除法求约数
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int res[N],idx;
void ans(int m){
idx = 0;
for(int i = 1;i<=m/i;i++){
if(m%i==0){
res[idx++] =i;
if(i!=m/i)res[idx++] = m/i;
}
}
sort(res,res+idx);
for(int i = 0;i<idx;i++)cout<<res[i]<<" ";
cout<<endl;
}
int main(){
int n;cin>>n;
while(n--){
int m;cin>>m;
ans(m);
}
return 0;
}
# 辗转相除法求最大公约数
#include<iostream>
using namespace std;
int main(){
int n;cin>>n;
while(n--){
int a,b;cin>>a>>b;
// if(a % b == 0){ 这一段是优化
// cout<<b<<endl; 聊胜于无
// continue;
// }
while(b){
int c = a%b;
a=b;
b=c;
}
cout<<a<<endl;
}
}
# 约数个数
#include<bits/stdc++.h>
using namespace std;
const int M = 1e9+7;
unordered_map<int,int> h;
int main(){
int n;cin>>n;
while(n--){
int m;cin>>m;
for(int i = 2;i<=m/i;i++){
while(m%i==0){
h[i]++;
m/=i;
}
}
if(m>1)h[m]++;
}
long long res=1;
for(auto iter=h.begin();iter!=h.end();iter++)
res=res*(iter->second+1)%M;
cout<<res<<endl;
return 0;
}
# 二分查找
# 数组nums里查找target最暴力方法:
int search(vector<int>& nums, int target) {
for(int i = 0;i<nums.size();i++){
if(nums[i] == target)return i;
}
return -1;
}
# 数组nums里查找target的二分方法:
int search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
while(l<=r){
int m=l+((r-l)/2);
if(nums[m]>target){
r=m-1;
}else if(nums[m]<target){
l=m+1;
}else{
return m;
}
}
return -1;
}
# 二叉树的所有路径
void dfs(TreeNode* cur,vector<int>& path,vector<string>& res){
path.push_back(cur->val);
if(cur->left == nullptr && cur->right == nullptr){
string s=to_string(path[0]);
for(int i=1;i<path.size();i++){
s+="->";
s+=to_string(path[i]);
}
res.push_back(s);
}
if(cur->left){
dfs(cur->left,path,res);
path.pop_back();
}
if(cur->right){
dfs(cur->right,path,res);
path.pop_back();
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
vector<int> path;
if(root == nullptr)return res;
dfs(root,path,res);
return res;
}
# 二叉树左叶子之和
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root==nullptr)return 0;
if(root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr)return root->left->val+sumOfLeftLeaves(root->right);
return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
}
};