A.BowWow and the Timetable

题目连接

题目大意

给你一个以二进制方式来表示数字\(n\)的字符串，问\(4^k < n\)数字的个数。

解题思路

题目给的数字是以二进制的方式给的，那么结合二进制数字的特点，可以发现每个\(4^k\)用二进制表示最前面的那个1都是在奇数位置，那么如果给的字符串长度是偶数，直接除以2；如果是奇数的话，加1除以2，并且判断最高位1是否满足条件。

AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    bool flag = false;
    int len = s.size();
    int res;
    if(len%2==0){
        res = len/2;
    }else{
        res = (len+1)/2;
        for(int i=1;i<len;i++){
            if(s[i]!='0'){
                flag = true;
            }
        }
        if(!flag)res--;
    }
    cout<<res<<endl;
    return 0;
}

B.Mislove Has Lost an Array

题目链接

题目大意

有大小为\(n\)的一个数组，这个数组中至少有\(l\)个不同的数，至多有\(r\)个不同的数,并且数组中如果有奇数的话，奇数只能是\(1\)，否则全是偶数，并且如果数组中有偶数\(a_i\)，那么数组中也必须有偶数\(a_i/2\)。求数组所有元素的最大和，最小和。

解题思路

所有元素的和最小，首先必须要满足至少有\(r\)个不同的元素,根据元素的要求，数组中的元素呈现\(1,2,4,8 \cdots,a[i-1]*2\)的规律，先算出\(r\)个不同元素的和，其余元素全部为\(1\)；所有元素的和最大，则先算出\(l\)个不同元素的和，其余元素全部为最大的那个元素。

AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,l,r;
    cin>>n>>l>>r;
    int minsum=1,maxsum=1;
    int cnt=1;
    for(int i=1;i<l;i++){
        cnt*=2;
        minsum+= cnt;
        maxsum+=cnt;
    }
    for(int i=l;i<n;i++){
        minsum+=1;
    }
    for(int i=l;i<r;i++){
        cnt*=2;
        maxsum+=cnt;
    }
    for(int i=r;i<n;i++){
        maxsum+=cnt;
    }
    cout<<minsum<<" "<<maxsum<<endl;
    return 0;
}

C.Anna,Svyatoslav and Maps

题目连接

题目大意

一个有向无自环图，给定一个序列\(p_1,p_2,p_3,\cdots,p_n\) , 删除序列\(p\)中除\(p_1,p_n\)外的某些点，得到序列\(v_1,v_2,\cdots,v_k\)，序列\(v\)必须满足通过这些点的最短路径是序列\(v\)，求出最短序列\(v\)。

解题思路

最开始做这道题的时候，切入点错了。应该考虑哪些点应该删除，删除的点必须要满足哪些条件。仔细思考之后发现,假设删除\(p_2\)这个点之后，经过这些点的最短路径依然能够得到原来的序列\(p\),那么说明\(p_2\)是\(p_1\)到\(p_3\)最短路径必须经过的点，即\(p_1\)到\(p_3\)必须要经过\(p_2\)，可以省略\(p_2\)的存在。反过来可以得到不是最短路径经过的点必须要存在，否则就存在另一条最短路径。

AC代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
const int maxn = 1e6+5;
const int maxm = 1e2+10;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int n,m;
int weight[maxm][maxm];
int p[maxn];
bool flag[maxn];
void init()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            if(c=='0'){
                weight[i][j]=INF;
            }else{
                weight[i][j]=1;
            }
        }
        //注意初始化自环
        weight[i][i]=0;
    }
    cin>>m;
    for(int i=1;i<=m;i++)cin>>p[i];
}
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                weight[i][j]=min(weight[i][j],weight[i][k]+weight[k][j]);
            }
        }
    }
}
void solve(){
    int t=m;
    int cnt=p[1];
    for(int i = 2 ; i <= m - 1 ; i++) {
        if(weight[cnt][p[i]]+weight[p[i]][p[i + 1]] <= weight[cnt][p[i + 1]]) {
            flag[i] = 1;
            t--;
        }
        else cnt = p[i];
    }
    cout<<t<<endl;
    for(int i = 1 ; i <= m ; i++) {
        if(flag[i])continue;
        cout << p[i] << " ";
    }
}
int main()
{
    ios::sync_with_stdio(false);
    init();
    floyd();
    solve();
    return 0;
}

D1. Kirk and a Binary String (easy version)

题目连接

题目大意

往下滑，看D2

解题思路

往下滑，看D2

AC代码

往下滑，看D2

D2. Kirk and a Binary String (hard version)

题目连接

题目大意

给你一个只包含\(0,1\)字符的字符串\(s\)，找到另一个字符串\(t\)，要求字符串\(t\)和\(s\)的长度一样，并且任意子区间的最长非递减子序列的长度一样，并且字符\(0\)的个数尽可能的多。

解题思路

先让\(t=s\)，肯定满足任意子区间的最长非递减子序列的长度一样,但不满足\(0\)的个数最多，所以可以将字符串\(t\)中的不影响子序列长度的\(1\)转为\(0\)。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int cnt=0;
    string s;
    cin>>s;
    for(int i=s.size()-1;i>=0;i--)
        if(s[i]=='0')cnt++;
        else if(cnt)cnt--;
        else s[i]='0';
    cout<<s<<endl;
}