今天这场vj出大问题，快速吃完午饭后回来抢水题一血结果发现根本提交不了（乐），直接回宿舍爆睡一小时回来仍然 submit failed直接开始补题，查了一下发现今天这场有一部分题面来自2019CCPC女生赛，也算是边缘鼠鼠ACMer初次体验ccpc了，不多废话，开始补题
A - Ticket
北京地铁票每月的打折规则为：本次乘车前总消费不足 100 元本次不打折，满 100 元不足 150 元本次打8 折，满 150 元不足 400 元本次打 5 折，已满 400 元后本次不打折，已知 wls 每次出行的原票价，请问实际的花费是多少?
Input
输入包含两行。第一行一个整数 n 代表 wls 将要出行的次数。第二行 n 个正整数, ai 代表每次出行的票的原价，wls 是按照输入顺序依次出行的。0 ≤ n ≤ 1000 ，0<ai≤ 1000
Output
一行一个数，代表实际的花费，保留小数点后两位小数。
input
3
100 20 20
output
132.00
水题秒切
code：
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int n;
while(scanf("%d",&n)!=EOF){
int x;
double sum = 0;
for(int i = 0; i < n; i ++){
scanf("%d",&x);
if(sum < 100){
sum += x;
}
else if(sum >= 100 && sum < 150){
sum += (x * 0.8);
}
else if(sum >= 150 && sum < 400){
sum += (x * 0.5);
}
else sum +=x;
}
printf("%.2lf\n",sum);
}
return 0;
}
B - Gcd
wls 有一个整数 n，他想将 1 n 这 n 个数字分成两组，每一组至少有一个数，并且使得两组数字的和的最大公约数最大，请输出最大的最大公约数。
输入一行一个整数 n
2 ≤ n ≤ 1, 000, 000, 000
sum = s1+s2;
ans = gcd(s1,s2)；
gcd(s,s1)gcd(s,s2)gcd(s1,s2);
#include<iostream>
using namespace std;
#define int long long
int n;
signed main()
{
cin>>n;
if(n==2)cout<<-1<<endl;
else
{
int ans=1;
int sum=n*(n+1)/2;
for(int i=2;i<sum;i++)
{
if(sum%i==0)
{
ans=sum/i;
break;
}
}
cout<<ans<<endl;
}
return 0;
}
C - Function
wls 有 n 个二次函数
F_i(x) = a_i * x^2 + b_i * x + c_i (1 ≤ i ≤ n).
现在他想在 ∑(i=1 to n) x_i = m 且 x 为正整数的条件下求 ∑(i=1 to n) F_i(x_i) 的最小值。
请求出这最小值。
Input
第一两个正整数 n, m。
下面 n 行，每行三个整数 a, b, c 分别代表二次函数的二次项，一次项，常数项数。
1 ≤ n ≤ m ≤ 100,000
1 ≤ a ≤ 1,
-1,000 ≤ b, c ≤ 1,
Output
一行一个整表示答案。
input
2 3
1 1 1
2 2 2
output
13
题意：有n个二次函数，给每个函数选择一个值x，让所选的x的和正好等于m,问此时f(x)的最小值是多少
思路：
为了满足取得最小值的要求，我们先假设所有函数就选择 -b/2a 的最小值点，然后观察这样选择后是比m大还是小，如果小我们就让所选的 pos 增加是必然的答案也会增加，所以我们需要选择n个函数里增幅最小的那个，用优先队列来进行维护
优化：
注意到所选的x必须是正整数，所以我们就全将其初始化为1，这样我们就只需要选择维护增加的部分，减小的部分就不用维护了
具体操作：
若n==m则就是让所有的x=1，结束直接计算出来得到总值即可
若n<m 由下可知
x=1 f=a+b+c;
差值：3a+b
x=2 f=4a+2b+c;
差值：5a+b
x=3 f=9a+3b+c;
差值：7a+b
x=4 f=16a+4b+c;
差值：9a+b
x=5 f=25a+4b+c;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
struct p
{
int a,b,c,x;
int ans;
bool operator<(const p &x)const
{
if(ans==x.ans)return a>x.a;
return ans>x.ans;
}
}t;
priority_queue<p> q;
signed main()
{
int n,m;
int sum=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
t.x=1;
cin>>t.a>>t.b>>t.c;
sum+=t.a+t.b+t.c;
t.ans=(2*t.x+1)*t.a+t.b;
q.push(t);
}
m-=n;
while(m--)
{
t=q.top();
q.pop();
t.x++;
sum+=t.ans;
t.ans=(2*t.x+1)*t.a+t.b;
q.push(t);
}
cout<<sum<<endl;
return 0;
}
D - Tree
wls 有三棵树，树上每个节点都有一个值 ai，现在有 2 种操作：
- 将一条链上的所有节点的值开根号向下取整；
- 求一条链上值的和；
链的定义是两点之间的最短路。
Input
第一行两个数 n, q 分别代表树上点的数量和操作数量。
第二行 n 个整数，第 i 个数代表第 i 个点的值 ai接下来 n −−11 行， 每行两个整数 u, v 代表 u，v 之间有一条边。数据保证点两两联通。接下来 q 行，每行有个整数 op, u, v,op = 0 表示将 u,
v这条链上所有的点的值开根号向下取整，
op = 1表示询问
u，
v 这条链上的值的和。
1 ≤ n, q ≤ 100, 000
0 ≤ ai≤ 1, 000, 000, 000
Output
对于每一组 op = 2 的询问，输出一行一个值表示答案。
(树链剖分+线段树)
这个知识点还不是很会，过两天在补吧 QAQ~~
E - Checkout
Alice 是一个身怀改变世界的抱负的著名企业家，手中掌控很多著名的公司，为了更好的管理， Alice 建立了一套很完善的架构体系，已知 Alice 的企业的架构体系是一棵树，每个节点代表一个人。对于每个节点，它的父节点就是这个人的直接 leader，每个节点都有一个权值，代表这个人的爱好，每对属于同 一直接 leader 的节点如果有相同的爱好那么他们就会给公司产生1的和谐度，如果一个人和他/她的直接 leader 的爱好相同也会给公司产生1的和谐度，但是再完美的公司都会产生离职的情况，如果一个人离职，并且这个人有直接下属，就从这个人的直接下属中选一个成为这个部门新的leader，使得新的组织架构的和谐度最高，新晋的人汇报给离职的人的 leader（如果存在的话），同时新 leader 的原来下属的直接 leader 不变，Alice 想知道如果某个人离职整个公司的和谐度是多少。
Input
第一行两个正整数 n, m 分别代表公司的总人数和爱好的种数。第二行有 n 个整数，第 i 个数 a i，代表第 i 个人的爱好。后面 n −− 1 行每行两个数u，v代表 u，v 存在上下属关系（上下级关系不确定）。假设树根为 1，即 1 号员工是公司的ceo，他/她不需要汇报给任何人。1 ≤ m ≤ n ≤ 100, 000,1 ≤ a i≤ m
Output
输出一行n个数，第i个数代表如果编号为 i 的人离职，公司的和谐度会是多少，以空格分隔，行末无空格。
一个挺复杂的图论代码过两天再看吧，好难QAQ~
#include<iostream>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
map<int, int> mp[maxn]; //mp[u][v] 记录的是u结点属性为v的儿子的结点数
int a[maxn], fa[maxn]; //记录属性和父节点
vector<int> e[maxn];
int n, m, sum = 0;
int ans[maxn];
void dfs1(int u, int f) //记录父节点和和谐度
{
fa[u] = f;
for(auto v : e[u])
{
if(v == f)
continue;
dfs1(v, u); //向下递归
if(a[u] == a[v]) //统计父子相等
sum++;
sum += mp[u][a[v]]; //统计儿子间
mp[u][a[v]]++;
}
}
void dfs2(int u) //u是父亲，v是儿子(新父亲), i是孙子(新儿子)
{
if(u == 1) //根节点
{
for(auto v : e[u]) //枚举哪个儿子当根
{
if(v == fa[u])
continue;
int tmp = sum - mp[u][a[u]]; //减去u离职对儿子的影响
for(auto i : e[v]) //枚举新根的儿子间影响
{
if(i == fa[v])
continue;
//v的儿子与u的儿子间的影响
int x = mp[u][a[i]];
if(a[v] == a[i])
tmp += ((mp[u][a[i]] - 1) > 0 ? (mp[u][a[i]] - 1):0);
else
tmp += mp[u][a[i]];
}
ans[u] = max(ans[u], tmp);
}
}
else if(e[u].size() == 1) //叶子结点
{
ans[u] = sum - ((mp[fa[u]][a[u]] - 1) > 0 ? (mp[fa[u]][a[u]] - 1):0); //只考虑对兄弟的影响
if(a[u] == a[fa[u]]) //考虑对父亲的影响
ans[u]--;
}
else
{
for(auto v : e[u]) //枚举谁当父亲
{
if(v == fa[u])
continue;
int tmp = sum - mp[u][a[u]]; //减去u离职对儿子的影响
// 考虑u离职对父亲和兄弟的影响
tmp = tmp - ((mp[fa[u]][a[u]] - 1) > 0 ? (mp[fa[u]][a[u]] - 1):0);
if(a[u] == a[fa[u]]) //考虑对父亲的影响
tmp--;
if(a[fa[u]] == a[v]) //u的父节点与u的儿子属性相同时
tmp++;
if(a[u] == a[v]) //u的儿子与u的兄弟间关系
tmp += mp[fa[u]][a[v]] - 1;
else
tmp += mp[fa[u]][a[v]];
for(auto i : e[v]) //枚举新父亲的儿子间关系
{
if(i == fa[v])
continue;
int x = mp[u][a[i]];
//v的儿子与u的儿子间的影响
if(a[v] == a[i]) //父子相等时父亲的父亲要减一，想想为什么
tmp += ((mp[u][a[i]] - 1) > 0 ? (mp[u][a[i]] - 1):0);
else
tmp += mp[u][a[i]];
}
ans[u] = max(ans[u], tmp);
}
}
if(u < n)
dfs2(u + 1); //开始搞下一个点
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for(int i = 1; i <= n - 1; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1, 0);
//cout << sum << endl;
dfs2(1); //开始枚举
for(int i = 1; i < n; ++i)
printf("%d ", ans[i]);
printf("%d\n", ans[n]);
return 0;
}