HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)
前言
好久没有打 AtCoder 了。有点手生。只拿到了 \(\operatorname{rk}1510\)，应该上不了多少分。
只切了 \(\texttt{A,B,C,D}\) 四题。
A - Generalized ABC
简要题意
给出一个整数 \(K\)，输出前 \(K\) 个大写英文字母。
\(1 \leq K \leq 26\)
思路
模拟。
时间复杂度 \(O(K)\)，难度 入门。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cout<<(char)('A'+i-1);
}
return 0;
}
B - Let's Get a Perfect Score
简要题意
给出一个 \(N\times M\) 的 \(01\) 矩阵。你需要求出有多少个无序数对 \((i,j)\)，满足：
- \(1 \leq i,j \leq N\)
- \(\forall k(1 \leq k \leq M),A_{i,k}\operatorname{OR}A_{j,k}=1\)
- \(i\neq j\)
\(2 \leq N \leq 30,1 \leq M \leq 30\)
思路
这道题太烦了，吃了两道罚时。
但是其实是一个很简单的暴力题，直接枚举所有 \((i,j)\) 再暴力判断是否满足条件即可。
时间复杂度 \(O(N^2M)\)，难度 普及-。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
bool sol[50][50];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;cin>>ch;
sol[i][j]=ch=='o';
}
}
int cnt=0;
for(int a=1;a<=n;a++){
for(int b=(a+1);b<=n;b++){
bool flag=1;
for(int pro=1;pro<=m&&flag;pro++){
if(!(sol[a][pro]||sol[b][pro])) flag=0;
}
if(flag){
cnt++;
}
}
}
cout<<cnt;
return 0;
}
C - String Delimiter
简要题意
给出一个长度为 \(N\) 的字符串。你需要将没有被 " 包裹的 , 替换成 .。输出最后的字符串。
\(1 \leq N \leq 2 \times 10^5\)
思路
仍然是模拟。维护一个中间变量来保存当前是否被 " 包裹。然后遇到一个 " 就取反，中途进行替换。
时间复杂度 \(O(N)\)，难度 入门。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
bool in=0;
string str;
signed main(){
cin>>n;
cin>>str;
str="0"+str;
for(int i=1;i<=n;i++){
char opt=str[i];
if(str[i]=='"'){
in=!in;
}
if(str[i]==','){
if(!in) opt='.';
}
putchar(opt);
}
return 0;
}
（切前三题用时 \(11\) 分钟）
D - Make Bipartite 2
简要题意
给出一个 \(N\) 个节点 \(M\) 条边的无向图（不保证为二分图，不保证连通，保证无重边、自环）。你需要添加一条原图中不存在的边，使得原图是一个二分图。求有多少种方案。
\(2 \leq N \leq 2\times 10^5,0 \leq M \leq\min\{2\times10^5,\frac{1}{2}N(N-1)\}\)
思路
这道题相当有意思。
首先判断 \(0\)。答案为 \(0\) 的大致有这两种情况：
- 给出的图不是二分图。
- 给出的图是完全二分图。
第一种情况好判断，我们直接对原图 BFS 求二分图染色，看看是不是二分图即可。时间复杂度 \(O(N)\)。（第二种方法不好判断，也不必判断）。
我们考虑符合要求的边 \((u,v)\) 按照连通分量分成两种：
- \(u,v\) 属于同一个连通分量，且 \(u\) 和 \(v\) 的颜色不同。
- \(u,v\) 不属于同一个连通分量。注意这时不必判断颜色。原因：如果 \(u\) 和 \(v\) 的颜色相同，我们可以将 \(v\) 所处的连通分量的所有点的颜色取反。再连边就满足条件了。
我们再 BFS 求二分图染色的时候顺便求一下所有的连通分量和每一个连通分量对应的点集。然后在枚举连通分量时进行分情况讨论（令情况 \(1\) 的贡献为 \(a_1\)，情况 \(2\) 的贡献为 \(a_2\)）：
- 第一种情况我们遍历连通块所有点，求出颜色为白的个数 \(c_0\)，黑的个数 \(c_1\)。根据乘法原理，可以知道当前贡献为 \(c_0c_1\)。
- 第二中情况设当前连通块大小为 \(c\)，根据乘法原理，贡献是 \(c(N-c)\)。
注意这样子 \(a_2\) 同一条边会计算两次（\((u,v),(v,u)\) 各一次），且原本在图里的边也会被计算，所以最终答案是：
\]
时间复杂度 \(O(N)\)，难度 普及+/提高。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int c[3];
const int N = 2e5+5;
struct edge{
int nxt,to;
} g[N<<1];
int head[N],ec;
void add(int u,int v){
g[++ec].nxt=head[u];
g[ec].to=v;
head[u]=ec;
}
int col[N];
bool vis[N];
vector<int> vct[N];
bool bfs(int x){
queue<int> q;
col[x]=0;
q.push(x);
while(!q.empty()){
int u=q.front();
vis[u]=1;
vct[x].push_back(u);
q.pop();
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to;
if(col[v]==-1){
col[v]=col[u]^1;
q.push(v);
continue;
}
if(col[v]==col[u]){
return false;
}
}
}
return true;
}
signed main(){
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
add(u,v);add(v,u);
}
for(int i=1;i<=n;i++){
vis[i]=0;
col[i]=-1;
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
bool bip=bfs(i);
if(!bip){
cout<<0;
return 0;
}
}
int ret=0,ret2=0,ccnt=0;
for(int i=1;i<=n;i++){
if(!vct[i].size()) continue;
ccnt=0;
c[0]=0,c[1]=0;
for(int j : vct[i]){
// cout<<j<<' ';
c[col[j]]++;
ccnt++;
}
// cout<<c[0]<<' '<<c[1]<<'\n';
ret += (c[0]*c[1]);
ret2 += (ccnt*(n-ccnt));
}
cout<<(ret-m+(ret2/2));
return 0;
}
E - Choose Two and Eat One
简要题意
给出两个整数 \(N,M\) 和一个长为 \(N\) 的序列 \(A\)。你每次可以选择两个数 \(A_i,A_j\)，你可以获得 \({A_i}^{A_j}+{A_j}^{A_i}\bmod M\) 的收益，然后删除其中的一个。
你需要重复上述操作直到只剩下一个元素。求可以获得的最大收益和。
\(2\leq N \leq 500,2\leq M \leq 10^9,1\leq A_i\leq M-1\)
思路
考场没做出这道题真是遗憾，其实是一个简单题。
我们对于每一个 \(A_i,A_j\)，连边 \((i,j,{A_i}^{A_j}+{A_j}^{A_i}\bmod M)\)。然后显然易见答案就是该图的最小生成树上所有边边权和。使用 Kruskal 算法即可。
时间复杂度 \(O(N^3)\)。难度 普及+/提高。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int fastpow(int a,int b,int p){
if(b==1) return a%p;
if(b==0) return 1;
int ret=fastpow(a,b>>1,p);
ret=ret*ret%p;
if(b&1) ret=ret*a%p;
return ret;
}
int fa[505];
int n,m,a[505];
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
struct node{
int x,y,v;
bool operator<(const node &an) const {
return v>an.v;
}
} edge;
vector<node> edges;
int ret=0,cnt=0;
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
edges.push_back({i,j,(fastpow(a[i],a[j],m)+fastpow(a[j],a[i],m))%m});
}
}
sort(edges.begin(),edges.end());
for(unsigned int i=1;i<=edges.size();i++){
if(cnt>=(n-1)) break;
edge=edges[i-1];
int fx=find(edge.x),fy=find(edge.y);
if(fx==fy) continue;
cnt++;
ret+=edge.v;
fa[fx]=fy;
}
cout<<ret<<'\n';
return 0;
}
F - Union of Two Sets
简要题意
这是一道 IO 交互题。
交互器首先会给你一个整数 \(N\)。你需要输出一个整数 \(M\)，然后输出 \(M\) 个区间，第 \(i\) 个区间为 \([l_i,r_i]\)。
然后交互器会给你一个整数 \(Q\)，表示有 \(Q\) 个询问，每个询问给出一个区间 \([L,R]\)，你需要输出两个整数 \(a,b\)，使得第 \(a\) 个区间的所有元素所组成的集合与第 \(b\) 个区间所有元素所组成的集合的并集恰好为 \([L,R]\) 中的所有元素的集合。
你的输出需要满足 \(1\leq M\leq5\times10^4,1\leq l_i\leq r_i\leq N,1 \leq a,b \leq N\)。
\(1 \leq N \leq 4\times10^3,1\leq Q \leq 10^5,1 \leq L \leq R \leq N\)。
思路
考场上我看到是交互题就跑了。其实还是很简单的。这是一道比较新颖的 ST 表模板题。
ST 表通过预处理 \(O(N\log N)\) 个区间。然后每一个询问合并两个已经预处理的区间来求得答案。而且 ST 表这种重复贡献数据结构满足的就是并集关系。完全符合题意。
于是就做完了，\(M\) 为 \(N\log_2 N\) 级别，可以通过本题。
时间复杂度 \(O(N\log N+Q)\)，难度 普及/提高-。
代码
#include <bits/stdc++.h>
#define int long long
#define nxt cout<<'\n'<<flush
using namespace std;
int n,q;
int f[4005][21],cnt;
vector<pair<int,int> > ranges;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
f[i][0]=(++cnt);
ranges.push_back({i,i});
}
for(int j=1;j<=log2(n);j++){
for(int i=1;i+(1<<j)-1<=n;i++){
f[i][j]=(++cnt);
ranges.push_back({i,i+(1<<j)-1});
}
}
cout<<cnt;nxt;
for(pair<int,int> range:ranges){
cout<<range.first<<' '<<range.second;nxt;
}
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
int p=log2(r-l+1);
cout<<f[l][p]<<' '<<f[r-(1<<p)+1][p];nxt;
}
return 0;
}
