比赛链接
B MST
题面
Sajin has recently delved into the study of minimum spanning trees and now he has mastered the algorithm of MST.
He is eager to assess your grasp of minimum spanning tree concepts through a series of queries.
You are confronted with an weighted undirected graph that encompasses $n$ vertices and $m$ edges without any self-loops.
Sajin presents $q$ inquiries. For each, a vertex set $S$ is given. Your objective is to determine the induced subgraph of $S$ and find the weight of its minimum spanning tree.
A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges, from the original graph, connecting pairs of vertices in that subset.
If the induced subgraph of $S$ is disconnected, output -1.
INPUT
The first line contains $3$ integers $n$, $m$, $q$ ($2 \le n \le 10^5,1 \le m, q \le 10^5$), — the number of points, the number of edges, and the number of queries.
Then $m$ lines follow, each line contains three integers $u_i$, $v_i$, $w_i$($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le w_i \le 10^9$), — the two endpoints of the $i$-th edge and the edge weight.
Next $q$ lines, each line first contains an integer $k_i$($1 \le k_i \le n$) — the size of the vertex set $S$ for the $i$-th query.
Then followed by $k_i$ distinct integers $s_{i,j}$($1 \le s_{i,j} \le n$) — the numbers of the vertex set $S$ for the $i$-th query.
It is guaranteed that the sum of $k_i$ over all queries does not exceed $10^5$.
OUTPUT
For each query, output one integer representing the answer.
解题思路
- 题目限制了总的需要查询的点数，所以可以从此入手。首先考虑单次查询点集较小的情况，因为点集k小所以位于诱导子图中的边的数目也小，最多只有$k^2$条边。此时我们便可以从map中处理出所有的边并排序，再用kruskal算出答案。此时总的时间复杂度为$\mathcal O(k^2 \log(k))$
- 再考虑单次查询点集较大的情况。此时我们可以直接去遍历所有的边，因为$k$的总数是固定的，所以点集大于等于$\log(10^5)$的次数最多是$\log (10^5)$次，总的时间复杂度为$\mathcal O(m \log (k))$。
- 综上所述分界点位于$\log (n)$处。
AC代码
#include <bits/stdc++.h>
// #define int long long
using ll = long long;
using PII = std::array<int, 2>;
using namespace std;
const ll INF = 2E18 + 10;
const int N = 1E5 + 5;
struct DSU {
std::vector<int> f, siz;
DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }
int find(int x) {
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (size(x) < size(y)) swap(x, y);
if (x == y) return false;
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) { return siz[find(x)]; }
};
ll d[N];
bool st[N], ex[N];
array<int, 3> edges[N];
unordered_map<int, int> mp[N];
void SINGLE_TEST() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
cin >> edges[i][1] >> edges[i][2] >> edges[i][0];
edges[i][1]--;
edges[i][2]--;
if (edges[i][1] > edges[i][2]) swap(edges[i][1], edges[i][2]);
}
sort(edges, edges + m);
for (int i = 0; i < m; i++) {
if (!mp[edges[i][1]].count(edges[i][2])) {
mp[edges[i][1]][edges[i][2]] = i;
}
}
DSU dsu(n);
for (int i = 0; i < n; i++) d[i] = INF;
while (q--) {
int k;
cin >> k;
vector<int> v(k);
for (int i = 0; i < k; i++) {
cin >> v[i];
v[i]--;
ex[v[i]] = 1;
}
ll ans = 0;
int cnt = 0;
if (k <= 300) {
sort(v.begin(), v.end());
vector<int> tmp;
for (auto v1 : v) {
int t = -1;
for (auto v2 : v) {
if (mp[v1].count(v2)) {
tmp.push_back(mp[v1][v2]);
}
}
}
sort(tmp.begin(), tmp.end());
for (auto i : tmp) {
if (dsu.merge(edges[i][1], edges[i][2])) {
ans += edges[i][0];
cnt++;
}
}
} else {
for (int i = 0; i < m; i++) {
if (ex[edges[i][1]] && ex[edges[i][2]]) {
if (dsu.merge(edges[i][1], edges[i][2])) {
ans += edges[i][0];
cnt++;
}
}
}
}
if (cnt < k - 1) ans = -1;
cout << ans << "\n";
for (auto v1 : v) {
dsu.f[v1] = v1;
dsu.siz[v1] = 1;
ex[v1] = 0;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int SAMPLES = 1;
// cin>>SAMPLES;
while (SAMPLES--) SINGLE_TEST();
}C Red Walking on Grid
题面
Red is on a $2\cdot n$ grid, with some cells being red and others being white.
Red can initially choose a red cell, and at each step, can choose a red cell above, below, to the left, or to the right. When Red leaves a cell, the cell immediately turns white.
Red wants to know the maximum number of steps she can take.
If there are no initial red cells, please output $0$.
INPTUT
The first line contains a positive integer $n(1\leq n \leq 10^6)$.
The next two lines contain a $2\cdot n$ character matrix, consisting only of \`R' and \`W' characters. \`R' represents a red cell, and \`W' represents a white cell.
OUTPUT
An integer — the maximum number of steps Red can take.
解题思路
- 很明的dp题。
AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+6;
int dp[3][N];
void solve()
{
int n;
cin>>n;
string a,b;
cin>>a>>b;
int ans=0;
for(int i=0;i<n;i++){
dp[0][i]=0;
dp[1][i]=0;
}
a=' '+a;
b=' '+b;
for(int i=1;i<=n;i++){
if(a[i]=='R'){
dp[0][i]=dp[0][i-1]+1;
}
if(b[i]=='R'){
dp[1][i]=dp[1][i-1]+1;
}
int x=dp[0][i],y=dp[1][i];
if(a[i]=='R'){
dp[0][i]=max(dp[0][i],y+1);
}
if(b[i]=='R'){
dp[1][i]=max(dp[1][i],x+1);
}
ans=max({ans,dp[1][i],dp[0][i]});
}
if(ans==0){
cout<<"0";
return ;
}
cout<<ans-1<<'\n';
}
signed main()
{
int _ = 1;
// cin>>_;
while (_--)
{
solve();
}
}E GCD VS XOR
题面
Ben\_H has a positive integer $x$. He wants you to find another positive integer $y$, which is strictly less than $x$, so that the equation $gcd(x, y) = x \oplus y$ holds. Can you help him?
where $\oplus$ is bitwise XOR operation (see notes for explanation).
INPUT
The first line contains a single integer $t (1 \leq t \leq 10^4)$ — the number of test cases.
The only line of each test case contains a single integer $x (1\leq x \leq 10^{18})$.OUTPUT
For each testcase, output a single positive integer $y$, if you find a feasible answer, or $-1$ otherwise.
解题思路
- 除了$2^n$多存在答案，暴力遍历所有二进制位即可。
AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[90];
void solve()
{
int n,y=-1;
cin>>n;
int x=n,t=0;
while(x){
a[t++]=x%2;
x/=2;
}
int p=1,f=0;
for(int i=0;i<t-1;i++){
if(i)p*=2;
if(a[i]==1){
y=p;
f=1;
break;
}
}
if(f)
cout<<n-y<<'\n';
else cout<<"-1\n";
}
signed main()
{
int _ = 1;
cin>>_;
while (_--)
{
solve();
}
}Instructions Substring
题面
Red stands at the coordinate $(0,0)$ of the Cartesian coordinate system. She has a string of instructions: up, down, left, right (where \`right' increases the x-coordinate by $1$, and \`up' increases the y-coordinate by $1$).
Now Red wants to select a continuous substring of instructions and execute them. Red hopes that the final execution of the instructions can pass through the coordinate $(x,y)$. She wants to know how many selection options there are.
INPUT
The first line contains three integers $n$, $x$, and $y$ $(1 \leq n \leq 2 \times 10^5, -10^5 \leq x, y \leq 10^5)$, — the length of the instruction string and the coordinates Red hopes to pass through.
The second line contains a string of length $n$, consisting of the characters $'W'$, $'S'$, $'A'$, and $'D'$. — the four directions: up, down, left, and right, respectively.
OUTPUT
Output one integer representing the number of selection options for the continuous substring.
解题思路
- 利用前缀和的思想，每次向前进的时候同时前进终点即可。
AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+6;
map<pair<int,int> ,int>mpp;
map<int,int>mp;
int l[N],r[N];
void solve()
{
int n,x,y,cnt;
cin>>n>>x>>y;
string p;
cin>>p;
p=' '+p;
int a=0,s=0,w=0,d=0;
int ans=0;
int u,v;
if(x==0&&y==0){
cout<<n*(n+1)/2<<'\n';
return ;
}
mpp[{0,0}]=1;
for(int i=1;i<=n;i++){
if(p[i]=='W'){
l[i]=1;
}
if(p[i]=='S'){
l[i]=-1;
}
if(p[i]=='A'){
r[i]=-1;
}
if(p[i]=='D'){
r[i]=1;
}
l[i]+=l[i-1];
r[i]+=r[i-1];
u=l[i]-y;
v=r[i]-x;
mpp[{l[i],r[i]}]++;
mp[cnt]=1;
ans+=mpp[{u,v}]*(n-i+1);
mpp[{u,v}]=0;
}
cout<<ans<<'\n';
}
signed main()
{
int _ = 1;
// cin>>_;
while (_--)
{
solve();
}
}