Balala Power!
배 권 치 는 이 n 개의 수의 합 이 가장 크다.(선도 0 은 안 되 지만 한 개 0 은 가능 합 니 다)
문제 풀이: 모든 문자 가 답 에 기여 하 는 것 은 26 진법 의 숫자 로 볼 수 있 습 니 다. 문 제 는 이러한 공헌 에 0 에서 25 의 가중치 를 더 해서 답 을 가장 크게 하 는 것 과 같 습 니 다.최대 수 는 25 와 일치 하고, 큰 수 는 24 와 일치 하 며, 순서대로 유추 합 니 다.정렬 후 이렇게 순서대로 욕심 을 부리 면 되 는데, 유일 하 게 주의 하 는 것 은 선도 0 이 나타 나 면 안 된다 는 것 이다.
#include
#include
#include
#include
typedef long long ll;
const int mod =1e9+7;
const int maxn =1e5+5;
using namespace std;
ll fac[maxn]= {1}; // 26
int Hash[27]; //
bool lead[27]; //
char str[maxn];
struct node
{
int cnt[maxn];//
int id; //
bool operator < (const node &a)const
{
for(int i=maxn-1; i>=0; i--) //
{
if( cnt[i] >a.cnt[i] ) return 1;
else if(cnt[i] < a.cnt[i]) return 0;
}
}
} a[27];
int main()
{
//freopen("in.txt","r",stdin);
for(int i=1; i<maxn; i++)
{
fac[i]=fac[i-1]*26%mod;
}
int n,ca=1;
while(~scanf("%d",&n))
{
memset(a,0,sizeof(a));
memset(Hash,-1,sizeof(Hash));
memset(lead,0,sizeof(lead));
for(int i=1; i<=n; i++)
{
scanf("%s",str);
int len=strlen(str);
if(len != 1)
lead[str[0]-'a']=1;
for(int i=0; i<len; i++)
{
a[str[i]-'a'].cnt[len-i-1]++;
}
}
// , 26
for(int i=0; i<26; i++)
{
for(int j=0; j<maxn; j++)
{
if(a[i].cnt[j] >=26)
{
a[i].cnt[j+1] += a[i].cnt[j]/26;
a[i].cnt[j] %= 26;
}
}
a[i].id=i;
}
sort(a,a+26);
for(int i=0; i<26; i++) //
{
Hash[a[i].id]= 26-i-1;
}
for(int j = 25; j >= 0; j--)
{
if(!lead[a[j].id])
{
for(int k = 25; k >= j+1; k--)
Hash[a[k].id] = Hash[a[k-1].id];
Hash[a[j].id] = 0;
break;
}
}
ll ans=0;
for(int i=0; i<26; i++)
{
for(int j=0; j<maxn; j++)
{
ans= (ans+ fac[j]*a[i].cnt[j]*Hash[a[i].id]%mod) %mod;
}
}
printf("Case #%d: %lld
", ca++, ans);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.