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=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';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==0){ ans=Min(ans,num);return; } if(now==n+1)return; if(s>=a[now])Dfs(now+1,num+1,s%a[now]); Dfs(now+1,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=0; a[0]=0;int c; for(int i=1;i<=n;i++){ c=init(); if(c<=x)a[++a[0]]=c; if(c==1)falg=1; } n=a[0];if(x==0)falg=0; if(falg){ printf("1 ");continue; } sort(a+1,a+1+n,cmp); Dfs(1,0,x); if(ans==inf)printf("-1 "); else printf("%d ",ans); } fclose(stdin);fclose(stdout); return 0; }
等比数列(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][110],a[maxn],b[maxn]; char s[maxn]; int init(){ int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void Mul(int a[maxn],int b[maxn],int c[maxn]){ for(int i=1;i<=a[0];i++){ for(int j=1;j<=b[0];j++){ c[i+j-1]+=a[i]*b[j]; if(c[i+j-1]>9){ c[i+j]+=c[i+j-1]/10; c[i+j-1]%=10; } } int p=b[0]+i-1; while(c[p+1]){ p++;c[p+1]+=c[p]/10;c[p]%=10; } } for(int i=a[0]+b[0];i>=1;i--) if(c[i]){ c[0]=i;break; } } bool Cmp(){ if(a[0]!=b[0])return 0; for(int i=1;i<=a[0];i++) if(a[i]!=b[i])return 0; return 1; } int main() { freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); T=init(); while(T--){ memset(A,0,sizeof(A)); n=init();int falg=0; for(int i=1;i<=n;i++){ scanf("%s",s); A[i][0]=strlen(s); for(int j=1;j<=A[i][0];j++) A[i][j]=s[A[i][0]-j]-'0'; } if(A[1][0]==1&&A[1][1]==0)falg=1; else if(A[2][0]==1&&A[2][1]==0)falg=1; else for(int i=2;i<n;i++){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); Mul(A[i-1],A[i+1],a); Mul(A[i],A[i],b); if(!Cmp()){ falg=1;break; } } if(falg)printf("No "); else printf("Yes "); } fclose(stdin);fclose(stdout); return 0; }
回文串(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[0]=1; for(int i=1;i<=20000;i++) p[i]=p[i-1]*P; } void Hash1(){ A[0]=0; for(int i=1;i<=n;i++) A[i]=A[i-1]*P+s[i]; } void Hash2(){ B[0]=0; for(int i=1;i<=n;i++) B[i]=B[i-1]*P+s[n-i+1]; } ll Query1(int l,int r){ return A[r]-A[l-1]*p[r-l+1]; } ll Query2(int l,int r){ return B[r]-B[l-1]*p[r-l+1]; } int main() { freopen("palindromes.in","r",stdin); freopen("palindromes.out","w",stdout); scanf("%d",&T);Get(); while(T--){ scanf("%s",s+1); n=strlen(s+1); a[0]=0;b[0]=0; Hash1();Hash2();falg=0; for(int i=1;i<=n;i++){ ll x=Query1(1,i); ll y=Query2(n-i+1,n); if(x==y)a[++a[0]]=i; } for(int i=n;i>=1;i--){ ll x=Query1(i,n); ll y=Query2(1,n-i+1); if(x==y)b[++b[0]]=i; } for(int i=1;i<=a[0];i++){ for(int j=1;j<=b[0];j++){ if(a[i]+1>b[j]-1)break; ll x=Query1(a[i]+1,b[j]-1); ll y=Query2(n-b[j]+2,n-a[i]); if(x==y){ falg=1;break; } } if(falg)break; } if(falg)printf("Yes "); else printf("No "); } fclose(stdin);fclose(stdout); return 0; }
正解你猜