太好了，这次写了 ABCDEG，就差 F 就能 AK 了！（这次题太水了）

A - What month is it?

求 $X$ 月往后 $Y$ 月是几月。

有周期，直接对 $12$ 取模。但月份是 $[1,12]$，余数是 $[0,11]$，平移一下即可。

1
cout<<(x+y-1)%12+1;

B - Most Minority

这题我读题读了10分钟，总共做了20分钟……所以我决定提供最好的题意。

题目大意

$N$ 个人（奇数）投了 $M$ 轮票，每一行给你每个人投的共 $M$ 轮票（$0$ 或 $1$），求得分最高的人，若有同分升序输出。

得分规则：设一轮票中，有 $x$ 人投 $0$，$y$ 人投 $1$

  • $x=0$ 或 $y=0$，所有人得 $1$ 分
  • $x<y$，投 $0$ 得一分
  • $x>y$，投 $1$ 得一分
  • 由于 $N$ 是奇数，不存在 $x=y$

题目分析

数据范围很小，枚举即可。值得注意的就是竖着一列才是一轮！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 for(int j=1;j<=m;j++){
    int x=0,y=0;
    for(int i=1;i<=n;i++){
        if(a[i][j]=='0') x++;
        else y++;
    }
    if(x==0||y==0) for(int i=1;i<=n;i++) p[i]++;
    else if(x<y){
        for(int i=1;i<=n;i++) if(a[i][j]=='0') p[i]++;
    } 
    else{
        for(int i=1;i<=n;i++) if(a[i][j]=='1') p[i]++;
    } 
}
int x=*max_element(p+1,p+n+1);
for(int i=1;i<=n;i++) if(p[i]==x) printf("%d ",i);

C - Sum of Min Query

给你长度为 $N$ 的数组 $A$ 和 $B$，$Q$ 次查询，每次输入 $A/B,X,V$，将 $A_X/B_X$ 改为 $V$，再输出 $\sum_{i=1}^n min(A_i,B_i)$。

每次查询对比原本的值更新即可，记得开 long long。

1
2
3
4
5
6
7
8
char ch;
int x,v;
cin>>ch>>x>>v;
int k=min(a[x],b[x]);
if(ch=='A') a[x]=v;
else b[x]=v;
sum+=min(a[x],b[x])-k;
printf("%lld\n",sum);

D - Toggle Maze

题目大意

一个 $N\times M$的地图，其中 $A_{i,j}$ 有如下情况：

  • . : 请输入文本
  • # : 障碍
  • S : 起点
  • G : 终点
  • o : 门（开）
  • x : 门（关）
  • ? : 开关（碰到时可让全图的门切换状态）

从起点上下左右走，求到终点最小步数。

题目分析

一眼 bfs，多加一个状态表示开关，只会有两种，用 bool 表示，碰到开关取反，碰到门判断状态是否符合即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,dx[]={0,1,0,-1},dy[]={1,0,-1,0},dis[N][N][2],sx,sy;
char a[N][N];
struct node{
    int x,y;
    bool f;
};
int bfs(){
    queue<node> q;
    q.push({sx,sy,0});
    dis[sx][sy][0]=0;
    while(!q.empty()){
        int x=q.front().x,y=q.front().y;
        bool f=q.front().f;
        q.pop();
        if(a[x][y]=='G') return dis[x][y][f];
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m) continue;
            char ch=a[nx][ny];
            if(ch=='#'||(ch=='x'&&!f)||(ch=='o'&&f)) continue;
            bool nf=f;
            if(ch=='?') nf=!f;
            if(dis[nx][ny][nf]==-1){
                dis[nx][ny][nf]=dis[x][y][f]+1;
                q.push({nx,ny,nf});
            }
        }	
    }
    return -1;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S') sx=i,sy=j;
            dis[i][j][0]=dis[i][j][1]=-1;
        }
    cout<<bfs();
    
}

E - Reachability Query

题目大意

给你一个 $N$ 个点的无向图，初始每个点都是白色，没有连边。$Q$ 个询问：

  • 类型 $1$，$u$和$v$ 之间连边
  • 类型 $2$，将 $v$ 变色
  • 类型 $3$，询问 $v$ 能否到达黑点

题目分析

判断连通性，一眼并查集。

接下来考虑如何处理变色，我们可以开一个数组 $cnt$，$cnt_i$表示以 $i$ 为祖宗的联通块的黑点的个数。

$u$ 变色时，若该点原是黑色，则 $cnt_{find(u)}$ 减一，反则加一。

合并 $u,v$ 时，将 $cnt$ 也转移即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,fa[N],cnt[N];
bool f[N];
int find(int x){return (x==fa[x]?x:fa[x]=find(fa[x]));}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x!=y) fa[x]=y,cnt[y]+=cnt[x];
}
void change(int x){
    int fx=find(x);
    if(f[x]) cnt[fx]--;
    else cnt[fx]++;
    f[x]=!f[x];
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) fa[i]=i;
    int op,u,v;
    while(q--){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d",&u,&v);
            merge(u,v);
        }
        else if(op==2){
            scanf("%d",&u);
            change(u);
        }
        else{
            scanf("%d",&u);
            if(cnt[find(u)]) printf("Yes\n");
            else  printf("No\n");
        }
    }
}

G - sqrt(n²+n+X)

当当当当！本次主角大水数学题登场！

这次 ABC，前 5 题很简单，F 一看就码量很大没敢写。于是，我就在茫茫人海中找到的这个标题直白的 G题——

发现很水，当然能让我做出来最好。

题目大意

给定 $x$，求能使 $\sqrt{n^2+n+x}$ 是整数的所有整数 $n$，升序输出。

题目分析

一眼数学（这次比赛怎么这么多一眼）。

设 $\sqrt{n^2+n+x}=k$
$$\therefore n^2+n+x=k^2$$
配一下方
$$（n+\frac{1}{2})^2+(x-\frac{1}{4})=k^2$$
$$(2n+1)^2+(4x-1)=(2k)^2$$
$$4x-1=(2k)^2-(2n+1)^2=(2k+2n+1)(2k-2n-1)$$
令 $a=(2k+2n+1),b=(2k-2n-1)$，则：
$$\begin{cases} ab=4x-1 \newline a-b=4n+2
\end{cases}$$
$$\therefore n=\frac{a-b-2}{4} ,①$$

那我们枚举一一下 $4x-1$ 的因数，再带入 ① 判断一下能否整除，求出 $n$ 即可，注意负数也要考虑。时间复杂度 $O(\sqrt n)$，常数略大。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int x,k;
set<int> ans;
void f(int a,int b){
    if(a*b==k&&(a-b-2)%4==0) ans.insert((a-b-2)/4);
}
signed main(){
    cin>>x;
    k=4*x-1;
    for(int i=1;i*i<=abs(k);i++){
        if(k%i!=0) continue;
        f(i,k/i),f(-i,-k/i);
        f(i,-k/i),f(-i,k/i);
        f(k/i,i),f(-k/i,i);
        f(k/i,-i),f(-k/i,-i);
    }
    printf("%lld\n",ans.size());
    for(auto i:ans) printf("%lld ",i);
}