寒假营第二场题解

Easy：A、B、F、G

Mid：D、J、K

Hard：C、E、H、M

AK：I、L

A 一起奏响历史之音！

https://ac.nowcoder.com/acm/contest/95334/A

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<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int ok=1;
    for(int i=1;i<=7;i++)
    {
        int x;
        cin>>x;
        if(x==4||x==7)ok=0;
    }    
    if(ok)cout<<"YES\n";
    else cout<<"NO\n";

    return 0;    
}

B 能去你家蹭口饭吃吗

https://ac.nowcoder.com/acm/contest/95334/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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    int shu=a[n/2+1];
    cout<<shu-1<<'\n';    

    return 0;    
}

F 一起找神秘的数！

https://ac.nowcoder.com/acm/contest/95334/F

很经典的一个结论 a+b = (a or b) + (a and 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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    while(n--)
    {
        int x,y;
        cin>>x>>y;
        cout<<y-x+1<<'\n';
    }    

    return 0;    
}

G 一起铸最好的剑！

https://ac.nowcoder.com/acm/contest/95334/G

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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
ll power(ll x,ll y)
{
    ll ret=1;
    while(y)
    {
        if(y&1)ret=ret*x;
        x=x*x;
        y>>=1;
    }
    return ret;
}
void solve(){
    int n,m;
    cin>>n>>m;
    if(m==1)return cout<<1<<'\n',void();
    int shu=log(n)/log(m);
    set<pair<int,int>>s;
    for(int i=-2;i<=2;i++)
    {
        if(shu+i>=1)
        s.insert({abs(power(m,shu+i)-n),shu+i});
    }
    cout<<(*s.begin()).second<<'\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

J 数据时间？

https://ac.nowcoder.com/acm/contest/95334/J

超级大模拟

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;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);   
    int n,h,m;
    cin>>n>>h>>m;
    set<string>s1,s2,s3;
    string a1="07:00:00",b1="09:00:00",a2="18:00:00",b2="20:00:00",a3="11:00:00",b3="13:00:00",a4="22:00:00",b4="24:00:00",a5="00:00:00",b5="01:00:00";
    for(int i=1;i<=n;i++)
    {
        string id,date,time;
        cin>>id>>date>>time;
        if(stoi(date.substr(0,4))==h&&stoi(date.substr(5,2))==m)
        {
            if((time>=a1&&time<=b1)||(time>=a2&&time<=b2))
            {
                s1.insert(id);
            }
            else if((time>=a3&&time<=b3))s2.insert(id);
            else if((time>=a4&&time<=b4)||(time>=a5&&time<=b5))s3.insert(id);
        }
    }
    cout<<s1.size()<<' '<<s2.size()<<' '<<s3.size();

    return 0;    
}

K 可以分开吗？

https://ac.nowcoder.com/acm/contest/95334/K

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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
const int N=510;
char a[N][N];
bool vis[N][N];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int shu=0;
char dix='2';
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    auto dfs=[&](auto self,int x,int y)->void{
        vis[x][y]=1;    
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]=='1'&&!vis[xx][yy])
            {
                self(self,xx,yy);
            }
        }
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
            {
                if(a[xx][yy]!=dix&&a[xx][yy]!='1')
                {
                    a[xx][yy]=dix;
                    shu++;
                }
            }
        }
    };
    int minn=INT_MAX;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='1'&&!vis[i][j])
            {
                shu=0;
                ++dix;
                dfs(dfs,i,j);
                minn=min(minn,shu);
            }
        }
    }
    cout<<minn<<'\n';
    return 0;    
}