Chieh's Blog

Because Of Coding

R307 DIV2 B. ZgukistringZ

Chieh posted @ 2015年6月13日 13:55 in codeforces , 583 阅读

飞机票：http://codeforces.com/contest/551/problem/B

题意:给你三个字符串，a,b,c，只包含小写字母,求字符串a重新排列后k包含最多的不重叠字串，为b或则为c.

分析：先想想先重组b或则c,会发现这个贪心不正确，因为可能重组一次b后，后面先重组c会比较优然后我就卡题了，一点感觉都没有，而且还分三种情况先b再c，或c再b，或则两个一起来，后面才发现这种贪心明显是错的，因为不是最优的。一直wa test12后来看了下字符串长度为1e5，可以暴力直接过。o(︶︿︶)o ，弱死了，想了半天，至于暴力，就是先预处理出都重组b的情况，假设为sum1,然后枚举sum1,推出重组c的情况sum2，求sum1+sum2的最大值，然后输出，复杂度0(sum1*26)sum1<=100000,所以还是非常快的，啪啪啪，就可以AC了

?
G++ code
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=123456;
char ch1[maxn];
char ch2[maxn];
char ch3[maxn];
int ai[27];
int bi[27];
int ci[27];
int len1,len2,len3;
void init()
{
    len1=strlen(ch1+1);
    len2=strlen(ch2+1);
    len3=strlen(ch3+1);
    memset(ai,0,sizeof(ai));
    memset(bi,0,sizeof(bi));
    memset(ci,0,sizeof(ci));
    for(int i=1; i<=len1; i++)
    {
        int t=ch1[i]-'a'+1;
        ai[t]++;
 
    }
    for(int i=1; i<=len2; i++)
    {
        int t=ch2[i]-'a'+1;
        bi[t]++;
    }
    for(int i=1; i<=len3; i++)
    {
        int t=ch3[i]-'a'+1;
        ci[t]++;
 
    }
}
void play()
{
 
    int sum1=1000000000;
    for(int i=1; i<=26; i++)
    {
        if(bi[i]>0)
        {
            sum1=min(sum1,ai[i]/bi[i]);
        }
    }
    int l=-1,r=-1;
    for(int i=0; i<=sum1; i++)
    {
        for(int j=1; j<=26; j++)
        {
            ai[j]-=(bi[j]*i);
        }
        int sum2=1000000000;
        for(int j=1; j<=26; j++)
        {
            if(ci[j]>0)
            {
                sum2=min(sum2,ai[j]/ci[j]);
            }
        }
        for(int j=1; j<=26; j++)
        {
            ai[j]+=(bi[j]*i);
        }
        if(l==-1&&r==-1)
        {
            l=i;
            r=sum2;
        }
        else
        {
            if(l+r<i+sum2)
            {
                l=i;
                r=sum2;
            }
        }
    }
    for(int i=1; i<=l; i++)printf("%s",ch2+1);
    for(int i=1; i<=r; i++)printf("%s",ch3+1);
    for(int i=1; i<=l; i++)
    {
        for(int j=1; j<=26; j++)
        {
            ai[j]-=bi[j];
        }
    }
    for(int i=1; i<=r; i++)
    {
        for(int j=1; j<=26; j++)
        {
            ai[j]-=ci[j];
        }
    }
    for(int i=1; i<=26; i++)
    {
        for(int j=1; j<=ai[i];j++)printf("%c",'a'+i-1);
    }
    printf("\n");
 
}
int main()
{
    while(scanf("%s%s%s",ch1+1,ch2+1,ch3+1)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter