ZROI#1000

我不是女神ヾ 2023-06-02 11:59 3阅读 0赞

[ZROI\#1000][ZROI_1000]

第一印象:啊,数位\\(DP\\),第一题这么清爽吗(内心\\(:mmp\\)).不过,这应该可以数位\\(DP\\)吧...不知道不知道,没想.  
冷静思考\\(\\times 1\\):对于线性的好像可以前缀和,因为这玩意儿非常稀疏,判定合法的\\(log\\)完全可以不管.

冷静思考\\(\\times 2\\):抛弃什么数位\\(DP\\),这题是不是枚举位数+枚举与其他位不相同的数是啥+枚举它在哪+枚举其他位是啥就行了?  
算一算复杂度\\(:\\Theta(17^2\\times 9^2)\\).哎呀,过了啊.写写写:  
\\(Code:\\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } int l , r , ans ; inline bool check (int x , int cmp) { int cnt = 0 ; while ( x ) ++ cnt , x /= 10 ; return cnt == cmp ; } signed main (int argc , char * argv[]) { l = rint () ; r = rint () ; rep ( i , 1 , 17 ) rep ( b , 1 , i ) rep ( j , 0 , 9 ) rep ( k , 0 , 9 ) { if ( j == k ) continue ; int res = 0 ; rep ( w , 1 , b - 1 ) res = res * 10 + k ; res = res * 10 + j ; rep ( w , b + 1 , i ) res = res * 10 + k ; if ( ! check ( res , i ) ) continue ; if ( res >= l && res <= r ) ++ ans ; } printf ("%lld\n" , ans ) ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11523698.html

[ZROI_1000]: http://www.zhengruioi.com/problem/1000