NOJ2019个人专题赛第一场题解

A - CF651B Beautiful Paintings

1000ms 262144K

Description:

There are $n$ pictures delivered for the new exhibition. The $i$-th painting has beauty $a_i$. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of $a$ in any order. What is the maximum possible number of indices $i$ (1 ≤ $i$ ≤ $n$ - 1), such that $a_{i+1}$ > $a_i$.

Input:

The first line of the input contains integer $n$ (1 ≤ $n$ ≤ 1000) — the number of painting.

The second line contains the sequence $a_1$, $a_2$, ..., $a_n$ (1 ≤ $a_i$ ≤ 1000), where $a_i$ means the beauty of the $i$-th painting.

Output:

Print one integer — the maximum possible number of neighbouring pairs, such that $a_{i+1}$ > $a_i$, after the optimal rearrangement.

Sample Input:

520 30 10 50 40

Sample Output:

4

Sample Input:

4200 100 100 200

Sample Output:

2

Note:

In the first sample, the optimal order is: 10, 20, 30, 40, 50.

In the second sample, the optimal order is: 100, 200, 100, 200.

分析:

题目大意是说将一个数组排序,使得$a_{i+1}$ > $a_i$的次数最多。

规律是用总长度减去出现单一值的最多出现次数。

题解:

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int a[1005];
int main(void) {
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        int x;
        scanf("%d", &x);
        a[x]++;
    }
    printf("%d\n", n - *max_element(a, a+1001));
    return 0;
}

B - CF758A Holiday Of Equality

1000ms 262144K

Description:

In Berland it is the holiday of equality. In honor of the holiday the king decided to equalize the welfare of all citizens in Berland by the expense of the state treasury.

Totally in Berland there are $n$ citizens, the welfare of each of them is estimated as the integer in $a_i$ burles (burle is the currency in Berland).

You are the royal treasurer, which needs to count the minimum charges of the kingdom on the king's present. The king can only give money, he hasn't a power to take away them.

Input:

The first line contains the integer $n$ (1 ≤ $n$ ≤ 100) — the number of citizens in the kingdom.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$, where $a_i$ (0 ≤ $a_i$ ≤ 106) — the welfare of the $i$-th citizen.

Output:

In the only line print the integer $S$ — the minimum number of burles which are had to spend.

Sample Input:

50 1 2 3 4

Sample Output:

10

Sample Input:

51 1 0 1 1

Sample Output:

1

Sample Input:

31 3 1

Sample Output:

4

Sample Input:

112

Sample Output:

0

Note:

In the first example if we add to the first citizen 4 burles, to the second 3, to the third 2 and to the fourth 1, then the welfare of all citizens will equal 4.

In the second example it is enough to give one burle to the third citizen.

In the third example it is necessary to give two burles to the first and the third citizens to make the welfare of citizens equal 3.

In the fourth example it is possible to give nothing to everyone because all citizens have 12 burles.

分析:

给定一个数组,通过扩大某些数的大小使得数组每个数都相等。

只需求出最大值,减去每个数然后求和即可。

题解:

#include<iostream>
using namespace std;
int m,s,n,a;
int main()
{
    cin>>n;
    for(int x=1;x<=n;x++)cin>>a,m=max(m,a),s+=a;
    cout<<n*m-s;
    return 0;
}

C - CF935A Fafa and his Company

1000ms 262144K

Description:

Fafa owns a company that works on huge projects. There are $n$ employees in Fafa's company. Whenever the company has a new project to start working on, Fafa has to divide the tasks of this project among all the employees.

Fafa finds doing this every time is very tiring for him. So, he decided to choose the best $l$ employees in his company as team leaders. Whenever there is a new project, Fafa will divide the tasks among only the team leaders and each team leader will be responsible of some positive number of employees to give them the tasks. To make this process fair for the team leaders, each one of them should be responsible for the same number of employees. Moreover, every employee, who is not a team leader, has to be under the responsibility of exactly one team leader, and no team leader is responsible for another team leader.

Given the number of employees $n$, find in how many ways Fafa could choose the number of team leaders $l$ in such a way that it is possible to divide employees between them evenly.

Input:

The input consists of a single line containing a positive integer $n$ (2 ≤ $n$ ≤ 105) — the number of employees in Fafa's company.

Output:

Print a single integer representing the answer to the problem.

Sample Input:

2

Sample Output:

1

Sample Input:

10

Sample Output:

3

Note:

In the second sample Fafa has 3 ways:

  • choose only 1 employee as a team leader with 9 employees under his responsibility.
  • choose 2 employees as team leaders with 4 employees under the responsibility of each of them.
  • choose 5 employees as team leaders with 1 employee under the responsibility of each of them.

分析:

暴力判断总员工数能不能被老大数整除即可。

题解:

#include<cstdio>
using namespace std;
int main(){
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        if(n%i==0) ans++;
    }
    printf("%d",ans);
    return 0;
}

D - POJ1835 宇航员

2000ms 30000K

Description:

问题描述:

  宇航员在太空中迷失了方向,在他的起始位置现在建立一个虚拟xyz坐标系,称为绝对坐标系,宇航员正面的方向为x轴正方向,头顶方向为z轴正方向,则宇航员的初始状态如下图所示:

img

现对六个方向分别标号,x,y,z正方向分别为0,1,2,负方向分别为3,4,5;称它们为绝对方向。宇航员在宇宙中只沿着与绝对坐标系xyz轴平行的方向行走,但是他不知道自己当前绝对坐标和自己面向的绝对方向。

任务描述:

  请根据宇航员对自己在相对方向上移动的描述确定宇航员最终的绝对坐标和面向的绝对方向。对在相对方向上移动的描述及意义如下:

forward x  向前走x米。

back x 先转向后,再走x米。

left x 先转向左,再走x米。

right x 先转向右,再走x米。

up x 先面向上,再走x米。

down x 先面向下,再走x米。

其中向上和向下如下图所示:

img

Input:

第一行一个正整数m,表示测试数据的组数。每组测试数据第一行是一个正整数n(1<=n<=10000)表示宇航员行走的次数,下面n行每行输入一次相对行走,格式如上所述,其中( 1 <= x <= 10000 为正整数)。

Output:

对于每组输入数据输出一行,x y z p, 中间用空格隔开,x y z是宇航员的位置的绝对坐标,p是宇航员面向的绝对方向编号(0<=p <=5)。

Sample Input:

1
6
left 10
right 11
up 12
down 13
forward 14
back 15

Sample Output:

23 -10 12 3

分析:

这一题出的还是蛮巧妙的。训练的时候估算了一下,大概是几百行的代码量,就没有动手去写。

实际上只需要二十几行就可以完成,先确定宇航员的方向,然后再确定宇航员走的步数即可。

题解:

#include<cstdio>
char s[10];
int main(){
    int t, n;
    int x, y, z, face, left, head, temp, move;
    scanf("%d", &t);
    while (t--){
        scanf("%d", &n);
        x = y = z = 0;
        face = 0, left = 4, head = 2;
        while (n--){
            scanf("%s %d", s, &move);
            if (s[0] == 'b')  face = (face + 3) % 6, left = (left + 3) % 6;
            else if (s[0] == 'l')  temp = face, face = left, left = (temp + 3) % 6;
            else if (s[0] == 'r')  temp = left, left = face, face = (temp + 3) % 6;
            else if (s[0] == 'u')  temp = face, face = head, head = (temp + 3) % 6;
            else if (s[0] == 'd')  temp = head, head = face, face = (temp + 3) % 6;
            if (face == 0)  x += move;
            else if (face == 1)  y += move;
            else if (face == 2)  z += move;
            else if (face == 3)  x -= move;
            else if (face == 4)  y -= move;
            else  z -= move;
        }
        printf("%d %d %d %d\n", x, y, z, face);
    }
    return 0;
}

E - CF1060A Phone Numbers

2000ms 524288K

Description:

Let's call a string a phone number if it has length 11 and fits the pattern "8xxxxxxxxxx", where each "x" is replaced by a digit.

For example, "80123456789" and "80000000000" are phone numbers, while "8012345678" and "79000000000" are not.

You have nn cards with digits, and you want to use them to make as many phone numbers as possible. Each card must be used in at most one phone number, and you don't have to use all cards. The phone numbers do not necessarily have to be distinct.

Input:

The first line contains an integer nn — the number of cards with digits that you have (1≤n≤1001≤n≤100).

The second line contains a string of nn digits (characters "0", "1", ..., "9") s1,s2,…,sns1,s2,…,sn. The string will not contain any other characters, such as leading or trailing spaces.

Output:

If at least one phone number can be made from these cards, output the maximum number of phone numbers that can be made. Otherwise, output 0.

Sample Input:

1100000000008

Sample Output:

1

Sample Input:

220011223344556677889988

Sample Output:

2

Sample Input:

1131415926535

Sample Output:

0

Note:

In the first example, one phone number, "8000000000", can be made from these cards.

In the second example, you can make two phone numbers from the cards, for example, "80123456789" and "80123456789".

In the third example you can't make any phone number from the given cards.

分析:

给定一些数字,问最多能生成多少个电话号码。电话号码要满足以8开头、11位数两个特征。

只需要输出8的个数和总数字数量除以11中小的那个即可。

题解:

#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    int count=0;
    int t;
    char temp;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> temp;
        if(temp=='8'){
            count++;
        }
    }
    int tmp = t / 11;
    if(tmp > count){
        printf("%d", count);
    }else{
        printf("%d", tmp);
    }
    return 0;
}

F - CF1057B DDoS

2000ms 262144K

Description:

We get more and more news about DDoS-attacks of popular websites.

Arseny is an admin and he thinks that a website is under a DDoS-attack if the total number of requests for a some period of time exceeds 100⋅t100⋅t, where tt — the number of seconds in this time segment.

Arseny knows statistics on the number of requests per second since the server is booted. He knows the sequence r1,r2,…,rnr1,r2,…,rn, where riri — the number of requests in the ii-th second after boot.

Determine the length of the longest continuous period of time, which Arseny considers to be a DDoS-attack. A seeking time period should not go beyond the boundaries of the segment [1,n][1,n].

Input:

The first line contains nn (1≤n≤50001≤n≤5000) — number of seconds since server has been booted. The second line contains sequence of integers r1,r2,…,rnr1,r2,…,rn (0≤ri≤50000≤ri≤5000), riri — number of requests in the ii-th second.

Output:

Print the only integer number — the length of the longest time period which is considered to be a DDoS-attack by Arseny. If it doesn't exist print 0.

Sample Input:

5100 200 1 1 1

Sample Output:

3

Sample Input:

51 2 3 4 5

Sample Output:

0

Sample Input:

2101 99

Sample Output:

1

分析:

考的是前缀和。

题解:

#include<iostream>
using namespace std;
int n,maxnn=0,maxmm=0;
int a[5050],s[5050];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;cin>>t;
        a[i]=t;
        s[i]=s[i-1]+t;
    }
    for(int i=n;i>=1;i--){
        for(int j=0;j<i;j++){
            if((s[i]-s[j])>(100*(i-j))&&i-j>maxnn){
                maxnn=i-j;
                break;
            }
        }
    }
    cout<<maxnn<<endl;
    return 0;
}

G - CF908A New Year and Counting Cards

1000ms 262144K

Description:

Your friend has $n$ cards.

You know that each card has a lowercase English letter on one side and a digit on the other.

Currently, your friend has laid out the cards on a table so only one side of each card is visible.

You would like to know if the following statement is true for cards that your friend owns: "If a card has a vowel on one side, then it has an even digit on the other side." More specifically, a vowel is one of 'a', 'e', 'i', 'o' or 'u', and even digit is one of '0', '2', '4', '6' or '8'.

For example, if a card has 'a' on one side, and '6' on the other side, then this statement is true for it. Also, the statement is true, for example, for a card with 'b' and '4', and for a card with 'b' and '3' (since the letter is not a vowel). The statement is false, for example, for card with 'e' and '5'. You are interested if the statement is true for all cards. In particular, if no card has a vowel, the statement is true.

To determine this, you can flip over some cards to reveal the other side. You would like to know what is the minimum number of cards you need to flip in the worst case in order to verify that the statement is true.

Input:

The first and only line of input will contain a string $s$ (1 ≤ |$s$| ≤ 50), denoting the sides of the cards that you can see on the table currently. Each character of $s$ is either a lowercase English letter or a digit.

Output:

Print a single integer, the minimum number of cards you must turn over to verify your claim.

Sample Input:

ee

Sample Output:

2

Sample Input:

z

Sample Output:

0

Sample Input:

0ay1

Sample Output:

2

Note:

In the first sample, we must turn over both cards. Note that even though both cards have the same letter, they could possibly have different numbers on the other side.

In the second sample, we don't need to turn over any cards. The statement is vacuously true, since you know your friend has no cards with a vowel on them.

In the third sample, we need to flip the second and fourth cards.

分析:

需要翻元音字母和奇数数字。

题解:

#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    int count=0;
    char temp;
    while(true){
        scanf("%c", &temp);
        if(temp=='\n'){
            break;
        }
        if(temp == 'a' || temp == 'e' || temp == 'i' || temp == 'o' || temp == 'u' || temp == '1' || temp == '3' || temp == '5' || temp == '7' || temp == '9'){
            count++;
        }
    }
    printf("%d", count);
    return 0;
}

H - CF808A Lucky Year

1000ms 262144K

Description:

Apart from having lots of holidays throughout the year, residents of Berland also have whole lucky years. Year is considered lucky if it has no more than 1 non-zero digit in its number. So years 100, 40000, 5 are luckyand 12, 3001 and 12345 are not.

You are given current year in Berland. Your task is to find how long will residents of Berland wait till the next lucky year.

Input:

The first line contains integer number $n$ (1 ≤ $n$ ≤ 109) — current year in Berland.

Output:

Output amount of years from the current year to the next lucky one.

Sample Input:

4

Sample Output:

1

Sample Input:

201

Sample Output:

99

Sample Input:

4000

Sample Output:

1000

Note:

In the first example next lucky year is 5. In the second one — 300. In the third — 5000.

分析:

仅需把最高位的数+1取整再减原来的数即可。

比如2345的最高位数+1取整得3000,输出3000-2345即可。

不过这一题有一个大坑!不能用pow函数,要自己写一个。

题解:

#include<cstdio>
#include<iostream>
#include<cmath>

using namespace std;

long long poww(int count){
    if(count == 0) return 1;
    else return 10*poww(count-1);
}

int main(){
    long long year;
    int count = 0;
    cin >> year;
    long long backup = year;
    while(year > 9){
        year = year / 10;
        count++;
    }
    long long temp = (year + 1) * poww(count);
    cout << temp - backup;
    return 0;
}

I - CF954A Diagonal Walking

1000ms 262144K

Description:

Mikhail walks on a 2D plane. He can go either up or right. You are given a sequence of Mikhail's moves. He thinks that this sequence is too long and he wants to make it as short as possible.

In the given sequence moving up is described by character U and moving right is described by character R. Mikhail can replace any pair of consecutive moves RU or UR with a diagonal move (described as character D). After that, he can go on and do some other replacements, until there is no pair of consecutive moves RU or UR left.

Your problem is to print the minimum possible length of the sequence of moves after the replacements.

Input:

The first line of the input contains one integer $n$ (1 ≤ $n$ ≤ 100) — the length of the sequence. The second line contains the sequence consisting of $n$ characters U and R.

Output:

Print the minimum possible length of the sequence of moves after all replacements are done.

Sample Input:

5
RUURU

Sample Output:

3

Sample Input:

17
UUURRRRRUUURURUUU

Sample Output:

13

Note:

In the first test the shortened sequence of moves may be DUD (its length is 3).

In the second test the shortened sequence of moves can be UUDRRRDUDDUUU (its length is 13).

分析:

判断一下和上一步是不是不同,如果是就步数不变,如果不是就加一步。

题解:

#include<cstdio>
#include<iostream>
using namespace std;
char arr[105];
int main(){
    int t;
    int count=0;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> arr[i];
        if(i != 0 && arr[i] != arr[i-1] && arr[i-1] != 'D'){
            arr[i] = 'D';
        }else{
            count++;
        }
    }
    printf("%d", count);
    return 0;
}

J - CF1006A Adjacent Replacements

1000ms 262144K

Description:

Mishka got an integer array aa of length nn as a birthday present (what a surprise!).

Mishka doesn't like this present and wants to change it somehow. He has invented an algorithm and called it "Mishka's Adjacent Replacements Algorithm". This algorithm can be represented as a sequence of steps:

  • Replace each occurrence of 11 in the array aa with 22;
  • Replace each occurrence of 22 in the array aa with 11;
  • Replace each occurrence of 33 in the array aa with 44;
  • Replace each occurrence of 44 in the array aa with 33;
  • Replace each occurrence of 55 in the array aa with 66;
  • Replace each occurrence of 66 in the array aa with 55;
  • ……
  • Replace each occurrence of 109−1109−1 in the array aa with 109109;
  • Replace each occurrence of 109109 in the array aa with 109−1109−1.

Note that the dots in the middle of this algorithm mean that Mishka applies these replacements for each pair of adjacent integers (2i−1,2i2i−1,2i) for each i∈{1,2,…,5⋅108}i∈{1,2,…,5⋅108} as described above.

For example, for the array a=[1,2,4,5,10]a=[1,2,4,5,10], the following sequence of arrays represents the algorithm:

[1,2,4,5,10][1,2,4,5,10] →→ (replace all occurrences of 11 with 22) →→ [2,2,4,5,10][2,2,4,5,10] →→(replace all occurrences of 22 with 11) →→ [1,1,4,5,10][1,1,4,5,10] →→ (replace all occurrences of 33 with 44) →→ [1,1,4,5,10][1,1,4,5,10] →→ (replace all occurrences of 44with 33) →→ [1,1,3,5,10][1,1,3,5,10] →→ (replace all occurrences of 55 with 66) →→ [1,1,3,6,10][1,1,3,6,10] →→ (replace all occurrences of 66 with 55) →→ [1,1,3,5,10][1,1,3,5,10] →→ ……→→ [1,1,3,5,10][1,1,3,5,10] →→ (replace all occurrences of 1010 with 99) →→ [1,1,3,5,9][1,1,3,5,9]. The later steps of the algorithm do not change the array.

Mishka is very lazy and he doesn't want to apply these changes by himself. But he is very interested in their result. Help him find it.

Input:

The first line of the input contains one integer number nn (1≤n≤10001≤n≤1000) — the number of elements in Mishka's birthday present (surprisingly, an array).

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the elements of the array.

Output:

Print nn integers — b1,b2,…,bnb1,b2,…,bn, where bibi is the final value of the ii-th element of the array after applying "Mishka's Adjacent Replacements Algorithm" to the array aa. Note that you cannot change the order of elements in the array.

Sample Input:

51 2 4 5 10

Sample Output:

1 1 3 5 9

Sample Input:

1010000 10 50605065 1 5 89 5 999999999 60506056 1000000000

Sample Output:

9999 9 50605065 1 5 89 5 999999999 60506055 999999999

Note:

The first example is described in the problem statement.

分析:

把所有的偶数减一。

题解:

#include<iostream>
using namespace std;
long long array[1005];
int main(){
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> array[i];
    }
    for(int i = 0; i < t; i++){
        if(array[i] % 2){
            cout << array[i];
        }else{
            cout << array[i]-1;
        }
        if(i != t-1) cout << " ";
    }
    return 0;
}

数字货币交易指南

从2010年一万枚比特币换两个披萨的交易起,到如今交易所中的约1万美元换一枚比特币。比特币的价值在短短的十年间翻了约四百万倍。这一奇迹吸引了源源不断的投资者与投机者进入这个市场,也让许多中国大陆的群众跃跃欲试。但是出于某些原因,我们进行交易的过程也许不是那么顺畅,今天我就来带着大家聊聊这件事。

值得注意的是,本篇文章不构成任何投资建议。数字货币是风险极高的投资品,其风险甚至远高于股票。如果你不能很明确地了解加密货币的基本原理,对于各种货币的基本面不了解的话,我建议你还是远离这个市场。毕竟,带着太强的功利心进入一个一无所知的高风险投机市场,最后的结局往往家破人亡,血本无归。

作为中国大陆的民众,目前最简单的方式就是采取法币交易+币币交易的模式。

法币交易是指通过银行转账、支付宝转账、微信转账等方式,将法币人民币与主流数字货币进行兑换的交易方式。优点在于……它是法币!也是你法币兑换数字货币的唯一出入口。但是缺点也很明显,由于和你交易的人一般是认证商家,交易时价格往往不是很优,交易的量一般也有限制。通常交易在五万元以上才会拿到比较好的价格,而这个门槛对于想入门试试水的人来说还是有点高了。

而币币交易就是在各种数字货币之间进行兑换。这里就要提一下USDT了。USDT是一家叫Tether的交易所发行的稳定币,其承诺每发行1USDT就会储备1美元作为背书。其理论值是1USDT=1USD,但是由于种种原因这并不是绝对的,在面向中国人的交易所中有时候USDT比美元“贵”,有时候又“便宜”一些。以现在为例,1USD=6.88CNY,但是1USDT=6.97CNY。其价格波动的具体原因不是本文的重点。

币币交易的优点在于可以实时交易,挂单等等,交易的金额也是可以随便设定的,一些交易所还提供止盈止损等选项,是比较方便的交易方式。所以我推荐法币交易入场,币币交易发财,再法币交易退场。这是比较明智的选择。

讲完了交易模式,是时候推荐一波交易所了。币圈的朋友们应该会公认这个观点:只在三大交易所交易:币安、火币、OKEX。

这三大交易所都非常的棒,只有一些小区别,我将它们没讲到的点整理成一个表格(截至2019年7月17日),请自行选择:

币安 火币 OKEX
法币交易 不支持 支持USDT、BTC、ETH、EOS等8种 支持USDT、BTC、ETH、EOS等14种
杠杆交易 支持 支持 支持
合约交易 不支持 支持 支持

虽然币安不支持法币交易,但是可以在其它两个交易所购买数字货币后再转入币安。同样,虽然火币和OKEX都支持杠杆和合约交易,但是杠杆和合约的风险太高,尤其是OKEX的简直是可以用臭名昭著来形容。所以究竟选哪个交易所还是要结合自身实际,审慎判断。

最后是这三家交易所的官网和注册链接。

币安:官网 注册链接

火币:官网 注册链接

OKEX:官网 注册链接

投资有风险 交易需谨慎 祝你发大财


区块链,不应是一场豪赌

随着比特币的起起伏伏,区块链的概念也越来越为人所知。区块链技术虽和人工智能、大数据、物联网一样,都是21世纪得到飞速发展的计算机技术,但是由于区块链技术的高门槛性,大多数人并不明确了解区块链技术到底是什么。区块链等于比特币吗?区块链是个骗局,还是大有用处?这篇文章,我将用通俗易懂的语言带你剖析区块链的前世今生,以及未来的发展方向。

区块链,首先还是要从比特币谈起。时间要回到2008年,一个代号叫中本聪的人发布了比特币白皮书:《比特币:一种点对点的电子现金系统》(Bitcoin: A peer-to-peer electronic cash system)。在这个白皮书里,中本聪提出了这样一种构想:比特币的每一笔交易其实都可以用一个字符串表示,我们将每4000条交易记录打包成一个区块(block),在区块头部添加一个唯一的特征码(具体技术细节略,感兴趣的可以搜索哈希算法)。如果再有4000条交易记录,就再生成一个区块,同时头部特征码的生成过程要包含上一个区块的特征码。这样区块就会一个接着一个地串起来变成一条链(chain),称作区块链(block chain)。

所以说,区块链是从比特币中抽象出来的一个概念。但是,区块链并不完全等同于比特币,区块链离开了比特币也可以作为一项技术为人类服务。这就要谈谈区块链的三个发展阶段。

在第一个阶段,也就是区块链1.0时代,区块链的最广泛应用以金融为主。由于交易的数据简单明确,交易系统易于构建,基于区块链的各种数字货币是区块链应用的主力军。

在第二个阶段,区块链2.0时代,区块链应用的核心是智能合约。但坦率地说,这个智能合约既不”智能“,也不”合约“。我更倾向于叫它”可编程金融“。在区块链1.0这种单纯的交易功能下,区块链2.0发展出了”可编程“这一特性。我们可以通过在链上编程,使得除转账之外的其它信息也被区块链存储。最知名的智能合约叫做”以太坊“。目前依我来看,我们正处于区块链2.0时代。由于区块链3.0的条件太过严苛,尽管有许多人尝试着做出类似区块链3.0的应用,但都没有取得比较好的效果。

在区块链3.0时代,区块链的核心是”可编程社会“。区块链技术会渗透到我们生活的方方面面。在医疗方面,病历可以在区块链上存储;在教育方面,学历可以在区块链上存储;在工业方面,操作可以在区块链上存储等等。以教育为例,现在存储在学信网上的学历信息其实并不是绝对安全的。我们假定学信网有一个高危漏洞,那我就可以侵入然后修改自己的学籍。但是,如果学历信息存储在区块链上,那么学历的安全问题将被解决。

现如今,有许多”伪区块链3.0“的项目在疯狂捞钱。但是,区块链3.0应该摆脱区块链1.0和2.0的金融属性,脱离数字货币才能让区块链更好地发展。中国区块链专利数量第一的阿里巴巴就曾明确表示自己不会发币。区块链技术的理解门槛高是区块链骗局多的主要原因之一。区块链是一个非常优秀的技术,我也反对任何将区块链与比特币绑定在一起的说法。区块链未来会和AI一样在生活中普及,只是大家对区块链的误解太多,想要真正实现区块链3.0时代还有很长的一段路要走。


PHPstudy2019发布

惊闻PHPstudy发布了2019版本正式版,我下载体验之后,觉得比2018版本的进步真的不是一点半点!

上几张截图给你们感受下!

phpstudy1

phpstudy2

phpstudy3

phpstudy4

phpstudy5

phpstudy6

话说我还发现他们给它起了个名字叫小皮系统,访问xp.cn也会重定向到官网2333。


NOJ榜单重构小结

今年上半年,我接了NOJ的第一个真正意义上的锅——重构比赛榜单。

期末考试结束,我终于可以好好谈谈这个重构是怎么实现的了。

之前的比赛榜单是这样生成的:

先去执行一个类似SELECT * FROM submission WHERE cid = $cid的SQL查询,然后根据查询到的赛中提交记录实时算一个榜单出来。这样做有什么问题呢?显而易见,那就是太慢了。每一个查询榜单的请求都需要调用一遍contestRank函数,contestRank函数再去调用一遍contestRankCache函数。但问题就是这个contestRankCache其实并不是cache。它这个函数的作用其实是传入一个包含所有比赛提交的集合对象,然后返回一个榜单的二维数组。由于计算的过程过于复杂,所以当计算榜单的时候会侵占学校垃圾的比赛服务器高达50%的CPU性能,更不用说多人同时查看榜单的情况了。记得一次榜单对外开放的比赛中途突然传出xxxAK的消息,大家冲进去看榜单,直接把服务器挤炸了,害的比赛选手交题时Submission Error。

所以,重构这个臭名昭著的榜单的重任就落在了我的头上。重构的思路是这样的:基于Redis驱动的Cache,以cid(比赛id)为键,比赛开始时建立一个空二维数组,当有选手交题时,根据单条交题记录去更新这个数组,该数组在Cache中永久保存。

这样一来,更新榜单的事件驱动就由请求榜单转为选手提交,大大减轻了服务器压力,请求榜单时也可以做到理论上的“秒开”。

以下是核心代码:

public function updateContestRankTable($cid,$sub){
    $lock = Cache::lock("contestrank$cid",10);
    try{
        if($lock->get()){
            if(Cache::tags(['contest','rank'])->get($cid) != null){
                $chache = Cache::tags(['contest','data'])->get($cid);
                $ret = Cache::tags(['contest','rank'])->get($cid);
                if (time() > $chache['frozen_time'])
                    return;

                $id = 0;

                foreach($chache['problemSet'] as $key => $p){
                    if ($p['pid'] == $sub['pid']){
                        $chache['problemSet'][$key]['cpid'] = $key;
                        $id = $key;
                    }
                }

                $ret = $this->updateContestRankDetail($chache['contest_info'],$chache['problemSet'][$id],$cid,$sub['uid'],$ret);
                $ret = $this->sortContestRankTable($chache['contest_info'],$cid,$ret);

                Cache::tags(['contest', 'rank'])->put($cid, $ret);
            }
            else{
                $ret=[];
                $chache=[];
                $chache['contest_info']=DB::table("contest")->where("cid", $cid)->first();
                $chache['problemSet']=DB::table("contest_problem")->join("problem", "contest_problem.pid", "=", "problem.pid")->where([
                    "cid"=>$cid
                ])->orderBy('ncode', 'asc')->select("ncode", "alias", "contest_problem.pid as pid", "title")->get()->all();
                $chache['frozen_time']=DB::table("contest")->where(["cid"=>$cid])->select(DB::raw("UNIX_TIMESTAMP(end_time)-froze_length as frozen_time"))->first()["frozen_time"];
                $chache['end_time']=strtotime(DB::table("contest")->where(["cid"=>$cid])->select("end_time")->first()["end_time"]);

                Cache::tags(['contest', 'data'])->put($cid, $chache);

                if ($chache['contest_info']["registration"]) {
                    $submissionUsers=DB::table("contest_participant")->where([
                        "cid"=>$cid,
                        "audit"=>1
                    ])->select('uid')->get()->all();
                }else{
                    $submissionUsers=DB::table("submission")->where([
                        "cid"=>$cid
                    ])->where(
                        "submission_date",
                        "<",
                        $chache['frozen_time']
                    )->select('uid')->groupBy('uid')->get()->all();
                }
                foreach ($submissionUsers as $s) {
                    foreach ($chache['problemSet'] as $key => $p) {
                        $p['cpid'] = $key;
                        $ret = $this->updateContestRankDetail($chache['contest_info'],$p,$cid,$s['uid'],$ret);
                    }
                }
                $ret = $this->sortContestRankTable($chache['contest_info'],$cid,$ret);
                Cache::tags(['contest', 'rank'])->put($cid, $ret);
            }
        }
    }catch(LockTimeoutException $e){
        Log::warning("Contest Rank Lock Timed Out");
    }finally{
        optional($lock)->release();
    }
}

public function sortContestRankTable($contest_info,$cid,$ret){
    if ($contest_info["rule"]==1){
        usort($ret, function ($a, $b) {
            if ($a["score"]==$b["score"]) {
                if ($a["penalty"]==$b["penalty"]) {
                    return 0;
                } elseif (($a["penalty"]>$b["penalty"])) {
                    return 1;
                } else {
                    return -1;
                }
            } elseif ($a["score"]>$b["score"]) {
                return -1;
            } else {
                return 1;
            }
        });
    }else if ($contest_info["rule"]==2){
        usort($ret, function ($a, $b) {
            if ($a["score"]==$b["score"]) {
                if ($a["solved"]==$b["solved"]) {
                    return 0;
                } elseif (($a["solved"]<$b["solved"])) {
                    return 1;
                } else {
                    return -1;
                }
            } elseif ($a["score"]>$b["score"]) {
                return -1;
            } else {
                return 1;
            }
        });
    }
    return $ret;
}

public function updateContestRankDetail($contest_info,$problem,$cid,$uid,$ret){
    $id = count($ret);
    foreach($ret as $key => $r){
        if($r['uid'] == $uid)
            $id = $key;
    }
    if ($contest_info["rule"]==1) {
        // ACM/ICPC Mode
            if($id == count($ret)){
                $prob_detail = [];
                $totPen = 0;
                $totScore = 0;
            }else{
                $prob_detail = $ret[$id]['problem_detail'];
                $totPen=$ret[$id]['penalty'];
                $totScore=$ret[$id]['score'];
            };

            $prob_stat=$this->contestProblemInfoACM($cid, $problem["pid"], $uid);

            $prob_detail[$problem['cpid']]=[
                "ncode"=>$problem["ncode"],
                "pid"=>$problem["pid"],
                "color"=>$prob_stat["color"],
                "wrong_doings"=>$prob_stat["wrong_doings"],
                "solved_time_parsed"=>$prob_stat["solved_time_parsed"]
            ];
            if ($prob_stat["solved"]) {
                $totPen+=$prob_stat["wrong_doings"] * 20;
                $totPen+=$prob_stat["solved_time"] / 60;
                $totScore+=$prob_stat["solved"];
            }

            $ret[$id]=[
                "uid" => $uid,
                "name" => DB::table("users")->where([
                    "id"=>$uid
                ])->first()["name"],
                "nick_name" => DB::table("group_member")->where([
                    "uid" => $uid,
                    "gid" => $contest_info["gid"]
                ])->where("role", ">", 0)->first()["nick_name"],
                "score" => $totScore,
                "penalty" => $totPen,
                "problem_detail" => $prob_detail
            ];
    } elseif ($contest_info["rule"]==2) {
        // OI Mode
        if($id == count($ret)){
            $prob_detail = [];
            $totPen = 0;
            $totScore = 0;
        }else{
            $prob_detail = $ret[$id]['problem_detail'];
            $totPen=$ret[$id]['penalty'];
            $totScore=$ret[$id]['score'];
        };

        $prob_stat=$this->contestProblemInfoOI($cid, $problem["pid"], $uid);
        $prob_detail[$problem['cpid']]=[
            "ncode"=>$problem["ncode"],
            "pid"=>$problem["pid"],
            "color"=>$prob_stat["color"],
            "score"=>$prob_stat["score"],
            "score_parsed"=>$prob_stat["score_parsed"]
        ];
        $totSolved+=$prob_stat["solved"];
        $totScore+=intval($prob_stat["score_parsed"]);

        $ret[$id]=[
            "uid" => $uid,
            "name" => DB::table("users")->where([
                "id"=> $uid
            ])->first()["name"],
            "nick_name" => DB::table("group_member")->where([
                "uid" => $uid,
                "gid" => $contest_info["gid"]
            ])->where("role", ">", 0)->first()["nick_name"],
            "score" => $totScore,
            "solved" => $totSolved,
            "problem_detail" => $prob_detail
        ];
    }
    return $ret;
}

唉,不提了,写Contest Admin Portal去了。


三角迷宫

这是“Wishare杯”南邮第十一届大学生程序设计竞赛网络赛的C题。

Description:

如图为一个三角迷宫,迷宫中的数字从1开始标号。现给出两个数字m、n,请求出从m到n的最短路径,输出路径长度。

注:如图所示,迷宫中的数字被网格线所分隔,我们规定,穿过一次网格线,路径长度加一,初始路径长度为0。

1555125122634

Input:

第一行,一个整数T(0≤T≤1e6)。

接下来T行,每行两个整数,m、n(1≤m,n≤1e9​​)。

Output:

输出T行,每行一个整数,表示结果。

Sample Input:

1
6 12

Sample Output:

3

可惜我太菜了,用简单的分类讨论完成了这道题。

该图可以转化成一个自顶向下的组织关系图, row表示上下移动的次数,col表示左右移动的次数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

long long getrow(long long num){
    long long sqrtnum = (long long)sqrt(num);
    for(long long i = 1;i <= sqrtnum+1;i++){
        if(num <= i*i){
            return i;
        }
    }
}

long long getdiffcol(long long m,long long n){
    long long diffrow = getrow(n) - getrow(m);
    long long diffcol;
    diffcol = fabs(n - (m + diffrow * getrow(m) * 2 + diffrow * (diffrow - 1)));
    if(diffcol >= diffrow){
        return diffcol;
    }else{
        if(getrow(m)%2 == m%2){
            diffcol += ((diffrow - diffcol - 1) / 2 + (diffrow - diffcol - 1) % 2) * 2;
        }else{
            diffcol += ((diffrow - diffcol) / 2 + (diffrow - diffcol) % 2) * 2;
        }
    }
    return diffcol;
}

int main(){
    long long t,m,n,diffrow,diffcol;
    scanf("%lld", &t);
    while(t--){
        scanf("%lld%lld",&m,&n);
        if(m > n){
            swap(m,n);
        }
        diffrow = getrow(n) - getrow(m);
        diffcol = getdiffcol(m,n); 
        printf("%lld\n",diffrow + diffcol);
    }
    return 0;
}

我是如何从零开始部署wordpress的

不知不觉我已经过完了整个大一。在这一年里我的前后端及运维知识都有了不少的增长。现在回头看我刚入学时候搭起来的博客,已经是不忍直视。遂决定重置系统,从零搭一个全新的个人主页。

由于之前的那个博客没有什么干货文章,所以重置系统前没有备份,所有的文章都不要了。

以下是我重置系统的过程:

首先在阿里云的控制台里选择重置系统,选择CentOS镜像。

然后通过SSH链接服务器,执行yum install screen以安装screen。

接下来使用LNMP一键安装包。执行:screen -S lnmp 后,执行:wget http://soft.vpser.net/lnmp/lnmp1.6.tar.gz -cO lnmp1.6.tar.gz && tar zxf lnmp1.6.tar.gz && cd lnmp1.6 && ./install.sh lnmp

这个过程会持续很久,需要耐心等待。

安装成功后我先去改了一下PhpMyAdmin的地址。执行cd /home/wwwroot/default切换到默认路径,然后执行mv phpmyadmin xxxxxx以更改PMA文件夹的名字。

接下来配置SSL证书。执行lnmp ssl add

运行结束后发现并不是强制跳转HTTPS,执行命令:

cd /usr/local/nginx/conf/vhost
vim pikanglong.com.conf

#error_page...# Deny...两行间添加

if ($ssl_protocol = "") { return 301 https://$host$request_uri; }

后保存退出。

接下来就要开始安装Wordpress啦!

cd /home/wwwroot/default
wget http://wordpress.org/latest.tar.gz
tar -xzvf latest.tar.gz
cp -r /home/wwwroot/default/wordpress/. /home/wwwroot/default
rm -rf /home/wwwroot/default/wordpress
chown -R www:www ./

前往网站首页执行安装指南。

大功告成!wordpress安装成功!

在更进一步之前,我先安装了一个可道云来方便文件管理。

wget http://static.kodcloud.com/update/download/kodexplorer4.40.zip
unzip kodexplorer4.40.zip
chmod -Rf 777 ./*

接下来就是配置wordpress基本设置了。语言啊,时区啊等等。