Dylan's Blog
Dylan's Blog

白衣苍狗

一首小诗

 发布于  收录于 日志

我喜欢你，毫无理由地

岚

我喜欢你，毫无理由地
若要举出些什么，那将是：
遇见时你张开又合拢的手指，
道别时你摇动的手腕，
你浅色的明眸，
和你头发恰到好处的鬈曲。

——谨以此诗献给

阅读全文
HTML

SG函数

 发布于  收录于 OI

SG function & SG theorem

文中证明皆为擢发数根所得，纰漏在所难免，请不吝赐教。

先介绍一些相关的定义。

ICG （公平组合游戏）

抽象模型：

给定一个有向无环图和一个起始顶点上的一枚棋子，玩家交替的将这枚棋子沿有向边进行移动，无法移动者判负。问是否有必胜策略。

P-position & N-position

定义

P：当前局面先手必败 N：当前局面先手必胜

以上都是指双方采取最优策略的情况。

性质

  1. 无法进行任何移动的局面（terminal position）是P-position；（死局，败）
  2. 可以移动到P-position的局面是N-position；（有办法让对方败）
  3. 所有移动都导致N-position的局面是P-position。（无路可走）

operation mex

mex（minimal excludant）是定义在整数集合上的操作。它的自变量是任意整数集合，函数值是不属于该集合的最小自然数。

阅读全文
OIC++博弈论SGNimICG

丑陋的高精度模板

 发布于  收录于 OI
  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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299

/*
high precision num

log:outbit is worth improving
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cctype>
using namespace std;
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
T Min(const T& a,const T& b){return a<b?a:b;}
const int bit=10000;
const int bitl=4;
const int maxbit=10003;
typedef int lint;
struct num
{
	lint ary[maxbit],len;
	bool up0;
	void set0()
	{
		up0=true;
		len=1;
		memset(ary,0,sizeof(ary));
	}
	bool is0()
	{
		return len==1&&ary[len]==0;
	}
	num()
	{
		up0=true;
		len=1;
		set0();
		//memset(ary,0,sizeof(ary));
	}
	num(int w)
	{
		set0();
		len=0;
		if(w==0)return;
		if(w<0)w=-w,up0=false;
		while(w)
		{
			ary[++len]=w%bit;
			w/=bit;
		}
	}

	lint& operator[](const int& pos)
	{
		return ary[pos];
	}
	void outbit(int x)
	{
		int tmpbit=bit/10;
		while(tmpbit>x)
			tmpbit/=10,putchar('0');
		while(tmpbit)
		{
			putchar(x/tmpbit+48);
			x%=tmpbit;
			tmpbit/=10;
		}
		//putchar('\n');
	}
	void input()
	{
		set0();
		char s[maxbit],r;
		int lens=0;
		do
		{r=getchar();}
		while(r!='-'&&!isdigit(r));
		if(r=='-')up0=false,r=getchar();
		if(!isdigit(r))
		{
			up0=true;
			return;
		}
		len=0;
		while(isdigit(r))
		{
			s[++lens]=r;
			r=getchar();
		}
		ungetc(r,stdin);
		for(int i=lens;i>=1;--i)
		{
			int j=Max(1,i-bitl+1);
			int tmp=0;
			for(int k=j;k<=i;++k)
				tmp=tmp*10+s[k]-48;
			ary[++len]=tmp;
			i=j;
		}
		while(len!=1&&!ary[len])
			--len;
		if(len==1&&ary[1]==0)
			up0=true;
	}
	void output()
	{
		if(!up0)putchar('-');
		printf("%d",ary[len]);
		for(int i=len-1;i>=1;--i)
			outbit(ary[i]);
	}
};
inline num operator-(num a)
{
	if(a.len==1&&a[1]==0)
		return a;
	a.up0=!a.up0;
	return a;
}
inline bool operator==(num a,num b)
{
	if(a.len!=b.len)return false;
	if(a.up0!=b.up0)return false;
	for(int i=1;i<=a.len;++i)
	{
		if(a[i]!=b[i])
			return false;
	}
	return true;

inline bool operator!=(num a,num b)
{
	return !(a==b);
}
inline bool operator>(num a,num b)
{
	if(a.up0!=b.up0)return a.up0;
	if(!a.up0)
	{
		a.up0=true;
		b.up0=true;
		return !(a>b||a==b);
	}
	if(a.len!=b.len)return a.len>b.len;
	for(int i=a.len;i>=1;--i)
	{
		if(a[i]!=b[i])
			return a[i]>b[i];
	}
	return false;
}
inline bool operator>=(num a,num b)
{
	return a==b||a>b;
}
inline bool operator<(num a,num b)
{
	return !(a>=b);
}
inline bool operator<=(num a,num b)
{
	return a<b||a==b;
}

num add(num a,num b)
{
	num ans;
	ans.len=Max(a.len,b.len)+1;
	for(int i=1;i<=ans.len;++i)
	{
		ans[i]+=a[i]+b[i];
		if(ans[i]>=bit)	
		{
			ans[i+1]+=ans[i]/bit;
			ans[i]%=bit;
		}
	}
	while(!ans[ans.len]&&ans.len!=1)--ans.len;
	return ans;
}
num sub(num a,num b)
{
	if(a<b)return -(sub(b,a));
	num ans;
	if(a==b)return ans;
	ans.len=Max(a.len,b.len);
	for(int i=1;i<=ans.len;++i)
	{
		if(a[i]<b[i])
		{
			--a[i+1];
			a[i]+=bit;
		}
		ans[i]=a[i]-b[i];
	}
	while(ans.len!=1&&!ans[ans.len])
		--ans.len;
	return ans;
}
num mul(num a,num b)
{
	num ans;
	ans.len=a.len+b.len;
	for(int i=1;i<=a.len;++i)
	{
		for(int j=1;j<=b.len;++j)
		{
			ans[i+j-1]+=a[i]*b[j];
			if(ans[i+j-1]>=bit)
			{
				ans[i+j]+=ans[i+j-1]/bit;
				ans[i+j-1]%=bit;
			}
		}
	}
	while(!ans[ans.len]&&ans.len!=1)--ans.len;
	return ans;
}
/*
a>0,b>0

a+b=a+b
a+(-b)=a-b
(-a)+b=b-a
(-a)+(-b)=-(a+b)
a-b=a-b;
a-(-b)=a+b
(-a)-b=-(a+b)
(-a)-(-b)=b-a
*/
num operator+(num a,num b)
{
	if(a.up0&&b.up0)
		return add(a,b);
	if(a.up0&&!b.up0)
		return sub(a,-b);
	if(b.up0&&!a.up0)
		return sub(b,-a);
	if((!b.up0)&&(!a.up0))
		return -(add(-a,-b));
}

num operator-(num a,num b)
{
	if(a.up0&&b.up0)
		return sub(a,b);
	if(a.up0&&!b.up0)
		return add(a,-b);
	if(b.up0&&!a.up0)
		return -add(-a,b);
	if((!b.up0)&&(!a.up0))
		return sub(-b,-a);
}
/*

a*b=(-a)*(-b)=a*b
a*(-b)=(-a)*b=-(a*b) 
*/
num operator*(num a,num b)
{
	if(a.is0())return a;
	if(b.is0())return b;
	if(a.up0==b.up0)
	{
		if(a.up0)
			return mul(a,b);
		else return mul(-a,-b);
	}
	else 
	{
		if(a.up0)return -mul(a,-b);
		if(b.up0)return -mul(-a,b);
	}
}
num op(num a,char r,num b)
{
	if(r=='+')return a+b;
	if(r=='-')return a-b;
}
int main()
{
	num x,y,ans;
	while(1)
	{
		x.input();
		y.input();
		cout<<"x:";
		x.output();
		cout<<endl;
		cout<<"y:";
		y.output();
		cout<<endl;
		ans=x*y;
		cout<<"x*y=";ans.output();
		cout<<endl;
	}
	return 0;
}
阅读全文
OIC++高精度

实用技巧

 发布于  收录于 OI

实用技巧

读入/输出优化

“天下武功，无坚不破，唯快不破。”

​ ——忘了出自哪里

众所周知，越是方便的读入输出方法一般越慢。所以大部分C++选手会使用scanf()&printf()代替cin&cout。

但是面对某些大得变态不太友好的数据，scanf也会显得无能为力。

所以，能不能更给力一点呢？

——自己动手，丰衣足食。

由于OI中面对的输入&输出对象一般为数字，所以通常针对数字进行优化。即对于输入数据全为整数的情况，逐个读入字符，如果是数字则累加，否则将之前的结果作为一个数返回。

阅读全文
OIC++

动态规划——背包问题

 发布于  收录于 OI

动态规划——背包问题

01背包

数组压成一维。

例题：luogu2871

 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

//01bag
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
template<typename T>
void read(T& w)
{
	char r;
	for(r=getchar();r<48||r>57;r=getchar());
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
const int maxn=3413;
const int maxm=12883;
int n,m,v[maxn],w[maxn];
void input()
{
	read(n),read(m);
	for(int i=1;i<=n;++i)
	{
		read(w[i]),read(v[i]);
	}
}
int f[maxm];
void solve()
{
	for(int i=1;i<=n;++i)
	{
		for(int j=m;j>=w[i];--j)
		{
			if(f[j-w[i]]+v[i]>f[j])
				f[j]=f[j-w[i]]+v[i];
		}
	}
}
int main()
{
	freopen("luogu2871_1.in","r",stdin);
	//freopen("luogu2871.out","w",stdout);
	input();
	solve();
	printf("%d\n",f[m]);
	return 0;
}

输出方案

这部分内容还不完整。

 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

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=103;
int n,m,v[maxn];
int f[maxn];
bool tag[maxn][maxn];
void solve()
{
	for(int i=1;i<=n;++i)
	{
		for(int j=m;j>=v[i];--j)
		{
			if(f[j-v[i]]+v[i]>f[j])
			{
				f[j]=f[j-v[i]]+v[i];
				tag[i][j]=true;
			}
		}
	}
}
int ans[maxn],ak;
void print(int pos,int vv)
{
	if(tag[pos][vv])
	{
		ans[++ak]=v[pos];
		vv-=v[pos];
	}
	if(pos==1)
	{
		for(int i=ak;i>=1;--i)
		{
			printf("%d ",ans[i]);
		}
		putchar('\n');
	}
	else print(pos-1,vv);
}
void input()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&v[i]);
	}
}
int main()
{
	input();
	solve();
	for(int i=n;i>=1;--i)
	{
		
	}
	return 0;
}

多重背包

每种物品有数量限制。

阅读全文
动态规划背包C++OI

Hexo + git + Coding Pages 博客

 发布于  收录于 笔记

Hexo + Git + Coding Pages = Blog

前置条件

git+命令行(linux)

环境配置

以下操作基于Windows

git安装与配置

  1. 下载git
  2. 安装与配置：略

Nodejs安装与配置

  1. 下载Nodejs

  2. 安装Nodejs

在安装时界面下方有一个"Add to PATH"的选项，最好勾上；或者也可以安装完成后自己手动添加环境变量。

安装依赖包

1

npm install

hexo安装

1

npm install -g hexo

npm是Node的包管理工具，后面还要多次用到它~ 其中的参数-g是将hexo安装到全局，如果不加的话则默认只会安装到当前目录

阅读全文
GitHexoNodejs

用栈实现简单表达式求值

 发布于  收录于 OI

用栈实现简单表达式求值

准备

建立两个栈：操作数栈+操作符栈

步骤

没有括号的情况

注意：弹出时两个操作数的顺序要反一下，以确保运算的顺序和输入的顺序一致

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

while(从左到右读入操作数/操作符)
{
    if(is 操作数x)
    {
        操作数栈.push(x);
    }
    if(is 操作符op)
    {
        while(优先级: op <= 操作符栈.top)
        {
            opt=操作符栈.top；
            操作符栈.pop;
            b=操作数栈.top;操作数栈.pop;   
            a=操作数栈.top;操作数栈.pop;
            操作数栈.push( 运算： a opt b );
        }
        操作符栈.push(op);
    }
}

处理括号

对于’(’：遇到时就加入操作符栈

对于’)’：遇到时不断弹出操作符和操作数，直到操作符栈顶为’)‘时将它弹出。（也就是计算这两个括号之间的表达式）

阅读全文
栈表达式OIC++

动态规划——最长上升子序列

 发布于  收录于 OI

最长上升子序列

O(n^2)

f[i]=max{f[j]+1}, a[j]<=a[i]

O(nlogn)

将思维过程转换一下。 假设i前面存在的上升子序列长度为1~len 那么只要将a[i]接到某个比它小的数a[j]后面，就构成了一个新的子序列，且f[i]=f[j]+1 想要f[i]尽量大，要求f[j]尽量大 一种策略是从len开始往前找，对于某个len，可能有j1,j2,…jm都满足f[jx]=len 那么只要其中有一个jx，使得a[jx]<=a[i]，就可以将i接到它后面 很明显，最有可能的jx是min{jn} 所以有了如下结论

阅读全文
动态规划子序列C++OI

左偏树

 发布于  收录于 OI

左偏树

这篇笔记尚不完整。

使用队列的左偏树

注意：叶节点dis=-1,单儿子节点dis=0

  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

template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
template<typename T,int size>
struct QUE
{
	T ary[size+1];
	int f,t,cnt;
	void clear(){f=t=cnt=0;}
	bool empty(){return cnt==0;}
	void push(const T& w)
	{
		ary[t++]=w,++cnt;
		if(t==size)t=0;
	}
	void pop(){++f,--cnt;if(f==size)f=0;}
	T front(){return ary[f];}
};
template<typename T,int size,bool comp(const T& a,const T& b)>
struct LTREE
{
	T v[size+1];
	int l[size+1],r[size+1];
	int d[size+1];
	int f[size+1];
	QUE<int,size> id;
	int t;
	void clear()
	{
		t=0;
		id.clear();
		memset(v,0,(n+1)*sizeof(int));
		memset(l,0,(n+1)*sizeof(int));
		memset(r,0,(n+1)*sizeof(int));
		memset(d,0,(n+1)*sizeof(int));
		memset(f,0,(n+1)*sizeof(int));
		d[0]=-1;
	}
	void update(int x)
	{
		//...
	}
	int merge(int x,int y)//merge y to x
	{
		if(x==y)return x;
		if(!x)return y;
		if(!y)return x;
		if(comp(v[y],v[x]))Swap(x,y);
		r[x]=merge(r[x],y);
		f[r[x]]=x;
		update(x);
		if(d[l[x]]<d[r[x]])Swap(l[x],r[x]);	
		//if(r[x])
		d[x]=d[r[x]]+1;
		//else d[x]=0;
		return x;
	}
	int pop(int x)// x must be a root
	{
		f[l[x]]=l[x],f[r[x]]=r[x];
		id.push(x);
		return merge(l[x],r[x]);
	}
	int findf(int x)
	{
		if(x==f[x])return x;
		else return findf(f[x]);
	}
	int push(int x,const T& w)
	{
		x=findf(x);
		int now;
		if(!q.empty())now=q.front();
		else now=++t;
		v[now]=w;
		f[now]=now;
		l[now]=r[now]=d[now]=0;
		return merge(x,now);
	}
	void balance(int x)//from x to  top
	{
		if(d[l[x]]<d[r[x]])Swap(l[x],r[x]);
		if(d[x]!=d[r[x]]+1&&f[x]!=x)
			d[x]=d[r[x]]+1,balance(f[x]);
	}
	void del(int x)
	{
		int fa=f[x];
		int son=merge(l[x],r[x]);		
		if(r[fa]==x)r[fa]=son;
		if(l[fa]==x)l[fa]=son;
		f[son]=fa;
		balance(fa);
	}
	void makeTree(int* ary,int n)//used queue in O(n)
	{
		static QUE<int,size> q;
		q.clear();
		for(int i=1;i<=n;++i)
			q.push(add(ary[i]));
		while(q.cnt!=1)
		{
			int t1=q.front();q.pop();
			int t2=q.front();q.pop();
			q.push(merge(t1,t2));
		}
		//need to be completed
	}
};

参考资料

不错的文章 另一个不错的文章

阅读全文
左偏树树队列数据结构OIC++
0%