首页 > 其他分享 >AtCoder Beginner Contest 161D 题解

AtCoder Beginner Contest 161D 题解

时间:2024-09-08 20:49:27浏览次数:16  
标签:AtCoder int 题解 long 一位 push 161D TA

原题链接:洛谷链接AtCoder链接

思路

每次根据上一位,计算下一位为TA-1/TA/TA+1,放入queue中,最后输出第\(K\)次弹出的整数。

注意事项

  • 不用long longWA
  • 上一位为\(0\)时下一位不能为\(-1\)!(要特判)
  • 上一位为\(9\)时下一位不能为\(10\)!(也要特判)

代码

#include <cstdio>
#include <queue>
using namespace std;

typedef long long LL;

int main(int argc, char** argv)
{
	int k;
	scanf("%d", &k);
	queue<LL> q;
	for(int i=1; i<10; i++) q.push(i);
	while(true)
	{
		LL x = q.front(); q.pop();
		if(--k == 0)
		{
			printf("%lld\n", x);
			return 0;
		}
		int r = x % 10LL;
		x *= 10LL;
		x += r;
		if(r > 0) q.push(x - 1);
		q.push(x);
		if(r < 9) q.push(x + 1);
	}
	return 0;
}

标签:AtCoder,int,题解,long,一位,push,161D,TA
From: https://www.cnblogs.com/stanleys/p/18403426/abc161

相关文章

  • CodeForces Round #621 ABC (1307A+1307B+1307C) 题解
    A.CowandHaybales题面TheUSAConstructionOperation(USACO)recentlyorderedFarmerJohntoarrangearowofnhaybalepilesonthefarm.The\(i\)-thpilecontains\(a_i\)haybales.However,FarmerJohnhasjustleftforvacation,leavingBessieal......
  • 2024CCPC网络赛题解
    前言开局掉线30min比较搞心态,不过比赛延迟了1个小时,但是后面也一直没过题,如果时间再少点可能排名还更好看。最后是8题前面,这里简单讲一下我有写的题,队友写的题就放一下队友的赛时代码,大家自己看看吧。B队友写的,签到,但是数据范围\(n\)给\(10^3\)给队友整不自信了,因为答案的......
  • AT_dwacon6th_prelims_c Cookie Distribution 题解
    组合意义保平安。思路发现\(\prod\)的贡献不好统计。我们可以考虑\(\prod\)的组合意义。容易发现:\[\prodc_i=\prod\sum_{j=1}^{c_i}1\]那么依照分配律,我们发现这个东西的组合意义是每个人从获得的饼干中选一个出来的方案。这样就会变好统计很多。设\(dp_{i,j}\)为......
  • CF1534F2 Falling Sand (Hard Version) 题解
    题目链接点击打开链接题目解法做法1一个沙子消失,会带走所有它所在列下面的沙子我们记每列从下往上第\(a_i\)个沙子为关键点,第\(i\)列至少消失\(a_i\)个沙子等价于所有关键点都消失一个显然的事情是:记一列最上面的沙子为起始点,则我们只会干扰起始点第一感觉是找到一......
  • LOJ4218 「IOI2024」尼罗河船运 题解
    题目描述有\(n\)件手工艺品,第\(i\)件重量为\(w_i\),有参数\(a_i\)和\(b_i\)。每艘船最多可以运输两件手工艺品:如果只运输第\(i\)件,重量没有要求,代价为\(a_i\)。如果同时运输第\(i\)和第\(j\)件,要求\(|w_i-w_j|\leD\),代价\(b_i+b_j\)。\(q\)次询问,给......
  • Leetcode第 414 场周赛题解
    Leetcode第414场周赛题解Q1.将日期转换为二进制表示给你一个字符串date,它的格式为yyyy-mm-dd,表示一个公历日期。date可以重写为二进制表示,只需要将年、月、日分别转换为对应的二进制表示(不带前导零)并遵循year-month-day的格式。返回date的二进制表示。解法:STL一......
  • 题解:P11020 「LAOI-6」Radiation
    我们发现一种最优策略,把石头按照斜线摆,即(1,1),......
  • P1419 寻找段落 题解
    其他学习笔记这题真是凝聚了很多精华,那么我们就介绍这题的四兄弟:大哥平均数这道题是其他兄弟的基础。二哥BestCow这位更是重量级,因为没特长只能强大哥的外貌,会大哥即识二哥。三哥PROSJEK这位哥看似有点创新却仍没逃过一家子的基因,只是变为了小数运算。四哥寻......
  • 【题解】CPS-S模拟2
    目录PreT1.不相邻集合题目描述部分分40pts10pts正解思路代码T2.线段树题目描述部分分20pts正解思路代码T3.部分分40pts正解思路代码T4.部分分10pts正解思路代码AndPre赛时没有第一时间找到签到题,遂四处游走,后来决定先打T1,约1h时切了,然后1h打后3题暴力,后面推了推T4一个特殊性质,......
  • [ABC370C] Word Ladder 题解
    题目描述:给予两个相等长度的序列,\(S\)与\(T\),以及一个空数组\(X\),每在\(S\)上修改一个字符,便将修改后的\(S\)加入\(X\)中,直到\(S\)与\(T\)相同。(输出字典序最小的\(X\)数组)拿过题一看,感觉还是蛮简单的,本题主要的难点在字符串的字典序上。字符串字典序的定义......