HDU 5442 Favorite Donut

2024-08-24 11:38
文章标签 hdu favorite donut 5442

本文主要是介绍HDU 5442 Favorite Donut，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一种方法，最小表示法
其实呢，你将每一个字母反转一下，将’a’变成’z’，就是最小表示法。
但是反转之后，我们如果用最小表示法，得到的是，在原串上位置最靠后的情况，与题意不服，所以我这里就强行将之往后硬判，最坏复杂度是当串所以的字符都相同的情况，退化成 O(n2) 。

//      whn6325689
//      Mr.Phoebe
//      http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<50
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define ls (idx<<1)
#define rs (idx<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=20010;char str[MAXN],rev[MAXN];
int n,ch[30];int init()
{int now='z';for(int i=0; i<26; i++)ch[i]=now--;
}int getsmall(string s, bool flag)
{int i,j,k,l;int N=s.length();s+=s;int ans=0;for(i=0,j=1; j<N;){for(k=0; k<N&&s[i+k]==s[j+k]; k++);if(k>=N){if(flag){ans=j;j++;continue;}break;}if(s[i+k]<s[j+k]){j+=k+1;}else{l=i+k;i=j;ans=i;j=max(l,j)+1;}}return ans;
}bool compare(int ans0,int ans1)
{int pos1=ans0,pos2=ans1;for(int i=0; i<n; i++){if(str[pos1]==str[pos2]){if(++pos1>=n) pos1-=n;if(--pos2<0) pos2+=n;}else{return str[pos1]>str[pos2];}}return ans0<=ans1;
}string st,en;int main()
{
//    freopen("data.txt", "r", stdin);init();int T;read(T);while(T--){st.clear();en.clear();read(n);scanf("%s",str);for(int i=0; i<n; i++)st+=ch[str[i]-'a'];en=st;reverse(en.begin(),en.end());int ans0=getsmall(st,false);int tmp=getsmall(en,true);int ans1=(n-tmp-1)%n;if (compare(ans0,ans1))printf("%d 0\n",ans0+1);elseprintf("%d 1\n",ans1+1);}return 0;
}

后缀数组法，裸的后缀数组应用

//      xixihaha
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define ls (idx<<1)
#define rs (idx<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=100010;char C[MAXN],rC[MAXN];
int idx[MAXN],mp[MAXN];int rk[MAXN],sa[MAXN],height[MAXN],w[MAXN],wa[MAXN],ret[MAXN];
void getSa (int len,int up)
{int *k = rk;int *id = height;int *r = ret;int  *cnt = wa;for(int i=0;i<up;i++) cnt[i] = 0;for(int i=0;i<len;i++) cnt[k[i] = w[i]]++;for(int i=0;i<up;i++) cnt[i+1] += cnt[i];for(int i = len - 1; i >= 0; i--) {sa[--cnt[k[i]]] = i;}for(int d = 1,p = 0; p < len;){for(int i = len - d; i < len; i++) id[p++] = i;for(int i=0;i<len;i++)if(sa[i] >= d) id[p++] = sa[i] - d;for(int i=0;i<len;i++) r[i] = k[id[i]];for(int i=0;i<up;i++) cnt[i] = 0;for(int i=0;i<len;i++) cnt[r[i]]++;for(int i=0;i<up;i++) cnt[i+1] += cnt[i];for(int i = len - 1; i >= 0; i--) {sa[--cnt[r[i]]] = id[i];}swap(k,r);p = 0;k[sa[0]] = p++;for(int i=0;i<len-1;i++) {if(sa[i]+d < len && sa[i+1]+d <len &&r[sa[i]] == r[sa[i+1]]&& r[sa[i]+d] == r[sa[i+1]+d])k[sa[i+1]] = p - 1;else k[sa[i+1]] = p++;}if(p >= len) return ;d *= 2,up = p, p = 0;}
}
void getHeight(int len) {for(int i=0;i<len;i++) rk[sa[i]] = i;height[0] =  0;for(int i = 0,p = 0; i < len - 1; i++) {int j = sa[rk[i]-1];while(i+p < len&& j+p < len&& w[i+p] == w[j+p]) {p++;}height[rk[i]] = p;p = max(0,p - 1);}
}
int getSuffix(char s[]) {int len = strlen(s),up = 0;for(int i = 0; i < len; i++) {w[i] = s[i];up = max(up,w[i]);}w[len++] = 0;getSa(len,up+1);getHeight(len);return len;
}int solve(char s[],int n)
{int len=getSuffix(s);/*   for(int i=1;i<len;i++){printf("%s\n",s+sa[i]);}*/int start=len-1;while(sa[start]>n/2)start--;int ans=idx[sa[start]];while(height[start]>=n/2){start--;ans=min(ans,idx[sa[start]]);}return ans;
}
int cmp(int x,int y,int n)
{for(int i=x,j=y,k=0;k<n;k++,i++,j++){if(C[i]==rC[j])continue;if(C[i]<rC[j])return -1;if(C[i]>rC[j])return 1;}return 0;
}
int main()
{//    freopen("in","r",stdin);int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);scanf("%s",C);for(int i=0;i<n;i++)rC[i]=C[i];reverse(rC,rC+n);for(int i=0;i<n;i++){C[i+n]=C[i];idx[i]=idx[i+n]=i;}C[n*2]='\0';int ans=solve(C,n*2),dir=0;for(int i=0;i<n;i++){rC[i+n]=rC[i];idx[i]=idx[n+i]=n-i-1;mp[n-i-1]=i;}rC[n*2]='\0';//        cout<<rC<<endl;int res=solve(rC,n*2);//        cout<<ans<<"!!"<<res<<endl;//        cout<<string(C+ans,n)<<endl;//        cout<<string(rC+mp[res],n)<<endl;int flag=cmp(ans,mp[res],n);if(flag==-1){ans=res,dir=1;}else if(flag==0){if(res<ans){ans=res;dir=1;}}printf("%d %d\n",ans+1,dir);}return 0;
}

这篇关于HDU 5442 Favorite Donut的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1102379。

相关文章

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 2093 考试排名（sscanf）

hdu 2093 考试排名（sscanf）

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。 这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
hdu 3790 (单源最短路dijkstra）

hdu 3790 (单源最短路dijkstra）

题意： 每条边都有长度d 和花费p，给你起点s 终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 解析： 考察对dijkstra的理解。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin
阅读更多...
hdu 2489 (dfs枚举 + prim)

hdu 2489 (dfs枚举 + prim)

题意： 对于一棵顶点和边都有权值的树，使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值，找到一个该图含有m 个顶点的子图，并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析： 因为数据量不大，先用dfs枚举搭配出m个子节点，算出点和，然后套个prim算出边和，每次比较大小即可。 dfs没有写好，A的老泪纵横。 错在把index在d
阅读更多...
hdu 1102 uva 10397（最小生成树prim）

hdu 1102 uva 10397（最小生成树prim）

hdu 1102: 题意： 给一个邻接矩阵，给一些村庄间已经修的路，问最小生成树。 解析： 把已经修的路的权值改为0，套个prim（）。 注意prim 最外层循坏为n-1。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2