cf 1511 D. Min Cost String

題意：

我們規定一個字符串的費用為存在一個i和j(i<j),然后s[i] = =s[j] && s[i+1] = =s[j+1]，組成字符串的字符必須是前k位
現在給你字符串的長度n和k，怎樣構造使得費用最少

題解：

其實第一個樣例就已經把答案說出來了。。
比賽時自己想的很近了，但是就是差一點，唉
構造題等告訴答案就很簡單了
為了讓費用最少，我們要盡可能實現更多的兩兩字符的組合
所以我們可以這樣構造，比如k為4，我們先讓a與b，c，d分別組合，然后b再和，c，d組合，然后 。。。這樣
但是這是其實還漏了一個情況，可以讓a和b組合+a和c組合+a和d組合，當然aa也是可以的
所以答案就是：aabacadbbcbd…
這樣構造出來是沒有費用的，有可能n很大，所以這個答案不斷復制，直到長度大于n，然后輸出前n項
（不難，但是一開始沒想到）

代碼：

#include<bits/stdc++.h> #define debug(x,y) printf("%s = %d\n",x,y); typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } int main() {int n,k;cin>>n>>k;string s;for(int i=0;i<k;i++){s+='a'+i;for(int j=i+1;j<k;j++){s+='a'+i;s+='a'+j;}}while(s.size()<n)s+=s;s.resize(n);cout<<s<<endl; } /* a abacad b bcbd */

總結

以上是生活随笔為你收集整理的cf 1511 D. Min Cost String的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。