首页 > 其他 > 详细

Codechef October Challenge 2019 Div.2

时间：2019-11-14 12:22:59      阅读：58      评论：0      收藏：0      [点我收藏+]

比赛传送门

CodeChef = ccf

S10E

水题，直接模拟即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();  
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int a[100010];
int main() {
    int t = read();
    while(t--) {
        int n = read(), ans = 0;
        for(int i = 1; i <= n; ++i) {
            a[i] = read();
            int minn = 2147483647;
            for(int j = max(i-5, 1); j <= i-1; ++j)
                minn = min(minn, a[j]);
            if(minn > a[i]) ++ans;
        }
        printf("%d\n", ans);
    }

    return 0;
}

SAKTAN

行和列分开处理，因为奇数+偶数=奇数，所以分别求出加了偶数次的行\(ea\)和列\(eb\)，加了奇数次的行\(oa\)和列\(ob\)最后答案就是\(oa\times eb + ea \times ob\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();  
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int a[100010], b[100010];
int main() {
    int t = read();
    while(t--) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        int n = read(), m = read(), q = read();
        for(int i = 1; i <= q; ++i) {
            int x = read(), y = read();
            ++a[x], ++b[y];
        }
        LL oa = 0, ob = 0, ea = 0, eb = 0;
        for(int i = 1; i <= n; ++i)
            if(a[i] & 1) ++oa;
            else ++ea;
        for(int i = 1; i <= m; ++i)
            if(b[i] & 1) ++ob;
            else ++eb;
        LL ans = ob * ea + oa * eb;
        printf("%lld\n", ans);
    }

    return 0;
}

MARM

每\(3n\)次操作是一个循环。但如果\(n\)是奇数，需特判最中间的数，当\(k \geq (n+1)/2\)时，最中间的数恒为\(0\)
不要忘记开long long！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
LL a[10010];
int main() {
    int t = read();
    while(t--) {
        LL n = read(), k = read();
        for(int i = 0; i < n; ++i) a[i] = read();

        LL flag = 0;
        if(k >= n/2ll+1ll) flag = 1;
        k = k % (3ll * n);
        
        for(LL i = 0; i <= k-1; ++i)
            a[i%n] ^= a[n-(i%n)-1ll];

        for(LL i = 0; i < n; ++i) {
            if((n & 1ll) && (i == n/2ll) && flag)
                printf("0 ");
            else printf("%lld ", a[i]);
        }
        printf("\n");
    }

    return 0;
}

MSV

对每个数暴力分解因数，然后用桶记录每个因数出现了几次

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int tong[1000010], ans = 0;
int main() {
    int t = read();
    while(t--) {
        int n = read(); ans = 0;
        memset(tong, 0, sizeof(tong));
        for(int i = 1; i <= n; ++i) {
            int x = read();
            ans = max(tong[x], ans);
            ++tong[1]; ++tong[x];
            for(int j = 2; j * j <= x; ++j) {
                if(x % j == 0) {
                    ++tong[j];
                    if(x/j != j) ++tong[x/j];
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

EVEDG

  1. 如果图的边数为偶数，则将所有点都划分到一个集合里即可
  2. 如果为边数为奇数
    1. 如果图中有一个点的度数为奇数，将这个点单独划为一个集合，其他点为另一个集合
    2. 如果所有点的度数都为偶数，先将一个有出度的点划为一个集合，然后就会变成上面的情况，即有至少一个点的度数会变成奇数。此情况需要三个集合
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int du[100010];
struct zzz {
    int t, nex;
}e[100010 << 1]; int head[100010], tot;
inline void add(int x, int y) {
    e[++tot].t = y;
    e[tot].nex = head[x];
    head[x] = tot;
}
int main() {
    int t = read();
    while(t--) {
        int n = read(), m = read(); tot = 0;
        for(int i = 1; i <= n; ++i) du[i] = 0, head[i] = 0;
        for(int i = 1; i <= m; ++i) {
            int x = read(), y = read();
            ++du[x], ++du[y];
            add(x, y); add(y, x);
        }
        if(!(m & 1)) {
            printf("1\n");
            for(int i = 1; i <= n; ++i)
                printf("1 ");
        }
        else {
            bool flag = 0;
            for(int i = 1; i <= n; ++i)
                if(du[i] & 1) flag = 1;
            if(flag) {
                flag = 0;
                printf("2\n");
                for(int i = 1; i <= n; ++i)
                    if((du[i] & 1) && flag == 0) printf("2 "), flag = 1;
                    else printf("1 ");  
            }
            else {
                int pos = 0;
                for(int x = 1; x <= n; ++x)
                    if(du[x]) {
                        for(int i = head[x]; i; i = e[i].nex) --du[e[i].t];
                        pos = x; break;
                    }
                printf("3\n");
                for(int i = 1; i <= n; ++i)
                    if(i == pos) printf("3 ");
                    else if((du[i] & 1) && flag == 0) printf("2 "), flag = 1;
                    else printf("1 ");
            }
        }
        printf("\n");
    }
    return 0;
}

MSNG

直接暴力模拟就好了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
#define lim 1000000000000ll
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
struct zzz {
    int len, maxx; LL opt, a[51];
}x[110];
int n;
bool judge(LL k) {
    if(k > lim) return 0;
    for(int i = 2; i <= n; ++i) {
        bool flag = 0;
        for(LL j = x[i].maxx; j <= 36; ++j) {
            LL a = 0;
            for(int o = 1; o <= x[i].len; ++o) {
                a = a * j + x[i].a[o];
                if(a > lim) return 0;
            }
            if(a == k) {
                flag = 1; break;
            }
        }
        if(!flag) return 0;
    }
    return 1;
}
int main() {
    int t = read();
    while(t--) {
        n = read();
        memset(x, 0, sizeof(x));
        for(int i = 1; i <= n; ++i) {
            x[i].opt = read();
            char s[51]; scanf("%s", s+1);
            int len = strlen(s+1);
            x[i].len = len;
            for(int j = 1; j <= len; ++j) {
                if(s[j] >= '0' && s[j] <= '9')
                    x[i].a[j] = s[j] - '0';
                else x[i].a[j] = s[j] - 'A' + 10;
                x[i].maxx = max((LL)x[i].maxx, x[i].a[j] + 1);
            }
        }
        for(int i = 2; i <= n; ++i) {
            if(x[1].opt != -1) break;
            if(x[i].opt != -1) {
                swap(x[1], x[i]);
                break;
            }
            if(x[i].maxx > x[1].maxx) swap(x[1], x[i]);
            else if(x[i].maxx == x[1].maxx && x[i].len > x[1].len) swap(x[1], x[i]);
            else if(x[i].maxx == x[1].maxx && x[i].len == x[1].len) {
                for(int j = 1; j <= x[i].len; ++j)
                    if(x[i].a[j] > x[1].a[j]) {
                        swap(x[1], x[i]); break;
                    }
            }
        }
        
        LL k = 0;
        if(x[1].opt != -1) {
            for(int i = 1; i <= x[1].len; ++i) {
                k = k * x[1].opt + x[1].a[i];
                if(k > lim) break;
            }
            if(!judge(k)) printf("-1\n");
            else printf("%lld\n", k);
        }
        else {
            bool flag = 0;
            for(LL o = x[1].maxx; o <= 36; ++o) {
                k = 0;
                for(int i = 1; i <= x[1].len; ++i) {
                    k = k * o + x[1].a[i];
                    if(k > lim) break;
                }
                //cout << k << endl;
                if(judge(k)) {
                    printf("%lld\n", k); flag = 1;
                    break;
                }
            }
            if(!flag) printf("-1\n");
        }
    }
    return 0;
}

BACREP

每过一秒，点权会下移。设点\(x\)的深度为\(deth_x\)，一个修改操作的时间是\(t\)，被修改的点\(i\)的深度为点\(deth_i\)，当前时间是\(T\)，只有当\(deth_x - T = deth_i - t\)、且\(x\)为\(i\)的后代时时，点\(x\)才会受这次修改影响。叶子节点需要特殊处理，它会受到所有\(deth_x - T \leq deth_i - t\)的修改的影响
考虑如何用线段树来维护\(deth_x - T\)
将操作离线，然后进行\(dfs\)，对每个节点\(x\)，枚举和它有关的所有操作，设该操作进行的时间为\(t\)。如果为修改，就在\(deth_x - t\)的位置加上修改的值\(k\)。如果是非叶子结点的询问，直接查询\(deth_x - t\)。如果是叶子节点的询问，则查询区间\([deth_x-t,MAXN]\)
在回溯时要将所有的修改操作撤回，防止对其他子树造成影响

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define LL long long
#define ls p << 1
#define rs p << 1 | 1
#define mid ((l+r) >> 1)
#define eps 500005
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
char read_c() {
    char c = getchar();
    while(c != '?' && c != '+') c = getchar();
    return c;
}
struct zzz {
    int t, nex;
}e[500010 << 1]; int head[500010], tot;
struct hhh {
    bool opt; LL k, tim;
};
vector <hhh> que[500010];
inline void add(int x, int y) {
    e[++tot].t = y;
    e[tot].nex = head[x];
    head[x] = tot;
}
bool leaf[500010];
int f[500010], deth[500010];
LL v[500010], tree[1000020 << 2];
void dfs(int x, int fa) {
    f[x] = fa, deth[x] = deth[fa] + 1; leaf[x] = 1;
    for(int i = head[x]; i; i = e[i].nex) {
        if(e[i].t != fa) dfs(e[i].t, x);
        else continue;
        leaf[x] = 0;
    }
}
inline void up(int p) {
    tree[p] = tree[ls] + tree[rs];
}
LL query(int pos, int l = 1, int r = 1000010, int p = 1) {
    if(l == r) return tree[p];
    if(pos <= mid) return query(pos, l, mid, ls);
    else return query(pos, mid+1, r, rs);
}
LL sum(int nl, int nr, int l = 1, int r = 1000010, int p = 1) {
    if(l >= nl && r <= nr) return tree[p];
    LL anss = 0;
    if(nl <= mid) anss += sum(nl, nr, l, mid, ls);
    if(nr > mid) anss += sum(nl, nr, mid+1, r, rs);
    return anss;
}
void update(int pos, LL k, int l = 1, int r = 1000010, int p = 1) {
    if(l == r) {
        tree[p] += k; return ;
    }
    if(pos <= mid) update(pos, k, l, mid, ls);
    else update(pos, k, mid+1, r, rs);
    up(p);
}
LL ans[500010]; bool vis[500010];
void dfs2(int x, int fa) {
    int len = que[x].size();
    update(deth[x] + eps, v[x]);
    for(int i = 0; i < len; ++i) {
        hhh a = que[x][i];
        if(a.opt == 1) {
            int pos = deth[x] - a.tim + eps;
            update(pos, a.k);
        }
        else {
            vis[a.tim] = 1;
            if(!leaf[x])
                ans[a.tim] = query(deth[x] - a.tim + eps);
            else {
                ans[a.tim] = sum(deth[x] - a.tim + eps, 1000010);
            }
        }
    }
    
    for(int i = head[x]; i; i = e[i].nex)
        if(e[i].t != fa) dfs2(e[i].t, x);
        
    update(deth[x] + eps, -v[x]);
    for(int i = 0; i < len; ++i) {
        hhh a = que[x][i];
        if(a.opt == 1) {
            int pos = deth[x] - a.tim + eps;
            update(pos, -a.k);
        }
    }
}
int main() {
    int n = read(), q = read();
    for(int i = 1; i <= n-1; ++i) {
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    for(int i = 1; i <= n; ++i) v[i] = read();
    dfs(1, 0);
    
    for(int i = 1; i <= q; ++i) {
        char opt = read_c();
        int x = read();
        if(opt == '+') que[x].push_back((hhh){1, read(), i});
        else que[x].push_back((hhh){0, -1, i});
    }
    dfs2(1, 0);
    for(int i = 1; i <= q; ++i)
        if(vis[i]) printf("%lld\n", ans[i]);
        
    return 0;
}

MAXLIS

真不会，乱搞只搞到了\(4.4\)分……

Codechef October Challenge 2019 Div.2

原文：https://www.cnblogs.com/morslin/p/11855857.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！