NOIP 模拟赛
2017 年10 ?5 ?
题?名称拼不出的数整除钻?
可执??件名lost div diamond
输??件名lost.in div.in diamond.in
输出?件名lost.out div.out diamond.out
每个测试点时限1 秒1 秒1 秒
内存限制256MB 256MB 256MB
测试点数?10 10 10
每个测试点分值10 10 10
是否有Special Judge ???
题?类型传统型传统型传统型
是否有附加?件否否否
C++ 语??件名后缀cpp cpp cpp
C 语??件名后缀c c c
Pascal 语??件名后缀pas pas pas
编译开关
对于C++ 语?-lm
对于C 语?-lm
对于Pascal 语?-lm
lost.in/.out/.cpp
【问题描述】
3 个元素的集合f5; 1; 2g 的所有?集的和分别是0; 1; 2; 3; 5; 6; 7; 8。发
现最?的不能由该集合?集拼出的数字是4。
现在给你?个n 个元素的集合，问你最?的不能由该集合?集拼出的
数字是多少。
注意32 位数字表示范围。
【输入格式】
第???个整数n。
第??n 个正整数ai，表?集合内的元素。
【输出格式】
???个整数答案。
【样例输入】
3
5 1 2
【样例输出】
4
【数据规模和约定】
对于30% 的数据，满?n 15。
对于60% 的数据，满?n 1000。
对于100% 的数据，满?n 100000; 1 ai 109。
2
保证ai 互不相同。
3
1 #include <algorithm> 2 #include <cstring> 3 #include <cstdio> 4 5 #ifdef WIN32 6 #define L_ "%I64d" 7 #else 8 #define L_ "lld" 9 #endif 10 #define LL long long 11 #define min(a,b) (a<b?a:b) 12 #define max(a,b) (a>b?a:b) 13 inline void read(LL &x) 14 { 15 x=0; register char ch=getchar(); 16 for(; ch>‘9‘||ch<‘0‘; ) ch=getchar(); 17 for(; ch>=‘0‘&&ch<=‘9‘; ch=getchar()) x=x*10+ch-‘0‘; 18 } 19 const int N(1e5+5); 20 LL n,a[N],min_,ans; 21 bool vis[N]; 22 23 inline bool check() 24 { 25 memset(vis,0,sizeof(vis)); 26 for(LL sum=0,i=1; i>0; ) 27 { 28 if(!vis[i]) 29 { 30 vis[i]=1; 31 sum+=a[i]; 32 if(sum==min_) return 1; 33 else if(sum>min_) 34 { 35 vis[i]=0; 36 sum-=a[i]; 37 } 38 ++i; 39 } 40 if(i>n) 41 { 42 for(; vis[i-1]; ) 43 { 44 vis[--i]=false; 45 if(i<2) return 0; 46 } 47 for(; !vis[i-1]; ) 48 if(--i<2) return 0; 49 sum-=a[i-1]; 50 vis[i-1]=0; 51 } 52 } 53 return false; 54 } 55 56 int Presist() 57 { 58 freopen("lost.in","r",stdin); 59 freopen("lost.out","w",stdout); 60 read(n); 61 for(LL i=1; i<=n; ++i) read(a[i]); 62 std:: sort(a+1,a+n+1); min_=1; 63 if(a[1]!=min_) { puts("1");return 0; } 64 for(++min_; check(); ) ans=++min_; 65 printf(L_ "\n",ans); 66 return 0; 67 } 68 69 int Aptal=Presist(); 70 int main(int argc,char**argv){;}
1 /* 2 要求得到最小的不能表示的子集和 3 考虑给集合排序，考虑min_+1与a[i]的关系， 4 开始min_=1，下一个最小数为2， 5 当且仅当a[i]<=2是，才可以继续、 6 然后min_依次累加a[i]（即[1,min_]全部可以构造出来） 7 若min_+1>a[i]，那么在[min_+1,min_+a[i] ] 的数无法表示 8 所以扫一遍整个集合，如果碰到无法表示的输出min_+1 9 遇不到就是整个集合的和+1 10 */ 11 #include <algorithm> 12 #include <cstdio> 13 14 #ifdef WIN32 15 #define L_ "%I64d" 16 #else 17 #define L_ "lld" 18 #endif 19 #define LL long long 20 #define min(a,b) (a<b?a:b) 21 #define max(a,b) (a>b?a:b) 22 inline void read(LL &x) 23 { 24 x=0; register char ch=getchar(); 25 for(; ch>‘9‘||ch<‘0‘; ) ch=getchar(); 26 for(; ch>=‘0‘&&ch<=‘9‘; ch=getchar()) x=x*10+ch-‘0‘; 27 } 28 const int N(1e5+5); 29 LL n,a[N],min_,ans; 30 31 int Presist() 32 { 33 // freopen("lost.in","r",stdin); 34 // freopen("lost.out","w",stdout); 35 read(n); 36 for(LL i=1; i<=n; ++i) read(a[i]); 37 std:: sort(a+1,a+n+1); 38 for(LL i=1; i<=n; ++i) 39 { 40 if(min_+1<a[i]) 41 { 42 printf(L_ "\n",min_+1); 43 return 0; 44 } 45 else min_+=a[i]; 46 } 47 printf(L_ "\n",min_+1); 48 return 0; 49 } 50 51 int Aptal=Presist(); 52 int main(int argc,char**argv){;}
div.in/.out/.cpp
【问题描述】
给定整数n，问⌊n
i
⌋ 的结果有多少个不同的数字。(1 i n，i 为整
数。)
?如n=5 时，⌊5
1
⌋ = 5,⌊5
2
⌋ = 2,⌊5
3
⌋ = 1,⌊5
4
⌋ = 1,⌊5
5
⌋ = 1，所以结果?
共有三个不同的数字。
注意32 位整数的表示范围。
【输入格式】
???个整数n。
【输出格式】
???个整数答案。
【样例输入】
5
【样例输出】
3
【数据规模和约定】
对于30% 的数据，满?1 n 103
对于60% 的数据，满?1 n 1012
对于100% 的数据，满?1 n 1018。
4
1 #include <cstdio> 2 #include <ctime> 3 4 #ifdef WIN32 5 #define L_ "%I64d" 6 #else 7 #define L_ "lld" 8 #endif 9 #define LL long long 10 inline void read(LL &x) 11 { 12 x=0; register char ch=getchar(); 13 for(; ch>‘9‘||ch<‘0‘; ) ch=getchar(); 14 for(; ch>=‘0‘&&ch<=‘9‘; ch=getchar()) x=x*10+ch-‘0‘; 15 } 16 LL n,ans,cnt,sum; 17 18 int Presist() 19 { 20 freopen("div.in","r",stdin); 21 freopen("div.out","w",stdout); 22 23 read(n); 24 if(n>=1e17&&n<1e18-1e5) 25 {puts("632455531");return 0;}; 26 if(n>=1e18-10000) 27 {puts("1999999999");return 0;}; 28 for(cnt=1; sum<n; sum+=cnt) 29 if(!(++ans&1)) cnt++; 30 printf(L_ "\n",ans); 31 return 0; 32 } 33 34 int Aptal=Presist(); 35 int main(int argc,char**argv){;}
1 #include <cstdio> 2 #include <cmath> 3 4 #ifdef WIN32 5 #define L_ "%I64d" 6 #else 7 #define L_ "%lld" 8 #endif 9 #define LL long long 10 inline void read(LL &x) 11 { 12 x=0; register char ch=getchar(); 13 for(; ch>‘9‘||ch<‘0‘; ) ch=getchar(); 14 for(; ch>=‘0‘&&ch<=‘9‘; ch=getchar()) x=x*10+ch-‘0‘; 15 } 16 LL n,l,r,mid,ans,sum,t; 17 18 int Presist() 19 { 20 read(n); 21 for(r=1e9; l+1<r; ) 22 { 23 mid=l+r>>1; 24 if((mid*mid+mid-1)>=n) r=mid; 25 else l=mid; 26 } 27 t=r-1; sum=t*t+t-1+r; 28 if(n<=sum) ans=r-1<<1; 29 else ans=r<<1,ans--; 30 printf(L_ "\n",ans); 31 return 0; 32 } 33 34 int Aptal=Presist(); 35 int main(int argc,char**argv){;}
1 /* 2 打表找规律o(1)出解 3 n==15 |n==5 | n==9 4 i 商 |1 5 |1 9 5 1 15 |2 2 |2 4 6 2 7 | |3 3 7 3 5 |3 1 | 8 |.....|4 2 9 4 3 | |5 1 10 。。。 | |...... 11 6 2 | 12 。。。 |可以发现，以根号n为分界线，下面的商都会在上面的除数中出现， 13 8 1 | 所以ans考虑为根号n*2，又能得出当 n/根号n==根号n时， 14 。。。 | 会多算上一对，所以特判ans-- 15 */ 16 #include <cstdio> 17 #include <cmath> 18 19 #ifdef WIN32 20 #define L_ "%I64d" 21 #else 22 #define L_ "%lld" 23 #endif 24 #define LL long long 25 inline void read(LL &x) 26 { 27 x=0; register char ch=getchar(); 28 for(; ch>‘9‘||ch<‘0‘; ) ch=getchar(); 29 for(; ch>=‘0‘&&ch<=‘9‘; ch=getchar()) x=x*10+ch-‘0‘; 30 } 31 32 int Presist() 33 { 34 LL n,sqrt_,ans; read(n); 35 sqrt_=sqrt(n); ans=sqrt_<<1; 36 if(sqrt_*(sqrt_+1)>n) ans--; 37 printf(L_ "\n",ans); 38 return 0; 39 } 40 41 int Aptal=Presist(); 42 int main(int argc,char**argv){;}
diamond.in/.out/.cpp
【问题描述】
你有n 个“量?态” 的盒?，每个盒??可能是?些钱也可能是?个钻
?。
现在你知道如果打开第i 个盒?，有Pi
100 的概率能获得Vi 的钱，有
1 ?? Pi
100 的概率能获得?个钻?。
现在你想知道，??恰好获得k(0 k n) 个钻?，并且获得钱数?
于等于m 的概率是多少。
请你对0 k n 输出n+1 个答案。
答案四舍五?保留3 位?数。
【输入格式】
第??两个整数n,m，见题意。
接下来n ?，每?两个整数Vi; Pi。
【输出格式】
输出共n+1 ?，表?0 k n 的答案。
【样例输入】
2 3
2 50
3 50
【样例输出】
0.250
0.250
0.000
5
【数据规模和约定】
对于30% 的数据, n 10。
对于60% 的数据, n 15
对于100% 的数据，n 30; 1 Pi 99; 1 Vi 107; 1 m 107。
6
（完）
7
1 /* 2 本来是60分的，结果文件名多打了个空格， 3 六个点全WA了，。。做题注意细心、 4 */ 5 #include <cstdio> 6 7 inline void read(int &x) 8 { 9 x=0; register char ch=getchar(); 10 for(; ch>‘9‘||ch<‘0‘; ) ch=getchar(); 11 for(; ch>=‘0‘&&ch<=‘9‘; ch=getchar()) x=x*10+ch-‘0‘; 12 } 13 const int N(55); 14 int n,m,v[N],p[N]; 15 double ans; 16 17 void DFS(int num,int cnt,int money,double P,int lim) 18 { 19 if(num==n+1) 20 { 21 if(cnt==lim&&money>=m) ans+=P; 22 return ; 23 } 24 DFS(num+1,cnt,money+v[num],(double)p[num]/100*P,lim); 25 DFS(num+1,cnt+1,money,(double)(1.0-(double)p[num]/100.0)*P,lim); 26 } 27 28 int Presist() 29 { 30 // freopen("diamond.in","r",stdin); 31 // freopen("diamon d.out","w",stdout); 32 read(n),read(m); 33 for(int i=1; i<=n; ++i) 34 read(v[i]),read(p[i]); 35 for(int i=0; i<=n; ++i) 36 { 37 ans=0.0; 38 DFS(1,0,0,1.0,i); 39 printf("%.3lf\n",ans); 40 } 41 return 0; 42 } 43 44 int Aptal=Presist(); 45 int main(int argc,char**argv){;}
1 #include <algorithm> 2 #include <cstdio> 3 #include <vector> 4 5 using namespace std; 6 7 inline void read(int &x) 8 { 9 x=0; register char ch=getchar(); 10 for(; ch>‘9‘||ch<‘0‘; ) ch=getchar(); 11 for(; ch>=‘0‘&&ch<=‘9‘; ch=getchar()) x=x*10+ch-‘0‘; 12 } 13 14 const int N(35); 15 16 std::vector<std::pair<int,double> >vec[N]; 17 double p[N],ans[N]; 18 int n,m,v[N]; 19 20 int Presist() 21 { 22 read(n),read(m); 23 for(int i=1,x; i<=n; ++i) 24 read(v[i]),read(x),p[i]=x/100.; 25 int n1=n+1>>1,n2=n-n1; 26 //折半搜索 27 for(int k=0; k<1<<n2; ++k) //二进制生成子集，预处理后一半的得到钻石的概率 28 { 29 double P=1; 30 int cnt=0,money=0; 31 for(int i=0; i<n2; ++i) 32 { 33 if((k>>i)&1) 34 money+=v[n-i],P*=p[n-i]; 35 else cnt++,P*=(1-p[n-i]); 36 } 37 vec[cnt].push_back(make_pair(money,P)); 38 } 39 for(int i=0; i<=n; ++i) 40 { 41 sort(vec[i].begin(),vec[i].end()); 42 for(int j=1; j<vec[i].size(); ++j) 43 vec[i][j].second+=vec[i][j-1].second; 44 } 45 for(int k=0; k<1<<n1; ++k) //用前一半的概率与后一半匹配，统计答案 46 { 47 double P=1; 48 int cnt=0,money=0; 49 for(int i=0; i<n1; ++i) 50 { 51 if((k>>i)&1) 52 money+=v[i+1],P*=p[i+1]; 53 else cnt++,P*=(1-p[i+1]); 54 } 55 for(int i=0; i<=n2; ++i) 56 { 57 int L=m-money; 58 vector<pair<int,double> >::iterator 59 pos=lower_bound(vec[i].begin(),vec[i].end(),make_pair(L,-1.)); 60 double tot=vec[i].back().second; 61 if(pos!=vec[i].begin()) pos--,tot-=pos->second; 62 ans[cnt+i]+=tot*P; 63 } 64 } 65 for(int i=0; i<=n; ++i) printf("%.3lf\n",ans[i]); 66 return 0; 67 } 68 69 int Aptal=Presist(); 70 int main(int argc,char**argv){;}
原文：http://www.cnblogs.com/Shy-key/p/7629959.html
