Codeforces Round #638 (Div. 2) ABC
1819 단어 Codeforces
제목:
아이디어:
코드:
B - Phoenix and Beauty
제목: 길이가 n인 서열 a, 1<=a[i]<=n을 지정하면 임의의 위치에 [1,n]의 숫자를 삽입하여 모든 길이가 k인 자단을 일치하게 할 수 있습니다.할 수 있는지 묻고, 할 수 있다면 최종 시퀀스를 출력합니다.
아이디어:
코드:
C - Phoenix and Distribution
제목: n 길이의 문자열을 정하고 알파벳 하나하나를 k개의 작은 문자열로 나누십시오. 이 k개의 작은 문자열 중 사전 순서가 가장 큰 문자열의 가장 작은 문자열은 무엇입니까?
욕심 전략:
1. 문자열을 사전순으로 작은 순서에서 큰 순서로 정렬하기
2. 이동한 후 k자모에서 k자모로 나누어 k개의 빈열에 넣는다(현재 k자 문자열은 각각 1자모를 포함한다)
3. 원열이 한 자모만 남으면 최소 자모로 시작하는 문자열에 균등하게 펼친다
4. 그렇지 않으면 나머지 모든 자모를 최소 자모의 뒤에 넣는다
5. 답은 첫 번째 문자열과 k번째 문자열 중 비교적 큰 자
가장 큰 문자열을 최소화해야 하기 때문에,
만약 1가지 문자만 남았다면 e.g.k=3, ab, ab, b | abb, a, b, 나머지 문자'b'를 균등하게 나누어야 한다. abb가 ab보다 크고 최소 자모의 문자열까지 균등하게 나누어야 하기 때문이다. 그렇지 않으면 답이 커질 수 있기 때문이다.
만약 한 글자만 남은 것이 아니라면, 남은 모든 문자를 최소 자모 뒤에 e.g.k=2, abz, ab | abbz, a, 남은 가장 큰 문자 'z' 를 모두 넣어야 하기 때문에, 문자열의 위치를 가능한 한 뒤로 돌려야만 답안을 최소화할 수 있다
//그래, 내 논리가 좀 더 유창했으면 좋겠어.
코드:
#include
using namespace std;
typedef long long ll;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,k;
scanf("%d%d",&n,&k);
string str;
cin>>str;
sort(str.begin(),str.end());
// cnt
auto pos=upper_bound(str.begin(),str.end(),str[0]);
int cnt;
if(pos==str.end()) cnt=k;
else cnt=pos-str.begin();
string s1,s2;
s1+=str[0],s2+=str[k-1];//
if(str[k]!=str[n-1]) { // 1
s1+=str.substr(k);
}else{ //
s1.insert(s1.end(),(n-k+cnt-1)/cnt,str[k]);
// (n-k+cnt-1)/cnt //(n-k)/cnt +1
}
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 1287C Garland제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.