qbxt 10 月模拟赛 Day3

Author： RainAir
发布时间：October 3, 2020
893views
No comments
414 words
Categories：题解

A

取 $\ln$，每次只需要判断 $\sum_{i=1}^k \ln(i) \geq \sum_{i=k+1}^n \ln(i)$ 即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e5 + 5;
int a[MAXN],n,b[MAXN];

int main(){
    scanf("%d",&n);
    long double a=0,b=0;
    FOR(i,1,n) a += log(i);
    ROF(i,n,1){
        b += log(i);
        a -= log(i);
        if(a < b){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}

B

难点在于读入方式。。

我的模拟写法大概是首先按照分号分组，然后每一组按照冒号分组，就可以知道名字了，然后在中括号内根据逗号分组，就可以知道依赖关系了。

然后根据类似拓扑排序的方法，每次维护正在做的工作，每次取出所有同时完成的工作一起扩展，如果有工作所有限制满足的话就按照题目顺序从当前时间开始做。

写+调了2h。。还是自己太菜了，直接导致T3没做出

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
int len;
std::map<std::string,int> S;
std::string str;
int n;
int a[MAXN];
std::vector<int> G[MAXN];
int rk[MAXN],deg[MAXN],ts[MAXN];

struct Node{
    int ts,rk,id;
    Node(int ts=0,int rk=0,int id=0) : ts(ts),rk(rk),id(id) {}

    inline bool operator < (const Node &t) const {
        return MP(ts,rk) < MP(t.ts,t.rk);
    }
};

bool vis[MAXN];
int sa[MAXN];

int main(){
  //  freopen("B.in","r",stdin);
    std::ios::sync_with_stdio(false);
    std::cin >> str;
    int tt = 0;
    for(int l = 0,r = 0;str[l] != '/';l = r+1){
        r = l;
        while(str[r] != ';' && str[r] != '/') ++r;
        int p = l;
        while(str[p] != ':') ++p;
        std::string name = str.substr(l,p-l);
        S[name] = ++n;
        while(str[r] != ':') --r;
        ++r;
        while(str[r] != ';' && str[r] != '/') a[n] = a[n]*10+str[r]-'0',++r;
        if(str[r] == '/') break;
    }
    for(int i=1,l = 0,r = 0;str[l] != '/';l = r+1,++i){
        r = l;
        while(str[r] != ';' && str[r] != '/') ++r;
        int p = l;
        while(str[p] != '[') ++p;
        int q = l;
        while(str[q] != ']') ++q;
        for(int ll = p+1,rr = p+1;ll < q;ll = rr+1){
            rr = ll;
            while(str[rr] != ']' && str[rr] != ',') ++rr;
            int to = S[str.substr(ll,rr-ll)];
//            if(i == 89) DEBUG(to),DEBUG(str.substr(ll,rr-ll));
            G[to].pb(i);++deg[i];
            if(str[rr] == ']') break;
        }
        if(str[r] == '/') break;
    }
    int p = 0,lim = 0;
    while(str[p] != '/') ++p;++p;
    while(p < str.length()) lim = lim*10+str[p]-'0',++p;
    p = 1;
    for(auto x:S) rk[x.se] = p++;
    std::set<Node> tba;
    std::set<P> inw;
    FOR(i,1,n) sa[rk[i]] = i;
    FOR(i,1,n){
        if(!deg[sa[i]]){
            vis[sa[i]] = 1;
            if(inw.size() < lim) inw.insert(MP(a[sa[i]],sa[i]));
            else tba.insert(Node(0,rk[sa[i]],sa[i]));
        }
    }
    int ans = 0;
/*    std::vector<P> sfsf;
    FOR(v,1,n){
        for(auto x:G[v]){
            sfsf.pb(MP(rk[v],rk[x]));
        }
    }*/
    while(!inw.empty()){
        int las = -1;
        while(!inw.empty() && (las == -1 || las == inw.begin()->fi)){
            P t = *inw.begin();inw.erase(inw.begin());
            int v = t.se,w = t.fi;ans = std::max(ans,w);
            for(auto x:G[v]){
                --deg[x];
                if(!deg[x]){
                    tba.insert(Node(w,rk[x],x));
                    vis[x] = 1;
                }
            }
            las = w;
        }
        while(!tba.empty() && inw.size() < lim){
            inw.insert(MP(las+a[tba.begin()->id],tba.begin()->id));
            tba.erase(tba.begin());
        }
    }
    std::cout << ans << '\n';
    return 0;
}

C

暴力的想法是找出循环节，然后可以轻松计算答案。但是发现循环节是 $\text{lcm}$，很大。

我们考虑合并循环节：如果我们在合并两个长度 $a,b$ ，如果 $(a,b)=1$，那么在到达循环节时，每种可能的位置都会被遍历。举个例子（$a=2,b=3$）：

1 2 1 2 1 2
1 2 3 1 2 3
1 - (1,2,3)
2 - (1,2,3)

合并相同长度只需要对应相加即可。所以对于长度全是质数的部分分，我们可以对于每个长度都设一个 $f_i$ 表示有 $i$ 个 $1$ 的位置个数，合并直接背包转移即可。

我们观察一下 $(a,b) = g,g \neq 1$ 的情况：举个例子（$a=4,b=6$）：

1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 5 6 1 2 3 4 5 6
1 - (1,3,5)
2 - (2,4,6)
3 - (1,3,5)
4 - (2,4,6)

也就是说，我们可以把所有数字按照 $\bmod g$ 分组，每一组内都是可以直接背包合并的。

但是如果这样直接做 $\gcd$ 可能会超级大，这里要用一个神奇的优化：

我们考虑我们实际上是可以任意重复每个串若干次，不影响答案的，所以我们的思路是用重复这个操作使得所有串两两之间 $\gcd$ 都不是很大，就可以顺次合并。

我们把长度分解质因数，如果质因数只包含 $2,3,5,7$，我们考虑这样的数的 $\text{lcm}$ 不会超过 $2^5 * 3^3 * 5^2 * 7^2 = 1058400$ ，所以可以都扩展到这个长度然后统一合并。

否则质因数一定包含且仅包含一个 $\geq 11$ 的质数，发现所有这样的数合并后的长度和 $1058400$ 的 $\gcd$ 不会超过 $2^2 * 3=12$。所以我们可以将这些数都扩展到质数$*12$的长度，这样保证了两两类之间的 $\gcd$ 都是 $12$，就可以背包合并了。

时间复杂度 $O(n^2 * 12^2)$，这个感觉就是类似根号平衡一样找一个比较中间的数字。。

这种套路就是如果合并复杂度和 $\gcd$ 有关，并且可以任意延长，就要想到可以通过延长降低 $\gcd$ 这样确实是可行的！

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100 + 5;
const int ha = 1e9 + 7;
const int prime[] = {0,11,13,17,19,23,29,31,37,41,43,47};
const int lcm = 32*27*25*49;

char str[MAXN][MAXN];int len[MAXN],n;
int ans[12][MAXN],t[12][MAXN],b[12][MAXN];
int cnt[2000000+5];
int res[MAXN];

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%s",str[i]+1),len[i] = strlen(str[i]+1);
    FOR(i,1,n){
        if(lcm%len[i]) continue;
        FOR(j,1,lcm) cnt[j] += (str[i][(j-1)%len[i]+1] == '1');
    }
    FOR(i,1,lcm) ans[(i-1)%12][cnt[i]]++;
    FOR(i,1,11){
        int p = prime[i];CLR(cnt,0);CLR(b,0);
        FOR(j,1,n){
            if(len[j]%p) continue;
            FOR(k,1,p*12){
                cnt[k] += (str[j][(k-1)%len[j]+1] == '1');
            }
        }
        FOR(j,1,p*12) b[(j-1)%12][cnt[j]]++;
        FOR(j,0,11) FOR(k,0,n) t[j][k] = ans[j][k],ans[j][k] = 0;
        // DEBUG(b[0][0]);
        FOR(j,0,11){
            FOR(x,0,n){
                FOR(y,0,n){
                    // if(j == 0 && x == 2 && y == 0){
                        // DEBUG(t[j][x]);DEBUG(b[j][y]);
                        // DEBUG(t[j][x]*b[j][y]);
                    // }
                    if(x+y <= n) add(ans[j][x+y],1ll*t[j][x]*b[j][y]%ha);
                }
            }
        }
    // DEBUG(ans[0][2]);
    }
    FOR(i,0,11) FOR(j,0,n) add(res[j],ans[i][j]);
    int coe = 1;
    FOR(i,2,50){
        if(i == 32 || i == 27 || i == 25 || i == 49) continue;
        bool flag = 0;
        FOR(j,1,11) if(i == prime[j]){flag = 1;break;}
        if(flag) continue;
        coe = 1ll*coe*i%ha;
    }
    FOR(i,0,n) res[i] = 1ll*res[i]*coe%ha;
    FOR(i,0,n) printf("%d\n",res[i]);
    return 0;
}

D

这个题就很 naive 了。。暴力的想法是枚举一个 $V$ 形，设坐标为 $i,j,k$，贡献就是 $i * (n-k)$，那么我们考虑枚举 $j$，相当于两边做一个卷积，只需要求一下大于它的所有 $i$ 和 $n-k$ 的和就好了。

这题我思考了一下可以加强：题目大概是计数这样的合法的子序列，满足输入的大小关系，这个题输入的大小关系就是 > < ，设大小关系长度为 $k$，这个题可以做到 $O(nk \log n)$：只需要先考虑处理处大小关系为 $2$ 的答案（对于每个前缀，后缀都处理），就能推到长度为 $3$，就能继续做。。。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

struct BIT{
    int tree[MAXN];
    #define lowbit(x) ((x)&(-(x)))

    inline void add(int pos,int x){
        while(pos){
            ::add(tree[pos],x);
            pos -= lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;
        while(pos < MAXN){
            ::add(res,tree[pos]);
            pos += lowbit(pos);
        }
        return res;
    }
}pre,suf;

int n,a[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i);
    FOR(i,2,n) suf.add(a[i],n-i+1);
    int ans = 0;
    FOR(i,2,n-1){
        pre.add(a[i-1],i-1);
        suf.add(a[i],ha-(n-i+1));
        add(ans,1ll*pre.query(a[i]+1)*suf.query(a[i]+1)%ha);
    }
    printf("%d\n",ans);
    return 0;
}

Last modification：October 8th, 2020 at 10:35 am

如果觉得我的文章对你有用，请随意赞赏

qbxt 10 月模拟赛 Day3

RainAir • 2020 年 10 月 03 日

A

取 $\ln$，每次只需要判断 $\sum_{i=1}^k \ln(i) \geq \sum_{i=k+1}^n \ln(i)$ 即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e5 + 5;
int a[MAXN],n,b[MAXN];

int main(){
    scanf("%d",&n);
    long double a=0,b=0;
    FOR(i,1,n) a += log(i);
    ROF(i,n,1){
        b += log(i);
        a -= log(i);
        if(a < b){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}

B

难点在于读入方式。。

我的模拟写法大概是首先按照分号分组，然后每一组按照冒号分组，就可以知道名字了，然后在中括号内根据逗号分组，就可以知道依赖关系了。

写+调了2h。。还是自己太菜了，直接导致T3没做出

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
int len;
std::map<std::string,int> S;
std::string str;
int n;
int a[MAXN];
std::vector<int> G[MAXN];
int rk[MAXN],deg[MAXN],ts[MAXN];

struct Node{
    int ts,rk,id;
    Node(int ts=0,int rk=0,int id=0) : ts(ts),rk(rk),id(id) {}

    inline bool operator < (const Node &t) const {
        return MP(ts,rk) < MP(t.ts,t.rk);
    }
};

bool vis[MAXN];
int sa[MAXN];

int main(){
  //  freopen("B.in","r",stdin);
    std::ios::sync_with_stdio(false);
    std::cin >> str;
    int tt = 0;
    for(int l = 0,r = 0;str[l] != '/';l = r+1){
        r = l;
        while(str[r] != ';' && str[r] != '/') ++r;
        int p = l;
        while(str[p] != ':') ++p;
        std::string name = str.substr(l,p-l);
        S[name] = ++n;
        while(str[r] != ':') --r;
        ++r;
        while(str[r] != ';' && str[r] != '/') a[n] = a[n]*10+str[r]-'0',++r;
        if(str[r] == '/') break;
    }
    for(int i=1,l = 0,r = 0;str[l] != '/';l = r+1,++i){
        r = l;
        while(str[r] != ';' && str[r] != '/') ++r;
        int p = l;
        while(str[p] != '[') ++p;
        int q = l;
        while(str[q] != ']') ++q;
        for(int ll = p+1,rr = p+1;ll < q;ll = rr+1){
            rr = ll;
            while(str[rr] != ']' && str[rr] != ',') ++rr;
            int to = S[str.substr(ll,rr-ll)];
//            if(i == 89) DEBUG(to),DEBUG(str.substr(ll,rr-ll));
            G[to].pb(i);++deg[i];
            if(str[rr] == ']') break;
        }
        if(str[r] == '/') break;
    }
    int p = 0,lim = 0;
    while(str[p] != '/') ++p;++p;
    while(p < str.length()) lim = lim*10+str[p]-'0',++p;
    p = 1;
    for(auto x:S) rk[x.se] = p++;
    std::set<Node> tba;
    std::set<P> inw;
    FOR(i,1,n) sa[rk[i]] = i;
    FOR(i,1,n){
        if(!deg[sa[i]]){
            vis[sa[i]] = 1;
            if(inw.size() < lim) inw.insert(MP(a[sa[i]],sa[i]));
            else tba.insert(Node(0,rk[sa[i]],sa[i]));
        }
    }
    int ans = 0;
/*    std::vector<P> sfsf;
    FOR(v,1,n){
        for(auto x:G[v]){
            sfsf.pb(MP(rk[v],rk[x]));
        }
    }*/
    while(!inw.empty()){
        int las = -1;
        while(!inw.empty() && (las == -1 || las == inw.begin()->fi)){
            P t = *inw.begin();inw.erase(inw.begin());
            int v = t.se,w = t.fi;ans = std::max(ans,w);
            for(auto x:G[v]){
                --deg[x];
                if(!deg[x]){
                    tba.insert(Node(w,rk[x],x));
                    vis[x] = 1;
                }
            }
            las = w;
        }
        while(!tba.empty() && inw.size() < lim){
            inw.insert(MP(las+a[tba.begin()->id],tba.begin()->id));
            tba.erase(tba.begin());
        }
    }
    std::cout << ans << '\n';
    return 0;
}

C

暴力的想法是找出循环节，然后可以轻松计算答案。但是发现循环节是 $\text{lcm}$，很大。

我们考虑合并循环节：如果我们在合并两个长度 $a,b$ ，如果 $(a,b)=1$，那么在到达循环节时，每种可能的位置都会被遍历。举个例子（$a=2,b=3$）：

1 2 1 2 1 2
1 2 3 1 2 3
1 - (1,2,3)
2 - (1,2,3)

我们观察一下 $(a,b) = g,g \neq 1$ 的情况：举个例子（$a=4,b=6$）：

1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 5 6 1 2 3 4 5 6
1 - (1,3,5)
2 - (2,4,6)
3 - (1,3,5)
4 - (2,4,6)

也就是说，我们可以把所有数字按照 $\bmod g$ 分组，每一组内都是可以直接背包合并的。

但是如果这样直接做 $\gcd$ 可能会超级大，这里要用一个神奇的优化：

时间复杂度 $O(n^2 * 12^2)$，这个感觉就是类似根号平衡一样找一个比较中间的数字。。

这种套路就是如果合并复杂度和 $\gcd$ 有关，并且可以任意延长，就要想到可以通过延长降低 $\gcd$ 这样确实是可行的！

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100 + 5;
const int ha = 1e9 + 7;
const int prime[] = {0,11,13,17,19,23,29,31,37,41,43,47};
const int lcm = 32*27*25*49;

char str[MAXN][MAXN];int len[MAXN],n;
int ans[12][MAXN],t[12][MAXN],b[12][MAXN];
int cnt[2000000+5];
int res[MAXN];

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%s",str[i]+1),len[i] = strlen(str[i]+1);
    FOR(i,1,n){
        if(lcm%len[i]) continue;
        FOR(j,1,lcm) cnt[j] += (str[i][(j-1)%len[i]+1] == '1');
    }
    FOR(i,1,lcm) ans[(i-1)%12][cnt[i]]++;
    FOR(i,1,11){
        int p = prime[i];CLR(cnt,0);CLR(b,0);
        FOR(j,1,n){
            if(len[j]%p) continue;
            FOR(k,1,p*12){
                cnt[k] += (str[j][(k-1)%len[j]+1] == '1');
            }
        }
        FOR(j,1,p*12) b[(j-1)%12][cnt[j]]++;
        FOR(j,0,11) FOR(k,0,n) t[j][k] = ans[j][k],ans[j][k] = 0;
        // DEBUG(b[0][0]);
        FOR(j,0,11){
            FOR(x,0,n){
                FOR(y,0,n){
                    // if(j == 0 && x == 2 && y == 0){
                        // DEBUG(t[j][x]);DEBUG(b[j][y]);
                        // DEBUG(t[j][x]*b[j][y]);
                    // }
                    if(x+y <= n) add(ans[j][x+y],1ll*t[j][x]*b[j][y]%ha);
                }
            }
        }
    // DEBUG(ans[0][2]);
    }
    FOR(i,0,11) FOR(j,0,n) add(res[j],ans[i][j]);
    int coe = 1;
    FOR(i,2,50){
        if(i == 32 || i == 27 || i == 25 || i == 49) continue;
        bool flag = 0;
        FOR(j,1,11) if(i == prime[j]){flag = 1;break;}
        if(flag) continue;
        coe = 1ll*coe*i%ha;
    }
    FOR(i,0,n) res[i] = 1ll*res[i]*coe%ha;
    FOR(i,0,n) printf("%d\n",res[i]);
    return 0;
}

D

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

struct BIT{
    int tree[MAXN];
    #define lowbit(x) ((x)&(-(x)))

    inline void add(int pos,int x){
        while(pos){
            ::add(tree[pos],x);
            pos -= lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;
        while(pos < MAXN){
            ::add(res,tree[pos]);
            pos += lowbit(pos);
        }
        return res;
    }
}pre,suf;

int n,a[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i);
    FOR(i,2,n) suf.add(a[i],n-i+1);
    int ans = 0;
    FOR(i,2,n-1){
        pre.add(a[i-1],i-1);
        suf.add(a[i],ha-(n-i+1));
        add(ans,1ll*pre.query(a[i]+1)*suf.query(a[i]+1)%ha);
    }
    printf("%d\n",ans);
    return 0;
}

qbxt 10 月模拟赛 Day3

A

B

C

D

Leave a Comment Cancel reply

NOI2021 退役记

I'm back

SDOI2020 退役记

点双连通分量 & 圆方树学习笔记

CSP2019 游记

最小树形图 / 朱刘算法

「JLOI2016」成绩比较

此内容被密码保护

CF 1404 题解

ARC099 题解

qbxt 10 月模拟赛 Day3

A

B

C

D