Gemini0325成功解题
原题链接：45866.[NOIP2024] 编辑字符串
2025-04-23 22:43:22
发布于：广东
14阅读
0回复
0点赞
gemini-2.5-pro-exp-03-25
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <map> // Still used for mapping fixed indices to their offset
using namespace std;
// Using a reasonable upper bound for INF for flow calculations
const long long INF = 1e12;
// --- Max Flow (Dinic Algorithm) Implementation ---
// Standard implementation - no changes needed here for optimization focus
struct Edge {
int to;
long long capacity;
int rev; // Index of the reverse edge in the destination's adjacency list
};
vector<vector<Edge>> graph;
vector<int> level; // Stores level in BFS for layered network
vector<int> iter; // Stores current edge index in DFS to avoid re-checking
// Add an edge and its reverse edge
void add_edge(int from, int to, long long cap) {
if (cap <= 0) return; // Optimization: Don't add edges with zero or negative capacity
graph[from].push_back({to, cap, (int)graph[to].size()});
// Add reverse edge with 0 capacity initially
graph[to].push_back({from, 0, (int)graph[from].size() - 1});
}
// BFS to build the level graph
bool bfs(int s, int t) {
level.assign(graph.size(), -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
// Iterate using indices for potentially minor speedup vs range-based for
for (size_t i = 0; i < graph[v].size(); ++i) {
const Edge& edge = graph[v][i];
if (edge.capacity > 0 && level[edge.to] < 0) {
level[edge.to] = level[v] + 1;
q.push(edge.to);
}
}
}
return level[t] != -1; // Return true if sink is reachable
}
// DFS to find augmenting paths and push flow
long long dfs(int v, int t, long long f) {
if (v == t) return f;
// Use size_t for loop counter matching vector::size() type
for (int& i = iter[v]; (size_t)i < graph[v].size(); ++i) {
Edge& e = graph[v][i];
if (e.capacity > 0 && level[v] < level[e.to]) {
// Pass std::min result directly
long long d = dfs(e.to, t, min(f, e.capacity));
if (d > 0) {
e.capacity -= d;
graph[e.to][e.rev].capacity += d;
return d;
}
}
}
return 0;
}
// Calculate maximum flow from s to t
long long max_flow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
iter.assign(graph.size(), 0);
long long f;
// Continue pushing flow as long as dfs finds augmenting paths
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
return flow;
}
// --- End of Max Flow Implementation ---
// Helper struct to store segment information
struct SegmentInfo {
vector<int> segment_id; // segment_id[i] = internal_id, or -1 if fixed
vector<pair<int, int>> segment_counts; // segment_counts[internal_id] = {count0, count1}
vector<int> fixed_indices; // list of original fixed indices
int num_segments = 0;
};
// Optimized function to identify segments and count characters
// Avoids map for segment_id_to_internal_idx mapping
SegmentInfo identify_segments(int n, const string& s, const string& t) {
SegmentInfo info;
info.segment_id.assign(n, -1);
info.segment_counts.reserve(n / 2 + 1); // Pre-allocate approximate space
info.fixed_indices.reserve(n); // Pre-allocate approximate space
int current_segment_internal_idx = -1;
for (int i = 0; i < n; ++i) {
if (t[i] == '1') {
if (current_segment_internal_idx == -1) { // Start of a new segment
current_segment_internal_idx = info.num_segments++;
info.segment_counts.emplace_back(0, 0); // Add counts for the new segment
}
info.segment_id[i] = current_segment_internal_idx; // Assign internal index
// Count characters within the segment directly
if (s[i] == '0') info.segment_counts[current_segment_internal_idx].first++;
else info.segment_counts[current_segment_internal_idx].second++;
} else {
info.segment_id[i] = -1; // Mark as fixed
info.fixed_indices.push_back(i);
current_segment_internal_idx = -1; // End current segment
}
}
return info;
}
int main() {
// Faster I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
// Reading strings efficiently
string s1(n, ' '), s2(n, ' '), t1(n, ' '), t2(n, ' ');
cin >> s1 >> s2 >> t1 >> t2;
// 1. Identify segments and fixed positions using the optimized helper
SegmentInfo info1 = identify_segments(n, s1, t1);
SegmentInfo info2 = identify_segments(n, s2, t2);
int num_s1_segs = info1.num_segments;
int num_s2_segs = info2.num_segments;
int num_s1_fixed = info1.fixed_indices.size();
int num_s2_fixed = info2.fixed_indices.size();
// 2. Calculate node indices using direct mapping (Optimized)
const int S = 0;
const int T = 1;
const int s1_seg_nodes_start = 2;
const int s1_fixed_nodes_start = s1_seg_nodes_start + num_s1_segs * 2;
const int s2_seg_nodes_start = s1_fixed_nodes_start + num_s1_fixed;
const int s2_fixed_nodes_start = s2_seg_nodes_start + num_s2_segs * 2;
const int total_nodes = s2_fixed_nodes_start + num_s2_fixed;
// Fast lookup for fixed position offset (improves on map if possible)
// If N is large, direct array lookup is faster than map.
vector<int> s1_fixed_pos_to_offset(n, -1);
for(int i = 0; i < num_s1_fixed; ++i) s1_fixed_pos_to_offset[info1.fixed_indices[i]] = i;
vector<int> s2_fixed_pos_to_offset(n, -1);
for(int i = 0; i < num_s2_fixed; ++i) s2_fixed_pos_to_offset[info2.fixed_indices[i]] = i;
// Initialize graph with calculated size
graph.assign(total_nodes, vector<Edge>());
// Reserve space in adjacency lists if beneficial (estimate edges)
// Example: graph[S].reserve(num_s1_segs * 2 + num_s1_fixed); ... etc.
// --- Add Edges ---
// S -> s1 supply nodes (Optimized loop)
for (int seg_idx = 0; seg_idx < num_s1_segs; ++seg_idx) {
// Calculate node indices directly
int node0_idx = s1_seg_nodes_start + seg_idx * 2;
int node1_idx = node0_idx + 1;
// Add edge only if capacity > 0 (already handled by add_edge)
add_edge(S, node0_idx, info1.segment_counts[seg_idx].first);
add_edge(S, node1_idx, info1.segment_counts[seg_idx].second);
}
for (int i = 0; i < num_s1_fixed; ++i) {
add_edge(S, s1_fixed_nodes_start + i, 1);
}
// s2 demand nodes -> T (Optimized loop)
for (int seg_idx = 0; seg_idx < num_s2_segs; ++seg_idx) {
int node0_idx = s2_seg_nodes_start + seg_idx * 2;
int node1_idx = node0_idx + 1;
add_edge(node0_idx, T, info2.segment_counts[seg_idx].first);
add_edge(node1_idx, T, info2.segment_counts[seg_idx].second);
}
for (int i = 0; i < num_s2_fixed; ++i) {
add_edge(s2_fixed_nodes_start + i, T, 1);
}
// Matching edges based on position i (Optimized Node Lookup)
for (int i = 0; i < n; ++i) {
// Determine s1 source node index for '0' and '1'
int s1_node_0 = -1, s1_node_1 = -1;
if (t1[i] == '0') { // s1 fixed
int offset = s1_fixed_pos_to_offset[i];
int fixed_node = s1_fixed_nodes_start + offset;
if (s1[i] == '0') s1_node_0 = fixed_node; else s1_node_1 = fixed_node;
} else { // s1 swappable
int s1_seg_internal_idx = info1.segment_id[i];
// Check if segment actually exists (should always be true here)
// if (s1_seg_internal_idx != -1) {
s1_node_0 = s1_seg_nodes_start + s1_seg_internal_idx * 2;
s1_node_1 = s1_node_0 + 1;
// }
}
// Determine s2 sink node index for '0' and '1'
int s2_node_0 = -1, s2_node_1 = -1;
if (t2[i] == '0') { // s2 fixed
int offset = s2_fixed_pos_to_offset[i];
int fixed_node = s2_fixed_nodes_start + offset;
if (s2[i] == '0') s2_node_0 = fixed_node; else s2_node_1 = fixed_node;
} else { // s2 swappable
int s2_seg_internal_idx = info2.segment_id[i];
// if (s2_seg_internal_idx != -1) {
s2_node_0 = s2_seg_nodes_start + s2_seg_internal_idx * 2;
s2_node_1 = s2_node_0 + 1;
// }
}
// Add matching edge for '0' if both nodes are valid
if (s1_node_0 != -1 && s2_node_0 != -1) {
add_edge(s1_node_0, s2_node_0, 1);
}
// Add matching edge for '1' if both nodes are valid
if (s1_node_1 != -1 && s2_node_1 != -1) {
add_edge(s1_node_1, s2_node_1, 1);
}
}
// 3. Compute Max Flow
cout << max_flow(S, T) << "\n";
}
return 0;
}
预计时间复杂度
有帮助，赞一个