注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Saffah's Blog

 
 
 

日志

 
 

BestCoder Round #9  

2014-09-15 07:39:28|  分类: BestCoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1001 Revenge of ex-Euclid (HDU 4993)

给a,b,c,求ax+by=c的解的组数。
数据组数≤100,1≤a,b,c≤10^6。
Solution
枚举x就行了。
int main(){
    int T; scanf("%d", &T);
    while(T--){
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        int mx = c / a;
        int ans = 0;
        f(x, 1, mx){
            int by = c - a * x;
            if(by % b == 0){
                int y = by / b;
                if(y > 0) ++ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
1002 Revenge of Nim (HDU 4994)
有N堆石子,第i堆有A_i个,双方轮流行动,每次可以取走最左端的一堆中的任意个石子(至少一个),取到最后一个石子的获胜。问先手是否必胜。
数据组数≤100,N≤1000。
Solution
如果当前堆只有1个石子,那么他别无选择;否则,他有权决定自己拿完这堆或给对方剩1个。
换言之,只要当前堆石子数大于1则先手必胜。
那么找到第一个不为1的堆,此时的先手必胜;如果所有堆都为1,那么根据N的奇偶性判断。
int a[1086];
int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        f(i, 1, n) scanf("%d", a + i);
        bool find = false;
        f(i, 1, n) if(a[i] != 1 && !find){
            find = true;
            if(i % 2) printf("Yes\n"); else printf("No\n");
        }
        if(!find){
            if(n % 2) printf("Yes\n"); else printf("No\n");
        }
    }
    return 0;
}
1003 Revenge of kNN (HDU 4995)
阅读理解题……
Solution
直接模拟就行了。(没看懂题千万不要乱写= =WA了5发)
struct pair{
    LL pos, id; double val;
} p[100086]; int pid[100086];
inline bool operator <(pair x, pair y){
    return x.pos < y.pos;
}

int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n, m, k; scanf("%d%d%d", &n, &m, &k);
        f(i, 1, n){
            int tmp; read(tmp); p[i].pos = tmp; read(tmp); p[i].val = tmp;
            p[i].id = i;
        }
        std::sort(p + 1, p + n + 1);
        f(i, 1, n) pid[p[i].id] = i;
        p[0].pos = -0x1f1f1f1f1f1f1f1fLL; p[n + 1].pos = 0x1f1f1f1f1f1f1f1fLL;
        p[0].id = 2000000; p[n + 1].id = 2000000;
        double tans = 0;
        while(m--){
            int c; read(c); c = pid[c];
            int ck = k, cl = c - 1, cr = c + 1;
            double cs = 0;
            while(ck--){
                LL lans = p[c].pos - p[cl].pos;
                LL rans = p[cr].pos - p[c].pos;
                if(lans < rans){
                    cs += p[cl].val; --cl;
                }else if(rans < lans){
                    cs += p[cr].val; ++cr;
                }else{
                    int lid = p[cl].id;
                    int rid = p[cr].id;
                    if(lid < rid){
                        cs += p[cl].val; --cl;
                    }else{
                        cs += p[cr].val; ++cr;
                    }
                }
            }
            cs /= k; p[c].val = cs;
            tans += cs;
        }
        printf("%.6lf\n", tans);
    }
    return 0;
}
1004 Revenge of LIS (HDU 4996)
给N和K,问有多少个1到N的排列的LIS长度为K。
K≤N≤18。
Solution
考虑用二分查找搞的O(nlogn)求LIS长度的算法。对于每个数可能有3种状态:没加入、已加入且仍在表中、已加入且不在表中。本地跑O(3^n)状态的dp,然后交表。

同样这种东西可以在OEIS上面找到……http://oeis.org/A047874
(在32位机上爆空间啊T_T所以mod 1e9算低位,然后用float算高位,然后把两个结果手动合并起来……)
int n;
//    0 wait    1 in    2 out
LL DP[387420489];
LL ans[20];

struct state{
    int dp[20], lis; bool in[20];
    inline state(){}
};
inline state unpack(int S){
    state ret;
    ret.lis = 0;
    f(i, 1, n){
        int c = S % 3;
        if(c == 0) ret.in[i] = 0;
        else if(c == 1){
            ret.in[i] = 1; ret.dp[++ret.lis] = i;
        }else ret.in[i] = 1;
        S /= 3;
    }
    return ret;
}
inline int pack(state s){
    int ans[20];
    memset(ans, 0, sizeof(ans));
    f(i, 1, n) if(s.in[i]) ans[i] = 2;
    f(i, 1, s.lis) ans[s.dp[i]] = 1;
    int ret = 0;
    h(i, n, 1) ret = ret * 3 + ans[i];
    return ret;
}
inline state trans(state s, int c){
    s.in[c] = 1;
    if(s.lis){
        bool succ = false;
        h(i, s.lis, 1) if(c > s.dp[i]){
            if(i == s.lis){
                ++s.lis; s.dp[s.lis] = c; 
            }else if(c < s.dp[i + 1]) s.dp[i + 1] = c;
            succ = true;
            break;
        }
        if(!succ && c < s.dp[1]) s.dp[1] = c;
    }else{
        s.lis = 1; s.dp[1] = c;
    }
    return s;
}
inline void upd(int S){
    state s = unpack(S);
    bool ok = true;
    f(c, 1, n) if(!s.in[c]){
        ok = false;
        state t = trans(s, c);
        int T = pack(t);
        DP[T] += DP[S];
    }
    if(ok) ans[s.lis] += DP[S];
}

int main(){
    printf("%lf\n", (double) sizeof(DP) / 1048576.0);
    scanf("%d", &n);
    int tot = 1; f(i, 1, n) tot *= 3;
    memset(DP, 0, sizeof(DP));
    memset(ans, 0, sizeof(ans));
    DP[0] = 1; int inv = tot / 100;
    g(i, 0, tot){
        upd(i);
        if(i % inv == 0) printf("%d percent finished\n", i / inv);
    }
    f(i, 1, n) printf("if(n == %d && k == %d) printf(\"\%I64d\\n\");\n", n, i, ans[i]);
    return 0;
}
下面是表……
int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n, k; scanf("%d%d", &n, &k);
        if(n == 1 && k == 1) printf("1\n");
        if(n == 2 && k == 1) printf("1\n");
        if(n == 2 && k == 2) printf("1\n");
        if(n == 3 && k == 1) printf("1\n");
        if(n == 3 && k == 2) printf("4\n");
        if(n == 3 && k == 3) printf("1\n");
        if(n == 4 && k == 1) printf("1\n");
        if(n == 4 && k == 2) printf("13\n");
        if(n == 4 && k == 3) printf("9\n");
        if(n == 4 && k == 4) printf("1\n");
        if(n == 5 && k == 1) printf("1\n");
        if(n == 5 && k == 2) printf("41\n");
        if(n == 5 && k == 3) printf("61\n");
        if(n == 5 && k == 4) printf("16\n");
        if(n == 5 && k == 5) printf("1\n");
        if(n == 6 && k == 1) printf("1\n");
        if(n == 6 && k == 2) printf("131\n");
        if(n == 6 && k == 3) printf("381\n");
        if(n == 6 && k == 4) printf("181\n");
        if(n == 6 && k == 5) printf("25\n");
        if(n == 6 && k == 6) printf("1\n");
        if(n == 7 && k == 1) printf("1\n");
        if(n == 7 && k == 2) printf("428\n");
        if(n == 7 && k == 3) printf("2332\n");
        if(n == 7 && k == 4) printf("1821\n");
        if(n == 7 && k == 5) printf("421\n");
        if(n == 7 && k == 6) printf("36\n");
        if(n == 7 && k == 7) printf("1\n");
        if(n == 8 && k == 1) printf("1\n");
        if(n == 8 && k == 2) printf("1429\n");
        if(n == 8 && k == 3) printf("14337\n");
        if(n == 8 && k == 4) printf("17557\n");
        if(n == 8 && k == 5) printf("6105\n");
        if(n == 8 && k == 6) printf("841\n");
        if(n == 8 && k == 7) printf("49\n");
        if(n == 8 && k == 8) printf("1\n");
        if(n == 9 && k == 1) printf("1\n");
        if(n == 9 && k == 2) printf("4861\n");
        if(n == 9 && k == 3) printf("89497\n");
        if(n == 9 && k == 4) printf("167449\n");
        if(n == 9 && k == 5) printf("83029\n");
        if(n == 9 && k == 6) printf("16465\n");
        if(n == 9 && k == 7) printf("1513\n");
        if(n == 9 && k == 8) printf("64\n");
        if(n == 9 && k == 9) printf("1\n");
        if(n == 10 && k == 1) printf("1\n");
        if(n == 10 && k == 2) printf("16795\n");
        if(n == 10 && k == 3) printf("569794\n");
        if(n == 10 && k == 4) printf("1604098\n");
        if(n == 10 && k == 5) printf("1100902\n");
        if(n == 10 && k == 6) printf("296326\n");
        if(n == 10 && k == 7) printf("38281\n");
        if(n == 10 && k == 8) printf("2521\n");
        if(n == 10 && k == 9) printf("81\n");
        if(n == 10 && k == 10) printf("1\n");
        if(n == 11 && k == 1) printf("1\n");
        if(n == 11 && k == 2) printf("58785\n");
        if(n == 11 && k == 3) printf("3704504\n");
        if(n == 11 && k == 4) printf("15555398\n");
        if(n == 11 && k == 5) printf("14516426\n");
        if(n == 11 && k == 6) printf("5122877\n");
        if(n == 11 && k == 7) printf("874886\n");
        if(n == 11 && k == 8) printf("79861\n");
        if(n == 11 && k == 9) printf("3961\n");
        if(n == 11 && k == 10) printf("100\n");
        if(n == 11 && k == 11) printf("1\n");
        if(n == 12 && k == 1) printf("1\n");
        if(n == 12 && k == 2) printf("208011\n");
        if(n == 12 && k == 3) printf("24584693\n");
        if(n == 12 && k == 4) printf("153315999\n");
        if(n == 12 && k == 5) printf("192422979\n");
        if(n == 12 && k == 6) printf("87116283\n");
        if(n == 12 && k == 7) printf("18943343\n");
        if(n == 12 && k == 8) printf("2250887\n");
        if(n == 12 && k == 9) printf("153341\n");
        if(n == 12 && k == 10) printf("5941\n");
        if(n == 12 && k == 11) printf("121\n");
        if(n == 12 && k == 12) printf("1\n");
        if(n == 13 && k == 1) printf("1\n");
        if(n == 13 && k == 2) printf("742899\n");
        if(n == 13 && k == 3) printf("166335677\n");
        if(n == 13 && k == 4) printf("1538907306\n");
        if(n == 13 && k == 5) printf("2579725656\n");
        if(n == 13 && k == 6) printf("1477363967\n");
        if(n == 13 && k == 7) printf("399080475\n");
        if(n == 13 && k == 8) printf("59367101\n");
        if(n == 13 && k == 9) printf("5213287\n");
        if(n == 13 && k == 10) printf("275705\n");
        if(n == 13 && k == 11) printf("8581\n");
        if(n == 13 && k == 12) printf("144\n");
        if(n == 13 && k == 13) printf("1\n");
        if(n == 14 && k == 1) printf("1\n");
        if(n == 14 && k == 2) printf("2674439\n");
        if(n == 14 && k == 3) printf("1145533650\n");
        if(n == 14 && k == 4) printf("15743413076\n");
        if(n == 14 && k == 5) printf("35098717902\n");
        if(n == 14 && k == 6) printf("25191909848\n");
        if(n == 14 && k == 7) printf("8312317976\n");
        if(n == 14 && k == 8) printf("1508071384\n");
        if(n == 14 && k == 9) printf("164060352\n");
        if(n == 14 && k == 10) printf("11110464\n");
        if(n == 14 && k == 11) printf("469925\n");
        if(n == 14 && k == 12) printf("12013\n");
        if(n == 14 && k == 13) printf("169\n");
        if(n == 14 && k == 14) printf("1\n");
        if(n == 15 && k == 1) printf("1\n");
        if(n == 15 && k == 2) printf("9694844\n");
        if(n == 15 && k == 3) printf("8017098273\n");
        if(n == 15 && k == 4) printf("164161815768\n");
        if(n == 15 && k == 5) printf("485534447114\n");
        if(n == 15 && k == 6) printf("434119587475\n");
        if(n == 15 && k == 7) printf("172912977525\n");
        if(n == 15 && k == 8) printf("37558353900\n");
        if(n == 15 && k == 9) printf("4927007100\n");
        if(n == 15 && k == 10) printf("410474625\n");
        if(n == 15 && k == 11) printf("22128576\n");
        if(n == 15 && k == 12) printf("766221\n");
        if(n == 15 && k == 13) printf("16381\n");
        if(n == 15 && k == 14) printf("196\n");
        if(n == 15 && k == 15) printf("1\n");
        if(n == 16 && k == 1) printf("1\n");
        if(n == 16 && k == 2) printf("35357669\n");
        if(n == 16 && k == 3) printf("56928364553\n");
        if(n == 16 && k == 4) printf("1744049683213\n");
        if(n == 16 && k == 5) printf("6835409506841\n");
        if(n == 16 && k == 6) printf("7583461369373\n");
        if(n == 16 && k == 7) printf("3615907795025\n");
        if(n == 16 && k == 8) printf("927716186325\n");
        if(n == 16 && k == 9) printf("143938455225\n");
        if(n == 16 && k == 10) printf("14353045401\n");
        if(n == 16 && k == 11) printf("947236425\n");
        if(n == 16 && k == 12) printf("41662441\n");
        if(n == 16 && k == 13) printf("1203441\n");
        if(n == 16 && k == 14) printf("21841\n");
        if(n == 16 && k == 15) printf("225\n");
        if(n == 16 && k == 16) printf("1\n");
        if(n == 17 && k == 1) printf("1\n");
        if(n == 17 && k == 2) printf("129644789\n");
        if(n == 17 && k == 3) printf("409558170361\n");
        if(n == 17 && k == 4) printf("18865209953045\n");
        if(n == 17 && k == 5) printf("97966603326993\n");
        if(n == 17 && k == 6) printf("134533482045389\n");
        if(n == 17 && k == 7) printf("76340522760097\n");
        if(n == 17 && k == 8) printf("22904111472825\n");
        if(n == 17 && k == 9) printf("4142847526101\n");
        if(n == 17 && k == 10) printf("484748595081\n");
        if(n == 17 && k == 11) printf("38094121561\n");
        if(n == 17 && k == 12) printf("2043822961\n");
        if(n == 17 && k == 13) printf("74797417\n");
        if(n == 17 && k == 14) printf("1830561\n");
        if(n == 17 && k == 15) printf("28561\n");
        if(n == 17 && k == 16) printf("256\n");
        if(n == 17 && k == 17) printf("1\n");

        if(n == 18 && k == 1) printf("1\n");
        if(n == 18 && k == 2) printf("477638699\n");
        if(n == 18 && k == 3) printf("2981386305018\n");
        if(n == 18 && k == 4) printf("207591285198178\n");
        if(n == 18 && k == 5) printf("1429401763567226\n");
        if(n == 18 && k == 6) printf("2426299018270338\n");
        if(n == 18 && k == 7) printf("1631788075873114\n");
        if(n == 18 && k == 8) printf("568209449266202\n");
        if(n == 18 && k == 9) printf("118504614869214\n");
        if(n == 18 && k == 10) printf("16029615164446\n");
        if(n == 18 && k == 11) printf("1470147102730\n");
        if(n == 18 && k == 12) printf("93574631242\n");
        if(n == 18 && k == 13) printf("4166173834\n");
        if(n == 18 && k == 14) printf("128922442\n");
        if(n == 18 && k == 15) printf("2708305\n");
        if(n == 18 && k == 16) printf("36721\n");
        if(n == 18 && k == 17) printf("289\n");
        if(n == 18 && k == 18) printf("1\n");
    }
    return 0;
}
  评论这张
 
阅读(59)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018