【比賽總結】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哈希