The 2018 ACM-ICPC Asia Qingdao Regional Contest

The 2018 ACM-ICPC Asia Qingdao Regional Contest

C - Flippy Sequence

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int maxn = 2e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
ll T,N;
char a[maxn],b[maxn];
ll solve(){
    vector<pii> LR;
    LR.clear();
    ll l = -1,r = -1;
    for(int i = 1;i<=N;i++){
        if(a[i] != b[i]){
            if(l == -1) l = i,r = i;
            else r = i;
        }else{
            if(l != -1 && r != -1){
                LR.pb({l,r});
                l = -1,r = -1;
                if(LR.size()>=3) return 0;
            }
        }
    }
    if(l != -1 && r != -1) LR.pb({l,r});
    if(LR.size()>=3) return 0;
    else if(LR.size()==0) return N*(N+1)/2;
    else if(LR.size()==1){
        ll l = LR[0].fs,r = LR[0].sc;
        ll ans = (r-l)*2;
        ans += (l-1)*2 + (N-r)*2;
        return ans;
    }else{
        return 6LL;
    }
}   
int main(){
    // debug;

    read(T);
    while(T--){
        read(N);
        scanf("%s",a+1);
        scanf("%s",b+1);
        ll ans = solve();
        printf("%lld\n",ans);
    }

    return 0;
}

D - Magic Multiplication

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
int T,N,M;
char c[2*maxn];int len;
int a[maxn],b[maxn];
bool judge(int s){
    for(int i = 1;i<=N;i++) a[i] = 0;
    for(int i = 1;i<=M;i++) b[i] = 0;
    a[1] = s;
    int idxa = 1,idxb = 1,pos = 1;
    for(int j = 1;j<=M;j++){
        if(a[1] <= c[pos]-'0' || c[pos] == '0'){
            if(pos>len) return false;
            int cur = c[pos] - '0';
            if(cur%a[1]) return false;
            b[j] = cur/a[1];
            pos++;
        }else{
            if(pos>len-1) return false;
            int cur = 10*(c[pos] - '0') + c[pos+1]-'0';
            if(cur%a[1]) return false;
            b[j] = cur/a[1];
            pos+=2;
        }
    }
    // for(int j= 1;j<=M;j++) printf("%d",b[j]);printf("\n");
    while(1){
        if(pos>len) break;
        int cur_ans = -1;
        for(int j = 1;j<=M;j++){
            if(pos>len || idxa >=N) return false;
            int cur = c[pos]-'0';
            if(cur>=b[j] || cur == 0){
                if(cur>0 && b[j] == 0) return false;
                else if(cur == 0 && b[j] == 0){
                    ;
                }else{
                    if(cur%b[j]) return false;
                    if(cur_ans == -1) cur_ans = cur/b[j];
                    else if(cur_ans == cur/b[j]) ;
                    else return false;
                }
                pos += 1;
            }else{
                if(pos>len-1) return false;
                cur = cur*10 + c[pos+1]-'0';
                if(cur%b[j]) return false;
                if(cur_ans == -1) cur_ans = cur/b[j];
                else if(cur_ans == cur/b[j]) ;
                else return  false;
                pos += 2;
            }
        }
        a[++idxa] = cur_ans;
        if(idxa > N) return false;
    }
    if(idxa != N) return false;
    return true;
}
void solve(){
    int ok = 0;
    for(int i = 1;i<=9;i++){
        if(judge(i)){
            ok = 1;
            break;
        }
    }
    if(!ok) puts("Impossible");
    else{
        for(int i = 1;i<=N;i++){
            if(a[i] == -1) printf("0");
            else printf("%d",a[i]);
        }
        printf(" ");
        for(int i = 1;i<=M;i++) printf("%d",b[i]);printf("\n");
    }
}   
int main(){
    // debug;
    read(T);
    while(T--){
        read(N,M);
        scanf("%s",c+1);len = strlen(c+1);
        solve();
    }

    return 0;
}

E - Plants vs. Zombies

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
ll T,N,M;
ll a[maxn];
ll d[maxn];
bool judge(ll mid){
    for(int i = 1;i<=N;i++) d[i] = 0;
    ll t = M,pos = 0;
    while(1){
        if(pos >N) break;
        if(t<=0) break;
        if(pos == 0 && t>0) {
            pos++;
            d[pos] += a[pos];
            t--;
        }else{
            if(d[pos] < mid){
                ll tim = (mid - d[pos] + a[pos] - 1)/a[pos];
                if(2*tim > t) return false;
                d[pos] += a[pos] * tim;
                d[pos+1] += a[pos+1] * tim;
                t -= 2*tim;
            }
            if(t>0 && pos<=N){
                pos++;
                d[pos] += a[pos];
                t--;
            }
        }

    }
    for(int i = 1;i<=N;i++) if(d[i] < mid) return false;
    return true;
}
void solve(){
    ll l = 0,r = 1e18+100,ans;
    while(l<=r){
        ll mid = (l+r)>>1;
        if(judge(mid)) l = mid+1,ans = mid;
        else r = mid-1; 
    }
    printf("%lld\n",ans);
}   
int main(){
    // debug;
    read(T);
    while(T--){
        read(N,M);
        for(int i = 1;i<=N;i++) read(a[i]);
        solve();
    }

    return 0;
}

J - Books

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
int T,N,M;
int a[maxn];
void solve(){
    int t1 = M,t2 = 0;
    for(int i = 1;i<=N;i++) if(a[i] <= 0) t2++;
    if(t2>t1) puts("Impossible");
    else if(t1 == 0){
        int mi = 1e9+10;
        for(int i = 1;i<=N;i++) mi = min(mi,a[i]);
        printf("%d\n",mi-1);
    }else{
        if(t1 == N) puts("Richman");
        else{
            t1 -= t2;
            ll ans = 0,ok = 1;
            for(int i =1;i<=N;i++){
                if(t1>0){
                    if(a[i] != 0) {
                        ans += a[i];
                        t1--;
                    }
                }else{
                    int mi = 1e9+10;
                    for(int j = i;j<=N;j++){
                        if(a[j] != 0) mi = min(mi,a[j]);
                    }
                    ans += mi-1;
                    break;
                }
            }
            printf("%lld\n",ans);
        }
    }
}   
int main(){
    // debug;

    read(T);
    while(T--){
        read(N,M);
        for(int i = 1;i<=N;i++) read(a[i]);
        solve();
    }

    return 0;
}

M - Function and Function

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
int T,x,k;
int a[100];
void init(){
    a[1] = a[2] = a[3] = a[5] = a[7] = 0;
    a[0] = a[4] = a[6] = a[9] = 1;
    a[8] = 2;
}
int solve(){
    int ans = x;
    for(int i = 1;i<=k;i++){
        int tmp = ans;
        int tmp2 = 0;
        if(tmp == 0){
            int left = k-i+1;
            if(left%2) return 1;
            else return 0;
        }else{
            while(tmp){
                tmp2 += a[tmp%10];
                tmp/=10;
            }
        }
        if(tmp2 == ans) break;
        ans = tmp2;
    }
    return ans;
}   
int main(){
    // debug;

    init();
    read(T);
    while(T--){
        read(x,k);
        int ans = solve();
        printf("%d\n",ans);
    }

    return 0;
}
Ryuichi的算法分享 文章被收录于专栏

分享我的一些算法题解，致力于把题解做好，部分题解可能会采用视频的形式来讲解。

全部评论

相关推荐

头像
11-17 09:06
已编辑
山东大学 嵌入式软件工程师
如何委婉地拒绝offer
刷到这篇说明啥，说明你已经拿到一大把offer并准备挨个拒绝了想起来学校开三方的时候，导员强调过一句话：签三方一定要谨慎，就算回头要拒绝offer、要违约，也一定得委婉一点跟人家讲，别说啥自己找到更好的了，这不就相当于骂人家不好嘛，换位思考一下有人说你不好，你还能爽快地给人家办解约手续嘛。我拍的评价是：在理。1.&nbsp;已拿到offer，公司准备签三方但你不想去您好，非常抱歉，经过慎重考虑，并结合个人规划和贵公司岗位的具体情况，我决定放弃这次机会。对于未能及时告知，深感抱歉。非常感谢贵公司在面试和沟通过程中给予的时间和支持，也非常感谢您对我的认可。对因此给您造成的不便，再次致歉。...
无奈秋招秋招无奈：我认真看完了，但是用处不大，我就一家😂😂😂，不用拒
点赞 评论 收藏
分享
11-17 02:29
武汉理工大学 销售计划与分析
点赞 评论 收藏
分享
09-29 12:39
黑龙江科技大学 Java
大家避雷
垃圾公司，大家避雷，没见过上来就骂人的
去B座二楼砸水泥地：不过也可以理解，这种应该没参加过秋招
点赞 评论 收藏
分享
11-16 22:03
长春理工大学 网页产品经理
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
245910次浏览 2003人参与
# 学历or实习经历，哪个更重要 #
40944次浏览 298人参与
# 北方华创开奖 #
22701次浏览 257人参与
# 地方国企笔面经互助 #
2509次浏览 6人参与
# 你最想要的公司福利是？ #
39773次浏览 124人参与
# 选完offer后，你后悔学本专业吗 #
10188次浏览 75人参与
# 面试题刺客退退退 #
136943次浏览 2091人参与
# 国企/银行/研究所公司爆料 #
89635次浏览 411人参与
# 应届生被毁约被毁意向了怎么办 #
26972次浏览 238人参与
# 一觉醒来，我觉醒了超级打工人系统 #
2838次浏览 35人参与
# 机械应届生薪资要多少才合适？ #
12366次浏览 60人参与
# 查收我的offer竞争力报告 #
16582次浏览 227人参与
# 校招入职后的感受 #
156845次浏览 1959人参与
# 你觉得第一学历对求职有影响吗？ #
14859次浏览 121人参与
# 没有实习经历，还有机会进大厂吗 #
804863次浏览 13813人参与
# 我的工作日记 #
21123次浏览 270人参与
# 不给转正的实习，你还去吗 #
1516537次浏览 16964人参与
# 寒假躺平还是提前实习 #
58340次浏览 438人参与
# 总结:哪家公司面试体验感最差 #
25629次浏览 129人参与
# 秋招OC许愿 #
226357次浏览 1869人参与
# 如何写一份好简历 #
601704次浏览 8429人参与
牛客网
牛客企业服务