noip模拟题day1
总览(Overview)
题目名称 |
取模 |
等比数列 |
回文串 |
程序名 |
mod |
sequence |
palindromes |
输入文件名 |
mod.in |
sequence.in |
palindromes.in |
输出文件名 |
mod.out |
sequence.out |
palindromes.out |
时间限制 |
1s |
1s |
2s |
空间限制 |
128M |
128M |
128M |
题目类型 |
传统题 |
传统题 |
传统题 |
取模(mod)
【题目描述】
有一个整数a和n个整数b_1, …, b_n。在这些数中选出若干个数并重新排列,得到c_1,…, c_r。我们想保证a mod c_1 mod c_2 mod … mod c_r=0。请你得出最小的r,也就是最少要选择多少个数字。如果无解,请输出-1.
【输入说明】
输入文件的第一行有一个正整数T,表示数据组数。
接下去有T组数据,每组数据的第一行有两个正整数n和a.
第二行有n个正整数b_1, …, b_n.
【输出说明】
一行,输出答案。
【样例输入】
2
2 9
2 7
2 9
6 7
【样例输出】
2
-1
【数据范围】
对于40%的数据,n<=8
对于100%的数据,T<=5,n<=20,1 <=a <=10^6,b_i<=10^6
暴力
#include<cstdio>
#include<algorithm>
#define inf 1e9
#define maxn 25
using namespace std;
int T,n,x,a[maxn],falg,ans;
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
int cmp(int x,int y){
return x>y;
}
int Min(int x,int y){
return x<y?x:y;
}
void Dfs(int now,int num,int s){
if(num>=ans)return;
if(s==){
ans=Min(ans,num);return;
}
if(now==n+)return;
if(s>=a[now])Dfs(now+,num+,s%a[now]);
Dfs(now+,num,s);
}
int main()
{
freopen("mod.in","r",stdin);
freopen("mod.out","w",stdout);
T=init();
while(T--){
n=init();x=init();
ans=inf;falg=;
a[]=;int c;
for(int i=;i<=n;i++){
c=init();
if(c<=x)a[++a[]]=c;
if(c==)falg=;
}
n=a[];if(x==)falg=;
if(falg){
printf("1\n");continue;
}
sort(a+,a++n,cmp);
Dfs(,,x);
if(ans==inf)printf("-1\n");
else printf("%d\n",ans);
}
fclose(stdin);fclose(stdout);
return ;
}
等比数列(sequence)
【题目描述】
判断一个数列是否为等比数列。
等比数列的定义为能被表示成a,aq,aq^2,aq^3...的数列,其中a和q不等于0。
【输入说明】
输入文件的第一行有一个正整数T,表示数据组数。
接下去有T组数据,每组数据的第一行一个整数n,接下来第二行n个数非负整数Ai,表示数列。
【输出说明】
对于每一个组的每个数据输出单独一行Yes或者No。
【样例输入】
2
3
1 1 1
3
1 4 2
【样例输出】
Yes
No
【数据范围】
对于40%的数据 0<=Ai<=10^9
对于100%的数据 T<=5,n<=1000,0<=Ai<=10^100
/*读题读题 首项公比不为0 */
#include<cstdio>
#include<cstring>
#define maxn 1010
using namespace std;
int T,n,A[maxn][],a[maxn],b[maxn];
char s[maxn];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
void Mul(int a[maxn],int b[maxn],int c[maxn]){
for(int i=;i<=a[];i++){
for(int j=;j<=b[];j++){
c[i+j-]+=a[i]*b[j];
if(c[i+j-]>){
c[i+j]+=c[i+j-]/;
c[i+j-]%=;
}
}
int p=b[]+i-;
while(c[p+]){
p++;c[p+]+=c[p]/;c[p]%=;
}
}
for(int i=a[]+b[];i>=;i--)
if(c[i]){
c[]=i;break;
}
}
bool Cmp(){
if(a[]!=b[])return ;
for(int i=;i<=a[];i++)
if(a[i]!=b[i])return ;
return ;
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
T=init();
while(T--){
memset(A,,sizeof(A));
n=init();int falg=;
for(int i=;i<=n;i++){
scanf("%s",s);
A[i][]=strlen(s);
for(int j=;j<=A[i][];j++)
A[i][j]=s[A[i][]-j]-'';
}
if(A[][]==&&A[][]==)falg=;
else if(A[][]==&&A[][]==)falg=;
else for(int i=;i<n;i++){
memset(a,,sizeof(a));
memset(b,,sizeof(b));
Mul(A[i-],A[i+],a);
Mul(A[i],A[i],b);
if(!Cmp()){
falg=;break;
}
}
if(falg)printf("No\n");
else printf("Yes\n");
}
fclose(stdin);fclose(stdout);
return ;
}
回文串(palindromes)
【题目描述】
判断是否能将字符串S分成三段非空回文串。
【输入说明】
第一行一个整数T,表示数据组数。
对于每一个组,仅包含一个由小写字母组成的串。
【输出说明】
对于每一组,单行输出"Yes" 或 "No"。
【样例输入】
2
abc
abaadada
【样例输出】
Yes
No
【数据范围】
对于40%的数据,|S|<=100
对于60%的数据,|S|<=1000
对于100%的数据,T<=20,|S|<=20000
乱搞80
/*hash+类似离散化的思想 80 已弃疗2333 */
#include<cstdio>
#include<cstring>
#define maxn 20010
#define P 29
#define ll long long
using namespace std;
ll T,n,A[maxn],B[maxn],a[maxn],b[maxn],p[maxn],falg;
char s[maxn];
void Get(){
p[]=;
for(int i=;i<=;i++)
p[i]=p[i-]*P;
}
void Hash1(){
A[]=;
for(int i=;i<=n;i++)
A[i]=A[i-]*P+s[i];
}
void Hash2(){
B[]=;
for(int i=;i<=n;i++)
B[i]=B[i-]*P+s[n-i+];
}
ll Query1(int l,int r){
return A[r]-A[l-]*p[r-l+];
}
ll Query2(int l,int r){
return B[r]-B[l-]*p[r-l+];
}
int main()
{
freopen("palindromes.in","r",stdin);
freopen("palindromes.out","w",stdout);
scanf("%d",&T);Get();
while(T--){
scanf("%s",s+);
n=strlen(s+);
a[]=;b[]=;
Hash1();Hash2();falg=;
for(int i=;i<=n;i++){
ll x=Query1(,i);
ll y=Query2(n-i+,n);
if(x==y)a[++a[]]=i;
}
for(int i=n;i>=;i--){
ll x=Query1(i,n);
ll y=Query2(,n-i+);
if(x==y)b[++b[]]=i;
}
for(int i=;i<=a[];i++){
for(int j=;j<=b[];j++){
if(a[i]+>b[j]-)break;
ll x=Query1(a[i]+,b[j]-);
ll y=Query2(n-b[j]+,n-a[i]);
if(x==y){
falg=;break;
}
}
if(falg)break;
}
if(falg)printf("Yes\n");
else printf("No\n");
}
fclose(stdin);fclose(stdout);
return ;
}
正解你猜