• <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>

            Why so serious? --[NKU]schindlerlee

            2010年03月04日星期四.pku1395 && nwerc2001 Cog-Wheels 動態規劃

            2010年03月04日星期四.pku1395 && nwerc2001 Cog-Wheels 動態規劃
            這個題其實不難,首先將所有可能的比例用二重循環求出來,然后在1~10000范圍內做dp,把所有
            可能的乘積都求出來,然后再看看最后所求的比例化簡之后得到的兩個數是否都可達。

            ?1?const?int?N?=?64;
            ?2?const?int?inf?=?1?<<?30;
            ?3?int?num[N],?n,?m,?qa,?qb;
            ?4?const?int?M?=?10010;
            ?5?bool?stat[M];
            ?6?
            ?7?int?gcd(int?a,?int?b)
            ?8?{
            ?9?????if?(b==0)?return?a;
            10?????return?gcd(b,a%b);
            11?}
            12?
            13?bool?judge(int?a,?int?b)
            14?{
            15???for?(int?i?=?1;?i?*?a?<?M?&&?i?*?b?<?M;?i++)?{
            16???????if?(stat[i?*?a]?&&?stat[i?*?b])?{
            17???????????return?true;
            18???????}
            19???}
            20???return?false;
            21?}
            22//http://www.shnenglu.com/schindlerlee
            23?int?fac[M],top;
            24?void?pre()
            25?{
            26???int?i,?j,?tmp;
            27???scanf("%d",?&n);
            28???for?(i?=?0;?i?<?n;?i++)?{
            29???????scanf("%d",?num?+?i);
            30???}
            31???top?=?0;
            32???for?(i?=?0;?i?<?n;?i++)?{
            33???????for?(j?=?0;j?<?n;j++)?{
            34???????????if?(i?==?j)?{?continue;?}
            35???????????if?(num[i]?%?num[j]?==?0)?{
            36???????????????fac[top++]?=?num[i]?/?num[j];
            37???????????}
            38???????}
            39???}
            40???stat[1]?=?1;
            41???for?(i?=?0;?i?<?top;?i++)?{
            42???????for?(j?=?1;?j?<?M;?j++)?{
            43???????????if?(stat[j])?{
            44???????????????tmp?=?j?*?fac[i];
            45???????????????if?(tmp?<?M)?{
            46???????????????????stat[tmp]?=?1;
            47???????????????}
            48???????????}
            49???????}
            50???}
            51?}
            52?
            53?int?main()
            54?{
            55???int?testcase,?testid,?a,?b;
            56???scanf("%d",?&testcase);
            57???for?(testid?=?1;?testid?<=?testcase;?testid++)?{
            58???????pre();
            59???????scanf("%d",?&m);
            60???????printf("Scenario?#%d:\n",?testid);
            61???????while?(m--)?{
            62???????????scanf("%d%d",?&a,?&b);
            63???????????int?d?=?gcd(a,?b);
            64???????????qa?=?a?/?d,?qb?=?b?/?d;
            65???????????if?(judge(qa,?qb))?{
            66???????????????printf("Gear?ratio?%d:%d?can?be?realized.\n",?a,?b);
            67???????????}?else?{
            68???????????????printf("Gear?ratio?%d:%d?cannot?be?realized.\n",?a,?b);
            69???????????}
            70???????}
            71???????putchar(10);
            72???????if?(testid?<?testcase)?{
            73???????????memset(stat,?0,?sizeof(stat));
            74???????}
            75???}
            76?
            77???return?0;
            78?}
            79?

            posted on 2010-03-04 17:27 schindlerlee 閱讀(1248) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            WWW婷婷AV久久久影片| 久久中文字幕无码专区| 日产精品久久久久久久性色| 久久久久高潮毛片免费全部播放| 99999久久久久久亚洲| 亚洲?V乱码久久精品蜜桃| 人妻久久久一区二区三区| 国内精品欧美久久精品| 久久久久亚洲精品日久生情| 国产精品视频久久| 一本色综合网久久| 久久伊人色| 丁香五月综合久久激情| 久久精品亚洲中文字幕无码麻豆| 久久播电影网| 国内精品久久久久久野外| 亚洲人成电影网站久久| 精品99久久aaa一级毛片| 久久综合亚洲欧美成人| 久久久久波多野结衣高潮| 国产精品久久久天天影视香蕉| 7777久久亚洲中文字幕| 中文无码久久精品| 久久天天躁夜夜躁狠狠躁2022| 久久本道综合久久伊人| 久久99精品国产99久久| 少妇久久久久久被弄高潮| 一本综合久久国产二区| 国产精品免费看久久久香蕉| 久久综合久久自在自线精品自| 狠狠色丁香久久婷婷综合图片 | 日本五月天婷久久网站| 国产精品激情综合久久| 久久精品国产WWW456C0M| 成人国内精品久久久久影院VR| 国产99久久精品一区二区| 狠狠干狠狠久久| 国产亚州精品女人久久久久久 | 久久免费看黄a级毛片| 日韩久久无码免费毛片软件| 日韩电影久久久被窝网|