每日一题5.26

495684945

icpc 2024 香港区域赛 2铜 3银 5金

比赛榜单

稳银题 第三题L

XinyuLin

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool check(vector<string>& a, char ch) {
    for (auto& ve : a)
    {
        for (char x : ve) {
            if (x != ch) {
                return false;
            }
        }
    }
    return true;
}



bool is_ok(vector<string>& s, char ch ) {
    int n = s.size(), m = s[0].size();
    vector<string> ans;
    string cur = "";
    for (int i = 0; i < 401; i++) {
        if (check(s, ch)) {
            break;
        }
        if (i == 400) {
            return false;
        }
        cur = "";

        int y = 0;
        s[0][0] = 'W' ^ 'B' ^ s[0][0];
        for (int k = 0; k < n - 1; k++) {
            auto it = s[k].find_last_not_of(ch);
            if (it == string::npos || it <= y) {
                it = y;
            }
            for (int j = y + 1; j <= it; j++) {
                y++;
                s[k][j] = 'W' ^ 'B' ^ s[k][j];
                cur += 'R';
            }
            cur += 'D';
            s[k + 1][y] = 'W' ^ 'B' ^ s[k + 1][y];
        }
        for (int j = y + 1; j <= m - 1; j++) {
            s[n - 1][j] = 'W' ^ 'B' ^ s[n - 1][j];
            cur += 'R';
        }
        ans.push_back(cur);
    }
    cout << "YES" << endl;
    cout << ans.size() << endl;
    for (string& ss : ans) {
        cout << ss << endl;
    }
    return true;
}


void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    vector<string> ts(s);
    if (is_ok(s, 'W')) {
        return;
    }
    if (is_ok(ts, 'B')) {
        return;
    }
    cout << "NO" << endl;

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

495684945

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;

void solve(){
	int n,m;
	cin>>n>>m;
	vector b(n+10,vector<int>(m+10));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='W')b[i][j]=1;
		}
	}
	auto check=[&](int x){
		vector a=b;
		vector<vector<char>>op(410);
		int cnt=1e9,f=1;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
//				cout<<a[i][j]<<" "<<1-x<<" \n"[j==m];
				if(a[i][j]!=1-x){
					f=0;
					break;
				}
			}
		}
		if(f){
			cnt=min(0ll,cnt);
			return pair<int,vector<vector<char>>>{cnt,op};
		}
		for(int k=1;k<=400;k++){
			int j=1;
			for(int i=1;i<=n;i++){
				if(i>=2)op[k].push_back('D');
				int j2;
				for(j2=m;j2>=1;j2--){
					if(a[i][j2]==x)break;
				}
				if(i==n)j2=m;
				for(int o=j+1;o<=j2;o++){
					a[i][o]=1-a[i][o];
					op[k].push_back('R');
				}
				a[i][j]=1-a[i][j];
				if(j2>j)j=j2;
			}
			f=1;
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++){
					if(a[i][j]!=1-x){
						f=0;
						break;
					}
				}
			}
			if(f){
				cnt=min(k,cnt);
				break;
			}
		}
		return pair<int,vector<vector<char>>>{cnt,op};;
	};
	int ans=1e18;
	vector<vector<char>>op;
	auto [ans2,op2]=check(0);
	if(ans>ans2){
		ans=ans2;
		op=op2;
	}
	auto [ans3,op3]=check(1);
	if(ans>ans3){
		ans=ans3;
		op=op3;
	}
	if(ans>400){
		cout<<"NO"<<endl;
		return ;
	}
	cout<<"YES"<<endl<<ans<<endl;
	for(int i=1;i<=ans;i++){
		for(auto j : op[i])cout<<j;
		cout<<endl;
	}
}

signed main(){
	int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)solve();
	return 0;
}

Fengyj

Fengyj 发表于 2025-5-27 10:43
#include
using namespace std;

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<string>s(n);
    for(int i=0;i<n;i++) cin>>s;
    vector<string>res;
    auto fun=[&](char tar)->bool{
        res.clear();
        vector<vector<int>>a(n,vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[j]=s[j]==tar;
            }
        }
       int ok=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                //cerr<<a[j]<<' ';
                if(a[j]==0){
                    ok=0;
                }
            }
            //cerr<<'\n';
        }
        if(ok) {
            return 1;
        }
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<m;j++){
        //         cerr<<a[j]<<' ';
        //     }
        //     cerr<<'\n';
        // }
        while((int)res.size()<400){
            string t="";
            int y=0;
            for(int i=0;i<n;i++){
               
               
                int flag=y;
               for(int j=m-1;j>=y;j--){
                    if(a[j]==0){
                        flag=j;
                        break;
                    }
                }
                while(y<flag){
                    a[y]^=1;
                    t+='R';
                    y++;
                }
                a[y]^=1;
                if(i!=n-1){
                    t+='D';
                }
            }
            y++;
            while(y<m){
                a[n-1][y]^=1;
                t+='R';
                y++;
            }
            res.push_back(t);
            int ok=1;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    //cerr<<a[j]<<' ';
                    if(a[j]==0){
                        ok=0;
                    }
                }
                //cerr<<'\n';
            }
            if(ok) {
                return 1;
            }
        }
      
         return 0;
    };
    if(fun('W')){
        cout<<"YES\n";
       // cout<<"W\n";
        cout<<res.size()<<endl;
        if(res.size())for(auto i:res) cout<<i<<endl;
      
    }
    else if(fun('B')){
        
        cout<<"YES\n";
        cout<<res.size()<<endl;
        if(res.size())for(auto i:res) cout<<i<<endl;
        
    }
    else{
        cout<<"NO\n";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}