uva 10785 The Mad Numerologist

2016年1月27日 0 作者 CrazyKK

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1726
题意：给出26个大写字母的权值，要求构造一个长度为n（n不超过210）的字符串。并且满足奇数位置只能放元音字母，偶数位置只能放辅音字母，且每个元音字母最多放21次，每个辅音字母最多放5次，要求构造的字符串的权值之和最小，在权值最小的前提下字典序最小。

思路：贪心。一开始错误得以为不是完整得不能交换（也就是不完整的字母只能放在最后，这是错误的）。但实际上只要每个字母的数量不变，那么就不影响权值。所以做法是，奇数位置偶数位置分别搞，先把构成字符串的字母按次存入，然后排序一下，输出即可。




/* ***********************************************
Author :111qqz
Created Time :2016年01月26日 星期二 15时10分28秒
File Name :code/uva/10785.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;


char a[30],b[30];
char oddans[210],evenans[210];
int n;
void pre()
{
    a[1]='A';
    a[2]='U';
    a[3]='E';
    a[4]='O';
    a[5]='I';

    b[1]='J';
    b[2]='S';
    b[3]='B';
    b[4]='K';
    b[5]='T';
    b[6]='C';
    b[7]='L';
    b[8]='D';
    b[9]='M';
    b[10]='V';
    b[11]='N';
    b[12]='W';
    b[13]='F';
    b[14]='X';
    b[15]='G';
    b[16]='P';
    b[17]='Y';
    b[18]='H';
    b[19]='Q';
    b[20]='Z';
    b[21]='R';


}

void solve ()
{
    int odd = (n+1)/2;
    int even = n/2;

    int vowa = odd/21;
    int vowr = odd%21;
    int cona = even/5;
    int conr = even%5;

    int cnt  = 0 ;
    for ( int i = 1 ; i <= vowa ; i++)
    {
	for ( int j =1 ; j <=21 ; j++)
	{
		cnt++;
		oddans[cnt] = a[i];
	}
    }

    for ( int i = 1 ; i <=vowr ; i++)
    {
	cnt++;
	oddans[cnt]=a[vowa+1];
    }
    
    cnt = 0 ;
    for ( int i = 1 ; i <= cona ; i++)
    {
	for ( int j = 1 ; j <= 5 ; j++)
	{
	    cnt++;
	    evenans[cnt]=b[i];
	}
    }
    for ( int i = 1 ; i <=conr ; i++)
    {
	cnt++;
	evenans[cnt]=b[cona+1];
    }

    sort(oddans+1,oddans+odd+1);
    sort(evenans+1,evenans+even+1);

    for ( int i = 1 ;i  <= n ; i++)
    {
	if (i%2==1)
	{
	    printf("%c",oddans[i/2+1]);
	}
	else
	{
	    printf("%c",evenans[i/2]);
	}
    }
    puts("");
}

int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	pre();
	//cout<<good<<endl;
	int T;             //之前想错了。以为不是完整的就必须在最后。但是实际上只要数量不变就不影响权值和。那么在这个前提下就应该把非完整的字典序小的放在前面。
	cin>>T;
	int cas = 0 ;
	while (T--)
	{
	    printf("Case %d: ",++cas);
	    scanf("%d",&n);
	    solve();
	}
	
	

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

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

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

/* ***********************************************

Author :111qqz

Created Time :2016年01月26日星期二 15时10分28秒

File Name :code/uva/10785.cpp

************************************************ */

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

#include <ctime>

#define fst first

#define sec second

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ms(a,x) memset(a,x,sizeof(a))

typedef long long LL;

#define pi pair < int ,int >

#define MP make_pair

using namespace std;

const double eps = 1E-8;

const int dx4[4]={1,0,0,-1};

const int dy4[4]={0,-1,1,0};

const int inf = 0x3f3f3f3f;

char a[30],b[30];

char oddans[210],evenans[210];

int n;

void pre()

{

a[1]='A';

a[2]='U';

a[3]='E';

a[4]='O';

a[5]='I';

b[1]='J';

b[2]='S';

b[3]='B';

b[4]='K';

b[5]='T';

b[6]='C';

b[7]='L';

b[8]='D';

b[9]='M';

b[10]='V';

b[11]='N';

b[12]='W';

b[13]='F';

b[14]='X';

b[15]='G';

b[16]='P';

b[17]='Y';

b[18]='H';

b[19]='Q';

b[20]='Z';

b[21]='R';

}

void solve ()

{

int odd = (n+1)/2;

int even = n/2;

int vowa = odd/21;

int vowr = odd%21;

int cona = even/5;

int conr = even%5;

int cnt = 0 ;

for ( int i = 1 ; i <= vowa ; i++)

{

for ( int j =1 ; j <=21 ; j++)

{

cnt++;

oddans[cnt] = a[i];

}

for ( int i = 1 ; i <=vowr ; i++)

{

cnt++;

oddans[cnt]=a[vowa+1];

}

cnt = 0 ;

for ( int i = 1 ; i <= cona ; i++)

{

for ( int j = 1 ; j <= 5 ; j++)

{

cnt++;

evenans[cnt]=b[i];

}

for ( int i = 1 ; i <=conr ; i++)

{

cnt++;

evenans[cnt]=b[cona+1];

}

sort(oddans+1,oddans+odd+1);

sort(evenans+1,evenans+even+1);

for ( int i = 1 ;i <= n ; i++)

{

if (i%2==1)

{

printf("%c",oddans[i/2+1]);

}

else

{

printf("%c",evenans[i/2]);

}

puts("");

}

int main()

{

#ifndef ONLINE_JUDGE

freopen("code/in.txt","r",stdin);

#endif

pre();

//cout<<good<<endl;

int T; //之前想错了。以为不是完整的就必须在最后。但是实际上只要数量不变就不影响权值和。那么在这个前提下就应该把非完整的字典序小的放在前面。

cin>>T;

int cas = 0 ;

while (T--)

{

printf("Case %d: ",++cas);

scanf("%d",&n);

solve();

}

#ifndef ONLINE_JUDGE

fclose(stdin);

#endif

return 0;

}

分类目录uva 白书

标签greedy 字符串构造

关于作者

CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！