526互联

Codeforces Round 866 (Div. 2)

发布时间 2023-04-18 23:01:05作者: PHarr

A. Yura's New Name

一个简单的 dp，状态是\(f[i][0/1]\)表示前\(i\)位变成合法的且最后一位是^或_的最小代价。

如果是_只能从^转移过来，如果是^则都可以转移过来

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

void solve(){
	string s;
	cin >> s;
	int n = s.size();
	if( n == 1 ){
		if( s == "_" ) cout << "2\n";
		else cout << "1\n";
		return;
	}
	vector< array<int,2> > f(n + 1 , { INT_MAX,INT_MAX}); 
	if( s[0] == '_' ) f[1][0] = 1 , f[1][1] = 2;
	else f[1][1] = 0 , f[1][0] = 1;
	for( int i = 2 ; i <= n ; i ++ ){
		if( s[i-1] == '_' ){
			if( f[i-1][1] != INT_MAX ) f[i][0] = f[i-1][1];
			if( f[i-1][1] != INT_MAX ) f[i][1] = f[i-1][1] + 1; 
		}else{
			f[i][1] = min( f[i-1][0] , f[i-1][1] );
			f[i][0] = f[i][1] + 1;
		}
	}
	cout << f[n][1] << "\n";
}

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

B. JoJo's Incredible Adventures

把序列当成环，找到最长的连续 1 即可。手推一下就能发现最长连续的 1 出现的位置和答案无关。

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

#define int long long

void solve(){
	string s;
	cin >> s;
	int n = s.size();
	if( s.find("0") == -1 ) {
		cout << n*n << "\n";
	}else{
		s = s + s;
		int m = 0;
		for( int i = 0 , t ; i < n ; i ++  ){
			if( s[i] == '1' ){
				t = 1;
				while( s[i + t] == '1' ) t ++;
				m = max( t , m );
				i = i + t - 1;
			} 
		}

		cout << (m/2ll+1ll)*((m+1ll) / 2ll) << "\n";
	}
	return ;
}

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

C. Constructive Problem

首先求一遍 mex，然后找到最左侧的 mex+1 和最右侧的 mex+1 然后把中间的全部变成 mex，再求一次 mex，如果加1 输出yes

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

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

#define int long long

void solve(){
	int n = read();
	vector<int> a(n), b;
	for( auto & i : a) i = read();
	b = a;
	sort( b.begin(),b.end() );
	int mex = 0;
	for( auto i : b ){
		if( i < mex ) continue;
		else if( i == mex ) mex ++;
		else break;
	}
	int l = -1 , r = -1;
	for( int i = 0 ; i < n ; i ++ ){
		if( a[i] == mex + 1 ){
			if( l == -1 ) l = i;
			r = i;
		} 
	}
	if( l == -1 && r == -1 ){
		if( mex == n ) printf("No\n");
		else printf("Yes\n");
	}else{
		for( int i = l ; i <= r ; i ++ ) a[i] = mex+1;
		int newMex = 0;
		sort(a.begin(),a.end());
		for( auto i : a ){
			if( i < newMex ) continue;
			else if( i == newMex ) newMex ++;
			else break;
		}
		if( newMex == mex ) printf("Yes\n");
		else printf("No\n");
	}
	return ;
}

int32_t main(){
	for( int t = read() ; t ; t -- )
		solve();
	return 0;
}

D. The Butcher

首先第一刀切下的一定是最长的或最宽的。所以我们统计出所有块的\(maxH,maxW\)以及总面积\(area\)就知道的为二的两种情况。

怎么判断两种情况是否合法呢？

以\((maxH,\frac{area}{maxH})\)为例，前几刀一定是沿着\(w\)方向切得，此时矩形由至少一个\(maxH\)的块，可能有一些更小的块构成。把所有的\(maxH\)的块都删掉后，剩下的部分前几刀是沿着\(h\)方向切得，剩下的块组成的矩形就是\((maxH,w’)\)，\(w'\)就是\(\frac{area}{maxH}\)减去删掉块的\(w\)剩下的部分。

此时矩形是有至少一个\(w’\)的方块，可能有一些更小的块构成的，然后删掉所有\(w’\)后剩下的部分前几刀是沿着\(w\)方向切得。

可以发现上述的操作实际是类似的，不断的操作就可以把块全部切开，如果切的过程中没有满足条件，或者没有切成\(n\)块都是不合法的。

#include<bits/stdc++.h>

using namespace std;

#define int long long
typedef long long ll;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

void solve() {
    typedef map<int, multiset<int>> MAP;
    int n = read();
    MAP mapW, mapH;
    int maxW = 0, maxH = 0, area = 0;
    for (int w, h, i = 1; i <= n; i++) {
        w = read(), h = read();
        maxH = max(maxH, h), maxW = max(maxW, w);
        area += w * h;
        mapW[w].insert(h), mapH[h].insert(w);
    }

    auto check = [](int n, int w, int h, int f, MAP mapW, MAP mapH) -> bool {
        while (w > 0 && h > 0) {
            int tot = 0;
            if (f) { // w
                for (auto i: mapW[w]) {
                    mapH[i].erase(mapH[i].find(w));
                    tot += i, n--;
                }
                h -= tot, f = 0;
            } else {
                for (auto i: mapH[h]) {
                    mapW[i].erase(mapW[i].find(h));
                    tot += i, n--;
                }
                w -= tot, f = 1;
            }
            if (tot == 0) return false;
        }
        return n == 0;
    };
    set<pair<int, int> > res;
    if (area % maxW == 0 && check(n, maxW, area / maxW, 1, mapW, mapH))
        res.emplace(maxW, area / maxW);
    if (area % maxH == 0 && check(n, area / maxH, maxH, 0, mapW, mapH))
        res.emplace(area / maxH, maxH);
    cout << res.size() << "\n";
    for (auto [w, h]: res)
        cout << w << " " << h << "\n";
    return;


}

int32_t main() {
    for (int t = read(); t; t--)
        solve();
    return 0;
}