A. World Football Cup

#include <bits/stdc++.h>

using namespace std;

 

const int N = ;

char name[N][N];

map<string, int> mp;

char s[N];

 

struct P {

    int id, point;

    int dif, goal;

    bool operator < (const P &rhs) const {

        if (point == rhs.point && goal - dif == rhs.goal - rhs.dif) return goal > rhs.goal;

        if (point == rhs.point) return goal - dif > rhs.goal - rhs.dif;

        return point > rhs.point;

    }

} p[N];

 

int main() {

    int n;

    scanf("%d", &n);

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

        scanf("%s", name[i]);

        mp[name[i]] = i;

        p[i].id = i;

    }

    for (int i = ; i < n * (n - ) / ; i++) {

        int pp, qq;

        scanf("%s%d:%d", s, &pp, &qq);

        int j = ;

        int len = strlen(s);

        char s1[] = {};

        char s2[] = {};

        int p1 = , p2 = ;

        for (; s[j] != '-'; j++) s1[p1++] = s[j];

        j++;

        for (; j < len; j++) s2[p2++] = s[j];

        int a = mp[s1], b = mp[s2];

        p[a].goal += pp, p[b].goal += qq;

        p[a].dif += qq; p[b].dif += pp;

        if (pp > qq) p[a].point += ;

        else if (pp == qq) p[a].point++, p[b].point++;

        else p[b].point += ;

    }

    sort(p, p + n);

    vector<string> ans;

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

        ans.push_back(name[p[i].id]);

    sort(ans.begin(), ans.end());

    for (auto x: ans)

        cout << x << '\n';

    return ;

}

B. Checkout Assistant

有$n$个商品，每个商品价格$c_i$，售货员处理这件商品需要时间$t_i$，偷走一个商品需要$1$个单位时间，问怎么安排这些商品的结账顺序可以使的最后要还的钱最少。

如果让一件商品去结账，相当于花$c_i$块钱，能偷走买走至多$t_i + 1$个商品，要使最后总花费最小，那么就是01背包了。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

 

const int N = ;

ll dp[N];

int w[N];

ll c[N];

 

int main() {

    memset(dp, 0x3f, sizeof dp);

    dp[] = ;

    int n;

    scanf("%d", &n);

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

        scanf("%d%lld", &w[i], &c[i]), w[i]++;

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

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

            dp[j] = min(dp[j], dp[max(j - w[i], )] + c[i]);

        }

    }

    printf("%lld\n", dp[n]);

    return ;

}

C. Deletion of Repeats

有一个序列，每种元素至多出现$10$次，如果有一个子串前一半等于后一半，那么把前一半及以前的字符全部删掉，要求从短的以及较左的地方开始删，问最后这个串长什么样。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + ;

int a[N], v[N];

vector<int> G[N];

int main() {

    int n;

    scanf("%d", &n);

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

        scanf("%d", &a[i]);

        v[i] = a[i];

    }

    sort(v + , v +  + n);

    int cnt = unique(v + , v +  + n) - v - ;

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

        a[i] = lower_bound(v + , v +  + cnt, a[i]) - v;

        G[a[i]].push_back(i);

    }

    int now = ;

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

        bool flag = ;

        for (auto pos: G[a[i]]) {

            flag = ;

            if (pos >= i) continue;

            if (n - i +  < i - pos) continue;

            if (pos <= now) continue;

            flag = ;

            for (int j = ; j < i - pos; j++) {

                if (a[i + j] != a[pos + j]) {

                    flag = ;

                    break;

                }

            }

            if (!flag) break;

        }

        if (!flag) now = i - ;

    }

    printf("%d\n", n - now);

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

        printf("%d%c", v[a[i]], " \n"[i == n]);

    return ;

}

D. Points

一个二维坐标系，有三个操作。

1.加点

2.删点

3.查询严格在$(x, y)$右上角的点，输出$x$坐标最小的那个点，如果有相同的，则输出$y$最小的，不存在输出$-1$

因为存在修改操作，那么就不能离线做了，用线段树维护$x$坐标下$y$坐标的最大值，然后就变成了查询$\left[x + 1, inf\right]$中最小的$x$其$y$大于要查询的$y$，那么就又是先查左及剪枝的那个写法了。然后找到对应$x$坐标后，加点删点用一个set维护每个$x$坐标出现过$y$的坐标，在这个set里面lower_bound一下就好了，刚开始都插入0以及所有$y$坐标都加个一会好操作很多。

#include <bits/stdc++.h>

using namespace std;

 

const int N = 5e5 + ;

 

struct Seg {

    #define lp p << 1

    #define rp p << 1 | 1

    int mx[N << ];

    void pushup(int p) {

        mx[p] = max(mx[lp], mx[rp]);

    }

    void update(int p, int l, int r, int x, int val) {

        if (l == r) {

            mx[p] = max(val, mx[p]);

            return;

        }

        int mid = l + r >> ;

        if (x <= mid) update(lp, l, mid, x, val);

        else update(rp, mid + , r, x, val);

        pushup(p);

    }

    void change(int p, int l, int r, int x, int val) {

        if (l == r) {

            mx[p] = val;

            return;

        }

        int mid = l + r >> ;

        if (x <= mid) change(lp, l, mid, x, val);

        else change(rp, mid + , r, x, val);

        pushup(p);

    }

    int query(int p, int l, int r, int x, int y, int val) {

        if (x > y) return -;

        if (mx[p] <= val) return -;

        if (l == r) return l;

        int mid = l + r >> ;

        if (x <= mid) {

            int temp = query(lp, l, mid, x, y, val);

            if (temp != -) return temp;

        }

        return query(rp, mid + , r, x, y, val);

    }

} seg;

 

struct OPT {

    int opt;

    int x, y;

} o[N];

int v[N];

set<int> st[N];

 

int main() {

//    freopen("in.txt", "r", stdin);

    int n;

    scanf("%d", &n);

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

        char s[] = {};

        scanf("%s%d%d", s, &o[i].x, &o[i].y);

        if (s[] == 'a') o[i].opt = ;

        else if (s[] == 'r') o[i].opt = ;

        else o[i].opt = ;

        v[i] = o[i].x;

        o[i].y++;

    }

    sort(v + , v +  + n);

    int cnt = unique(v + , v +  + n) - v - ;

    for (int i = ; i <= cnt; i++) st[i].insert();

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

        o[i].x = lower_bound(v + , v +  + cnt, o[i].x) - v;

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

        if (o[i].opt == ) {

            st[o[i].x].insert(o[i].y);

            seg.update(, , cnt, o[i].x, o[i].y);

        } else if (o[i].opt == ) {

            st[o[i].x].erase(o[i].y);

            set<int>::iterator it = st[o[i].x].end();

            it--;

            int res = ;

            res = *it;

            seg.change(, , cnt, o[i].x, res);

        } else {

            int pos = seg.query(, , cnt, o[i].x + , cnt, o[i].y);

            if (pos == -) printf("-1\n");

            else {

                int ans = *st[pos].upper_bound(o[i].y);

                printf("%d %d\n", v[pos], ans - );

            }

        }

    }

    return ;

}

E. Fairy

一个图为二分图的充要条件就是不存在奇环。
先求出一个dfs树，然后考虑非树边对dfs树的影响。
有几种情况需要考虑。
一、不存在自环及奇环
都可以删。
二、自环
如果存在两个自环及以上，就不可能了，因为它只能删除一条边。
有一个自环，当不存在奇环的时候就只能删除这个自环，否则也没边可删了。
三、存在一个奇环
那么这个奇环上的树边及非树边都可以删。也只有这种情况能删非树边。
四、存在多个奇环
那么能删除的边就是这些奇环的树边的交集。同时，这个交集的边不能出现在偶环上，否则奇环+偶环还是会得到奇环。
那么树上差分一下得到每条边在多少个奇环上，如果在偶环上就把路径减一下，就能处理出不能在偶环上的情况。最后就判断一下每一条边的值是否为奇环的个数。

#include <bits/stdc++.h>

namespace IO {

    void read() {}

    template<class T, class... T2>

    void read(T &x, T2 &... oth) {

        x = ; T f = ; char ch = getchar();

        while (!isdigit(ch)) { if (ch == '-') f = -; ch = getchar(); }

        while (isdigit(ch)) x = x *  + ch - '', ch = getchar();

        x *= f;

        read(oth...);

    }

}

const int N = 1e6 + ;

struct E {

    int v, ne, id;

} e[N << ];

int head[N], tag[N], dep[N], cnt = ;

bool vis[N];

int self, n, m;

void add(int u, int v, int id) {

    e[++cnt].v = v; e[cnt].ne = head[u]; e[cnt].id = id; head[u] = cnt;

    e[++cnt].v = u; e[cnt].ne = head[v]; e[cnt].id = id; head[v] = cnt;

}

int tol, fei;

void dfs(int u, int f) {

    for (int i = head[u]; i; i = e[i].ne) {

        if (i == (f ^ )) continue;

        int v = e[i].v;

        if (dep[v]) {

            if (dep[v] > dep[u]) continue;

            if ((dep[u] - dep[v] + ) & ) {

                tol++;

                fei = e[i].id;

                tag[u]++; tag[v]--;

            } else {

                tag[u]--; tag[v]++;

            }

        } else {

            dep[v] = dep[u] + ;

            dfs(v, i);

            tag[u] += tag[v];

        }

    }

}

std::vector<int> vec;

void dfs(int u) {

    vis[u] = ;

    for (int i = head[u]; i; i = e[i].ne) {

        int v = e[i].v;

        if (vis[v]) continue;

        if (tag[v] == tol)

            vec.push_back(e[i].id);

        dfs(v);

    }

}

int main() {

    IO::read(n, m);

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

        int u, v;

        IO::read(u, v);

        if (u == v && !self) {

            self = i;

            continue;

        }

        if (u == v) {

            self = -;

            continue;

        }

        add(u, v, i);

    }

    if (self == -) {

        puts("");

        return ;

    }

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

        if (!dep[i])

            dep[i] = , dfs(i, );

    }

    if (tol == ) {

        if (self) {

            printf("1\n%d\n", self);

        } else {

            printf("%d\n", m);

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

                printf("%d%c", i, " \n"[i == m]);

        }

        return ;

    }

    if (self) {

        puts("");

        return ;

    }

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

        if (!vis[i])

            dfs(i);

    if (tol == )

        vec.push_back(fei);

    printf("%d\n", (int)vec.size());

    std::sort(vec.begin(), vec.end());

    for (int i = ; i < vec.size(); i++)

        printf("%d%c", vec[i], " \n"[i +  == vec.size()]);

    return ;

}

最新文章

  1. CentOS 7.0，启用iptables防火墙
  2. spark 特殊函数
  3. Outlook2003收到的邮件不能显示图片，但转发或回复可以 故障排错
  4. Water --- CSU 1550: Simple String
  5. Java学习-004-传世经典Helloworld
  6. 新发布GoldenGate 12c版本中的主要特性
  7. 第二百八十八天 how can I坚持
  8. Linux下U盘的格式化
  9. jqPlot，一个 jQuery这个 JavaScript 框架的绘图插件
  10. 使用gzip优化web应用(filter实现)
  11. linux的链接工具secure设置字体大小和颜色
  12. 计科1702冯亚杰C语言程序设计预备作业
  13. vi显示中文乱码
  14. Windows和Mac浏览器启动本地程序
  15. 【Codeforces Round 1132】Educational Round 61
  16. Ionic 动态配置url路由的设置
  17. Python 安装 OpenCV 遇到的问题
  18. HDU4662(SummerTrainingDay03-B)
  19. 看懂Oracle执行计划、表连接方式
  20. JAVA 操作Excel工具类

热门文章

  1. Spring 源码分析之AbstractApplicationContext源码分析
  2. eclipse打开本地文件所在目录位置的快捷键
  3. 解决mac/win双系统，mac原生读写NTFS分区重启后失效的问题
  4. MySQL使用现状分析与优化
  5. 手写LRU实现
  6. 查看索引在哪些ES集群节点上的命令
  7. 浅谈Vue.js2.0核心思想
  8. QGraphicsItem鼠标旋转控制研究
  9. How to prove that SAP CRM WebUI is a stateful application
  10. LabWindows/CVI第一章：基本规则