【比赛总结】2014 Multi-University Training Contest 9

话说多校都结束这么长时间了才写。。。主要是这场感觉有很多题都可搞啊，最后竟然奇迹般的四题~（感谢中山大学T^T）

于是下来把当时队友搞的，还有当时没搞出来但是下来发现挺容易的题目自己实现了一下，于是就拖到现在了。。。

但愿明年多校四题能成为常态吧~

下面放题解——

1002 Boring Sum

这题当时是学长过掉的，之后自己做竟然没有马上想出来，还好后来有思路了，又是一个开记录表的题目。

题意比较绕，大概就是给出数列a，要求统计出数列b和c，b[i] 是 a[i] 之前且离它最近的 a[i] 的倍数，如果不存在则 b[i] = a[i]；c[i] 是 a[i] 之后且离它最近的 a[i] 的倍数，如果不存在则 c[i] = a[i]。现在让求b[1]*c[1]+b[2]*c[2]+...+b[n]*c[n]的值。

反正是要先把b、c 两个数列求出来的。求b 数组的话直接暴力显然没戏，但由于数的大小是限定在10^5以内的，所以可以借助一个记录表vis[ a[i]的数据范围 ]，从左到右遍历过程中对每个a[i]都将所有 vis[ a[i]的约数 ] 更新为a[i] 的值，这样在遍历到后面的a[i] 时，就可以直接查询 vis[ a[i] ] 是否有值，如果有就一定是离他最近的他的倍数~这样就可以用比较低的复杂度统计出b，然后c 数列其实也是同理的，反过来刷一遍就行了~

话说数列查找这里面真的有好多神奇的算法呢O(∩_∩)O

代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef __int64 LL;
#define MAXN 100010

int a[MAXN];
int b[MAXN];
int c[MAXN];
int vis[MAXN];

int main()
{
    int n;
    while(1){
        scanf("%d",&n);
        if(!n) break;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);

        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; i++){
            if(vis[a[i]]) b[i] = a[vis[a[i]]];
            else b[i] = a[i];
            for(int j=1; j<=(int)sqrt(1.0*a[i])+1; j++){
                if(a[i]%j==0){
                    vis[j] = i;
                    vis[a[i]/j] = i;
                }
            }
        }

        memset(vis,0,sizeof(vis));
        for(int i=n; i>=1; i--){
            if(vis[a[i]]) c[i] = a[vis[a[i]]];
            else c[i] = a[i];
            for(int j=1; j<=(int)sqrt(1.0*a[i])+1; j++){
                if(a[i]%j==0){
                    vis[j] = i;
                    vis[a[i]/j] = i;
                }
            }
        }

        LL sum = 0;
        for(int i=1; i<=n; i++){
            sum += (LL)b[i] * c[i];
        }
        printf("%I64d\n",sum);
    }
    return 0;
}

1006 Fast Matrix Calculation

明显的矩阵快速幂嘛~就是不能不动脑子的乱搞，之前我们直接敲了一个然后光荣的TLE，之后崔神突然发现k的数据范围那么小，n那么大，然后顺理成章的发现对B*A做快速幂要比对A*B规模小好多，这个一听就是正解啊！！果然顺利AC~

不过这个题我之后敲的时候忘初始化了，白wrong好几次，我勒个去。。。

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

#define LL __int64
const int MOD = 6;
const int SIZE = 10;

struct Matrix {
    LL a[SIZE][SIZE];
    Matrix() {
        memset(a,0,sizeof(a));
    }
    void _union() {
        int l = SIZE;
        while(l--) a[l][l] = 1;
    }
    Matrix operator * (Matrix& B);
    Matrix pow(LL k);
};

//矩阵乘法
Matrix Matrix::operator * (Matrix& B) {
    Matrix ret;
    for(int i=0; i<SIZE; i++)
        for(int j=0; j<SIZE; j++)
            for(int k=0; k<SIZE; k++)
                ret.a[i][j] = (ret.a[i][j]+a[i][k]*B.a[k][j]) % MOD;
    return ret;
}
//矩阵乘方(快速幂)
Matrix Matrix::pow(LL k) {  //方阵才能乘方!
    Matrix ret;
    Matrix A = *this;
    ret._union();
    while(k) {
        if(k&1) ret = ret*A;
        A = A*A;
        k >>= 1;
    }
    return ret;
}

int A[1010][10], B[10][1010];
int tmp[1010][10];
int ans[1010][1010];

int main()
{
    //freopen("1006.in","r",stdin);
    int n, K;
    while(scanf("%d%d",&n,&K)!=EOF){
        if(!n) break;
        memset(A,0,sizeof A);
        memset(B,0,sizeof B);
        memset(tmp,0,sizeof tmp);
        memset(ans,0,sizeof ans);
        for(int i=0;i<n;i++){
            for(int j=0;j<K;j++) scanf("%d",&A[i][j]);
        }
        for(int i=0;i<K;i++){
            for(int j=0;j<n;j++) scanf("%d",&B[i][j]);
        }
        Matrix C;
        for(int i = 0; i < K; i++){ //A的行数
            for(int j = 0; j < n; j++){ //A的列数 == B的行数
                if(B[i][j]==0) continue;
                for(int k = 0; k < K; k++){ //B的列数
                    C.a[i][k] = (C.a[i][k] + B[i][j] * A[j][k]) % MOD;
                }
            }
        }
        C = C.pow(n*n-1);
        for(int i = 0; i < n; i++){ //A的行数
            for(int j = 0; j < K; j++){ //A的列数 == B的行数
                if(A[i][j]==0) continue;
                for(int k = 0; k < K; k++){ //B的列数
                    tmp[i][k] = (tmp[i][k] + A[i][j] * C.a[j][k]) % MOD;
                }
            }
        }
        for(int i = 0; i < n; i++){ //A的行数
            for(int j = 0; j < K; j++){ //A的列数 == B的行数
                if(tmp[i][j]==0) continue;
                for(int k = 0; k < n; k++){ //B的列数
                    ans[i][k] = (ans[i][k] + tmp[i][j] * B[j][k]) % MOD;
                }
            }
        }
        int sum = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) sum += ans[i][j];
        }
        cout<<sum<<endl;
    }
    return 0;
}

1009 Improve the GPA

这个属于思路很巧妙的题目，刚开始很是苦恼，后来学长突然发现可以换个思路枚举GPA的情况，然后进行合法性判断，于是轻松搞定。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int cse;
    int avg, n;
    cin>>cse;
    while(cse--){
        scanf("%d%d",&avg,&n);
        int s = avg * n;
        int a, b, c, d, e;
        double h = 0.0, l = 100.0;
        for(a=0;a<=n;a++){
            for(b=0;b<=n;b++){
                for(c=0;c<=n;c++){
                    for(d=0;d<=n;d++){
                        if(a+b+c+d>n) continue;
                        e = n - (a + b + c + d);
                        int smin = 85*a + 80*b + 75*c + 70*d + 60*e;
                        int smax = 100*a + 84*b + 79*c + 74*d + 69*e;
                        if(s >= smin && s <= smax){
                            double gpa = 4.0*a + 3.5*b + 3.0*c + 2.5*d + 2.0*e;
                            if(gpa < l) l = gpa;
                            if(gpa > h) h = gpa;
                        }
                    }
                }
            }
        }
        printf("%.4f %.4f\n",l/n,h/n);
    }
    return 0;
}

1010 Just a Joke

话说这是第一次在正式的比赛里遇到高数题呢→_→当时比赛时候因为过四题有点累了，就没有好好想这个，下来一想发现真是简单啊！！！

看来高数学会能拿奖学金也能A题啊~我是不是应该考虑回去刷一下高数的分呢。。。

题意挺好懂，核心就是对一个微分的方程求积分，公式推出来秒A，直接挂代码了——

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    double v1, v2, r, d;
    int cse;
    cin>>cse;
    while(cse--){
        scanf("%lf %lf %lf %lf",&v1,&v2,&r,&d);
        double dd = v2 * r * asin(v1/v2) / v1;
        if(dd > d) puts("Why give up treatment");
        else puts("Wake up to code");
    }
    return 0;
}

1011 Killing Monsters

本场比赛最大败笔，明明是大水题，但是当时我的思路卡了一下下，错误的认为直接刷一遍不可行，让队友搞线段树了，姿势不好TLE了大概5次吧。。。最后终于A了，后来想想真是人品好，这题小数据查询量应该很大，线段树超时很正常。。。从各个角度看都是一个水题啊，白白浪费了那么多时间，唉。。。

正解就是搞一个辅助数组t，初始化为0，如果某个塔的伤害半径为[l,r]，就让t[l]+=伤害值，t[r+1]-=伤害值，然后用一个变量从左往右扫一遍，到每一格 i 都加上t[i] 的值就行，因为题目只要求在某一格所有塔的叠加伤害，所以这样统计是可行的。统计出这个每格所受伤害值以后，反刷一遍即得从这一格到最右的总伤害值，然后O(1)判断即可。

话说这种水题已经做了不少了，还是有时失手，唉自己太水了。。。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 100010
#define LL __int64

int tmp[MAXN];
LL hurt[MAXN];

int main()
{
    int n, m, k;
    int l, r, d;
    int x;
    LL h;
    while(1){
        scanf("%d",&n);
        if(!n) break;

        memset(tmp,0,sizeof(tmp));

        scanf("%d",&m);
        while(m--){
            scanf("%d %d %d",&l,&r,&d);
            tmp[l] += d;
            tmp[r+1] -= d;
        }
        LL hit = 0; //最后一遍倒着加回来可以到10^13
        for(int i=1;i<=n+1;i++){
            hit += tmp[i];
            hurt[i] = hit;
        }
        hit = 0;
        for(int i=n;i>0;i--){
            hit += hurt[i];
            hurt[i] = hit;
        }
        int sum = 0;
        scanf("%d",&k);
        while(k--){
            scanf("%I64d %d",&h,&x);
            if(hurt[x]<h) sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}

于是今年多校就这么结束了，绝大多数都是一题，偶尔两题，总之是被完虐了，不知道明年再做的时候能不能有所突破呢？希望吧~

经过争取我们队也获得了打星上省赛的机会，能不能愉快的去区域赛一定程度上也看这次省赛的成绩了，希望能如愿！

【比赛总结】2014 Multi-University Training Contest 9

继续阅读

HDU Reorder the Books

POJ 1284 Primitive Roots (欧拉函数&原根定理)

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

hdu 4741 Save Labman No.004（计算几何） Save Labman No.004

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希