Matrix
Time Limit: 10000MS Memory Limit: 131072KB 64bit IO Format: %lld & %llu
Submit

Status

Description
A NM coordinate plane ((0, 0)~(n, m)). Initially the value of all NM grids are 0.
An operation T(a, b, h, x, y) is defined as follow:

  1. Select the maximum value in the matrix (x, y) ~ (x+a, y+b), suppose the maximum value is max
  2. Change all the value in the matrix (x, y) ~ (x+a, y+b) into max+h
    After C operations, please output the maximum value in the whole N*M coordinate.

Input
The input consists of several cases.
For each case, the first line consists of three positive integers N , M and C (N ≤ 1000, M ≤ 1000, C ≤ 1000). In the following C lines, each line consists of 5 non-negative number, ai, bi, hi, xi, yi (0 ≤ hi ≤ 10000, 0 ≤ xi < n, 0 ≤ yi < m).

Output
For each case, output the maximum height.

Sample Input
3 2 2
2 1 9 1 1
1 1 2 2 1
Sample Output
11

二重循环,前i-1个,对第i个造成影响。

#include <cstdio>

const int C = 1010;

int a[C],b[C],h[C],x[C],y[C];

bool cross(int i,int j){
    int l1 = x[i];
    int l2 = x[j];
    int r1 = x[i]+a[i]-1;
    int r2 = x[j]+a[j]-1;
    int t1 = y[i];
    int t2 = y[j];
    int b1 = y[i]+b[i]-1;
    int b2 = y[j]+b[j]-1;
    return r1>=l2 && r2>=l1 && b1>=t2 && b2>=t1;
}

int main(){
    int n,m,c;
    while (~scanf("%d%d%d",&n,&m,&c)){
        for (int i=0;i<c;i++){
            scanf("%d%d%d%d%d",a+i,b+i,h+i,x+i,y+i);
            int max = h[i];
            for (int j=0;j<i;j++){
                if (cross(i,j) && h[j]+h[i] > max){
                    max = h[j] + h[i];
                }
            }
            h[i] = max;
        }
        int max = 0;
        for (int i=0;i<c;i++){
            max = max<h[i]?h[i]:max;
        }
        printf("%d\n",max);
    }

    return 0;
}

Mayor’s posters
Time Limit: 1000MS Memory Limit: 65536KB 64bit IO Format: %I64d & %I64u
Submit

Status

Description
The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:
Every candidate can place exactly one poster on the wall.
All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
The wall is divided into segments and the width of each segment is one byte.
Each poster must completely cover a contiguous number of wall segments.

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters’ size, their place and order of placement on the electoral wall.
Input
The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers l i and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= l i <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered l i, l i+1 ,… , ri.
Output
For each input data set print the number of visible posters after all the posters are placed.

The picture below illustrates the case of the sample input.

Sample Input
1
5
1 4
2 6
8 10
3 4
7 10
Sample Output
4
Source
Alberta Collegiate Programming Contest 2003.10.18


线段树模板题
由于1 <= l i <= ri <= 10000000条件的存在,导致建立线段树很困难。
然而1 <= n <= 10000,并且意识到两点之间的距离是无用的数据,因此进行离散化。
unique和sort是离散化的好帮手。

if (tree[i] != -1){
    tree[i<<1] = tree[(i<<1)+1] = tree[i];
}

线段树的lazy处理,一定不要忘了配对的向上传递和向下传递。
这样避免了父亲存储了儿子的数据,却把儿子的信息丢掉了的情况(即因为两个儿子数据的不一致而置位-1)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10300;

bool mark[N];
int hash[10000010];
int tree[N<<4];

struct Edge{
    int l,r;
}edge[N];

int point[N<<2];
int psum;

void change(int i,int l,int r,int ll,int rr,int c){
    int mid = ((l+r)>>1);

    if (l>=ll && r<=rr){
        tree[i] = c;
        return;
    }
    if (tree[i] != -1){
        tree[i<<1] = tree[(i<<1)+1] = tree[i];
    }

    if (rr <= mid){
        change(i<<1, l,mid, ll,rr,c);
    } else if (ll > mid) {
        change((i<<1)+1, mid+1,r, ll,rr,c);
    } else {
        change(i<<1, l,mid, ll,mid,c);
        change((i<<1)+1,mid+1,r,mid+1,rr,c);
    }
    if (tree[i<<1] == tree[(i<<1)+1] && tree[i<<1]!=-1){
        tree[i] = tree[i<<1];
    }else{
        tree[i] = -1;
    }
}

void find(int i,int l,int r){
    int mid = ((l+r)>>1);

    if (tree[i] != -1){
        mark[tree[i]] = true;
        return;
    }
    find(i<<1,l,mid);
    find((i<<1)+1,mid+1,r);
}

int main(){
    int c;
    scanf("%d",&c);
    while (c--){
        memset(mark,0,sizeof mark);
        memset(tree,0,sizeof tree);
        memset(hash,0,sizeof hash);
        psum = 0;
        int n;

        scanf("%d",&n);
        for (int i=0;i<n;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            point[psum++] = l;
            point[psum++] = r;
            edge[i].l = l;
            edge[i].r = r;
        }

        sort(point,point+psum);
        int npsum = unique(point,point+psum)-point;

        for (int i=0;i<npsum;i++){
            hash[point[i]] = i+1;
        }

        for (int i=0;i<n;i++){
            edge[i].l = hash[edge[i].l];
            edge[i].r = hash[edge[i].r];

            change(1,1,npsum,edge[i].l,edge[i].r,i+1);
        }

        find(1,1,npsum);

        int ans = 0;
        for (int i=1;i<n+1;i++)
            if (mark[i])
                ans ++;
        printf("%d\n",ans);
    }
    return 0;
}

ssh-keygen -t rsa
把id_rsa.pub粘贴到github里去
ssh -T git@github.com
提示id_rsa的others权限过高,于是改成600


mkdir blog 建立文件夹
cd blog/
echo “# wuyihao14.github.io” >> README.md 创建README
git init 初始化git
git remote add origin git@github.com:wuyihao14/wuyihao14.github.io.git 在github上添加repository,origin是默认的远程版本库名称

touch a 添加文件
git add a 添加到repository中
git commit -m “first commit” 提交更改
git push -u origin master 推送到github

hexo init 创建hexo博客
npm install 下载modules
hexo g 生成静态文件,因为github只支持静态,hexo d部署,只会提交.deploy文件夹,也就是只有静态文件,合并为hexo d -g。hexo s预览


这些在本博客中都用不上
git add -f 强制添加所有文件
git commit -m “Set up Blog”
git push -u origin master


git remote remove origin 有时候会提醒已存在origin
error:src refspec master does not match any 这个错误说明提交的空目录
[error] Deployer not found: null 因为没有配置deployer
修改_config.yml
deploy:
type: github
repository: https://github.com/wuyihao14/wuyihao14.github.io.git
branch: master
但是这样之后每次都要求输入密码,有什么办法?

Count the Length
Time Limit: 2000MS Memory Limit: 65536KB 64bit IO Format: %lld & %llu
Submit

Status

Description
You are given a board of mn, so there are mn unit squares(1*1) in the board. Suppose all unit squares are colored red or blue, and no adjacent(have common edge) unit squares share the same color. Consider the diagonal D of the board from left bottom to right top, D is a segment with color too, a point in D is red(or blue) if it falls in a red(or blue) unit square. Assume the left bottom square’s color is red, then what is the total length of red part of the diagonal D?

the sample of 2 * 4 board

the total length of red part of the diagonal is 2.236068
Input
There are multiple test cases(less than 10000). Each case is a line containing two integers m,n(1 ≤ m,n ≤ 2^31-1).

Output
For each case, output a single line containing the right answer(rounded up to 3 digits after the decimal point).

Sample Input
2 4
1 3
Sample Output
2.236
2.108

最大公约数

#include <cstdio>
#include <cmath>

int GCD(int a, int b)
{
    while(b != 0)
    {
        int r = b;
        b = a % b;
        a = r;
    }
    return a;
}


int main(){
    int m,n;
    while (~scanf("%d%d",&m,&n)){
        int gcd = GCD(m,n);
        m /= gcd;
        n /= gcd;
        double mm = m;
        double nn = n;
        double sum = mm*nn;
        double ans = sqrt(mm*mm + nn*nn) * (double)gcd;
        ans = ans*ceil(sum/2.0)/sum;
        printf("%.3lf\n",ans);
    }
    return 0;
}