A - What month is it? (abc420 A)

题目大意

问x后y月是哪个月。

解题思路

模拟。

代码

void solve()
{
	int x,y;
    cin>>x>>y;
    cout<<((x+y)%12==0?12:(x+y)%12);
}

B - Most Minority (abc420 B)

题目大意

题目意思给的很复杂，意思是一群人投票，每次少数派会得分，最后问分数最高的是哪些人。

解题思路

模拟，注意输入是xy反转的。

代码

void solve()
{
	int n,m;
    cin>>n>>m;
    vector<string> s(n);
	for(int i=0;i<n;i++)
		cin>>s[i];
	vector<int> ans(n);
    for(int i=0;i<m;i++){
        int cnt=0;
        for(int j=0;j<n;j++){
            if(s[j][i]=='0')
                cnt++;
        }
		for(int j=0;j<n;j++){
			if(cnt==0 || cnt==n)
				ans[j]++;
			else if(cnt<=(n/2) && s[j][i]=='0')
				ans[j]++;
			else if(cnt>(n/2) && s[j][i]=='1')
				ans[j]++;
		}
    }
    int maxn=*max_element(ans.begin(),ans.end());
    for(int i=0;i<n;i++)
        if(ans[i]==maxn)
            cout<<i+1<<" ";
}

C - Sum of Min Query (abc420 C)

题目大意

给定两个数组A和B，每次操作修改A[i]或B[i]，问每次操作后A[i]和B[i]的最小值的和。

解题思路

每次修改对答案的修改很好计算，直接模拟即可。

代码

void solve()
{
	int n,q;
    cin>>n>>q;
    vi a(n),b(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    ll ans=0;
    for(int i=0;i<n;i++) {
        cin>>b[i];
        ans+=min(a[i],b[i]);
    }
    while(q--){
        char c;
        int x,y;
        cin>>c>>x>>y;
        x--;
        ans-=min(a[x],b[x]);
        if(c=='A'){
            a[x]=y;
        }
        else{
            b[x]=y;
        }
        ans+=min(a[x],b[x]);
        cout<<ans<<"\n";
    }
}

D - Toggle Maze (abc420 D)

题目大意

给定n*m的地图，地图上有关着的门和开着的门和开关，开关会反转所有门的状态，问到终点要走多久。

解题思路

BFS，但是需要记录当前开关的状态。

代码

#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
int dis[505][505][3];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void solve()
{
	int n,m;
    cin>>n>>m;
    vector<string> s(n);
    rep(i,n) cin>>s[i];
    pii st,ed;
    rep(i,n){
        rep(j,m){
            dis[i][j][0]=dis[i][j][1]=1e9+7;
            if(s[i][j]=='S') st={i,j};
            if(s[i][j]=='G') ed={i,j};
        }
    }
    queue<pair<pii,int> > q;
    q.push({st,0});
    dis[st.fi][st.se][0]=0;
    while(!q.empty()){
        int x=q.front().fi.fi,y=q.front().fi.se,flag=q.front().second;
        q.pop();
        if(x==ed.fi&&y==ed.se){
            cout<<dis[x][y][flag]<<"\n";
            return;
        }
        rep(i,4){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(s[nx][ny]=='#' || (s[nx][ny]=='o' && flag) || (s[nx][ny]=='x' && !flag)) continue;
            int nf=flag;
            if(s[nx][ny]=='?') nf^=1;
            if(dis[nx][ny][nf]>dis[x][y][flag]+1){
                dis[nx][ny][nf]=dis[x][y][flag]+1;
                q.push({ {nx,ny},nf});
            }
        }
    }
    cout<<"-1\n";
}

E - Reachability Query (abc420 E)

题目大意

给定n个点，q次操作，操作可以翻转点的黑白，也可以把两个点之间连边，还可以问某个点所在的连通块中有没有黑色点。

解题思路

带权并查集模板题，记录一下一个联通块内有多少个黑色的点即可。

代码

const int maxn=200005;
int fa[maxn],cnt[maxn];
int col[maxn];
int findfa(int x){
    if(fa[x]==x)
    return x;
    else
    return fa[x]=findfa(fa[x]);
}
void solve()
{
	int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    while(q--){
        int c;
        cin>>c;
        if(c==1){
            int x,y;
            cin>>x>>y;
            int fx=findfa(x),fy=findfa(y);
            if(fx!=fy){
                fa[fx]=fy;
                cnt[fy]+=cnt[fx];
            }
        }
        else if(c==2){
            int x;
            cin>>x;
            col[x]^=1;
            if(col[x]==0){
                cnt[findfa(x)]--;
            }
            else{
                cnt[findfa(x)]++;
            }
        }
        else if(c==3){
            int x;
            cin>>x;
            int fx=findfa(x);
            if(cnt[fx]){
                cout<<"Yes\n";
            }
            else{
                cout<<"No\n";
            }
        }
    }
}

F - kirinuki (abc420 F)

题目大意

待补充

解题思路

待补充

代码

// 待补充

G - sqrt(n²+n+X) (abc420 G)

题目大意

待补充

解题思路

待补充

代码

// 待补充