新手村-循环!循环!循环!

计算机最不怕的就是重复。你让它做10000次同样的事它也不怕啦,但是让他做1亿亿次的话……

P1008 三连击 模拟+打表

题目背景

本题为提交答案题,您可以写程序或手算在本机上算出答案后,直接提交答案文本,也可提交答案生成程序。

题目描述

将$1,2, \cdots ,9$共9个数分成3组,分别组成3个三位数,且使这3个三位数构成1:2:3的比例,试求出所有满足条件的3个三位数。

Code $O(bit^3)$

Force。筛。。(这种类型似乎被叫做模拟题)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;

struct tri{
int n3,n2,n1;
void init(int i, int j, int k){
n3 = i; n2 = j; n1 = k;
}
tri operator *(int scale){
tri T; T.n1 = n1*scale; T.n2 = n2*scale; T.n3 = n3*scale;
if(T.n1 > 9){
T.n2 += T.n1 / 10;
T.n1 %= 10;
}
if(T.n2 > 9){
T.n3 += T.n2 / 10;
T.n2 %= 10;
}
return T;
}
};

bool check(tri a, tri b){
return (a.n1 != b.n1) && (a.n1 != b.n2) && (a.n1 != b.n3) && (a.n2 != b.n1) && (a.n2 != b.n2) && (a.n2 != b.n3) && (a.n3 != b.n1) && (a.n3 != b.n2) &&(a.n3 != b.n3);
}

bool check_single(tri a){
return (a.n1 != a.n2) && (a.n1 != a.n3) && (a.n3 != a.n2);
}

bool ex(int i){
return i<1 || i>9;
}

bool excess(tri c){
return ex(c.n1) || ex(c.n2) || ex(c.n3);
}

bool singular(tri a, tri b, tri c){
if(excess(c)) return 0;
else return check(a,b)&&check(a,c)&&check(b,c)&&check_single(a)&&check_single(b)&&check_single(c);
}

void generate(int i, int j, int k){
tri tr1,tr2,tr3;
tr1.init(i,j,k);
tr2 = tr1 * 2;
tr3 = tr1 * 3;

// printf("生成:%d%d%d %d%d%d %d%d%d\n",tr1.n3, tr1.n2, tr1.n1, tr2.n3, tr2.n2, tr2.n1, tr3.n3, tr3.n2, tr3.n1);

if(singular(tr1,tr2,tr3)){
// printf("\tSingular!--> ");
printf("%d%d%d ", tr1.n3, tr1.n2, tr1.n1);
printf("%d%d%d ", tr2.n3, tr2.n2, tr2.n1);
printf("%d%d%d\n", tr3.n3, tr3.n2, tr3.n1);
}
}


int main(){
for(int i = 1; i <=3; ++i)
for(int j = 1; j <=9; ++j)
for(int k = 1; k <=9; ++k)
if(i!=j && j!=k && i!=k)
generate(i,j,k);
return 0;
}

可以看看这个,没有构造int数位,利用统计法来确定singular。

来自题解 P1008 【三连击】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
#include<cstring>
int i,j,v;bool a[10];//ai表示第i个数已经用过了
int main()
{
for(i=192;i<=327;i++)//第一个数最小192,最大327。其实不知道的情况下简单来说是从123-329的但是算出来是最值就稍微改了下下
{
memset(a,0,sizeof(a));v=0;//清零
a[i%10]=a[i/10%10]=a[i/100]=a[i*2%10]=a[i*2/10%10]=a[i*2/100]=a[i*3%10]=a[i*3/10%10]=a[i*3/100]=1;//统计数字
for(j=1;j<=9;j++) v+=a[j];//v表示1-9这些数字是否全部齐了
if(v==9) printf("%d %d %d\n",i,i*2,i*3);//如果齐了就输出
}
return 0;
}

P1035 级数求和 调和级数

题目描述

已知:$Sn=1+1/2+1/3+…+1/n$。显然对于任意一个整数K,当n足够大的时候,Sn大于K。

现给出一个整数K(1≤k≤15),要求计算出一个最小的n;使得Sn>K。

这是调和级数(发散)。

Code

Force $O(e^k)$

写一个累加器和一个溢出灯就行。

以后可能会将回归性函数称为,分类性函数称为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;

bool excess(double sn,double k){ //溢出灯
return sn > k;
}

int main(){
int i=1;
double sn=0,k;
cin>>k;
while(1){ //累加器
sn += (double)1/(double)(i++);
if(excess(sn,k)) {cout<<i-1;break;}
}
return 0;
}

数论优化 $O(logk)$

https://www.luogu.org/problemnew/solution/P1035

exp(k)是指数调用的复杂度,最高可以优化到log(k)(相当多项式幂),因此最后得到的复杂度为$O(logk)$。

值得指出的$O(logk)$仅仅是理论的,因为最后cout打印的数的宽度已经是O(k)了

运算虽然可以很快,却会被输出所限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

bool excess(double sn,double k){
return sn > k;
}

int main(){
int i=1;
double k;
while(cin>>k){
cout<<floor(exp(k-0.5772156649) + 0.5)<<endl;
}
return 0;
}

P1423 小玉在游泳 等比级数

题目描述

小玉开心的在游泳,可是她很快难过的发现,自己的力气不够,游泳好累哦。已知小玉第一步能游2米,可是随着越来越累,力气越来越小,她接下来的每一步都只能游出上一步距离的98%。现在小玉想知道,如果要游到距离x米的地方,她需要游多少步呢。请你编程解决这个问题。

Code $O(1)$

等比级数。

Force $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

bool excess(double sn,double x){ //溢出灯
return sn > x;
}

int main(){
int i=1;
double sn=0,k=2,x;
cin>>x;
while(1){ //累加器
sn += k;
k *= 0.98;
i++;
if(excess(sn,x)) {cout<<i-1;break;}
}
return 0;
}

通项公式

Force $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

bool excess(double sn,double x){ //溢出灯
return sn > x;
}

int main(){
int i=1;
double sn=0,k=2,x;
cin>>x;
while(1){ //累加器
sn = 2*(1 -pow(0.98,i) ) / 0.02;
i++;
if(excess(sn,x)) {cout<<i-1;break;}
}
return 0;
}

通项公式+二分 $O(logn)$

强行二分。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

bool excess(double sn,double x){ //溢出灯
return sn > x;
}

int main(){
double sn=0,k=2,x;
cin>>x;
int left=1, right=300; //题目的数据不行。。右边界非常小
while(1){
int mid = (left+right)>>1;
sn = 2*(1 -pow(0.98, mid ) ) / 0.02;
if(excess(sn,x))
right = mid;
else
left = mid;
if(left == right - 1) break;
}
cout<<right;
return 0;
}

解法2 $O(1)$

https://www.luogu.org/problemnew/solution/P1423

相当于代入具体参数化简通项公式,溢出灯功能由上取整函数取代

1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
double x;
int main()
{
std::cin>>x;
std::cout<<ceil(log(1-x/100)/log(0.98));
return 0;
}

P1424 小鱼的航程(改进版) 循环统计

题目背景

原来的题目太简单,现改进让小鱼周末也休息,请已经做过重做该题。

题目描述

有一只小鱼,它上午游泳150公里,下午游泳100公里,晚上和周末都休息(实行双休日),假设从周x(1<=x<=7)开始算起,请问这样过了n天以后,小鱼一共累计游泳了多少公里呢?

Code $O(1)$

Force $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;

int main(){
long int n,x;
long int sn=0;
cin>>x>>n;
x--;
while(n--){ //累加器
sn += ( ( x % 7 ) != 5 ) && ( ( x % 7 ) != 6 ); x++;
}
cout << sn*250;
return 0;
}

通项法 $O(1)$

虽然表面上由for循环,但该循环次数不会超过7。

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;

int main(){
long int n,x;
cin>>x>>n;
long int times = n/7*5, res = n%7+x;
for(long int i = x - 1; i < res-1; i++) //Note: res-1
if(!( i%7==5||i%7==6 )) times++;
cout << times*250;
return 0;
}

P1980 计数问题 组合数学

题目描述

试计算在区间 1 到 n的所有整数中,数字x(0≤x≤9)共出现了多少次?
例如,在 1到11中,即在 1,2,3,4,5,6,7,8,9,10,11中,数字1出现了 4 次。

Code $O(logn)$

Force会死人的。。直接分析一下然后求更优解了。

然而写了一个多小时,思路越来越混乱了。。本来想求按照位数进行迭代。

比如:取x=1,对区间1~111的1位数、2位数、3位数分别统计。

  • 1位数:1~9,1
  • 2位数:10~99,10+9=19
  • 3位数:100~111,12+2+2=16
  • 总共36

这个跟优化的解法是类似的,但在分类层次是相反的。(我没有想到固定某一位

Force $O(nlogn)$

最后参考了题解的force算法。对每一个数单独查询。居然没有我想象中那样复杂度高到不行,看来直觉还是不可靠。。

作者: 王超wangchao
更新时间: 2017-12-26 21:46

在Ta的博客查看

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;

int main(){
int n,x,ans; cin>> n >> x; n++;
while(n--){ //O(n)
int tem=n;
while(tem) //O(logn)
tem%10 == x ? ans++,tem/=10 : tem/=10;
}
cout<< ans <<endl;
return 0;
}

snprintf 传入四个参数:snprintf(ch,sizeof(ch),"%lld",a);

  1. 要写入的字符数组
  2. 数组大小(一般用sizeof(ch)
  3. 要转的数的格式(和printf()类似)
  4. 要转的数

该函数常用来快捷的 将数转存于字符数组中,方便好用

再将数转为字符数组后,一位一位的判就AK

作者: 二班的蒟蒻
更新时间: 2018-08-26 21:51

在Ta的博客查看

按位组合 $O(logn)$

作者: Curry28
更新时间: 2016-02-08 20:39

在Ta的博客查看

优化思路:固定某一位,求剩余位的组合数。(相当于按位切分为三部分)

1548149844523

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

int main(){
int n,x,a,b,c,m=1,ans=0;
cin>> n >> x;
while(m<=n){
a=n/(m*10); b=n/m%10; c=n%m;
if(b < x)
ans += a*m;
else if( b == x)
ans += (a - (x==0))*m + (c + 1); //x==0可以用灯合并进来
else
ans += (a - (x==0))*m + m;
m*=10;
}
cout<< ans <<endl;
return 0;
}

考虑把高位数字用0补齐来统计低位整数:

  • 假设n=12308x=2
  • 则对于三位整数###,可以拓展为一类00###
    • 附加统计一个00###组合数即可
      • 比如,统计百位数位置,这里的组合数将附加一个10*10=100
0%