[BZOJ 3835][Poi2014]Supercomputer
HauntedProgrammer
posted @ 2015年1月07日 21:00
in 未分类
, 1823 阅读
这饼图被我搞得太可怕了。
鸣谢xyz111提供主要想法。 orz xyz111
首先求出每一层有多少个节点。如果一层中的个数[tex]num[i] \leq k[/tex]，那么这一层可以直接一次运行完毕。如果[tex]num[i]>k[/tex]，那么就开始一段，直到这一段的平均数小于等于[tex]k[/tex]，对答案的贡献是[tex]\lceil\frac{sum}{k}\rceil[/tex]（sum是这一段的和）。证明Under Construction，好了以后会写上来的。
然后就是求出[tex]k=1 \rightarrow n[/tex]的答案。注意到对于一个[tex]k[/tex]，最多只有[tex]\frac{n}{k}[/tex]个段起始点，所有的段长度的和也最多只有[tex]\frac{n}{k}[/tex]，所以使用链表维护段起始点可以做到[tex]O(nlog(n))[/tex]的时间复杂度。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#define MAXN 1000010
int n,ki[MAXN],nums[MAXN],fa[MAXN],q,dep[MAXN],maxd=0,ans[MAXN];
std::vector<int> depn[MAXN];
int nex[MAXN],prv[MAXN],head=0;
inline void rm(int x){head=(head==x)?nex[x]:head,nex[prv[x]]=nex[x],prv[nex[x]]=prv[x];}
inline int ceildv(int x,int y){return x/y+(x%y!=0);}
int main()
{
scanf("%d%d",&n,&q);
for(int i=0;i<q;i++) scanf("%d",&ki[i]);
for(int i=2;i<=n;i++) scanf("%d",&fa[i]);
dep[1]=head=1;
for(int i=2;i<=n;i++) dep[i]=dep[fa[i]]+1,maxd=std::max(maxd,dep[i]);
for(int i=1;i<=n;i++) nums[dep[i]]++;
for(int i=1;i<=maxd;i++) depn[nums[i]].push_back(i);
for(int i=1;i<=maxd;i++) nex[i]=i+1,prv[i]=i-1;
for(int i=1;i<=n;i++)
{
for(int j=0,len=depn[i].size();j<len;j++) rm(depn[i][j]);
int cur=0,elaps=0,last=0,tot=0;
for(int j=head;j&&j<=maxd;j=nex[j]) if(j>last)
{
for(int k=j;k<=maxd;k++)
{
cur+=nums[k],elaps++;
if(cur<=elaps*i){ans[i]+=ceildv(cur,i),tot+=elaps,elaps=cur=0,last=k;break;}
}
if(elaps) ans[i]+=ceildv(cur,i),tot+=elaps,last=maxd;
}
ans[i]+=(maxd-tot);
}
printf("%d",ki[0]>n?maxd:ans[ki[0]]);
for(int i=1;i<q;i++) printf(" %d",ki[i]>n?maxd:ans[ki[i]]);
printf("\n");
return 0;
}
2021年9月01日 20:39
Almost all cleaning corporations work daily time and to obtain your household cleaned as long as you're at do the job, you need to be OK having permitting maids to enter your own home in ones absence. Only then it will be possible for you to have a clean house from long day's do the job. Hiring a dependable company that includes a strict getting approach and is particularly insured will reduce the risk connected with any sort and may make you sense more at ease.
2022年8月21日 06:34
Numerous courses are offered by this board, and it also administers tests to students in this state. Each year, thousands of students participate in these exams. Numerous students will take part in the class 11 examinations this year, and the Tripura Board 11th class Important Question Paper 2023 will be released as soon as it is ready. TBSE Plus One Previous Paper 2023 based on data from the prior year supplied by the Tripura Board of Higher Secondary, It has been discovered that six blind pupils and three prisoners both passed Tripura's higher secondary (+2) test. Numerous kids will take part in the class 11th examinations this year, which were also administered by this board, and they will wait afterward.
2023年11月19日 23:58
Although there are various finishing options inside the metal manufacture industry, powdered ingredients coating is actually relatively brand new. Prior for this technology, almost all metal had been painted - however it was discovered that paint didn't bond perfectly to steel fabricated products, and you can only put a lot paint on the product prior to it arrived at maximum width.
2023年11月20日 00:12
You will possibly not get gleaming results with only one cleaning period. Thus, repeat the actual window cleansing for 2 to 3 times before you get the required outcome. Or even, you can give the tension of cleansing services towards the professionals. Get window cleansing services through DIALAMAID with regard to effortless cleansing and clean windows.
2023年11月20日 00:19
If the business contains a soiled office would you buy from such firm? A clean up and perfect office declares your professionalism and yes it would help you to get success. A new cleaning, office won't only leaves a fantastic impression on the clients, the truth is, it impacts on the employers operate progress.
2024年1月30日 02:52
Here are a few factors that you should consider before buying a painting below wholesale supplier. First off you have got to take a thorough look about the room you'll hang this painting with. Take an in depth think about the color on the furniture, window curtains, wall paints, for example. Analyze consider some of the colors within the oil painting that may perfectly blend while using the interiors. This would assist you zero with on the best selection, whether it truly is your company or the house.