首页 > 其他分享 >LY1376 [ 20231008 NOIP 模拟赛 T0 ] 递增路径

LY1376 [ 20231008 NOIP 模拟赛 T0 ] 递增路径

时间:2023-10-10 17:35:47浏览次数:36  
标签:putchar NOIP 20231008 LY1376 write int read isl include

题意

\(A\), \(B\) 两人轮流在一张图上移动一个点。要求这次移动的边权必须大于上次的。

\(A\) 希望游戏进行的轮数多,\(B\) 希望游戏进行的轮数少。

对于每个 \(s = 1, 2, ..., n\) 作为起点,若双方都采用最优策略,游戏会进行多少轮。

Sol

考虑将所有边按照从大到小的顺序排序。

每次操作在当前的图上添加一条边:\(u \to v\),因为已经排序,所以当前 \(u \to v \to \forall k \leq n\) 都是合法的情况。

我们记 \(f_{i, 0/1}\) 表示从当前点出发当前操作的人为 \(0/1\) 的游戏轮数。

所以我们只需要 \(u \to v\) 转移一次,\(v \to u\) 转移一次即可。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <tuple>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 2e5 + 5, inf = 0x7f7f7f7f;
array <tuple <int, int, int>, N> isl;
array <array <int, 2>, N> f;
/*
0 Alice
1 Bob
*/
int main() {
#ifdef ONLINE_JUDGE
	freopen("increase.in", "r", stdin);
	freopen("increase.out", "w", stdout);
#endif
	int n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		get <1>(isl[i]) = read(), get <2>(isl[i]) = read();
		get <0>(isl[i]) = read();
	}
	sort(isl.begin() + 1, isl.begin() + 1 + m, greater <tuple <int, int, int> >());
	for (int i = 1; i <= n; i++)
		f[i][1] = 0x7f7f7f7f;
	for (int i = 1; i <= m; i++) {
		int u = get <1>(isl[i]), v = get <2>(isl[i]);
		int pu = f[u][0], ku = (f[u][1] == inf ? 0 : f[u][1]),
			pv = f[v][0], kv = (f[v][1] == inf ? 0 : f[v][1]);
		f[u][0] = max(f[u][0], kv + 1), f[u][1] = min(f[u][1], pv + 1);
		f[v][0] = max(f[v][0], ku + 1), f[v][1] = min(f[v][1], pu + 1);
		/* write(f[u][0]), putchar(32); */
		/* write(f[u][1]), putchar(32); */
		/* write(f[v][0]), putchar(32); */
		/* write(f[v][1]), puts(""); */
	}
	for (int i = 1; i <= n; i++)
		write(f[i][0]), putchar(32);
	puts("");
	return 0;
}

标签:putchar,NOIP,20231008,LY1376,write,int,read,isl,include
From: https://www.cnblogs.com/cxqghzj/p/17755270.html

相关文章

  • NOIPTG联合权值
    P1351[NOIP2014提高组]联合权值我们对于每个点计算它的子结点的\(\sumw,\maxw\)。如图,发现贡献有三类:直接计算。需要剔除自己这个点,对于sum直接减去即可,对于max维护一个次大值,发现这个点是最大值用次大值代替。枚举子节点,然后直接利用子节点的\(\sum,\max\)信......
  • LY1380 [ 20231009 NOIP 模拟赛 T1 ] AK 神
    题意给定长度为\(n\)的序列\(S\)。\(A\),\(B\)两人轮流取连续\(k\)个数,保证\(n\equiv1\pmodk\)。\(A\)使最终数字更小,\(B\)使最终数字更大。问取到数的和。Sol直接考虑每次选哪些数,怎么选显然是不好做的。不难发现\(n\equiv1\pmodk\)的条件。题面提示我们......
  • 20231008
    //assess,fair,hike,nominal,prevailing,prohibitive,quarter,register,tendency,beinlinewith,goingrate,riseinaspiral,riseperpendicularly,rulingpriceassess-评估Toassessmeanstoevaluateorestimatethevalue,quality,orsignificance......
  • LY1366 [ 20231005 NOIP 模拟赛 T0 ] 加固
    题意设\(T\)是由\(26\)小写英文字母排列得到的字符串。\(T'\)由\(T\)复制若干次得到。给定字符串\(S\)为\(T'\)的子序列,求\(T'\)的最小复制次数。保证出现的不同字母不超过\(20\)种\(1\le|S|\le10^5\)Sol一个巧妙的转化,考虑将\(T\)串作为字典序,那么当......
  • LY1374 [ 20231008 NOIP 模拟赛 T2 ] 机房惨案
    题意给定一棵树,每次操作将一个点染成黑色。求询问的点到所有黑点的路径编号最小值。**数据保证第一次为染色操作**Sol注意到保证第一次为染色。考虑钦定根节点为染色的点。那么对于所有染色操作,暴力记录染色的点到根节点的路径上所有点的贡献。每个点只会贡献一次,这部分......
  • P1003 [NOIP2011 提高组] 铺地毯
    第一思路:开一个N*N的数组,每次都扫一遍地毯范围并标记编号然后你会发现:喜提MLE为什么呢?我们来看看数据范围0≤n≤1e4n的范围是1e4,数组总大小为1e16,大约需要4000TB的内存空间服务器也不带这么玩的正解:将地毯信息用结构体存储structnode{ intx1,y1,x2,y2;//x1......
  • 2023NOIP A层联测5
    A.T1(cook)复合题,考场上只做出来了分块的部分,没有想到那个组合数求和可以用莫队分块部分具体不说了,对散块部分加权时,可以采用归并优化时间复杂度(因为我北卡长哩,卡到了晚饭之后,卡了一下午,好欸!)现在考虑问题\(\sum_{i=0}^{k}\dbinom{x}{i}\)令$(S(n,m)=\sum_{i=0}^{m}C......
  • 洛谷 P1969 [NOIP2013 提高组] 积木大赛 - 小思维
    洛谷P1969[NOIP2013提高组]积木大赛[NOIP2013提高组]积木大赛题目描述春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为\(n\)的大厦,大厦可以看成由\(n\)块宽度为\(1\)的积木组成,第\(i\)块积木的最终高度需要是\(h_i\)。在搭建开始之前......
  • 2023NOIP A层联测6
    A.万花筒考虑发现每次相当于把x和x+d连边,不难发现最后一定是一些环证明可以看白简B.冒泡排序趟数期望写一下我曾经比较疑惑的点为什么inv和p一定一一对应,因为我们发现只要给出我们一个inv我们就可以倒推出唯一确定的p,所以它们是一一对应的关系这道......
  • P3953 [NOIP2017 提高组] 逛公园
    Description策策同学特别喜欢逛公园。公园可以看成一张\(N\)个点\(M\)条边构成的有向图,且没有自环和重边。其中\(1\)号点是公园的入口,\(N\)号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间。策策每天都会去逛公园,他总是从\(1\)号点进去,从\(N\)......