# Who = Penalty * A B C D E F
479 arkethos 4 247  

+

00:08

+

00:19

+1

00:59

+2

01:41

    
479  ne-leonardinkret 4 247  

+

00:04

 -1

+1

00:27

+2

01:47

+

00:49

  
481 MeePwn# 4 248  

+

00:14

+

00:21

+

00:54

+3

01:39

    
482  shreypandey 4 251  

+

00:06

+

00:10

+

00:17

  

+5

01:58

  
483 iskander232 4 252  

+1

00:06

+2

00:23

+

00:17

 -3

+2

01:46

  

Chess For Three

默认第一场比赛由AB进行

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<string>

using std::vector;

using std::queue;

using std::map;

using std::sort;

using std::string;

using std::lower_bound;

using std::upper_bound;

#define read(x) scanf("%d", &x)

#define reads(x) scanf("%s", x)

#define write(x) printf("%d ", x)

#define writes(x) printf("%s ", x)

#define writeln(x) printf("%d\n", x)

#define writesln(x) printf("%s\n", x)

#define fillchar(x, a) memset(x, a, sizeof(x))

typedef long long llint;

/*data structure*/

/*data structure*/

int cmp(const void * x, const void * y) {

#define datatype int

    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));

    //x < y

    return dx > dy ?  : -;

#undef datatype

}

/*global variable*/

int a[];

/*global variable*/

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    int n;

    read(n);

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

        read(a[i]);

        a[i]--;

    }

    int p1 = , p2 = , spec = ;

    bool flag1 = true;

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

        if (a[i] == spec) {

            flag1 = false;

            break;

        }

        if (p1 == a[i]) {

            int t = p2;

            p2 = spec;

            spec = t;

        } else {

            int t = p1;

            p1 = spec;

            spec = t;

        }

    }

    if (flag1) printf("YES\n");

    else printf("NO\n");

    return ;

}

Beautiful Divisors

直接把符合条件的数列出来找

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<string>

using std::vector;

using std::queue;

using std::map;

using std::sort;

using std::string;

using std::lower_bound;

using std::upper_bound;

#define read(x) scanf("%d", &x)

#define reads(x) scanf("%s", x)

#define write(x) printf("%d ", x)

#define writes(x) printf("%s ", x)

#define writeln(x) printf("%d\n", x)

#define writesln(x) printf("%s\n", x)

#define fillchar(x, a) memset(x, a, sizeof(x))

typedef long long llint;

/*data structure*/

/*data structure*/

int cmp(const void * x, const void * y) {

#define datatype int

    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));

    //x < y

    return dx > dy ?  : -;

#undef datatype

}

/*global variable*/

int a[];

/*global variable*/

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    int n;

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

        a[i] = (( << i) - ) * ( << (i - ));

        if (a[i] > ) {

            n = i;

            break;

        }

    }

    int x;

    read(x);

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

        if (x % a[i] == ) {

            writeln(a[i]);

            break;

        }

    }

    return ;

}

Rumor

贪心，每次贿赂还不知道的人里边底线最低的

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<string>

#include<functional>

using std::priority_queue;

using std::vector;

using std::queue;

using std::map;

using std::sort;

using std::string;

using std::lower_bound;

using std::upper_bound;

#define read(x) scanf("%d", &x)

#define reads(x) scanf("%s", x)

#define write(x) printf("%d ", x)

#define writes(x) printf("%s ", x)

#define writeln(x) printf("%d\n", x)

#define writesln(x) printf("%s\n", x)

#define fillchar(x, a) memset(x, a, sizeof(x))

typedef long long llint;

/*data structure*/

struct cha {

    int id;

    llint c;

    friend bool operator< (cha n1, cha n2) {

        return n1.c > n2.c;

    }

};

/*data structure*/

int cmp(const void * x, const void * y) {

#define datatype int

    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));

    //x < y

    return dx > dy ?  : -;

#undef datatype

}

/*global variable*/

priority_queue<cha> q;

vector<int> G[];

bool v[];

/*global variable*/

void dfs(int x) {

    for (int i = ; i < G[x].size(); i++) {

        int u = G[x][i];

        if (v[u]) continue;

        v[u] = true;

        dfs(u);

    }

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    int n, m;

    read(n);

    read(m);

    while (!q.empty()) q.pop();

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

        cha ccc;

        ccc.id = i;

        scanf("%lld", &ccc.c);

        q.push(ccc);

        G[i].clear();

    }

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

        int x, y;

        read(x);

        read(y);

        G[x].push_back(y);

        G[y].push_back(x);

    }

    fillchar(v, false);

    long long ans = ;

    while (!q.empty()) {

        cha x = q.top();

        q.pop();

        if (v[x.id]) continue;

        ans += x.c;

        v[x.id] = true;

        dfs(x.id);

    }

    printf("%I64d\n", ans);

    return ;

}

Credit Card

首先，早上不存钱，把所有操作模拟一遍，记录每天晚上结束时的钱数m，如果某一天超过d，输出-1。

因为钱不会凭空消失，所以在某一天存入钱后，当天及以后每天的m值增加相同大小。

为了尽量少去，显然只有当a为0的日子才去，存的钱应该在不会导致之后超出d的情况下尽量多，为d减去之后的m值中最大的，再减去之前已经存过的钱数。

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<string>

#include<functional>

using std::priority_queue;

using std::vector;

using std::queue;

using std::map;

using std::sort;

using std::string;

using std::lower_bound;

using std::upper_bound;

#define read(x) scanf("%d", &x)

#define reads(x) scanf("%s", x)

#define write(x) printf("%d ", x)

#define writes(x) printf("%s ", x)

#define writeln(x) printf("%d\n", x)

#define writesln(x) printf("%s\n", x)

#define fillchar(x, a) memset(x, a, sizeof(x))

typedef long long llint;

/*data structure*/

/*data structure*/

int cmp(const void * x, const void * y) {

#define datatype int

    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));

    //x < y

    return dx > dy ?  : -;

#undef datatype

}

/*global variable*/

int a[];

llint m[], max[];

/*global variable*/

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    int n;

    llint d;

    scanf("%d%I64d", &n, &d);

    for (int i = ; i < n; i++) read(a[i]);

    m[] = a[];

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

        m[i] = m[i - ] + a[i];

    }

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

        if (m[i] > d) {

            printf("-1\n");

            return ;

        }

    }

    max[n - ] = m[n - ];

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

        if (m[i] > max[i + ]) max[i] = m[i];

        else max[i] = max[i + ];

    }

    int ans = ;

    llint add = , l, r;

    bool flag = true;

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

        if (a[i] != ) continue;

        if (m[i] + add >= ) continue;

        l = (llint) -  * m[i] - add;

        r = d - (max[i] + add);

        if (l > r) {

            flag = false;

            break;

        }

        ans++;

        add += r;

    }

    if (flag) printf("%d\n", ans);

    else printf("-1\n");

    return ;

}

Counting Arrays

把x分解质因数，对于有cnt个的质因子，答案乘以C(y+cnt-1,cnt)，关于这类问题，有一张总结的图（懒得编辑了，治疗一下颈椎病吧）：

这题被这个数据搞了一下：

1
524288 1000000

这个524288=1<<19，y是最大值1000000，加起来就是1000018，而我数组开的是1000005，于是就跪了。脸打的啪啪啪，牛批啊老哥。

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<string>

#include<functional>

#include<iostream>

//#include<bits/stdc++.h>

using namespace std;

#define fillchar(x, a) memset(x, a, sizeof(x))

typedef long long lint;

/*data structure*/

template <int size> class NoCombination {

public:

    lint fac[size], inv[size], f[size];

    lint mod;

    void init(lint m) {

        mod = m;

        fac[] = fac[] = inv[] = inv[] = f[] = f[] = ;

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

            fac[i] = fac[i - ] * i % mod;

            f[i] = (mod - mod / i) * f[mod % i] % mod;

            inv[i] = inv[i - ] * f[i] % mod;

        }

    }

    lint C(lint a, lint b) {

        return fac[a] * inv[b] % mod * inv[a - b] % mod;

    }

};

/*data structure*/

int cmp(const void * x, const void * y) {

#define datatype int

    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));

    //x < y

    return dx > dy ?  : -;

#undef datatype

}

/*global variable*/

NoCombination<> nc;

const lint mod = ;

bool f[];

int p[], m = ;

/*global variable*/

/*function*/

inline lint pow(lint a, lint b, lint p) {

    lint rtn = ;

    while (b) {

        if (b & ) rtn = rtn * a % p;

        a = a * a % p;

        b >>= ;

    }

    return rtn;

}

/*function*/

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    std::ios::sync_with_stdio(), cin.tie();

    nc.init(mod);

    fillchar(f, true);

    f[] = f[] = false;

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

        if (f[i]) {

            p[m++] = i;

            for (int j = i + i; j < ; j+=i) f[j] = false;

        }

    }

    int q, x, y;

    lint ans;

    cin >> q;

    while (q--) {

        cin >> x >> y;

        ans = ;

        int maxp = (int)sqrt(x);

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

            if (x ==  || p[i] > maxp) break;

            if (x % p[i] != ) continue;

            int cnt = ;

            while (x % p[i] == ) x /= p[i], cnt++;

            ans = ans * nc.C(y + cnt - , cnt) % mod;

        }

        if (x > ) ans = ans * y % mod;

        ans = ans * pow(, y - , mod) % mod;

        cout << ans << endl;

    }

    return ;

}

//

Subtree Minimum Query

这道题跟以前做过的一道题解法差不多，记录从每个点往下走1步，2步，4步，8步......能得到的最小的a，然后对于查询的k步用二进制表示出来各个位一凑就行。比如走7步相当于从第0个点走到第4个点的最小值、从第4个点走到第6个点的最小值、第6个点走到第7个点的最小值这3个最小值中的最小值，这样复杂度就变成了对数级别的。有几个可能会出错的坑，卡了我很久才弄明白，整理成两组测试数据：

2 1

1 2

1 2

1

1 100

4 1

10000 10000 10000 1

1 2

2 3

1 4

1

1 2

 
#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<string>

#include<functional>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

vector<int> G[];

vector<int> P[][];

int Q[][];

int a[], fa[], dep[];

vector<int> vi[];

int cmp(const void * x, const void * y) {

#define datatype int

    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));

    //x < y

    return dx > dy ?  : -;

#undef datatype

}

void dfs(int x) {

    for(int i = ; i < G[x].size(); i++) {

        int u = G[x][i];

        if(u == fa[x]) continue;

        fa[u] = x;

        dfs(u);

        if(dep[u] +  > dep[x]) dep[x] = dep[u] + ;

    }

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    std::ios::sync_with_stdio(), cin.tie();

    int n, r, x, y;

    cin >> n >> r;

    for(int i = ; i <= n; i++) cin >> a[i];

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

        cin >> x >> y;

        G[x].push_back(y);

        G[y].push_back(x);

    }

    memset(fa, , sizeof(fa));

    memset(dep, , sizeof(dep));

    fa[r] = -;

    dfs(r);

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

        Q[i][] = a[i];

        for(int j = ; j < G[i].size(); j++) {

            int u = G[i][j];

            if(u == fa[i]) continue;

            P[i][].push_back(u);

            Q[i][] = min(Q[i][], a[u]);

        }

    }

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

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

            Q[i][j] = Q[i][j - ];

            for(int k = ; k < P[i][j - ].size(); k++) {

                int u = P[i][j - ][k];

                Q[i][j] = min(Q[i][j], Q[u][j - ]);

                for(int p = ; p < P[u][j - ].size(); p++) {

                    int v = P[u][j - ][p];

                    P[i][j].push_back(v);

                }

            }

        }

    }

    int t, p, q, cur, step, ans, last = ;

    cin >> t;

    while(t--) {

        cin >> p >> q;

        //p = (p + last) % n + 1, q = (q + last) % n;

        if(q > dep[p]) q = dep[p];

        int pp = p, qq = q;

        vi[].clear(), vi[].clear();

        ans = a[p];

        cur = ;

        vi[cur].push_back(p);

        step = ;

        while(q) {

            vi[ - cur].clear();

            if(q & ) {

                for(int i = ; i < vi[cur].size(); i++) {

                    int u = vi[cur][i];

                    ans = min(ans, Q[u][step]);

                    for(int j = ; j < P[u][step].size(); j++) {

                        vi[ - cur].push_back(P[u][step][j]);

                    }

                }

                cur =  - cur;

            }

            step++;

            q >>= ;

        }

        cout << ans << endl;

        last = ans;

    }

    return ;

}

最新文章

  1. USACO翻译：USACO 2014 DEC Silver三题
  2. CentOS 7使用nmcli配置双网卡聚合
  3. java1234初学maven
  4. Java 网络爬虫获取网页源代码原理及实现
  5. JavaScript执行bat文件清理浏览器缓存
  6. 关于c#的一些笔记
  7. Buy Tickets（线段树）
  8. linux chmod命令(转）
  9. Linux 命令速查
  10. PMP考试--三点估计法
  11. assembly的说明
  12. Week12（11月25日）
  13. 初次使用Mybatis
  14. ELK 5.5.0 安装
  15. Lucene的其他搜索(三)
  16. MSSQL一种取代游标的方案
  17. JPA（六）：映射关联关系------映射单向一对多的关联关系
  18. 关于Apache (httpd)服务器防DDOS模块mod_evasive的使用说明
  19. 抽象工厂模式（ Abstract Factory )
  20. 一些常用的c++系统函数

热门文章

  1. python从TXT创建PDF文件——reportlab
  2. 重写servlet，可以获取不同的方法
  3. 使用百度fis3构建前端多页应用
  4. 2013 - lost connection to mysql server at &#39;reading initial communication packet&#39; 连接mysql报错
  5. raize5的修改。
  6. 【Codeforces 350B】Resort
  7. maven知识总结
  8. 苦酒入喉心作痛，红酒入鹅鹅想哭——震惊！勒索病毒想哭靠wine感染了Ubuntu16.04
  9. js dom元素加载完成执行
  10. [jQuery]jQuery获取URL参数