新手村-BOSS战*

这里将前面的内容综合起来了,会有点难,不过你可以问老师同学,也能上网查资料。

P1478 陶陶摘苹果(升级版) 贪心

题目描述

又是一年秋季时,陶陶家的苹果树结了n个果子。陶陶又跑去摘苹果,这次她有一个a公分的椅子。当他手够不着时,他会站到椅子上再试试。

这次与NOIp2005普及组第一题不同的是:陶陶之前搬凳子,力气只剩下s了。当然,每次摘苹果时都要用一定的力气。陶陶想知道在s<0之前最多能摘到多少个苹果。

现在已知n个苹果到达地上的高度xi,椅子的高度a,陶陶手伸直的最大长度b,陶陶所剩的力气s,陶陶摘一个苹果需要的力气yi,求陶陶最多能摘到多少个苹果。

说明

所有数据:n<=5000 a<=50 b<=200 s<=1000

1
xi<=280  yi<=100

Code $O(nlogn)$

贪心 $O(nlogn)$

Force的话就是递归,对每一个苹果按状态选、不选(决策树??),直到s用完。复杂度约$O(2^n)$。可以用DFS,就不写了。。

滑稽题解第二弹

作者: ASZIIIS
更新时间: 2018-10-31 18:25

在Ta的博客查看

只要有递归,就要想传播。传播当然是DP辣,DP再特殊一点就是贪心辣~~

由于只讨论摘果子最多能摘多少,显然代价越低的必然优先。

假设摘了某个苹果花费s',那么如果存在没有摘的苹果s<s',显然摘s会让总花费更小,而总花费更小当然比原来更优辣(大概是这样吧。。)。

所以先排个序,再求和直到溢出就行了。(排序+栈灯)这里的栈仍然只需要记录容量。

实际上过滤的时候,只要记录y就好了。但时间复杂度不会明显降低,还会降低通用性。

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
#include <bits/stdc++.h>
using namespace std;

struct apple
{
int x; //height
int y; //cost
bool operator <(apple p){
return y < p.y;
}
};

int main(){
int n,s;
int a,b;
vector<apple> Apple;
cin>>n>>s;
cin>>a>>b;
for(int i = 0; i < n; ++i){
int x; cin>>x;
if( x <= a + b){ //filter apples too high
int y; cin>>y;
apple tem; tem.x = x; tem.y = y;
Apple.push_back(tem);
} else{
cin>>x;
}
}

sort(Apple.begin(), Apple.end()); //排序

int i, len = Apple.size();
for(i = 0; i < len && s - Apple[i].y >= 0; ++i){ //栈灯
s -= Apple[i].y;
}
cout<<i;
}

P1618 三连击(升级版) 计数、打表

题目描述

将1,2,…,9共9个数分成三组,分别组成三个三位数,且使这三个三位数的比例是A:B:C,试求出所有满足条件的三个三位数,若无解,输出“No!!!”。

//感谢黄小U饮品完善题意

说明

保证A<B<C

Code $O(logb)$

又是三连击orz

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
#include<bits/stdc++.h>
using namespace std;

bool flag[10]; //flag[i]表示数字i是否有
bool No = 1; //输出No的控制

bool check(){ //是否所有数字都有
for(int i = 1; i < 10; ++i) //从1开始检查
if(flag[i] == 0) return 0; //有一个数字没有,退出
No = 0;
return 1;
}

void clear(){ //清空
for(int i = 1; i < 10; ++i)
flag[i] = 0;
}

void mark(int num){ //标记每个数使用的数字
flag[num/100] = 1; //百位
flag[(num/10)%10] = 1; //十位
flag[num%10] = 1; //个位
}

int main(){
int a, b, c; cin>> a >> b >> c;
for(int i = 123; i <= 987/(c/a); ++i){ //最小的数显然是123,最大的数是987
clear(); //清空flag
if(i%a != 0) continue; //如果i%a除不尽,显然不可能
int j = i/a*b; int k = i/a*c;
mark(i); mark(j); mark(k); //标记
if(check()) cout<< i <<" "<< j <<" "<<k<<endl;
}
if(No) cout<<"No!!!"<<endl;
return 0;
}

STL_next_permutation()

STL中的next_permutation函数提供下一个排列功能,是用生成法实现的,所以速度要比搜索快多了。

作者: ElevenX
更新时间: 2017-10-08 17:50

在Ta的博客查看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int a[10]={0,1,2,3,4,5,6,7,8,9};
int main()
{
int A,B,C,h=0;
cin>>A>>B>>C;
int t=A*B*C;
A=t/A;
B=t/B;
C=t/C;
do{
if((100*a[1]+10*a[2]+a[3])*A==(100*a[4]+10*a[5]+a[6])*B&&(100*a[1]+10*a[2]+a[3])*A==(100*a[7]+10*a[8]+a[9])*C)//如果符合比例;
{
cout<<a[1]<<a[2]<<a[3]<<" "<<a[4]<<a[5]<<a[6]<<" "<<a[7]<<a[8]<<a[9]<<endl;//输出
h++;
}
}while(next_permutation(a+1,a+10));//STL中的下一个排列函数;
if(h==0) cout<<"No!!!";//没有解输出NO;
return 0;
}

打表。。 $O(b)$

打表程序:

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
#include<bits/stdc++.h>
using namespace std;

#define MAX 10

bool flag[10]; //flag[i]表示数字i是否有
bool No = 1; //输出No的控制
bool dex = 1;
bool check(){ //是否所有数字都有
for(int i = 1; i < 10; ++i) //从1开始检查
if(flag[i] == 0) return 0; //有一个数字没有,退出
No = 0;
return 1;
}

void clear(){ //清空
for(int i = 1; i < 10; ++i)
flag[i] = 0;
}

void mark(int num){ //标记每个数使用的数字
flag[num/100] = 1; //百位
flag[(num/10)%10] = 1; //十位
flag[num%10] = 1; //个位
}

int main(){
int a, b, c;
cout<<"#include<bits/stdc++.h>\nusing namespace std;\nint main(){\n int a, b, c; cin>>a>>b>>c;\n";
for(int a = 1; a <= MAX-2; ++a)
for(int b = a+1; b <= MAX-1; ++b)
for(int c = b+1; c <= MAX; ++c){
for(int i = 123; i <= 987/(c/a); ++i){ //最小的数显然是123,最大的数是987
clear(); //清空flag
if(i%a != 0) continue; //如果i%a除不尽,显然不可能
int j = i/a*b; int k = i/a*c;
mark(i); mark(j); mark(k); //标记
if(check()){
if(dex == 1){
cout<<" if(a=="<<a<<" && b=="<<b<<" && c=="<<c<<"){\n";
dex = 0;
}
cout<<" cout<< "<<i<<" <<\" \"<< "<<j<<" <<\" \"<<"<<k<<"<<endl;\n";
}
}
if(dex == 0) cout<<" return 0;\n }\n";
dex = 1;
}
cout<<" cout<<\"No!!!\"<<endl;\n}"<<endl;
return 0;
}

OJ程序:

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
#include<bits/stdc++.h>
using namespace std;
int main(){
int a, b, c; cin>>a>>b>>c;
if(a==1 && b==2 && c==3){
cout<< 192 <<" "<< 384 <<" "<<576<<endl;
cout<< 219 <<" "<< 438 <<" "<<657<<endl;
cout<< 273 <<" "<< 546 <<" "<<819<<endl;
cout<< 327 <<" "<< 654 <<" "<<981<<endl;
return 0;
}
if(a==1 && b==3 && c==5){
cout<< 129 <<" "<< 387 <<" "<<645<<endl;
return 0;
}
if(a==2 && b==4 && c==6){
cout<< 192 <<" "<< 384 <<" "<<576<<endl;
return 0;
}
if(a==3 && b==6 && c==9){
cout<< 192 <<" "<< 384 <<" "<<576<<endl;
cout<< 219 <<" "<< 438 <<" "<<657<<endl;
cout<< 273 <<" "<< 546 <<" "<<819<<endl;
cout<< 327 <<" "<< 654 <<" "<<981<<endl;
return 0;
}
if(a==3 && b==7 && c==8){
cout<< 213 <<" "<< 497 <<" "<<568<<endl;
cout<< 321 <<" "<< 749 <<" "<<856<<endl;
return 0;
}
if(a==4 && b==5 && c==6){
cout<< 492 <<" "<< 615 <<" "<<738<<endl;
return 0;
}
cout<<"No!!!"<<endl;
}

特判+最大公约数化简

由于本题b出的可能较大,所以。。过不了测试点5(最后一个是123 456 789。。。跪了跪了)。。只能考虑化简有理分式。。。先求a,b,c的最大公约数。。。(貌似还是有点问题。。

仔细一看,123 456 789明显是特例。。看来要额外加进去。。。

最后将OJ程序修改为:

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
#include<bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a%b);
}
int gcd(int a, int b, int c){
return gcd(gcd(a,b), gcd(b,c));
}

int main(){
int a, b, c; cin>>a>>b>>c;
// int G = gcd(a, b, c);
// if(a % G == 0) a/=G, b/=G, c/=G;
if(a==1 && b==2 && c==3){
cout<< 192 <<" "<< 384 <<" "<<576<<endl;
cout<< 219 <<" "<< 438 <<" "<<657<<endl;
cout<< 273 <<" "<< 546 <<" "<<819<<endl;
cout<< 327 <<" "<< 654 <<" "<<981<<endl;
return 0;
}
if(a==1 && b==3 && c==5){
cout<< 129 <<" "<< 387 <<" "<<645<<endl;
return 0;
}
if(a==2 && b==4 && c==6){
cout<< 192 <<" "<< 384 <<" "<<576<<endl;
return 0;
}
if(a==3 && b==6 && c==9){
cout<< 192 <<" "<< 384 <<" "<<576<<endl;
cout<< 219 <<" "<< 438 <<" "<<657<<endl;
cout<< 273 <<" "<< 546 <<" "<<819<<endl;
cout<< 327 <<" "<< 654 <<" "<<981<<endl;
return 0;
}
if(a==3 && b==7 && c==8){
cout<< 213 <<" "<< 497 <<" "<<568<<endl;
cout<< 321 <<" "<< 749 <<" "<<856<<endl;
return 0;
}
if(a==4 && b==5 && c==6){
cout<< 492 <<" "<< 615 <<" "<<738<<endl;
return 0;
}
if(a==123 && b==456 && c==789){
cout<< 123 <<" "<< 456 <<" "<<789<<endl;
return 0;
}
cout<<"No!!!"<<endl;
}

没有调用gcd()

然后我发现,题意就有问题吧啊喂!!!调用公约数反而错了?????成比例这个事很邪乎啊啊啊啊啊。难道不应该很自然地化简吗。。

P1579 哥德巴赫猜想(升级版) 素数+模拟

题目背景

1742年6月7日哥德巴赫写信给当时的大数学家欧拉,正式提出了以下的猜想:任何一个大于9的奇数都可以表示成3个质数之和。质数是指除了1和本身之外没有其他约数的数,如2和11都是质数,而6不是质数,因为6除了约数1和6之外还有约数2和3。需要特别说明的是1不是质数。

这就是哥德巴赫猜想。欧拉在回信中说,他相信这个猜想是正确的,但他不能证明。

从此,这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。

题目描述

现在请你编一个程序验证哥德巴赫猜想

先给出一个奇数n,要求输出3个质数,这3个质数之和等于输入的奇数。

Code $O(n^2)$

当然最朴素的方法是遍历2个数i,j,对i,j,n-i-j验证素数。素数验证优化得好的话大约是$O(n^2\sqrt n)\rightarrow O(n\sqrt n)$吧。。

1
2
3
4
5
bool is_prime(int number){
for(int i = 2; i*i <= number; i+=1) //i*i是优化
if(!(number % i)) return 0;
return 1;
}

Force $O(n^3)\rightarrow O(n)+O(n)$

如果做过之前的回文素数题的话,这道题就相当简单辣。。套板子就行。

先生成n范围内的质数(比如欧拉筛法),然后暴力组合验证。。不稳定。

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
#include<bits/stdc++.h>
using namespace std;

#define MAX_N 20005

bool prime[MAX_N];
int p_numbers[MAX_N], size = 0; //reserve primes

void Euler(int Length){ //about O(n)
prime[0] = prime[1] = 0;
for(int i = 2; i <= Length; ++i) prime[i] = 1; //initialize all as true
for(int i = 2; i <= Length; ++i){
if(prime[i]){
p_numbers[size++] = i;
}
for(int j = 0; j <size && i*p_numbers[j] < Length; j++){
prime[ i*p_numbers[j] ] = 0; //sieve i*p_numbers[j]
if(i % p_numbers[j] == 0) //special
break;
}
}
}

int main(){
int n; cin>> n;
Euler(n);
for(int i = 0; i < size; ++i)
for(int j = i; j < size; ++j)
for(int k = j; k < size; ++k){
if(p_numbers[i]+p_numbers[j]+p_numbers[k]==n){
cout<<p_numbers[i]<<" "<<p_numbers[j]<<" "<<p_numbers[k];
return 0;
}
}
}

稍微优化一下 $O(n^2)\rightarrow O(n)+O(n)$

注意到我们并不需要遍历第三个循环,因为n已知,第3个数一定是n-p[i]-p[j]

然后就可以借助prime数组进行O(1)的判断辣。

怎么又是这个套路,好熟悉的感觉。。orz

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
#include<bits/stdc++.h>
using namespace std;

#define MAX_N 20005

bool prime[MAX_N];
int p_numbers[MAX_N], size = 0; //reserve primes

void Euler(int Length){ //about O(n)
prime[0] = prime[1] = 0;
for(int i = 2; i <= Length; ++i) prime[i] = 1; //initialize all as true
for(int i = 2; i <= Length; ++i){
if(prime[i]){
p_numbers[size++] = i;
}
for(int j = 0; j <size && i*p_numbers[j] < Length; j++){
prime[ i*p_numbers[j] ] = 0; //sieve i*p_numbers[j]
if(i % p_numbers[j] == 0) //special
break;
}
}
}

int main(){
int n; cin>> n;
Euler(n);
for(int i = 0; i < size; ++i)
for(int j = i; j < size; ++j) //直接少了一个循环
if(prime[n - (p_numbers[i]+p_numbers[j])]){
cout<<p_numbers[i]<<" "<<p_numbers[j]<<" "<<n - (p_numbers[i]+p_numbers[j]);
return 0;
}
}

*P2089 烤鸡 记忆、组合数学

题目背景

猪猪hanke得到了一只鸡

题目描述

猪猪Hanke特别喜欢吃烤鸡(本是同畜牲,相煎何太急!)Hanke吃鸡很特别,为什么特别呢?因为他有10种配料(芥末、孜然等),每种配料可以放1—3克,任意烤鸡的美味程度为所有配料质量之和

现在,Hanke想要知道,如果给你一个美味程度,请输出这10种配料的所有搭配方案

说明

枚举

Code $O(n)$

由于有1克是必须放的。。那么可供选择的余地就只有2克辣。

这么小的数据量就不要复杂度了。。

Force $O(n)+O(n)$

输出格式烦人。。只能先求完b才能得到a,但是输出格式要求是a b(a的长度远远远小于b),难道没有办法改变输出位置吗?(两种方法:缓存算两遍,感觉都耗费巨大。。)

缓存 $O(n)+O(n)$

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
#include<bits/stdc++.h>
using namespace std;

#define for(x) for(int x = 1; x <= 3; ++x)
#define MAX_N 10000000

int cache[MAX_N][10];

int main(){
int n; cin>> n;
int ans = 0;
for(s1)
for(s2)
for(s3)
for(s4)
for(s5)
for(s6)
for(s7)
for(s8)
for(s9)
for(s10)
if(s1+s2+s3+s4+s5+s6+s7+s8+s9+s10 == n){
cache[ans][0] = s1;
cache[ans][1] = s2;
cache[ans][2] = s3;
cache[ans][3] = s4;
cache[ans][4] = s5;
cache[ans][5] = s6;
cache[ans][6] = s7;
cache[ans][7] = s8;
cache[ans][8] = s9;
cache[ans][9] = s10;
ans++;
}
cout<<ans<<endl;
int index = 0;
while(index < ans){
cout<<cache[index][0]<<" "<<cache[index][1]<<" "<<cache[index][2]<<" "<<cache[index][3]<<" "<<cache[index][4]<<" "<<cache[index][5]<<" "<<cache[index][6]<<" "<<cache[index][7]<<" "<<cache[index][8]<<" "<<cache[index][9]<<endl;
index++;
}
}
字符流缓存

作者: 氢氧化铯CsOH
更新时间: 2016-11-30 19:14

在Ta的博客查看

想明白了。。如果想一次性地先输出ans,那么所有的方案必然要缓存。这是无可避免的。(这里用字符sprintf缓存会比int高效一点)

算两遍 $O(2n)+O(1)$

算两遍虽然略显暴力。。但是在缓存容量不好考察的时候作用就非常明显了。。而且无意中满足了题设输出0的条件。。

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
#include<bits/stdc++.h>
using namespace std;

#define for(x) for(int x = 1; x <= 3; ++x)

int main(){
int n; cin>> n;
int ans;
for(s1)
for(s2)
for(s3)
for(s4)
for(s5)
for(s6)
for(s7)
for(s8)
for(s9)
for(s10)
if(s1+s2+s3+s4+s5+s6+s7+s8+s9+s10 == n){
ans++;
}
cout<<ans<<endl;
for(s1)
for(s2)
for(s3)
for(s4)
for(s5)
for(s6)
for(s7)
for(s8)
for(s9)
for(s10)
if(s1+s2+s3+s4+s5+s6+s7+s8+s9+s10 == n){
cout<<s1<<" "<<s2<<" "<<s3<<" "<<s4<<" "<<s5<<" "<<s6<<" "<<s7<<" "<<s8<<" "<<s9<<" "<<s10<<endl;
}
}

*分配组合

总觉得如果只求方案数应该对应某个组合公式。。然而并不知道。

1
2


*DFS+模板

Author: 周宇恒

在看最优解的时候偶然发现了这个。。666666666已经有成熟的板子了。(以后慢慢尝试理解。。)

板子不可少!

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
namespace fast_IO
{
const int IN_LEN=10000000,OUT_LEN=10000000;
char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf;
char *lastin=ibuf+IN_LEN;
const char *lastout=ibuf+OUT_LEN-1;
inline char getchar_()
{
if(ih==lastin)lastin=ibuf+fread(ibuf,1,IN_LEN,stdin),ih=ibuf;
return (*ih++);
}
inline void putchar_(const char x)
{
if(ih==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;
*oh++=x;
}
inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}
}
using namespace fast_IO;
//#define getchar() getchar_()
//#define putchar(x) putchar_((x))
typedef long long LL;
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
//template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(a%b==0)return b;return gcd(b,a%b);}
template <typename T> inline void read(T&x)
{
char cu=getchar();x=0;bool fla=0;
while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}
while(isdigit(cu))x=x*10+cu-'0',cu=getchar();
if(fla)x=-x;
}
template <typename T> void printe(const T x)
{
if(x>=10)printe(x/10);
putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{
if(x<0)putchar('-'),printe(-x);
else printe(x);
}
int n,sum[11],ans;
void DFS(const int x,const int all)
{
if(x==11&&all==n)
{
ans++;
return;
}
if(all>n)return;
if(x>10)return;
for(sum[x]=1;sum[x]<=3;sum[x]++)
DFS(x+1,all+sum[x]);
}
void dfs(const int x,const int all)
{
if(x==11&&all==n)
{
for(register int i=1;i<=10;i++)print(sum[i]),putchar(' ');
putchar('\n');
return;
}
if(all>n)return;
if(x>10)return;
for(sum[x]=1;sum[x]<=3;sum[x]++)
dfs(x+1,all+sum[x]);
}
int main()
{
read(n);
DFS(1,0);
print(ans),putchar('\n');
dfs(1,0);
return 0;
}

错误解法: 决策树

因为要字典序,那就贪心优先+倒序DFS就行了。(实在是办不到辣~~我放弃了。。因为遍历完成以前不知道是否合法)


勇士,竟然来到了BOSS的老巢!来一场恶斗,证明自己的实力,解锁下一个级别!


P1426 小鱼会有危险吗 等比数列+灯

题目描述

有一次,小鱼要从A处沿直线往右边游,小鱼第一秒可以游7米,从第二秒开始每秒游的距离只有前一秒的98%。有个极其邪恶的猎人在距离A处右边s米的地方,安装了一个隐蔽的探测器,探测器左右x米之内是探测范围。一旦小鱼进入探测器的范围,探测器就会在这一秒结束时把信号传递给那个猎人,猎人在一秒后就要对探测器范围内的水域进行抓捕,这时如果小鱼还在这范围内就危险了。也就是说小鱼一旦进入探测器范围,如果能在下1秒的时间内马上游出探测器的范围,还是安全的。现在给出s和x的数据,请你判断小鱼会不会有危险?如果有危险输出’y’,没有危险输出’n’。

//感谢黄小U饮品完善题意

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
20
21
22
#include<bits/stdc++.h>
using namespace std;

int s, x;

bool activate(double dis){
return dis >= s - x; //注意辐射半径
}

int main(){
cin>>s>>x;
double it = 7, dis = 0;
while(!activate(dis)){
dis += it; it*=0.98;
}
if(dis - s + it*0.98 > 2*x){
cout<<"n";
}
else{
cout<<"y";
}
}

公式法 $O(1)$

等比求和公式:

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 s, x;

double fun(double Sn){
return log(1 - Sn*(1-0.98)/7)/log(0.98);
}

int main(){
cin>>s>>x;

if(fun(s+x) - fun(s-x) < 1){ //小于1s,则安全
cout<<"n";
}
else{
cout<<"y";
}
}

小于1s,则区间内包含的每秒里程点不超过1个,则总是能1s内跳过。

P1464 Function 记忆宏

1548580075159

说明

记忆化搜索

Code

模拟。状态方程都给出来了。。规模比较小。。

递归+记忆+宏函数

直接定义一个记忆宏就行辣。(重复写那么多会累死orz)

调试会死人的好吧?

然而写了一个记忆宏以后,代码立刻就清晰了!

1
#define W_MEM(x,y,z) (w_mem[x][y][z] ? w_mem[x][y][z] : w_mem[x][y][z] = w(x, y, z))

意思就是W被求过,就返回W,否则将求得的值先赋给W然后返回。

这样之后很快调出了之前的1个BUG,表达式后面有减号啊喂!!!WTF!!!

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

#define W_MEM(x,y,z) (w_mem[x][y][z] ? w_mem[x][y][z] : w_mem[x][y][z] = w(x, y, z))

int a=1,b=1,c=1;
int w_mem[25][25][25];

int w(int a, int b, int c){
if(a<=0 || b<=0 || c<=0) return 1;
if(a > 20 || b > 20 || c > 20) return W_MEM(20,20,20);
if(a < b && b < c) return W_MEM(a,b,c-1)+W_MEM(a,b-1,c-1) - W_MEM(a,b-1,c);
return W_MEM(a-1,b,c)+W_MEM(a-1,b-1,c)+W_MEM(a-1,b,c-1) - W_MEM(a-1,b-1,c-1);
}

int main(){
while(1){
cin>>a>>b>>c;
if(a==-1 && b==-1 && c==-1) break;
cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<w(a,b,c)<<endl;
}
}

*P1014 Cantor表 数论

题目描述

现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的:

1/1 , 1/2 , 1/3 , 1/4, 1/5, …

2/1, 2/2 , 2/3, 2/4, …

3/1 , 3/2, 3/3, …

4/1, 4/2, …

5/1, …

… 我们以Z字形给上表的每一项编号。第一项是1/1,然后是1/,2/1,3/1,2/2,…

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;

int main(){
int N; cin>>N;
int i = 2;
bool flag = 1;
int count = 0;
while(i<N){
if(flag){ //zigzag的方向每次都相反,所以用flag控制
int number = i - 1; //模拟生成cantor数
while(number > 0){
if(++count == N){ //如果统计到了N就输出
cout<<number<<"/"<<i-number<<endl;
break;
}
number--;
}
}
else{
int number = 1;
while(number < i){
if(++count == N){
cout<<number<<"/"<<i-number<<endl;
break;
}
number++;
}
}
flag = !flag; //调转flag
i++;
}
}

快速枚举 $O(\sqrt n)$

由于每个循环增长的分式个数是一个等差级数:$1+2+3+…+k$。则可以快速定位到斜线。

因为用k步跳过的总数目约为n=(1+k)k/2,所以复杂度是O(k)也就是$O(\sqrt n)$。

只须在while(i<N)额外补充一下跳跃代码:

1
2
3
4
5
6
int K = 1;
while(i*K < N){
count += K++;
i++;
flag = !flag;
}

比较简单的写法:(结合奇偶)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,k=1;
cin>>n;

while (n>k) {
n=n-k;
k++;
}

if(k%2==0) cout<<n<<"/"<<(k+1-n);
else cout<<k+1-n<<"/"<<n;
return 0;
}

作者: 哦哟筷子
更新时间: 2018-12-16 22:40

在Ta的博客查看

*数论+二分 $O(logn)$

更快速的定位关键循环

作者: cplusplus
更新时间: 2017-12-10 11:13

在Ta的博客查看

发现第i条斜线(即分子分母之和=i+1的所有项)中包含i*(i-1)/2+1i*(i+1)中的每一项。

所以可以二分 [分子分母之和],再根据分子分母之和的奇偶性直接计算第n

时间复杂度O(㏒₂n),可以通过n≤10^18,加上高精可通过n≤10^1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cmath>
using namespace std;
int main(){
long long l=1,r,mid,n,a;
cin>>n;

r=n;
while(l<r){
mid=(l+r)/2;
if(mid*(mid+1)/2<n)l=mid+1;
else r=mid;
}

a=n-l*(l-1)/2;
if(l%2==0)cout<<a<<'/'<<l+1-a;
else cout<<l+1-a<<'/'<<a;
return 0;
}

*超级数论 $O(1)$

Cantor表里的每一个数都是行数除以列数【坐标】。

更多解法。各种叼炸天的数论分析。

作者: Clever_Jimmy
更新时间: 2018-07-13 13:36

在Ta的博客查看

作者: wmxwmx
更新时间: 2018-01-23 23:44

在Ta的博客查看

*P1022 计算器的改良 模拟

题目背景

NCLNCLNCL是一家专门从事计算器改良与升级的实验室,最近该实验室收到了某公司所委托的一个任务:需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手ZL先生。

题目描述

为了很好的完成这个任务,ZL先生首先研究了一些一元一次方程的实例:

4+3x=8

6a−5+1=2−2a

−5+12y=0

ZL先生被主管告之,在计算器上键入的一个一元一次方程中,只包含整数、小写字母及+、-、=这三个数学符号(当然,符号“-”既可作减号,也可作负号)。方程中并没有括号,也没有除号,方程中的字母表示未知数。

你可假设对键入的方程的正确性的判断是由另一个程序员在做,或者说可认为键入的一元一次方程均为合法的,且有唯一实数解。

Code

Force $O(n)$

考虑自动机+循环展开(成两个循环)。。

  • 设置变量系数Var和常数Const,初始flag为正
  • 顺序读入
    • 遇到数字先缓存
    • 遇到字母将缓存根据flag加入Var,清空缓存(记录字母)
    • 遇到+将缓存根据flag加入Const,变flag为正,清空缓存
    • 遇到-将缓存根据flag加入Const,变flag为负,清空缓存
    • 遇到=则加入Const,清空缓存并退出
  • 将变量系数Var和常数Const变号
  • 然后再继续读入(虽然理论上两个读入可以合到一个函数里然而懒的改了orz
    • 遇到数字先缓存
    • 遇到字母将缓存根据flag加入Var,清空缓存(记录字母)
    • 遇到+将缓存根据flag加入Const,变flag为正,清空缓存
    • 遇到-将缓存根据flag加入Const,变flag为负,清空缓存
    • 遇到\n则加入Const,清空缓存并退出【只有这里不一样】
  • X = - Const / Var
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;

char buffer; //字符缓存
int Var, Const; //变量系数、常数系数
bool sign = 1; //变号器
int number_buf; //数字缓存
char letter_mem; //记忆字母

int main(){

while(1){ //顺序读入
buffer = getchar();
if(buffer <='9' && buffer >='0'){ //遇到数字先缓存
number_buf*=10;
number_buf+=(int)(buffer - '0');
// cout<<"buffer:"<<number_buf<<endl;
continue;
}
if(buffer <='z' && buffer >='a'){
letter_mem = buffer;
if(number_buf == 0) number_buf=1;
if(sign == 1) Var += number_buf;
else Var -= number_buf;
number_buf = 0;
// cout<<"--->字母系数Var:"<<Var<<endl;
continue;
}
if(buffer == '+'){
if(sign == 1) Const += number_buf;
else Const -= number_buf;
// cout<<"读取到:+"<<endl;
// cout<<"--->常数系数Const:"<<Const<<endl;
sign = 1;
number_buf = 0;
continue;
}
if(buffer == '-'){
if(sign == 1) Const += number_buf;
else Const -= number_buf;
// cout<<"读取到:-"<<endl;
// cout<<"--->常数系数Const:"<<Const<<endl;
sign = 0;
number_buf = 0;
continue;
}
if(buffer == '='){
if(sign == 1) Const += number_buf;
else Const -= number_buf;
sign = 1;
number_buf = 0;
break;
}
}

// cout<<"Var = "<<Var<<"; Const = "<<Const<<endl;

Var = -Var; Const = -Const;
while(1){ //顺序读入
buffer = getchar();
if(buffer <='9' && buffer >='0'){ //遇到数字先缓存
number_buf*=10;
number_buf+=(int)(buffer - '0');
// cout<<"buffer:"<<number_buf<<endl;
continue;
}
if(buffer <='z' && buffer >='a'){
letter_mem = buffer;
if(number_buf == 0) number_buf=1;
if(sign == 1) Var += number_buf;
else Var -= number_buf;
number_buf = 0;
// cout<<"--->字母系数Var:"<<Var<<endl;
continue;
}
if(buffer == '+'){
if(sign == 1) Const += number_buf;
else Const -= number_buf;
// cout<<"读取到:+"<<endl;
// cout<<"--->常数系数Const:"<<Const<<endl;
sign = 1;
number_buf = 0;
continue;
}
if(buffer == '-'){
if(sign == 1) Const += number_buf;
else Const -= number_buf;
// cout<<"读取到:-"<<endl;
// cout<<"--->常数系数Const:"<<Const<<endl;
sign = 0;
number_buf = 0;
continue;
}
if(buffer == '\n'){
if(sign == 1) Const += number_buf;
else Const -= number_buf;
sign = 1;
number_buf = 0;
break;
}
}

// cout<<"Var = "<<Var<<"; Const = "<<Const<<endl;
cout<<fixed<<setprecision(3)<<letter_mem<<"="<<(Const == 0 ? Const : -(double)Const/(double)Var);
}

未考虑到的样例:

  • 读入等号后不仅要退出,还要清空缓存

20+3x=-18:第二次循环前变号时还要重新初始化sign=1

模拟退火 orz

作者: Anakin
更新时间: 2018-10-28 11:23

在Ta的博客查看

数值逼近

第一步:把输入的方程转化成 f(x) = 0 的形式

第二步:用二分法逼近求该函数的近似根

作者: xzzhangqiaochu
更新时间: 2018-10-26 00:13

在Ta的博客查看

P1307 数字反转 模拟

题目描述

给定一个整数,请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零(参见样例2)。

说明

数据范围

−1,000,000,000≤N≤1,000,000,000

noip2011普及组第一题

Code

这个题位置放错了吧,超简单。用升级版的C++代码直接就能过。。

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
#include <bits/stdc++.h>
using namespace std;

void reverse(vector<char> &str, int i, int j){ //reverse every part
j--;
while(i < j){
char tmp = str[i];
str[i] =str[j];
str[j] = tmp;
i++; j--;
}
}

int main(){
vector<char> str; str.resize(25, 'F'); //initialize every char to 'F'
char tmp;
string STR; cin>>STR;
int i = 0; int len = STR.length();
while(i < len){
str[i] = STR[i]; i++;
}

int num1=0, symbol, num2;

while(str[num1] >= '0' && str[num1] <= '9') num1++;
symbol = num1; num2 = symbol + 1;
while(str[num2] !='F') num2++;

// cout<<endl<<"num1:"<<num1<<" symbol:"<<symbol<<" num2"<<num2<<endl;


int real_begin=0;
while(str[real_begin] == '0' && str[real_begin+1] <= '9' && str[real_begin+1] >= '0') real_begin++;
reverse(str, real_begin , num1);

// i=0;
// while(str[i] != 'F'){
// cout<<str[i++];
// }
// cout<<endl;
while((str[num2 - 1] == '0' && str[num2 - 2] <= '9' && str[num2 - 2] >= '0') || str[num2 - 1] == 'F') num2--;
reverse(str, symbol + 1, num2);

int begin = real_begin, end = num2; //fiter zeros in the begining and end
while(str[begin] == '0' && str[begin+1] <= '9' && str[begin+1] >= '0') begin++;
while((str[end - 1] == '0' && str[end - 2] <= '9' && str[end - 2] >= '0') || str[end - 1] == 'F') end--;

i= begin;
while(i < end){
cout<<str[i++];
}
}

Python稍微改了改。。。

1
2
3
4
5
6
7
import re
s = re.split('(\-)', input())
if s[0] != '':
print(int(str(int(s[0]))[::-1]),end='')
else:
print(s[1],end='')
print(int(str(int(s[2]))[::-1]),end='')

0%