cf #833 Div.2(A-D)

Cf #833 Div.2

A. The Ultimate Square

• 题意

  • 给定一个数字n，总共有n块木板，木板高度都为1，木板长度为ceil(i/2) 1<=i<=n
  • 用其中一些木板组成一个正方形，问最大的正方形边长为多少

• 题解

  • 贪心。结论：可以组成的正方形的边长最大为ceil(n/2)
  • 证明：假设n为奇数，那么最长的木板只有一块，其长度为m=ceil(n/2)。那么枚举即可发现其余的木板可以全部用上组成一个m*m的正方形。如果n为偶数，那么发现有2块m的木板，所以和奇数时同理，只不过可以不用其中一块长度为m的木板。

• 代码

#include 
#include 

using namespace std;

//ceil(n/k)==(n+k-1)/k
//floor(n/k)==n/k;

void solve() {
    int n; cin>>n;
    cout<<int(ceil(n/2.0))<<'\n';
}

int main() {
    int t; cin>>t;
    while(t--) solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

B. Diverse Substrings

• 题意

  • 若一个数字串中，所有数字出现的次数都不超过串中数字的种类数，那么称这个串为diverse
  • 给定一个数字字符串，问有多少个子串是diverse

• 题解

  • 贪心+暴力。可以知道任何一个数字串的种类数最多只有10种，所以最长的diverse为100个字符。所以直接遍历每一个字符，以其为开头循环100次看有多少个是diverse即可。时间复杂度为O(100*n)

• 代码

#include 
#include 
#include 

using namespace std;

map<char,int> h;
int n;

void solve() {
    cin>>n;
    string s; cin>>s;
  
    int res=0;
    for(int i=0;i<n;i++) {
        h.clear();
        bool f=1;
        int kinds=0,ma=0,ans=0;
        for(int j=i;f && j<n & j<=i+100;j++) {
            if(h[s[j]]==0) kinds++;
            h[s[j]]++;
            ma=max(ma,h[s[j]]);
            if(ma<=kinds) ans++;
        }
        res+=ans;
    }
    cout<<res<<'\n';
}

int main() {
    int t; cin>>t;
    while(t--) solve();
    
    return 0;
}
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

C. Swap Game

• 题意

  • 给定数组an，其前缀和为Sn。可以将ai=0的元素改变为任意的数，问经过若干此操作，最多可以使多少个S[i]=0。

• 题解

  • 思维+贪心。如果数组a中没有0，那么答案为Si==0的数量
  • 由前缀和知识可得，在ai=0，aj=0的位置改变元素大小，相当于把Si,Si+1,…,Sj-1这一段的大小改变了。
  • 那么可以用ai=0把S分为相对变化相同的几段，第一段如上所述，无法更改S的大小，这一段答案为Si=0的数量；其他段可以通过改变ai=0来把S的大小变为0，所以贪心来看，把出现次数最多的S变为0即可，这一段答案为出现最多的数量，这里只需要知道数量而不需要知道后续的变化，所以数组如何变换不用管。

• 代码

正着遍历(添加一个虚空的n+1边界，使得S数组被不重不漏的分为若干段，同时避免恶心讨论)

#include 
#include 

using namespace std;
const int N=2e5+10;
typedef long long ll;

int n,a[N],pos[N];
ll s[N];

void solve() {
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++) {
        cin>>a[i],s[i]=s[i-1]+a[i];
        if(a[i]==0) pos[cnt++]=i;
    }
    pos[cnt++]=n+1;
    
    ll res=0;
    for(int i=0;i<cnt;i++) {
        ll ans=0;
        if(i==0) {
            for(int j=1;j<pos[0];j++) if(s[j]==0) ans++;
        }
        else {
            int j=pos[i-1],k=pos[i];
            map<ll,ll> h; 
            ll ma=0;
            for(int x=j;x<k;x++) {
                h[s[x]]++;
                if(h[s[x]]>ma) ma=h[s[x]];
            }
            ans=ma;
        }
        res+=ans;
    }
    
    cout<<res<<'\n';
}

int main() {
    int t; cin>>t;
    while(t--) solve();
    
    return 0;
}
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

逆着遍历(与上述添加n+1同理，但是这里更加的简单，只需统计碰到0时那一段的S最多次数，而第一段没有0，所以不会按这个方法统计，避免讨论，只要最后加上Si=0的数量)。注意#define long long int 会re

#include 
#include 

using namespace std;
const int N=2e5+10;
typedef long long ll;

int n,a[N];
ll s[N];

void solve() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
    
    ll res=0;
    map<ll,ll> h;
    for(int i=n;i>=1;i--) {
        h[s[i]]++;
        if(a[i]==0) {
            ll ma=0;
            for(auto x:h) if(x.second>ma) ma=x.second;
            res+=ma;
            h.clear();
        }
    }
    cout<<res+h[0]<<'\n';
}

int main() {
    int t; cin>>t;
    while(t--) solve();
    
    return 0;
}
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

D. Yet Another Problem

• 题意

  • 给定三个数a,b,d (1< a,b,d <2 ^30)。找到一个x(1< x <2的60方)，使得(a or x)以及(b or x)整除d

• 题解

  • 构造+位运算逻辑。首先讨论无解的情况：当a或者b(即a or b)为奇数时，(a or x)以及(b or x)一定为奇数，若此时的d为偶数，无论如何都不能整除d，所以无解。不失一般性的，(a or b)的最低位的1位置低于d的最第一位1时，无解
  • 除去上述的情况，一定可以构造出一个x符合要求。构造方法：先把(a or b)和d的低位0都去掉，那么如果有解，得到的d最低位一定为1。初始化x=0，一位一位构造。
    • 对于某一位i，若(a or b)i==1，xi=0，把xi通过移动(d<
    • 若(a or b)i=0，xi=0，此时xi对于x的数值贡献是0，也是d的倍数。所以(a or x)以及(b or x)一定是d的倍数，所以这一位本身是符合要求的。(a or b)i==1，xi=1同理。
  • 注意，x的范围会溢出long long ，所以要么用int64_t，要么用long long取模2^60

• 代码

直接用int64_t

#include 

using namespace std;

void solve() {
    int64_t a,b,d; cin>>a>>b>>d;
    a|=b;
    
    int cntz=0;
    while(d%2==0) {
        if(a%2) { cout<<-1<<'\n'; return ;}
        d/=2; a/=2;
        cntz++;
    }
    
    int64_t x=0;
    for(int i=0;i<30;i++) {
        if((x>>i & 1)==0 && (a>>i & 1)==1) x+=d<<i;
    }
    cout<<(x<<cntz)<<'\n';
}

int main() {
    int t; cin>>t;
    while(t--) solve();
    
    return 0;
}
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

用long long 取模来构造一个范围符合要求的答案

#include 

using namespace std;
const long long mod=11529215e11;//2^60的值

void solve() {
    long long a,b,d; cin>>a>>b>>d;
    a|=b;
    
    int cntz=0;
    while(d%2==0) {
        if(a%2) { cout<<-1<<'\n'; return ;}
        d/=2; a/=2;
        cntz++;
    }
    
    long long x=0;
    for(int i=0;i<30;i++) {
        if((x>>i & 1)==0 && (a>>i & 1)==1) x=(x+(d<<i)+mod)%mod;
    }
    cout<<(x<<cntz)<<'\n';
}

int main() {
    int t; cin>>t;
    while(t--) solve();
    
    return 0;
}
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