Codeforces Round #603 (Div. 2)补题

发表于 更新于 分类于 阅读次数：

手速场……
我们的知识面还不够广……
Standing 2438，Rating1394 → 1404
排在三题末尾，能力全方位缺失

本场关键词

乱搞、STL-map、整除分块、并查集、前缀和、线段树维护区间前缀和极大极小值

A. Sweet Problem

题意

有三堆颜色不同的糖，最多可以凑成颜色不同的多少对。

思路

分类讨论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=0x3f3f3f3f;
int main()
{
    ll t,c[3];
    cin>>t;
    while(t--)
    {
        for(int i=0;i<3;i++)
            cin>>c[i];
        sort(c,c+3);
//        for(int i=0;i<3;i++)
//            cout<<c[i]<<endl;
        ll diss=c[2]-c[1];
        ll cnt=0;
        if(c[0]+c[1]<=c[2])//c[0]全部取走
        {
            cnt=c[0]+c[1];
        }
        else{
            cnt=c[2]+(c[0]+c[1]-c[2])/2;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

B. PIN Codes

面向范围编程

思路

因为n<=10，所以重复数字只需要修改一位。
用map统计重复的数量，并进行计算。
n<=10，直接暴力枚举查询修改即可

AC的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f,maxn=204;
string s[maxn];
int c[maxn]={0};
map<string,int>QAQ;
int main()
{
//    freopen("B.txt","r",stdin);
    int t,n;
    cin>>t;
    while(t--)
    {
        QAQ.clear();
        cin>>n;
        int cnt=0;
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++)
        {
            cin>>s[i];
            if(QAQ[s[i]]==0)
                QAQ[s[i]]=++cnt;//编号
            c[QAQ[s[i]]]++;//数量++
        }
        int ans=0;
        for(int i=1;i<=cnt;i++)
            ans+=c[i]-1;
        cout<<ans<<endl;
        for(int i=0;i<n;i++)
        {
            int no=QAQ[s[i]];
            if(c[no]>1)
            {
                bool flag=0;
                for(int j=3;j>=0;j--)//枚举位数
                {
                    string tem=s[i];
                    for(int k=0;k<=9;k++)//枚举符号
                    {
                        tem[j]='0'+k;
//                        cout<<"tem="<<tem<<endl;
                        if(QAQ[tem]>0)//重复
                        {
                            continue;
                        }
                        QAQ[tem]=++cnt;
                        flag=1;
                        cout<<tem<<endl;
                        c[no]--;
//                        printf("c[%d]=%d\n",no,c[no]);
                        c[QAQ[tem]]=1;
                        if(flag)
                            break;
                    }
                    if(flag)
                        break;
                }
            }
            else
                cout<<s[i]<<endl;
//            printf("c[%d]=%d\n",no,c[no]);
            label:
                continue;
        }
    }
    return 0;
}

C. Everyone is a Winner!

整除分块，CF上难得一见的模板裸题
第一遍用了set来去重，nlogn直接T飞

AC的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int main()
{
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
    {
        ll n,cnt=1;
        cin>>n;
        stack<ll> ans;
//        set<ll> ans;
////        ans.clear();
//        ans.insert(0);
//        for(ll i=1;i<=n;i++)
//            ans.insert(n/i);
//        cout<<ans.size()<<'\n';
//        for(set<ll>::iterator it=ans.begin();it!=ans.end();it++)
//            cout<<*it<<' ';
        for (int l=1,r;l<=n;l=r+1)
        {
            r=n/(n/l);
            ans.push(n/l);
            cnt++;
        }
        cout<<cnt<<'\n';
        ans.push(0);
        while(!ans.empty())
        {
            cout<<ans.top()<<' ';
            ans.pop();
        }
        cout<<'\n';
    }
    return 0;
}

D. Secret Passwords

题意

给你n个字符串，只要含有相同字母的字符串就归为一组，关系可传递。问你最后有多少个集合。

思路

并查集胡搞。
在B上浪费了太多时间，在最后一分钟过了C，应该给我发个顽强拼搏奖hhh。
没时间开D，如果当时有时间的话，多半也是过不去的。
如果当时有时间看这题肯定会往并查集的方向想，但因为读题出现错误，误以为是求最小集合的大小，在这上就会卡住。
还有一个难点就是如何处理26个字母和字符串的关系（当然这个对诸位大神好像也不是很难）

AC的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int father[maxn];//
int findfa(int x)
{
    if(x!=father[x])
        father[x]=findfa(father[x]);
    return father[x];
}
bool Merge(int x,int y)
{
    int a=findfa(x),b=findfa(y);
    if(a==b)
        return 0;
    if(a<b)
        father[b]=a;
    else
        father[a]=b;
    return 1;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        father[i]=i;//
    vector<int> table[27];//记录每个字母含有的字符串编号
    string a;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        bool vis[30]={0};
        for(int j=0;j<a.length();j++)
        {
            if(!vis[a[j]-'a'+1])//只加一次
                vis[a[j]-'a'+1]=1;
            else
                continue;
            table[a[j]-'a'+1].push_back(i);
        }
    }
    int ans=n;
    for(int i=1;i<=26;i++)//含有相同的字母分在一组
    {
        if(table[i].empty())//必须有这个
            continue;
        int now=table[i][0];//该组第一个字符串的编号
        for(int j=1;j<table[i].size();j++)//整组合并
        {
            if(Merge(now,table[i][j]))
                ans--;
        }
    }
    cout<<ans<<endl;
    return 0;
}

E. Editor

题意

洛谷题目
只有一行的打字机，光标只指向一个字符，一开始指向最左侧的字符。
有三种操作

  • L，左移一格
  • R，右移一个
  • 在当前位置写下指定字符
    给出操作序列，在每次操作后，判断当前行括号是否合法。
    不合法输出-1，否则输出括号最大嵌套层数。

思路

括号匹配常见的前缀和，强制在线。
将(权值看作1，将)权值看作-1，并用线段树维护。
判断当前序列是否合法：

  • 前缀和最终等于0
  • 所有前缀和都不为负

括号的最大嵌套层数就是前缀和的最大值。
注意将(修改为)或)修改为(的情况。
n次操作，可能达到的最右端点即为n。
线段树维护当前区间前缀和极大极小值
单点修改，维护区间和及前缀和最值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000005,inf=0x3f3f3f3f;
struct node
{
    ll val,ma,mi;
    node()
    {
        val=ma=mi=0;
    }
} tree[maxn<<2];
inline void pushup(int root)
{
    tree[root].val=tree[root<<1].val+tree[root<<1|1].val;
    tree[root].ma=max(tree[root<<1].ma,tree[root<<1].val+tree[root<<1|1].ma);//维护子区间最大前缀和,tree[1]维护的即为总区间最大/最小前缀和
    tree[root].mi=min(tree[root<<1].mi,tree[root<<1].val+tree[root<<1|1].mi);//维护区间最小前缀和
}
void modify(int root,int l,int r,int q,ll num)
{
    if(l==r&&l==q)
    {
        tree[root].val=tree[root].ma=tree[root].mi=num;
        return;
    }
    int mid=(l+r)>>1;
    if(q<=mid)
        modify(root<<1,l,mid,q,num);
    else
        modify(root<<1|1,mid+1,r,q,num);
    pushup(root);
}
char s[maxn];
int main()
{
    int n;
    cin>>n>>s;
    int cur=1;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='R')
            cur++;
        else if(s[i]=='L')
        {
            if(cur>1)
                cur--;
        }
        else if(s[i]=='(')
            modify(1,1,n,cur,1);
        else if(s[i]==')')
            modify(1,1,n,cur,-1);
        else//字母,该节点权值改为0
            modify(1,1,n,cur,0);
        if(tree[1].mi<0||tree[1].val!=0)//tree[1].val维护的为总区间和
            cout<<"-1 ";//tree[1].mi维护的即为总区间最小前缀和
        else
            cout<<tree[1].ma<<' ';
    }
    return 0;
}

2019年11月30日19点30分