HDU 4162 Shape Number(字符串,最小表示法)

HDU 4162

题意:

给一个数字串(length <= 300,000),数字由0~7构成,求出一阶差分码,然后输出与该差分码循环同构的最小字典序差分码。

思路:

第一步是将差分码求出:s[i] = (s[i] - s[i+1] + 8) % 8;

第二步是求出最小字典序的循环同构差分码,我之前没注意到字符串规模。

。直接用set做,MLE+TLE。。。

正确的方式应该是一种O(n)的解法。即最小表示法。

//关于最小表示法的证明与详述请參考最小表示法:)

最小表示法算法:

初始时,i=0,j=1,分别以i,j。为起始点顺着i,j,往下比較直到找的str[i+k]!=str[j+k],然后分两种情况考虑:

1、  str[i+k]>str[j+k],i变成i=i+k+1。j不变,然后继续往下比較。

2、  str[i+k]<str[j+k],j变成j=j+k+1。i不变,然后继续往下比較。

直到i或j大于串长。找较小者。

最小表示法的实现代码是这种:

/*s表示字符串,l表示字符串长度,输出最小字符串起始位置*/
int MinimumRepresentation(char *s, int l)
{
int i = 0, j = 1, k = 0, t;
while(i < l && j < l && k < l) {
t = s[(i + k) >= l ? i + k - l : i + k] - s[(j + k) >= l ? j + k - l : j + k];
if(!t) k++;
else{
if(t > 0) i = i + k + 1;
else j = j + k + 1;
if(i == j) ++ j;
k = 0;
}
}
return (i < j ? i : j);
}

AC code:(这次代码写的太丑啦。。)

/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint; string s;
set<string>ss; int main(){
// freopen("input.txt","r",stdin);
while(cin >> s) {
// cout << s << endl;
ss.clear();
int len = s.length();
char tmp = s[0];
set<string>:: iterator it;
for(int i = 0 ; i < len - 1; i++){
if(s[i] > s[i+1])
s[i] = 8 - (s[i] - s[i+1]) + '0';
else s[i] = s[i+1] - s[i] + '0';
// cout << s[i] << ' ';
}
s[len-1] = (s[len-1]>tmp)? (8 - s[len-1] + tmp + '0') : (tmp - s[len-1] + '0');
// cout << s << endl;
int i = 0 , j = 1 , k = 0 , t;
while(i < len && j < len && k < len){
t = s[(i+k)] - s[(j+k)];
if(t == 0) k++;
else if(t > 0) i += k + 1;
else if(t < 0) j += k + 1;
if(t) k = 0;
if(i == j) j++;
}
int pos = min(i,j);
// cout << pos << endl;
for(int i = 0 ; i < len ; i++)
putchar(s[(i+pos) % len]);
cout << endl; // cout << s << endl; s.clear();
}
return 0;
}
上一篇:jquery 实现页面拖拽并保存到cookie


下一篇:WPF实现物理效果 拉一个小球