今天的比赛比上一次而言,特点如下:

1,如果你AC了一题,你基本上会涨Rating

2,如果你challenge成功了4个人,或者300分的题拿了大概180分左右就能进前40了

===================================

上一次是这样

1,如果你AC了一题,你基本上会涨Rating

2,如果你challenge成功了5个人,或者400分的题拿了大概230分左右就能进前40了

然而问题是..这次我似乎拿了160分,Rank 47没晋级...

谈谈今天的题目吧

300

求有多少a,b,c满足1<=a<=A,1<=b<=B,1<=c<=C且a,b,c能构成个三角形(答案对[tex]10^9+7[/tex]取模)(a,b,c均为整数)

1<=A,B,C<=[tex]10^9[/tex]

大概这题的做法不是很难,但不算特别好想

实现不算难吧

我们这时候可以这么办

不妨设a<=b<=c

先算出a*b*c的值,然后容斥的减掉三种情况

1, a>=b+c

2, b>=a+c

3, c>=a+b

对于1情况,我们可以枚举a=1,2,3...n,可以发现方案数为:

0,1,1+3,1+3+6...

据说,它们的和就是[tex]\frac{(A-1)*A*(A+1)}{6}[/tex]

所以..情况1就解决了

然后接下来,我们看2和3的情况

因为这么算,a>A的时候就挂了

我们可以容斥啊!

再容斥一发不就行了么!

所以我们对于2号情况的方案,就是

[tex]\frac{(B-1)*B*(B+1)}{6}-\frac{(B-A-1)*(B-A)*(B-A+1)}{6}[tex]

同理,3号方案稍微复杂点,还要考虑一些别的东西..

不仅a>A的问题,还有b>B的问题,还有两者同时发生的问题

[tex]\frac{(C-1)*C*(C+1)}{6}-\frac{(C-A-1)*(C-A)*(C-A+1)}{6}-\frac{(C-B-1)*(C-B)*(C-B+1)}{6}+\frac{(C-A-B-1)*(C-A-B)*(C-A-B+1)}{6}[tex]

特别的,如果C<A+B,则我们定义最后一项是0

也就是..

[tex]\frac{(C-1)*C*(C+1)}{6}-\frac{(C-A-1)*(C-A)*(C-A+1)}{6}-\frac{(C-B-1)*(C-B)*(C-B+1)}{6}[tex]

真奇怪..自己是公式恐惧症竟然还推了一堆这些东西出来..

反正..代码如下就对了

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int modo=1000000007;
long long power(int x,int y)
{
    if (y==0) return 1ll;
    long long t=power(x,y/2);
    t=t*t%modo;
    if (y&1) t=(long long)t*x%modo;
    return t;
}
struct TriangleTriples
{
    int count(int a,int b,int c)
    {
        if (a>b) swap(a,b);
        if (a>c) swap(a,c);
        if (b>c) swap(b,c);
        long long ans=(long long)a*b%modo*c%modo;
        ans-=(long long)a*(a+1)%modo*(a-1)%modo*power(6,modo-2)%modo;
        ans-=(long long)b*(b+1)%modo*(b-1)%modo*power(6,modo-2)%modo;
        ans-=(long long)c*(c+1)%modo*(c-1)%modo*power(6,modo-2)%modo;
        ans+=(long long)(b-a-1)*(b-a)%modo*(b-a+1)%modo*power(6,modo-2)%modo;
        ans+=(long long)(c-a-1)*(c-a)%modo*(c-a+1)%modo*power(6,modo-2)%modo;
        ans+=(long long)(c-b-1)*(c-b)%modo*(c-b+1)%modo*power(6,modo-2)%modo;
        if (c>=a+b) ans-=(long long)(c-a-b-1)*(c-a-b)%modo*(c-a-b+1)%modo*power(6,modo-2)%modo;
        return (ans%modo+modo)%modo;
    }
};
#ifdef absi2011
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    
    return 0;
}
#endif

下面谈谈500

500分题大概是:

给你16种钻石,每种钻石的质量你不知道(但互不相同)

你现在有若干个包,每个包里有若干个钻石,一定是这16种中间的

对于任意相对质量顺序:

求是否都能找到重量最大的那个包(注意,是能不能找到而不是让你去找)

例如样例"AB""AC"

对于A>B>C或者B>A>C或者B>C>A的相对顺序,我们都可以抓"AB"

对于别的顺序,我们可以抓"AC"

重要的事情说三遍,问的是能不能

所以..

我不会做了..瞎搞了个算法很果断的爆炸了..不管了