欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JZ DAY3总结

程序员文章站 2022-03-14 19:45:26
...

DAY3DAY3

T1T1

体面略显古怪,我竟理解题目都理解了二十分钟。
小Y 最近学习了线段树,但是由于她的智商比较低,运用的还不是很熟练。于是小R 给了她一点练习题训练,其中有一道是这样的。
这是小R 写的线段树的一段建树代码:

void build(int x,int l,int r)
{
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(x << 1,l,mid);
	build(x << 1,mid + 1,r);
}

只要调用buildtree(1,0,n) 就可以得到一颗线段树了。显然,一颗线段树一共有O(n) 个节点,因为每一个节点都代表了一个不同的区间,所以线段树上一共出现了O(n) 个不同的区间。
现在小R 给了你一个区间[l; r],他想要你告诉他一个最小的n 使得区间[l; r] 出现在了用buildtree(1,0,n) 建出来的线段树中。

L,R <= 1e9,lim <= 2e9,L/(R - L +1) <= 2e3。

EEEE

考场首先是先打了一个三十分的暴力,代码如下

#include <cstdio>
using namespace std;

int t,ll,rr,lim;

bool check(int l,int r)
{
	if (l == ll && r == rr) return 1;
	if (l == r) return 0;
	int mid = (l + r) >> 1;
	bool p = 0;
	p = p | check(l,mid);
	p = p | check(mid + 1,r);
	return p;
}

int main()
{
	scanf("%d",&t);
	while (t --)
	{
		scanf("%d%d%d",&ll,&rr,&lim);
		bool p = 0;
		if (ll == 0)
		{
			printf("%d\n",rr);
			continue;
		}
		for (int i = rr; i <= lim; i ++)
		{
			if (check(0,i)) 
			{
				printf("%d\n",i);
				p = 1;
				break;
			}
		}
		if (!p) printf("%d\n",-1);
	}
}

OK中规中矩,无任何优化的暴力。

那么考场我总感觉这题不是很难,反复思索后我有了如下思路。

对于一个给定的区间L,R,那我可以按照这个给定的区间去推它的父亲节点,这个思路其实也不难。对于一个给定的区间,那么它的父亲节点有且仅有四种可能。(有个十分显而易见的结论就是左区间一定小于等于右区间)

因此父亲节点的四种可能分别为

L,2 * R - L;

L,2 * R - L + 1;

2 * L - R - 1,R;

2 * L - R - 2,R;

所以就是一个深搜,考场由于没有判深度所以出错也就没交。

下面是AC代码

#include <cstdio>
#define ll long long
using namespace std;

const ll inf = 0x3f3f3f3f3f3f3f3f;
int l,r,lim,T;

int read()
{
	int x = 0,w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}
	return x * w;
}

ll min(ll a,ll b) {return a < b ? a : b;}

ll build(ll l,ll r,int dep)
{
	if (l == 0 && r <= lim) return r;
	if (dep > 11) return inf;
	ll res = inf;
	if (r + (r - l) <= lim) res = min(build(l,r + (r - l),dep + 1),res);
	if (l - 1 - (r - l) >= 0) res = min(build(l - 1 - (r - l),r,dep + 1),res);
	if (r + (r - l) + 1 <= lim) res = min(build(l,r + (r - l) + 1,dep + 1),res);
	if (l - 1 - (r - l) - 1 >= 0) res = min(build(l - 1 - (r - l) - 1,r,dep + 1),res);
	return res;
}

int main()
{
	T = read();
	while (T --)
	{
		l = read(),r = read(),lim = read();
		if (l == 0)
		{
			printf("%d\n",r);
			continue;
		}
		ll x = build(1ll * l,1ll * r,1);
		if (x != inf) printf("%lld\n",x); else printf("%d\n",-1);
	}
}

T2T2

小Y 最近开始学习算法姿势,但是因为小R 非常BB,给了她很多B6 题,所以她觉得自己已经没有什么前途了。于是小R 给了她一些稍微简单的题,让她觉得已经没有什么好害怕的了,其中一道是这样的:
给定一个长度为n 只包含左括号和右括号的序列,现在小R 想要知道经过每一个位置的合法子串有多少个。
空串是一个合法的串,如果A 和B 都是合法的串,那么(A) 和AB 都是合法的串。

考场最后三十分钟才思考这道题,且并未做出什么有效思考,因此直接零分。后面得知是差分+栈,暂时还没做出来,若我还记得,做出来会补上。

T3T3

小Y:“小R 你是萝莉控吗。”小R:“…”
为了避免这个尴尬的话题,小R 决定给小Y 做一道题。
有一个长度为n 的正整数数组A,满足Ai >= Ai+1,现在构造一个数组B,令Bi = sigma a[j] (j = i to n )。

现在,有一个n * n 的网格图,左下角坐标是(1, 1),右上角坐标是(n, n)。有一个小SB正在坐标为(n, 1) 的位置,每一时刻,如果他现在在(x, y),他可以选择走到(x -1,y + 1) 或者(x, (y + 1) div 2),如果选择后者,他要支付Bx的代价。
现在他想走到(1, 1),你可以告诉他他支付的代价最少是多少吗?注意在任何时候他都不能离开这个网格图。

对于30% 的数据,n <= 10
对于50% 的数据,n <=1000
对于100% 的数据,n<= 10^5,1 <= T<= 10,1 <= Ai<= 10^4

考场一看感觉可做度挺高,便先思考了最后一题。首先拿下三十分的广搜暴力。代码如下

#include <cstdio>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;

const int maxn = 1e5 + 10;
struct Node{
	int x,y;
	ll sum;
};
int T,n,a[maxn];
ll b[maxn],v[5010][5010],ans;
queue <Node> q;

ll min(ll a,ll b) {return a < b ? a : b;}

int read()
{
	int x = 0,w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
	return x * w;
}

int main()
{
	T = read();
	while (T --)
	{
		while (!q.empty()) q.pop();
		ans = 0x3f3f3f3f3f3f3f3f;
		memset(v,0x3f,sizeof v);
		memset(b,0,sizeof b);
		memset(a,0,sizeof a);
		n = read();
		for (int i = 1; i <= n; ++ i) a[i] = read();
		b[n] = 1ll * a[n];
		for (int i = n - 1; i >= 1; -- i) b[i] = b[i + 1] + 1ll * a[i];
		v[n][1] = 0;
		q.push(Node{n,1,0});
		while (!q.empty())
		{
			Node u = q.front();
			q.pop();
			if (u.x - 1 >= 1 && u.y + 1 >= 1 && u.x - 1 <= n && u.y + 1 <= n && v[u.x - 1][u.y + 1] > u.sum) 
			{
				v[u.x - 1][u.y + 1] = u.sum;
				q.push(Node{u.x - 1,u.y + 1,u.sum});
			}
			if (v[u.x][(u.y + 1) / 2] > u.sum + b[u.x]) 
			{
				v[u.x][(u.y + 1)/ 2] = u.sum + b[u.x];
				q.push(Node{u.x,(u.y + 1) / 2,u.sum + b[u.x]});	
			}		
			ans = min(ans,v[1][1]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}	

然后我竟然直接跳过了五十分的spfa,直接思考100分做法(当然没想出来),我考场想到了这一定符合某种规律,最后竟然直接套一个合并果子就过了(或哈夫曼树)。

#include <cstdio>
#include <algorithm>
using namespace std;

int T,n,a[100010],ans;

int main()
{
	scanf("%d",&T);
	while (T --)
	{
		scanf("%d",&n);
		for (int i = 1; i <= n; i ++) scanf("%d",&a[i]);
		ans = 0;
		sort(a + 1,a + 1 + n);
		int j = 1;
		while (1)
		{
			if (j == n) break; 
			else
			{
				a[j] += a[j + 1];
				ans += a[j];
				for (int i = j + 1; i < n; i ++)
				{
					a[i] = a[i + 1];
				}
				n --;
			}
			for (int i = j; i < n; i ++)
			{
				if (a[i] > a[i + 1])
				{
					swap(a[i],a[i + 1]);
				} else break;
			}
		}
		printf("%d\n",ans);	
	}
	return 0;
}

至于为什么可以直接套一个合并果子,暂时还不是非常理解,还需学习。

今天最终得分30 + 0 + 30;

PS.前两天的比赛明天补上

相关标签: 比赛总结