A.很水的题目，3个for循环就可以了
#include <iostream> #include <cstdio> #include <cstring> using namespace std; char str[1000]; int main() { cin>>str; int ans = 0; int L = strlen(str); for(int i = 0; i < L; i++) for(int j = i+1; j < L; j++) for(int k = j+1; k < L; k++) if(str[i] == 'Q' && str[j] == 'A' && str[k] == 'Q') ans++; cout<<ans<<endl; return 0; }
B.如果存在解，那么答案就是2^(x-1)(y-1)，然后快速幂就可以了。
实际上就是判断(x-1)*(y-1)都填1有没有解，如果有的话，其实你变换任意一个矩阵内元素的值都有对应的唯一一种情况成立。
注意费马小定理和long long的溢出问题。
#include <iostream> #include <cstdio> using namespace std; typedef long long LL; const LL MOD = 1e9 + 7; LL mypow(LL a, LL b){ LL ans = 1; for(; b; b>>=1, (a*=a)%=MOD) if(b&1) (ans*=a)%=MOD;return ans; } LL x, y, k; int main() { cin>>x>>y>>k; if( ((x+y)&1) && k == -1){ cout<<0<<endl; return 0; } cout<<mypow(2, ((x-1)%(MOD-1)) *((y-1)%(MOD-1)) %(MOD-1))<<endl; return 0; }
C.首先必定有一个元素是所有元素的gcd，否则就是无解。
然后这个gcd也必定是最小的，令它为g，那么我们只需要把g插入到原序列中，就可以保证两两之间的gcd被限制到g，就满足了要求。
这个构造还是挺巧妙的。
#include <iostream> #include <cstdio> using namespace std; const int maxn = 5000; int a[maxn], n; int H[2000000]; int gcd(int x, int y) { return x % y == 0 ? y : gcd(y, x%y); } int main() { cin>>n; for(int i = 1; i <= n; i++) scanf("%d", &a[i]); int ans = a[1]; for(int i = 2; i <= n; i++) ans = gcd(ans, a[i]); if(ans != a[1]){ cout<<"-1"<<endl; return 0; } cout<<2*n-1<<endl; cout<<a[1]<<" "; for(int i = 2; i <= n; i++){ cout<<a[1]<<" "<<a[i]<<" "; } }
D.树是二叉树，就很好做了
每个结点保存子树中到它的距离集合
答案就是子树内满足要求的点的个数n*h和它们的距离和的差，就是n*h - sum
查询这个用二分查找就可以了
注意到非子树内也有满足要求的点，
解决这个问题只需要沿着祖先往上爬就可以了，沿途统计答案。
这里使用了upper_bound，还是很好用的。
#include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int maxn = 1e6 + 100; long long v[maxn][2]; vector<long long> D[maxn], Sum[maxn]; long long getsum(int k, int i, int j){ if(i > j) return 0; return i-1 < 0 ? Sum[k][j] : Sum[k][j] - Sum[k][i-1]; } int main() { int n, m, x, a, h; cin>>n>>m; for(int i = 1; i < n; i++) { scanf("%d", &x); v[(i+1)/2][(i+1)%2] = x; } for(int i = n; i >= 1; i--){ D[i].push_back(0); if(i*2 <= n){ for(auto x : D[i*2]) D[i].push_back(x+v[i][0]); } if(i*2+1 <= n){ for(auto x : D[i*2+1]) D[i].push_back(x+v[i][1]); } sort(D[i].begin(), D[i].end()); Sum[i].push_back(D[i][0]); for(int j = 1; j < D[i].size(); j++) Sum[i].push_back(D[i][j]+Sum[i][j-1]); } while(m--){ scanf("%d %d", &a, &h); long long d = 0, n = 0, decans = 0; int pos1 = upper_bound(D[a].begin(), D[a].end(), h) - D[a].begin(); n += pos1; decans += getsum(a, 0, pos1-1); int i = a, j; while(i != 1){ j = i^1; d += v[i/2][i&1]; if(d < h) { n++; decans += d; } i /= 2; pos1 = upper_bound(D[j].begin(), D[j].end(), h-v[i][j&1]-d) - D[j].begin(); n += pos1; decans += getsum(j, 0, pos1-1)+pos1*(d+v[i][j&1]); } long long ans = (long long)n*h - decans; printf("%lld ", ans); } }
E.就是tarjan缩点+动态规划。
缩点之后可以用dfs直接更新dp。
注意要先求最大值，再加环构成的影响。
求一个边的循环贡献，这里是先排了个序，然后按顺序扫一遍求出来的。
当然也可以二分找。
#include <iostream> #include <cstdio> #include <stack> #include <vector> #include <queue> #include <algorithm> #define mp make_pair #define fi first #define se second using namespace std; const int maxn = 1e6 + 100; stack<int> S; vector< pair<int, int> > G2[maxn]; vector<int> G[maxn]; long long dp[maxn], v[maxn]; int dfn[maxn], low[maxn], ins[maxn], bl[maxn], C = 0, Z = 0; int vis[maxn]; void tj(int x) { dfn[x]=low[x]=++C; ins[x]=1; S.push(x); for(auto b : G[x]) { if(!dfn[b]) tj(b),low[x]=min(low[x],low[b]); else if(ins[b]) low[x]=min(low[x],dfn[b]); } if(dfn[x]!=low[x]) return; ++Z; while(!S.empty()) { int g=S.top(); S.pop(); ins[g]=0; bl[g]=Z; if(g==x) break; } } struct Edge{ int from, to, cost; Edge(int from, int to, int cost):from(from), to(to), cost(cost) {} bool operator <(const Edge &B) const{ return cost < B.cost; } }; vector<Edge> edges; int n, m, x, y, z, s; long long ans = 0; void dfs(int x){ if(vis[x]) return; vis[x] = 1; dp[x] = 0; for(auto e : G2[x]){ dfs(e.fi); dp[x] = max(dp[x], dp[e.fi] + e.se); } dp[x] += v[x]; ans = max(ans, dp[x]); } int main() { cin>>n>>m; for(int i = 1; i <= m; i++){ scanf("%d %d %d", &x, &y, &z); G[x].push_back(y); edges.push_back(Edge(x, y, z)); } sort(edges.begin(), edges.end()); cin>>s; tj(s); int k = 0; for(auto &e : edges){ while(e.cost >= (k+1)*(k+2)/2) k++; long long temp = (long long)e.cost*(k+1) - (long long)k*(k+1)*(k+2)/6; if(bl[e.from] == bl[e.to]) v[bl[e.from]] += temp; else G2[bl[e.from]].push_back(mp(bl[e.to], e.cost)); } dfs(bl[s]); cout<<ans<<endl; return 0; }