A

#include 
    
     using namespace std;typedef long long ll;string st;int main(){    //freopen("in.txt","r",stdin);    cin>>st;    int cnt=0;    for(int i=0;i<(int)st.size();i++)        for(int j=i+1;j<(int)st.size();j++)            for(int k=j+1;k<(int)st.size();k++)                if(st[i]=='Q'&&st[j]=='A'&&st[k]=='Q')                    cnt++;    cout<
    

B

猜结论。。。

#include 
    
     using namespace std;typedef long long ll;ll n,m,k;inline ll power(ll a,ll n,ll p){    ll ret=1;ll now=a;    while(n!=0){        if(n&1)            ret=ret*now%p;        now=now*now%p;        n>>=1;    }    return ret;}int main(){    //freopen("in.txt","r",stdin);    cin>>n>>m>>k;    if(((n+m)&1)&&k==-1)        puts("0");    else {        ll res = power(2,n-1,1000000007);        res = power(res,m-1,1000000007);        cout<
    

C

提供了一个假算法，惨遭hack。正解构造。

如果整个数列的最大公约数是最小的那个数字，那么可以构造出一个数列，只需要让每个数字中间夹着一个a[0] 就可以让区间长度大于等于二的区间的最大公约数为a[0]。

#include 
    
     int n,a[1005];int main(){    scanf("%d",&n);    for(int i=0;i
    

D

预处理出每个子树，每个点到该子树的根的距离，排个序。复杂度$O(n log n log n)$

然后对于每个询问，每次向上爬就行了。复杂度$O(m log n log n)$。

#include 
    
     #define pb push_backusing namespace std;typedef long long ll;const int maxn = 1e6 + 5;vector
     
       dis[maxn];vector
      
        sum[maxn];int n, m, A;ll H;int L[maxn];int cnt;template
       
         inline void read(T &x) {    x = 0; T f = 1; char ch; do {ch = getchar(); if (ch == '-')f = -1;} while (ch < '0' || ch > '9'); do x = x * 10 + ch - '0', ch = getchar(); while (ch <= '9' && ch >= '0'); x *= f;}template
        
          inline void read(A&x, B&y) {read(x); read(y);}template
         
           inline void read(A&x, B&y, C&z) {read(x); read(y); read(z);}template
          
            inline void read(A&x, B&y, C&z, D&w) {read(x); read(y); read(z); read(w);}void dfs(int id) { dis[id].pb(0); if (id * 2 > n) { return; } else if (id * 2 + 1 > n) { int l = id * 2; dfs(l); for (auto d : dis[l]) { dis[id].pb(d + L[l]); } } else { int l = id * 2, r = id * 2 + 1; dfs(l); for (auto d : dis[l]) { dis[id].pb(d + L[l]); } dfs(r); for (auto d : dis[r]) { dis[id].pb(d + L[r]); } }}ll get(int A, ll H) { int id = upper_bound(dis[A].begin(), dis[A].end(), H) - dis[A].begin(); if (!id) return 0; return H * id - sum[A][id - 1];}int main() { //freopen("in.txt","r",stdin); read(n, m); for (int i = 2; i <= n; i++) read(L[i]); dfs(1); for (int i = 1; i <= n; i++) sort(dis[i].begin(), dis[i].end()); for (int i = 1; i <= n; i++) { ll tmp = 0; for (int j = 0; j < (int)dis[i].size(); j++) { tmp += dis[i][j]; sum[i].pb(tmp); } } ll xres; while (m--) { read(A, H); ll res = 0; res += xres = get(A, H); //cout<<"#"<
           
            <
            
             = L[now * 2]) { res += xres = get(now * 2, H - L[now * 2]); //cout<<"#"<
             
              <
              
               = L[now * 2 + 1]) { res += xres = get(now * 2 + 1, H - L[now * 2 + 1]); //cout<<"#"<
               
                <
               
              
             
            
           
          
         
        
       
      
     
    

E

首先，强连通分量中的每条边是都可以走"完"的。

对于边权w，可以二分一个最大的p，满足$w-1-2-...-p>=0$，此时的贡献为$w(p+1)-\frac{p(p+1)(p+2)}{6}$.

缩点之后做一次dag上的dp。

#include 
    
     using namespace std;typedef long long ll;const int maxn = 1e6+5;const int maxm = 1e6+5;template
     
       inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}template
      
        inline void read(A&x,B&y){read(x);read(y);}template
       
         inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}template
        
          inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}struct node{    int v;ll w;    node(){}    node(int _v,ll _w):v(_v),w(_w){}};vector
         
           e[maxn];int Low[maxn],DFN[maxn],Stack[maxn],Belong[maxn];int num[maxn];int Index,top,n,m,x,y;ll z;int scc;bool Instack[maxn];ll score[maxn];vector
          
            scce[maxn];ll dp[maxn];void Tarjan(int u){ int v; Low[u]=DFN[u]=++Index; Stack[top++]=u; Instack[u]=true; for(auto enxt:e[u]){ v=enxt.v; if(!DFN[v]){ Tarjan(v); Low[u]=min(Low[u],Low[v]); } else if(Instack[v] && Low[u]>DFN[v]) Low[u]=DFN[v]; } if(Low[u]==DFN[u]){ scc++; do{ v=Stack[--top]; Instack[v]=false; Belong[v]=scc; num[scc]++; }while(v!=u); }}int indeg[maxn],outdeg[maxn];ll calc(ll w){ ll l=0,r=1e6+5,rt; while(l<=r){ ll mid=(l+r)/2; if(mid*(mid+1)/2<=w) l=(rt=mid)+1; else r=mid-1; } ll ret=w*(rt+1ll)-rt*(rt+1ll)*(rt+2ll)/6ll; return ret;}inline void solve(int n){ memset(DFN,0,sizeof DFN); memset(num,0,sizeof num); memset(Instack,0,sizeof Instack); Index=scc=top=0; for(int i=1;i<=n;i++) if(!DFN[i]) Tarjan(i); memset(indeg,0,sizeof indeg); memset(outdeg,0,sizeof outdeg); for(int u=1;u<=n;u++) scce[Belong[u]].push_back(u); for(int u=1;u<=n;u++) for(auto enxt:e[u]){ int v=enxt.v; if(Belong[u]!=Belong[v]){ outdeg[Belong[u]]++; indeg[Belong[v]]++; } else { score[Belong[u]]+=calc(enxt.w); } }}ll find(int nowscc){ if(dp[nowscc]!=-1) return dp[nowscc]; ll ret = 0; for(auto u:scce[nowscc]) for(auto enxt:e[u]){ int v=enxt.v; if(Belong[u]==Belong[v]) continue; ll w=enxt.w; ret = max(ret,find(Belong[v])+w); } dp[nowscc]=(ret+score[nowscc]); return dp[nowscc];}int main(){ //freopen("in.txt","r",stdin); read(n,m); for(int i=1;i<=m;i++){ read(x,y,z); e[x].push_back(node(y,z)); } solve(n); // printf("%d\n",Belong[0]); // for(int i=1;i<=scc;i++){ // for(auto ep:scce[i]) // printf("%d ",ep); // puts(""); // } memset(dp,-1,sizeof dp); int start; read(start); ll res = find(Belong[start]); cout<