首页 > 其他分享 >24暑假集训day2上午

24暑假集训day2上午

时间：2024-08-03 17:20:02浏览次数：6  
标签：24 std int void 元素 day2 nx include 集训

上午

内容：基础数据结构

1. 链表

分类：单向和双向

单向：当前链表只指向下一个元素

双向：对于每个元素，记录其前面一个元素，也记录其后面一个元素。

注意：链表不建议使用 STL 的某些元素进行替代，手写链表更为方便。

1. 单向链表

做法：维护每个元素编号，然后维护 nx 指针，表示当前元素的下一个元素是谁加入和删除都是方便的。

手写的单向链表：

void ins(int x,int y){
	int to=nx[x];
	nx[x]=y,nx[y]=to;
}
void erase(int x){
	int to=nx[x];
	nx[x]=nx[to];
}

T1 单向链表

问题简述：如题

思路：我谔谔， 直接模拟

std：

#include <iostream>
using namespace std;
const int MAXN = 1e6 + 10;
int nx[MAXN];
int main(){
	int q;
	cin >> q;
	for(int i = 1;i <= q;i++){
		int op;
		cin >> op;
		if(op == 1){
			int x, y;
			cin >> x >> y;
			int a;
			a = nx[x];
			nx[x] = y;
			nx[y] = a;
		}else if(op == 2){
			int x;
			cin >> x;
			cout << nx[x] << '\n';
		}else{
			int x;
			cin >> x;
			int a = nx[x];
			nx[x] = nx[a];
		}
	}
	return 0;
}

记录

前项星

本质：多个单项链表组成，维护链头数组，然后可以支持每个点加边。

struct nod{
	int next,to;
}e[xx*2];
int cnt,h[xx];
void add(int x,int y){
	cnt++;
	e[cnt]={h[x],y};
	h[x]=cnt;	
}
void dfs(int x,int y){
	for(int i=h[x];i;i=e[i].next){
		dfs(e[i].to,x);
	}
}

T2 单向链表

思路：直接复制上述程序

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
struct Node{
	int next,to;
}e[MAXN*2];
int n,m,cnt,h[MAXN];
void add(int x,int y){
	cnt++;
	e[cnt]={h[x],y};
	h[x]=cnt;
}
int ans[MAXN],id;
void dfs(int x){
	if(!ans[x])ans[x]=id;
	else return;
	for(int i=h[x];i;i=e[i].next)dfs(e[i].to);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		add(b,a); 
	}
	for(int i=n;i>=1;i--)id=i,dfs(i);
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
	return 0;
}

记录

2. 双向链表

做法：每个元素维护前驱 \(\text{pr}\) 和后继 \(\text{nx}\) 两个数组，可以实现动态增删的操作

手写的双向链表：

void ins(int x,int y){
	int to=nx[x];
	nx[x]=y,pr[to]=y;
	pr[y]=x,nx[y]=to;
}
void era(int x){
	int L=pr[x],R=nx[x];
	nx[L]=R,pr[R]=L;
}

2. 栈

做法：维护一个序列，每次从末端加入元素，然后末端弹出元素

具体维护：使用一个数组，维护一个 \(\text{tp}\) 指针进行处理

手写的栈：

int stk[xx],tp;
void push(int x){
	stk[++tp]=x;
}
int top(){
	return stk[tp];	
}
void pop(){
	--tp;
}

STL 的栈：

stack<int>stk;
stk.push(1);
stk.pop();
cout<<stk.top()<<"\n";
cout<<stk.size()<<"\n";

T3 栈

模板题直接用 STL。

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
#define int unsigned long long
stack<int>stk;
void a(int n){
	for(int i = 1;i <= n;i++){
		string op;
		cin >> op;
		if(op == "push"){
			int x;
			cin >> x;
			stk.push(x);
		} else if(op == "pop"){
			if(!stk.empty()){
				stk.pop();
			} else {
				cout << "Empty" << '\n';
			}
		} else if(op == "query"){
			if(!stk.empty()){
				cout << stk.top() << '\n';
			} else {
				cout << "Anguei!" << '\n';
			}
		} else if(op == "size"){
			cout << stk.size() << '\n';
		}
	}
}
int t, n;
signed main(){
	cin >> t;
	for(int i = 1;i <= t;i++){
		int n;
		cin >> n;
		a(n);
		while(!stk.empty()){
			stk.pop();
		}
	}
	/*
	stack<int>stk;
	stk.top();
	stk.pop();
	cout << stk.top() << '\n';
	cout << stk.size() << '\n';
	*/
	return 0;
}

记录

单调栈

实质：用栈维护了单调的结构

T3 栈

问题简述：给定一个长度为 \(n\) 的数列 \(a_i\)。然后，对于每个元素，找到在这个元素之后，第一个大于当前元素的下标。

方法：从后往前枚举，栈内维护单调的下标，满足这些下标的值是递减的

关键：保留对当前状态最优的信息。

#include<bits/stdc++.h>
using namespace std;
int n,a[3000005];
int top,ans[3000005],maxn;
struct node{
    int val,i;
};
stack<node>sta;
stack<int>p; 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]; 
    }
    for(int i=n;i>=1;i--){
        int vis=0;
        while(!sta.empty()){
            if(a[i]<sta.top().val){
                p.push(sta.top().i);
                vis=1;
                break;
            }
            else sta.pop();
        }
        if(!vis)p.push(0);
        sta.push((node){a[i],i});
    }
    for(int i=1;i<=n;i++){
        cout<<p.top()<<' ';
        p.pop();
    }
}

记录

3. 队列

方法：后进先出

手写的队列：

int q[xx],l,r;
void push(int x){
	q[++r]=x;
}
int front(){
	return q[l];
}
void pop(){
	l++;
}

STL 队列：

queue<int>q;
q.push(1);
q.pop();
cout<<q.front()<<"\n";
cout<<q.size()<<"\n";

T4 队列

模板题直接用 STL。

#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		int op;
		cin >> op;
		if(op == 1){
			int x;
			cin >> x;
			q.push(x);
		} else if(op == 2){
			if(!q.empty()){
				q.pop();
			} else {
				cout << "ERR_CANNOT_POP" << '\n';
			}
		} else if(op == 3){
			if(!q.empty()){
				cout << q.front() << '\n';
			} else {
				cout << "ERR_CANNOT_QUERY" << '\n';
			}
		} else {
			cout << q.size() << '\n';
		}
	}
	return 0;
}

单调队列

定义：权值是递减的（求目前最大值），但是 \(\text{id}\) 是递增的（有 \(\text{id}\) 大于某个位置的限制），有单调性质。

关键：保留对于当前而言更优的一个信息。

T5 单调队列

方法：

  1. 判断队首元素是否超出范围，如果是，则队首元素出队；

  2. 判断队尾元素是否满足要求（例如求区间最大值，要求则为队尾元素小于插入的元素），如果是，则队尾元素出队，返回步骤 \(2\)；如果不是，则进入下一步；

  3. 将元素插入队尾。

std：

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int q[1000005];
int l, r;
int read() {
    char c;
    int w = 1;

    while ((c = getchar()) > '9' || c < '0')
        if (c == '-')
            w = -1;

    int ans = c - '0';

    while ((c = getchar()) >= '0' && c <= '9')
        ans = (ans << 1) + (ans << 3) + c - '0';

    return ans * w;
}
int m;
int main() {
    int n;
    n = read();
    m = read();

    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }

    l = r = 1;
    q[1] = 1;

    for (int i = 1; i <= n + 1; i++) {
        while (l <= r && q[l] < i - m)
            l++;

        if (i > m)
            printf("%d ", a[q[l]]);

        while (l <= r && a[q[r]] >= a[i])
            r--;

        q[++r] = i;
    }

    l = r = 1;
    q[1] = 1;
    cout << endl;

    for (int i = 1; i <= n + 1; i++) {
        while (l <= r && q[l] < i - m)
            l++;

        if (i > m)
            printf("%d ", a[q[l]]);

        while (l <= r && a[q[r]] <= a[i])
            r--;

        q[++r] = i;
    }

    return 0;
}

记录

4. 队列

方法：维护一个序列，每次加入一个元素，询问当前序列中最小的元素，然后删除最小元素。

具体维护：一般维护的称为二叉堆，即维护一个结构，支持上述处理过程。

每个节点 \(i\) 储存一个权值，左儿子是 \(2 \cdot i\)，右儿子是 \(2 \cdot i + 1\)。

手写的堆：

int hp[xx],sz;
void push(int val){
	int id=++sz;
	hp[id]=val;
	while(id!=1){
		int to=id/2;
		if(hp[id]<hp[to])swap(hp[id],hp[to]);
		id=to;
	}
}
void pop(){
	hp[1]=hp[sz],--sz;
	int id=1;
	while((id*2)<=sz){
		int L=id*2,R=id*2+1,ty=L;
		if(R<=sz&&hp[R]<hp[ty])ty=R;
		if(hp[ty]<hp[id])swap(hp[ty],hp[id])
		id=ty;
	}
}

STL 堆：

priority_queue<int>q;//大根堆!
q.push(1),q.pop();
cout<<g.top()<<"\n";
cout<<q,size()<<\n";

priority_queue<int,vector<int>,greater<int>>q;//小根堆!
q.push(1),q.pop();
cout<<g.top()<<"\n";
cout<<q.size()<<"\n";

T5 堆

思路：模板是小根堆，直接用STL

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1000005;
priority_queue<int,vector<int>,less<int> > h;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            h.push(-x);
        }else if(op==2)cout<<-h.top()<<'\n';
        else h.pop();
    }
    return 0;
}

记录

对顶堆

T6 堆

问题简述：一个序列，我们每次加入一个元素，或者进行询问。
维护一个初始指针 \(i=0\)，每次询问的时候将 \(i=i+1\) 然后询问第 \(i\) 小的值是多少。

思路：使用两个堆，把序列分为前半和后半，分界点位置就是我们尝试输出的值。

std：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
priority_queue<int>q1, q2;
int a[MAXN], u[MAXN];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>u[i];
        for(int l=u[i-1]+1;l<=u[i];l++){
            q2.push(a[l]);
        }
        while(q1.size()&&q2.size()&&-q1.top()<q2.top()){
            q1.push(-q2.top());
            q2.pop();
        }
        while(q2.size()<i){
            q2.push(-q1.top());
            q1.pop();
        } 
        while(q2.size()>i){
            q1.push(-q2.top());
            q2.pop();
        }
        cout<<q2.top()<<endl;
    }
    return 0;
}

记录

5. 哈夫曼树

本质：在堆的基础上的一点点贪心的扩展

性质：
每个数贡献的次数是他到根的边数。
数大的贡献较少，即经过的边数较少。
如果把边顺次标号为 \(0, 1\)，则每个叶子到根的一个字符串称为哈夫曼编码。

T7 合并果子

问题简述：有 \(n\) 堆果子，第 \(i\) 堆初始为 \(a_i\) 大，然后你需要做 \(n − 1\) 次操作，
每次选择两堆果子，将其合并为一堆，
即删除原来两堆 \(i, j\) 变成新堆 \(a_i + a_j\)，并消耗新堆大小的体力，问：最少消耗体力。

std：

#include <iostream>
#include <queue>
using namespace std;
int n, x, ans;
priority_queue<int, vector<int>, greater<int> >q;
int main(){
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> x;
		q.push(x);
	}
	while(q.size() >= 2){
		int a = q.top();
		q.pop();
		int b = q.top();
		q.pop();
		ans += a + b;
		q.push(a + b);
	}
	cout << ans << endl;
	return 0;
}

记录

哈夫曼树扩展

思路：选择最小的两堆合并，并一直执行这个过程

多叉的哈夫曼树同样涉及到一个补 \(0\) 的贪心思想。
具体的，补其 \(0\) 使得 \(n − 1 \bmod (k − 1) = 0\)。

T8 荷马史诗

问题简述：给定 \(n\) 个单词的出现次数，请你用字符集大小为 \(k\) 的字符串来替换每个单词，使得每个单词的出现次数乘对应字符串的长度最小，你需要满足要求：对于任意两个单词对应的字符串不应该有前缀包含关系，比如 \(\texttt{abbc}\) 前缀包含 \(\texttt{abb}\)。

思路：注意到，没有前缀包含关系完全对应了哈夫曼编码，而我们最优化次数正好是哈夫曼树的最小的贡献！
所以我们建立扩展的 \(k\) 叉哈夫曼树即可得到答案。

std：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
	char c;
	int w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	int ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
priority_queue<pair<int,int> >q;
int a[5000005];
int n;
int k;
signed main(){
	n=read();
	k=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		q.push(make_pair(-a[i],-1));
	}
	while((n-1)%(k-1))n++,q.push(make_pair(0,-1));
	int anss=0;
	for(int i=1;i<=(n-1)/(k-1);i++)
	{
		int ans=0;
		int maxx=0;
		for(int j=1;j<=k;j++)
		{
			ans+=(-q.top().first);
			maxx=max(maxx,-q.top().second);
			q.pop();
		}
		anss+=ans;
		q.push(make_pair(-ans,-maxx-1));
	}
	cout<<anss<<endl<<-q.top().second-1<<endl;
	return 0;
}

记录

标签：24,std,int,void,元素,day2,nx,include,集训
From： https://www.cnblogs.com/yantaiyzy2024/p/18340807

相关文章

  • 24暑假集训day1上午
    上午内容：枚举递推贪心广告：推荐此题单1.枚举枚举：最基础、最容易想到本质：不重复，不遗漏T1数的划分问题简述：将整数\(n\)分成\(k\)份，且每份不能为空，任意两个方案不相同（不考虑顺序）。方法：搜索关键：有顺序具体步骤：尝试从大到小进行拆分，我们记录当前数剩下总和，记录当前还需......
  • 24暑假集训day3下午
    实现代码：intexgcd(inta,intb,int&x,int&y){ if(b==0){ x=1; y=0; returna; } intd=exgcd(b,a%b,x,y); intk=x; x=y; y=k-(a/b)*y; returnd;}intmain(){ inta=read(),b=read(); intx,y; intd=exgcd(a......
  • 24暑假集训day3上午
    进制转换一个\(m\)进制的数字\(\overline{a_0a_1\cdotsa_k}\)实际上是\(a_0m^k+a_1m^{k-1}+\cdots+a_k\)。\(10\)进制转\(m\)进制：每次除以\(m\)并取出余数。\(m\)进制转\(10\)进制：计算\(a_0m^k+a_1m^{k-}+\cdots+a_k\)。进制转换问题简述：将\(n\)进制数转换......
  • 24暑假集训day2下午
    下午内容：STL差分前缀和倍增1.STL#include<iostream>#include<queue>#include<cmath>#include<algorithm>#include<vector>#include<cstring>#include<cstdio>#include<set>#include<map>#include<uno......
  • 24暑假集训day6上午&下午
    DP概念状态、转移方程、初始化先放一张图（相信都能理解：状态、转移方程、初始化的含义，随便引入斐波那契数列的题）入门题Problem1斐波那契数列\[f_i=f_{i-1}+f_{i-2}\]组合数转移方程：\[C(n,m)=C(n-1,m-1)+C(n-1,m)\]\[C(n,0)=1\]杨辉三角：\[f[i][j]=f[i-1][j-1]+f[i-1]......
  • 24暑假集训day5下午
    DFS本质：一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。该算法讲解时常常与BFS并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况。关键：递归调用自身对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以......
  • 24暑假集训day5上午
    图论差分约束有\(......
  • 24暑假集训day4上午&下午
    基础图论图的存储方式无向边可以拆成两条有向边1.邻接矩阵邻接矩阵：若\(......
  • Day 8.2 NOIP2024 模拟赛 总结
    Day8.2NOIP模拟赛总结T1T1赛时打表输出发现了等差数列的性质（好像不需要打表也能知道），然后我码完T2过后剩不到2个小时了，于是连T3T4暴力都没码就过来推了，但也没推出来，时间倒是耽误了不少，剩一个小时的时候去开始去码后面的暴力了。T2水题一道，做法，性质全给了。只不过比较玄学的......
  • 20240803题解
    话说T3都把式子推出来了结果忘记差分约束怎么写了。光线(light)题面：有\(n\)个玻璃板，第\(i\)个玻璃板的透光率为\(a_i\%\)，反射率为\(b_i\%\)，有大小为\(1\)个单位的一束光从第\(1\)个玻璃板开始，有多少光能穿透\(n\)层玻璃板。题解：考虑\(n=2\)时，可以简单算出两个玻璃板组合后的反......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99