2018年8月

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;
    }
}

Taotao Picks Apples

题目连接

[HDU 6406] 2018 Multi-University Training Contest 8--1010 Taotao Picks Apples

题解

高档题。题意大概是给定一组数字,按照如下规则以此取数:

  • 取出第一个数
  • 如果当前数字严格大于上一个选取的数字,取出当前数字

现在给出多个询问,每个询问处理将某个数字改成其他数字,求取出多少数字。

首先将原序列中取出的数字找出来,标记为关键点,之后将两两关键点之间以上一个关键点作为第一个取出的数字,找出区间内可以取到的关键点。接下来分为以下几种情况讨论

  • 修改的数字为第一组关键点

    • 将当前数字升高
      直接判断第一批关键点中严格大于修改后数字的第一个数字,输出原始序列答案减去两数之间的关键点数即可。
    • 将当前数字降低
      首先判断修改后数字的值是否严格大于上一个关键点。如果不是,将答案记录为原数字减一,之后再将答案加上该位置对应的第二组关键点中大于修改后数字的数量。
  • 修改的数字不是第一组关键点

    • 将当前数字升高

      • 修改后的值小于等于上一个第一组关键点
        直接输出原始序列的答案
      • 修改后的值大于上一个第一组关键点
        判断第一批关键点中严格大于当前位置值最小的一个,原始序列答案减去两数之间关键点数即为答案。
    • 将当前数字降低
      直接输出原始序列的答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int input[maxn];
int imp[maxn],pos[maxn];
int isimp[maxn];
vector<int> decc[maxn];
int main(){
//    freopen("1.in","r",stdin);
//    freopen("zj.out","w",stdout);
//    ios::sync_with_stdio(0);
//    cout.tie(0);
//    cin.tie(0);
    int t,n,m,pre,num,p,q;

    for (cin>>t;t;t--){
        memset(isimp,0,sizeof(isimp));
        memset(imp,0,sizeof(imp));
        memset(pos,0,sizeof(pos));
        num=0;

        cin>>n>>m;
        for(int i=1;i<=n;i++)decc[i].clear();
        for (int i=1;i<=n;i++){
            scanf("%d",&input[i]);
        }

        pre=input[1];
        imp[++num]=input[1];
        pos[num]=1;
        isimp[num]=1;
        for (int i=2;i<=n;i++){
            if(input[i]>pre){
                pre=input[i];
                imp[++num]=input[i];
                pos[num]=i;
                isimp[i]=num;
            }
        }
        for (int i=1;i<num;i++){
            pre=imp[i-1];
            for (int j=pos[i]+1;j<pos[i+1];j++){
                if (input[j]>pre){
                    pre=input[j];
                    decc[i].push_back(pre);
                }
            }
        }
        pre=imp[num-1];
        for (int j=pos[num]+1;j<=n;j++){
            if (input[j]>pre){
                pre=input[j];
                decc[num].push_back(pre);
            }
        }

        for (int i=1;i<=m;i++){
            cin>>p>>q;
            if (isimp[p]){
                if (q==input[p]){
                    //cout<<num<<endl;
                    printf("%d\n",num);
                }
                else if (q>input[p]){
                    int temp=(int)(upper_bound(imp+1,imp+num+1,q)-imp);
                    printf("%d\n",isimp[p]+num-temp+1);
                    //cout<<isimp[p]+num-temp+1<<endl;
                }
                else if(q<input[p]){
                    int temp=(int)(upper_bound(decc[isimp[p]].begin(),decc[isimp[p]].end(),q)-decc[isimp[p]].begin());
                    //cout<<num-(q>imp[isimp[p]-1]?0:1)+decc[isimp[p]].size()-temp<<endl;
                    printf("%d\n",num-(q>imp[isimp[p]-1]?0:1)+decc[isimp[p]].size()-temp);
                }
            }
            else{
                int temp=(int)(upper_bound(pos+1,pos+num+1,p)-pos);
                temp--;
                if (q<=imp[temp])printf("%d\n",num);
                else{
                    int temp1=(int)(upper_bound(imp+1,imp+num+1,q)-imp);
                    //cout<<temp+num-temp1+1+1<<endl;
                    printf("%d\n",temp+num-temp1+1+1);
                }

            }
        }
    }
}

Magic Square

题目链接

[[HDU 6401] 2018 Multi-University Training Contest 8--1005 Magic Square](http://acm.hdu.edu.cn/showproblem.php?pid=6401]

题解

简单题。题意大概是给定一个矩阵,要求你做出一些旋转操作后输出矩阵。
签到题,直接输出即可。

代码

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
typedef pair<int,int>P;
const int maxn=1e5+50;
string s[5];
string temp;
void zhuanc(char&lt,char&rt,char&ld,char&rd){
    char temp;
    temp=lt;
    lt=ld;
    ld=rd;
    rd=rt;
    rt=temp;
}
void zhuanr(char&lt,char&rt,char&ld,char&rd){
    char temp;
    temp=lt;
    lt=rt;
    rt=rd;
    rd=ld;
    ld=temp;
}
int main() {
    int n,t;
    for (cin>>t;t;t--){
        cin>>n;
        for (int i=0;i<=2;i++){
            cin>>s[i];
        }
        for (int i=1;i<=n;i++){
            cin>>temp;
            if (temp[0]=='1'){
                temp[1]=='C'?zhuanc(s[0][0],s[0][1],s[1][0],s[1][1]):zhuanr(s[0][0],s[0][1],s[1][0],s[1][1]);
            }
            else if (temp[0]=='2'){
                temp[1]=='C'?zhuanc(s[0][1],s[0][2],s[1][1],s[1][2]):zhuanr(s[0][1],s[0][2],s[1][1],s[1][2]);
            }
            else if (temp[0]=='3'){
                temp[1]=='C'?zhuanc(s[1][0],s[1][1],s[2][0],s[2][1]):zhuanr(s[1][0],s[1][1],s[2][0],s[2][1]);
            }
            if (temp[0]=='4'){
                temp[1]=='C'?zhuanc(s[1][1],s[1][2],s[2][1],s[2][2]):zhuanr(s[1][1],s[1][2],s[2][1],s[2][2]);
            }
        }
        for (int i=0;i<=2;i++){
            cout<<s[i]<<'\n';
        }

    }
    return 0;
}

Parentheses Matrix

题目连接

[HDU 6440] 2018 Multi-University Training Contest 8--1004 Parentheses Matrix

题解

中档题,结论题。题意大概是构造一个h行w列的矩阵由'(',')'组成,使得每行每列所组成的匹配的括号串数最大。

首先考虑行或列为奇数的情况,显然任意一个匹配的字符串其长度必然为偶数,所以我们只要考虑为偶数的那一侧即可。
当行或列均为偶数时,首先我们必然可以保证行或列单独一个完全符合匹配。具体如下

((((((
))))))
((((((
))))))

在此基础之上可以稍加改进使得另一侧有(n-2)/2的数量可以获得匹配,具体如下

((((((
()()()
)()()(
))))))

之后可以发现,若要使得第一行匹配,至多只可能有一半的列匹配,第一列匹配的情况同理。所以我们首相将第一行列与最后一行列稍加改进,具体如下

((((((
(....)
(....)
))))))

在此基础之上将中间空白部分交替排列即可做到行数+列数-4的匹配数量,具体如下:

((((((
(()())
()()()
))))))

当数据较小时这种匹配方式可能未必比前几种更优秀,但当数据量增大时显著比前几种更优。

代码

#include <bits/stdc++.h>

using namespace std;
char output[205][205];
int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t;
    for (cin >> t; t; t--) {
        int h,w;
        cin >> h >> w;
        if (h % 2) {
            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) {
                    putchar((j) % 2 ? '(' : ')');
                }
                putchar('\n');
            }
        } else
            if (w % 2) {
                for (int i = 1; i <= h; i++) {
                    for (int j = 1; j <= w; j++) {
                        putchar((i) % 2 ? '(' : ')');
                    }
                    putchar('\n');
                }
            } else {
                if (max(h,w)+(min(h,w)-2)/2>=h+w-4){
                if (h >= w) {
                    for (int i=1;i<=h;i++){
                        output[i][1]='(';
                        output[i][w]=')';
                    }
                    for (int i=1;i<=h;i++){
                        for (int j=2;j<=w-1;j++){
                            output[i][j]=(i+j)%2?'(':')';
                        }
                    }
                }
                else {
                    for (int i=1;i<=w;i++){
                        output[1][i]='(';
                        output[h][i]=')';
                    }
                    for (int i=2;i<=h-1;i++){
                        for (int j=1;j<=w;j++){
                            output[i][j]=(i+j)%2?'(':')';
                        }
                    }
                }
                for (int i=1;i<=h;i++){
                    for (int j=1;j<=w;j++){
                        putchar(output[i][j]);
                    }
                    putchar('\n');
                }}
                else {
                    for (int i=1;i<=h;i++){
                        for (int j=1;j<=w;j++){
                            if (i==1||j==1)output[i][j]='(';
                            else if (i==h||j==w)output[i][j]=')';
                            else output[i][j]=(i+j)%2?')':'(';
                        }
                    }
                    for (int i=1;i<=h;i++) {
                        for (int j = 1; j <= w; j++) {
                            putchar(output[i][j]);
                        }
                        putchar('\n');
                    }
                }
            }
    }
}