第一次在牛客写题解，蒟蒻，有待大佬指正。
A 怪盗-1412
题目描述
一个长度为n+m+k包含n个数字1，m个数字2和k个数字4的数组，最多可能有多少个子序列1412？
如果一个序列是数组的子序列，当且仅当这个序列可以由数组删去任意个元素，再将数组中的剩余元素按顺序排列而成。
输入描述
第一行一个整数t，表示测试用例的组数。
接下来t行每行三个整数n,m,k表示一组测试用例。
输出描述
对于每组测试用例输出一行一个整数表示答案。
示例1
输入
3
6 7 8
1 2 2
6 0 3
输出
504
0
0
备注
{1<=t<=200000}1<=t<=200000
{0<=n,m,k<=10000}0<=n,m,k<=10000
解法
思考
本题求子序列，顺序不能变。既然要得到更多的‘1412’，那么2就尽量在最后面，前面能有几个‘141’（假设是a），并且最后面有b个‘2’，那么最终就有ab个结果。
所以问题就转换为求最多能组合出多少个‘141’（假设是a个）。
先把所有1放在这里：111111···11 ，再把4插入到1中间。
（图片链接： https://uploadfiles.nowcoder.com/images/20200522/617345919_1590159032352_67747B83CBF494375B673B06A4BA5C42 ）
所有最终答案就是a*b，即为n1/2(n1-n1/2)n4n2 。
保险起见，全部开long long。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long N;
cin>>N;
while(N--)
{
long long a,b,c;
cin>>a>>b>>c;
long long d=a>>1;
cout<<d*(a-d)*b*c<<endl;
}
return 0;
}B Dis2
题目描述
给出一颗n个点n−1条边的树，点的编号为1,2,...,n−1,n，对于每个点i(1<=i<=n)，输出与点i距离为2的点的个数。
两个点的距离定义为两个点最短路径上的边的条数。
输入描述
第一行一个正整数n。
接下来n−1行每行两个正整数ui ,vi表示点ui ,vi之间有一条边。
输出描述
输入共n行，第i行输出一个整数表示与点i距离为2的点的个数。
示例1
输入
4
1 2
2 3
3 4
输出
1
1
1
1
说明
点1,3的距离为2，点2,4的距离为2。
备注
1<=ui,vi<=n<=200000
解法
思考
n个点，n-1条连线的树，没有环。到一个点a距离为2的点的个数，就是与a相邻的所有点直接相连的点的个数减一。举例如下：（图片链接https://uploadfiles.nowcoder.com/images/20200522/617345919_1590159841443_568001D9EB97F2B157D06DF96FEB0648 ）
如图，设与3距离为3的点的个数为s（初值s=0），与3相邻的点有2,5,6，
对于2：与2相邻的点（除3外）有1，所以s=s+1(s=1);
对于5：与5相邻的点（除3外）没有了;
对于6：与6相邻的点（除3外）有7，所以s=s+1(s=2);
所以3对应的答案就是2.
对于每一个点，我们只需要求出这个点相邻点的相邻个数减一的和，就能求出这个点距离为2的点的个数。
代码
#include<bits/stdc++.h>
using namespace std;
int a[200010]={0};//a[i]:与i相连的有几个
map<int,vector<int> >b;//b[i]:记录点i直接相邻的点有哪些
int main()
{
int N,n;
cin>>N;
n=N;
while(--N)
{
int x,y;
scanf("%d%d",&x,&y);
a[x]++,a[y]++;//与x相邻的点多一个y,与y相邻的点多一个x
b[x].push_back(y);//与x相邻的点多一个y
b[y].push_back(x);//与y相邻的点多一个x
}
for(int i=1;i<=n;i++)
{
int s=0;//对于每一个点，s从0算起
for(vector<int>::iterator it=b[i].begin();it!=b[i].end();it++)//历遍多有与i相邻的点
{
s+=a[*it]-1;//s+=这个与i相邻的点又有几个相邻的点（-1是因为出去i本身）
}
printf("%d\n",s);
}
return 0;
}如有错误与不足，欢迎大佬指正。
京公网安备 11010502036488号