Codeforces Round 928 (Div. 4) | vegeone

vegeone
0%

Codeforces Round 928 (Div. 4)

发表于 更新于 分类于 Valine：

开始回归算法了，先来波div 4练练手

Vlad and the Best of Five

题意

给定一个字符串，求A和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
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
void solve()
{
    string str;
    int cnt1=0,cnt2=0;
    cin>>str;
    for(auto ch:str){
        if(ch=='A')cnt1++;
        else cnt2++;
    }
    cout<<(cnt1>=cnt2?'A':'B')<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)	solve();
    return 0;
}

Vlad and Shapes

题意

给定一个01二维数组，求1组成的是三角形还是正方形，三角形只有正三角和倒三角，没有旋转30度的

分析

输出都说了答案只有三角和正方形，碰到第一个1看看它下面和右边是否一样即可

代码

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
void solve()
{
    int n;
    cin>>n;
    vector<vector<char> > vec(n+1,vector<char>(n+1));
    for(int i=1;i<=n;++i){
        string str;
        cin>>str;
        for(int j=1;j<=n;++j){
            vec[i][j]=str[j-1];
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(vec[i][j]=='1'){
                if(vec[i][j+1]==vec[i+1][j]){
                    cout<<"SQUARE"<<endl;
                    return;
                }else {
                    cout<<"TRIANGLE"<<endl;
                    return;
                }
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)	solve();
    return 0;
}

Vlad and a Sum of Sum of Digits

题意

求1-n的各数的数位和的和

分析

预处理一下即可，求第n个数的答案的前缀和，每次增加需要花费,总时间复杂度nlogn，2e5可以接受

代码

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>
#define int long long
using namespace std;
#define endl '\n'
const int N=2e5+10;
typedef pair<int,int>pp;
int pre[N];
void solve()
{
    int n;
    cin>>n;
    cout<<pre[n]<<endl;
}
void init(){
    for(int i=1;i<N;++i){
        pre[i]=pre[i-1];
        int t=i;
        while(t){
            pre[i]+=t%10;
            t/=10;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    init();
    while(T--)	solve();
    return 0;
}

Vlad and Division

题意

对一堆数进行分组，每组内每个数的二进制各31个数位都不能相同，求最少分几组

分析

一组最多两个数，看看有没有对应的异或值即可

代码

当时看错成,结果一直爆边界

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
#include<bits/stdc++.h>
// #define int long long
using namespace std;
#define endl '\n'
typedef unsigned long long ll;
const int N=1e5+10;
// const ll tt=(1<<32)-1;
typedef pair<int,int>pp;
void solve()
{
    int n;
    cin>>n;
    vector<ll>a(n+1);
    map<ll,int>mp;
    for(int i=1;i<=n;++i)cin>>a[i],mp[a[i]]++;
    // ll tt=1;
    // for(int i=1;i<=31;++i){
    //     tt*=2;
    // }
    // tt--;
    ll tt=(1<<31)-1;
    // cerr<<tt<<endl;
    int ans=0;
    for(auto t:mp){
        ll x=t.first;
        ans+=t.second;
        if(mp[tt^x]){
            mp[tt^x]-=min(mp[tt^x],mp[x]);
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)	solve();
    return 0;
}

Vlad and Avoiding X

题意

给定一个7*7矩阵，你可以进行一项操作选择一个格子使它变为白色，问使矩阵不存在某个黑格子且这个黑格子的四个对角都是黑格子的情况的最少操作次数

分析

手推可以发现最多次数不会超过8次，有人剪枝优化过了，这种卡常的感觉有点玄学。

从最暴力的角度可以发现只要对每个格子都考虑一边变白或不变就行了，这个时候复杂度为，显然会爆，然后可以发现相邻的格子两两之间互不影响

如图中，红色所影响的区域和蓝色所影响的区域并没有交集，所以可以对两者进行分开讨论，此时的复杂度就降到了,然后还可以发现对于最外的一圈，他们变白显然可以等效或不如内部的某个点变白，去掉外面一圈后，时间复杂度直接降到,至此就过了

代码

dot写错了结果wa了一发

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
int ans=8;
int dot[2][13][2]={{{2,2},{2,4},{2,6},{3,3},{3,5},{4,2},{4,4},{4,6},{5,3},{5,5},{6,2},{6,4},{6,6}},{{2,3},{2,5},{3,2},{3,4},{3,6},{4,3},{4,5},{5,2},{5,4},{5,6},{6,3},{6,5}}};
bool check(vector<vector<char> >&temp,int flag){
    for(int k=0;k<13;++k){
        int i=dot[flag][k][0],j=dot[flag][k][1];
        if(temp[i][j]=='B'&&temp[i-1][j-1]=='B'&&temp[i-1][j+1]=='B'&&temp[i+1][j-1]=='B'&&temp[i+1][j+1]=='B')
                return false;
    }        
              
    return true;
}
void dfs(vector<int>&num,vector<vector<char> >&temp,int flag,int step){
    // for(int i=0;i<13;++i)cerr<<num[i]<<" \n"[i==12];
    
    if(check(temp,flag)){
        int cnt=0;
        for(int i=0;i<13;++i){
            if(num[i])++cnt;
        }
        // if(cnt<ans){
        //     cerr<<flag<<" "<<step<<endl;
        //     for(int i=0;i<13;++i)cerr<<num[i]<<" \n"[i==12];
        // }
        ans=min(ans,cnt);
        return;
    }
    if(step==13)return;
    char ch=temp[dot[flag][step][0]][dot[flag][step][1]];
    if(ch=='W'){
        dfs(num,temp,flag,step+1);
    }else {
        dfs(num,temp,flag,step+1);
        temp[dot[flag][step][0]][dot[flag][step][1]]='W';
        num[step]=1;
        dfs(num,temp,flag,step+1);
        num[step]=0;
        temp[dot[flag][step][0]][dot[flag][step][1]]=ch;
    }
    
}
void solve()
{
    ans=8;
    vector<vector<char> > vec(8,vector<char>(8));
    for(int i=1;i<=7;++i){
        string str;
        cin>>str;
        for(int j=1;j<=7;++j){
            vec[i][j]=str[j-1];
        }
    }
    vector<int>num(13,0);
    dfs(num,vec,0,0);
    int reans=ans;
    // cerr<<ans<<endl;
    ans=8;
    for(int i=0;i<13;++i)num[i]=0;
    dfs(num,vec,1,0);
    reans+=ans;
    cout<<reans<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)	solve();
    return 0;
}

Vlad and Trouble at MIT

题意

给定一棵树，树上每个点分别用C、S、P表示，S和P相连时需要在中间加一堵墙，求最少需要加多少堵墙

分析

树上dp,表示当前结点为i,表示的类型为j所需要加的最少墙数。

​ j=0表示C，j=1表示S，j=2表示P

代码

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
string str;
int n;
int e[N],ne[N],h[N],idx;
int f[N][3];
void add(int a,int b){
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}
void dfs(int u){
    f[u][1]=str[u]=='S'?1e18:0;
    f[u][2]=str[u]=='P'?1e18:0;   
    int f0=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int v=e[i];
        dfs(v);
        f[u][1]=f[u][1]+min({f[v][0],f[v][1],f[v][2]+1});
        f[u][2]=f[u][2]+min({f[v][0],f[v][1]+1,f[v][2]});
        f0+=f[v][0];
    }
    f[u][0]=min({(int)(str[u]=='C'?f0:1e18),f[u][1]+1,f[u][2]+1});
}
void solve()
{
    cin>>n;
    idx=0;
    for(int i=1;i<=n;++i){
        e[i]=ne[i]=0;
        h[i]=-1;
    }
    for(int i=2;i<=n;++i){
        int v;
        cin>>v;
        add(v,i);
    }
    cin>>str;
    str=" "+str;
    // cerr<<1<<endl;
    dfs(1);
    cout<<min({f[1][0],f[1][1],f[1][2]})<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)	solve();
    return 0;
}