A.很水的题目，3个for循环就可以了
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char str[];
int main()
{
cin>>str;
int ans = ;
int L = strlen(str);
for(int i = ; i < L; i++)
for(int j = i+; j < L; j++)
for(int k = j+; k < L; k++)
if(str[i] == 'Q' && str[j] == 'A' && str[k] == 'Q') ans++;
cout<<ans<<endl;
return ;
}
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 + ;
LL mypow(LL a, LL b){
LL ans = ; for(; b; b>>=, (a*=a)%=MOD) if(b&) (ans*=a)%=MOD;return ans;
}
LL x, y, k;
int main()
{
cin>>x>>y>>k;
if( ((x+y)&) && k == -){
cout<<<<endl;
return ;
}
cout<<mypow(, ((x-)%(MOD-)) *((y-)%(MOD-)) %(MOD-))<<endl;
return ;
}
C.首先必定有一个元素是所有元素的gcd，否则就是无解。
然后这个gcd也必定是最小的，令它为g，那么我们只需要把g插入到原序列中，就可以保证两两之间的gcd被限制到g，就满足了要求。
这个构造还是挺巧妙的。
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = ;
int a[maxn], n;
int H[];
int gcd(int x, int y) { return x % y == ? y : gcd(y, x%y); }
int main()
{
cin>>n;
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
int ans = a[];
for(int i = ; i <= n; i++) ans = gcd(ans, a[i]);
if(ans != a[]){
cout<<"-1"<<endl;
return ;
}
cout<<*n-<<endl;
cout<<a[]<<" ";
for(int i = ; i <= n; i++){
cout<<a[]<<" "<<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 + ;
long long v[maxn][];
vector<long long> D[maxn], Sum[maxn];
long long getsum(int k, int i, int j){
if(i > j) return ;
return i- < ? Sum[k][j] : Sum[k][j] - Sum[k][i-];
}
int main()
{
int n, m, x, a, h;
cin>>n>>m;
for(int i = ; i < n; i++) {
scanf("%d", &x);
v[(i+)/][(i+)%] = x;
}
for(int i = n; i >= ; i--){
D[i].push_back();
if(i* <= n){
for(auto x : D[i*])
D[i].push_back(x+v[i][]);
}
if(i*+ <= n){
for(auto x : D[i*+])
D[i].push_back(x+v[i][]);
}
sort(D[i].begin(), D[i].end());
Sum[i].push_back(D[i][]);
for(int j = ; j < D[i].size(); j++) Sum[i].push_back(D[i][j]+Sum[i][j-]);
}
while(m--){
scanf("%d %d", &a, &h);
long long d = , n = , decans = ;
int pos1 = upper_bound(D[a].begin(), D[a].end(), h) - D[a].begin();
n += pos1;
decans += getsum(a, , pos1-);
int i = a, j;
while(i != ){
j = i^;
d += v[i/][i&];
if(d < h) {
n++;
decans += d;
}
i /= ;
pos1 = upper_bound(D[j].begin(), D[j].end(), h-v[i][j&]-d) - D[j].begin();
n += pos1;
decans += getsum(j, , pos1-)+pos1*(d+v[i][j&]);
}
long long ans = (long long)n*h - decans;
printf("%lld\n", 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 + ;
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 = , Z = ;
int vis[maxn];
void tj(int x)
{
dfn[x]=low[x]=++C; ins[x]=; 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]=; 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 = ;
void dfs(int x){
if(vis[x]) return;
vis[x] = ; dp[x] = ;
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 = ; 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 = ;
for(auto &e : edges){
while(e.cost >= (k+)*(k+)/) k++;
long long temp = (long long)e.cost*(k+) - (long long)k*(k+)*(k+)/;
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 ;
}