$AtCoder Beginner Contest 319$-526互联

$A - Legendary Players$

map<char ,int >mp;
void solve(){
    string s;
    cin>>s;
    cout<<mp[s[0]]<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}
signed main(){
    mp['t']=3858;
//ksun48 
    mp['k']=3679;
// Benq 
    mp['B']=3658;
// Um_nik 
    mp['U']=3648;
// apiad 
    mp['a']=3638;
// Stonefeang 
    mp['S']=3630;
// ecnerwala 
    mp['e']=3613;
// mnbvmar 
    mp['m']=3555;
// newbiedmy 
    mp['n']=3516;
// semiexp 
    mp['s']=3481;

    int t=1;
    while(t--){
        solve();
    }
}

$B - Measure$

理解了半天题意，然后就按照题目的意思暴力模拟，我现在也没懂他在干什么。

void solve(){
    int n=read();
    for(int i=0;i<=n;i++){
        if(i==0){
            cout<<1;
            continue;
        }
        int ans=10;
        for(int j=1;j<=9;j++){
            if(n%j==0&&i%(n/j)==0){
                ans=min(ans,j);
            }
        }
        if(ans==10)cout<<'-';
        else cout<<ans;
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

$C - False Hope$

$D - Minimum Width$

这题也是显然的二分答案，每次 $check$ 的时候 $O(n)$ 模拟。

int a[N],n,k;
bool check(int x) {
    int now=a[1],h=1;
    for(int i=2;i<=n;i++){
        if(now+a[i]+1<=x){
            now+=a[i]+1;
        }else{
            now=a[i];
            h++;
        }
    }
    return h<=k;
}
int bs1(int l, int r){ //左偏二分
    while (l < r){
        int mid = (l + r )>> 1;
        if (check(mid)) r = mid;    
        else l = mid + 1;
    }
    return l;
}
void solve(){
    n=read(),k=read();
    int sum=0,maxx=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        maxx=max(a[i],maxx);
        sum+=a[i];
    }
    cout<<bs1(maxx,sum*2)<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

$E - Bus Stops$

显然对于所有间隔的 $lcm$ ，余数相同的时候答案应该相同。看到间隔的范围很小，可以自然的想到预处理出 $lcm$ 内的所有答案，然后就可以 $O(1)$ 的回答询问。

int n,m,a[N],b[N];
int ans[N];
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
void yuchuli(){
    m=1;
    for(int i=1;i<=8;i++){
        m=m*i/gcd(m,i);
    }
    for(int i=0;i<=m;i++){
        int x=i;
        for(int j=1;j<n;j++){
            if(x%a[j])x+=a[j]-x%a[j];
            x+=b[j];
        }
        ans[i]=x;
    }
}
void solve(){
    n=read();
    int s=read(),t=read();
    for(int i=1;i<n;i++){
        a[i]=read();
        b[i]=read();
    }
    yuchuli();
    int q=read();
    while(q--){
        int x=read();
        x+=s;
        x+=ans[x%m]-x%m;
        x+=t;
        cout<<x<<'\n';
    }    
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}