个人感受：这一场考试是网开着的，然后第一题就水过了，第二三题应该是暴力吧，然后各水了50。拿了200分。排名第10。
问题 A: 重复字符串
时间限制: 1 Sec 内存限制: 256 MB
提交: 239 解决: 109
[提交][状态][讨论版]
题目描述
给定两个字符串a和b，我们可以定义一些操作：a*b为将字符串a和字符串b连接起来，比如a=
"aoe"，b=
"jkw"，那么a*b= "aoejkw"。进一步，我们可以有指数操作，a^0= ""， a^1=a， a^2=a*a， a^n=a*(a^(n-1))=a*a*…*a
(n个a)
现在给你一个字符串，你可以将它看成是a^n的形式，比如字符串"abababab"，可以认为是"abab"^2， 也可以是"abababab"^1，还可以是"ab"^4。
现在问题是，给定的字符串，我们想让它变成a^n中的n达到最大，那么这个n最大是多少？例如："abababab"最大的n是4。
输入
第一行，一个整数m，表示有m个字符串。
接下来m行每行输入一个只含小写字母的字符串。
输出
输出m行，对于每行输出相应字符串的最大n。
样例输入
3 abcde aaaaaa abababab
样例输出
1 6 4
这是第一题，考试时用力kmp的next数组的预处理，但是现在其实并不会，还得去学。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
;
char c[MM];
int cas,len,next[MM];
int main()
{
scanf("%d\n",&cas);
while (cas--)
{
memset(next,,sizeof(next));
gets(c);
len=strlen(c);
;i--)
c[i]=c[i-];
int k;
;i<=len;i++)
{
k=i-;
]!=c[i]&&k>)
k=next[k];
) next[i]=;
;
}
int ans=next[len];
)
{
printf("1\n");
continue;
}
,flag=;
while (i<=len)
{
)%ans+]!=c[i])
{
flag=;
break;
}
else i++;
}
) printf("1\n");
else printf("%d\n",len/(len-ans));
}
}问题 B: Fibonacci进制
时间限制: 1 Sec 内存限制: 256 MB
提交: 328 解决: 66
[提交][状态][讨论版]
题目描述
定义一种Fibonacci进制，可以将十进制数用Fibonacci数表示。Fibonacci进制中，每个位上的数值只有0或1，权值是Fibonacci数。令f0=f1=1，fi=fi-1+fi-2, N=an*fn+an-1*fn-1+…+a1*f1，写成N=anan-1..a2a1f。Fibonacci表示中，不能出现相邻的两个1。例如：自然数（十进制）表示为Fibonacci进制为1=1F，2=10F，3=100F，4=3+1=101F，5=1000F，6=5+1=1001F，7=5+2=1010F。
现在，Bsny将所有自然数按照Fibonacci进制，依次输出在屏幕上，110100101100010011010……现在，Bsny想知道这个长串的前N个数字中，包含多少个1。
输入
第一行一个整数N，表示统计范围是自然数的Fibonacci
表示的前N个数字
输出
一个数，前N个数字中1的个数。
样例输入
21
样例输出
10
提示
30% 的数据N≤1000；
50% 的数据N≤10；
100% 的数据N≤10。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
];
],n;
int mid_find(int x)
{
,r=,mid;
while (l<r)
{
mid=(l+r+)/;
;
else l=mid;
}
return l;
}
int get(int i,int ll)
{
,b[]={};
)
{
t=mid_find(i);
b[t]=;
i-=a[t];
}
,ii;
;ii>=;ii--)
) break;
;
for (int j=ii;j>=downn;j--)
{
) res++;
}
return res;
}
int main()
{
a[]=,a[]=;
;i<=;i++)
a[i]=a[i-]+a[i-];
scanf("%d",&n);
num[]=num[]=num[]=;
;
;i<=;i++)
{
];
])
{
now++;
num[i]=;
}
+num[k];
}
now=;
,i,ans=;
;i<=;i++)
{
]) now++;
zhi+=now,ans+=num[i];
if (zhi>=n) break;
}
if (zhi==n) printf("%d\n",ans);
else
{
zhi-=now;
n=n-zhi;
ans-=num[i];
ans+=get(i,n);
printf("%d\n",ans);
}
}问题 C: 发奖金
时间限制: 1 Sec 内存限制: 256 MB
提交: 203 解决:
17
[提交][状态][讨论版]
题目描述
Bsny最近公司运作不佳，本年度利润才m元，但员工的奖金还是要发的，公司有n个员工，怎么发奖金这个完全由老板Bsny自己决定。Bsny想要么把这m元全发了，激励一下员工，但具体怎么分配方案有很多。比如m=1, n=2, 那么可以员工1发1元，员工2发0元；也可以员工1发0元，员工2发1元，有两种方案。
但其实，Bsny还是有点吝啬的，他想这m元不一定全部作为奖金，可以部分留给自己，这样的话，发奖金的方案数就更多了。还是以m=1, n=2为例子：
方案1：员工1发1元，员工2发0元
方案2：员工1发0元，员工2发1元
方案3：员工1发0元，员工2发0元
意味着老板Bsny发的奖金范围为[0, m]。
好奇的Bsny想知道，给定n和m，他有多少种发奖金的方案？这个答案很大，所以再给定一个p，最终的答案取模p的余数.
输入
第一行三个整数n, m, p。
输出
仅一行，一个整数表示最终的答案取模p的余数。
样例输入
2 1 5
样例输出
3
提示
对于p：设p=p1^c1 * p2^c2 * p3^c3 * … *pt ^ ct ，pi为质数。
20% 的数据：1 ≤ n, m≤ 15
40% 的数据：1≤n, m≤1000，p=10007；
60%的数据：保证t=1，ci=1，pi^ci≤10^5 ；
80%的数据：t≤2，ci=1，pi≤10^5；
100% 的数据：1≤ n, m≤10^9，1≤pi^ci≤10^5，所有P不超过2^31-1。
这道题n^2预处理了以每个人为队长的情况，然后暴力，水了50分。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int n,m,p,sum;
];
int main()
{
memset(num,,sizeof(num));
scanf("%d%d%d",&n,&m,&p);
sum=n+m;
;i<=sum;i++)
{
int k=i,up=(int)sqrt(i);
;j<=up;j++)
{
)
{
num[j]++;
k=k/j;
}
}
) num[k]++;
}
;i<=m;i++)
{
int k=i,up=(int)sqrt(i);
;j<=up;j++)
{
)
{
num[j]--;
k=k/j;
}
}
) num[k]--;
}
;
;i<=;i++)
while (num[i])
{
num[i]--;
ans=(ans*i)%p;
}
printf("%lld\n",ans);
}