比赛记录

第一次AK周赛

比赛传送门

A

开始时间 +$5$(mod24) 即可

Code

1
2
3
4
5
void solve() {
    int n;
    cin >> n;
    cout << (n+5)%24 <<el;
}

B

五的倍数,即末位数字为 $0$ 或 $5$ 且数字本身不为 $0$
但据数据范围可知 $n$ 不为 $0$ ,无需特判直接判断每一位看看是不是 $5$ 或 $0$即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
    int n;
    cin >> n;
    while (n) {
        int t=n%10;
        if (t==5 || t==0) {
            cout <<"YES"<<el;
            return;
        }
        n=n/10;
    }
    cout<<"NO"<<el;
}

C

对于$(2≦i≦n)$ 如果gcd(a[i],a[i-1])为 $1$ ,那么肯定要修改,可以修改为任意正整数,那就修改成相邻的数的倍数,这样左右邻居都能保留不用修改

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans=0;
    if (a[1]==1) {
        ans++;
        a[1]=a[2];
    }
    for (int i = 2; i <= n; i++) {
        int t=gcd(a[i],a[i-1]);
        if (t<=1) {
            ans++;
            if (i!=n) a[i]=a[i-1]*a[i+1];
        }
    }
    cout<<ans<<el;
}

D

先求所有无序对的总和 $sum$ ,以及奇偶性不同的无序对对数 $cnt$ (通过奇数个数乘偶数个数求得)
因为 $a_i +a_j$ 为奇数即二者奇偶性不同时除以 $2$ 会损失 $0.5$
所以答案就为 $(sum-cnt)/2$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    int n;
    cin >>n;
    vector<int> a(n+1);
    int sum=0;
    int cnt=0;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        sum+=a[i];
        if (a[i]%2==0) cnt++;
    }
    sum=(n-1)*sum;
    int ans=(sum-cnt*(n-cnt))/2;
    cout<<ans<<el;
}

E

BFS模拟过程即可,注意用 $set$ 存走过的数避免重复陷入循环
同时加入位数剪枝

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
void solve() {
    int a,b,k;
    cin>>a>>b>>k;
    auto bzd=[&](int x)-> int{
        int bbb=0;
        if (x==0) return 1;
        while (x) {
            x/=10;
            bbb++;
        }
        return bbb;
    };
    int count=bzd(b);
    queue<int> q;
    unordered_map<int,int> mp;
    q.push(a);
    mp[a]=0;
    unordered_set<int> vis;
    vis.insert(a);
    while(!q.empty()) {
        auto p=q.front();
        q.pop();
        if (p==b) {
            cout<<mp[p]<<el;
            return;
        }
        int t=p+k;
        if (vis.find(t)==vis.end() && bzd(t)<=count) {
            vis.insert(t);
            q.push(t);
            mp[t]=mp[p]+1;
        }
        if (p%10!=0) {
            int x=0;
            int temp=p;
            while (temp) {
                x=x*10+temp%10;
                temp/=10;
            }
            if (bzd(x)<=count && vis.find(x)==vis.end()) {
                q.push(x);
                mp[x]=mp[p]+1;
                vis.insert(x);
            }
        }
    }
    cout <<-1<<el;
}

F

通过改一段区间来最小化邻居距离,不难想到对每一个位置倒置时产生的变化值求前缀和,然后求得区间变化量的最小值(可能是正,也可能是负)
若是正数可以选择不进行倒置操作,负数则可以更新答案
对于变化值怎么求:
如果当前位是 $1$ (即$a_i='1'$) 变化值为 $cnt1[i]-cnt0[i]-1$
如果当前位是 $0$ 变化值为 $cnt0[i]-cnt1[i]-1$

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
void solve() {
    int n,m;
    cin >> n >> m;
    vector<int> cnt1(m+1);
    vector<int> cnt0(m+1);
    vector<string> a(n+1);
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        s=" "+s;
        for (int j = 1; j <= m; j++) {
            if (s[j]=='1') cnt1[j]++;
            else cnt0[j]++;
        }
        a[i]=s;
    }
    for (int i = 1; i <= n; i++) {
        vector<int> d(m+1);
        int ans=0;
        for (int j = 1; j <= m; j++) {
            if (a[i][j]=='1') {
                d[j]=cnt1[j]-cnt0[j]-1;
                ans+=cnt0[j];
            }
            else {
                d[j]=cnt0[j]-cnt1[j]-1;
                ans+=cnt1[j];
            }
        }
        vector<int> pre(m+1);
        for (int j = 1; j <= m; j++) pre[j]=pre[j-1]+d[j];
        int res=LLONG_MAX;
        int mx=0;
        for (int j = 1; j <= m; j++) {
            int x=pre[j];
            int cur=x-mx;
            res=min(res,cur);
            mx=max(mx,x);
        }
        ans=min(ans,res+ans);
        cout<<ans<<el;
    }
}

说些什么吧！

waline