Codeforces Round #447 (Div. 2) 题解

题目链接：http://codeforces.com/contest/894

A. QAQ

题意：问你有多少个QAQ子序列

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<s.size();i++){
        for(int j=i+1;j<s.size();j++){
            for(int k=j+1;k<s.size();k++){
                if(s[i]=='Q'&&s[j]=='A'&&s[k]=='Q') ans++;
            }
        }
    }
    return 0*printf("%d\n", ans);
}

B. Ralph And His Magic Field

题意：给你n*m的矩阵，问你有多少种填数的方案，使得每一行和每一列的乘积都是k

解法：打表找了规律发现是2^{(n-1)*(m-1)}，唯一的hack点，无解的情况。当n,m不同为奇偶的时候，k=-1时无解。靠着这个hack点上分。。。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL qsm(LL a, LL n){
    LL ret=1;
    while(n){
        if(n&1) ret=(ret%mod*a%mod)%mod;
        a=(a%mod*a%mod)%mod;
        n/=2;
    }
    return ret;
}

int main(){
    LL n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    if(k==1) printf("%lld\n", qsm(qsm(2,n-1),m-1)%mod);
    else{
        if((n+m)&1) puts("0");
        else printf("%lld\n", qsm(qsm(2,n-1),m-1));
    }
    return 0;
}

C. Marco and GCD Sequence

题意：Marco在梦中遇见一个老头，老头告诉了他长生不老的方法，然后Marco想来后却只记得：给你n个所有GCD的集合S，然后让你去构造原来的序列，使得所有原序列的子区间的GCD都在集合S中。如果不存在则输出-1.

解法：这个题是真的秀了我一脸，一直以为是原序列，结果是every。构造方法十分脑洞：如果最小的GCD集合中的元素不是其他的GCD则输出-1，否则把最小的元素插空到集合中。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n, a[maxn];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=2; i<=n; i++){
        if(a[i]%a[1]!=0){
            return 0*puts("-1");
        }
    }
    printf("%d\n", n*2);
    for(int i=1; i<=n; i++){
        printf("%d %d ", a[i], a[1]);
    }
    printf("\n");
}

D. Ralph And His Tour in Binary Country

题意：给你一个树，边的连接方式是i与i/2连一条无向边，长度为l[i]。q个询问，每个询问给出一个点a和一个值H，求以a为起点到任意点为终点获得（happiness=H-路径长度）不为负数的所有happiness之和。

解法：题解搬运：每一个点递增有序地储存以它为根节点，所有子节点（包括自己）到它的距离并处理出前缀和。所需总空间为O(nlog(n))，然后对于每个询问，从询问点不断往上爬（编号/2就是了）并且减去边长,在每一层时，二分查询左右子树lch和rch（不是刚爬上来的那个子树）中满足条件（总路径小于H）的最大编号，然后就是直接利用前缀和贡献答案就是了。时间复杂度为O(nlog(n) + m(log(n))2)——使用归并排序的情况下（预处理时从下往上处理就可以使用归并了）。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+50;
vector <int> ln[maxn];
vector <LL> sum[maxn];
int n, q, a[maxn], len[maxn];
void Merge(int x, int y){
    int ad = len[y];
    int i=0,j=0,k=0,lx = ln[x].size(), ly = ln[y].size();
    while(i<lx&&j<ly){
        if(ln[x][i]<ln[y][j]+ad) a[k++]=ln[x][i++];
        else a[k++]=ln[y][j++]+ad;
    }
    while(i<lx) a[k++]=ln[x][i++];
    while(j<ly) a[k++]=ln[y][j++]+ad;
    for(i=0;i<lx;i++) ln[x][i]=a[i];
    for(i=lx;i<k;i++) ln[x].push_back(a[i]);
}
LL cal(int x, int lx){
    int l=0,r=ln[x].size()-1,ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(ln[x][mid]<=lx) ans=mid,l=mid+1;
        else r=mid-1;
    }
    if(ans==-1) return 0;
    return 1LL*lx*(ans+1)-sum[x][ans];
}

int main(){
    scanf("%d %d", &n,&q);
    for(int i=2; i<=n; i++) scanf("%d", &len[i]);
    for(int i=1; i<=n; i++) ln[i].push_back(0);
    for(int i=n; i>1; i--) Merge(i/2, i);
    for(int i=1; i<=n; i++){
        for(int j=0,k=ln[i].size();j<k; j++){
            sum[i].push_back(ln[i][j]);
            if(j) sum[i][j]+=sum[i][j-1];
        }
    }
    while(q--){
        int j, k;
        scanf("%d %d", &j,&k);
        LL now = 0;
        for(int last=0;j;k-=len[j],last=j,j>>=1){
            if(k<0) break;
            now += k;
            int lson = j*2, rson = j*2+1;
            if(lson<=n&&last!=lson) now += cal(lson, k-len[lson]);
            if(rson<=n&&last!=rson) now += cal(rson, k-len[rson]);
        }
        printf("%lld\n", now);
    }
}

E. Ralph and Mushrooms

题意：给你n个点m条边的有向图，每条边都会有蘑菇，一开始第i个边有a[i]个蘑菇，第一次经过能获得a[i]个，第二次能获得a[i]-1个，第三次能获得a[i]-1-2个，直到a[i]非负。现在给你起点，问你最多能获得多少个蘑菇。

解法：非常套路的强连通缩点。一个强连通里面，一定能把所有边的蘑菇都采完。然后缩点之后就是一个dag了，跑个dp就好了。中间算一个边能取多少个蘑菇的时候，用二分就好了。给点编号用unorder_map加速。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+7;
vector <int> G[maxn],V[maxn],E[maxn],V2[maxn];
int st, pre[maxn], low[maxn], scc[maxn], dfsclk, scccnt, num[maxn], in[maxn], n, m;
LL val[maxn], dp[maxn];
vector <int> p[maxn], q[maxn];
unordered_map <int, int> mp;
stack <int> S;
void dfs(int u){
    pre[u] = low[u] = ++dfsclk;
    S.push(u);
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(!pre[v]){
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if(!scc[v]){
            low[u] = min(low[u], pre[v]);
        }
    }
    if(low[u]==pre[u]){
        scccnt++;
        do{
            u = S.top(); S.pop();
            scc[u] = scccnt;
            num[scccnt]++;
        }while(pre[u]!=low[u]);
    }
}
void find_scc(){
    dfsclk = scccnt = 0;
    memset(pre, 0, sizeof(pre));
    memset(scc, 0, sizeof(scc));
    for(int i=0; i<n; i++) if(!pre[i]) dfs(i);
}
LL cal_sum(LL x){
    x++;
    return x*(x-1)*(x+1)/6LL;
}
LL calc(LL x){
    LL l=1, r=1e5+7, ans=0;
    while(l <= r){
        LL mid = (l+r)/2;
        if(x>mid*(mid+1)/2){
            ans = mid;
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    return x+x*ans-cal_sum(ans);
}
LL solve(int x){
    if(dp[x]!=-1) return dp[x];
    dp[x] = 0;
    for(int i=0; i<E[x].size(); i++){
        dp[x] = max(dp[x], solve(E[x][i])+V2[x][i]);
    }
    dp[x] += val[x];
    return dp[x];
}

int main(){
    scanf("%d %d", &n,&m);
    for(int i=0; i<m; i++){
        int a,b,c;
        scanf("%d %d %d", &a,&b,&c);
        G[a].push_back(b);
        V[a].push_back(c);
    }
    find_scc();
    int tot = 0;
    for(int i=1; i<=n; i++){
        if(!mp.count(scc[i])){
            mp[scc[i]] = tot;
            tot++;
        }
        p[mp[scc[i]]].push_back(i);
    }
    scanf("%d", &st);
    for(int i=0; i<tot; i++){
        for(int j=0; j<p[i].size(); j++){
            for(int k=0; k<G[p[i][j]].size(); k++){
                int u = p[i][j], v = G[u][k];
                if(scc[u]==scc[v]){
                    val[i]+=calc(V[u][k]);
                }else{
                    E[i].push_back(mp[scc[v]]);
                    V2[i].push_back(V[u][k]);
                }
            }
        }
    }
    memset(dp, -1, sizeof(dp));
    solve(mp[scc[st]]);
    LL ans = 0;
    for(int i=0; i<tot; i++) ans = max(ans, dp[i]);
    return 0*printf("%lld\n", ans);
}