发表于 | 阅读次数:
字数统计: 1,239 字

DAY1

今天是焦景辉dalao的题. . . 然后各种爆炸. . . 3道题打的十分绝望. . .

总分：
10+64 = 74分

其实今天这一套题的难度是明显大于昨天的那一套题的。感觉昨天的题就是比较水， 感觉很水的分数有很多， 但是今天的题就感觉十分硬核。考验真正的实力。

比赛过程：

其实今天的比赛开始之后大概扫一遍题目就感觉好像并不简单。看了下T1，好像暴力都没有办法写啊. . . 但是我还是硬着头皮推了下T1。感觉好像是有什么规律。但是当我验证完n<=4的情况之后并且过掉了第一组小样例的时候，我惊奇的发现这个规律对于n>4完全没有用 . . . . 所以一度凉凉， 等我做完这些事情的时候已经10点10分左右。好像大家对T1也都没什么思路. . .写到这时我感觉有一点慌了. . 毕竟连暴力都没有， 如果n<=4的规律不对的话那就一分都拿不到了. . . 所以感觉把这个T1先敲完放下， 慌忙看T3. . . （其实我也不知道我为啥要看T3的，应该按照顺序做题的. . . ）。看完之后其实有一点小激动， 有30分的纯暴力可以拿一下。然后正解肯定是写不出来的，这种深深的绝望已经许久没有感受了 . .. 记得上一次感受好像还是HAOI省选。真的就是很绝望， 这么大的数据范围肯定没办法写的 . . .
T3暴力打完之后分析一波发现心态有一点爆炸， 觉得今天肯定凉凉 . .. 预估10+30 = 40 。真的是惨，这时候时间已经到了11点左右。
于是我开始看T2， 大概感觉好像是贪心或者DP这一方面的东西。手推了一下样例感觉好像有一些性质可以发现一下。 然后就写了一波， 感觉好像可以80+左右，10分钟后，比赛结束。 预估分数 10+30+80 = 120左右

拿到结果之后首先感觉比较不可思议的是好像T3的30没了. . . 觉得不应该啊。搜索的话好像时间和空间给的都很大的呀。过30分的数据应该很稳的. . .

最后发现是题中并没有对30%数据的m进行限制，在这30%的数据中m就是10^9的数量级，导致我的数组开小. . .当场GG 直接RE。解决方法是离散化或者直接记录左右端点。

试题总结：

T1：
组合数学， 排列组合， 计数原理
问题答案即为

一个组合数问题， 并不会。 组合数学要学习一波了。

T2:

二分+贪心
一类经典题型， 其实在当时是想到了二分的， 但是二分的上下界并不是很好找 。并且并不知道二分的check判定要怎么写. . . 于是在场上就否定掉了二分这个做法。

设一共需要m瓶。正解的二分下界为a[m+1]；上界为m。
二分判定的依据是S1,S2满足S1>=S2。

时k成立

T3:

可持久化线段树/2-SAT（确定这是NOIP考点?. . . . ）（2-SAT 已学会√）
看不懂，高级数据结构，蓝书上都没有讲的东西， 怕是省选+的知识点吧 . . . .

DAY2

今天还是焦景辉dalao的题， 感觉好像今天的暴力分比较好拿？
总分：
65+4 = 69

做题过程：

其实今天做的还好， 没有那么的难受。 出现题正解不会， 暴力又打不了的情况发生。其实3道题两道题应该都可以打一下高分暴力。T1看完后发现好像可以用并查集写， 9点10分左右打完， 还算不错。 估分40 ~ 70分左右。

然后开始看T2，发现是概率与期望。 好吧老规矩直接看T3。（真的要整一下概率和期望的部分了）。

T3看完题之后感觉好像是线段树的操作啊， 然后连题都没看完就开始码线段树， 120+的代码，大约30+分钟调完。 然后开始看题目要求， 第一眼好像数据范围有一点大， 应该要二分。 打完之后发现好像这个答案并没有单调性 ，于是GG。 打了一下O（n^3）暴力判断，然后发现好像大样例并过不去。 但是时间到了于是就上交了。最后4分，（好像得分率并不高）

试题总结：

T1 就是并查集相关， 只不过好像需要维护点集之间的一些比较复杂的关系。

T2 套路题， 概率与期望相关

T3 需要维护的信息好像比较多一点的一个DP

发表于 | 阅读次数:
字数统计: 530 字

考试总结

这次分数100+10+40 = 150 有点爆炸

这是我停文化课以来的第一场模拟赛。感觉难度一般， 但是打的比较爆炸， 在场的250+的高分并不在少数。

考试过程：
这次考试感觉比较顺利， T1拿到后感觉好像比较难， 但是按照样例推了一下发现并不是看起来那么没法写。借助大样例的帮助，在9点10分左右T1写完并且通过了大样例。于是就放在那里看T2。

T2感觉好像没法直接写， 我对这种好像比较麻烦的DP并不是很感兴趣， 一眼没有看出来就直接跳了. . .于是开始看T3

T3看完以后感觉好像可以写一下， 如果比较暴力的去写的话好像只能拿20？ QAQ 所以感觉这估计是一道高级数据结构的题， 我先把暴力打了一下。 并查集， 稳了前20%。然后想什么数据结构可以实现 . . . 但是可能是因为自身实力的限制， 并没有发现有什么好的数据结构可以支持这么大的数据范围。 于是一度凉凉 . . . 但是看了一下好像有部分分可以拿一下， 于是就把一个比较好写的40%写了一下。

然后回过来看T2，这个数据范围好像正解做DP有点不好做， 所以我觉得好像是找规律的题. . . 但是还是由于自己太弱了 . . 并没有发现什么实质的规律 . . . 随便打了一个表就交上去了

结果是T2是一个卡特兰数列， 基本上O(n)递推。 T3好像做法也很多。 有什么树刨（并不会），按秩合并的并查集（也不会）. . . 但是好像这一道题如果好好打的话， 暴力就可以拿高分， 旁边dalao暴力拿了80 . . . 所以告诉我们即使想不出来正解也要打一下这些高分暴力。说不定就拿了很多分也不一定. . . .

发表于 | 阅读次数:
字数统计: 1,739 字

数论

Gcd 以及 EX_Gcd

学习了一下gcd和拓展gcd。之前一直以为是十分难得东西， 其实好像没有那么复杂。
Gcd（最小公倍数） 我们使用欧几里得算法来求解最小公倍数问题， 代码如下：

1
2
3
int gcd(int x, int y ){
    return (b==0) ? a : gcd(b,a%b);
}

这个一行的代码可以快速求出两数的gcd， 时间复杂度为O(logn)，效率还算不错。

lcm 如果我们已经求出了两个数的gcd，那么只需要一个式子就可以求出两数的lcm了：

1
2
3
inline int lcm(int a, int b) {
    return a/gcd(a, b)*b;
}//lcm(a, b) = a*b/gcd(a, b);
阅读全文 »

发表于 | 阅读次数:
字数统计: 2,379 字

今天听澜神讲了一下平衡树， 来总结一下

常见的平衡树主要有这几种： splay， treap， 红黑树， 替罪羊树等。 他们的本质都是二叉搜索树， 可以在logn的数量级内进行一些操作。

几个常见平衡树的对比

平衡树 附加域 平衡性 效率 编程难度 实用性 特点
Treap 修正值 较好 较快 易 好 随机平衡
Splay - 玄学 玄学（中） 中 好 灵活易变
SBT 子树大小 好 快 中 好 短小精湛
BST 无 差 不稳定 易 一般 编写容易

treap树

这是一个很玄学的平衡树， 它的平衡由一个dat来维持， 其实就是一个随机生成的数， 这个treap树满足dat的值是小根堆， 这种玄学的操作可以使treap树比较平衡， 两棵子树的大小都差不多。
其中应该是维护大多数平衡树的一个操作就是旋转， 旋转又分为左旋和右旋两种。 这两种操作可以保证平衡树的性质也就是大小关系不会出现错误， 但是可以将平衡树的结构进行调整， 使之成为一棵深度大概为logn的一棵树。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
typedef long long LL;
using namespace std;
int RD(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
//第一次打treap，不压行写注释XD
const int maxn = 1000019,INF = 1e9;
//平衡树，利用BST性质查询和修改，利用随机和堆优先级来保持平衡，把树的深度控制在log N，保证了操作效率
//基本平衡树有以下几个比较重要的函数：新建，插入，删除，旋转
//节点的基本属性有val(值)，dat(随机出来的优先级)
//通过增加属性，结合BST的性质可以达到一些效果，如size(子树大小，查询排名)，cnt(每个节点包含的副本数)等
int na;
int ch[maxn][2];//[i][0]代表i左儿子，[i][1]代表i右儿子
int val[maxn],dat[maxn];
int size[maxn],cnt[maxn];
int tot,root;
int New(int v){//新增节点，
    val[++tot] = v;//节点赋值
    dat[tot] = rand();//随机优先级
    size[tot] = 1;//目前是新建叶子节点，所以子树大小为1
    cnt[tot] = 1;//新建节点同理副本数为1
    return tot;
    }
void pushup(int id){//和线段树的pushup更新一样
    size[id] = size[ch[id][0]] + size[ch[id][1]] + cnt[id];//本节点子树大小 = 左儿子子树大小 + 右儿子子树大小 + 本节点副本数
    }
void build(){
    root = New(-INF),ch[root][1] = New(INF);//先加入正无穷和负无穷，便于之后操作(貌似不加也行)
    pushup(root);//因为INF > -INF,所以是右子树，
    }
void Rotate(int &id,int d){//id是引用传递，d(irection)为旋转方向，0为左旋，1为右旋
    int temp = ch[id][d ^ 1];//旋转理解：找个动图看一看就好(或参见其他OIer的blog)
    ch[id][d ^ 1] = ch[temp][d];//这里讲一个记忆技巧，这些数据都是被记录后马上修改
    ch[temp][d] = id;//所以像“Z”一样
    id = temp;//比如这个id，在上一行才被记录过，ch[temp][d]、ch[id][d ^ 1]也是一样的
    pushup(ch[id][d]),pushup(id);//旋转以后size会改变，看图就会发现只更新自己和转上来的点，pushup一下,注意先子节点再父节点
    }//旋转实质是({在满足BST的性质的基础上比较优先级}通过交换本节点和其某个叶子节点)把链叉开成二叉形状(从而控制深度)，可以看图理解一下
void insert(int &id,int v){//id依然是引用，在新建节点时可以体现
    if(!id){
        id = New(v);//若节点为空，则新建一个节点
        return ;
        }
    if(v == val[id])cnt[id]++;//若节点已存在，则副本数++;
    else{//要满足BST性质，小于插到左边，大于插到右边
        int d = v < val[id] ? 0 : 1;//这个d是方向的意思，按照BST的性质，小于本节点则向左，大于向右
        insert(ch[id][d],v);//递归实现
        if(dat[id] < dat[ch[id][d]])Rotate(id,d ^ 1);//(参考一下图)与左节点交换右旋，与右节点交换左旋
        }
    pushup(id);//现在更新一下本节点的信息
    }
void Remove(int &id,int v){//最难de部分了
    if(!id)return ;//到这了发现查不到这个节点，该点不存在，直接返回
    if(v == val[id]){//检索到了这个值
        if(cnt[id] > 1){cnt[id]--,pushup(id);return ;}//若副本不止一个，减去一个就好
        if(ch[id][0] || ch[id][1]){//发现只有一个值，且有儿子节点,我们只能把值旋转到底部删除
            if(!ch[id][1] || dat[ch[id][0]] > dat[ch[id][1]]){//当前点被移走之后，会有一个新的点补上来(左儿子或右儿子)，按照优先级，优先级大的补上来
                Rotate(id,1),Remove(ch[id][1],v);//我们会发现，右旋是与左儿子交换，当前点变成右节点；左旋则是与右儿子交换，当前点变为左节点
                }
            else Rotate(id,0),Remove(ch[id][0],v);
            pushup(id);
            }
        else id = 0;//发现本节点是叶子节点，直接删除
        return ;//这个return对应的是检索到值de所有情况
        }
    v < val[id] ? Remove(ch[id][0],v) : Remove(ch[id][1],v);//继续BST性质
    pushup(id);
    }
int get_rank(int id,int v){
    if(!id)return 0;//若查询值不存在，返回
    if(v == val[id])return size[ch[id][0]] + 1;//查询到该值，由BST性质可知：该点左边值都比该点的值(查询值)小，故rank为左儿子大小 + 1
    else if(v < val[id])return get_rank(ch[id][0],v);//发现需查询的点在该点左边，往左边递归查询
    else return size[ch[id][0]] + cnt[id] + get_rank(ch[id][1],v);//若查询值大于该点值。说明询问点在当前点的右侧，且此点的值都小于查询值，所以要加上cnt[id]
    }
int get_val(int id,int rank){
    if(!id)return INF;//一直向右找找不到，说明是正无穷
    if(rank <= size[ch[id][0]])return get_val(ch[id][0],rank);//左边排名已经大于rank了，说明rank对应的值在左儿子那里
        else if(rank <= size[ch[id][0]] + cnt[id])return val[id];//上一步排除了在左区间的情况，若是rank在左与中(目前节点)中，则直接返回目前节点(中区间)的值
    else return get_val(ch[id][1],rank - size[ch[id][0]] - cnt[id]);//剩下只能在右区间找了，rank减去左区间大小和中区间，继续递归
    }
int get_pre(int v){
    int id = root,pre;//递归不好返回，以循环求解
    while(id){//查到节点不存在为止
        if(val[id] < v)pre = val[id],id = ch[id][1];//满足当前节点比目标小，往当前节点的右侧寻找最优值
        else id = ch[id][0];//无论是比目标节点大还是等于目标节点，都不满足前驱条件，应往更小处靠近
        }
    return pre;
    }
int get_next(int v){
    int id = root,next;
    while(id){
        if(val[id] > v)next = val[id],id = ch[id][0];//同理，满足条件向左寻找更小解(也就是最优解)
        else id = ch[id][1];//与上方同理
        }
    return next;
    }
int main(){
    build();//不要忘记初始化[运行build()会连同root一并初始化，所以很重要]
    na = RD();
    for(int i = 1;i <= na;i++){
        int cmd = RD(),x = RD();
        if(cmd == 1)insert(root,x);//函数都写好了，注意：需要递归的函数都从根开始，不需要递归的函数直接查询
        else if(cmd == 2)Remove(root,x);
        else if(cmd == 3)printf("%d\n",get_rank(root,x) - 1);//注意：因为初始化时插入了INF和-INF,所以查询排名时要减1(-INF不是第一小，是“第零小”)
            else if(cmd == 4)printf("%d\n",get_val(root,x + 1));//同理，用排名查询值得时候要查x + 1名，因为第一名(其实不是)是-INF
        else if(cmd == 5)printf("%d\n",get_pre(x));
        else if(cmd == 6)printf("%d\n",get_next(x));
        }
    return 0;
}

从网上摘下来的一个板子， 可以满足大部分线段树的一般操作。是一道平衡树板子题的代码。

下面是一些自己的理解与总结：

  1. 函数参数id要用引用的原因是如果旋转的话， 根的节点编号可能发生改变。在旋转的过程中就直接将根的节点编号直接改变。
  2. 在很多函数中if（！id）的含义一般是指如果通过递归进入了一个新的节点ch[id][d]那么这个节点内的值一定是0， 所以就可以断定这个节点上没有点 的存在。
  3. 递归函数直接从根节点进入进行递归， 而不需要递归的函数直接进行查询。
  4. 旋转可以使平衡树的中序遍历的输出结果不变

splay

splay是一个复杂度比较友好的平衡树， 不会像treap一样玄学。还是通过旋转来实现树的基本的平衡。

发表于 | 阅读次数:
字数统计: 622 字

这是一道(很恶心的)数论题，斥容原理的应用， 没很懂实现原理， 来总结一下

原题：

小x最近对数字8很感兴趣，有8进制，2008奥运会之类的。
现在小x想知道，在[x,y]区间里，有多少个数能被8整除。
小y觉得题目太简单，于是给出n个其他数，问在[x,y]区间里，有多少个数能被8整除且不能被这n个数整除。

1≤n≤15，1≤x≤y≤10^9，N个数全都小于等于10^4大于等于1。

思路：

如果要求1 ~ n有多少数可以被8整除， 那么答案直接就是n/8， 但是加上了限定条件被能被a[i]整除。
我们可以把求x ~ y区间内的问题， 转化为分别求出1 ~ x-1 和 1 ~ y 两个区间内的个数， 然后相减。
但是我们需要找出的是在区间内可以被8整除单是不能被a[i]整除的树的个数， 那么我们可以先找出a[i]和8的lcm也就是最小公倍数， 然后直接拿y来除lcm（8， a[i]）
那么我们得到的就是从1到y之间的所有的能够被8整除但是不能被a[i]整除的所有数的个数。比如说16为y a[1] = 16, 那么16和8的lcm 是 16 ， 而且在1 ~ 16之间的能被8整出但是不能被16整除的数字就只有 8 一个了。

在这时我们需要再次使用一下斥容原理， 当我们枚举出这i个数字的选与不选的情况的时候， 我们根据选择的数字的个数的多少来决定答案的个数是加上还是减去。

Code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) {return (y)?gcd(y,x%y):x;}
ll n, a[20], xx, yy;
bool use[20];
ll ansx, ansy, bowl = 0;
void dfs(int x, int y) {
	if (x>n) {
		ll lcm = 8; int ge = 0;
		for (int i=1;i<=n;++i) if(use[i]){
			lcm*=a[i]/gcd(lcm, a[i]);
			if (lcm>y) break;
			ge++;
		}
		if(ge%2) bowl -= y/lcm;
		else bowl += y/lcm;
		return;
	}
	use[x] = false; dfs(x+1, y);
	use[x] = true; dfs(x+1,y);
}
int main() {
	scanf("%d", &n);
	for (int i=1;i<=n;++i) scanf("%d", &a[i]);
	memset(use, 0, sizeof(use));
	scanf("%d%d", &xx,&yy);
	dfs(1, yy); ansy = bowl;
	bowl = 0;
	dfs(1, xx-1); ansx = bowl; 
	printf("%d\n", ansy - ansx);
	return 0;
}

发表于 | 阅读次数:
字数统计: 292 字

这些优化方法都是从网络上找到的一些奇奇怪怪的方法。

  1. 常数用const定义而不是#define， 可以大大提升程序运行效率。
  2. 线段树或者其他可以将乘法运算或者加法运算写成二进制操作的话就写成二进制操作，不仅仅是（zhuang bi）而且真的会快的。
  3. 一些简单的判断使用三目运算符而不是if， 可以节省时间。
  4. long long 的运算时间要大于 int 的运算时间。
  5. ST表里的log函数进行先处理，而不是在程序中使用log函数。
  6. 模数设置成const。
  7. 读入优化+输出优化必备
  8. 调用频繁的函数加上 inline 来加快函数的展开速度
  9. 一些库函数手写常数要比stl常数小
  10. 在大循环上的循环终止变量上加上register标志
  11. bool的运算速度要小于int
  12. 取模优化， 加取模与减取模
  13. 选择前自增， ++i 而不是 i++
  14. 判断奇偶性使用位运算n&1来实现

持续补充中

发表于 | 阅读次数:
字数统计: 1,294 字

JZYZOJ

Sep/17 P1219 一道图论的题， 可以DP拿来做， 大概就是维护一个在当前节点所遇到的最小值， 和总价值的最优值。LA 3882 一道递推题，voj的数据挂掉了，于是到Poj上过了一下。这道题是来求约瑟夫问题， 进行倒退，f[n] 中储存的值为如果0为幸存者的话， 第一个点的人的序号。大概就是下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
using namespace std;
long long n,m,k,f;
int main() {
	while(scanf("%lld%lld%lld", &n,&k,&m) == 3 &&n) {
		f = 0;
		for (long long i=2;i<=n;++i) f=(f+k)%i;
		f = (m-k+1+f)%n;
		if(f<=0)f+=n;
		printf("%lld\n",f);
	}
}

Sep/18 P1828 一道图论题， 大概就是求一个拓扑序， 在进行拓扑序的同时维护一个数组， 来保证是每个节点通过拓扑序中最大的消耗值， 然后维护答案即可。　P1843 一道差分， 区间的大量操作， 然后求区间的最后结果很多时候都可以用差分来做 P1888 一道二分题， 注意如果题中出现最大的最小值或者最小的最大值的时候就要往二分的方向进行考虑， 二分+判定的效率是很高的

Sep/19 P1822 一个很水的单调栈的题， 一共建6个栈然后进行模拟即可
P1895 一道可以用差分来做的题， 使a数组都变成一样的， 等同于将f数组除第一项以外都变成0。因为对a数组的区间加减1的效果相当于对f[i], f[j+1]两项进行操作， 其实就是f数组中正负两个全部的权值和中绝对值最大的那一种数会消耗更多的操作， 而第一个就是一个没用的可以当做f[i]前一项的量， 而且a数组最后的值取决于f[1]里的值， 由于f正负权值和的绝对值之差这么多种可能可以在f[1]上加减， 所以a的数列的可能出现的情况就为 abs(p-q)+1 种 P1835 一道贪心， 区间内操作， 直接按照右端点进行排序， 左端点作为次要特征，然后优先填满右端点的那几个， 这样就能保证贪心是正确的.

Sep/20 P1824 一道搜索题， 第一遍打TLE了， 很懵逼， 我从每一个老师开始BFS显然效率十分低， 最后还是看了下学弟的代码（丢人）。 我承认自己搜索不是很好， 所以以后要注意锻炼这种题， 大概就是把所有的1点入队 ， 然后维持一个时间变量， 这个量的维护很巧妙：

1
2
3
4
5
int flag = tail;
for (int i=head; i<=tail; ++i) {
		if (i > flag)  flag = tail,++ans;
    	. . . 
}

这样可以维护BFS的层次， ans里存的就是第几层拓展。P1813 这是一道数论题， 该来的总算是来了， 不过自己想是根本没有思路的。详情请参考题解。

Sep/21 今天键盘到了， 感觉还行， ikbc C104 红轴感觉就是轻， 而且真的会出现误触的情况。 以后还要好好练习打字， 不能辜负这个键盘。 加油吧， 为了自己的梦想努力一把！
今天一上午把treap树过了一下， 把之前的东西整理了一下， 学习了一下fread。下午计划打几道题
下午沉浸在机械键盘的舒适感中无法自拔， 于是乎又没刷多少题。过掉了一道这个题 P1871 一道迭代加深搜索， 然而并没有一眼看出来。 还是因为太菜了 . . .

Sep/22 上午做了一道 P1866 自己想出来的，等下再写下思路. 这其实是一道很水的一个模拟吧， 其实也不很好给这道题分一个类别。 思路大概就是先找到第一个满足情况的奶牛然后删除之后的所有的这个奶牛的周期， 直到全部删完为止。

Sep/25 三天假期结束， 时间越来越上。 这星期打算把往年的Noip题都再重新做一遍， 来大概熟悉一下题的难度。今天做了Noip2017的前2道题， 第一题就是那一道很弱智的小学奥数题。 第二题就是时间复杂度这一道十分恶心的一个大模拟。 然而这题真的很恶心， 会有很多的细节， 像这种题在今年的Noip上应该还会出现。要提高自己的代码能力了。 虽然这种题好像思维难度并不是很大， 但是仍然会占据很大一部分的分数。 晚上在裕神的指导下A掉了一道锣鼓月赛的水题 P4889 kls与flag 不得不说这次洛谷的月赛是真的比较水， 技术含量比较低. . . 这就是一个比较水的模拟题， 离散化一下就好啦，可能还会有一点斥容的思想。反正就是很水的一道题

发表于 | 阅读次数:
字数统计: 920 字

​ 高一已经过去， 高二已经到来。 高中的生活也已经过去了1/3。 我不会对着过去的一年的迅速而感到惊叹， 而应该总结得失， 然后从心 出发。
在过去的一年中，我从一个不是十分优秀的学校来到了这个十分优秀的班集体中。 在当时心中最多的是对未知的恐惧。 三年初中安定的学习与生活被新的节奏所打乱， 让我们不知所措。 人们总是害怕不安定， 那时的我， 学着小心翼翼的去接触身边的未知的一切， 心中还充满着一些不自信的小自卑。 这种状态一直持续到我第一次考试。
我记得很清， 那次我考了全班30多名， 不很优秀。 但我还是十分的兴奋， 因为我知道， 在这里， 我不用被倒着数。 接下来的一段日子， 在我的记忆里是都是混乱的， 就像我那时的生活。 就好像自己还生活在初中， 上上下下， 沉沉浮浮， 麻木， 没有斗志。 记得有几时突然惊醒， 却又开始抱怨起周围的一切， 人、 物、 甚至环境。 认为仿佛自己成绩的好坏与这些有着十分必然的关系， 再到后来， 不知不觉就到了高一下半学期， 在那段日子里， 自己心中所想的与自己的实际的成绩之间的差距让我陷入深深的焦虑与不安， 就好像学长们说的一样，——浮躁却无所作为。 就在这学期即将结束之际， 我有幸得到了一个机会， 可以到外边的世界去看看， 于是我就去了。 在那里， 我真正见识到了“平台”与“眼界”的威力： 在一些地方， 初二的学生就已经保送清华。 他们可以接触到最新，最优秀的资源。 对比之下， 就感到自己的生活十分不公， 好像又要开始怨天尤人。 但是就焦作而言， 搞信息竞赛的不止焦作一中一个， 但是三中就没有像一中这么好的资源， 这么大的平台去和其他学校，机构去合作。 所以说， “平台”是自己打拼出来的。
说完了一年的回首， 再讲一下这一年的展望。
河南省， 2018年高考考生的数量达到了98万人。 约占全国高考总人数的1/10。 这是一个多么可怕的数量。 可是算下来我只剩下700天左右的时间去面对了。 在接下来的一段日子里。 如果发觉自己生活的不够好， 还请不要总是抱怨环境的不公。你也许确实应该感到生气， 但应该是生自己的气， 你为什么会和这些你让你感到气愤的人在一起？ 归根到底还是因为你自身的实力的问题。 你若奋斗， 若能升到高一层次的平台。 那里的环境自然就会好些。 与其咒骂身边的种种的不合你意， 为什么不静下心来提升自己的能力， 来摆脱这种你所讨厌的环境呢， 这是才是你最为明智的选择。
这篇文章也没有展望太多， 太远。 因为知道如果静不下心来去提升自己， 那些东西都将会是空谈。 希望如果日后再次浮躁之时，能想起这篇文章。 然后沉下心来， 提升自己， 摆脱困境。
——写于2018\8\31

发表于 | 阅读次数:
字数统计: 767 字

这只是一个板子， 想要有解释？ 想什么呢， 背就好了啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct Wint:vector<int>
{
    Wint(int n=0)
    {
        push_back(n);
        check();
    }
    Wint& check()
    {
        while(!empty()&&!back())pop_back();
        if(empty())return *this;
        for(int i=1; i<size(); ++i)
        {
            (*this)[i]+=(*this)[i-1]/10;
            (*this)[i-1]%=10;
        }
        while(back()>=10)
        {
            push_back(back()/10);
            (*this)[size()-2]%=10;
        }
        return *this;
    }
};
istream& operator>>(istream &is,Wint &n)
{
    string s;
    is>>s;
    n.clear();
    for(int i=s.size()-1; i>=0; --i)n.push_back(s[i]-'0');
    return is;
}
ostream& operator<<(ostream &os,const Wint &n)
{
    if(n.empty())os<<0;
    for(int i=n.size()-1; i>=0; --i)os<<n[i];
    return os;
}
bool operator!=(const Wint &a,const Wint &b)
{
    if(a.size()!=b.size())return 1;
    for(int i=a.size()-1; i>=0; --i)
        if(a[i]!=b[i])return 1;
    return 0;
}
bool operator==(const Wint &a,const Wint &b)
{
    return !(a!=b);
}
bool operator<(const Wint &a,const Wint &b)
{
    if(a.size()!=b.size())return a.size()<b.size();
    for(int i=a.size()-1; i>=0; --i)
        if(a[i]!=b[i])return a[i]<b[i];
    return 0;
}
bool operator>(const Wint &a,const Wint &b)
{
    return b<a;
}
bool operator<=(const Wint &a,const Wint &b)
{
    return !(a>b);
}
bool operator>=(const Wint &a,const Wint &b)
{
    return !(a<b);
}
Wint& operator+=(Wint &a,const Wint &b)
{
    if(a.size()<b.size())a.resize(b.size());
    for(int i=0; i!=b.size(); ++i)a[i]+=b[i];
    return a.check();
}
Wint operator+(Wint a,const Wint &b)
{
    return a+=b;
}
Wint& operator-=(Wint &a,Wint b)
{
    if(a<b)swap(a,b);
    for(int i=0; i!=b.size(); a[i]-=b[i],++i)
        if(a[i]<b[i])
        {
            int j=i+1;
            while(!a[j])++j;
            while(j>i)
            {
                --a[j];
                a[--j]+=10;
            }
        }
    return a.check();
}
Wint operator-(Wint a,const Wint &b)
{
    return a-=b;
}
Wint operator*(const Wint &a,const Wint &b)
{
    Wint n;
    n.assign(a.size()+b.size()-1,0);
    for(int i=0; i!=a.size(); ++i)
        for(int j=0; j!=b.size(); ++j)
            n[i+j]+=a[i]*b[j];
    return n.check();
}
Wint& operator*=(Wint &a,const Wint &b)
{
    return a=a*b;
}
Wint divmod(Wint &a,const Wint &b)
{
    Wint ans;
    for(int t=a.size()-b.size(); a>=b; --t)
    {
        Wint d;
        d.assign(t+1,0);
        d.back()=1;
        Wint c=b*d;
        while(a>=c)
        {
            a-=c;
            ans+=d;
        }
    }
    return ans;
}
Wint operator/(Wint a,const Wint &b)
{
    return divmod(a,b);
}
Wint& operator/=(Wint &a,const Wint &b)
{
    return a=a/b;
}
Wint& operator%=(Wint &a,const Wint &b)
{
    divmod(a,b);
    return a;
}
Wint operator%(Wint a,const Wint &b)
{
    return a%=b;
}
Wint pow(const Wint &n,const Wint &k)
{
    if(k.empty())return 1;
    if(k==2)return n*n;
    if(k.back()%2)return n*pow(n,k-1);
    return pow(pow(n,k/2),2);
}
int main()
{
    Wint a,b;
    cin>>a>>b;
    cout<<(a<b)<<endl
        <<(a==b)<<endl
        <<a+b<<endl
        <<a-b<<endl
        <<a*b<<endl
        <<a/b<<endl
        <<a%b<<endl
        <<pow(a,b);//有可能小数减大数时要自己写一下if(a<b) cout<<'-';
	return 0;
}

亲测能用， 可以解决高精度的大部分问题。

发表于 | 阅读次数:
字数统计: 312 字

这个blog是经常犯的小错误的总结， 避免这种错误的发生

  1. 数组正好开在n的最大值， 如果数据在n的话会被卡掉一些分数， 差不多开在 maxn+10 左右。
  2. 在dfs的时候剪枝要经过考虑， 不然很可能会剪掉一个正确的答案
  3. 对浮点数操作的时候一定要小心， 不然很有可能丢失精度
  4. 在用 printf 或者 scanf 的输入输出的时候， 一定记得吧格式符换成对应的， 比如 longlong 在 win 下 和 linux 下的差异
  5. topsort或者其他图论题中， 如果需要维持队列的话， 记得要把堆顶弹出， 防止出现死循环的情况发生。
  6. 全局变量与函数内部变量冲突， 出现一些不很好找的Bug
  7. 矩阵中n，m的顺序尤其是样例中n=m的情况会导致即使你把nm搞反了但是还是能过样例的情况发生
  8. 最短路的时候dis数组的初值
  9. if中判断 == 写成 = 不会报错， 但是会很浪费时间来照这个小错误， 不容易发现的错误
  10. 在define后面加 ‘；’