@Dmaxiya 2018-08-17T10:27:35.000000Z 字数 7584 阅读 990

Codeforces Round #346 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #346 (Div. 2)
过题数：5
排名：614/15230

A. Round House

题意

有 $n$ 个围成圈的入口，入口 $1$ 和入口 $n$ 相邻， $Vasya$ 最开始在入口 $a$ ，他将移动 $|b|$ 步，如果 $b>0$ ，则 $Vasya$ 从数字小到大的方向移动，若 $b<0$ ，则他从数字从大到小的方向移动，问最终 $Vasya$ 的位置。

数据范围

$1\leq n\leq100,1\leq a\leq n,-100\leq b\leq100$

题解

直接求 $a+b$ 对应在 $n$ 个入口的位置就是答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n, a, b;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &a, &b) != EOF) {
        int ans = ((a + b) % n + n) % n;
        if(ans == 0) {
            printf("%d\n", n);
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

B. Qualifying Contest

题意

有 $n$ 个选手参加 $m$ 个地区的比赛，每个地区将会对每个选手的分数进行排名，并选出每个地区的第一名和第二名，如果由于分数相同而无法确定某个地区的第 $1、2$ 名，则输出问号，否则输出前两名选手的名字。

数据范围

$2\leq n\leq10^5,1\leq m\leq10^4,n\geq2m$

题解

对每个地区开一个 $vector$ 按题意模拟排序，若比赛人数只有 $2$ 人，则直接输出两人的名字，否则判断第二名和第三名的成绩是否相等，来判断能否决定出前两名。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 10000 + 100;
struct Node {
    string name;
    int score;
};
bool operator<(const Node &a, const Node &b) {
    return a.score > b.score;
}
int n, m, t;
Node node;
vector<Node> G[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(cin >> n >> m) {
        for(int i = 1; i <= m; ++i) {
            G[i].clear();
        }
        for(int i = 0; i < n; ++i) {
            cin >> node.name >> t >> node.score;
            G[t].push_back(node);
        }
        for(int i = 1; i <= m; ++i) {
            sort(G[i].begin(), G[i].end());
        }
        for(int i = 1; i <= m; ++i) {
            if(G[i].size() <= 2) {
                cout << G[i][0].name << " " << G[i][1].name << endl;
                continue;
            }
            if(G[i][1].score == G[i][2].score) {
                cout << "?" << endl;
            } else {
                cout << G[i][0].name << " " << G[i][1].name << endl;
            }
        }
    }
    return 0;
}

C. Tanya and Toys

题意

最近 $Berland$ 掀起了一股新的玩具收集热，总共有 $10^9$ 种玩具，编号为 $1-10^9$ ，编号为 $i$ 的玩具价值为 $i$ 元， $Tania$ 已经有 $n$ 种不同的玩具，玩具种类分别为 $a_1,a_2\cdots a_n$ ，她还想要更多种类的玩具，她妈妈给了她 $m$ 元，问她要收集到最多的不同的玩具种类，应该买哪些玩具，输出买玩具的方案。

数据范围

$1\leq n\leq10^5,1\leq m\leq10^9\\1\leq a_i\leq10^9$

题解

贪心按照从价格最小的开始买。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, m;
int num;
set<int> st;
int ans[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        st.clear();
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num);
            st.insert(num);
        }
        int Index = 0;
        int cnt = 1;
        while(m >= cnt) {
            if(st.find(cnt) == st.end()) {
                m -= cnt;
                ans[Index++] = cnt;
            }
            ++cnt;
        }
        printf("%d\n", Index);
        for(int i = 0; i < Index; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

D. Bicycle Race

题意

$Maria$ 参加了一个环湖自行车比赛，比赛路线上有 $n$ 个转折点，每个转折点都用一个平面直角坐标系上的点 $(x_i,y_i)$ 表示，这些点将从起点按照顺时针的顺序给出，两个转折点之间的路线都是直线， $Maria$ 是个新手，她每骑到一个转折点，如果在这个转折点直行会掉到湖里，她就有可能存在危险，问这个赛道上有多少个转折点对她来说可能是危险的。数据保证是一条合法的赛道。

数据范围

$4\leq n\leq1000\\-10^4\leq x_i,y_i\leq10^4$

题解

用向量叉积判断下一条路线是是否是往左转的，如果是，则答案 $+1$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
LL n, x, y, dx, dy, lastx, lasty;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%I64d", &n) != EOF) {
        scanf("%I64d%I64d", &lastx, &lasty);
        scanf("%I64d%I64d", &dx, &dy);
        int ans = 0;
        for(int i = 2; i <= n; ++i) {
            scanf("%I64d%I64d", &x, &y);
            LL xx1 = dx - lastx;
            LL yy1 = dy - lasty;
            LL xx2 = x - dx;
            LL yy2 = y - dy;
            if(xx1 * yy2 - xx2 * yy1 > 0) {
                ++ans;
            }
            lastx = dx;
            lasty = dy;
            dx = x;
            dy = y;
        }
        printf("%d\n", ans);
    }
    return 0;
}

E. New Reform

题意

给一个 $n$ 个节点 $m$ 条边的无向图，无向图不保证连通，现在要将所有边都变成有向边，要使入度为 $0$ 的点个数最少，输出最少的入度为 $0$ 的点的个数。

数据范围

$2\leq n\leq10^5,1\leq m\leq10^5$

题解

画几组数据就可以发现，如果一个连通块内存在环，就可以将这个环的所有边变成顺时针旋转的有向图，将与这个环相连的所有边，都转化为从这个环上的点出发的边，这样这个连通块上的所有的点入度就都不为 $0$ 了，而对于一条链的情况，有向边可以从链的一头指向另一头，这样这条链上入度为 $0$ 的点就只有一个。所以这题要做的就是用并查集判断图上链的数量。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, m, u, v, ans;
int num[maxn], fa[maxn], sum[maxn];
bool vis[maxn];
void Init() {
    for(int i = 1; i <= n; ++i) {
        fa[i] = i;
        num[i] = sum[i] = 1;
        vis[i] = false;
    }
}
int Find(int x) {
    return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    if(xx != yy) {
        fa[xx] = yy;
        sum[yy] += sum[xx];
    }
    num[yy] += num[xx];
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        ans = 0;
        Init();
        for(int i = 0; i < m; ++i) {
            scanf("%d%d", &u, &v);
            unit(u, v);
        }
        for(int i = 1; i <= n; ++i) {
            int f = Find(i);
            if(!vis[f]) {
                vis[f] = true;
                if(num[f] == sum[f]) {
                    ++ans;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

F. Polycarp and Hay

题意

在一个 $n\times m$ 的仓库里，每个位置上都有一个高度为 $a_{i,j}$ 的草垛，如果 $a_{i,j}=0$ ，则说明那个位置没有草垛，现在 $Polycarp$ 想要搬走一些草垛，使得所有的草垛满足以下条件：

所有草垛的高度和为 $k$ ；

除了高度为 $0$ 的草垛，其他草垛的高度都应该相等；

至少要有一个高度非零的草垛，保留原来的高度；

所有剩下的草垛都应该相互连通。

数据范围

$1\leq n,m\leq1000,1\leq k\leq10^{18}\\1\leq a_{i,j}\leq10^9$

题解

枚举所有非零的草垛高度 $h$ ，在满足 $k\%h=0$ 的条件下， $bfs$ 判所有高度大于等于 $h$ 的草垛是否相互连通。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
struct Node {
    int x, y;
    LL num;
    Node() {}
    Node(int xx, int yy, LL n) {
        x = xx;
        y = yy;
        num = n;
    }
};
bool operator<(const Node &a, const Node &b) {
    return a.num < b.num;
}
int n, m, cnt, ansx, ansy;
LL k;
LL num[maxn][maxn];
Node node[maxn * maxn];
Node *it;
bool vis[maxn][maxn];
queue<Node> que;
const int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
bool bfs(int x, int y, int cnt) {
    vis[x][y] = true;
    --cnt;
    if(cnt == 0) {
        return true;
    }
    while(!que.empty()) {
        que.pop();
    }
    que.push(Node(x, y, 0));
    while(!que.empty()) {
        Node tmp = que.front();
        que.pop();
        for(int i = 0; i < 4; ++i) {
            int xx = tmp.x + dir[i][0];
            int yy = tmp.y + dir[i][1];
            if(in(xx, yy) && !vis[xx][yy] && num[xx][yy] >= num[x][y]) {
                --cnt;
                vis[xx][yy] = true;
                que.push(Node(xx, yy, 0));
            }
            if(cnt == 0) {
                return true;
            }
        }
    }
    return false;
}
bool Check(int x, int y) {
    memset(vis, 0, sizeof(vis));
    int cnt = k / num[x][y];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(num[i][j] == num[x][y] && !vis[i][j]) {
                if(bfs(i, j, cnt)) {
                    ansx = i;
                    ansy = j;
                    return true;
                }
            }
        }
    }
    return false;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%I64d", &n, &m, &k) != EOF) {
        cnt = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                scanf("%I64d", &num[i][j]);
                node[cnt++] = Node(i, j, num[i][j]);
            }
        }
        bool flag = false;
        sort(node, node + cnt);
        it = node;
        while(it != node + cnt) {
            if(k % it->num == 0 && it->num * (cnt - (it - node)) >= k) {
                if(Check(it->x, it->y)) {
                    flag = true;
                    break;
                }
            }
            it = upper_bound(node, node + cnt, *it);
        }
        if(flag) {
            printf("YES\n");
            memset(vis, 0, sizeof(vis));
            bfs(ansx, ansy, k / num[ansx][ansy]);
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < m; ++j) {
                    if(j != 0) {
                        printf(" ");
                    }
                    if(vis[i][j]) {
                        printf("%I64d", num[ansx][ansy]);
                    } else {
                        printf("0");
                    }
                }
                printf("\n");
            }
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

Codeforces Round #346 (Div. 2)

A. Round House

题意

数据范围

题解

过题代码

B. Qualifying Contest

题意

数据范围

题解

过题代码

C. Tanya and Toys

题意

数据范围

题解

过题代码

D. Bicycle Race

题意

数据范围

题解

过题代码

E. New Reform

题意

数据范围

题解

过题代码

F. Polycarp and Hay

题意

数据范围

题解

过题代码

内容目录