20160819 训练记录

tonyfang posted @ 2016年8月21日 14:08 in 随笔 with tags c++ OI , 766 阅读

1. 要依次插入$n$个数,分别为$1,2, ..., n$,第$i$个数要插在当前第$a_i$个数的右边,求最后序列。

【题解】

很明显考虑从后往前插入,那么我们就能用一棵线段树搞定啦!

 

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <iostream>
# include <algorithm>

using namespace std;

int n, a[1000010], f[1000010];

// ================================ //
int lc[8000010], rc[8000010];
int w[8000010];
inline void build(int x, int l, int r) {
	lc[x]=l, rc[x]=r; 
	if(l==r) {
		w[x] = 1;
 		return;
	}
	int mid=l+r>>1;
	build(x<<1, l, mid);
	build(x<<1|1, mid+1, r);
	w[x] = w[x<<1] + w[x<<1|1];
}

inline int get(int x, int c) {
	int L=lc[x], R=rc[x];
	w[x] --;
	if(L == R) return L;
	if(w[x<<1] >= c) return get(x<<1, c);
	else return get(x<<1|1, c-w[x<<1]);
}
// ================================ //
int cx;char ch;
inline int getint() {
	cx=0;
	ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) {
		cx=(cx<<3)+(cx<<1)+ch-'0';
		ch=getchar();
	}
	return cx;
}
int wss[8], wsn=0;
inline void putint(int x) {
	wsn=0;
	while(x) {
		wss[++wsn] = x%10;
		x=x/10;
	}
	for (int i=wsn; i>=1; --i) putchar(wss[i]+'0');
	putchar(' ');
}

int main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	n=getint();
	for (int i=1; i<=n; ++i) a[i] = getint();
	build(1, 1, n);
	for (int i=n; i>=1; --i) {
		int pos = get(1, a[i]+1);
//		printf("POS=%d\n", pos);
		f[pos] = i; 

	}
	
	for (int i=1; i<=n; ++i) putint(f[i]); 
	puts("");
	
	return 0;
}

2. 给$n$个物品,有重量和价值,要求在重量不超过$m$的情况下,最大化价值。

$n \leq 40, m \leq 10^{18}$

【题解】这不就是折半?然后建线段树变成区间查询啦!

复杂度$O(n 2^{n/2})$

 

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>

using namespace std;

int n;
long long m;
long long x[50], w[50];

struct pir {
	long long sum;
	long long ws;
} p[2000100];
int pn=0;

long long ans=0;

int lc[5000010], rc[5000010];
long long wc[5000010], xl[5000010], xr[5000010];

inline long long MAX(long long a, long long b) {
	return a>b?a:b;
}

// ======================== //
inline void build(int x, int l, int r) {
	lc[x] = l, rc[x] = r;
	if(l == r) {
		wc[x] = p[l].ws;
		xl[x] = xr[x] = p[l].sum;
		return ;
	}
	int mid=l+r>>1;
	build(x<<1, l, mid);
	build(x<<1|1, mid+1, r);
	wc[x] = MAX(wc[x<<1], wc[x<<1|1]);
	xl[x] = xl[x<<1], xr[x] = xr[x<<1|1];
}

inline long long query(int x, long long xs) {
//	printf("x=%d, xs=%I64d, xl=%I64d, xr=%I64d\n", x, xs, xl[x], xr[x]);
	int l=lc[x], r=rc[x];
	if(xl[x] > xs) return 0;
	if(xr[x] <= xs) return wc[x];
	if(xs < xr[x<<1]) return query(x<<1, xs);
	else return MAX(query(x<<1, xs), query(x<<1|1, xs));
}
// ======================== //


inline void dfs1(int step, long long sum, long long ws) {
	if(sum>m) return;
	if(step == n/2+1) {
		p[++pn].sum = sum, p[pn].ws = ws;
		return ;
	}
	dfs1(step+1, sum+x[step], ws+w[step]);
	dfs1(step+1, sum, ws);
}

inline bool cmp(pir a, pir b) {
	return a.sum < b.sum || (a.sum == b.sum && a.ws < b.ws);
}

inline void dfs2(int step, long long sum, long long ws) {
	if(sum>m) return ;
	if(step == n+1) {
		if(m-sum<0) return;
//		printf("%d %I64d %I64d\n", step, m-sum, ws);
		long long cur = ws + query(1, m-sum);
		if(cur>ans) ans=cur;
		return ;
	}
	dfs2(step+1, sum+x[step], ws+w[step]);
	dfs2(step+1, sum, ws);
}



int main() {
	freopen("pack.in", "r", stdin);
	freopen("pack.out", "w", stdout);
	scanf("%d%I64d", &n, &m);
	
//	printf("%I64d\n", (long long)sizeof(p)+sizeof(x)+sizeof(w)+sizeof(lc)+sizeof(rc)+sizeof(wc)+sizeof(xl)+sizeof(xr));
	
	for (int i=1; i<=n; ++i)
		scanf("%I64d%I64d", &x[i], &w[i]);
	
	dfs1(1, 0, 0);
	sort(p+1, p+pn+1, cmp);
	
//	for (int i=1; i<=pn; ++i) {
//		printf("sum=%I64d ws=%I64d\n", p[i].sum, p[i].ws);
//	}
	build(1, 1, pn);
//	for (int i=1; i<=pn*4; ++i)
//		printf("i=%d, lc=%d, rc=%d, xl=%I64d, xr=%I64d, wx=%I64d\n", i, lc[i], rc[i], xl[i], xr[i], wc[i]);
	
	
	dfs2(n/2+1, 0, 0);
	// sum + pi < m && max(qi+ws)
	printf("%I64d\n", ans);
	
	return 0;
}

3. 给你一个线段树,每个节点的左儿子区间为$[l, k]$,右儿子为$[k+1, r]$,对于每个点任意选取$k$。

对于询问一个区间$[l, r]$,会访问到所有的叶子节点。对于$m$个询问,求出最少访问多少个节点。

$ n \leq 5000, m \leq 100000$

【题解】

区间dp。$f[i,j]$表示区间$[i,j]$的最少访问次数。那么转移方程很好列。之后直接套上四边形不等式优化就行啦

 

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>

using namespace std;

int n, m;
int f[5050][5050];
int p[5050][5050];
int w[5050][5050];
int left[5050], right[5050];

int main() {
	freopen("segment.in", "r", stdin);
	freopen("segment.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	for (int i=1, a, b; i<=m; ++i) {
		scanf("%d%d", &a, &b);
		left[a] ++;
		right[b] ++;
	}
	for (int i=n; i>=1; --i) left[i] += left[i+1];
	for (int i=1; i<=n; ++i) right[i] += right[i-1];
	for (int i=1; i<=n; ++i)
		for (int j=i; j<=n; ++j) {
			w[i][j] = m-left[j+1]-right[i-1];
			if(i==j) f[i][j]=w[i][j], p[i][i] = i;
		}
	for (int len=1; len<=n; ++len) 
		for (int i=1; i<=n-len+1; ++i) {
			int j = i+len;
			f[i][j] = 2000000000LL;
			for (int k=p[i][j-1]; k<=p[i+1][j]; ++k)
				if(f[i][k] + f[k+1][j] + w[i][j] < f[i][j]) {
					f[i][j] = f[i][k] + f[k+1][j] + w[i][j];
					p[i][j] = k;
				} 
		}
	printf("%d\n", f[1][n]);	
	return 0;
}
/*
6 6
1 4
2 6
3 4
3 5
2 3
5 6
*/
boardmodelpaper.com 说:
2024年1月18日 16:52

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter