新型快读

2018-02-07 09:35:34


这次又是基于get_char()的优化,但是用到了更高级的东西:

#include <cstdio>
#include <sys/mman.h> 
#include <fcntl.h>
#include <unistd.h>
using namespace std;

int main(){    
    char *data;
    int size = lseek(0, 0, SEEK_END);
    data = (char *) mmap( NULL,  size ,PROT_READ, MAP_PRIVATE, 0, 0 );
    fwrite(data, 1, size, stdout);
    return 0;
}

mmap:直接把文件映射到内存,比fread快,因为:

1.read(fread)是一种阻塞系统调用的行为

2.会以内核为缓冲而导致占用CPU时间的内存拷贝 

3.没有显示地通知从文件的某个位置开始,导致需要每次使用lseek

上面代码的stdin的标识为0,所以mmap先从stdin映射输入到data内,然后此题为直接输出。

那些标号在OI中无需关注,背背就好了。

注意这种快读有几个使用要求:

1.不接受键盘输入
2.只能在linux等unix或类unix下跑

例如在P3205下跑快读,代码如下,其中还加入了一些莫名奇妙但是没用的优化:

// luogu-judger-enable-o2
#include <cstdio>
#include <sys/mman.h>
#include <unistd.h>
using namespace std;

#define MAXN 1005
#define MODS 19650827

int num[MAXN] __attribute__ ((aligned(64)));
int dp[MAXN][MAXN][2] __attribute__ ((aligned(64)));

int main(){
    int n = 0;
    register int i, j;
    register char *pc = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0), c;
    while ((c = *pc++) < 48);
    while (n = n * 10 + c - 48, (c = *pc++) >= 48);
    for(i = 1; i <= n; i++){
        int &p = num[i];
        while ((c = *pc++) < 48);
        while (p = p * 10 + c - 48, (c = *pc++) >= 48);
    }
    for(i = 1; i <= n; i++) dp[i][i][0] = 1;
    for(i = n; i >= 1; i--){
        int (*px) [2] = dp[i];
        for(j = i; j <= n; j++){
            int &p0 = px[j][0], &p1 = px[j][1];
            if(num[i] < num[j]) p1 += px[j - 1][0], p0 += dp[i + 1][j][1];
            if(num[i] < num[i + 1]) p0 += dp[i + 1][j][0];
            if(num[j] > num[j - 1]) p1 += px[j - 1][1];
            if(p0 >= MODS) p0 -= MODS;
            if(p1 >= MODS) p1 -= MODS;
        }
    }
    printf("%d", (dp[1][n][0] + dp[1][n][1]) % MODS);
    return 0;
}

又一次更新:Luogu4047

这是我和某大佬轮流卡常的结果:

然而多亏这个快读。所以最后这个快读的函数封装版就在下面,其中get_char部分用指针控制,此部分只有1行!不需要开额外数组,可能(可能)在某些评测系统下会忽略快读的buf空间。

#include <cmath>
#include <cstdio>
#include <fcntl.h>
#include <unistd.h>
#include <algorithm>
#include <sys/mman.h>
using namespace std;
#define Finline __inline__ __attribute__ ((always_inline))

char *pc = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0);

inline int read(){
    int num = 0;
    char c;
    while ((c = *pc++) < 48);
    while (num = num * 10 + c - 48, (c = *pc++) >= 48);
    return num;
}
inline void Swap(int &a, int &b){
    int t = a;
    a = b;
    b = t;
}
Finline void upmin(double &a, const double &b){
    if(a > b) a = b;
}
Finline void upmax(int &a, const int &b){
    if(a > b) a = b;
}

int tot, n, k, cnt;
int x[1001], y[1001];
double ans = 0x3f3f3f3f3f3f;

int father[1001], rnk[1001];
inline void Init(){
    for(int i = 1; i <= n; i++) father[i] = i; 
}
inline int Get_Father(int u){
    return father[u] == u ? u : father[u] = Get_Father(father[u]);
}
inline void Merge(int fu, int fv){
    fu = Get_Father(fu), fv = Get_Father(fv);
    if(rnk[fu] > rnk[fv]) Swap(fu, fv);
    father[fu] = fv;
    upmax(rnk[fv], rnk[fu] + 1);  
}

struct P{
    int u, v;
    double dis;
    Finline bool operator < (const P &tar) const {
        return dis < tar.dis;
    }
}edge[500501];

inline int pow2(int tar){
    return tar * tar;
}

signed main(){
freopen("in.in", "r", stdin);
    n = read(), k = read(), k = n - k;
    Init();
    for(int i = 1; i <= n; i++){
        x[i] = read(), y[i] = read();
        for(int j = 1; j < i; j++)
            edge[++tot] = (P){i, j, sqrt(pow2(x[i] - x[j]) + pow2(y[i] - y[j]))};
    }
    sort(edge + 1, edge + 1 + tot);
    for(int i = 1; i <= tot; i++){
        int u = edge[i].u, v = edge[i].v;
        if(Get_Father(u) != Get_Father(v)){
            if(cnt == k){
                printf("%.2lf", edge[i].dis);
                return 0;
            }
            cnt ++;
            Merge(u, v);
        }
    }
    return 0;
}

最后这篇文章大致更新完毕。

License:

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行许可。