hdu4333 Revolving Digits - exkmp

2024-05-12 00:18
文章标签 digits revolving exkmp hdu4333

本文主要是介绍hdu4333 Revolving Digits - exkmp,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4333

题意:多组数据,给一串数字,问每次旋转得到的数字串比原串小、等、大的数量。e.g.原串为"341",而3次旋转得到的数字串分别是:341、134、413。故答案输出1 1 1

题解:exkmp;题目中说的是能构成的不同的串,而当且仅当原串有循环节时所构成的串有重复(自己想想),所以先用next[]判断最短的循环节长度找到重复的次数,最后除掉。

哦,如何比较大小呢?看extend[]~若extend[i]>=n(原串长度),就是说该子串的前n个与原串完全匹配(就是相等啦);不然的话就直接比较失配处。
[忽然发现有0什么的用exkmp是不用管的除非暴力过什么的]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 201000int nt[maxn],extend[maxn];
char s[maxn];
int mymin(int x,int y){return (x<y)?x:y;}
int mymax(int x,int y){return (x>y)?x:y;}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int T,i,n,len,mx,id,L,E,G,as,Case=0;scanf("%d\n",&T);while (T--){memset(s,'\0',sizeof(s));gets(s+1);n=strlen(s+1);L=E=G=0;memset(nt,0,sizeof(nt));id=1;mx=0;nt[1]=n;as=n;for (i=2;i<=n;i++){if (mx>i+nt[i-id+1]-1) nt[i]=nt[i-id+1];else{nt[i]=mymax(mx-i+1,0);while (i+nt[i]<=n && s[i+nt[i]]==s[1+nt[i]]) nt[i]++;if (i+nt[i]-1>mx) mx=i+nt[i]-1,id=i;}if (i+nt[i]-1==n && n%(n-nt[i])==0) as=mymin(as,n-nt[i]);//找循环节orz}as=n/as;id=0;mx=0;//循环节的长度就是最后要除多少memset(extend,0,sizeof(extend));len=n*2;for (i=1;i<=n;i++) s[i+n]=s[i];for (i=1;i<=len;i++){extend[i]=mymin(nt[i-id+1],mymax(mx-i+1,0));while (1+extend[i]<=n && s[i+extend[i]]==s[1+extend[i]]) extend[i]++;if (i+extend[i]-1>mx) mx=i+extend[i]-1,id=i;}for (i=1;i<=n;i++)if (extend[i]>=n) E++;//与原串相等else if (s[i+extend[i]]>s[1+extend[i]]) G++;//比原串大else L++;//比原串小printf("Case %d: %d %d %d\n",++Case,L/as,E/as,G/as);}return 0;
}


这篇关于hdu4333 Revolving Digits - exkmp的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/981064

相关文章

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

ural 1014. Product of Digits贪心

1014. Product of Digits Time limit: 1.0 second Memory limit: 64 MB Your task is to find the minimal positive integer number  Q so that the product of digits of  Q is exactly equal to  N. Inpu

【FZU】2105 Digits Count 线段树

传送门:【FZU】2105 Digits Count 题目分析:与、或、异或三种操作都是每一位相互独立的,所以可以将线段树建四棵,分别对应一位,and和or操作相当于覆盖操作,xor操作相当于反转操作,就和普通的线段树方法类似,设立两个lazy标记即可。查询的时候求得每一位的1的个数*权重(1,2,4,8),全部累加就是答案。 代码如下: #include <cst

Subtract the Product and Sum of Digits of an Integer

Given an integer number n, return the difference between the product of its digits and the sum of its digits. Example 1: Input: n = 234Output: 15 Explanation: Product of digits = 2 * 3 * 4 = 24

java 2.6** Summing the digits in an integer

例如 : 999 process: sum=9+9+9=27; 例如 : 932 process: sum=9+3+2=14;   import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input=new Scanner(System.in);int

codeforces 289 C Sums of Digits

贪心,做了两个半小时没做出来!主要在于求有k位且恰比某个数大的最小值,从左到右检查可以加1的位,若后面的位满足条件,再根据solve中的方法满足条件的最小值。 #include<iostream>#include<string>#include<cstring>#include<cstdio>#include<cmath>#include<iomanip>#include<map

F - Problem where +s Separate Digits

算第三遍了。。都没有想透 。。 而且这题的解法非常多样。。有正序 逆序 递推的方式也非常多。 下面是找到的一个感觉相对比较简洁的。(核心代码) 有兴趣再看吧。。先pass了。 //上面都是mod的模版部分 省略掉 下面才是核心代码Z base[N], p[N];void solve() {string s;cin >> s;n = s.size();base[0] = 1;p[0] = 1

Add Digits问题及解法

问题描述: Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. 示例: Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit

HDU 4333 Revolving Digits 扩展KMP

题目来源:HDU 4333 Revolving Digits 题意:求一个数字循环移动后有多少个不同的小于 等于 大于的数字 思路:扩展KMP求出S[i..j]等于S[0..j-i]的最长前缀 判断 next[i] 大于等于n就是相同 小于n判断S[next[i]]和S[next[i]+i]的大小 next数组的含义就是S字符串以i开始的和S本身(以0开始)的最长公共前缀 把题目输入的复制一

uva11198 Dancing Digits

简单题,直接暴力,而且不需要太多剪枝就能过。 忘了写insert函数的返回值导致wa一次,怎么感觉oj上的编译器和我电脑上的g++不一样 #include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define HASHSIZE 40000#define MAX 50000using namespac