2024tysc1160

UID: 13427, 注册于 2024-6-14 13:23:53, 最后登录于 2026-4-1 16:28:39, 最后活动于 2026-4-1 18:22:36.

解决了 555 道题目，RP: 271.38 (No. 28)

个人简介

喵喵喵，我是小猫娘，喵~

本人是学习时长两年半的蒟蒻，天天TLE

我发誓从此以后永不JC别人

一个出衣的OIer

（原创）超级STL

还没调好

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+5;
struct vec{//约等于标准库中的vector 
	int value[N],n;
	void push_back(int x) {value[++n] = x;}
	void pop_back() {
		value[n] = 0;
		--n;
	}
	void input() {
		cin>>n;
		for(int i =1;i<=n;i++) cin>>value[i];
	}
	void output() {
		for(int i =1;i<=n;i++) cout<<value[i]<<" ";
	}
	void erase(int l,int r) {
		for(int i =l;i<=n-(r-l+1);i++) value[i] = value[i+(r-l+1)];
		n -= r-l+1;
	}
	void srt(){
		sort(value+1,value+n+1);
	}
}; 
vec operator+(vec a,vec b) {
	vec c;
	for(int i =1;i<=a.n;i++)c.push_back(a.value[i]);
	for(int i =1;i<=b.n;i++)c.push_back(b.value[i]);
	return c;
}
bool operator<(vec a,vec b) {
	for(int i =1;i<=a.n;i++){
		if(a.value[i]<b.value[i]) return 1;
		if(a.value[i]>b.value[i]) return 0;
	}
	return 0;
}
struct str{//约等于标准库中的string 
	char a[N];
	int len;
	str substr(int st,int lth){
		str res;
		for(int i =st;i<st+lth;i++){
			res.a[res.len++] = a[i];
		}
		res.len--;
		return res;
	}
	void erase(int l,int r) {
		for(int i =l;i<=len-(r-l+1);i++) a[i] = a[i+(r-l+1)];
		len -= r-l+1;
	}
	void input(){//输入 
		char tmp;
		while(cin>>tmp){
			a[len++] = tmp;
		} 
		--len;
	}
	void output(){//输出 
		for(int i =0;i<len;i++)cout<<a[i];
	}
};
bool operator<(str x,str y) {
	for(int i =0;i<min(x.len,y.len);i++){
		if(x.a[i]<y.a[i]) return 1;
		if(x.a[i]>y.a[i]) return 0;
	}
	if(x.len<y.len)return 1;
	return 0;
}
str operator+(str x,str y) {
	str res;
	for(int i =0;i<x.len;i++){
		res.a[res.len++] = x.a[i];
	}
	for(int i =0;i<y.len;i++){
		res.a[res.len++] = y.a[i];
	}
	--res.len;
	return res;
}
int main(){
}

代码

快读快写

int read(){
    int k=0,f=1;
    char c=getchar_unlocked();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar_unlocked();
    return k*f;
}
void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

倍增（st表）

#include<bits/stdc++.h>
using namespace std;
int st[100005][23],lg[100005];
int ask(int l,int r){
    int k = lg[r-l+1];
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
    int n,m;cin>>n>>m;
    lg[0] = -1;
    for(int i =1;i<=n;i++){
        lg[i] = lg[i>>1]+1;
        cin>>st[i][0];
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i =1;i+(1<<j)-1<=n;i++){
            st[i][j] = max(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
    while(m--){
        int l,r;cin>>l>>r;
        cout<<ask(l,r)<<"\n";
    }
}

链表

#include<bits/stdc++.h>
using namespace std;
struct node{
	int data;
	node * next;
};
node * p, *head=NULL,*q;
void print(){
	p=head;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<"\n";

}
int k,x,y;
void del(){
	cin>>y;
	if(y==1){
		p=head;
		head=p->next;
		delete p;
	}
	else{
		q=head;
		for(int i =1;i<y-1;i++){
		 	q=q->next;
		}
		p=q->next;
		q->next=p->next;
		delete p;
	}
	print();
}
void insert(){
	cin>>k>>x;
	q=head;
	p=new node;
	p->data=x;
	if(k==1){
		p->next=head;
		head=p;
	}
	else{
		for(int i =1;i<k-1;i++){
			q=q->next;
		}
		
		p->next=q->next;
		q->next=p;
	}
	print();
}
int main(){
	int n;cin>>n;
	for(int i =1;i<=n;i++){
		int w;cin>>w;
		p=new node;
		p->data=w;
		p->next=head;
		head=p;
	}
	insert();
	del();
}

神秘网址

https://cdn.luogu.com.cn/upload/image_hosting/z4yt0840.png

二分查找

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],x,q;
int main(){
    cin>>n;
    for(int i =1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    cin>>q;
    while(q--){
        cin>>x;
        int l = 1,r = n;
        while(l<=r){
            int mid = (l+r)>>1;
            if(a[mid]>=x) r = mid-1;
            else l = mid+1;
        }
        if(a[r+1]==x) cout<<r+1<<"\n";
        else cout<<"-1\n";
   	}
}

Dijkstra

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
vector<pii>g[10005];
int dis[10005];
void dijkstra(){
	memset(dis,127,sizeof(dis));
	priority_queue<pii,vector<pii>,greater<pii>> p;
	dis[1] = 0;
	p.push({1,0});
	while(p.size()){
		int u = p.top().first,disn = p.top().second;
		p.pop();
		if(disn>dis[u]) continue;
		for(auto i:g[u]){
			int v = i.first,w = i.second;
			if(dis[v]>dis[u]+w){
				dis[v] = dis[u]+w;
				p.push({v,dis[v]});
			}
		}
	}
     cout<<dis[n];
} 
signed main(){
	int n,m;cin>>n>>m;
	for(int i =1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		g[u].push_back({v,w}); 
	}
	dijkstra();
	
}

SPFA(它死了)

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#define pii pair<int,int>
using namespace std;
int dis[100005],inq[100005];
vector<pii>g[100005];
int n,m;
void spfa(){
	memset(dis,127,sizeof(dis));
	queue<int>q;
	q.push(1);
	dis[1] = 0;
	inq[1] = 1;
	while(q.size()){
		int u = q.front();
		q.pop();
		inq[u] = 0;
		for(auto i:g[u]){
			int v = i.first,w = i.second;
			if(dis[v]>dis[u]+w){
				dis[v] = dis[u]+w;
				if(!inq[v]){
					q.push(v);
					inq[v] = 1;
				}
			}
		} 
	} 
	cout<<dis[n];
}
signed main(){
	cin>>n>>m;
	for(int i =1;i<=m;i++){
		int u,v,w;
		g[u].push_back({v,w});
	}
	spfa(); 
}

离散化（很慢）

void ls(){
    set<int>s;
    for(int i =1;i<=n;i++){
        s.insert(a[i]);
    }
    for(int i:s){
        b[++tot] = i;
    }
    for(int i =1;i<=n;i++){
        int tmp = a[i];
        a[i] = lower_bound(b+1,b+tot+1,a[i])-b;
        c[a[i]] = tmp;
    }
}

树状数组

#include<bits/stdc++.h>
using namespace std;
int a[500005],tree[500005],s[500005],n,q;
int lowbit(int x){return x&-x;}
void add(int x,int k){
  while(x<=n){
  	tree[x] += k;
  	x += lowbit(x);
  }
} 
int query(int r){
  int res = 0;
  while(r>=1){
  	res += tree[r];
  	r -= lowbit(r);
  }
  return res;
}
int ask(int l,int r){
  return query(r)-query(l-1);
}
void init(){
  for(int i =1;i<=n;i++){
  	tree[i] = s[i]-s[i-lowbit(i)];
  }
}
signed main(){
  cin>>n>>q;
  for(int i =1;i<=n;++i){cin>>a[i];s[i] = s[i-1]+a[i];}
  init();
  while(q--){
  	int t,x,y;cin>>t>>x>>y;
  	if(t==1){
  		add(x,y);
  	} 
  	else {
  		cout<<ask(x,y)<<"\n";
  	}
  }
}

神秘的东西

MAK是猫娘的24条证据

这是MAK的抽象画：

⣿⣿⣿⠟⠛⠛⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢋⣩⣉⢻⣿⣿
⣿⣿⣿⠀⣿⣶⣕⣈⠹⠿⠿⠿⠿⠟⠛⣛⢋⣰⠣⣿⣿⠀⣿⣿
⣿⣿⣿⡀⣿⣿⣿⣧⢻⣿⣶⣷⣿⣿⣿⣿⣿⣿⠿⠶⡝⠀⣿⣿
⣿⣿⣿⣷⠘⣿⣿⣿⢏⣿⣿⣋⣀⣈⣻⣿⣿⣷⣤⣤⣿⡐⢿⣿
⣿⣿⣿⣿⣆⢩⣝⣫⣾⣿⣿⣿⣿⡟⠿⠿⠦⠀⠸⠿⣻⣿⡄⢻
⣿⣿⣿⣿⣿⡄⢻⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣾⣿⣿⣿⣿⠇⣼
⣿⣿⣿⣿⣿⣿⡄⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣰⣿
⣿⣿⣿⣿⣿⣿⠇⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢀⣿⣿
⣿⣿⣿⣿⣿⠏⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿
⣿⣿⣿⣿⠟⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⣿⣿
⣿⣿⣿⠋⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⣿⣿
⣿⣿⠋⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢸⣿

千万别打开

讲个笑话：