hihoCoder Challenge 16题解

10
7

Problem A

考虑面积公式sqrt((a+b+c)(a+b-c)(b+c-a)(a+c-b))/4，如果固定了a和b+c，那么b和c越接近越好。

所以将三条边排序，首先增加第一条边到和第二条边一样长，然后一起增加前两条边到和第三条边一样长，然后三条边一起增加。

Problem B

首先d一定是所有数总和的约数，这样的数并不多。

接着判断一个d是否可能为k段和的约数，只要将前缀和按模d分类即可，看相同的个数是否大于等于k。

Problem C

一条边作为轻边的贡献为两边子树大小的乘积。

对于一个非叶节点会选择一条边作为重边，作为重儿子，也就是去掉贡献最大的轻边。这样就能贪心得到答案。

对于每个点的答案，在遍历过程中，根从一个点移动到相邻点，只会影响两个点的子树情况，简单维护一下即可。

Problem D

由群论知识的，选出的为Sn的一个子群。

当k=1时答案为1。

当k=2,3,5时，为质数阶的循环群。所以只要计算出生成元的个数，生成元一定为若干个p轮换组成。这可以用dp进行计算。

最后减去恒等置换，并且除掉自同构群大小，也就是p-1。

k=4是，为4阶循环群，或者克莱因四元群。

首先考虑4阶循环群，自同构群大小为2。生成元为对换和4轮换组成。最后减去恒等置换和由对换组成的轮换。

接着考虑四元群。即i,j,k满足i^2=j^2=k^2=1,ij=k,jk=i,ki=j。自同构群大小为6。

可以证明每个组成的部分为为(a b)(c d),(a c)(b d),(a d)(b c)，或者为(a b)这样一个对换。

令dp[i]表示i个元素的方案，如果为第一类，就是前i-1个元素中选3个元素再乘上6。如果是第二类，就是前i-i个元素中选1个元素乘上3，表示(a b)放在i,j或i,k或j,k两个置换中。

若i为恒等置换，那么有j=k，也就是减去若干个对换的方案数。同理减去j或k为恒等置换，和i,j,k都为恒等置换的方案。

9 answer(s)

0

include

include

include

include

include

include

include

include

include

include

include

using namespace std;

long long d[1200],a[2010]; int n,dn,k[1200];

void fac(long long x) { int m=sqrt(x)+0.5; dn=0; for(int i=1;i<=m;i++) if(x%i==0) d[dn++]=i; for(int i=dn-1;i>=0;i--) d[dn++]=x/d[i]; }

int findk(int idx) { long long r; int i,k=0; set q; for(i=0;i

int main() { // freopen("/home/user/桌面/in","r",stdin); while(scanf("%d",&n)==1) { scanf("%lld",&a[0]); for(int i=1;i=0;j--) if(k[j]>=i) { printf("%lld\n",d[j]); break; } } //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC); return 0; } 这B题代码为什么WA，求解释

0

我服

0

problem B: "接着判断一个d是否可能为k段和的约数，只要将前缀和按模d分类即可，看相同的个数是否大于等于k。"

谁可以帮助解释一下？不是很明白。

  • 主要是因為這是環形的.... 那麼當前綴和pre%d=k出現了m次時.... 就會像這樣子... a_1,a_2,a_3....,a_t | a_(t1+1),a_(t1+2).....,a_(t2) | a_(t3).... 共有m個分隔符號..... 可以知道除了第一段和最後一段都是d的倍數.... 而且第一段和最後一段加起來一定要是d的倍數....否則整段總和就不是d的倍數了... 所以把頭跟尾接起來.... 就是環形答案了....

  • 添加评论
  • ✖reply
0

我也是这样做的啊，提交了一直不对!

include

include

int main() { int n,a,b,c,l,A,B,C;//A>=B>=C double t,s; scanf("%d",&n); while(n--) {

    scanf("%d %d %d %d",&a,&b,&c,&l);

    t=a+b+c+l;
    if(a>b) {
        A=a;
        C=b;
        if(a>c) A=c;//max
        if(c<b) C=c;//min
    }
    else{
        A=b;
        C=a;
        if(b<c) A=c;//max
        if(c<a) C=c;//min
    }
    B=a+b+c-(A+C);//中间的那个数
    if(l<=(B-C))                 s=sqrt(t/2*(t/2-A)*(t/2-B)*(t/2-(C+l)));
    else if(l>(B-C)&&l<=(2*A-B-C)) s=sqrt(t/2*(t/2-A)*(t/2-(B+C+l)/2)*(t/2-(B+C+l)/2));
    else                         s=t*t/12/sqrt(3);
    printf("%.10lf\n",s);
}
return 0;

}

  • G++用%.10f吧

  • 还是不对，(┬＿┬)。大哥，你的代码能不能给我学习学习，我的邮箱是2541979212@qq.com。拜托啦

  • http://paste.ubuntu.com/13301882/

  • 添加评论
  • ✖reply
0

我服

1

我服

0

我服

0

我服

1

我服

write answer 切换为英文 切换为中文

转发分享

▲