1265 - B. Beautiful Numbers

痛定思痛。 2021-07-17 02:20 307阅读 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 条评论，307人围观）

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

相关阅读

相关 B - New Year‘s Number

[传送门][Link 1] use array when writint a for loop, use termination condition(condit

ゝ一世哀愁。/ 2022年10月29日 01:53/ 0 赞/ 161 阅读

相关 UESTC 1265-宝贵资源

宝贵资源 [Edit][] Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Jav

悠悠/ 2022年08月19日 13:20/ 0 赞/ 120 阅读

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

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

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

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

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

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

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

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

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

相关 B. Split a Number（字符串加法）

Dima worked all day and wrote down on a long paper strip his favorite number nn consisti

偏执的太偏执、/ 2021年12月12日 06:51/ 0 赞/ 182 阅读

相关北京邀请赛 B. Beautiful Garden

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

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

相关 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 赞/ 365 阅读

相关 1265 - B. Beautiful Numbers

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

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

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

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

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