1265 - B. Beautiful Numbers

痛定思痛。 2021-07-17 02:20 324阅读 0赞

[Beautiful Numbers][]

思路：先想想暴力的方法，对于m把从一到m每个数的位置求出来，如果最右边的减最左边的数+1等于m,则说明所有数覆盖的范围刚好是m不会有其他的数是一个1–m的置换。但暴力会T掉，我们再优化一下，其实我们求m+1是否满足可以利用前面求到的范围，只需对m+1这个数更新一下范围，再看是否符合即可，细节见代码。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e6 + 5;
    int lst[Max];
    int pos[Max];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n;cin >> n;
    		for (int i = 1;i <= n;i++)
    		{ 
    			cin >> lst[i];pos[lst[i]] = i;
    		}
    		int l = pos[1], r = pos[1];
    		string str="";
    		for (int i = 1;i <= n;i++)
    		{ 
    			l = min(l, pos[i]);
    			r = max(r, pos[i]);
    			if (r - l + 1 == i)str += '1';
    			else str += '0';
    		}
    		cout << str << endl;
    	}
    }

[Beautiful Numbers]: https://codeforces.ml/contest/1265/problem/B

发表评论取消回复

表情：

评论列表（有 0 条评论，324人围观）

还没有评论，来说两句吧...

相关阅读

相关 CodeForces 55D-Beautiful numbers【数位DP+思维】

题目链接：[https://codeforces.com/problemset/problem/55/D][https_codeforces.com_problemset_pr

布满荆棘的人生/ 2023年08月17日 17:37/ 0 赞/ 139 阅读

相关 poj 1265 Area

> 题目衔接：[http://poj.org/problem?id=126][http_poj.org_problem_id_126]5 > <table> > <tbo

末蓝、/ 2023年08月17日 17:33/ 0 赞/ 121 阅读

相关【数位DP】CF55D Beautiful numbers

$dp\[x\]\[p\]\[pp\]$表示第x位，当前已有数字mod 2520（1~9数字的lcm）为p，当前各位数字的lcm为pp 观察到数组太大，考虑压缩，第三维lcm

矫情吗；*/ 2023年06月01日 06:10/ 0 赞/ 19 阅读

相关 Codeforces 55D Beautiful Number （数位统计）

把数位dp写成记忆化搜索的形式，方法很赞，代码量少了很多。下面为转载内容：　　 a positive integer number is beautiful if an

左手的ㄟ右手/ 2022年08月09日 12:54/ 0 赞/ 165 阅读

相关 #51 D. Beautiful numbers （数位dp+离散化）

题目链接: [点击打开链接][Link 1] http://codeforces.com/contest/55/problem/D 题意：定义：Beaut

小咪咪/ 2022年06月17日 03:44/ 0 赞/ 195 阅读

相关【数位DP+离散化】Beautiful numbers CodeForces - 55D

Think: 1知识点：数位DP(+记忆化搜索)+离散化 2题意：输入一个区间，询问在这个区间内有多少个beautiful number，a positive inte

àì夳堔傛蜴生んèń/ 2022年06月08日 11:20/ 0 赞/ 203 阅读

相关北京邀请赛 B. Beautiful Garden

题意：给你坐标和n个点，求最少移动的点使得n个点成等差数列思路：既然要成等差数列，那么最起码有两个点是不动的，然后枚举这两个点中间的点的个数，近期水的要死，看了队友的代码做

约定不等于承诺〃/ 2021年11月16日 06:24/ 0 赞/ 280 阅读

相关 CodeForces - 55D Beautiful numbers (数位dp)

Volodya is an odd boy and his taste is strange as well. It seems to him that a positive

偏执的太偏执、/ 2021年09月29日 13:24/ 0 赞/ 386 阅读

相关 1265 - B. Beautiful Numbers

[Beautiful Numbers][] 思路：先想想暴力的方法，对于m把从一到m每个数的位置求出来，如果最右边的减最左边的数+1等于m,则说明所有数覆盖的范围刚好是m

痛定思痛。/ 2021年07月17日 02:20/ 0 赞/ 325 阅读

相关 1265 - C. Beautiful Regional Contest （贪心）

[题目][Link 1] 思路：要求每个金牌切的题高于银牌，银牌高于铜牌，铜牌高于铁牌，那么必然对于切题一样的队伍只会获得相同的牌。此时我们把切题一样的队看作一个个打包好

忘是亡心i/ 2021年07月17日 00:35/ 0 赞/ 362 阅读