首页 > 其他分享 >Codeforces Round 812 (Div. 2)

Codeforces Round 812 (Div. 2)

时间:2023-12-13 16:58:29浏览次数:37  
标签:std psq min int max Codeforces 812 now Div

基本情况

第一次赛时做出div2的ABC。

然而B题是秒的最快的?

A题卡了一段时间经典+4,C题代码实现卡了一段时间。

A. Traveling Salesman Problem

Problem - A - Codeforces

卡题分析

主要原因在少了特判,没有自己多构造几个特殊情况数据。

这是一开始的代码

void solve()
{
	int n, x, y;
	int max_x, max_y, min_x, min_y;
	max_x = max_y = -0x7fffffff, min_x = min_y = 0x7fffffff;
	std::cin >> n;
	while(n--)
	{
		std::cin >> x >> y;
		max_y = std::max(max_y, y), min_y = std::min(min_y, y);
		max_x = std::max(max_x, x), min_x = std::min(min_x, x);
	}
	std::cout << (max_x - min_x + max_y - min_y << 1) << std::endl;
}

这忽略了一些数据,比如说我造的一个:

4
0 -2
0 -3
1 0
-1 0

这类在 \(x\) 或 \(y\) 轴的其中一个或几个方向没有任何箱子的数据在我的做法下就是有问题的,因为此时没法计算从原点到有箱子的那个方向的距离,只是单纯计算了那个方向箱子距离的差值

加入特判即可

void solve()
{
	int n, x, y;
	int max_x, max_y, min_x, min_y;
	max_x = max_y = -0x7fffffff, min_x = min_y = 0x7fffffff;
	std::cin >> n;
	while(n--)
	{
		std::cin >> x >> y;
		max_y = std::max(max_y, y), min_y = std::min(min_y, y);
		max_x = std::max(max_x, x), min_x = std::min(min_x, x);
	}
    int res = max_x - min_x + max_y - min_y;
    if (max_x < 0) res -= max_x;//最大的都小于零,显然都在下方
    if (max_y < 0) res -= max_y;
    if (min_x > 0) res += min_x;//最小的都大于零,显然都在上方
    if (min_y > 0) res += min_y;
	std::cout << (res << 1) << std::endl;
}

B. Optimal Reduction

Problem - B - Codeforces

思想和这类题是一样的:

注意到我们可以把数组变成柱状图并“切片”,有几片答案就是几,而片数很好统计:每当数组元素增加时都会产生一个或几个“切片”的左端,增加几就是几个“切片”。

C. Build Permutation

Problem - C - Codeforces

卡题分析

二分加(贪心?)过了。

这题我得到经验,就是如果代码一大坨了,就尽量先简化、重写,这样比较容易调好。

附上代码(psq是预处理的完全平方数,从零开始)

void solve()
{
	int n;
	std::cin >> n;
	memset(vis, false, sizeof(vis));
	auto now = std::upper_bound(psq.begin(), psq.end(), n - 1);
	for (int i = n - 1; i >= 0; i--)
	{
		if (*now >= i) 
		{
			while(*now - i >= n && now != psq.begin()) now--;
			while(vis[*now - i] && now != psq.begin()) now--;
			ans[i + 1] = *now - i, vis[*now - i] = true;
		}
		else
		{
			now = std::upper_bound(psq.begin(), psq.end(), n - 1);
			while(vis[*now - i] && now != psq.begin()) now--;
			ans[i + 1] = *now - i, vis[*now - i] = true;
		}
	}
	for (int i = 1; i <= n; i++) std::cout << ans[i] << " ";
	std::cout << std::endl;
}

标签:std,psq,min,int,max,Codeforces,812,now,Div
From: https://www.cnblogs.com/kdlyh/p/17899429.html

相关文章

  • Codeforces Round 810 (Div. 2)
    基本情况A题秒了,B、C题死活看不懂题目。B.PartyProblem-B-Codeforces错误分析为啥看不懂题目,一方面是英语水平确实不够,另一方面就是图的意识不行,如果能看出来这题隐含的建图思想,就很有助于理解题目。正确思路题意有\(T\)组数据,每组数据给你一组\(n,m\)表示共......
  • [Codeforces] CF1737C Ela and Crickets
    CF1737CElaandCrickets题意给定一个\(n\timesn\)的棋盘,棋盘上有且仅有三颗排成\(\text{L}\)形的棋子。对于\(\text{L}\)形的定义,有且仅有以下四种情况:棋子的移动规则和跳棋相同。它可以水平、垂直或斜向移动。当且仅当一个棋子的某个方向紧随另一个棋子时,它能跳......
  • [ARC133B] Dividing Subsequence
    DividingSubsequence这道题与最长公共子序列类似,可以先去水一水那道题。题意本题就是让你从\(p\)里面选出一个子序列\(b_i\)和\(q\)里面选出一个子序列\(a_i\),我们要使\(b_i\)是\(a_i\)的倍数。解法本题直接用动态规划,是\(O(n^2)\)做法,会超时,因此我们用树状数......
  • Codeforces Round 809 (Div. 2)
    基本情况A题秒了。B题卡了很久,最后过了。C来不及了。B.MakingTowersProblem-B-Codeforces卡题分析最初想法其实已经推出来下标差为奇数才能构成高塔了。但是思维固化,认为这个问题就必须用LIS那类做法做,然后硬打了一个\(\operatornameO(n^2)\)的DP,然后就TLE......
  • Codeforces Round 808 (Div. 2)
    基本情况最难受的一集。A搞了一个半小时愣是没开出来。A.DifferenceOperationsProblem-A-Codeforces错误分析我分了好多类讨论,换言之没找到更本质的东西。我想的是如果前面有一个数能处理到\(1\)那后面就都能过。止步于此,而没有往更本质,更普适的地方想。然后又......
  • Codeforces Round 807 (Div. 2)
    基本情况AB题秒了。C题搞了半天,搞了一个假的解法,最后还是爆空间了。D题没想下去。C.MarkandHisUnfinishedEssayProblem-C-Codeforces错误分析写出来自己的错解之后没有进一步思考,而是觉得没希望直接做D去了,实则D也没可能半小时写完。我的错解就是预处理好每个......
  • Codeforces 198 B Jumping on Walls
    题面翻译题目描述瓦西亚在和忍者玩电脑游戏。在这个关卡,瓦西亚需要操控忍者走出一个很深的峡谷。峡谷由两面垂直于地面且互相平行的墙组成,它们的高度为\(n\)米。我们将这些墙分成许多\(1\)米长的区域,并从下到上用\(1\)到\(n\)的正整数对它们进行编号。有些地方是安全的,忍者可以......
  • Codeforces Round 914 (Div. 2)
    基本情况A题+2,幸好后面突然悟了。B题体现了读题以及一词多义的重要性。C题不会。看了一下1700分的题目,暂时先放了。A.TheThirdThreeNumberProblemProblem-A-Codeforces推出了规律,\(n\)为偶数的时候,无脑\(a=n\oplus1,b=n\oplus1,c=1\)就行。然而奇数......
  • Codeforces Round 914 (Div. 2)
    CodeforcesRound914(Div.2)A-Forked!解题思路:枚举皇后和国王能被骑士吃到的位置,重合的点数就是答案。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;typedefpair<ll,ll>pii;#definefifirst#definesesecondconstintmod=1e9......
  • 232-父级div,包含子div,子div有点击事件,父div有点击事件,js如何实现,2个点击事件不干扰
    HTML结构<divid="parent"><divid="child"></div></div>JavaScript/jQuery代码:$(document).ready(function(){//父级div的点击事件处理程序$('#parent').on('click',function(){console.log(&#......