前言：
自己考试的时候，又犯了低级错误，导致到手的 100 分直接丢了。哎，蓝瘦。
【问题描述】
每一个物品有 \(a_i,b_i,c_i\) 三种属性，在每一层有 \(n\) 种物品。每一种在 第 \(x\) 层的代价为 \(a_i \times x^2 + b_i \times x + c_i\)
每一层的代价总和为这 \(n\) 中物品的代价之和，问你 \(1-F\) 这些层中总代价最少的那一层是第几层。
考试的时候打了个三分，结果就得了 \(50\) 分的暴力分。
快考完了才发现这是个 \(SB\) 数学题，然后没时间写了，只能交了三分的解法。
关键是他 \(T\) 的范围很小，我当时怀疑这种 \(O(T)\) 的解法不对。
推一下柿子，我们要求的是：
\(a_1\times x^2 + b_1\times x + c_1 + a_2\times x^2 + b_2 \times x + c_2 \cdots a_n \times x^2 + b_n \times x + c_n\)
然后合并一下同类项可得：
\(\displaystyle\sum_{i=1}^{n} a_i \times x^2 \sum_{i=1}^{n} b_i \times x + \sum_{i=1}^{n} c_o\)
然后你就会发现他还是个二次函数，求一下这个函数的对称轴就可以。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e5+10;
int T,n,F,ans,id,a[N],b[N],c[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘){if(ch == ‘-‘) w = -1; ch = getchar();}
while(ch >= ‘0‘ && ch <= ‘9‘){s = s * 10 + ch - ‘0‘; ch = getchar();}
return s * w;
}
int calc(int x)
{
int res = 0;
return x * x * a[n] + x * b[n] + c[n];
}
signed main()
{
//freopen("shopping.in","r",stdin);
//freopen("shopping.out","w",stdout);
T = read();
while(T--)
{
n = read(); F = read(); ans = 0;
for(int i = 1; i <= n; i++)
{
a[i] = read(); b[i] = read(); c[i] = read();
}
for(int i = 1; i <= n; i++)
{
a[i] = a[i-1] + a[i];//前缀和
b[i] = b[i-1] + b[i];
c[i] = c[i-1] + c[i];
}
int ans = -1 * b[n] / (2 * a[n]);//二次函数对称轴
if(ans <= 0) ans = 1;//对称轴小于0，说明1是最小的
if(ans >= F) ans = F;//大于F的话,取 F 是最小的
else if(ans >= 1 && ans <= F)
{
int k = ans + 1;
if(calc(k) < calc(ans)) ans = k;//最后特判一下取 k 小还是 k+1 小
}
printf("%lld\n",ans);
}
fclose(stdin); fclose(stdout);
return 0;
}
给你一个 \(n\) 个点 \(m\) 条边的无向图，每个点有一个权值 \(a_i\) 满足 \(a_i \in [1-L]\) ，每次操作你都可以让相邻的两个点 \(a_u + 1, a_v-1\)
你可以进行任意多次操作，但最后要满足 \(a_i\in[1-L]\) ，问你最后 \(\displaystyle\sum_{i=1}^{n} i \times a_i\) 的值最大是多少。
一个贪心的想法就是尽可能的让 编号大的点的权值最大，并且每个联通块的答案是互不影响的。
我们只需要处理的就是每个联通块中的情况。
联通块里面的点因为是互相联通的，所以点权是可以互相转化的。
那我们可以对每个联通块开个 \(vector\) 存这个块里面的节点编号，然后从大到小排一遍序。
贪心的分配一下每个点的权值就行。
然后考场上犯了个 SB错误，这题直接炸了。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e5+10;
int n,m,L,u,v,top,num,cnt,tot;
int head[N],w[N],a[N];
vector<int> c[N];
bool vis[N];
long long ans;
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘){if(ch == ‘-‘) w = -1; ch = getchar();}
while(ch >= ‘0‘ && ch <= ‘9‘){s = s * 10 + ch - ‘0‘; ch = getchar();}
return s * w;
}
struct node
{
int to,net;
}e[400010];
void add(int x,int y)
{
e[++tot].to = y;
e[tot].net = head[x];
head[x] = tot;
}
void dfs(int x,int cnt)
{
vis[x] = 1; w[cnt] += a[x];
c[cnt].push_back(x);
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(vis[to]) continue;
dfs(to,cnt);
}
}
void slove(int x)
{
sort(c[x].begin(),c[x].end());//先按编号从大到小排一遍序
int t = c[x].size();
for(int i = t-1; i >= 0; i--)
{
int to = c[x][i];
a[to] = 1;//确保每个点的点权最小为1
}
w[x] -= t;
for(int i = t-1; i >= 0; i--)//从编号大的点先分配开始
{
int to = c[x][i];
a[to] += min(w[x],L-a[to]);
w[x] -= a[to] - 1;
if(w[x] <= 0) break;
}
}
int main()
{
freopen("pmlaw.in","r",stdin);
freopen("pmlaw.out","w",stdout);
n = read(); m = read(); L = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= m; i++)
{
u = read(); v = read();
add(u,v); add(v,u);
}
for(int i = 1; i <= n; i++)//dfs找联通块
{
if(!vis[i]) cnt++, dfs(i,cnt);
}
for(int i = 1; i <= cnt; i++) slove(i);//解决每个联通块的情况
for(int i = 1; i <= n; i++) ans += 1LL * a[i] * i;
printf("%lld\n",ans);
fclose(stdin); fclose(stdout);
return 0;
}
T3 是个神仙数学题，暂时还不会。
原文：https://www.cnblogs.com/genshy/p/13737129.html