新型快读

这次又是基于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 中国大陆许可协议](http://creativecommons.org/licenses/by-nc-sa/3.0/cn/)进行许可。