第九届校赛总结

     本来不打算写总结的，想来博客已经很久没更新了，觉得还是来一发吧。

     赶脚这次比赛纯粹是运气好，基本上是沿着这样的模式：翻到一个题 → 嗯，有思路 → 敲一敲 → 提交 → 1A → 看下一道题 .... 所以噼里啪啦交了6道水题，所以中途没有卡在哪一道题上浪费时间，（除了E题第一次提交忘了开LL），幸运地最大化利用了时间，结果莫名其妙就2nd了.... (= =#

     （PS：话说刚开场敲A的时候，一激动碰到了键盘右边的关机键，然后电脑就注销了。。销了。。了。。然后找了帅气的taos学长，让他帮我重发一下login和ranklist，所以当我过A的时候已经17分钟过去了。。现在想想真是可怕。。）

      A题：签到题。

#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int sum = 0;int x;
        for(int i =0 ; i < n; ++i)
        scanf("%d", &x), sum += x;
        printf("%d
", sum);
            }
    return 0;
}

      B题：比较裸的Lucas，直接上结论：C(n,r)=(n!)*(r!)^(P-2)*(n-r)!^(P-2)%P，至于证明我说过由费马小定理可以得出a和a^(P-2)在模P运算下互为逆元，因此得证。

#include <stdio.h>
#include <string.h>
using namespace std;

typedef long long LL;
const LL P = 1000000007;
LL f[110000];

LL Pow(LL x, LL n)
{
    LL ans = 1LL;
    while(n)
    {
        if(n & 1)
        ans = ((ans % P) * (x % P)) % P;
        x = ((x % P) * (x % P)) % P;
        n >>= 1;
    }
    return ans;
}

LL c(LL n, LL r)
{
    return  (f[n] % P) * ((Pow(f[r], P - 2) % P) * (Pow(f[n-r], P - 2) % P) % P) % P;
}

int main()
{
    LL n;
    while(~scanf("%I64d", &n))
    {
    f[0] = 1LL;
    f[1] = 1LL;
        for(LL i = 2LL; i <= n; ++i)
        f[i] = (f[i-1] % P * i) % P;
                for(LL i = 0LL; i < n; ++i)
        printf("%I64d ", c(n, i));
        printf("1
");
//          LL m, r;
//         scanf("%I64d%I64d", &m, &r);
//         printf("%I64d
", c(m, r));
    }
    return 0;
}

      C题：留坑待填，据说用DP，又据说暴力可过，没看到题目说最多分解成4项，QwQ。

      D题：水题，把元素装进一个muiltiset里面，然后对于每个元素a，在其中查找s-a，然后对于s=2*a的情况特判一下即可。

#include <stdio.h>
#include <string.h>
#include <set>
using namespace std;

int a[110000];

int main()
{
    int t;
    while(~scanf("%d", &t))
    {
        while(t--)
        {
            multiset<int> ms;
            ms.clear();
            int n, s;
            scanf("%d", &n);
            for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]), ms.insert(a[i]);
            scanf("%d", &s);

            bool flag = 0;
            for(int i = 0; i < n; ++i)
            {
            //    printf("%d
", ms.count(s - a[i]));
            if(ms.count(s - a[i]) != 0)
            {
                if(s != 2 * a[i])
                {
                 flag = 1; break;
                }
                else
                {
                    if(ms.count(s - a[i]) >= 2)
                   {
                       flag = 1; break;
                   }
                }
            }

            }
//
//            multiset<int>::iterator it;
//            for(it = ms.begin(); it != ms.end(); ++it)
//            printf("%d ", *it);
//            puts("");

            if(flag) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

      E题：水题，本来封榜之后准备弃疗，然后看了下这个题，觉得好像可以搞一搞，然后发现是个大水题，2333....关键就是由∑((xi-xj)^2+(yi-yj)^2) 化为 (n-1)(∑xi^2+∑yi^2)+∑xi*(sn-si)+∑yi*(tn-yi)即可，（其中si=∑xi,ti=∑yi），复杂度由O(n^2)降为O(n)。

#include <stdio.h>
using namespace std;

typedef long long LL;
const int N = 110000;
LL a[N], b[N], sum1[N], sum2[N];

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        LL tep1 = 0, tep2 = 0;
        sum1[0] = 0, sum2[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
        scanf("%I64d%I64d", &a[i], &b[i]);
        tep1 += a[i] * a[i];
        tep2 += b[i] * b[i];
        sum1[i] = sum1[i-1] + a[i];
        sum2[i] = sum2[i-1] + b[i];
        }

        LL tep3 = (n - 1) * (tep1 + tep2);

        LL tep4 = 0, tep5 = 0;
         for(int i = 1; i < n; ++i)
          tep4 += a[i] * (sum1[n] - sum1[i]);
         for(int i = 1; i < n; ++i)
          tep5 += b[i] * (sum2[n] - sum2[i]);

          LL ans = tep3 - 2 * (tep4 + tep5);
            printf("%I64d
", ans);
    }
    return 0;
}

      F题：水过去的，用抛物线方程跟墙的方程联立，没啥可说的。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;

const double g = 9.8;
double a[11000];

struct Wall
{
    double x, y;
} w[110000], ans[11000];

bool cmpx(Wall a, Wall b)
{
    return a.x < b.x;
}

int main()
{
   // freopen("f.txt", "w", stdin);
    int n;
    double v;
    while(~scanf("%d%lf", &n, &v))
    {
        for(int i = 0; i < n; ++i)
            scanf("%lf", &a[i]);
        int m;
        scanf("%d", &m);
        for(int i = 0 ; i < m; ++i)
            scanf("%lf%lf", &w[i].x, &w[i].y);
        sort(w, w + m, cmpx);

        for(int i = 0; i < n; ++i)
        {
        double vx, vy, h, x0, d;
        vx = v * cos(a[i]);
        vy = v * sin(a[i]);
        h = vy * vy / (2.0 * g);
        x0 = v * v * sin(2.0 * a[i]) / g;
        d = 2.0 * vy * vy / (g * x0 * x0);
            bool flag = 0;
            for(int j = 0; j < m; ++j)
            {
                double yt = -d * w[j].x * (w[j].x - x0);
                if(0 <= yt && yt <= w[j].y)
                {
                    ans[i].x = w[j].x, ans[i].y = yt;
                    flag = 1;
                    break;
                }
            }
            if(!flag)
            ans[i].x = x0, ans[i].y = 0;
        }

        for(int i = 0; i < n; ++i)
       printf("%.6f %.6f
", ans[i].x,ans[i].y);
    }
    return 0;
}

      G题：留坑待填，据说用高斯消元。

      H题：简单的公式题，palapala一顿搞，结果就是ans=2*v*T^2/t，没啥可说的。

#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
    double T, v, t;
    while(~scanf("%lf%lf%lf", &T, &v, &t))
    {
        double ans = 2 * v * T * T / t;
        printf("%.5f
", ans);
    }
    return 0;
}

      I题：模拟题，嫌题目太啰嗦没看，留坑待填。

      J题：离散+博弈，居然有人过，orz....，留坑待填。

   以上。