Part1 3/3

求出两个数的最大公约数

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int gcd(int a,int b);
int main()
{
system("pause");
return 0;
}
int gcd(int a,int b)
{
if(a%b==0) return b;
return gcd(b,a%b);
}

Question From:HERE

判断给定的链表中是否有环。如果有环则返回true,否则返回false。

  • My Code
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
#include <iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool hasCycle(ListNode *head);
int main()
{
system("pause");
return 0;
}
bool hasCycle(ListNode *head)
{
ListNode *slow=head,*fast=head;
while(slow&&fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast) return true;
}
return false;
}
  • 思路:定义快慢指针,若慢指针能追上快指针,说明链表中存在环,否则不存在;

Question From:HERE

Part2 3/5

TRDD开了一家免费WiFi体验店, 所有人都可以免费连接WiFi, 只有一个条件, 你要提前一天预约。今天,TRDD收到了n(1 <= n <=1000)个人的预约, 每个人有一个时间段[L, R] (1 <= L <= R <= 5000)表示这个人预约连接WiFi从L时刻到R时刻。 但是市面上只有一种路由器, 这种路由器单台最多能同时连接m(n <= 100)台设备, TRDD想要知道最少使用多少台路由器就能保证明天每个人都能连上WiFi。

  • 思路:首先在纸上直角坐标系,可以清晰地找到最大值;

  • 在C++中,通过定义二维数组来模拟坐标系;

  • 每当有人来使用WiFi时,找到可以使x=l和x=r之间(x,y)恒等于0的y的最小值,将(l,y),(l+1,y)…(r,y)全部置1,问题得解;

  • 不过由于题目中n为1000,定义一个[1000] [1000]的二维数组在提交时提示越界。

  • Answer

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
#include <iostream>
using namespace std;
int main(){
int n,m;
int a[5001]={0};
cin>>n>>m;
int Max=1e-7;
while(n--){
int l,r;
cin>>l>>r;
for(int i=l;i<=r;i++){
a[i]++;
if(a[i]>Max){
Max=a[i];
}
}
}
int result;
if(Max%m==0){
result = Max/m;
}
else{
result = Max/m+1;
}
cout<<result<<endl;
}
  • 思路:与我思路相似,不过在实现时将二维数组改为一维数组,二维数组的纵坐标即为一维数组中的元素大小,输入所有人的时间后,找到最大值,问题得解。

Question From:HERE

Part3 3/6

tabris有一个习惯,无聊的时候就会数圈圈,无论数字还是字母。

现在tabris更无聊啦,晚上睡不着觉就开始数羊,从a只数到b只。

顺便还数了a到b之间有多少个圈。

但是tabris笨啊,虽然数羊不会数错,但很可能数错圈的个数。

但是tabris很难接受自己笨这个事实,所以想问问你他一共应该数出多少个圈,这样tabris才好判断他到底笨不笨啊。

  • My Code
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
#include <iostream>
using namespace std;
int main()
{
int t;
while(cin>>t)
{
int a,b;
for(int i=0;i<t;i++)
{
cin>>a>>b;
int sum=0;
for(int j=a;j<=b;j++)
{
int temp=j;
while(temp!=0)
{
int r=temp%10;
if(r==4||r==6||r==9||r==0) sum++;
else if(r==8) sum=sum+2;
temp=temp/10;
}
}
cout<<sum<<endl;
}
}
system("pause");
return 0;
}
  • 思路:暴力循环即可。

Question From:HERE

Part4 3/7

Atsa just bought Super Mario Maker and wants to test your skills for an analysis with a level that he prepared.

  • My Code
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
#include <iostream>
using namespace std;
int main()
{
int l,g;
while(cin>>l>>g)
{
int max=0;
for(int i=0;i<g;i++)
{
int p,d;
cin>>p>>d;
if(d==0&&d>max)
{
max=d;
}
else if(d==1&&l-d>max)
{
max=l-d-1;
}
}
cout<<max<<endl;
}
system("pause");
return 0;
}
  • 思路:相撞并不影响走的距离,就像高中物理,质量相同的两小球相撞,无能量损失,碰撞后都按原来相反方向相同速率运动。

Question From:HERE

妞妞希望能选取最大数量的硬币,使其总价值足以支付车费并且出租车司机能接受。 妞妞希望你能帮她计算最多可以支付多少个硬币。

  • My Code
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
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,s;
while(cin>>n>>s)
{
int p[20]={};
for(int i=0;i<n;i++) cin>>p[i];
sort(p,p+n);
int temp=0,ans=0,i=0;
while(temp<s)
{
temp=temp+p[i];
ans++;
i++;
}
for(int i=ans-1;i>=0;i--)
{
if(temp-p[i]>=s)
{
ans--;
temp=temp-p[i];
}
}
cout<<ans;
}
system("pause");
return 0;
}
  • 思路:将硬币大小从小到大排序,用循环拿硬币,直到钱已经大于车费时停止循环;再在所拿的硬币中从大到小取出硬币,直到司机接受为止。

Question From:HERE

Part5 3/8

情人节到了,小芳和小明手牵手,打算过一个完美的情人节,但是小刚偏偏也来了,当了一个明晃晃的电灯泡,小明很尴尬,就和小刚说,我交给你个任务,你完成了我俩就带你玩,否则你就回家吧。小刚很有当单身狗的觉悟,他坚决不想让小明过好情人节,同为单身狗的你能帮帮他吗?现在有一个n×n(1 <= n <= 1000)的格子,每一个格子都有一个电灯泡,可能是亮的,也可能是灭的(1代表亮, 0代表灭),现在有两种操作,一种是给你一个坐标,对于那个坐标上的灯泡,如果他是亮的,那么熄灭他,反之如果他是灭的,那么打开它。第二种操作是给你两个坐标,第一个坐标代表一个子矩阵的左上角,另一个坐标是右下角,请你求出当前子矩阵中有多少个灯泡是亮着的。燥起来吧!!!单身狗们!!!!

  • My Code
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
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m)
{
int bulb[1010][1010]={};
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>bulb[i][j];
}
}
for(int i=0;i<m;i++)
{
int f;
cin>>f;
if(f==1)
{
int x,y;
cin>>x>>y;
if(bulb[x][y]==1) bulb[x][y]=0;
else if(bulb[x][y]==0) bulb[x][y]=1;
}
else if(f==2)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
int num=0;
for(int j=x1;j<=x2;j++)
{
for(int k=y1;k<=y2;k++)
{
if(bulb[j][k]==1) num++;
}
}
cout<<num<<endl;
}
}
}
system("pause");
return 0;
}

Question From:HERE

今天qwb要参加一个数学考试,这套试卷一共有n道题,每道题qwb能获得的分数为ai,qwb并不打算把这些题全做完,他想选总共2k道题来做,并且期望他能获得的分数尽可能的大,他准备选2个不连续的长度为k的区间,即[L,L+1,L+2,…,L+k-1],[R,R+1,R+2,…,R+k-1](R >= L+k)。

  • My Code
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 <iostream>
using namespace std;
int getSum(int a[],int l,int r);
int main()
{
int t;
while(cin>>t)
{
int n,k;
for(int i=0;i<t;i++)
{
cin>>n>>k;
int *a=new int [n+1];
for(int j=0;j<n;j++)
{
cin>>a[j];
}
int max=0;
for(int j=0;j+k+k<=n;j++)
{
for(int m=j+k;m+k<=n;m++)
{
int temp=getSum(a,j,j+k-1)+getSum(a,m,m+k-1);
if(temp>max) max=temp;
}
}
cout<<max<<endl;
}
}
system("pause");
return 0;
}
int getSum(int a[],int l,int r)
{
int sum=0;
for(int i=l;i<=r;i++)
{
sum=sum+a[i];
}
return sum;
}
  • 思路:暴力循环求解,超时。

  • 答案代码如下

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;
typedef long long ll;
ll a[2000005];
int main(){

ios::sync_with_stdio(0);
int _;cin>>_;
while(_--){
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
ll ma=-1e18,ans=-1e18;
for(int i=k;i+k<=n;i++){
ma=max(ma,a[i]-a[i-k]);
ans=max(ans,ma+a[i+k]-a[i]);
}
cout<<ans<<endl;
}

return 0;
}
  • 因为区间大小是固定为k的,所以显然需要前缀和处理一下
    处理之后我们去维护前缀中长度为k的最大值ma,枚举第二个长度为k的起点,那么答案就是max(ma+当前长度为k的序列和)

    复杂度为O(n)
    极限数据计算 n为2e5,k=1e5 所有ai都是1e5 那么最大值是2e5*1e5>(1<<31)-1 超过了int所能表示的范围 所以需要开long long
  • 定义数组a[0]=0; cin>>a, a[1]=a[1-1]+a; cin>>a, a[2]=a[2-1]+a; … cin>>a, a[n]=a[n-1]+a.
  • 通过单层for循环找到前两个最大值,问题得解。

Question From:HERE

Part6 3/9

良神爱吃甜点,如果他吃不到甜点的话就会很暴躁!现在桌子上摆着一排n个点心,每个点心具有一个甜度ai,良神一次能吃连续的一些点心,但是他一次不能吃总甜度和超过m(可以等于m),否则他就长不高啦!良神想要知道他最少吃几次才能把这些点心都吃完。

  • My Code
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
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m)
{
int *a=new int[n+1];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int ans=0;
int temp=0;
for(int i=0;i<n;i++)
{
if(temp+a[i]<=m)
{
temp=temp+a[i];
}
else
{
ans++;
temp=0;
i=i-1;
}
}
cout<<ans+1<<endl;
}
system("pause");
return 0;
}

Question From:HERE

大吉大利,今晚吃鸡——枪械篇

  • My Code
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
#include <iostream>
#include <iomanip>
using namespace std;
struct GUN
{
double p;
int k;
double accessory[1010]={};
};
struct ACCESSORY
{
int type;
double damage;
};
int main()
{
int n,m;
while(cin>>n>>m)
{
//输入n把枪的属性
//GUN *gun=new GUN[n+10];
GUN gun[1010];
for(int i=0;i<n;i++)
{
cin>>gun[i].p>>gun[i].k;//输入p,k
for(int j=0;j<gun[i].k;j++) cin>>gun[i].accessory[j];//输入第i把枪可以装备的配件种类,共k种
}
//输入m个配件的属性
//ACCESSORY *a=new ACCESSORY[m+10];
ACCESSORY a[1010];
for(int i=0;i<m;i++)
{
cin>>a[i].type>>a[i].damage;//输入配件的种类和威力
}
//找到每个配件的最大值
double *maxA=new double[m+10];
maxA[0]=-1;
for(int i=1;i<=m;i++)
{
double max=0;
for(int j=0;j<m;j++)
{
if(a[j].type==i&&a[j].damage>max) max=a[j].damage;
}
maxA[i]=max;
}
/*
for(int i=0;i<=m;i++)
{
cout<<i<<":"<<maxA[i]<<endl;
}
*/
double MAX=0;
for(int i=0;i<n;i++)
{
double tempG=gun[i].p;
double tempA=0;
for(int j=0;j<gun[i].k;j++)
{
tempA=tempA+maxA[int(gun[i].accessory[j])];
}
double temp=tempG*(1+tempA);
if(temp>MAX) MAX=temp;
}
cout<<fixed<<setprecision(4)<<MAX<<endl;
}
system("pause");
return 0;
}

Question From:HERE

Part7 3/10

现在给出一个赛区的规模,也就是这个赛区的实际参赛队伍数,小 Q 同学想知道有多少队伍的奖牌会由银变金、由铜变银、由铁变铜。

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
double n;
while(cin>>n)
{
double gold=n*0.1;
double silver=n*0.2;
double bronze=n*0.3;
int goldChange=0,silverChange=0,bronzeChange=0;
if(gold-(int)gold>0) goldChange=1;
if(silver-(int)silver>0) silverChange=goldChange+1;
else silverChange=goldChange;
if(bronze-(int)bronze>0) bronzeChange=silverChange+1;
else bronzeChange=silverChange;
cout<<goldChange<<" "<<silverChange<<" "<<bronzeChange<<endl;
}
system("pause");
return 0;
}

Question From:HERE

Part8 3/11

彩虹岛网红脸盆大哥最骄傲就是自己制作的木桶。一天𝑙𝑤𝑞拿了𝑛块木板,其中第𝑖块木板的高度为ℎ𝑖,他希望脸盆大哥能够用这些木板制作出精美的木桶。脸盆大哥告诉𝑙𝑤𝑞制作一个木桶需要𝑘块木板,并且所有桶的底面积为𝑠,底面的木板由𝑠𝑙𝑝提供。𝑙𝑤𝑞想知道用这些木块所制作出来的木桶最多能够盛多少体积的水。
注意,木板不能叠在另一个木板上,且不需要考虑木桶具体是怎么由木板组成的,即是说1块或2块木板也可以组成木桶,底面积仍为𝑠。

  • My Code
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 <iostream>
#include <algorithm>
#include <iterator>
#include <valarray>
using namespace std;
//int findMax(int h[]);
int main()
{
int t;
while (cin >> t)
{
while (t--)
{
int n, k, s;
cin >> n >> k >> s;
int height[1010]={};
for (int i = 0; i < n; i++)
cin >> height[i];
//for(int i=0;i<n;i++) cout<<height[i]<<" ";
//cout<<endl;
int ans = 0;
for (int i = 0; i < n / k; i++)
{
int min = 10000;
for (int j = 0; j < k; j++)
{
int max = *max_element(height, height + n);
//cout<<"max:"<<max<<endl;
if (max < min)
min = max;
//int index = *find(height, height + n, max) - 1;
int index=0;
for(int m=0;m<n;m++)
{
if(height[m]==max)
{
index=m;
break;
}
}
//cout<<"index:"<<index<<endl;
height[index] = -1;
}
//cout<<min*s<<endl;
ans = ans + min * s;
}
cout << ans << endl;
}
}
system("pause");
return 0;
}

Question From:HERE

银行的定期存款一般有1年期、2年期、3年期、5年期四种。
现在我们有1块钱,我们想知道,通过合理安排存款方式,n年以后这1块钱最多会变成几块钱。
假设在这n年里利率不变,且n年以后这笔钱不能处于2年期、3年期、5年期存款年限的中间(否则会变成活期)。

  • My Code
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
#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;
int main()
{
int n;
double r1,r2,r3,r5;
cin>>n>>r1>>r2>>r3>>r5;
double money=1;
while(n)
{
if(n>=5)
{
int time=n/5;
for(int i=0;i<time;i++)
{
money=money*pow(1+r5,5);
}
n=n%5;
}
else if(n>=3)
{
int time=n/3;
for(int i=0;i<time;i++)
{
money=money*pow(1+r3,3);
}
n=n%3;
}
else if(n>=2)
{
int time=n/2;
for(int i=0;i<time;i++)
{
money=money*pow(1+r2,2);
}
n=n%2;
}
else
{
money=money*(1+r1);
n--;
}
}
cout<<fixed<<setprecision(5)<<money<<endl;
system("pause");
return 0;
}
  • 思路:起初认为存钱年数越长,得到的本息越多,后发现这是错的;

  • 需要使用动态规划。

  • Answer

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
# include<iostream>
# include <cstdio>
# include <algorithm>
# include <math.h>
# define ll long long
using namespace std;
double max(double a,double b)
{
if(a>b)
return a;
else
return b;
}
double dp[40];
int main(){
int n;double r1,r2,r3,r5;
cin>>n>>r1>>r2>>r3>>r5;
r1=pow(1+r1,1);
r2=pow(1+r2,2);
r3=pow(1+r3,3);
r5=pow(1+r5,5);
dp[0]=1;
for(int i=1;i<=20;++i)
{
if(i>=1)dp[i]=max(dp[i-1]*r1,dp[i]);
if(i>=2)dp[i]=max(dp[i-2]*r2,dp[i]);
if(i>=3)dp[i]=max(dp[i-3]*r3,dp[i]);
if(i>=5)dp[i]=max(dp[i-5]*r5,dp[i]);
}
cout<<dp[n]<<endl;
return 0;
}
  • 动态规划

Question From:HERE

Part9 3/13

栗酱在酒桌上玩一个小游戏,第一个人从1开始数数,如果遇到数字中含4或者数字是4的倍数则跳过报下一个,数错了就要罚酒一杯。

  • My Code
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
#include <iostream>
using namespace std;
bool isFour(int num);
int main()
{
int n;
while(cin>>n)
{
for(int i=1;i<=n;i++)
{
if(i%4!=0&&isFour(i)) cout<<i<<endl;
}
}
system("pause");
return 0;
}
bool isFour(int num)
{
while(num!=0)
{
int rest=num%10;
if(rest==4) return false;
num=num/10;
}
return true;
}

Question From:HERE

坤酱想把一块圆形的布裁成正多边形,于是请你告诉坤酱正多边形的几个顶点应在哪里?

为了方便表示,圆给出在坐标系中,正多边形的第一个顶点固定在该圆在平行于x轴正方向最远的位置上,请按顺时针顺序输出所有的顶点。

  • My Code
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
#include <iostream>
#include <iomanip>
#include <math.h>
const double PI(acos(-1));
using namespace std;
int main()
{
int t;
while (cin >> t)
{
while (t--)
{
double x, y, r, n;
cin >> x >> y >> r >> n;
double angle = 2 * PI / n;
double tempAngle = 0;
for (int i = 0; i < n; i++, tempAngle = tempAngle - angle)
{
if(fabs(x+r*cos(tempAngle))<10e-6) cout<<"0.00 ";
else
cout << fixed << setprecision(2) << x + r * cos(tempAngle) << " ";
if(fabs(y+r*sin(tempAngle))<10e-6) cout<<"0.00"<<endl;
else
cout << fixed << setprecision(2) << y + r * sin(tempAngle) << endl;
}
}
}
system("pause");
return 0;
}
  • 思路:第一个顶点在原点右边;通过for循环以及cos和sin三角函数计算每次的横坐标和纵坐标改变量;
  • 注意:
    • 通过const double PI(acos(-1));定义PI来减小误差
    • 通过判断横纵坐标绝对值是否足够小来决定输出(避免输出-0.00),其中fabs为适用于double类型的绝对值函数。

Question From:HERE

Part10 3/14

中国文化的五行:金、木、水、火、土相生相克, 一天Alice和Bob玩起了卡牌游戏。卡牌包含5种类型Jin,Mu,Shui,Huo,Tu,分别代表金、木、水、火、土。 金克木,木克土,土克水,水克火,火克金。游戏规则如下: 两人玩n轮,每轮各自抽取一张卡牌,如果其中一个人的牌克制另一个人的牌那么这个人得3分,另一个人得0分。没有克制关系两人都得1分。最后得分高的获胜。

  • My Code
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
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int getLevel(string s);
int main()
{
int n;
while(cin>>n)
{
int score1=0,score2=0;
while(n--)
{
string s1,s2;
cin>>s1>>s2;
int Alice=getLevel(s1),Bod=getLevel(s2);
if(abs(Alice-Bod)==1)
{
if(Alice>Bod) score1=score1+3;
else score2=score2+3;
}
else if(abs(Alice-Bod)==4)
{
if(Alice==1) score1=score1+3;
else score2=score2+3;
}
else
{
score1++;
score2++;
}
}
if(score1>score2) cout<<"Alice"<<endl;
else if(score1<score2) cout<<"Bob"<<endl;
else cout<<"Draw"<<endl;
}
system("pause");
return 0;
}
int getLevel(string s)
{
if(s=="Jin") return 5;
if(s=="Mu") return 4;
if(s=="Tu") return 3;
if(s=="Shui") return 2;
else return 1;
}

小明在坐景驰科技研发的无人车到达了目的地。 景驰科技(JingChi.ai)是一家由人工智能技术驱动、以无人驾驶技术为核心的智能出行公司。它将打造面向中国市场的全无人驾驶。从无人车下来以后,小明看到了一个长长的楼梯。 有一个n级台阶的楼梯,小明一次可以向上跳1步,两步,甚至是n步,请问小明跳到n级台阶有多少种跳法?

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int f(int n)
{
if(n==1)
return 1;
return 2*f(n-1);
}
int main()
{
int t,n;
cin>>t;
while(t--){
cin>>n;
cout<<f(n)<<endl;
}
return 0;
}
  • 思路:f(0)=1
    1. n=1,f(1)=1;
    2. n=2,第一步有两种跳法,分别为一次跳一步和一次跳两步。跳一步时,第二步有一种跳法,即f(1);跳两步时,不用跳第二步,也就是有一种跳法f(0)。所以f(2)=f(1)+f(0)。
    3. n=3,第一步有三种跳法,分别为1,2,3。跳一步时,第二步有f(2)种跳法;跳两步时,第二步有f(1)种跳法;跳三步时,第二步有f(0)种跳法。所以f(3)=f(2)+f(1)+f(0),又因为f(2)=f(1)+f(0),所以f(3)=2*f(2)。
  • 推广到n时,f(n)=2*f(n-1)。

Question From:HERE

Part11 3/15

点点是一名出色的狼人。众所周知,狼人只有在满月之夜才会变成狼。同时,月亮的大小随着时间变化,它的大小变化30天为一循环。它的变化情况(从第一天开始)为0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 然后又再一次循环。今年夏天点点很无聊,于是开始看月亮。由于点点很忙,所以他只选择一段连续的时间看月亮,并把月亮的大小记录了下来。现在,他告诉你他记录下东西,让你告诉他下一天(即点点记录下的最后一天的第二天)的月亮是比前一天(即点点记录下的最后一天)大还是小。

  • My Code
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
#include <iostream>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
if (n == 1)
{
int a;
cin >> a;
if (a == 15)
cout << "DOWN" << endl;
else if (a == 0)
cout << "UP" << endl;
else
cout << "-1" << endl;
continue;
}
else
{
int a = 0, b = 0;
int situation = 0;
for (int i = 1; i <= n; i++)
{
if (i < n - 1)
{
int x;
cin >> x;
}
else
{
if (i == n - 1)
cin >> a;
else if (i == n)
{
cin >> b;
if (a > b)
situation = -1;
else
situation = 1;
}
}
}
if (b == 15)
cout << "DOWN" << endl;
else if (b == 0)
cout << "UP" << endl;
else if (situation == 1)
cout << "UP" << endl;
else if (situation == -1)
cout << "DOWN" << endl;
//0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
}
}
system("pause");
return 0;
}
  • 注意:
    • n==0时不是全部不能判断;
    • 只取输入的后两位时,前面还有n-2个数会输入。

Question From:HERE

Part12 3/16

小明现在在玩一个游戏,游戏来到了教学关卡,迷宫是一个N*M的矩阵。小明的起点在地图中用“S”来表示,终点用“E”来表示,障碍物用“#”来表示,空地用“.”来表示。障碍物不能通过。小明如果现在在点(x,y)处,那么下一步只能走到相邻的四个格子中的某一个:(x+1,y),(x-1,y),(x,y+1),(x,y-1);小明想要知道,现在他能否从起点走到终点。

  • Answer
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int f;
int s,e;
int vis[505][505];
char a[505][505];
int dir[][2]={{-1,0}, {1 ,0} , {0,-1} ,{0,1}};//方向 上 下 左 右
void dfs(int x,int y)
{
if(x==s&&y==e)
{
f=1;
}
for(int i=0;i<4;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(a[xx][yy]!='#'&&!vis[xx][yy]&&xx>=0&&xx<n&&yy>=0&&yy<m)
{
vis[xx][yy]=1;
dfs(xx,yy);
}
}
}
int main()
{
int sv,se;
while(cin>>n>>m)
{
f=0;
memset(vis,0,sizeof(vis));
memset(a,0,sizeof(a));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf(" %c",&a[i][j]);
if(a[i][j]=='S'){sv=i,se=j;}
if(a[i][j]=='E'){s=i,e=j;}

}
}
dfs(sv,se);
if (f) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
  • 深度优先算法DFS

Question From:HERE

栗酱突发闲心,玩了一会儿仙剑。她玩的这个版本的仙剑非常简单,打架的时候,每次只有一个小怪,栗酱也只有一个主角,主角在每回合开始先攻击小怪,小怪有a点生命值,主角有b点生命值,小怪有c点攻击力,主角有d点攻击力,每次攻击都会造成确确实实的攻击力的伤害。生命值小于等于零时就会挂掉。栗酱发现好像战斗一开始就已经能知道结果了,请你帮她算一下,这样她就可以挂机去做更有趣的事了。数据保证攻击力和初始生命值均大于等于1。

  • My Code
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 <iostream>
using namespace std;
int main()
{
int t;
while (cin >> t)
{
while (t--)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
//cout<<a<<" "<<b<<endl;
while (1)
{
a = a - d;
if (a <= 0)
{
cout << "Yes" << endl;
break;
}
b = b - c;
if (b <= 0)
{
cout << "No" << endl;
break;
}
//cout<<a<<" "<<b<<endl;
}
}
}
system("pause");
return 0;
}

Question From:HERE

Part13 3/19

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

bool cmp(pair<int, int>a, pair<int, int>b)
{
return a.first<b.first;//根据fisrt的值升序排序
//return a.second<b.second;//根据second的值升序排序
}
typedef pair<int, int> p;

int main()
{
int n,k;
while(cin>>n>>k)
{
//pair<int,int> dawn[1000010];
//pair<int,int> dusk[1000010];
p *dawn=new p[n+1];
p *dusk=new p[n+1];
for(int i=0;i<n;i++){
int x;
cin>>x;
dawn[i]=make_pair(x,i);
//cin>>dawn[i].first;
//dawn[i].second=i;
}
sort(dawn,(dawn+n),cmp);
for(int i=0;i<n;i++){
int x;
cin>>x;
dusk[i]=make_pair(x,i);
//cin>>dusk[i].first;
//dusk[i].second=i;
}
sort(dusk,(dusk+n),cmp);
int sweet=0;
for(int i=0,index=n-1;i<=k;i++,index--)
{
int index1=dawn[index].second;
int index2=dusk[index].second;
int max1=dawn[index].first;
int max2=dusk[index].first;
if(index1==index2)
{
if(max1>=max2)
{
sweet=sweet+max1;
dawn[index1].first=0;
dusk[index2].first=0;
}
else
{
sweet=sweet+max2;
dawn[index1].first=0;
dusk[index2].first=0;
}
}
else
{
sweet=sweet+max1+max2;
dawn[index1].first=0;
dusk[index1].first=0;
dawn[index2].first=0;
dusk[index2].first=0;
}
//cout<<max1<<" "<<max2<<endl;
//cout<<sweet<<endl;
}
cout<<sweet<<endl;
delete [] dawn;
delete [] dusk;
}
system("pause");
return 0;
}
  • 思路:对甜度从小到大排序,每次取早上甜度的最大值和晚上甜度的最大值进行比较,分为块数相同和不同两种情况。若块数相同,则增加该块数的早晚甜度最大值;若块数不同,则增加这两个
  • 思路错误,明天再更>_<

Question From:HERE

Part14 3/27

巴啦啦能量,沙鲁沙鲁,小魔仙大变身:对于一个数,把他所有位上的数字进行加和,得到新的数。

如果这个数字是个位数的话,那么他就满足条件。

  • My Code
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
#include <iostream>
using namespace std;
typedef long long ll;
ll solution(ll n);
int main()
{
ll n;
while (cin >> n)
{
int ans=solution(n);
while(ans>=10){
ans=solution(ans);
}
cout<<ans;
}
system("pause");
return 0;
}
ll solution(ll n)
{
int ans = 0;
while (n / 10 != 0)
{
ans = ans + n % 10;
n = n / 10;
}
ans = ans + n;
return ans;
}

Question From:HERE

Forever97与未央是一对笔友,他们经常互相写信。有一天Forever97去邮局寄信,发现邮局的收费方式变成了按字收费,收取的费用为总字数除了其自身以外的最大因子。虽然Forever97是一个有情调的人,但他不想因新收费方式而破财,所以他打算把信分成几份寄出去来减少邮费。已知Forever97写的信共有n个字,可以拆成无数封信,也可以不拆,每封信最少为2个字。求Forever97最少需要付多少邮费?

  • My Code
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
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool isPrime(int n);
int main()
{
int t;
while(cin>>t)
{
while(t--)
{
int n;
cin>>n;
if(isPrime(n)) cout<<"1"<<endl;
else if(n%2==0) cout<<"2"<<endl;
else if(isPrime(n-2)) cout<<"2"<<endl;
else cout<<"3"<<endl;
}
}
system("pause");
return 0;
}
// bool isPrime(int n)
// {
// for(int i=2;i<=n/2+1;i++)
// {
// if(n%i==0) return false;
// }
// return true;
// }
bool isPrime(int x)//判断是不是是素数
{
int l=sqrt(x*1.0);
for(int i=2;i<=l;i++)
{
if(x%i==0) return 0;
}
return 1;
}
  • 思路:找到n可以被分为最少几个质数;
  • 需要注意的是
    • 不是所有合数都能分成两个质数的和,例如27、35、51等奇合数;
    • 大于2的偶数都可以表示为两个质数的和。
  • 所以,这道题一共只有三种输出:1,2和3。
  • 注意:在使用函数判断一个数是否为质数时,在for循环中只需循环至根号n即可。

Question From:HERE

Points

  • C++对double类型取余

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    include <math.h>
    double a,b;
    fmod(double a,double b);//a对b取余
    modf(double a,double *b);//将参数的整数部分通过指针回传,返回小数部分
    //Example
    #include <iostream>
    #include <math.h>
    using namespace std;
    int main()
    {
    double a = 12.4, b = 3;
    double c=0;
    cout << fmod(a, b) << endl
    << modf(a, &c) << endl
    << c << endl;
    system("pause");
    return 0;
    }
    /*
    输出:
    0.4
    0.4
    12
    */
  • C++ max_element find max

  • 深度优先算法DFS