第九届题目

第几天

#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { printf("%d",31+29+30+31+4); return 0; }

乘积尾零

#include <stdio.h> #include <stdlib.h> int count(int n,int f) { int cnt=0; while(n%f==0&&n!=0) { cnt++; n/=f; } return cnt; } int main(int argc, char *argv[]) { int a[]={5650,4542,3554,473, 946, 4114, 3871, 9073, 90, 4329, 2758, 7949, 6113, 5659, 5245, 7432, 3051, 4434, 6704, 3594, 9937, 1173, 6866, 3397, 4759, 7557, 3070, 2287, 1453, 9899, 1486, 5722, 3135, 1170, 4014, 5510, 5120, 729, 2880,9019, 2049, 698, 4582, 4346, 4427, 646, 9742, 7340, 1230, 7683, 5693, 7015, 6887, 7381, 4172, 4341, 2909, 2027, 7355, 5649, 6701, 6645, 1671, 5978, 2704, 9926, 295, 3125, 3878, 6785, 2066, 4247, 4800, 1578, 6652, 4616, 1113, 6205, 3264, 2915, 3966, 5291, 2904, 1285, 2193, 1428, 2265, 8730, 9436, 7074, 689, 5510, 8243, 6114, 337, 4096, 8199, 7313, 3685, 211 }; int k2=0,k5=0; for(int i=0;i<100;i++) { k2+=count(a[i],2); k5+=count(a[i],5); } printf("%d",k2<k5?k2:k5); return 0; }

测试次数

#include <stdio.h> #include <stdlib.h> int max(int a,int b) { return a>b?a:b; } int min(int a,int b) { return a<b?a:b; } int main(int argc, char *argv[]) { int dp[1005][5]; for(int i=1;i<=1000;i++) { dp[i][1]=i; } for(int hight=1;hight<=1000;hight++) { for(int cnt=2;cnt<=3;cnt++) { dp[hight][cnt]=dp[hight-1][cnt]+1; for(int k=2;k<hight;k++) { dp[hight][cnt]=min(dp[hight][cnt],max(dp[k-1][cnt-1],dp[hight-k][cnt])+1); } } } printf("%d",dp[1000][3]); return 0; }

递增三元组

#include <stdio.h> #include <stdlib.h> typedef long long ll; int cmp(const void *a,const void *b) { return *(int*)a-*(int*)b; } int lower_bound(int *arr,int n,int target) { int left=1,right=n; int ans=n+1; while(left<=right) { int mid=left+(right-left)/2; if(arr[mid]>=target) { ans=mid; right=mid-1; } else left=mid+1; } return ans; } int upper_bound(int *arr,int n,int target) { int left=1,right=n; int ans=n+1; while(left<=right) { int mid=left+(right-left)/2; if(arr[mid]>target) { ans=mid; right=mid-1; } else left=mid+1; } return ans; } int main(int argc, char *argv[]) { int n; scanf("%d",&n); int a[100005],b[100005],c[100005]; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { scanf("%d",&b[i]); } for(int i=1;i<=n;i++) { scanf("%d",&c[i]); } qsort(a+1,n,sizeof(int),cmp); qsort(b+1,n,sizeof(int),cmp); qsort(c+1,n,sizeof(int),cmp); ll cnta,cntc; ll ans=0; for(int i=1;i<=n;i++) { cnta=lower_bound(a,n,b[i])-1; cntc=n-(upper_bound(c,n,b[i])-1); ans+=cnta*cntc; } printf("%lld",ans); return 0; }

日志统计

#include <stdio.h> #include <stdlib.h> typedef struct { int ts,id; }Log; int cmp(const void *a,const void *b) { Log *pa=(Log*)a; Log *pb=(Log*)b; return pa->ts-pb->ts; } int cmp_b(const void *a,const void *b) { return *(int*)a-*(int*)b; } int main(int argc, char *argv[]) { int n,d,k; scanf("%d %d %d",&n,&d,&k); Log log[100005]; for(int i=0;i<n;i++) { scanf("%d %d",&log[i].ts,&log[i].id); } qsort(log,n,sizeof(Log),cmp); int a[100005]={0}; int b[100005]; int cnt=0; int j=0; for(int i=0;i<n;i++) { while(log[j].ts-log[i].ts<d&&j<n) { a[log[j].id]++; if(a[log[j].id]>=k) { b[cnt++]=log[j].id; } j++; } a[log[i].id]--; } qsort(b,cnt,sizeof(int),cmp_b); for(int i=0;i<cnt;i++) { if(i==0||b[i]!=b[i-1]) printf("%d\n",b[i]); } return 0; }

乘积最大

#include <stdio.h> #include <stdlib.h> #define N 100010 #define MOD 1000000009 typedef long long LL; int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int main() { int n, k; scanf("%d%d", &n, &k); int a[N]; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } qsort(a, n, sizeof(int), cmp); LL ans = 1; int l = 0, r = n - 1; int sign = 1; if (k % 2) { ans = a[r]; r--; k--; if (ans < 0) sign = -1; } while (k) { LL x = (LL)a[l] * a[l + 1]; LL y = (LL)a[r] * a[r - 1]; if (x * sign > y * sign) { ans = (x % MOD) * (ans % MOD) % MOD; l += 2; } else { ans = (y % MOD) * (ans % MOD) % MOD; r -= 2; } k -= 2; } printf("%lld\n", ans); return 0; }