Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

Vinllen Chen


To be a better coder

Codeforces 374 Div 2解题报告

  codeforces越打越差,我都无力吐槽了,脑子真的赶不上当年了T_T。

A. One-dimensional Japanese Crossword

  题意:挨个输出连续的B的个数。
  解题:暴力即可。

B. Passwords

  题意:给定一堆密码,Vanya 忘记密码,需要不断尝试,尝试的规则是:长度小的先试,长度一样的顺序不定。求Vanya 最长和最短的尝试次数,尝试k次失败后需要暂停5秒。
  解题:暴力即可,注意边界情况的考虑。

C. Journey

  题意:给定一个有向图,给定时间约束T,每条边有个时间长度,求在给定时间内经过点的最大值。
  解题:简单的爆搜题,需要剪枝的是dist[x][node_nr] != -1 && dist[x][node_nr] <= len,表示到达x点,且经过的结点数为node_nr的距离大于之前保存的结果。然而我sb的竟然用map存储(别问我为啥,我也不知道),这题就这样被我TE了……
  代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <memory.h>
#include <map>
#include <string>
#include <cstring>
#include <stack>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <cmath>

using namespace std;

#define Clear(f, nr) memset(f, nr, sizeof(f))
typedef long long ll;  
const int INF = 1 << 30;  
const int SIZE = 5010;  
const int MSIZE = 100020;

struct Node {  
    int y;
    int len;
};
vector<Node> path[SIZE];  
vector<int> ans;  
int fa[SIZE];  
ll tot;  
ll T;  
int et;  
//map<int, ll> dist[SIZE];
ll dist[SIZE][SIZE];

void Print(int x) {  
    ans.clear();
    while (x != -1) {
        ans.push_back(x);
        x = fa[x];
    }
}

void dfs(int pre, int x, ll len, int node_nr) {  
    //cout << pre << ", " << x << ", " << len << ", " << node_nr << endl;
    if (x == et) {
        if (node_nr > tot && len <= T)  {
            tot = node_nr;
            fa[et] = pre;
            Print(et);
        }
        return ;
    }
    if (dist[x][node_nr] != -1 && dist[x][node_nr] <= len)
        return;
    dist[x][node_nr] = len;
    for (int i = 0; i < path[x].size(); i ++) {
        int now = path[x][i].y;
        fa[now] = x;
        dfs(x, now, len + path[x][i].len, node_nr + 1);
    }
}

int main() {  
    int n, m;
    int a, b, x;
    scanf("%d %d", &n, &m);
    cin >> T;
    Clear(fa, -1);
    for (int i = 0; i < m; i ++) {
        scanf("%d %d %d", &a, &b, &x);
        Node now;
        now.y = b;
        now.len = x;
        path[a].push_back(now);
    }

    Clear(dist, -1);
    tot = 0;
    et = n;
    dfs(-1, 1, 0, 1);

    printf("%lu\n", ans.size());
    for (int i = ans.size() - 1; i >= 0; i --)
        printf("%d ", ans[i]);
    puts("");
}

D. Maxim and Array

  题意:给定n个数,给定k次操作和数x,每次可以对任意一个数+x或者-x,求怎么样操作使得最后的数组乘积最少,输出最后的数组。
  解题:结果最小必然最好是负数,所以只要有奇数个负数即可,然后每次对绝对值最小的数进行操作,如果大于0则+x,小于0则-x。那么一开始不满足奇数个负数怎么办?取绝对值最小的数(正数或负数都可以),正数-x,负数则+x,也能保证最后的值最小,就算最后乘积大于0。优先队列就能搞定。
  代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <memory.h>
#include <map>
#include <string>
#include <cstring>
#include <stack>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <cmath>

using namespace std;

#define Clear(f, nr) memset(f, nr, sizeof(f))
typedef long long ll;  
const int INF = 1 << 30;  
const int SIZE = 1000;  
const int MSIZE = 200020;

ll a[MSIZE];

struct Node {  
    ll x;
    int id;
    bool operator<(const Node &p) const {
        return abs(x) > abs(p.x);
    }
};

int main() {  
    int n, k, x;
    ll val;
    priority_queue<Node> q;
    while (cin >> n >> k >> x) {
        while (!q.empty())
            q.pop();
        bool flag = 0;
        for (int i = 0; i < n; i ++) {
            cin >> val;
            if (val < 0)
                flag = !flag;
            Node now;
            now.x = val;
            now.id = i;
            q.push(now);
        }
        while (k --) {
            Node top = q.top();
            //cout << top.x << endl;
            q.pop();
            if (top.x >= 0) {
                if (!flag) {
                    top.x -= x;
                    if (top.x < 0)
                        flag = !flag;
                }
                else {
                    top.x += x;
                }
            }
            else {
                if (!flag) {
                    top.x += x;
                    if (top.x >= 0)
                        flag = !flag;
                }
                else
                    top.x -= x;
            }
            q.push(top);
        }

        while (!q.empty()) {
            Node top = q.top();
            q.pop();
            a[top.id] = top.x;
        }
        for (int i = 0; i < n; i ++)
            cout << a[i] << " ";
        cout << endl;
    }
}

Reference

http://codeforces.com/contest/721


About the author

vinllen chen

Beijing, China

格物致知


Discussions

comments powered by Disqus