Educational Codeforces Round 116 (Rated for Div. 2)

差亿点过三题

A题，考虑将相同的字母压缩，要也即要压缩后的字符数为奇数，考虑修改则需要修改开头或者结尾。

这时考虑到修改一位便可，于是只需

s[0]=s.back();

B题,先求出k在二进制下最高位1的位置，然后按等比数列求和求出如果就模拟，否则就除k算。

不开long long见祖宗。

C题,考虑到，先预处理出十的幂与各幂次之间允许的次数

---

A:

LL t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    f(sb,1,t){
        string s;
        cin>>s;
        vector<pii> v;
        char last=s[0];
        int cnt=0;
        for(auto it:s){
            if(it!=last){
                v.pb(mp(last,cnt));
                last=it;
                cnt=1;
            }
            else cnt+=1;
        }
        v.pb(mp(last,cnt));
        if(v.size()&1)
        cout<<s<<"\n";
        else {
            if(s[0]=='a') s[0]='b';
            else s[0]='a';
            cout<<s<<"\n";
        }
    }
    return 0;
}

B:

LL quikpower(int b)
{
    LL ans = 1, base = 2;
    while (b > 0)
    {
        if (b & 1)
        {
            ans *= base;
        }
        base *= base;
        b >>= 1;
    }
    return ans;
}
 
LL t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    f(ab, 1, t)
    {
        LL n, k, bas = 1, cnt = 0;
        cin >> n >> k;
        n -= 1;
        LL sb = k;
        while (sb > 0)
        {
            sb>>=1;
            cnt += 1;
        }
        LL ma=quikpower(cnt)-1;
        if (n <ma)
        {
            cnt=0;
            while (n > 0)
            {
                cnt += 1;
                n -= bas;
                bas *= 2;
            }
        }
        else if(n>ma)
        {
            n-=ma;
            cnt+=(n/k+(n%k?1:0));
        }
        cout << cnt << "\n";
    }
    return 0;
}

C:

LL t,n,k;
LL a[11]={1};
LL b[11]={0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    f(i,1,9){
        a[i]=a[i-1]*10;
        b[i]=b[i-1]*10+9;
    }
    cin>>t;
    f(sb,1,t){
        cin>>n>>k;
        k+=1;
        vi v;
        LL ans=0;
        f(i,1,n){
            LL temp;
            cin>>temp;
            v.pb(temp);
        }
        auto it=v.begin();
        it++;
        while(it!=v.end()&&k>0){
            LL mid=min(k,b[(*it)-(*(it-1))]);
            ans+=mid*a[(*(it-1))];
            //cout<<b[(*it)-(*(it-1))]<<"::::"<<(*it)-(*(it-1))<<"hw\n";
            k-=mid;
            it++;
        }
        if(k>0){
            ans+=k*a[(*(it-1))];
        }
        cout<<ans<<"\n";
    }
    return 0;
}