DIV1 250pt

题意：称各个数位只含有4和7的数为lucky number，给定a，b，求[a, b]中的lucky number有多少个。a, b <= 10^9

解法：很明显的数位dp，写出来也就20行左右。本来以为最近刚好在做数位dp，可以很快出，结果我想着刚才做的那个数位dp，脑袋进水居然直接敲了段递归的代码还半天没调出来.......然后很快写了段非递归的代码过了.....160score...

　　　后来看官方题解说，由于10^9内实际上只有1022个lucky number，所以可以求全部生成出来，看有哪些在[a, b]上。

tag:数位dp，think

 // BEGIN CUT HERE

 /*

  * Author:  plum rain

  * score :

  */

 /*

  */

 // END CUT HERE

 #line 11 "TheLuckyNumbers.cpp"

 #include <sstream>

 #include <stdexcept>

 #include <functional>

 #include <iomanip>

 #include <numeric>

 #include <fstream>

 #include <cctype>

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <cstdlib>

 #include <set>

 #include <queue>

 #include <bitset>

 #include <list>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define CLR1(x) memset(x, -1, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define ALL(t) t.begin(),t.end()

 #define zero(x) (((x)>0?(x):-(x))<eps)

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef pair<int, int> pii;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 int dit[], two[];

 int gao(int x)

 {

     two[] = ;

     for (int i = ; i < ; ++ i)

         two[i] = two[i-] * ;

     int len = ;

     while (x){

         dit[len++] = x % ;

         x /= ;

     }

     int ret = ;

     for (int i = ; i < len; ++ i)

         ret += two[i];

     for (int i = len-; i >= ; -- i){

         if ( < dit[i]) ret += two[i];

         if ( < dit[i]) ret += two[i];

         if (dit[i] !=  && dit[i] != ) break;

     }

     return ret;

 }

 class TheLuckyNumbers

 {

     public:

         int count(int a, int b){

             return gao(b+) - gao(a);

         }

 // BEGIN CUT HERE

     public:

     void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); }

     private:

     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

     void test_case_0() { int Arg0 = ; int Arg1 = ; int Arg2 = ; verify_case(, Arg2, count(Arg0, Arg1)); }

     void test_case_1() { int Arg0 = ; int Arg1 = ; int Arg2 = ; verify_case(, Arg2, count(Arg0, Arg1)); }

     void test_case_2() { int Arg0 = ; int Arg1 = ; int Arg2 = ; verify_case(, Arg2, count(Arg0, Arg1)); }

     void test_case_3() { int Arg0 = ; int Arg1 = ; int Arg2 = ; verify_case(, Arg2, count(Arg0, Arg1)); }

 // END CUT HERE

 };

 // BEGIN CUT HERE

 int main()

 {

 //    freopen( "a.out" , "w" , stdout );

     TheLuckyNumbers ___test;

     ___test.run_test(-);

        return ;

 }

 // END CUT HERE

DIV1 500pt

题意：称各个数位只含有4和7的数为lucky number，称完全由来自vector<int> numbers(含有lucky number和也含有unlucky number)里面的lucky number组成，且每一个a[i]的末位数字和a[i+1]的首位数字均相同的序列为lucky sequence。给定vector<int> numbers和int n，求长度为n的lucky sequence有多少个。只要一个数不同，则lucky sequence视为不同。

解法：lucky number分为四种，分别为4开头4结尾的，4开头7结尾的，7开头4结尾的，7开头7结尾的。若a[i]属于第A类，且a[i+1]可以为B类，则从A向B连接一条有向边。这样，就相当于求长度为n的路径有多少条。

　　　我最初的想法是二分，设f(x, s, e)表示求长度为x，从s类开始，从e类结束的路径有多少条，f(x, s, e)由 f(x/2, s, i) 和 f(x-x/2, i, e)求得。我以为这样二分以后时间复杂度降低了，实际上每次二分都有4个决策，时间复杂度反而提升了，于是我毫无悬念地TLE了。然后，我改了代码，把x / 2变成了x / 10000，即将x分为10001段来求，由于前面每一段长度均为x/10000，后面一段长度为x - x/10000，所以实际上只需要求20个东西，这样时间复杂度就降低到能接受的范围了。

　　　虽然算是水过了这道题，还是蛮开心的.....

　　　官方题解给出的方法是用矩阵快速幂优化。其实要构造这个并不难吧。。。当时想了一下用矩阵，怎么就没想出来呢。。。。

tag:矩阵乘法

 // BEGIN CUT HERE

 /*

  * Author:  plum rain

  * score :

  */

 /*

  */

 // END CUT HERE

 #line 11 "TheLuckySequence.cpp"

 #include <sstream>

 #include <stdexcept>

 #include <functional>

 #include <iomanip>

 #include <numeric>

 #include <fstream>

 #include <cctype>

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <cstdlib>

 #include <set>

 #include <queue>

 #include <bitset>

 #include <list>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define CLR1(x) memset(x, -1, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define ALL(t) t.begin(),t.end()

 #define zero(x) (((x)>0?(x):-(x))<eps)

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef pair<int, int> pii;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 const int mod = ;

 int64 cnt[];

 pii temp[];

 set<int> st;

 int64 pat[][], d[][][];

 int64 an[][];

 int gao(int x)

 {

     pii num;

     num.second = x % ;

     while (x >= ){

         int tmp = x % ;

         x /= ;

         if (tmp !=  && tmp != ) return -;

     }

     num.first = x % ;

     for (int i = ; i < ; ++ i)

         if (num == temp[i]) return i;

     return -;

 }

 int64 rec(int len, int s, int e)

 {

     if (!len) return s == e;

     if (len == ) return pat[s][e];

     if (len <  && d[len][s][e] != -)

         return d[len][s][e];

     if (len < ){

         int haf = len / ;

         int64 &ret = d[len][s][e];

         ret = ;

         for (int i = ; i < ; ++ i)

             ret = (ret + rec(haf, s, i) * rec(len-haf, i, e)) % mod;

         return ret;

     }

     int haf = len / ;

     CLR (an);

     for (int i = ; i < ; ++ i)

         an[][i] = rec(haf, s, i);

     for (int i = ; i < ; ++ i)

         for (int j = ; j < ; ++ j)

             for (int k = ; k < ; ++ k)

                 an[i][j] = (an[i][j] + an[i-][k] * rec(haf, k, j)) % mod;

     int64 ret = ;

     for (int i = ; i < ; ++ i)

         ret = (ret + an[][i] * rec(len-haf*, i, e)) % mod;

     return ret;

 }

 class TheLuckySequence

 {

     public:

         int count(vector <int> num, int len){

             temp[] = make_pair(,); temp[] = make_pair(,);

             temp[] = make_pair(,); temp[] = make_pair(,);

             CLR (cnt); st.clear();

             for (int i = ; i < (int)num.size(); ++ i){

                 int tmp = gao(num[i]);

                 if (tmp != - && !st.count(num[i])){

                     ++ cnt[tmp];

                     st.insert(num[i]);

                 }

             }

             CLR (pat);

             for (int i = ; i < ; ++ i)

                 for (int j = ; j < ; ++ j)

                     if (temp[i].second == temp[j].first){

                         pat[i][j] = cnt[i];

                     }

             CLR1 (d);

             int64 ret = ;

             for (int i = ; i < ; ++ i)

                 for (int j = ; j < ; ++ j)

                     ret = (ret + rec(len-, i, j) * cnt[j]) % mod;

             return (int)ret;

         }

 // BEGIN CUT HERE

     public:

     void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); }

     private:

     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

     void test_case_0() { int Arr0[] = {, , , , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, count(Arg0, Arg1)); }

     void test_case_1() { int Arr0[] = {, , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, count(Arg0, Arg1)); }

     void test_case_2() { int Arr0[] = {, , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, count(Arg0, Arg1)); }

     void test_case_3() { int Arr0[] = {, , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, count(Arg0, Arg1)); }

 // END CUT HERE

 };

 // BEGIN CUT HERE

 int main()

 {

 //    freopen( "a.out" , "w" , stdout );

     TheLuckySequence ___test;

     ___test.run_test(-);

        return ;

 }

 // END CUT HERE

最新文章

  1. 基于MATLAB求解矩阵的正交补矩阵
  2. 快速搭建Webservice接口测试环境
  3. Oracle数据库习题
  4. sql日期函数操作
  5. iOS 中关于ViewController总结
  6. Oracle数据库——表的创建与管理
  7. CSS 居中大全【转】
  8. JavaScript创建对象的写法
  9. Oracle select 中case 的使用以及使用decode替换case
  10. swiper遇到的问题及解决方法
  11. 【Java入门提高篇】Day9 Java内部类——静态内部类
  12. Docker最全教程——从理论到实战（八）
  13. Ubuntu寻找某某库
  14. 愚人节CDACMFinal
  15. nltk——文本分类
  16. OCP知识点讲解 之 检查点队列与增量检查点
  17. 异步IO（协程，消息循环队列）
  18. MP实战系列(九)之集成Shiro
  19. 三分钟彻底禁用、隐藏Android设备底部虚拟按钮（亲测有效）
  20. how to build jdk 9 source code

热门文章

  1. Xcode7插件开发：从开发到拉到恶魔岛
  2. 十七、C# 反射、特性和动态编程
  3. hdoj 2040
  4. 【转】《我的WCF之旅》博文系列汇总
  5. SGU 172.eXam（二分图染色）
  6. Flume研究心得
  7. jQuery慢慢啃筛选（四）
  8. MVC埰坑日记 文件权限
  9. 为什么我们不喜欢用富UI控件
  10. 根据打开页面加载不同Js