JOISC 2014 Day1

KafuuChinocpp / 2023-05-03 / 原文

T1 巴士走读

考虑在每个节点 \(u\) 维护 \(f_u(x)\) 表示在时刻 \(x\) 到达节点 \(u\) 时的最晚出发时间，显然这个函数单调递增。考虑进行转移，将所有巴士按照 \(Y\) 进行排序，依次枚举每辆巴士，设巴士出发节点为 \(A\) ，终止节点为 \(B\) ，发车时间为 \(X\) ，到达时间为 \(Y\) ，由于我们按照时间进行排序，因此 \(f_u(x)(x\le Y-1)\) 已经求解完毕，转移没有后效性，此时我们有转移 \(f_A(X)\to f_B(Y)\) 。由于可以在车站停留，因此存在转移 \(f_u(x)\to f_u(x+1)\) 。考虑到每个节点存在很多状态数值相同，因此可以在每个节点维护 vector 用于保存第一种转移产生的有用状态，同时由于函数单调递增，可以舍弃第二种转移，因为我们可以通过在 vector 内二分第一个有用的状态来查询任意的 \(f_u(x)\) ，复杂度 \(O(n\log n)\) 。

code

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int max1 = 1e5, lim = 1e8;
int n, m, q, save[max1 * 6 + 5], len;
struct Node
{
	int A, B, X, Y;
	bool operator < ( const Node &A ) const
		{ return Y < A.Y; }
}edge[max1 * 3 + 5];
struct Data
{
	int tim, x;
	Data () {}
	Data ( int __tim, int __x )
		{ tim = __tim, x = __x; }
	bool operator < ( const Data &A ) const
		{ return tim < A.tim; }
};
vector <Data> f[max1 + 5];
int main ()
{
	scanf("%d%d", &n, &m);
	for ( int i = 1; i <= m; i ++ )
		scanf("%d%d%d%d", &edge[i].A, &edge[i].B, &edge[i].X, &edge[i].Y), save[++len] = edge[i].X, save[++len] = edge[i].Y;
	sort(edge + 1, edge + 1 + m);
	sort(save + 1, save + 1 + len);
	len = unique(save + 1, save + 1 + len) - ( save + 1 );
	for ( int i = 1; i <= len; i ++ )
		f[1].push_back(Data(save[i], save[i]));
	for ( int i = 1; i <= m; i ++ )
	{
		int A = edge[i].A, B = edge[i].B, X = edge[i].X, Y = edge[i].Y;
		auto it = upper_bound(f[A].begin(), f[A].end(), Data(X, 0));
		if ( it == f[A].begin() )
			continue;
		--it;
		int up = it -> x;
		if ( !f[B].empty() )
			up = max(up, f[B].back().x);
		if ( f[B].empty() || f[B].back().tim != Y )
			f[B].push_back(Data(Y, up));
		else
			f[B].back().x = up;
	}
	scanf("%d", &q);
	int tim;
	for ( int i = 1; i <= q; i ++ )
	{
		scanf("%d", &tim);
		auto it = upper_bound(f[n].begin(), f[n].end(), Data(tim, 0));
		if ( it == f[n].begin() )
			printf("-1\n");
		else
			printf("%d\n", (--it) -> x);
	}
	return 0;
}

T2 有趣的家庭菜园

发现一种方案合法的条件是 \(h_i\) 构成单峰函数，考虑贪心地进行构造，将所有位置按照 \(h_i\) 从大到小排序，不考虑元素相同的情况，发现当前决策的元素有插入到峰的左边和峰的右边两种选择，设当前峰构成的集合为 \(S\) ，设当前元素所在的位置为 \(i\) ，如果放在峰的左边，这个元素会对 \(S\) 内所有位置小于 \(i\) 的元素的移动次数产生 \(1\) 的贡献，如果放在峰的右边，这个元素会对 \(S\) 内所有位置大于 \(i\) 的元素的移动次数产生 \(1\) 的贡献，由于 \(S\) 不会因为当前元素的决策放生变化，因此直接贪心选择位置是正确的。考虑存在相同元素的情况，将所有相同的元素一同考虑，容易发现最终形成的序列相同元素一定按照原先的位置顺序进行排列，因为这样相同元素两两之间不会产生贡献，因此可以按照元素种类依次考虑。

code

#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 3e5;
const long long inf = 0x3f3f3f3f3f3f3f3f;
int n;
struct Point
{
	int high, pos;
	bool operator < ( const Point &A ) const
		{ return high > A.high; }
}p[max1 + 5];
long long ans;
struct Bit
{
	#define lowbit(now) ( now & -now )
	int tree[max1 + 5];
	void Clear ()
	{
		for ( int i = 1; i <= n; i ++ )
			tree[i] = 0;
		return;
	}
	void Insert ( int now, int x )
	{
		while ( now <= n )
		{
			tree[now] += x;
			now += lowbit(now);
		}
		return;
	}
	int Query ( int now )
	{
		int res = 0;
		while ( now )
		{
			res += tree[now];
			now -= lowbit(now);
		}
		return res;
	}
	int Query ( int L, int R )
		{ return Query(R) - Query(L - 1); }
}Tree;
int main ()
{
	scanf("%d", &n);
	for ( int i = 1; i <= n; i ++ )
		scanf("%d", &p[i].high), p[i].pos = i;
	sort(p + 1, p + 1 + n);
	Tree.Clear();
	for ( int L = 1, R; L <= n; L = R + 1 )
	{
		R = L - 1;
		while ( R + 1 <= n && p[R + 1].high == p[L].high )
			++R;
		for ( int i = L; i <= R; i ++ )
			ans += min(Tree.Query(1, p[i].pos), Tree.Query(p[i].pos, n));
		for ( int i = L; i <= R; i ++ )
			Tree.Insert(p[i].pos, 1);
	}
	printf("%lld\n", ans);
	return 0;
}

T3 历史研究

回滚莫队板子题？

code

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int max1 = 1e5, max2 = 316;
int n, q, x[max1 + 5], save[max1 + 5], siz;
int len, block, op[max2 + 5], ed[max2 + 5], belong[max1 + 5];
struct Question
{
	int id, L, R;
	bool operator < ( const Question &A ) const
	{
		if ( belong[L] == belong[A.L] )
			return R < A.R;
		return L < A.L;
	}
}qus[max1 + 5];
int bin[max1 + 5];
long long max_val, ans[max1 + 5];
int main ()
{
	scanf("%d%d", &n, &q);
	for ( int i = 1; i <= n; i ++ )
		scanf("%d", &x[i]), save[i] = x[i];
	sort(save + 1, save + 1 + n);
	siz = unique(save + 1, save + 1 + n) - ( save + 1 );
	for ( int i = 1; i <= n; i ++ )
		x[i] = lower_bound(save + 1, save + 1 + siz, x[i]) - save;
	for ( int i = 1; i <= q; i ++ )
		scanf("%d%d", &qus[i].L, &qus[i].R), qus[i].id = i;
	len = n / sqrt(q);
	len = max(1, len), block = n / len;
	for ( int i = 1; i <= block; i ++ )
		{ op[i] = ed[i - 1] + 1; ed[i] = i * len; }
	ed[block] = n;
	for ( int i = 1; i <= block; i ++ )
		for ( int k = op[i]; k <= ed[i]; k ++ )
			belong[k] = i;
	sort(qus + 1, qus + 1 + q);
	int now = -1, R = 0;
	for ( int i = 1; i <= q; i ++ )
	{
		if ( now != belong[qus[i].L] )
		{
			for ( int k = 1; k <= siz; k ++ )
				bin[k] = 0;
			max_val = 0;
			now = belong[qus[i].L];
			R = ed[now];
		}
		while ( R < qus[i].R )
		{
			++R;
			++bin[x[R]];
			max_val = max(max_val, 1LL * save[x[R]] * bin[x[R]]);
		}
		long long pre = max_val;
		for ( int k = qus[i].L; k <= min(qus[i].R, ed[now]); k ++ )
		{
			++bin[x[k]];
			max_val = max(max_val, 1LL * save[x[k]] * bin[x[k]]);
		}
		ans[qus[i].id] = max_val;
		for ( int k = qus[i].L; k <= min(qus[i].R, ed[now]); k ++ )
			--bin[x[k]];
		max_val = pre;
	}
	for ( int i = 1; i <= q; i ++ )
		printf("%lld\n", ans[i]);
	return 0;
}

T4 拉面比较

两个元素为一组，可以通过 \(\tfrac{n}{2}\) 次查询得到组内元素的大小关系，然后暴力枚举组内较大 / 较小的元素，可以通过 \(\tfrac{n}{2}\) 次查询得到所有元素的最大 / 最小值。

code

#include "ramen.h"
using namespace std;
const int max1 = 400;
int p1[max1 + 5], p2[max1 + 5], len1, len2;
void Ramen ( int n )
{
	len1 = len2 = 0;
	for ( int i = 0; i + 1 < n; i += 2 )
	{
		if ( Compare(i, i + 1) < 0 )
			p1[++len1] = i, p2[++len2] = i + 1;
		else
			p1[++len1] = i + 1, p2[++len2] = i;
	}
	if ( n & 1 )
		p1[++len1] = n - 1, p2[++len2] = n - 1;
	int X = p1[1], Y = p2[1];
	for ( int i = 2; i <= len1; i ++ )
		if ( Compare(X, p1[i]) > 0 )
			X = p1[i];
	for ( int i = 2; i <= len2; i ++ )
		if ( Compare(Y, p2[i]) < 0 )
			Y = p2[i];
	Answer(X, Y);
	return;
}