QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#789899 | #9621. 连方 | yuhaowei | AC ✓ | 9ms | 4280kb | C++20 | 6.6kb | 2024-11-27 22:35:06 | 2024-11-27 22:35:06 |
Judging History
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.