Timus 1219

系统 1743 0
      
        #include 
      
      
        <
      
      
        iostream
      
      
        >
      
      
        
#include
< fstream >
using namespace std;

unsigned
short counter_3D[ 26 ][ 26 ][ 26 ] = { 0 };
unsigned
short counter_2D[ 26 ][ 26 ] = { 0 };
unsigned
short counter_1D[ 26 ] = { 0 };
char ret[ 1000001 ] = { ' \0 ' };
char seq[ 3 ] = { 0 };


int cnt = 0 ,check[ 26 ] = { 0 }, check2D[ 26 ][ 26 ] = { 0 }, check3D[ 26 ][ 26 ][ 26 ] = { 0 };
char test[ 1000001 ] = { ' \0 ' };

int main() {

/* ofstream fout;
fout.open("output.txt");
*/

int i,p1,p2,p3,j,l1,l2,l3,tmp;
seq[
0 ] = seq[ 1 ] = 0 ;
p1
= 0 ; p2 = 1 ; p3 = 2 ;
ret[
0 ] = ret[ 1 ] = ' a ' ;

counter_2D[seq[
0 ]][seq[ 0 ]] ++ ;
counter_1D[seq[
0 ]] ++ ;
counter_1D[seq[
1 ]] ++ ;

for (i = 2 ;i < 1000000 ;i ++ ) {

l1
= seq[p1];
l2
= seq[p2];
for (j = 1 ;j <= 26 ;j ++ ) {
l3
= (seq[p3] + j) % 26 ;
if (counter_3D[l1][l2][l3] < 100 && counter_2D[l2][l3] < 2000 && counter_1D[l3] < 40000 ) {
ret[i]
= l3 + ' a ' ;
seq[p3]
= l3;
tmp
= p1;
p1
= p2;
p2
= p3;
p3
= tmp;
counter_3D[l1][l2][l3]
++ ;
counter_2D[l2][l3]
++ ;
counter_1D[l3]
++ ;
break ;
}
}
}

cout
<< ret;

return 0 ;
}
/* fout.close();
ifstream fin;
fin.open("output.txt",ios_base::in);

i = 0;
while(!fin.eof())
fin>>test[i++];

cnt = strlen(test);
cout<<"count:"<<cnt<<endl;

check[test[0]-'a']++;
check[test[1]-'a']++;
check2D[test[0] - 'a'][test[1] - 'a']++;

i = 2;
while(i < cnt ) {
check[test[i] - 'a']++;
check2D[test[i-1] - 'a'][test[i] - 'a']++;
check3D[test[i-2] - 'a'][test[i-1] - 'a'][test[i] - 'a']++;
i++;
}

for(int i=0;i<26;i++) {
if(check[i] > 40000) {
cout<<"1 D exceeds\n"<<endl;
return 0;
}
for(int j=0;j<26;j++) {
if(check2D[i][j] > 2000) {
cout<<"2 D exceeds"<<check2D[i][j]<<endl;
cout<<(char)(i + 'a')<<(char)(j + 'a')<<endl;
return 0;
}
for(int k=0;k<26;k++) {
if(check3D[i][j][k] > 100) {
cout<<"3 D exceeds"<<check3D[i][j][k]<<endl;
cout<<(char)(i + 'a')<<(char)(j + 'a')<<(char)(k + 'a')<<endl;
}
}
}
}

return 0;
}
*/

这题我的基本思路是,每次都根据前面的两个字母,来判断跟第三个字母构成的组合是否能用(超过出现次数就不能了)。

不过这里有个小问题就是,例如aaa, 如果循环下一个找的还是aaa,那么这样很快会耗掉"aaa"这组合的次数,通过验证这样的话构造不了1000000个。

但一个trick就是每次找的时候都从上一个找个字母的后一个字符开始,例如aaa,下一个找aab,然后找abc,bcd这样,马上就OK了 ^_^

Timus 1219


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论