首页 > 其他分享 >5 线性数据结构 参考代码

5 线性数据结构 参考代码

时间：2023-07-28 20:33:54浏览次数：42  
标签：include int 代码 len ++ MAXN 线性 数据结构 scanf

P3156 [深基15.例1] 询问学号

#include <cstdio>
const int MAXN = 2000005;
int a[MAXN];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    while (m--) {
        int q;
        scanf("%d", &q);
        printf("%d\n", a[q - 1]);
    }
    return 0;
}

P3613 [深基15.例2] 寄包柜

#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 100005;
vector<int> v[MAXN];
int main()
{
	int n, q;
	scanf("%d%d", &n, &q);
	while (q--) {
		int op, i, j;
		scanf("%d%d%d", &op, &i, &j);
		if (op == 1) {
			int k; scanf("%d", &k);
			if (v[i].size() <= j) v[i].resize(j + 1);
			v[i][j] = k;
		} else {
			printf("%d\n", v[i][j]);			
		}
	}
	return 0;
}

UVA673 平衡的括号 Parentheses Balance

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 150;
char stk[MAXN], paren[MAXN];
int p;
int main()
{
	paren['['] = ']'; paren['('] = ')'; 
	int n;
	scanf("%d\n", &n);
	while (n--) {
		p = 0;
		string seq;
		getline(cin, seq);
		bool ok = true;
		for (int i = 0; i < seq.length(); i++) {
			if (seq[i] == '(' || seq[i] == '[') {
				// 入栈
				stk[p] = seq[i]; p++;
			} else {
				// stk[p-1]  seq[i]
				if (p > 0 && paren[stk[p-1]] == seq[i]) p--;
				else {
					ok = false; break;
				}
			}
		}
		if (p != 0) ok = false;
		printf("%s\n", ok ? "Yes" : "No");
	}
	return 0;
}

P1449 后缀表达式

#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
char expr[1005];
stack<int> s;
int main()
{
    scanf("%s", expr);
    int len = strlen(expr);
    int i = 0;
    while (i < len) {
        char ch = expr[i];
        if (ch == '@') break;
        if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            int n2 = s.top();
            s.pop();
            int n1 = s.top();
            s.pop();
            if (ch == '+') s.push(n1 + n2);
            else if (ch == '-') s.push(n1 - n2);
            else if (ch == '*') s.push(n1 * n2);
            else s.push(n1 / n2);
        } else {
            int n = 0;
            while (ch >= '0' && ch <= '9') {
                n = n * 10 + ch - '0';
                ++i;
                ch = expr[i];
            }
            s.push(n);
        }
        ++i;
    }
    printf("%d\n", s.top());
    return 0;
}

P1996 约瑟夫问题

#include <cstdio>
const int MAXN = 15000;
int q[MAXN], head, tail;
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		q[tail] = i; tail++;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m - 1; j++) {
			q[tail] = q[head]; tail++;
			head++;
		}
		printf("%d ", q[head]);
		head++;
	}
	return 0;
}

P1540 [NOIP2010 提高组] 机器翻译

#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 1005;
bool used[MAXN];
queue<int> que;
int main()
{
    int m, n;
    scanf("%d%d", &m, &n);
    int sz = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        if (!used[x]) {
            ++ans;
            if (sz == m) {
                int cur = que.front();
                que.pop();
                used[cur] = false;
            } else ++sz;
            que.push(x);
            used[x] = true;
        }
    }
    printf("%d\n", ans);
    return 0;
}

P1160 队列安排

#include <cstdio>
const int MAXN = 100005;
int l[MAXN], r[MAXN];
bool del[MAXN];
int main()
{
    int n;
    scanf("%d", &n);
    r[0] = 1;
    l[1] = 0;
    r[1] = n + 1;
    l[n + 1] = 1;
    for (int i = 2; i <= n; ++i) {
        int k, p;
        scanf("%d%d", &k, &p);
        if (p == 0) {
            int pre = l[k];
            r[pre] = i;
            l[i] = pre;
            r[i] = k;
            l[k] = i;
        } else {
            int suf = r[k];
            r[k] = i;
            l[i] = k;
            r[i] = suf;
            l[suf] = i;
        }
    }
    int m;
    scanf("%d", &m);
    while (m--) {
        int x;
        scanf("%d", &x);
        if (!del[x]) {
            del[x] = true;
            int pre = l[x];
            int suf = r[x];
            r[pre] = suf;
            l[suf] = pre;
        }
    }
    int cur = r[0];
    while (cur != n + 1) {
        printf("%d ", cur);
        cur = r[cur];
    }
    return 0;
}

P2058 [NOIP2016 普及组] 海港

#include <cstdio>
int t[100005], k[100005];
int x[300005], xlen;
int cnt[100005]; // cnt记录每个国家对应的乘客人数
int main()
{
    int n;
    scanf("%d", &n);
    int tp = 0, xp = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &t[i], &k[i]);
        for (int j = 0; j < k[i]; j++) {
            scanf("%d", &x[xlen]);
            if (cnt[x[xlen]] == 0) ans++;
            cnt[x[xlen]]++;
            xlen++;
        }
        // 删除到达时间小于等于Ti-86400的乘客
        while (t[tp] <= t[i] - 86400) {
            for (int j = 0; j < k[tp]; j++) {
                --cnt[x[xp]];
                if (cnt[x[xp]] == 0) ans--;
                xp++;
            }
            tp++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

P4387 [深基15.习9] 验证栈序列

#include <cstdio>
#include <stack>
using namespace std;
const int MAXN = 100005;
int in[MAXN], out[MAXN];
stack<int> s;
int main()
{
	int q;
	scanf("%d", &q);
	while (q--) {
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) scanf("%d", &in[i]);
		for (int i = 1; i <= n; i++) scanf("%d", &out[i]);
		while (!s.empty()) s.pop();
		int p = 1;
		for (int i = 1; i <= n; i++) {
			s.push(in[i]);
			while (!s.empty() && p <= n && s.top() == out[p]) {
				s.pop(); p++;
			}
		}
		printf("%s\n", s.empty() && p > n ? "Yes" : "No");
	}
	return 0;
}

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10005;
int a[MAXN], b[MAXN];
int p, q, r, n;
int getmin() {
	int res;
	if (q > r || (p <= n && a[p] < b[q])) {
		res = a[p]; p++; 
	} else {
		res = b[q]; q++;
	}
	return res;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	int ans = 0;
	p = 1; q = 1; r = 0;
	for (int i = 1; i < n; i++) {
		int cur = 0;
		cur += getmin(); cur += getmin();
		ans += cur;
		r++; b[r] = cur;
	}
	printf("%d\n", ans);
	return 0;
}

P2201 数列编辑器

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1000005;
char op[5];
stack<int> s1, s2;
int sum[MAXN], ans[MAXN];
int main()
{
    int n;
    scanf("%d", &n);
    int len = 0;
    ans[0] = -1e9;
    for (int i = 0; i < n; i++) {
        scanf("%s", op);
        if (op[0] == 'I') {
            int x;
            scanf("%d", &x);
            s1.push(x);
            ++len;
            sum[len] = sum[len - 1] + x;
            ans[len] = max(ans[len - 1], sum[len]);
        } else if (op[0] == 'D') {
            s1.pop();
            len--;
        } else if (op[0] == 'L') {
            if (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
                len--;
            }
        } else if (op[0] == 'R') {
            if (!s2.empty()) {
                s1.push(s2.top());
                s2.pop();
                len++;
                sum[len] = sum[len - 1] + s1.top();
                ans[len] = max(ans[len - 1], sum[len]);
            }
        } else {
            int k;
            scanf("%d", &k);
            printf("%d\n", ans[k]);
        }
    }
    return 0;
}

P5788 [模板] 单调栈

#include <cstdio>
#include <stack>
using namespace std;
const int MAXN = 3e6 + 5;
int h[MAXN], ans[MAXN];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    stack<int> s;
    for (int i = 1; i <= n; i++) {
        while (!s.empty() && h[s.top()] < h[i]) {
            ans[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}

P2866 [USACO06NOV] Bad Hair Day S

#include <cstdio>
#include <stack>
using namespace std;
typedef long long LL;
const int MAXN = 80005;
int h[MAXN];
stack<int> s;	// s存牛的编号而不是牛的身高
int main()
{
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
	LL ans = 0;
	for (int i = 1; i <= n; i++) {
		// 淘汰掉栈中之前<=h[i]的牛
		while (!s.empty() && h[s.top()] <= h[i]) {
			ans += i - s.top() - 1;
			s.pop();	
		}
		s.push(i);
	}
	while (!s.empty()) {	// 假设了h[n+1]是一头很高很高的牛
		ans += n - s.top();
		s.pop();
	}
	// 整体复杂度O(n)
	printf("%lld\n", ans);
	return 0;
}

P1106 删数问题

#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
const int MAXN = 255;
char num[MAXN];
bool del[MAXN];
int main()
{
	int k;
	scanf("%s%d", num, &k);
	stack<char> s;
	int len = strlen(num);
	for (int i = 0; i < len; i++) {
		while (!s.empty() && k > 0 && num[s.top()] > num[i]) {
			del[s.top()] = true; s.pop(); k--;
		}
		s.push(i);
	}
	while (!s.empty() && k > 0) {
		del[s.top()] = true; s.pop(); k--;
	}
	bool flag = false;
	for (int i = 0; i < len; i++) {
		if (!del[i] && (num[i] != '0' || flag)) {
			printf("%c", num[i]);
			flag = true;
		}
	}
	if (!flag) printf("0");
	return 0;
}

P1901 发射站

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1000005;
int h[MAXN], v[MAXN];
LL sum[MAXN];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d", &h[i], &v[i]);
	stack<int> s;
	LL ans = 0;
	for (int i = 1; i <= n; i++) {
		while (!s.empty() && h[s.top()] < h[i]) {
			sum[i] += v[s.top()]; ans = max(ans, sum[i]);
			s.pop();
		}
		s.push(i);
	}
	while (!s.empty()) s.pop();
	for (int i = n; i >= 1; i--) {
		while (!s.empty() && h[s.top()] < h[i]) {
			sum[i] += v[s.top()]; ans = max(ans, sum[i]);
			s.pop();
		}
		s.push(i);
	}
	printf("%lld\n", ans);
	return 0;
}

P1886 滑动窗口 / [模板] 单调队列

#include <cstdio>
const int MAXN = 1000005;
int a[MAXN];
struct Queue {
    int q[MAXN], head, tail;
    bool empty() { return head == tail; }
    int front() { return q[head]; }
    int back() { return q[tail - 1]; }
    void pop_front() { head++; }
    void pop_back() { tail--; }
    void push(int x) { q[tail++] = x; }  
};
Queue qmax, qmin;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        while (!qmin.empty() && qmin.front() <= i - k) qmin.pop_front();
        while (!qmin.empty() && a[qmin.back()] > a[i]) qmin.pop_back();
        qmin.push(i);
        if (i >= k) printf("%d ", a[qmin.front()]);
    }
    printf("\n");
    for (int i = 1; i <= n; i++) {
        while (!qmax.empty() && qmax.front() <= i - k) qmax.pop_front();
        while (!qmax.empty() && a[qmax.back()] < a[i]) qmax.pop_back();
        qmax.push(i);
        if (i >= k) printf("%d ", a[qmax.front()]);
    }
    printf("\n");
    return 0;
}

标签：include,int,代码,len,++,MAXN,线性,数据结构,scanf
From： https://www.cnblogs.com/ronchen/p/17588836.html

相关文章

  • 数据结构之带头节点的单链表增删改查操作实现
     单链表的定义什么是单链表   单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。   单链表的各个数据元素在物理上可以是离散存放的，每个结点除了存放数据元素外，还要存储指向下一个节点的指针。而顺序表是连续存放的，每个结点中只......
  • lazy 线段树代码
    描述 代码：1classNode{2intl,r;3intsum;4intlazy;5}67classSegmentTree{89privateNode[]tree;1011privateint[]nums;1213publicSegmentTree(int[]nums){14intn=nums.length;15......
  • idea远程连接服务器代码，进行debug操作
    1.配置远程断点 2.将你的springboot项目上传至远程服务器3.在你的远程服务器通过下面的命令启动你的项目nohupjava-Xdebug-agentlib:jdwp=transport=dt_socket,server=y,suspend=n,address=5005-jarmonitor_26-0.0.1-SNAPSHOT.jar--server.port=8000>nohup.log......
  • 深度学习-->线性回归模型
    #线性回归#创建数据集frommxnetimportndarrayasndfrommxnetimportautogradasadnum_input=2num_examples=1000true_w=[2,-3.4]true_b=4.2x=nd.random_normal(shape=(num_examples,num_input))y=true_w[0]*x[:,0]+true_w[1]*x[:,1]......
  • 4 前缀和与差分 参考代码
    P8218[深进1.例1]求区间和数列\(\{a_n\}\)的前缀和为\(S_n=\sum_{i=1}^{n}a_i=a_1+a_2+\cdots+a_n\)则区间\([l,r]\)的区间和为\(a_l+a_{l+1}+\cdots+a_r=S_r-S_{l-1}\)预处理出前缀和，则单次区间和的查询就做到了\(O(1)\)复杂度#include<cs......
  • 非线性规划【复习笔记】
    一、基本概念(一)、非线性规划数学模型非线性规划数学模型的一般形式是：\(\begin{cases}minf(\boldX)\\\quadh_i(\boldX)=0(i=1,2,\dots,m)\\\quadg_j(\boldX)\geq0(j=1,2,\dots,l)\end{cases}\)其中，\(X=(x_1,x_2,\dots,x_n)^T\)是\(n\)维欧氏空间\(E_n\)中的点......
  • 如何在VSCode中配置GitHub GPT代码辅助提示工具
    安装GitHubGPT插件（如果有的话）：在VSCode扩展市场中搜索并安装GitHubGPT插件。该插件可能还不存在，如果是这样，你可能需要开发自定义的代码提示插件。在此假设有一个现有的插件可用。安装VSCode：如果你还没有VSCode，首先要安装它。你可以从VSCode的官方网站（http://www.duozitu.com......
  • 写一段python爬虫下载登录用户商品图片的代码
    要下载登录用户的商品图片，你需要模拟登录网站并获取登录后的会话。下面是一个示例代码，用于登录网站并下载登录用户的商品图片：importrequestsimportosfrombs4importBeautifulSoupdeflogin(username,password):login_url="https://example.com/login"sessio......
  • 数据结构中队列的存储和应用
    队列：只有两个口进出数据，一个专门进入数据，另一个专门出数据，先进先出，FIFO表 一、顺序队列：存储元素的连续内存的首地址容量队头位置(出队)队尾位置(入队)[元素数量]运算：创建、销毁、清空、出队、入队、队空、队满、队头、队尾、元素数量#inclu......
  • zabbixn 源码中 ui / frontends 文件夹下的代码文件负责的是哪方面的职责
    ui/frontends代码的职责通过下载源码查看，可以看到在zabbix-4.X中前端代码在frontends目录下，zabbix-6.X在ui目录下，虽然换了个马甲，但里面都是一些php文件。在Zabbix源码中，ui/frontends文件夹下的代码文件负责处理与用户界面（UI）相关的职责。这些文件包含了Zabbix前端......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99