牛客寒假训练赛2

赶时间 不多说了 七点要去打小米oj月赛
https://ac.nowcoder.com/acm/contest/327#question


放四题

D:
大水题,签到的
模拟:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
int n;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]<60)ans++;
}
cout<<ans*400<<endl;
return 0;
}

J:
贪心,一开始写MLE了
因为我会用到一个bool s[1e9+9]的数组,这显然崩了
后来只好重新写,以为麻烦其实也还好了

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 <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int need;
int begin;
int over;
}muse[100005];
bool cmp(node a,node b){
return a.begin<b.begin;
}
signed main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>muse[i].need;
}
for(int i=0;i<n;i++){
cin>>muse[i].begin;
}
sort(muse,muse+n,cmp);
/*cout<<"sort"<<endl;
for(int i=0;i<n;i++)
cout<<muse[i].begin<<" "<<muse[i].need<<endl;
cout<<endl;*/
if(muse[0].begin<muse[0].need){
cout<<"NO"<<endl;
}
else {
int ans=muse[0].begin-muse[0].need;
for(int i=1;i<n;i++){
ans+=muse[i].begin-muse[i-1].begin-2;
if(ans<muse[i].need){
cout<<"NO"<<endl;
return 0;
}
else {
ans-=muse[i].need;
}
}
cout<<"YES"<<endl;
return 0;
}
return 0;
}

G:
复读机
一开始没有思路后来想用分类,写到一半觉得有些情况不知道怎么处理,就挂机了
赛后看了题解觉得长就直接跑去看了别人的AC代码,简短易懂,真幸运
有两种方法一种是DP,一种是DFS
dp 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 <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int dp[3202][3202];
int main(){
string a,b;
cin>>a>>b;
int la=a.length();
int lb=b.length();
memset(dp,inf,sizeof(dp));
for(int i=1;i<=la;i++)
dp[i][0]=i;
for(int i=1;i<=lb;i++)
dp[0][i]=i;
dp[0][0]=0;
for(int i=1;i<=la;i++){
for(int j=1;j<=lb;j++){
if(a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
}
}
}
if(dp[la][lb]<=2)
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}

dfs 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
#include <bits/stdc++.h>
using namespace std;
int flag = 0;
string a, b;
int lena , lenb;
void dfs(int i , int j , int ans)
{
if(flag||ans>2)
return ;
if(i>=lena&&j>=lenb)
{
flag=1;
return ;
}
if(a[i]==b[j])
dfs(i+1,j+1,ans);
else
{
dfs(i,j+1,ans+1);//删除
dfs(i+1,j,ans+1);//添加
dfs(i+1,j+1,ans+1);//替换
}
}
int main(void)
{
cin>>a>>b;
lena=a.length();
lenb=b.length();
dfs(0,0,0);
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}

感觉对我来说dp更容易看懂,但是其实我觉得DFS更好想但是不好写出来,DP对我来说不够熟悉

C:
算是和数学有关系吧,但是我跟觉得这是找规律吧..

如图:1=3^0,3^1,9=3^2;
而1 3 9 分别需要用1 2 3个砝码
也就是说
1个只能称1
2个可以是1-4
3个可以是1-13
4个可以是1-40

官方解释:

那么考虑到高精度可以使用py大法:

1
2
3
4
5
6
7
8
9
10
11
12
13
'''输入
复制
20
输出
复制
4'''
n=int(input())
k=1
ans=1
while k<n:
ans=ans+1
k=3*k+1
print(ans)

C++大数当然也可以写,但是麻烦啊
不过我看有人long double 也给过了我就试了下确实可以:
牛批老哥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n;
cin>>n;
int ans=1;
int k=1;
while(k<n){
ans++;
k=3*k+1;
}
cout<<ans<<endl;
return 0;
}

话说回来,这场比赛大概最大的亮点就是处女座的硬核签到题了
A题:处女座的签到题,比赛开始两小时好像就一个过了的…tql
处女座牛逼,波大女神牛逼!

晚风。
coswindy

-------------本文结束感谢您的阅读-------------