首页 > 其他分享 >题解:AT_xmascon21_b Bad Mood

题解:AT_xmascon21_b Bad Mood

时间:2024-04-06 17:47:00浏览次数:26  
标签:得分 Mood xmascon21 题解 long times Bad

AT_xmascon21_b Bad Mood

题意

给定你一个 \(n\times m\) 的矩形。

以一条对角线为基础上,制作一个无向图,该图的顶点对应于格子的共有 \((m+1) \times (n+1)\) 个顶点,画上的对角线对应于图的边。这种方式能形成的连通分量的数量为得分。

求最小得分和最大得分。

思路

最小得分是好算的,就是 \((n+1)\times (m+1)−n\times m\),也就是 \(n+m+1\)。

最大得分就是最小得分加上 \(\frac{n\times m-(n-2)\times(m-2)}{4}\),即 \(\frac{n\times m+n+m}{2}+2\)。

注意

\(n\) 和 \(m\) 要用 long long 类型

代码

#include <bits/stdc++.h>
using namespace std;
long long a, b;
int main() {
	cin>>a>>b;
	cout<<a+b+1<<' '<<(a+b+a*b)/2+2<<'\n';
	return 0;
}

标签:得分,Mood,xmascon21,题解,long,times,Bad
From: https://www.cnblogs.com/AUBSwords/p/18117662

相关文章

  • 题解:CF1918B Minimize Inversions
    CF1918BMinimizeInversions思路暴力一个一个的算,复杂度巨大。数学规律让逆序最少,也就是让升序更多。我们可以通过多组数据实验,最终我们会发现,将数列\(A\)减少一个逆序对,让数列\(B\)随着\(A\)变化,最多会只会增加一个逆序对。而让\(A\)相邻两个数保持升序,\(B\)相邻......
  • CF1934B Yet Another Coin Problem 题解
    CF1934BYetAnotherCoinProblem题解题意目前有\(5\)种硬币,面值分别为\(1,3,6,10,15\)。给你一个数字\(n\),求出可以凑出\(n\)的最少的硬币的数量。思路这道题,大多数的人大概会想到动态规划的方法。但是,我们应该有敢于创新的精神。于是我就想到了一个简单的数学方法......
  • CF1950B Upscaling题解
    CF1950BUpscaling题解题意给予你一个正整数\(n\),构造一个如图的字符矩阵。思路注意数据\(1\len\le20\),可以发现数据很小,于是我们可以暴力模拟。我们可以将两列看为一列,两行看为一行。然而我们可以发现缩成的一行的\(i\)等于被缩的两行的\({i\div2}\)的向上取整。......
  • P4551 最长异或路径 题解
    题目链接:最长异或路径看到树上路径问题,且是异或和这种,先思考树上前缀和转化为前缀和问题。如果我们预处理出\(pre[curr]\)表示\(curr\)这个点到根的前缀异或值,那么很显然我们路径的两个点\(u\)与\(v\)的\(pre[u]\opluspre[v]\)和传统的加法的树上前缀和并不一样,因为异......
  • 24.4.6 题解
    4.6模拟赛T1困难的图论题意:找出所有在且仅在1个简单环中的边,输出编号的异或和。一个错误的想法:找边双连通分量,看边数是否等于点数反例:正解是点双所以我在想,为什么是点双,不是边双呢?什么时候找点双,什么时候找边双呢?T2中等的字符串已知\(m\)个关键词\(s_i\),每出现......
  • CF1200E Compress Words 题解
    题目链接:CF或者洛谷注意到总字符串长度不超过\(1e6\),对于两个串之间找前后缀匹配,只要能暴力枚举长度,\(check\为\O(1)\),那么最后显然线性复杂度。可以考虑\(kmp\),也可以考虑字符串哈希,最好上双哈希,然后拼串显然是在尾部继续添加新的前缀哈希,这个需要添加的串可以单独由匹配......
  • 牛客小白月赛90题解
    A.小A的文化节#include<bits/stdc++.h>#defineintlonglong#defineendl"\n"usingnamespacestd;constintN=1e5+10,mod=1e9+7;intn,m,a[N];voidsolve(){ cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];intres=0......
  • BNDS 2024/4/6模拟赛题解
    T1方程描述给出非负整数\(N\),统计不定方程\(X+Y^2+Z^3=N\)的非负整数解\((X,Y,Z)\)的数量。输入输入数据,包含一个非负整数\(N\)。输出输出数据,包含一个非负整数表示解的数量。数据范围40%的数据,\(N<=10000\)60%的数据,\(N<=10^8\)100%的数据,\(N<=10^{16}\)分析......
  • LG_B3951 [GESP样题 五级] 小杨的队列 题解
    比较简单的一道逆序对的题,甚至不用\(\Omicron(n\logn)\)的归并,只需要\(\Omicron(n^2)\)的优化冒泡。就是一个在队列里每次push一个元素,然后查找逆序对的问题。值得一提的是,这道题身高不重复,所以才能优化冒泡拿满分,不然的话就得老实用归并了。直接看代码吧。#include<b......
  • AT_xmascon21_b Bad Mood 题解
    这是一道比较简单的结论题。不难发现,最小得分为\((n+1)(m+1)-nm\),化简得到:\[\begin{aligned}&(n+1)(m+1)-nm\\=&nm+n+m+1-nm\\=&n+m+1\end{aligned}\]继续不难发现,最大得分应该是最小得分加上\(\lfloor\frac{(n-2)(m-2)+nm}{4}\rfloor\)的结果,化简,得到(忽略向下取整......