8.20 test

· · 个人记录

T1

签到题，可以借助一个整数和一个整数减一互质的特性，算出最大的n/c和n/c-1，注意，当n/c-1<0时，即n<c时是不存在的 

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  freopen("T1.in","r",stdin);
//  freopen("T1.out","w",stdout);
    int c,n;
    cin>>c>>n;
    if(c>n) {
        cout<<-1;
        return 0;
    }
    int a=n/c,b=n/c-1;
    if(n/c-1==0) {
        b=n/c;
    }
    cout<<a*c*b*c;
    return 0;
}

T2

暴力挂挂挂死没了然后发现写了假解（）
我们可以构造一个样例：ABCBC转换第一次后变成了BCABC，第二次变成BCBCA，我们可以发现，A是重复利用的，所以我们只要考虑A对后面BC的贡献，遇到单独的BC直接清空

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    string s;
    cin>>s;
    int cnt=0,ans=0;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='A') {
            cnt++;
            continue;
        } else if(s[i]=='B'&&s[i+1]=='C'&&i+1<s.size()) {
            ans+=cnt;
            i++;
            continue;
        }
        else cnt=0; 
    }
    cout<<ans;
    return 0;
}
//BCBCA

T3

对于暴力我们可以发现b的范围是10-1e18之间，所以我们可以暴力枚举拿10pts（然后进制转换出锅了）
正解思路是分段二分，在1e6的范围内使用暴力，在1e6的范围外二分
设转换后的数是x，推一下可以知道，最多三位数，所以我们可以枚举x的每一种情况，然后二分看能不能得到原来的数

#include<bits/stdc++.h>
using namespace std;
#define int long long
int judge(int x, int k) { 
    int now=0, temp=1;
    while (x) {
        if (x % k >= 10) {          
            return -1;
        }
        now += temp * (x % k); 
        x /= k;
        temp *= 10; 
    }
    return now;
}
int check(int x,int k) {
    return x%10+(x/10%10)*k+(x/100)*k*k;
}
signed main() {
    int n,m,ans=10;
    cin>>n>>m;
    for (int i = m; i <= 999; i++) {
        int l = 1e6 - 1, r = (1e18 + 1);
        if (i >= 100) {
            r = 1e9 + 1;
        }
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (check(i, mid) >= n) {
                r = mid;
            } else {
                l = mid;
            }
        }
        if (check(i, r) == n) {
            ans = max(ans, r);
        }
    } 
    for(int i=1000000; i>=ans; i--) {
        if(judge(n,i)>=m) {
            ans=i;
            break;
        }
    }
    cout<<ans;
    return 0;
}