2019 jxcpc 部分题解和代码
Problem A. Cotree
题意：给你两棵树（两棵树的结点数为 
1、树中所有点到某个点的距离和中，到重心的距离和是最小的。
2、考虑给两颗树的重心连一条线，这样会使答案最小。
3、如何求树的重心？https://blog.csdn.net/qq_41608020/article/details/95201070
4、对整棵树从上向下dfs一次，当前节点到当前节点的某一儿子节点的边的贡献就是以儿子节点为根的树的节点个数。
5、递归自底向上依此求到每一个子树的大小和每一条边的使用次数。
Code：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
struct edge
{
int to;
int nex;
}e[MAXN * 2];
int head[MAXN], tot = 1;
void add(int a, int b)
{
e[tot] = edge{ b,head[a] };
head[a] = tot++;
}
int num[MAXN], dp[MAXN], n;
bool vis[MAXN];
void init()
{
memset(head, -1, sizeof(head));
tot = 1;
}
void dfs(int u, int fa, bool bol, int size)//求重心
{
num[u] = 1;
vis[u] = bol;
for (int i = head[u]; i + 1; i = e[i].nex)
{
int v = e[i].to;
if (v != fa)
{
dfs(v, u, bol, size);
dp[u] = max(dp[u], num[v]);
num[u] += num[v];
}
}
dp[u] = max(dp[u], size - num[u]);
}
ll ans = 0;
void dfs1(int u, int fa)//计算每条边使用的次数
{
num[u] = 1;
for (int i = head[u]; i + 1; i = e[i].nex)
{
int v = e[i].to;
if (v != fa)
{
dfs1(v, u);
num[u] += num[v];
ans += 1LL * (n - num[v]) * num[v];
}
}
}
int cnt(int u, int fa)
{
int num = 1;
for (int i = head[u]; i + 1; i = e[i].nex)
{
int v = e[i].to;
if (v != fa)
num += cnt(v, u);
}
return num;
}
int main()
{
init();
int a, b;
scanf("%d", &n);
for (int i = 2; i < n; i++)
{
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
dfs(1, 0, true, cnt(1, 0));
int res = n, zhong1 = 0;
for (int i = 1; i <= n; i++)
{
if (dp[i] < res && vis[i] == true)
{
res = dp[i];
zhong1 = i;
}
}
for (int i = 1; i <= n; i++)
{
if (vis[i] == false)
{
dfs(i, 0, false, cnt(i, 0));
break;
}
}
res = n;
int zhong2 = 0;
for (int i = 1; i <= n; i++)
{
if (dp[i] < res && vis[i] == false)
{
res = dp[i];
zhong2 = i;
}
}
add(zhong1, zhong2);
add(zhong2, zhong1);
memset(dp, 0, sizeof(dp));
dfs1(1, 0);
printf("%lld\n", ans);
} Problem BCE
留坑
Problem D. Wave
题意：给你一个长度为 n 的序列，保证里面所有的数字都大于等于1，小于等于c。
定义波浪数列如下，
1、长度不小于2
2、偶数位置的元素都是相等的。
3、奇数位置的元素都是相等的。
4、所有偶数位置上的元素都不等于奇数位置上的元素。
求最长的波浪数列。
1、记一下每个数字出现的位置和每一个位置出现数字次数的前缀。然后暴力取两个数字，求这两个数字能够成的最长波浪序列。
2、记得最后的答案如果是1的话，要变成0。
Code：
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int num[100005][105];
vector<int>v[105];
int main()
{
int n, c;
scanf("%d%d", &n, &c);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
for (int j = 1; j <= c; j++)
num[i][j] = num[i - 1][j];
num[i][a[i]]++;
v[a[i]].push_back(i);
}
int ans = 0;
for (int i = 1; i <= c; i++)
{
for (int j = i+1; j <= c; j++)
{
int res = 0;
if (v[i].empty())
continue;
int len = v[i].size();
for (int k = 1; k < len; k++)
{
if (num[v[i][k]][j] != num[v[i][k - 1]][j])
res += 2;
}
res++;
//head tail
if (num[v[i][0] - 1][j])
res++;
if (num[v[i][len - 1]][j] != num[n][j])
res++;
ans = max(ans, res);
}
}
if (ans == 1)
ans = 0;
printf("%d\n", ans);
} 另一种做法，考虑存下每种可能序列的最后一个元素和长度，这样可以在每次读入数字的时候判断是否可以更新。
Code：
#include <bits/stdc++.h>
#define ll long long
#define Pair pair<int,int>
using namespace std;
int a[100005];
Pair ans[105][105];// 一维 < 二维
int main()
{
int n, m;
int maxn = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
for (int j = 1; j < a[i]; j++)
{
if (ans[j][a[i]].second != a[i])
{
ans[j][a[i]].first++;
ans[j][a[i]].second = a[i];
maxn = max(maxn, ans[j][a[i]].first);
}
}
for (int j = a[i]; j <= m; j++)
{
if (ans[a[i]][j].second != a[i])
{
ans[a[i]][j].first++;
ans[a[i]][j].second = a[i];
maxn = max(maxn, ans[a[i]][j].first);
}
}
}
printf("%d\n", maxn);
} Problem F. String
题意：给你一个长度为 n 的只包含‘a’，‘v’，‘i’，‘n’字符串，任取四个字符，求他们是‘avin’的概率。
1、记录‘a’，‘v’，‘i’，‘n’的个数，相乘就是分子。
2、分母就是
Code：
#include <bits/stdc++.h>
using namespace std;
char s[105];
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int n;
scanf("%d",&n);
scanf("%s",s);
int a=0,b=0,c=0,d=0;
for (int i=0;i<n;i++)
{
if (s[i]=='a')
a++;
else if (s[i]=='v')
b++;
else if (s[i]=='i')
c++;
else if (s[i]=='n')
d++;
}
int q=a*b*c*d;
int w=n*n*n*n;
if (q==0)
printf("0/1\n");
else
{
int g=gcd(q,w);
printf("%d/%d\n",q/g,w/g);
}
} Problem G. Traffic
题意：在一个十字路口，有东西方向和南北方向的道路，东西方向有 n 辆车，已知他们到达的时间，南北方向有 m 辆车，已知他们到达的时间，在同一时间，东西方向和南北方向的车不能同时通过十字路口，为了不让他们相撞，现在让南北方向的车等待一个相同的时间，求这个时间的最小值。
1、说白了就是让南北方向的车等待一个相同的时间，等待之后，他们就不用再等待也不会发生车祸。求一个最小等待时间
Code：
#include <bits/stdc++.h>
using namespace std;
int a[2005],b[2005];
int main()
{
int n,m,t;
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++)
{
scanf("%d",&t);
a[t]=1;
}
for (int i=0;i<m;i++)
{
scanf("%d",&b[i]);
}
int ans=0;
for (;true;ans++)
{
for (int i=0;i<m;i++)
{
if (a[b[i]+ans]==1)
goto qwe;
}
break;
qwe:;
}
printf("%d\n",ans);
} Problem H. Rng
题意：给一个数字 n ，让你在区间 
暴力打表？然后看出规律
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll power(ll a,ll b)
{
ll res=1;
while (b)
{
if (b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main()
{
ll n;
scanf("%lld",&n);
ll a=n+1;
ll b=2*n;
ll ans=a*power(b,mod-2)%mod;
printf("%lld\n",ans);
} Problem I. Budget
题意：有一个公司需要升级系统，所以他们所有的三位小数要四舍五入为两位小数，求误差。
保证给出的数字是三位小数，给出的数字
1、不能直接double读，有精度误差，考虑字符串读入，或者读一个数字一个小数点再一个数字。
#include <bits/stdc++.h>
using namespace std;
char s[1005];
int main()
{
int n;
double ans=0;
scanf("%d",&n);
while (n--)
{
scanf("%s",s);
int t=s[strlen(s)-1]-'0';
if (t>=5)
ans+=10-t;
else
ans-=t;
}
printf("%.3f\n",ans/1000);
} Problem J. Worker
题意：有n个房子，m个工人，每个房子有一个数字 
1、求出所有房子的 
2、如果总人数是最小人数的倍数，就可行，否则不可行。
Code：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll m;
ll gcd(ll a, ll b)
{
return b==0?a:gcd(b,a%b);
}
ll a[1005];
int main()
{
scanf("%d%lld",&n,&m);
ll bei=1;
for (int i=0;i<n;i++)
{
scanf("%d",&a[i]);
int g=gcd(bei,a[i]);
bei=bei*a[i]/g;
}
ll cnt=0;
for (int i=0;i<n;i++)
cnt+=bei/a[i];
if (m%cnt!=0)
{
printf("No\n");
}
else
{
printf("Yes\n");
for (int i=0;i<n;i++)
{
printf("%lld%c",m/cnt*bei/a[i],i==n-1?'\n':' ');
}
}
} Problem K. Class
Code：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",(a+b)/2*(a-b)/2);
}
携程公司氛围 85人发布