nocriz的博客

苔花如米小，也学牡丹开。

AGC037做题记

什么时候应该看题解？

当你觉得你“不可能”做出一个题的时候。

三个顶俩采访（另选手说“不能钻牛角尖”）

这是一场还算成功的训练……让我在若干天颓废中感受到比较充实……

A、B、C、D、E、F都是自己想的（F算一半吧）做法，但是不是很想费时间写很长在博客上（对不起），写了一点吐槽提示……我有时间再去看看F AC的短代码是怎么搞的吧……

希望自己未来能够有计划地做更多有意义的题。希望以后每天能做更多作业题或者其他好题。

  • A:猜想只有长度为1、2的划分有用，没证明，题解说随便证明短于5的有用，但是真的有人会这么思考？
  • B:写了一个很直觉但是感觉有点对的算法，也没证明居然过了？
  • C:显然每次需要操作最大的那个，操作尽可能多次。堆维护一下即可。
  • D:转化为一个二分图匹配问题，暴力匹配复杂度看上去有点高但是30ms。
  • E:感觉就是个Div2 C题，这种题还能放在AGC E?
  • F:这道题有点nb，题解写的很好，但是思路还需要自己领悟一下……我写的也够长，好像有的选手又短又快，我太菜了……

这场训练告诉我：对于一道题目，应该从多种角度去想（F）……要相信题目是简单的，你是能做出来的，至少不是不可能做出来的不是吗？对于AGC，似乎永远都是这样的，只要自己想的出，就能AC。因为Atcoder里面好像没有啥莫名其妙的高深算法和费劲的实现。如果随便看了题解，再补题，就变成搬砖了，而且也不会有补题的兴趣了，毕竟就变成告诉你怎么干你去写一个很长的代码……听上去也很无趣，但是如果是自己想出来的就会很感兴趣去写，因为你想看到自己的算法是对的，自己独立AC了一道似乎有点难度的题，还很好。

希望以后能够和高水平选手多交流学习……找个大腿抱一下……

希望明天开始的五场ICPC比赛不要垫底，成绩最好能比选拔赛好一些，再好一些……希望我能够在不看题解的情况下做出、补出更多的题目。

算法题像弹簧，你弱它就强！一道难度为1.5的题目，如果你思考五分钟能够思考1.2，然后你说：我知道至少这个题难度比1.2高，我的水平是1.2，不做了看题解，那就爬了。如果你换种方法想，这个题难度小于2，看上去又不是啥尚且不会的算法，自己不是不可能做出，以这种思路再想20分钟，或许总的思考量就足以解决这个1.5的题目了……

睡觉了。还是写了一些莫名其妙的文字……

A

char s[200020];
int main() {
    cin>>(s+1);
    int cp = 1,la = 2,ans = 0,n = strlen(s+1);
    while(cp<=n){
        if(la == 2 || s[cp]!=s[cp-1]){
            la = 1;
            cp+=1;
            ans+=1;
        }else{
            la = 2;
            cp+=2;
            if(cp<=n+1)ans+=1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

B

int n;
char S[300030];
int main() {
    cin>>n>>S;
    int cnt[8] = {0},ans = 1;
    for(int i=1;i<=n;i++) ans = mul(ans,i);
    for(int i=0;i<3*n;i++){
        int cv = S[i] == 'R'?0:(S[i] == 'G'?1:2),cs = 1<<cv;
        if(cnt[7-cs]){
            ans = mul(ans,cnt[7-cs]);
            cnt[7-cs]--;
        }else{
            if(((cs!=1 && cnt[1]) || (cs!=2 && cnt[2]) || (cs!=4 && cnt[4]))){
                for(int i=1;i<=8;i*=2)
                if(cs!=i && cnt[i]){
                    ans = mul(ans,cnt[i]);
                    cnt[i|cs] = add(cnt[i|cs],1);
                    cnt[i]-=1;
                }
            }else{
                cnt[cs]+=1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

C


int n,A[200020],B[200020];
void exi(){
    cout<<-1<<endl;
    exit(0);
}
signed main() {
    read(n);
    for(int i=1;i<=n;i++){
        read(A[i]);
    }
    int ans = 0;
    priority_queue<pii> Q;
    for(int i=1;i<=n;i++){
        read(B[i]);
        Q.push(MP(B[i],i));
    }
    B[0] = B[n];B[n+1] = B[1];
    while(!Q.empty()){
        pii C = Q.top();Q.pop();
        if(C.first == A[C.second])continue;
        int lr = B[C.second-1]+B[C.second+1];
        int req = (C.first-A[C.second])/lr;
        ans+=req;
        if(!req)exi();
        C.first-=req*lr;
        B[C.second] = C.first;
        B[0] = B[n];B[n+1] = B[1];
        Q.push(C);
    }
    cout<<ans<<endl;
    return 0;
}

D

int n,m,A[110][110],B[110][110];
vector<int> cnt[110][110];
vector<int> G[110];
int vis[110] = {0},btoa[110] = {0},btob[110];
bool dfs(int num){
    if(vis[num])return false;vis[num] = 1;
    for(auto ct:G[num]){
        if(btoa[ct] == 0 || dfs(btoa[ct])){
            btoa[ct] = num;
            btob[num] = ct;
            return true;
        }
    }
    return false;
}
int main() {
    read(n,m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            read(A[i][j]);
            cnt[i][(A[i][j]-1)/m+1].PB(A[i][j]);
        }
    }
    for(int i=1;i<=m;i++){
        for(int a=1;a<=n;a++){
            G[a].clear();
            for(int b=1;b<=n;b++){
                if(cnt[b][a].size()){
                    G[a].PB(b);
                }
            }
        }
        set0(btoa);
        for(int j=1;j<=n;j++){
            set0(vis);
            assert(dfs(j));
        }
        for(int j=1;j<=n;j++){
            B[btob[j]][i] = cnt[btob[j]][j].back();
            cnt[btob[j]][j].pop_back();
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cout<<B[i][j]<<" \n"[j == m];
    }
    for(int k=1;k<=m;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n-1;j++)if(B[j][k]>B[j+1][k])swap(B[j][k],B[j+1][k]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cout<<B[i][j]<<" \n"[j == m];
    }
    return 0;
}

E

int n,k;
int main() {
    string S;
    cin>>n>>k>>S;
    string T = S;
    reverse(all(T));
    string U = S+T;
    vector<string> V;
    for(int i=0;i<=n;i++){
        V.PB(U.substr(i,n));
    }
    sort(all(V));
    string C = V[0];
    if(k == 1){
        cout<<C<<endl;
        return 0;
    }
    if(k>13){
        for(int i=0;i<n;i++)cout<<C[0];
        cout<<endl;
    }else{
        int cc = 0;
        while(C[cc] == C[0])cc++;
        int cl = cc<<(k-1);
        for(int i=0;i<n;i++){
            if(i<cl)cout<<C[0];
            else{
                cout<<C[i-cl+cc];
            }
        }
        cout<<endl;
    }
    return 0;
}

F

int n,k,cc;
ll ans = 0;
template<class T>
struct RMQ {
    vector<vector<T>> jmp;
    RMQ(const vector<T>& V) : jmp(1, V) {
        for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
            jmp.emplace_back(sz(V) - pw * 2 + 1);
            rep(j,0,sz(jmp[k]))
            jmp[k][j] = max(jmp[k - 1][j], jmp[k - 1][j + pw]);
        }
    }
    T query(int a, int b) {
        assert(a < b); // or return inf if a == b
        int dep = 31 - __builtin_clz(b - a);
        return max(jmp[dep][a], jmp[dep][b - (1 << dep)]);
    }
};
set<pii> S;
#define CAT(A,B)  A.insert(A.end(),all(B))
struct ret{
    vll val,L,R;
    void absorb(ret rhs){
        CAT(val,rhs.val);
        CAT(L,rhs.L);
        CAT(R,rhs.R);
    }
};
vector<int> A(1,0);
RMQ<int> Q(A);
ll calc(ret &C){
    ll cr = 0;
    int c = 0;
    while(c<C.val.size()){
        int d = c,cu = 0;
        while(d<C.val.size() && C.val[d]!=-1){
            if(d>c+k-2)cu+=C.R[d];
            d++;
        }
        for(int i=c;i<d;i++){
            cr = cr+C.L[i]*C.R[i];
            cr = cr+1ll*cu*C.L[i];
            if(i+k-1<d){
                cu-=C.R[i+k-1];
            }
        }
        c = d+1;
    }
    return cr;
}
ret solve(int l,int r,int ep){
    if(l>r)return ret();
    int p = l,cmx = Q.query(l,r+1);
    ret C,I;I.val.PB(cmx);I.R.PB(1);I.L.PB(1);
    while(p<=r){
        int nxt = S.lower_bound(MP(cmx,p))->second;
        if(nxt>r){
            C.absorb(solve(p,r,cmx));
            break;
        }else{
            C.absorb(solve(p,nxt-1,cmx));
            C.absorb(I);
            p = nxt+1;
        }
    }
    ans+=calc(C);
    if(ep-cmx>25 || pow(1.0*k,ep-cmx)>2*(r-l+1) || pow(k,ep-cmx)>C.val.size()){
        I.val[0] = -1;
        return I;
    }
    int req = 1;for(int i=0;i<ep-cmx;i++)req*=k;
    int cnt = 0;
    for(auto ct:C.val)if(ct == -1)cnt+=1;
    ret CR;
    if(cnt){
        vll L,R;
        for(int i=0;C.val[i] == cmx;i++){
            if((i+1)/req!=0){
                int cp = (i+1)/req-1;
                if(R.size()<cp+1)R.PB(0);
                R[cp]+=C.R[i];
            }
        }
        for(int i=0;C.val[C.val.size()-1-i] == cmx;i++){
            if((i+1)/req!=0){
                int cp = (i+1)/req-1;
                if(L.size()<cp+1)L.PB(0);
                L[cp]+=C.L[C.L.size()-1-i];
            }
        }
        for(int i=0;i<R.size();i++){
            CR.R.PB(R[i]);
            CR.L.PB(0);
            CR.val.PB(ep);
        }
        CR.R.PB(0);
        CR.L.PB(0);
        CR.val.PB(-1);
        for(int i=0;i<L.size();i++){
            CR.R.PB(0);
            CR.L.PB(L[L.size()-1-i]);
            CR.val.PB(ep);
        }
    }else{
        int cul = C.val.size()/req;
        CR.val = vll(cul,ep);
        CR.L = vll(cul,0);
        CR.R = vll(cul,0);
        for(int i=req;i<=C.val.size();i++){
            CR.R[i/req-1]+=C.R[i-1];
            CR.L[cul-i/req]+=C.L[C.val.size()-i];
        }
    }
    ans-=calc(CR);
    return CR;
}
int main() {
    read(n,k);
    for(int i=1;i<=n;i++){
        read(cc);
        A.PB(cc);
        S.insert(MP(cc,i));
        S.insert(MP(cc,1e9));
    }
    Q = RMQ<int>(A);
    solve(1,n,1e9+1);
    cout<<ans<<endl;
    return 0;
}

评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注