题外话：这次比赛打得很开心(指没爆0)，前面两个题目难度还行，第三题我感觉好有意思啊hah。(没划水就是好比赛)
A:怪盗-1412
题意：一个长度为n+m+k包含n个数字1，m个数字2和k个数字4的数组，最多可能有多少个子序列1412？
如果一个序列是数组的子序列，当且仅当这个序列可以由数组删去任意个元素，再将数组中的剩余元素按顺序排列而成。
思路：第一眼感觉是个数学题，一开始心里的答案是C(n,2) * m * k,然后发现样例都过不了，然后发现我构造的串是11111122244444这样的，这样会少取一个1，所以不行，也就是说1必须会分成两部分一部分在前面一部分在中间，也就是1111122222111111444444这样子的，讨论一下n的奇偶性，我们知道当n为偶数答案是k * m * (n / 2) * (n / 2)，当n为奇数的时候答案是k * m * (n / 2) * ((n / 2) + 1)。这样这题就结束了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long int ll;
void solved(){
int t;cin>>t;
while(t--){
ll n,m,k;cin>>n>>m>>k;
if(n & 1){
cout<<k * m * (n / 2) * ((n / 2) + 1)<<endl;
}else{
cout<<k * m * (n / 2) * (n / 2)<<endl;
}
}
}
int main(){
solved();
return 0;
}B:Dis2
题意：
给出一颗n个点n−1条边的树，点的编号为1,2,...,n−1,n，对于每个点i(1<=i<=n)，输出与点{i}i距离为2的点的个数。
两个点的距离定义为两个点最短路径上的边的条数。
思路：
注意到是树，我们可以从贡献的角度来思路，一个节点它会对它父亲的父亲产生贡献，同时它父亲的父亲也会对它产生贡献，所以我们可以先BFS求个每个节点的父子关系，然后计算贡献即可，但是这样会漏掉一个贡献就是节点的兄弟节点也会对这个点产生贡献，所以我们还需要统计每个节点父亲的儿子个数，然后加上这个贡献即可，注意要-1,不包含自己。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
vector<int>G[maxn << 2];
int f[maxn],cnt[maxn],son[maxn];
bool vis[maxn];
void bfs(){
queue<int>st;
st.push(1);
vis[1] = true;
while(!st.empty()){
int u = st.front();st.pop();
for(int i = 0 ;i < G[u].size(); i++){
int v = G[u][i];
if(!vis[v]){
vis[v] = true;
f[v] = u;
st.push(v);
}
}
}
}
void solved(){
int n;cin>>n;
for(int i = 1; i < n; i++){
int u,v;cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
bfs();
for(int i = 1; i <= n ;i++){
cnt[f[f[i]]]++;
if(f[f[i]] > 0)cnt[i]++;
}
for(int i = 1; i <= n; i++){
son[f[i]]++;
}
for(int i = 1; i <= n ;i++){
cnt[i] += (son[f[i]] - 1);
}
for(int i = 1; i <= n ;i++){
cout<<cnt[i]<<endl;
}
}
int main(){
solved();
return 0;
} C:序列卷积之和
题意：
思路：这个题目老有意思了，差一点点就出了，可惜时间不够了唉。
我是先带入样例把这个式子展开，然后就做出来了，这个题目最核心的就是i对j的贡献计算，也就是i会乘以j多少次，我们把这个次数计算出来就行了。
就样例而言我们可以得到一个这样的矩形(我就不细展开公式了)：
ai,j表示a[i]需要乘上a[j]的次数可以认为是k * a[i] * a[j]，ai,j保存的就是系数k。
我们展开这个矩形可以得到
如果想到这里，我们可以O(n^2)写出这个题，但是O(n^2)是过不了的(***落泪)。
所以我们还要继续优化。
我们还可以从哪里优化呢？注意到，a1的所有项的系数都是公差为1的等差数列，a2的所有项都是系数为2的等差数列，a3都是系数为3的等差数列。。。。我们就可以从这里入手，看我怎么操作。
我们把每项的公差提出去，矩阵就变成一个比较好处理的样子了。
然后用系数*ai就行了，这里弄一个后缀数组搞一下就好了。嗯。。大概长这样。这样乘上了ai后的矩阵
可以用一个数组存一下提出去的公差最后答案就是公差 * 后缀和 * ai 的和。
求后缀和可以O(n)操作，这样可以不用O(n^2)，整体O(n)结束这个题。是个好题！！！
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long int ll;
ll mod = 1e9 + 7;
ll a[maxn],suf[maxn],v[maxn];
void solved(){
int n;cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i];v[i] = i;
}
suf[n] = a[n];
for(int i = n - 1,k = 2;i >= 1; i--,k++){
suf[i] = suf[i + 1] + a[i] * k % mod;
}
ll s = 0;
for(int i = 1; i <= n; i++){
s = s + (i * suf[i] % mod) * a[i] % mod;
}
cout<<s % mod<<endl;
}
int main(){
solved();
return 0;
} 
京公网安备 11010502036488号