• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統計

            • 隨筆 - 182
            • 文章 - 1
            • 評論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            SRM 484

            DIV 2

            1 250
            十分無恥的一道題目,無恥的過掉


            2 500
              需要比較強的YY能力。
              按照題目給出的思路,很顯然不能有進位!然后數字只剩下了0 1 2 3;
              我的第一反應是這些東西,應該是前面的某些數字的組合。。。(這個十分逼近答案了。。無語,然后卡住了)
              既然只剩下了0123,很顯然的四進制!我們算一下10^9次方范圍上,這樣的數究竟有多少個呢?2^18(0也算在內了) 2^18這個數很小的!262144,然后逐個檢查吧!
                看到這種low 和high數據范圍的題目往往讓人們想到數學解法。。怎么從數學中轉到計算機中,是一門能力啊!
            long long  S(long long N)
            {
                int ans=0;
                while(N>0)
                    ans+=N%10,N/=10;
                return ans;

            }
            class RabbitNumber
            {
                    public:
                    int theCount(int low, int high)
                    {
                        int ans=0;
                        for(int i=0;i<(1<<18);i++)
                        {
                            long long x=0,y=i;
                            for(int j=0;j<9;j++){x=x*10+y%4;y/=4;}
                            if(x>=low&&x<=high && S(x*x)==S(x)*S(x))ans++;
                        }
                        if(high==1000000000)ans++;
                        return ans;               
                    }
            };
            如果你是在沒有觀察出來,這個4進制,也沒有關系,來看一下S(x)的性質。如果x的數據范圍是10^9,那么S(x*x)是多大呢? 9*18=162,然后S(x)的范圍就是sqrt(162)<13.我們枚舉數字之和小于等于14的數就完全OK。
            那么數字之和小于等于14 的大概有多少呢?  319770! 也是一個相當小的數! 看一下wuyi大神的解法:
            #define LL long long
            const int limit = 14;
            const int MaxN = 9;
            int S, L,R;
            int res;

            int f(LL x) {
                int ret=0;
                while(x)ret+=x%10,x/=10;
                return ret;
            }

            int Dfs(int d, LL x, int r) {
                cout<<d<<"     "<<x<<"       "<<r<<endl;
                if(x > R) return 0;
                if(x >= L && x <= R) {
                    if((14-r)*(14-r) == f((LL)x * x)) ++ res;
                }
                for(int c = !d ; c < 10 && c <= r; ++ c)
                    Dfs(d + 1, x * 10 + c, r - c);
            }

            class RabbitNumber
            {
            public:
                int theCount(int l, int r){
                    L=l;R=r;
                    res=0;
                    if(R == 1000000000) ++ res, -- R;
                    if(L > R) return res;
                    Dfs(0,0,14);
                    return res;
                }
            };

             

            3 1000

            很顯然純粹枚舉,當然沒戲!但是有技巧的枚舉(剪枝)還是可以的!比如說,純粹暴力數據是2^40,如果我們枚舉四個對角點,則數據范圍下降到了2^20!這種剪枝技巧實在是太強大了!
            比如枚舉0 2 5 7

            class CubeColoring
            {
            public:
                long long theCount(vector <string> colors)
                {
                    int n=colors[0].size();
                    long long res=0;
                    for(int a=0;a<n;a++)for(int c=0;c<n;c++)for(int f=0;f<n;f++)for(int h=0;h<n;h++)
                    {
                        if(colors[0][a]=='Y'&&colors[2][c]=='Y'&&colors[5][f]=='Y'&&colors[7][h]=='Y')
                        {
                            int B=0;for(int b=0;b<n;b++)if(b!=a&&b!=c&&b!=f&&colors[1][b]=='Y')B++;
                            int D=0;for(int d=0;d<n;d++)if(d!=a&&d!=c&&d!=h&&colors[3][d]=='Y')D++;
                            int E=0;for(int e=0;e<n;e++)if(e!=a&&e!=f&&e!=h&&colors[4][e]=='Y')E++;
                            int G=0;for(int g=0;g<n;g++)if(g!=c&&g!=f&&g!=h&&colors[6][g]=='Y')G++;
                            res +=B*D*E*G;

                        }

                    }
                    return res;            
                }
            };

             

             

            Test Case: 5
            Succeeded: Yes
            Execution Time: 604 ms
            Args:
            {{"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY"}}

            Expected:
            751325186912

            Received:
            751325186912

            操作規模是2^27的,數據規模是一億三千萬....TC還是蠻快的!

            這個問題的難點是怎么找到處理數據的方法,解法中就是把0 2 5 7單獨抽離,做枚舉!

            整個DIV2的題目都是在處理數據范圍上下功夫!畢竟,這是coder的一個基本功!

            ================================================================================

            不算華麗的分割線

            ================================================================================

             

            DIV 1

            0 250

            通過DIV2 250

            1 550
            一樣的一個組合DP問題,與SRM 478 rng58的那個dp組合問題相似!以后再整理!

            2 1000
            沒看,以后再說。。抓緊時間寫作業。。。-_-~~~!!!!!!!!!好囧啊。。。

            posted on 2010-10-06 16:18 Sosi 閱讀(376) 評論(0)  編輯 收藏 引用

            統計系統
            久久久青草久久久青草| 国内精品久久久久影院网站| 久久精品中文字幕一区| 国产精品嫩草影院久久| 久久精品一区二区三区中文字幕 | 日韩美女18网站久久精品| 欧美激情精品久久久久久| 亚洲成色WWW久久网站| 久久91精品国产91久久户| 一本久道久久综合狠狠躁AV| 久久精品国产亚洲AV蜜臀色欲 | 欧美色综合久久久久久| 伊人色综合久久天天人手人婷 | AV狠狠色丁香婷婷综合久久| 久久久噜噜噜久久中文字幕色伊伊| 久久久久人妻一区二区三区 | 久久久久久免费一区二区三区| 久久久久这里只有精品 | 一本久道久久综合狠狠爱| 国产精品美女久久久m| 性做久久久久久免费观看| 亚洲乱亚洲乱淫久久| 亚洲中文字幕久久精品无码APP| 中文字幕久久欲求不满| 久久精品亚洲一区二区三区浴池| 久久亚洲AV永久无码精品| 色综合久久中文色婷婷| 国产成人精品白浆久久69| 久久久久免费精品国产| 久久精品桃花综合| 久久精品亚洲精品国产欧美| 91久久精品电影| 88久久精品无码一区二区毛片| 日韩精品久久无码中文字幕| 国产A三级久久精品| 久久久久久精品无码人妻| 无码任你躁久久久久久老妇App| 亚洲精品久久久www| 久久久中文字幕日本| 综合久久久久久中文字幕亚洲国产国产综合一区首 | 无夜精品久久久久久|