基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
收藏
关注数组A和数组B，里面都有n个整数。数组C共有n^2个整数，分别是A[0] * B[0],A[0] * B[1] ......A[1] * B[0],A[1] * B[1]......A[n - 1] * B[n - 1]（数组A同数组B的组合）。求数组C中第K大的数。
例如：A：1 2 3，B：2 3 4。A与B组合成的C包括2 3 4 4 6 8 6 9 12共9个数。
Input
第1行：2个数N和K，中间用空格分隔。N为数组的长度，K对应第K大的数。(2 <= N <= 50000，1 <= K <= 10^9) 第2 - N + 1行：每行2个数，分别是A[i]和B[i]。(1 <= A[i],B[i] <= 10^9)
Output
输出第K大的数。
Input示例
3 2 1 2 2 3 3 4
Output示例
9
这道题就是二分题，先二分那个答案，然后对于判断有几个数乘起来比它大，这就可以先枚举A中的数，然后在B中二分。
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; typedef long long ll; const int MAXN = 5e4+5; ll a[MAXN], b[MAXN]; ll Judge(ll x, int n) { ll sum = 0, tp; for(int i=n-1; i>=0; i--) { if(x % a[i]) tp = x/a[i]+1; else tp = x/a[i]; int tmp = lower_bound(b,b+n,tp)-b; sum += n-tmp; if(sum == 0) break; } return sum; } int main() { int n, k; while(~scanf("%d%d",&n,&k)) { for(int i=0; i<n; i++) scanf("%I64d%I64d",&a[i],&b[i]); sort(a, a+n); sort(b, b+n); ll l = a[0]*b[0], r = a[n-1]*b[n-1]; while(l<=r) { ll mid = (l+r)>>1; ll tmp = Judge(mid, n); if(tmp < k) r = mid-1; else l = mid+1; } printf("%I64d ",l-1); } return 0; }
N元钱换为零钱，有多少不同的换法？币值包括1 2 5分，1 2 5角，1 2 5 10 20 50 100元。
例如：5分钱换为零钱，有以下4种换法：
1、5个1分
2、1个2分3个1分
3、2个2分1个1分
4、1个5分
(由于结果可能会很大，输出Mod 10^9 + 7的结果)
Input
输入1个数N，N = 100表示1元钱。(1 <= N <= 100000)
Output
输出Mod 10^9 + 7的结果
Input示例
5
Output示例
4
DP一下即可
#include<iostream> #include<stdio.h> using namespace std; #define mod 1000000007 int dp[100005]; int main() { int arr[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000}; int size = 13,n; while (~scanf("%d",&n)) { dp[0] = 1; for (int i=0;i<size;i++) { for (int j=arr[i];j<=n;j++) dp[j] = (dp[j]+dp[j-arr[i]])%mod; } printf("%d ",dp[n]); } }
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
收藏 关注给定一个自然数N，找出一个M，使得M > 0且M是N的倍数，并且M的10进制表示只包含0或1。求最小的M。
例如：N = 4，M = 100。
Input
输入1个数N。(1 <= N <= 10^6)
Output
输出符合条件的最小的M。
Input示例
4
Output示例
100
宽搜题，保存一下%N的值，以及前缀的数字，当前的数字0或1.
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; queue<int> Q; bool boo[1000005]; int cnt; int N,pre[1000005],num[1000005],tt,level[1000005],kpl[100005]; int main() { scanf("%d",&N); Q.push(1); pre[1]=0;boo[1]=1;num[1]=level[1]=1;level[0]=0; while(!Q.empty()) { int p=Q.front(),q=p; Q.pop(); if(p==0) { kpl[++cnt]=num[q]; do { q=pre[q]; kpl[++cnt]=num[q]; }while(level[q]!=1); for(int pp=cnt;pp>=1;pp--) printf("%d",kpl[pp]); cout<<endl; return 0; } tt=(p*10)%N; if(!boo[tt]) { Q.push(tt); level[tt]=level[p]+1; pre[tt]=p;num[tt]=0; boo[tt]=1; } tt=(p*10+1)%N; if(!boo[tt]) { Q.push(tt); level[tt]=level[p]+1; pre[tt]=p;num[tt]=1; boo[tt]=1; } } }