QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#789899#9621. 连方yuhaoweiAC ✓9ms4280kbC++206.6kb2024-11-27 22:35:062024-11-27 22:35:06

Judging History

你现在查看的是最新测评结果

  • [2024-11-27 22:35:06]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:4280kb
  • [2024-11-27 22:35:06]
  • 提交

answer

#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
#include<string.h>
#include<cstring>
#include <string>
#include<unordered_map>
#include <set>
#include<numeric>
#include<queue>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
#include<assert.h>
#include<climits>
#include <map>
#include <random>
#include <bitset>
#include <chrono>
#include <limits>
#include<fstream>

using ll = long long;
using i64 = long long;

/**   最大流(MaxFlow 新版)
 *    2023-07-21: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62915815
**/

constexpr int inf = 1E9;
template<class T>
struct MaxFlow {
    //边结构体
    struct _Edge {
        int to;//
        T cap;
        _Edge(int to, T cap) : to(to), cap(cap) {}
    };

    int n;
    std::vector<_Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;

    MaxFlow() {}
    MaxFlow(int n) {
        init(n);
    }
    //初始化
    void init(int n) {
        this->n = n;
        e.clear();
        g.assign(n, {});
        cur.resize(n);
        h.resize(n);
    }
    //对点分层,找增广路,找一条增广路
    bool bfs(int s, int t) {//给定起点和终点
        h.assign(n, -1);//分配n个空间,每个空间初始化为-1
        std::queue<int> que;
        h[s] = 0;//起点为0
        que.push(s);//放入起点
        while (!que.empty()) {
            const int u = que.front();//拿到点
            que.pop();
            for (int i : g[u]) {//遍历它的下一层
                int v = e[i].to;//拿到下一个点和该边的容量
                auto c = e[i].cap;
                if (c > 0 && h[v] == -1) {//如果容量大于0且该点没有被重复走过
                    h[v] = h[u] + 1;//走过的第几个点
                    if (v == t) {//如果走到了终点就返回true
                        return true;
                    }
                    que.push(v);//否则将这个点放到队列中继续往下找
                }
            }
        }
        //如果最终都没有找到终点,这说明没有合法的增广路,则返回false
        return false;
    }
    //多路增广
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        auto r = f;//
        for (int& i = cur[u]; i < int(g[u].size()); ++i) {
            const int j = g[u][i];
            int v = e[j].to;//拿到下一个点和该边的容量
            auto c = e[j].cap;
            //
            if (c > 0 && h[v] == h[u] + 1) {
                auto a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) {
                    return f;
                }
            }
        }
        return f - r;
    }
    //添边
    //起点,终点,容量
    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());//点u的下一条边在e的哪个位置记录着
        e.emplace_back(v, c);//往后放
        g[v].push_back(e.size());//
        e.emplace_back(u, 0);//往回连一条边,容量为0,用来构建残留网
    }
    //dinic算法.累加可行流
    T flow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {//首先看有没有合法的增广路
            cur.assign(n, 0);
            //传入起点和终点和数据t的最大值
            ans += dfs(s, t, std::numeric_limits<T>::max());//
        }
        return ans;
    }

    std::vector<bool> minCut() {
        std::vector<bool> c(n);
        for (int i = 0; i < n; i++) {
            c[i] = (h[i] != -1);
        }
        return c;
    }

    struct Edge {
        int from;
        int to;
        T cap;
        T flow;
    };
    std::vector<Edge> edges() {
        std::vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};



void solve() {
    //正整数n和仅包含.和#的长为n的字符串a,b,要求构造一个7*n的仅由.和#组成的矩阵
    /*std::vector<int>a(10);
    for (int i = 1; i <= 9; i++)std::cin >> a[i];
    for (int i = 2; i < 9; i++) {
        if (a[1] != 0) {
            int res = std::min(a[i], a[1]);
            a[i] -= res;
            a[i + 1] += res;
            a[1] -= res;
        }
        else {
            break;
        }
    }*/
    int n;
    std::cin >> n;
    std::string a, b, a1, b1, a2, b2,k;
    std::cin >> a >> b;
    int num1 = 0, num2 = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == '.')num1++;
        if (b[i] == '.')num2++;
    }
    if (num1 == 0 || num2 == 0) {
        if (num1 == 0 && num2 == 0) {
            std::cout << "Yes\n";
            for (int i = 0; i < 7; i++) {
                std::cout << a << "\n";
            }
            return;
        }
        else {
            std::cout << "No\n";
            return;
        }
    }
    a1 = a, b1 = b;
    int op = 0;
    for (int i = 0; i < n; i++) {
        a1[i] = (a[i] == '.' ? '#' : '.');
    }
    op = 0;
    for (int i = 0; i < n; i++) {
        b1[i] = (b[i] == '.' ? '#' : '.');
    }
    if (a1[0] == '.') {
        op = 0;
        for (int i = 0; i < n; i++) {
            if (a1[i] == '.' && op == 0)a2.push_back('#');
            else {
                op = 1;
                a2.push_back('.');
            }
        }
    }
    else {
        if (a1[1] != '.')a1[0] = '.';
        a2.push_back( '#');
        for (int i = 1; i < n; i++)a2.push_back('.');
    }
    if(a2[1]!='.')a2[0] = '.';
    if (b1[0] == '.') {
        op = 0;
        for (int i = 0; i < n; i++) {
            if (b1[i] == '.' && op == 0)b2.push_back('#');
            else {
                op = 1;
                b2.push_back('.');
            }
        }
    }
    else {
        if (b1[1] != '.')b1[0] = '.';
        b2.push_back('#');
        for (int i = 1; i < n; i++)b2.push_back('.');
    }
    if(b2[1]!='.')b2[0] = '.';
    k.push_back('#');
    for (int i = 1; i < n; i++) {
        k.push_back('.');
    }
    std::cout << "Yes\n";
    std::cout << a << "\n" << a1 << "\n" << a2 << "\n" << k << "\n" << b2 << "\n" << b1 << "\n" << b<<"\n";
}

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3552kb

input:

5
4
#..#
.##.
5
##.#.
.#.##
6
######
.####.
27
.######.######.####.#.#####
.####...####..#.......#####
10
##########
##########

output:

Yes
#..#
.##.
#...
#...
#...
#..#
.##.
Yes
##.#.
..#.#
.#...
#....
#....
#.#..
.#.##
No
Yes
.######.######.####.#.#####
#......#......#....#.#.....
#..........................
#..........................
#..........................
#....###....##.#######.....
.####...####..#.......#####
Yes
########...

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 8ms
memory: 3852kb

input:

10000
6
.#..##
..#...
5
#..#.
##...
6
.###.#
...###
17
.####..#######..#
###########.#####
6
..##.#
#.##.#
25
#.##.##############.####.
####################.##.#
9
##.#..##.
##..#####
6
.###.#
##.###
6
###..#
#.####
25
#####################.#.#
######.##################
6
.#.###
.##..#
6
..####
#......

output:

Yes
.#..##
#.##..
#.....
#.....
#.....
.#.###
..#...
Yes
#..#.
.##.#
#....
#....
.#...
..###
##...
Yes
.###.#
#...#.
#.....
#.....
#.....
.##...
...###
Yes
.####..#######..#
#....##.......##.
#................
#................
.##########......
...........#.....
###########.#####
Yes
..##.#
.#..#.
...

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 9ms
memory: 3844kb

input:

10000
41
#######.#######.#########################
################.###.#######.############
6
..#..#
#..##.
6
#.#...
#...#.
6
.#.##.
....##
6
...#.#
##..#.
33
#####.###########################
###########.#####################
6
.##.##
.##.#.
5
..##.
####.
17
#.###.##########.
####.##.#####.##.
5
....

output:

Yes
#######.#######.#########################
.......#.......#.........................
.######..................................
#........................................
.###############.........................
................#...#.......#............
################.###.#######.############
Ye...

result:

ok Correct.

Test #4:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

10000
6
..####
.#....
6
...#.#
#..##.
9
..####.##
######..#
33
#######################.#####..##
######.######.###########.#######
6
####.#
#..##.
6
...###
##.###
25
######.#.#.##############
.#########.##########.###
17
############.####
###############.#
6
#..#.#
#####.
6
.#.###
..#...
49
########...

output:

Yes
..####
.#....
#.....
#.....
#.....
#.####
.#....
Yes
...#.#
.##.#.
#.....
#.....
#.....
.##..#
#..##.
Yes
..####.##
.#....#..
#........
#........
.#####...
......##.
######..#
Yes
#######################.#####..##
.......................#.....##..
.######################..........
#................

result:

ok Correct.

Test #5:

score: 0
Accepted
time: 5ms
memory: 3932kb

input:

10000
5
...#.
#####
6
###...
##..#.
9
.#.######
#.#..####
49
######.##########################################
########.#############.##########################
41
###########.#######.#####################
##############.##########################
6
###..#
###.##
49
#################################...

output:

No
Yes
###...
...###
.##...
#.....
.#....
..##.#
##..#.
Yes
.#.######
#.#......
#........
#........
#........
.#.##....
#.#..####
Yes
######.##########################################
......#..........................................
.#####...........................................
#..................

result:

ok Correct.

Test #6:

score: 0
Accepted
time: 5ms
memory: 4072kb

input:

2
100000
###.#...#..####...#####..####.#.######.##.##..#..#..####...###.#..##.#.##.####.#.#.###...#.##...####.#.#.####...####.#..##.##.#.#.....####..####..#...#..#.##..#.##.#.....#..#.#.###.#....####...####..##.#.#####..####.##.#.###.#.#....#.##.##...#.######.#..##..##...#.....#....#.####...#...##.#...

output:

Yes
###.#...#..####...#####..####.#.######.##.##..#..#..####...###.#..##.#.##.####.#.#.###...#.##...####.#.#.####...####.#..##.##.#.#.....####..####..#...#..#.##..#.##.#.....#..#.#.###.#....####...####..##.#.#####..####.##.#.###.#.#....#.##.##...#.######.#..##..##...#.....#....#.####...#...##.##.#.....

result:

ok Correct.

Test #7:

score: 0
Accepted
time: 6ms
memory: 4280kb

input:

2
100000
##.####.#..#..#.##..#.#..###..##..#####.....#..##.##.#...#.###..##..#...##...####..#...##...##.......#.#..##.##..###.#.###.##.#########..#...###.####.##...#..#.....#####.....#.####.#####..#.#....#..###.#.##..#..#.##.......#.###.##...####.....######..#.##....#.#.###.#.###.#..#.....####....##...

output:

Yes
##.####.#..#..#.##..#.#..###..##..#####.....#..##.##.#...#.###..##..#...##...####..#...##...##.......#.#..##.##..###.#.###.##.#########..#...###.####.##...#..#.....#####.....#.####.#####..#.#....#..###.#.##..#..#.##.......#.###.##...####.....######..#.##....#.#.###.#.###.#..#.....####....##........

result:

ok Correct.