首页 > 其他分享 >HDU 5442 Favorite Donut

HDU 5442 Favorite Donut

时间:2022-11-09 22:37:55浏览次数:46  
标签:case HDU return int 5442 Favorite donut flag ring

Problem Description Lulu has a sweet tooth. Her favorite food is ring donut. Everyday she buys a ring donut from the same bakery. A ring donut is consists of  n  parts. Every part has its own sugariness that can be expressed by a letter from  a  to  z  (from low to high), and a ring donut can be expressed by a string whose i-th character represents the sugariness of the  i−th  part in clockwise order. Note that  z  is the sweetest, and two parts are equally sweet if they have the same sugariness.

Once Lulu eats a part of the donut, she must continue to eat its uneaten adjacent part until all parts are eaten. Therefore, she has to eat either clockwise or counter-clockwise after her first bite, and there are  2n  ways to eat the ring donut of  n  parts. For example, Lulu has  6  ways to eat a ring donut  abc :  abc,bca,cab,acb,bac,cba . Lulu likes eating the sweetest part first, so she actually prefer the way of the greatest lexicographic order. If there are two or more lexicographic maxima, then she will prefer the way whose starting part has the minimum index in clockwise order. If two ways start at the same part, then she will prefer eating the donut in clockwise order. Please compute the way to eat the donut she likes most.  
Input First line contain one integer  T,T≤20 , which means the number of test case.

For each test case, the first line contains one integer  n,n≤20000 , which represents how many parts the ring donut has. The next line contains a string consisted of  n  lowercase alphabets representing the ring donut.  
Output You should print one line for each test case, consisted of two integers, which represents the starting point (from  1  to  n ) and the direction ( 0  for clockwise and  1  for counterclockwise).  
Sample Input 2 4 abab 4 aaab  
Sample Output 2 0 4 0  


最小表示法

正向直接上,逆向来个二分

#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
const int maxn = 100001;
int n,T,f[maxn];
char s[maxn],S[maxn];

int cmp(int x, char a, char b)
{
    if (a > b) return x - 0;
    if (a < b) return 1 - x;
    return 2;
}

int present(int z)
{
    int i, j, k, x, y;
    for (i = 0, j = 1, k = 0; k < n;)
    {
        if (i == j) { j++; k = 0; }
        x = (i + k) % n;    y = (j + k) % n;
        switch (cmp(z, s[x], s[y]))
        {
            case 0:i += k + 1; k = 0; break;
            case 1:j += k + 1; k = 0; break;
            case 2:k++; break;
        }
    }
    return min(i, j);
}

int Present(int z,int a,int b)
{
    int i, j, k, x, y;
    //int tot=n;
    //memset(f,0,sizeof(f));
    for (i = a, j = b, k = 0; k < n;)
    {
        if (i == j) { j--; k = 0; }
        x = ((i - k) % n + n)%n;
        y = ((j - k) % n + n)%n;
        switch (cmp(z, s[x], s[y]))
        {
            case 0:i -= k + 1; k = 0; break;
            case 1:j -= k + 1; k = 0; break;
            case 2:k++; break;
        }
    }
    return max(i, j);
}

int get()
{
    int l=1,r=n-1,mid,ans;
    while (l<r)
    {
        mid=(l+r)>>1;
        ans=Present(1,mid,mid-1);
        if (ans>=0) r=mid;
        else l=mid+1;
    }
    ans=Present(1,r,r-1);
    return ans;
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%s",&n,s);
        if (n==1) printf("1 0\n");
        else 
        {
            int v1=present(1);
            int v2=get();
            int flag=-1;
            for (int i=0;i<n;i++)
            {
                char c1=s[(v1+i)%n];
                char c2=s[(v2-i+n)%n];
                if (c1>c2) {flag=0;    break;}
                if (c1<c2) {flag=1; break;}
            }
            if (flag==-1)
            {
                if (v1>v2) flag=1;
                else flag=0;
            }
            if (flag) printf("%d %d\n",v2+1,flag);
            else printf("%d %d\n",v1+1,flag);
        }
    }
    return 0;
}


标签:case,HDU,return,int,5442,Favorite,donut,flag,ring
From: https://blog.51cto.com/u_15870896/5838873

相关文章

  • HDU 3518 Boring counting
    Description035nowfacedatoughproblem,hisenglishteachergiveshimastring,whichconsistswithnlowercaseletter,hemustfigureouthowmanysub......
  • HDU 4210 Su-domino-ku
    ProblemDescriptionAsiftherewerenotalreadyenoughsudoku-likepuzzles,theJuly2009issueofGamesMagazinedescribesthefollowingvariantthat......
  • HDU 5722 Jewelry
    ProblemDescriptionAfterallthedifficulties,PsycheandCupidarefinallygettingmarried.NoordinarypearlscanholdCupid'sloveforPsyche.So......
  • HDU 3713 Double Maze
    ProblemDescriptionUnlikesinglemaze,doublemazerequiresacommonsequenceofcommandstosolvebothmazes.Seethefigurebelowforaquickunderst......
  • HDU 3442 Three Kingdoms
    ProblemDescriptionThreeKingdomsisafunnygame.OftenLiuBeiisweakandhastorunaway,sointhegameLiuBeihasaskillcalled"Dunzou".Thist......
  • HDU 4127 Flood-it!
    ProblemDescriptionFlood-itisafascinatingpuzzlegameonGoogle+platform.Thegameinterfaceislikefollows:Atthebeginningofthegame,sys......
  • HDU 2757 Ocean Currents
    ProblemDescriptionForaboatonalargebodyofwater,strongcurrentscanbedangerous,butwithcarefulplanning,theycanbeharnessedtohelpthe......
  • HDU 1252 Hike on a Graph
    ProblemDescription"HikeonaGraph"isagamethatisplayedonaboardonwhichanundirectedgraphisdrawn.Thegraphiscompleteandhasallloops......
  • HDU 3345 War Chess
    ProblemDescriptionWarchessishh'sfavoritegame:Inthisgame,thereisanN*Mbattlemap,andeveryplayerhashisownMovingVal(MV).Ineach......
  • HDU 2660 Accepted Necklace
    ProblemDescriptionIhaveNpreciousstones,andplantouseKofthemtomakeanecklaceformymother,butshewon'tacceptanecklacewhichistooh......