得分： (100+20+100=220)（还不错）
排名： (Rank 16)
(Rating)：(+20)
(T1)：【HHHOJ263】「NOIP模拟赛 玖」三个和尚（点此看题面）
第一眼看完毫无想法。
仔细思考，可以发现一个性质：只要原数数位之和(sum)不能被(3)整除，就说明无解。
然后就很简单了，只要使输出的(3)个数数位之和全部为(frac{sum}3)即可。
代码如下：
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define abs(x) ((x)<0?-(x):(x))
#define INF 1e9
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
#define ten(x) (((x)<<3)+((x)<<1))
#define N 10000
using namespace std;
int n=0,num[N+5];
class FIO
{
private:
#define Fsize 100000
#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)
#define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))
int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];
public:
FIO() {FinNow=FinEnd=Fin;}
inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}
inline bool read_digit(int &x) {while(!isdigit(x=tc())) if(!~x) return false;return x&=15,true;}
inline void read_char(char &x) {while(isspace(x=tc()));}
inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}
inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}
inline void write_char(char x) {pc(x);}
inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}
inline void end() {fwrite(Fout,1,FoutSize,stdout);}
}F;
inline void Solve(int x,int v)//x表示当前处理到的位数，v表示剩余的数位和
{
if(num[x]>=v) return (void)(F.write_char(v+48),num[x]-=v);//如果该位数字≥v，就输出v，并将该位数字减去v
Solve(x-1,v-num[x]),F.write_char(num[x]+48),num[x]=0;//如果该位数字<v，就处理更高的一位，然后输出该位数字（注意，这顺序不能反），然后将该位数字赋值为0
}
int main()
{
register int i,x,sum=0;
while(F.read_digit(x)) sum+=(num[++n]=x);//用sum统计数位之和
if(sum%3) return puts("-1"),0;//如果sum不能被3整除，说明无解
for(i=1;i<=3;++i) Solve(n,sum/3),F.write_char(' ');//输出答案
return F.end(),0;
}
(T2)：【HHHOJ264】「NOIP模拟赛 玖」疯狂祖玛（点此看题面）
比赛时写了一个区间(DP)，样例水过，交上去挂了，只有(20)分... ...
正解貌似是一个更加高级的区间(DP)，但是要用记忆化搜索实现，思路十分巧妙。
为了简便，我们可以用(NeedBall(x))表示有(x)个颜色相同且连续的珠子时还需加多少个珠子才能将其消掉。具体实现如下：
#define NeedBall(x) ((x)<k?k-(x):0)
首先，我们把颜色相同且连续的珠子压缩在一起，用(col_i)表示颜色，(num_i)表示个数。
然后，考虑用(f_{l,r,v})表示在编号为(r)的珠子右边有(v)个与(r)号珠子同色的珠子时，要把([l,r])区间内的珠子消完所需要增加的最少珠子数。
则有两种转移方式：
- 直接加上(Need(v+num_r))个珠子把(r)号珠子消掉。即(f_{l,r,v}=f_{l,r-1,0}+Need(v+num_r))。
- 找到([l,r])范围内的一个(i)使其满足(col_i=col_r)，我们可以选择将([i+1,r-1])之间的珠子消掉，然后将(i)和(r)两块珠子连在一起。即(f_{l,r,v}=min(f_{l,r,v},f_{l,i,min(k,v+num_r)}+f_{i+1,r-1,0}))。
代码如下：
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define abs(x) ((x)<0?-(x):(x))
#define INF 1e9
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
#define ten(x) (((x)<<3)+((x)<<1))
#define N 100
#define K 5
#define AddBalls(y,z) (s[++n]=Balls(y,z),lst[n]=End[y],End[y]=n)
#define NeedBall(x) ((x)<k?k-(x):0)//求出还需多少个球
using namespace std;
int n,k,lst[N+5],End[N+5];
struct Balls//记录连续一段颜色相同的求的信息
{
int col,num;//col记录颜色，num记录数量
Balls(int x=0,int y=0):col(x),num(y){}
}s[N+5];
class FIO
{
private:
#define Fsize 100000
#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)
#define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))
int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];
public:
FIO() {FinNow=FinEnd=Fin;}
inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}
inline void read_char(char &x) {while(isspace(x=tc()));}
inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}
inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}
inline void write_char(char x) {pc(x);}
inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}
inline void end() {fwrite(Fout,1,FoutSize,stdout);}
}F;
class Class_DP
{
private:
int f[N+5][N+5][K+5];//f[l][r][v]表示在编号为r的珠子右边有v个与r号珠子同色的珠子时，要把[l,r]区间内的珠子消完所需要增加的最少珠子数
public:
inline void Init() {for(register int i=0,j,l;i<=n;++i) for(j=i;j<=n;++j) for(l=0;l<=k;++l) f[i][j][l]=-1;}//初始化全部为-1，方便记忆化
inline int GetAns(int l,int r,int v)//记忆化搜索
{
if(~f[l][r][v]) return f[l][r][v];//如果已经求解过，返回求出的答案
register int i,t;
for(f[l][r][v]=GetAns(l,r-1,0)+NeedBall(s[r].num+v),i=l;i<r;++i)
if(!(s[i].col^s[r].col)) t=GetAns(l,i,min(k,s[r].num+v))+GetAns(i+1,r-1,0),f[l][r][v]=min(f[l][r][v],t);//状态转移
return f[l][r][v];
}
}DP;
int main()
{
register int i,nn,x,y,z=1;
for(F.read(nn),F.read(k),F.read(y),--nn;nn;--nn) F.read(x),(x^y?(AddBalls(y,z),y=x,z=1):++z);
return AddBalls(y,z),DP.Init(),F.write(DP.GetAns(1,n,0)),F.end(),0;//输出答案
}
(T3)：【HHHOJ265】「NOIP模拟赛 玖」回文单词（点此看题面）
说实话，这题就是一个比较简单的哈希。
考虑题意，其实不难有一个贪心的想法：每次选取最短的相同的前缀和后缀，将其从字符串中删去，并将答案加(1)。
关于如何求出最短的相同的前缀和后缀，我首先想到的是利用(KMP)算法的(Next)数组。
后来发现不行（因为前缀是在变化的）。
所以我们要用更灵活的字符串匹配方式：字符串哈希。
个人感觉得出上面那个结论，这道题就不难了。
具体实现可以看下面的代码：
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define abs(x) ((x)<0?-(x):(x))
#define INF 1e9
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
#define ten(x) (((x)<<3)+((x)<<1))
#define N 1000000
using namespace std;
string st;
class FIO
{
private:
#define Fsize 100000
#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)
#define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))
int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];
public:
FIO() {FinNow=FinEnd=Fin;}
inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}
inline void read_char(char &x) {while(isspace(x=tc()));}
inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}
inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}
inline void write_char(char x) {pc(x);}
inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}
inline void end() {fwrite(Fout,1,FoutSize,stdout);}
}F;
class Class_HashSolver//用字符串哈希求解答案
{
private:
struct Hash//双哈希
{
ull fir,sec;
Hash(ull x=0,ull y=0):fir(x),sec(y){}
}seed,s[N+5],t[N+5];
inline friend Hash operator + (Hash x,Hash y) {return Hash(x.fir+y.fir,x.sec+y.sec);}//重载加法
inline friend Hash operator - (Hash x,Hash y) {return Hash(x.fir-y.fir,x.sec-y.sec);}//重载减法
inline friend Hash operator * (Hash x,Hash y) {return Hash(x.fir*y.fir,x.sec*y.sec);}//重载乘法
inline friend bool operator == (Hash x,Hash y) {return !(x.fir^y.fir||x.sec^y.sec);}//重载等于号
public:
Class_HashSolver() {seed=Hash(31,41),t[0]=Hash(1,1);for(register int i=1;i<=N;++i) t[i]=t[i-1]*seed;}//初始化
inline void Init(string st) {s[0]=Hash(1,1);for(register int i=1,len=st.length();i<=len;++i) s[i]=s[i-1]*seed+Hash(st[i-1]&31,st[i-1]&31);}//对字符串进行哈希
inline bool check(int l1,int r1,int l2,int r2) {return (s[r1]-(s[l1-1]*t[r1-l1+1]))==(s[r2]-(s[l2-1]*t[r2-l2+1]));}//比较两段区间内的字符串是否相同
inline int GetAns(int l,int r)//求解[l,r]区间内的答案
{
if(l>r) return 0;
for(register int i=l;(i<<1)<(l+r);++i) if(check(l,i,l+r-i,r)) return GetAns(i+1,l+r-i-1)+2;//找到最短的相同的前缀和后缀，将其从字符串中删去，并将答案加2
return 1;//否则，这整个字符串对答案造成的贡献为1
}
}HashSolver;
int main()
{
register int T;F.read(T);
while(T--) F.read_string(st),HashSolver.Init(st),F.write(HashSolver.GetAns(1,st.length())),F.write_char('
');
return F.end(),0;
}