首页 > 其他分享 >LGR-156-Div.3 题解

LGR-156-Div.3 题解

时间:2023-08-26 23:14:26浏览次数:47  
标签:read 题解 sum int MAXN ans LGR Div.3 ll

LGR-156-Div.3 题解

洛谷网校 8 月普及组月赛 I & MXOI Round 1 & 飞熊杯 #2

第一次AK一个比赛!而且排名这么靠前!!!

T1 宝箱

题目链接

思路

注意到答案有两种情况。1.从原点走到 \(a\),再从 \(a\) 走到 \(b\) ,2.从原点走到 \(b\),再从 \(b\) 走到 \(a\)。取一个最小值即可。

代码

int myabs(int x) {
	return x < 0 ? -x : x;	
}
int a, b, ans = 0x7fffffff;
int main() {
	read(a), read(b);
	ans = min(ans, myabs(a - 0) + myabs(a - b));
	ans = min(ans, myabs(b - 0) + myabs(b - a));
	write(ans);
	return 0;
}

T2 方格

题目链接

思路

注意到每个点好朋友的个数即与它的数字相同的点的个数减去与它相邻且数字相同的点的个数。又注意到 \(a_{i,j} \le 9\) ,前者用桶维护,后者暴力判断即可,注意实现时需减去自己,答案最大是 \(nm\) 级别的,需开 long long。时间复杂度: \(O(nm)\) 。

代码

const int MAXN = 2005;
ll n, m, a[MAXN][MAXN];
ll t[20], ans;
int main() {
	read(n), read(m);
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++) {
			read(a[i][j]);
			t[a[i][j]] ++;
		}
	for (int i = 1; i <= n; i ++) 
		for (int j = 1; j <= m; j ++) {
			ans += t[a[i][j]] - 1;
			if (i > 1 && a[i - 1][j] == a[i][j])
				ans --;
			if (i < n && a[i + 1][j] == a[i][j])
				ans --;
			if (j > 1 && a[i][j - 1] == a[i][j])
				ans --;
			if (j < m && a[i][j + 1] == a[i][j])
				ans --;
		}
	write(ans);
	return 0;
}

T3 涂色

题目链接

思路

注意到答案为涂色后层数 \(\mod k \ne 0\) 的格子个数。又注意到格子的层数为其行涂色的次数加上其列涂色的次数,分别设为 \(a, b\),答案即 \((a+b)\mod k \ne 0\) 的总数。枚举每一行的 \(a\),答案即 \(m - (满足b \mod k = k-a的b的个数)\) ,统计每行每列涂色的次数,用桶维护 \(b \mod k\) ,每次查桶即可,答案最大是 \(nm\) 级别的,需开 long long。时间复杂度:\(O(n)\)。

代码

const ll MAXN = 200005, MAXK = 500005;
ll n, q, k, sum, ans;
ll h[MAXN], l[MAXN], t[MAXK];
int main() {
    read(n), read(m), read(q), read(k);
	for (ll i = 1, op, x; i <= q; i ++) {
		read(op), read(x);
		if (op == 1) h[x] ++; // 统计
		else l[x] ++;
	}
	for (ll i = 1; i <= n; i ++) h[i] %= k; // mod
	for (ll i = 1; i <= m; i ++) {
		l[i] %= k; // mod
		t[l[i]] ++;	// 桶
	}
	for (ll i = 1; i <= n; i ++) 
		ans += m - t[(k - h[i]) % k]; // 查桶
	write(ans);
	return 0;
}

T4 城市

题目链接

思路

设点 \(x\) 到其他点的距离之和为 \(sum_x\) ,注意到加入的点对答案的贡献为 \(2sum_{k} + 2nw\),只需预处理出 \(sum_k\) 即可。又注意到这是一个换根 \(dp\) ,令 1 为根节点,先 dfs 一遍求出 \(sum_1\) 以及以点 \(x\) 为根的子树大小 \(siz_x\) ,再 dfs 一遍换根,求出每个 \(sum\) ,设当前点为 \(y\) 令 \(x\) 为 \(y\) 的父亲,连边的权值为 \(z\) ,状态转移方程:

\[sum_y=sum_x - siz_yz+(siz_1-siz_y)z=sum_x-z(siz_1-2siz_y) \]

时间复杂度:\(O(n)\),实现细节看代码。

代码

ll tot, ver[MAXN << 1], nxt[MAXN << 1], head[MAXN], edge[MAXN << 1];
ll n, q, sum[MAXN], siz[MAXN], ans, nowans; // 模数大,不开long long见祖宗
void add(ll x, ll y, ll z) {
	ver[++ tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
	edge[tot] = z;
}
void dfs1(ll x, ll fa) {
	siz[x] = 1; // 子树大小
	for (ll i = head[x], y; i; i = nxt[i]) {
		y = ver[i];
		if (y == fa) continue;
		dfs1(y, x); 
		siz[x] += siz[y];
		sum[x] = 1ll * (sum[x] + sum[y] + (1ll * edge[i] * siz[y]) % mod) % mod;
	}
}
void dfs2(ll x, ll fa) {
	for (ll i = head[x], y; i; i = nxt[i]) {
		y = ver[i];
		if (y == fa) continue;
		sum[y] = 1ll * (sum[x] + 1ll * (siz[1] - 2ll * siz[y]) % mod * edge[i] % mod) % mod;
        // 转移方程
		sum[y] = (sum[y] % mod + mod); // 注意处理负数情况
		dfs2(y, x);
	}
}
int main() {
    read(n), read(q);
	for (ll i = 1, u, v, c; i < n; i ++) {
		read(u), read(v), read(c);
		add(u, v, c);
		add(v, u, c);
	}  
    dfs1(1, 0); // 两次dfs
    dfs2(1, 0);
    for (ll i = 1; i <= n; i ++) 
    	ans = 1ll * (ans % mod + sum[i] % mod) % mod; // 不加点的答案
    for (ll i = 1, k, w; i <= q; i ++) {
    	read(k), read(w);
    	nowans = 1ll * (ans % mod + 2ll * (sum[k] % mod + n % mod * w % mod) % mod) % mod;
        // 处理加点后的答案
    	write(nowans);
    	putchar('\n');
	}
	return 0;
}

标签:read,题解,sum,int,MAXN,ans,LGR,Div.3,ll
From: https://www.cnblogs.com/maniubi/p/17659657.html

相关文章

  • react-pdf在部分iOS手机上加载pdf失败问题解决
    最近项目快结束了,测试提了一个bug,iOS手机上加载pdf一直在转圈,加载不出来内容。看到这个bug,在电脑上和安卓手机上没有问题,iOS手机中打开确实又问题,初步确定为app问题。我们的项目是集成在客户的app里的,可能是app内的WebView和Safari有一些差异导致的问题。首先直接在iOS手机上用a......
  • 力扣-2. 两数相加(C++题解)
    题目链接:https://leetcode.cn/problems/add-two-numbers/description/给你两个 非空的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字0之......
  • 【LGR-153-Div.2】梦熊联盟 8 月月赛 Ⅳ & Cfz Round 1 & 飞熊杯 #1
    【LGR-153-Div.2】梦熊联盟8月月赛Ⅳ&CfzRound1&飞熊杯#1\(T1\)「CfzRound1」DeadCells\(100pts\)正解:模拟(注意特判)llgcd(lla,llb){ returnb?gcd(b,a%b):a;}intmain(){ lla,b,k,d,i,ans=1; a=read();b=read();k=read(); d=a/gcd(a,b)*b; f......
  • 关于自建Rustdesk 远程桌面服务器的公网访问:无法连接中继服务器的问题解决方法
    自建服务器位于内网时,内网客户端ID/中继的地址通常写成内网IP,外网客户端一般会用公网IP进行端口映射,但这样设置出现外网客户端无法连接中继服务器,但内网客户端使用正常的现象。经过半天的排查分析,当内网和外网填写的自定义服务器地址时,rust服务器无法识别出需要使用nat包的地址,默......
  • P1848 Bookshelf G 题解
    这是本蒟蒻写的第一篇题解(写不好请指出)很明显他是一道dp题,因为第i本书放哪里只跟前i-1本树的放法有关系。我们可以是定义f[i][j]表示放了i本书,最后一层书架是以第j本书开始的。那么有动态转移方程:\(f[i][i]=min(f[i-1][j])+hi,w[j]+...+w[i-1]<=L\)\(f[i][j]=f[i-1][j]+max(0......
  • 力扣-228. 汇总区间(C++题解)
    题目链接:https://leetcode.cn/problems/summary-ranges/description/给定一个 无重复元素的 有序整数数组\(nums\)。返回恰好覆盖数组中所有数字的最小有序区间范围列表 。也就是说,\(nums\)的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于\(......
  • P2151 [SDOI2009] HH去散步 题解
    传送门简要题意:有\(n\)个人,\(m\)条无向边,走\(e\)条边,满足条件若第\(i\)条边为\(u->v\)则第\(i+1\)条边不能是\(v->u\),问\(s->t\)的方案有多少个,取模45989。因为要满足题目关于边的条件,所以我们考虑点边互换。将\(u-v\)的无向边一分为二变成\(u->v,v->u\),第\(i\)条边记录两个变......
  • 【题解】CF1413C Perform Easily(双指针)
    【题解】CF1413CPerformEasily写篇题解水水经验~顺便增加一下RP~比较套路和简单的一道绿题。题目链接PerformEasily-洛谷|计算机科学教育新生态(luogu.com.cn)题意概述给你一个长度为\(6\)的\(a\)数组,和一个长度为\(n\)的\(b\)数组,要求将\(b\)数组内的每......
  • [CF1794E] Labeling the Tree with Distances 题解
    [CF1794E]LabelingtheTreewithDistances题解题目描述给你一个树,边权为\(1\)。给定\(n-1\)个数,你需要将这些数分配到\(n-1\)个节点上。一个点\(x\)是好的,当且仅当存在一种分配方案,所有被分配数的点到\(x\)的最短路径长度等于其被分配的数。求所有好点。思路从......
  • 1.2 金字塔原理-构建金字塔原理与问题解决
    一、构建金字塔原理与问题解决1.自上而下2.自下而上3.解决问题的过程界定问题详细描述问题的背景信息用SMART原理定义目标明确想要达到的成果以及衡量成功与否的标准分解问题关键分析以假设和最终结果为导向反复地进行假设和数据分析尽可能地简化分......