分类 Codeforces 下的文章

C. Plasticine zebra

题目链接

Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)--C. Plasticine zebra

题解

中档题,题意大概是给定一个只包含'b','w'的字符串,每次可以指定一个位置,将字符串切开,两部分切开分别翻转后判断。求所能组成字符串中'b','w'交替字串的最大数目。
经过分析可以发现,每次操作相当于把原序列连成环后从某位置重新断开,所以直接判断循环的字符串即可。

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;

string s;
int arr[maxn];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    int len = s.size();
    if (len == 1) {
        cout << 1 << endl;
        return 0;
    }
    s = s + s;
    int num = 0;
    arr[0] = 1;
    for (int i = 1; i < s.size() - 1; i++) {
        if (s[i] != s[i - 1])
            arr[i] = arr[i - 1] + 1;
        else
            arr[i] = 1;
        num = max(num, arr[i]);
    }
    cout << (num > len ? len : num) << endl;
}

A. Doggo Recoloring

题目链接

Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)--A. Doggo Recoloring

题解

简单题,题意大概是给定一个字符串,可以将任意一个字符数量大于2的字母变成其他字母,求最终能否变成同一个字母。
只要存在任意一个可以变换的字符,即可将每个字母遍历一遍全部组成相同的。注意特判长度为1的字符串。

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int n;
string s;
int c[233];
int main(){
    cin >> n;
    if (n == 1) {
        cout << "Yes" << endl;
        return 0;
    }
    cin >> s;
    for (auto i:s) {
        c[i]++;
        if (c[i] >= 2) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

E. Inverse Coloring

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--E. Inverse Coloring

题解

高档题,题意大概是构造一个n*n的矩阵,要求满足相邻行与相邻列之间要么完全相同,要么完全相反。且不存在面积大于等于k的子矩阵颜色完全相同。
首先我们可以发现,只要确定了首行和首列即可得到整个矩阵,且最大颜色相同的矩阵为行最大连续颜色乘以列最大连续颜色。则我们dp行最大连续颜色与列最大连续颜色的数量,再分别枚举即可。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int mod = 998244353;
ll dp[maxn][maxn][2];//λ�ã�������������ɫ��
ll num[maxn];

int main() {
    ios::sync_with_stdio(0);    cin.tie(0);    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int k = 1; k <= n; k++) {
        memset(dp, 0, sizeof(dp));
        dp[1][1][0] = dp[1][1][1] = 1;
        for (int i = 2; i <= n; i++) {//�
            for (int j = 1; j <= min(i,k); j++) {//��������
                dp[i][1][1] += dp[i - 1][j][0];
                dp[i][1][0] += dp[i - 1][j][1];
                dp[i][j][1] += dp[i - 1][j - 1][1];
                dp[i][j][0] += dp[i - 1][j - 1][0];
                dp[i][1][0] %= mod;
                dp[i][1][1] %= mod;
                dp[i][j][0] %= mod;
                dp[i][j][1] %= mod;
            }
        }
        for (int i = 1; i <= k; i++) {
            num[k] += dp[n][i][0] + dp[n][i][1];
            num[k] %= mod;
        }
    }
    for (int i = n; i >= 2; i--) {
        num[i] = num[i] - num[i - 1] + mod;
        num[i] %= mod;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i*j >= k)break;
            ans += num[i] * num[j];
            ans %= mod;
        }
    }
    if (ans % 2 == 1)ans = (ans + mod) / 2;
    else ans /= 2;
    cout << ans << endl;
}

D. Mouse Hunt

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--D. Mouse Hunt

题解

中档题,题意大概是一只老鼠与一群房间,每个房间老鼠会往某个特定的房间跑,求最少的可以抓到老鼠的陷阱费用。
枚举每个最终的环即可。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 50;

int dfn[maxn], low[maxn], scccnt = 0, sccindex = 0, belong[maxn];

bool instack[maxn];
stack<int>sta;
vector<int>G[maxn];

void tarjan(int v) {
    dfn[v] = low[v] = ++sccindex;
    sta.push(v); instack[v] = true; int j;
    for (auto i = G[v].begin(); i != G[v].end(); i++) {
        int j = *i;
        if (!dfn[j]) {
            tarjan(j);
            low[v] = min(low[v], low[j]);
        }
        else if (instack[j] && dfn[j]<low[v])
            low[v] = dfn[j];
    }
    if (low[v] == dfn[v]) {
        scccnt++;
        do {
            j = sta.top(); instack[j] = false;
            sta.pop(); belong[j] = scccnt;
        } while (j != v);
    }
}

int outdegree[maxn], c[maxn];
int minn[maxn], size1[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, i, j, k;
    cin >> n;
    for (i = 1; i <= n; i++)cin >> c[i];
    long long ans = 0;
    for (i = 1; i <= n; i++) {
        cin >> j;
        G[i].push_back(j); outdegree[i]++;
        if (j == i)ans += c[i];
    }
    for (i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);

    for (i = 1; i <= n; i++)
        size1[belong[i]]++;
    memset(minn, 0x3f, sizeof(minn));
    for (i = 1; i <= n; i++) {
        if (size1[belong[i]] <= 1)continue;
        minn[belong[i]] = min(minn[belong[i]], c[i]);
    }
    for (i = 1; i <= n; i++) {
        if (minn[i] != 0x3f3f3f3f)
            ans += minn[i];
    }
    cout << ans << endl;

    return 0;
}

C. Minimum Value Rectangle

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--C. Minimum Value Rectangle

题解

中档题。题意大概是给出多个木棍,找出四个木棍组成矩形且满足周长平方除以面积最小。
经过计算得知(计算过程不写了),满足要求的必定是长度相邻的。所以排序依次判断比较即可。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;

int q1, q2, pre, pre2;
long double minnum;
int input[maxn];
int t, n;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (cin >> t; t; t--) {
        minnum = 1ll << 60;
        pre = pre2 = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> input[i];
        }
        sort(input + 1, input + n + 1);
        for (int i = 1; i <= n; i++) {
            if (pre == input[i]) {
                if (pre2 != 0) {
                    long double x(pre), y(pre2);
                    long double temp = (x + x + y + y)*(x + x + y + y) / (x*y);
                    if (temp < minnum) {
                        q1 = pre2;
                        q2 = pre;
                        minnum = temp;
                    }
                }
                pre2 = pre;
                pre = 0;
            }
            else {
                pre = input[i];
            }
        }
        cout << q1 << ' ' << q1 << ' ' << q2 << ' ' << q2 << endl;
    }
}

B. Numbers on the Chessboard

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--B. Numbers on the Chessboard

题解

简单题,题意大概是在一个 n * n 的矩阵内隔一个位置放置一个数,大概长这样
1 9 2 10
11 3 12 4
5 13 6 14
15 7 16 8
或这样
1 14 2 15 3
16 4 17 5 18
6 19 7 20 8
21 9 22 10 23
11 24 12 25 13
给出多个询问询问某个位置的数字。

直接计算即可,具体参照代码。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    ll n, q, x, y;
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        cin >> x >> y;
        ll ans = 0;
        if ((x + y) % 2 == 1) {
            ans += (n*n - 1) / 2 + 1;
        }
        if (n % 2 == 1) {
            ans += (x - 1) / 2 * n;
            if ((x + y) % 2 == 1)
                ans += (x - 1) % 2 * (n / 2);
            else
                ans += (x - 1) % 2 * (n / 2 + 1);
            ans += (y + 1) / 2;
        }
        else if (n % 2 == 0) {
            ans += (x - 1) * n / 2;
            ans += (y + 1) / 2;
        }
        cout << ans << endl;
    }
}

A. Palindromic Twist

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--A. Palindromic Twist

题解

简单题,题意大概是给定一个字符串,判断能否通过将每个字符或不变或加一或减一变成回文字符串。
从头至尾依次判断对应的回文位置是否为相差0或2即可。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

string s;
int main() {
    int n, temp;
    for (cin >> n; n; n--) {
        cin >> temp;
        cin >> s;
        bool pd(0);
        for (int i = 0; i < (s.size() - 1) / 2 + 1; i++) {
            if (abs(s[i] - s[temp - i - 1]) == 1 || abs(s[i] - s[temp - i - 1]) > 2)
                pd = true;
        }
        if (pd)cout << "NO" << endl;
        else cout << "YES" << endl;
    }
}

B. s-palindrome

题目链接

Educational Codeforces Round 14--B. s-palindrome

题解

简单题,题意大概是给定一个字符序列,判断是否使镜面对称。
每个字符一一对应过去判断一下即可。

代码

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

set<char> midd;
set<char> allowed;
char changed[233];
string s;
int main() {
    midd.insert('A');
    midd.insert('H');
    midd.insert('I');
    midd.insert('M');
    midd.insert('O');
    midd.insert('o');
    midd.insert('T');
    midd.insert('U');
    midd.insert('V');
    midd.insert('v');
    midd.insert('W');
    midd.insert('w');
    midd.insert('X');
    midd.insert('x');
    midd.insert('Y');
    allowed.insert('A');
    allowed.insert('H');
    allowed.insert('I');
    allowed.insert('M');
    allowed.insert('O');
    allowed.insert('o');
    allowed.insert('T');
    allowed.insert('U');
    allowed.insert('V');
    allowed.insert('v');
    allowed.insert('W');
    allowed.insert('w');
    allowed.insert('X');
    allowed.insert('x');
    allowed.insert('Y');
    for (int i=0;i<=125;i++){
        changed[i]=i;
    }
    changed['p']='q';
    changed['q']='p';
    changed['d']='b';
    changed['b']='d';
    allowed.insert('b');
    allowed.insert('d');
    allowed.insert('p');
    allowed.insert('q');
    cin>>s;
    if (s.length()%2){
        if (midd.find(s[s.length()/2])==midd.end()){
            cout<<"NIE"<<endl;
            return 0;
        }
    }
    for (int i=0;i<s.length()/2;i++){
        if (allowed.find(s[i])==allowed.end()){
            cout<<"NIE"<<endl;
            return 0;
        }
        else if(s[i]!=changed[s[s.length()-i-1]]){

            cout<<"NIE"<<endl;
            return 0;
        }
    }
    cout<<"TAK"<<endl;
    return 0;
}

C. Array

题目链接

Codeforces Beta Round #53--C. Array

题解

中档题。题意大概是求出一段长度为n的序列,其中的元素可以是1..n,求出满足非严格单调递增与非严格单调递减的序列数目。
对于每一种可能的元素分配方式,均存在的唯一的非严格单调递增排列方式与非严格单调递减的排列方式,当且仅当序列中所有元素都相同时这两种分配方式才等同。所以求出序列的分配方式再减去n即可。而序列的分配方式等同于球同盒不同,盒子允许为空的情况。
如果有n个相同的球放进m个不同的盒子中,盒子允许为空的组合方式有C(m+n-1,n-1)种。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
const ll INF=1ll<<60;
const ll MOD=1000000007;
long long  fac[MAXN], inv[MAXN], input[MAXN];
inline long long C(long long a, long long b) {
    return fac[a] * inv[b] % MOD * inv[a - b] % MOD;
};
int n;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    inv[0] = inv[1] = fac[0] = 1;
    for (int i = 2; i < MAXN; i++) {
        inv[i] = inv[MOD%i] * (MOD - MOD / i) % MOD;
    }
    for (int i = 1; i < MAXN; i++) {
        fac[i] = fac[i - 1] * i%MOD;
        inv[i] = inv[i - 1] * inv[i] % MOD;
    }
    cin>>n;
    cout<<(2*C(2*n-1,n-1)-n)%MOD<<endl;
}

B. Anton and Classes

题目链接

Codeforces Round #404 (Div. 2)--B. Anton and Classes

题解

简单题,题意大概是给出两组时间区间,从这两组时间区间中各选一组来使它们中间的空闲时间最大,求空闲时间的最大值。
从第一组中找到结束时间最早与开始时间最晚的,分别于第二组开始时间最晚的和结束时间最早的做差,取较大值。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1<<30;
int n,m;
int minn,maxn,minm,maxm;
int q1,q2;
int main() {
    cin>>n;
    minn=minm=INF;
    for (int i=1;i<=n;i++){
        cin>>q1>>q2;
        minn=min(q2,minn);
        maxn=max(q1,maxn);
    }
    cin>>m;
    for (int i=1;i<=m;i++){
        cin>>q1>>q2;
        minm=min(q2,minm);
        maxm=max(q1,maxm);
    }
    cout<<max(max(maxn-minm,maxm-minn),0)<<endl;
}