【牛客练习赛64】前三题题解
A 怪盗-1412
题意：给定字符1、4、2的数量，求将所给的字符排列后子序列为1412的最大个数。
可以发现当排列为111...444...111...222... 的时候可以得到最大个数。
答案为 (n/2) * m * (n-n/2) * k
代码：
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n, m, k;
void slove() {
cin >> n >> m >> k;
if (n < 2 || m < 1 || k < 1) {cout << "0\n"; return;}
ll tmp = n / 2;
if (n%2) tmp++;
cout << m * k * tmp * (n/2) << '\n';
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int t; cin >> t; while(t--)
slove();
return 0;
} B Dis2
题意：给出一颗树，求每个结点与自身距离为2的结点的个数 （一看题一直以为是相同深度结点的个数QAQ...)（划掉
可以用邻接表来储存，答案即为该结点所连接的结点的儿子的个数（如果连接的是父结点那么就是父结点的父结点的个数，当然只有一个），直接写就好了。
代码：
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i=(a); i<(n); i++)
#define per(i, a, n) for (int i=(a); i>(n); i--)
typedef long long ll;
const int maxn = 2e5+5;
using namespace std;
vector<ll> G[maxn];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
ll n,u,v;
cin >> n;
rep(i,1,n) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
rep(i,1,n+1) {
ll ans = 0;
for(auto c:G[i]) {
ans += G[c].size() - 1;
}
cout << ans << '\n';
}
return 0;
} C 序列卷积之和
思路：这道题就是求贡献。
不会的题目就打表看规律（雾
int n=5;
int map[100][100];
for(int l=1; l<=n; l++)
for(int r=l; r<=n; r++)
for(int i=l; i<=r; i++)
for(int j=i; j<=r; j++)
map[i][j]++;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
cout << map[i][j] << ' ';
if (j==n) cout << '\n';
} 就像这样， 然后会发现产生了下图的数据 
第一行可以表示成
，以此类推，把所有行加起来就得到了答案。我们就能得到一个)
的算法，但是交上去就超时了QAQ
进一步处理前缀和就可以得到答案。
代码：
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i=(a); i<(n); i++)
#define per(i, a, n) for (int i=(a); i>(n); i--)
typedef long long ll;
const int maxn = 2e5+5;
const int mod = 1e9+7;
using namespace std;
ll a[maxn], k[maxn]={0};
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
ll n; cin >> n;
ll res = 0;
rep(i, 1, n+1) cin>>a[i];
per(i, n, 0) {
k[i] = (k[i+1] + (n-i+1)*a[i]%mod)%mod;
}
rep(i, 1, n+1) {
res = (res + (i*a[i])%mod*k[i]%mod)%mod;
}
cout << res;
return 0;
} 
阿里巴巴HR面98人在聊