ACM

2016

hdu 5835 || ccpc 2016 网络赛 1004 Danganronpa (模拟)

2016-08-14·2 分钟

hdu 5835 题目链接题意：n种礼物，每种a[i]个。现在有无穷个小朋友排成一排，分给每个人一个“普通”的礼物，一个“昂贵”的礼物（哪个普通哪个昂贵是自己定的，或者说，任意的）要求是相邻的小朋友的普通的礼物不能是同一种。现在问最多能给多少小朋友分礼物。。。

hdu 5842 || 2016 ccpc 网络赛 1011 Lweb and String（set）

2016-08-14·1 分钟

ACM Set

hdu 5842题目链接题意：给一个只由小写字母组成的字符串，每个字符映射到一个数字，问映射之后的最长上升子序列的长度。。

hdu 3374 String Problem (字符串的最小/大表示法+kmp)

2016-08-12·2 分钟

ACM Kmp 字符串循环同构最小表示法

hdu 3374 题目链接题意：给出一个循环字符串，问最小表示出现的位置以及次数，最大表示出现的位置以及次数。思路：之前只写过最小表示。。最大表示其实是一样的。。。把不等式方向变号即可。。。对于出现的次数。。。其实就等同于这个字符串是由几个子串组成。。。跑一遍kmp。。答案为len-nxt[len]，1A

hdu 2609 How many (字符串的最小表示法+set)

2016-08-12·1 分钟

ACM Set 字符串循环同构最小表示法

hdu 2609 题目链接题意：给出n个循环字符串，问有多少种。思路：将每个字符串换成最小表示，然后set存一下即可。

hdu 4162 Shape Number (字符串的最小表示法)

2016-08-12·1 分钟

ACM 字符串循环同构最小表示法

hdu 4162 题意：给出一串代表8个方向的数字，求这串序列的一阶差分（the first difference）的字典序最小的表示。

poj 1509 Glass Beads (字符串的最小表示法)

2016-08-12·1 分钟

ACM 最小表示法

poj 1509 题目链接题意&思路：同uva 1314 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日星期五 18时48分29秒 4File Name :code/uva/1314.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E5+7; 34int n ; 35char s[N]; 36int minRep(char *s) 37{ 38 int n = strlen(s); 39 int i = 0; 40 int j = 1; 41 int k = 0; 42 while (i<n&&j<n&&k<n) 43 { 44 int t = s[(i+k)%n]-s[(j+k)%n]; 45 if (t==0) k++; 46 else 47 { 48 if (t>0) 49 i+=k+1; 50 else j+=k+1; 51 if (i==j) j++; 52 k = 0 ; 53 } 54 } 55 return i<j?i:j; 56} 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 int T; 63 cin>>T; 64 while (T--) 65 { 66 scanf("%s",s); 67 printf("%d\n",minRep(s)+1); 68 } 69 #ifndef ONLINE_JUDGE 70 fclose(stdin); 71 #endif 72 return 0; 73}