发表于 | 更新于 | 评论数：

现在菜的不行不行的，也就会个fhq_treap板子，但是还是希望能够熟练掌握平衡树

先对着kuangbin的刷刷吧

现在就只会用fhq_treap的操作

A Simple Problem with Integers POJ - 3468
这个玩意就是明确的告诉你，平衡树完全可以执行线段树的操作，代码也很简单打个lazytag

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
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
typedef long long ll;
const int N=300005;
long long s[N];
int l[N],r[N],rt,sz[N],rnd[N],a[N],cnt,f[N];
void up(int p)
{
	sz[p]=sz[l[p]]+sz[r[p]]+1;
	s[p]=s[l[p]]+s[r[p]]+a[p];
}
void lazy(int p)
{
	if(f[p])
	{
		s[l[p]]+=1LL*sz[l[p]]*f[p];
		s[r[p]]+=1LL*sz[r[p]]*f[p];
		f[l[p]]+=f[p];
		f[r[p]]+=f[p];
		a[l[p]]+=f[p];
		a[r[p]]+=f[p];
		f[p]=0;
	}
}
void split(int p,int k,int& x,int& y)
{
	if(!p) x=y=0;
	else
	{
		lazy(p);
		if(k>sz[l[p]])
		x=p,split(r[p],k-sz[l[p]]-1,r[p],y);
		else
		y=p,split(l[p],k,x,l[p]);
		up(p);
	}
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	else
	{
		lazy(x),lazy(y);
		if(rnd[x]<rnd[y])
		{r[x]=merge(r[x],y),up(x);return x;}
		else
		{l[y]=merge(x,l[y]),up(y);return y;}
	}
}
int npt(ll x)
{
	a[++cnt]=x;
	sz[cnt]=1;
	rnd[cnt]=rand();
	s[cnt]=x;
	return cnt;
}
void change(int p,int x,int y,int z)
{
	int aa,b,c;
	split(rt,y,aa,c);
	split(aa,x-1,aa,b);
	f[b]+=z;
	a[b]+=z;
	rt=merge(merge(aa,b),c);
}
void sum(int p,int x,int y)
{
	int aa,b,c;
	split(rt,y,aa,c);
	split(aa,x-1,aa,b);
	printf("%lld\n",s[b]);
	rt=merge(merge(aa,b),c);
}
int main()
{
	srand(time(0));
	int n,m,x,y,z;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&x),rt=merge(rt,npt(x));
	while(m--)
	{
		char c;
		scanf(" \n%c",&c);
		if(c=='Q')
		{
			scanf("%d%d",&x,&y);
			sum(rt,x,y);
		}	
		else
		{
			scanf("%d%d%d",&x,&y,&z);
			change(rt,x,y,z);
		}
	}	
}

差点没卡过去，还是int快啊。。。。
SuperMemo POJ - 3580
真的恶心好多操作啊，感觉单拿出来都是弱鸡合在一起就变得有点恶心(虽然也是弱鸡)
区间搬运就是直接%一下乱搬就行了，这个地方注意一下我们如果对树进行过操作更新最小值的话要在up操作里面加上 

1
m[p]=a[p];

这样就行了，我最初还以为tmd要dfs遍历修改一下结果TLE，这样就能过了。
这里出现了两个lazy但是我感觉也没有啥先后顺序吧，翻转和加和谁在前面好像没差啊 

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
#include <cstdio>
#include <iostream>
#include <ctime>
#include <cstring>
using namespace std;
const int N=500005;
int l[N],r[N],cnt,rt,f1[N],f2[N],a[N],m[N],rnd[N],sz[N];
char ss[105];
void lazy(int p)
{
	if(f2[p])
	{
		swap(l[p],r[p]);
		f2[l[p]]^=1;
		f2[r[p]]^=1;
		f2[p]=0;
	}
	if(f1[p])
	{
		f1[l[p]]+=f1[p];
		f1[r[p]]+=f1[p];
		a[l[p]]+=f1[p];
		a[r[p]]+=f1[p];
		m[l[p]]+=f1[p];
		m[r[p]]+=f1[p];
		f1[p]=0;
	}
}
void out(int p)
{
//	lazy(p);
	if(l[p])
	out(l[p]);
	cout<<a[p]<<" ";
	if(r[p])
	out(r[p]);
}
void up(int p)
{
	sz[p]=sz[l[p]]+sz[r[p]]+1;
	m[p]=a[p];
	if(l[p])
	m[p]=min(m[p],m[l[p]]);
	if(r[p])
	m[p]=min(m[p],m[r[p]]); 
//	cout<<p<<" "<<m[p]<<"\n";
}
void split(int p,int k,int& x,int& y)
{
	if(!p) x=y=0;
	else
	{
		lazy(p);
		if(k>sz[l[p]])
		x=p,split(r[p],k-sz[l[p]]-1,r[p],y);
		else
		y=p,split(l[p],k,x,l[p]);
		up(p);
	}
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	else
	{
		lazy(x),lazy(y);
		if(rnd[x]<rnd[y])
		{r[x]=merge(r[x],y),up(x);return x;}
		else
		{l[y]=merge(x,l[y]),up(y);return y;}
	}
}
int npt(int x)
{
	a[++cnt]=x;
	rnd[cnt]=rand();
	sz[cnt]=1;
	m[cnt]=x;
	return cnt;
}
void add(int x,int y,int z)
{
	int aa,bb,cc;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	f1[bb]+=z;
	a[bb]+=z;
	m[bb]+=z;
	rt=merge(merge(aa,bb),cc);
}
void reve(int x,int y)
{
	int aa,bb,cc;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	f2[bb]^=1;
	rt=merge(merge(aa,bb),cc);
}
void revo(int x,int y,int z)
{
	int aa,bb,cc,dd;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	split(bb,y-x+1-z,bb,dd);
	rt=merge(merge(aa,merge(dd,bb)),cc);
}
void ins(int x,int y)
{
	int aa,bb;
	split(rt,x,aa,bb);
	rt=merge(merge(aa,npt(y)),bb);
}
void del(int x)
{
	int aa,bb,cc;
	split(rt,x,aa,cc);
	split(aa,x-1,aa,bb);
	rt=merge(aa,cc);
}
void minn(int x,int y)
{
	int aa,bb,cc;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	//cout<<aa<<" "<<bb<<" "<<cc<<"\n";
	printf("%d\n",m[bb]);
	rt=merge(merge(aa,bb),cc);
}
int main()
{
	srand(19260817);
	int n,x,mm,y,z;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&x),rt=merge(rt,npt(x));
	scanf("%d",&mm);
	while(mm--)
	{
		scanf("%s",ss+1);
		if(ss[1]=='A')
		{
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
		}
		else if(ss[1]=='R'&&ss[4]=='E')
		{
			scanf("%d%d",&x,&y);
			reve(x,y);
		}
		else if(ss[1]=='R'&&ss[4]=='O')
		{
			scanf("%d%d%d",&x,&y,&z);
			z%=(y-x+1);
			if(z==0)
			continue;
			revo(x,y,z);
		}
		else if(ss[1]=='I')
		{
			scanf("%d%d",&x,&y);
			ins(x,y);
		}
		else if(ss[1]=='D')
		{
			scanf("%d",&x);
			del(x);
		}
		else
		{
			scanf("%d%d",&x,&y);
			minn(x,y);
		}
	}
}
/*
10
1 2 3 4 5 6 7 8 9 10
15
ADD 4 8 3
MIN 5 7
MIN 7 10
REVERSE 2 5
MIN 2 6
MIN 2 3
INSERT 3 4
MIN 3 4
MIN 5 10
DELETE 6
MIN 3 5
MIN 4 4
REVOLVE 3 6 7
MIN 5 8
MIN 7 10
*/

Play with Chain HDU - 3487
水题比起上一题来说真的是放水不少了。。。就是有一个地方他会卡PE。。。
我们在中序遍历平衡树的时候注意最后不要有多余的空格然后就A了

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
#include <bits/stdc++.h>
using namespace std;
const int N=600005;
int sz[N],l[N],r[N],f[N],rnd[N],a[N],cnt,rt,jk,n;
char s[N];
int npt(int x)
{
	a[++cnt]=x;
	rnd[cnt]=rand();
	sz[cnt]=1;
	f[cnt]=l[cnt]=r[cnt]=0;
	return cnt;
}
void lazy(int p)
{
	if(f[p])
	{
		swap(l[p],r[p]);
		f[l[p]]^=1;
		f[r[p]]^=1;
		f[p]=0;
	}
}
void out(int p)
{
	lazy(p);
	if(l[p])
	out(l[p]);
	jk++;
	printf("%d%c",a[p],jk==n?'\n':' ');
	if(r[p])
	out(r[p]);
}
void up(int p)
{
	sz[p]=sz[l[p]]+sz[r[p]]+1;
}
void split(int p,int k,int& x,int& y)
{
	if(!p) x=y=0;
	else
	{
		lazy(p);
		if(k>sz[l[p]])
		x=p,split(r[p],k-sz[l[p]]-1,r[p],y);
		else
		y=p,split(l[p],k,x,l[p]);
		up(p);
	}
} 
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	else
	{
		lazy(x),lazy(y);
		if(rnd[x]<rnd[y])
		{r[x]=merge(r[x],y),up(x);return x;}
		else
		{l[y]=merge(x,l[y]),up(y);return y;}
	}
}
void cut(int x,int y,int z)
{
	int aa,bb,cc,dd,re,re1;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	re=merge(aa,cc);
	split(re,z,re,re1);
	rt=merge(merge(re,bb),re1);
}
void rev(int x,int y)
{
	int aa,bb,cc;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	f[bb]^=1;
	rt=merge(merge(aa,bb),cc);
}
int main()
{
	srand(19260817);
	int m,x,y,z;
	while(~scanf("%d%d",&n,&m))
	{
		if(n==m&&n==-1)
		break;
		rt=cnt=jk=0;
		for(int i=1;i<=n;i++)	
		rt=merge(rt,npt(i));
		while(m--)
		{
			scanf("%s",s+1);
			if(s[1]=='C')
			{
				scanf("%d%d%d",&x,&y,&z);
				cut(x,y,z);
			}
			else
			{
				scanf("%d%d",&x,&y);
				rev(x,y);
			}
		}
		out(rt);
	} 
}

发表于 | 评论数：

A - Minimum Integer(签到)

想清楚我直接累加会超时,我们就判断一下如果不在其中就直接输出否则就用右边的r的下一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll t;
	cin>>t;
	while(t--)
	{
		ll x,y,z;
		cin>>x>>y>>z;
		if(z<x||z>y)
		cout<<z<<"\n";
		else
		cout<<((y/z)+1)*z<<"\n";
	}
}

B - Accordion(模拟)

就是我们先找到最左边和最右边的[]然后再找到::最后从::中找|

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int ans=0,st,ed,f=0;
	string x;
	cin>>x;
	for(int i=0;i<x.size();i++)
	if(x[i]=='[')
	{
		st=i,f=1;
		break;
	}
	if(!f)
	return cout<<-1,0;
	f=0;
	for(int i=x.size()-1;i>st;i--)
	if(x[i]==']')
	{
		ed=i,f=1;
		break;
	}
	if(!f)
	return cout<<-1,0;
	f=0;
	for(int i=st;i<ed;i++)
	if(x[i]==':')
	{
		st=i,f=1;
		break;
	}
	if(!f)
	return cout<<-1,0;
	f=0;
	for(int i=ed;i>st;i--)
	if(x[i]==':')
	{
		ed=i,f=1;
		break;
	}
	if(!f)
	return cout<<-1,0;
	f=0;
	for(int i=st;i<=ed;i++)
	if(x[i]=='|')
	ans++;
	cout<<ans+4;
}

C - Strings Equalization(思维)

直接判断如果两个字符串有相同的字符那么就可以转换否则不能

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll bk1[305],bk2[305];
int main()
{
	ios::sync_with_stdio(0);
	ll t;
	cin>>t;
	while(t--)
	{
		string a,b;
		int f=0;
		cin>>a>>b;
		memset(bk1,0,sizeof(bk1));
		memset(bk2,0,sizeof(bk2));
		for(int i=0;i<a.size();i++)
		{
			bk1[a[i]]++,bk2[b[i]]++;
		}
		for(int i='a';i<='z';i++)
		if(bk1[i]&&bk2[i])
		{
			f=1;
			break;
		}
		if(f)
		puts("YES");
		else
		puts("NO");
	}
}

D - Knights(思维or构造)

思维就是WBWBWB这样的
构造的话就是一个一个放进去即可 

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105][105],bk[105][105],n;
int check(int x,int y)
{
	if(x>=1&&x<=n&&y>=1&&y<=n)
	return 1;
	else
	return 0;
}
void dye(int x,int y)
{
	if(!check(x,y))
	return;
	if(check(x-2,y-1)&&!bk[x-2][y-1])
	{
		bk[x-2][y-1]=1;
		a[x-2][y-1]=!a[x][y];
		dye(x-2,y-1);
	}
	if(check(x-2,y+1)&&!bk[x-2][y+1])
	{
		bk[x-2][y+1]=1;
		a[x-2][y+1]=!a[x][y];
		dye(x-2,y+1);
	}
	if(check(x-1,y-2)&&!bk[x-1][y-2])
	{
		bk[x-1][y-2]=1;
		a[x-1][y-2]=!a[x][y];
		dye(x-1,y-2);
	}
	if(check(x-1,y+2)&&!bk[x-1][y+2])
	{
		bk[x-1][y+2]=1;
		a[x-1][y+2]=!a[x][y];
		dye(x-1,y+2);
	}
	if(check(x+2,y-1)&&!bk[x+2][y-1])
	{
		bk[x+2][y-1]=1;
		a[x+2][y-1]=!a[x][y];
		dye(x+2,y-1);
	}
	if(check(x+2,y+1)&&!bk[x+2][y+1])
	{
		bk[x+2][y+1]=1;
		a[x+2][y+1]=!a[x][y];
		dye(x+2,y+1);
	}
	if(check(x+1,y-2)&&!bk[x+1][y-2])
	{
		bk[x+1][y-2]=1;
		a[x+1][y-2]=!a[x][y];
		dye(x+1,y-2);
	}
	if(check(x+1,y+2)&&!bk[x+1][y+2])
	{
		bk[x+1][y+2]=1;
		a[x+1][y+2]=!a[x][y];
		dye(x+1,y+2);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(!bk[i][j])
	{
		bk[i][j]=1;
		a[i][j]=1;
		dye(i,j);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		printf("%c",a[i][j]?'W':'B');
		printf("\n");
	}
}

或者直接思维即可 by dhz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

char s[1000], t[1000];
int main()
{
    int temp;
    cin >> temp;
    while (temp--) {
        cin >> s >> t;
        int len = strlen(s), flag = 0;
        for (int i = 0; i < len; i++)
            for (int j = 0; j < len; j++)
                if (s[i] == t[j]) {
                    flag = 1;
                    break;
                }
        cout << (flag ? "YES" : "NO") << endl;
    }
}

E - Pipes(思维)

我也没有啥的好方法，我就把每种可能进去的情况都想了一下然后走一下，可以发现就两行也走不了多少，直接递归走能走出来就ok了

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f,n,a[5][300005];
void go(int x,int y,int px,int py)
{
//	cout<<x<<" "<<y<<"\n";
	if(x>2||y>n||x==0||y==0)
	return;
	if(x==2&&y==n)
	{
		if(a[x][y]>=1&&a[x][y]<=2)
		{
			if(px==2&&py==n-1)
			f=1;
		}
		else
		{
			if(px==1&&py==n)
			f=1;
		}
		return;
	}
	if(a[x][y]>=1&&a[x][y]<=2)
	go(x,y+1,x,y);
	else
	{
		if(x==1)
		{
			if(px==1)
			{
				if(a[x+1][y]>2)
				go(x+1,y,x,y);
			}
			else
			go(x,y+1,x,y);
		}
		else
		{
			if(px==1)
			go(x,y+1,x,y);
			else
			{
				if(a[x-1][y]>2)
				go(x-1,y,x,y);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	ll t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=2;i++)
		for(int j=1;j<=n;j++)
		{
			char x;
			cin>>x;
			a[i][j]=x-'0';
		}
		f=0;
		go(1,1,1,1);
		if(f)
		cout<<"YES\n";
		else
		cout<<"NO\n";
	}

}

F - Save the Nature(二分)

二分裸题啊，nlog^2n 二分里面排序贪心

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
struct node
{
	ll id,v;
}jk[N],re[N];
ll f,lcmm,a,b;
ll aa[N],maxn,minn,mk[N],k,bk[N],mkk[N];
bool cmp1(node a,node b)
{
	return a.v>b.v;
}
ll check(ll x)
{
	double sum=0;
	for(int i=1;i<=x;i++)
	re[i]=jk[i];
	sort(re+1,re+1+x,cmp1);
	for(int i=1;i<=x;i++)
	sum+=aa[i]*re[i].v;
	return sum>=k*100LL;
}
bool cmp(ll a,ll b)
{
	return a>b;
}
int main()
{
	ios::sync_with_stdio(0);
	ll t;
	cin>>t;
	while(t--)
	{
		ll n,p=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		cin>>aa[i];
		for(int i=1;i<=n;i++)
		mk[i]=0;
		double x,y;
		cin>>x>>a>>y>>b>>k;
		for(int i=a;i<=n;i+=a)
		mk[i]+=x;
		for(int i=b;i<=n;i+=b)
		mk[i]+=y;
		for(int i=1;i<=n;i++)
		if(mk[i]>0)
		jk[++p]=(node){i,mk[i]};
		sort(aa+1,aa+1+n,cmp);
		ll l=1,r=p;
		while(r-l>1)
		{
			ll mid=(l+r)>>1;
			//cout<<mid<<"\n";
			if(check(mid))
			r=mid;
			else
			l=mid;
		}
		if(check(l))
		cout<<jk[l].id<<"\n";
		else if(check(r))
		cout<<jk[r].id<<"\n";
		else
		cout<<"-1\n";
	}
}

G - Anadi and Domino(N^N暴力)

直接搜索暴力枚举7个点都是几我们两个点是多少知道了那么我们筛子边也就知道了，对于图我们判断一下是否符合然后求个极值

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
#include <bits/stdc++.h>
using namespace std;
int mk[105][105],dye[105],n,m,ans,x,y,mp[105][105],mpp[105][105],bk[105][105];
void dfs(int cur)
{
	if(cur==n+1)
	{
		int jk=0;
//		for(int i=1;i<=n;i++)
//		cout<<dye[i]<<" ";
//		cout<<"\n";
		for(int i=1;i<=6;i++)
		for(int j=1;j<=6;j++)
		mk[i][j]=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		mpp[i][j]=mp[i][j];
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		if(mpp[i][j]||mpp[j][i])
		if(!mk[dye[i]][dye[j]]&&dye[i]<=dye[j])
		{
			mk[dye[i]][dye[j]]=1;
			mpp[i][j]=mpp[j][i]=0;
			jk++;
		}
		ans=max(ans,jk);
	}
	else
	{
		for(int i=cur;i<=n;i++)
		{
			if(dye[i])
			continue;
			for(int j=1;j<=6;j++)
			{
				dye[i]=j;
				dfs(cur+1);
				dye[i]=0;
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
		mp[y][x]=1;
	}
	dfs(1);
	printf("%d",ans);
}

发表于 | 评论数：

题意

题目大意是要让一连串连续的数字左右相邻两个两两不同，如果相同可以改高度，改的高度代价输入已知

解法

首先我们可以看到这应该就是一个DP,数据范围也不大不需要带优化(带优化的我现在也不会).我们观察发现一个点最多更改两次,然后我们进行转移即可也就是用当前的点推下一个点,如果当前的点更改0,1,2次和下一个点更改0,1,2次有不同的话那么取min转移.具体看代码吧

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300005;
ll f[N][4],a[N],b[N];
int main()
{
	ll t;
	scanf("%lld",&t);
	while(t--)
	{
		ll n,m;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i],&b[i]);
		for(int i=0;i<=n;i++)
		f[i][0]=f[i][1]=f[i][2]=m=1LL<<60;
		a[0]=-m;
		f[0][0]=0;
		for(int i=0;i<n;i++)
		for(int j=0;j<=2;j++)
		{
			if(f[i][j]==m)
			continue;
			for(int k=0;k<=2;k++)
			if(a[i]+j!=a[i+1]+k)
			f[i+1][k]=min(f[i+1][k],f[i][j]+k*b[i+1]);
		}
		printf("%lld\n",min(f[n][0],min(f[n][1],f[n][2])));
	}
}

发表于 | 评论数：

一个一个网上跳

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
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int f[N][30],d[N];
vector<int> G[N];
void dfs(int p,int fa)
{
	d[p]=d[fa]+1;
	f[p][0]=fa;
	for(int i=1;(1<<i)<=d[p];i++)
	f[p][i]=f[f[p][i-1]][i-1];
	for(int i=0;i<G[p].size();i++)
	if(G[p][i]!=fa)
	dfs(G[p][i],p);
}
int LCA(int x,int y)
{
	if(d[x]<d[y])
	swap(x,y);
	while(d[x]>d[y])
	x=f[x][(int)log2(d[x]-d[y])];
	if(x==y)
	return x;
	for(int i=log2(d[x]);i>=0;i--)
	if(f[x][i]!=f[y][i])
	x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
	int n,m,s,l,r;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&l,&r);
		G[l].push_back(r);
		G[r].push_back(l);
	}
	dfs(s,s);
	while(m--)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",LCA(l,r));
	}
}

发表于 | 评论数：

A. The beautiful values of the palace

二维偏序离线操作用树状数组排序一维之后再一个一个放入还是离线操作有魅力啊

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
ll tt,n,m,k,p,re[N],t[N],xx1,yy1,xx2,yy2;
struct point
{
	int x,y,v;
}pt[N];
struct query
{
	ll x,y,id,f;
}q[N];
bool cmp1(point a,point b)
{
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
bool cmp2(query a,query b)
{
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
void insert(ll x,ll y)
{
	for(ll i=x;i<=N;i+=i&(-i))
	t[i]+=y;
}
ll sum(ll x)
{
	ll ans=0;
	for(ll i=x;i>0;i-=i&(-i))
	ans+=t[i];
	return ans;
}
ll cal(ll x,ll y)
{
	x=x-n/2-1;
	y=y-n/2-1;
	ll t=max(abs(x),abs(y)),ans,jk=0;
	if(x>=y)
	ans=n*n-4*t*t-2*t-x-y;
	else
	ans=n*n-4*t*t+2*t+x+y;
	while(ans)
	jk+=ans%10,ans/=10;
	return jk;
}
int main()
{
	scanf("%lld",&tt);
	while(tt--)
	{
		p=0;
		memset(t,0,sizeof(t));
		memset(re,0,sizeof(re));
		scanf("%lld%lld%lld",&n,&m,&k);
		for(ll i=1;i<=m;i++)
		scanf("%lld%lld",&pt[i].x,&pt[i].y),pt[i].v=cal(pt[i].x,pt[i].y);
		sort(pt+1,pt+1+m,cmp1);
		for(ll i=1;i<=k;i++)
		{
			scanf("%lld%lld%lld%lld",&xx1,&yy1,&xx2,&yy2);
			q[++p]=(query){xx2,yy2,i,1};
			q[++p]=(query){xx1-1,yy1-1,i,1};
			q[++p]=(query){xx1-1,yy2,i,-1};
			q[++p]=(query){xx2,yy1-1,i,-1};			
		}
		sort(q+1,q+1+p,cmp2);
		ll jk=1;
		for(ll i=1;i<=p;i++)
		{
			while(pt[jk].x<=q[i].x&&jk<=m)
			{
				insert(pt[jk].y,pt[jk].v);
				jk++;
			}
			if(q[i].y==0)
			continue;
			re[q[i].id]+=sum(q[i].y)*q[i].f;
		}
		for(ll i=1;i<=k;i++)
		printf("%lld\n",re[i]);
	}
}

B. super_log

欧拉降幂应用题注意幂塔函数递归的玩法，挺好的这题….但是洛谷好像还有一个跟他相似的题之前没做过….Luogu P4139 上帝与集合的正确用法

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
ll t,a,b,m,bk[N],phi[N],p[N],q;
void get()//线性筛欧拉函数
{
	phi[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!bk[i])
		p[++q]=i,phi[i]=i-1;
		for(int j=1;j<=q&&i*p[j]<=N;j++)
		{
			bk[i*p[j]]=1;
			if(i%p[j]==0)
			{
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
			phi[i*p[j]]=phi[i]*(p[j]-1);
		}
	}
}
ll qpow(ll a,ll b,ll m)//快速幂
{
	ll ans=1,base=a;
	while(b)
	{
		if(b&1)
		ans=ans%m*base%m,ans%=m;
		base=base%m*base%m,base%=m;
		b>>=1;
	}
	return ans;
}
ll fun(ll a,ll b,ll m)
{
	if(a==1)//题目里面黑体note
	return 1;
	if(b==0)//a^0=1
	return 1;
	if(m==1)
	return 0;
	ll jk=fun(a,b-1,phi[m]);
	if(jk<m)
	return qpow(a,jk,m);
	else
	return qpow(a,jk%phi[m]+phi[m],m);
}
int main()
{
	get();
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld%lld",&a,&b,&m);
		printf("%lld\n",fun(a,b,m)%m);
	}
}

F. Greedy Sequence

题意很难懂就是找左边右边第一个比他小的数一直找下去问能找到最多多少个?
就是给定一个窗口一个一个往里面塞玩意,然后计算出每个的前驱再从第一个数开始更新f[i]=f[pre[i]]+1即可 

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
int a[100005],ans[100005],bk[100005],pre[100005];
void read(int &x)
{
    char ch = getchar();x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
struct node1
{
	ll l,r,s;
}t[N<<2];
void build(ll p,ll l,ll r)
{
	t[p].l=l;t[p].r=r;t[p].s=0;
	if(l==r) return;
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void change(ll p,ll x,ll y)
{
	if(t[p].l==t[p].r)
	{
		if(t[p].s+y>=0)
		t[p].s+=y;
		return;
	}
	ll mid=(t[p].l+t[p].r)>>1;
	if(x<=mid) change(p<<1,x,y);
	else change(p<<1|1,x,y);
	t[p].s=t[p<<1].s+t[p<<1|1].s;
}
ll sum1(ll p,ll x,ll y)
{
	if(x<=t[p].l&&t[p].r<=y) return t[p].s;
	ll mid=(t[p].l+t[p].r)>>1,ans=0;
	if(x<=mid) ans+=sum1(p<<1,x,y);
	if(y>mid) ans+=sum1(p<<1|1,x,y);
	return ans;
}
ll sum2(ll p,ll x)
{
	if(t[p].l==t[p].r) return t[p].l;
	ll mid=(t[p].l+t[p].r)>>1;
	if(x<=t[p<<1].s) return sum2(p<<1,x);
	else return sum2(p<<1|1,x-t[p<<1].s);
}
int main()
{
	int t;
	read(t);
	while(t--)
	{
		int n,k;
		read(n);
		read(k);
		build(1,1,n);
		for(int i=1;i<=n;i++)
		read(a[i]),bk[i]=a[i];
		for(int i=0;i<=n;i++)
		ans[i]=0;
		int rm=0;
		for(int i=1;i<=k;i++)
		change(1,a[i],1);
		for(int i=1;i<=n;i++)
		{
			if(i+k<=n)
			change(1,a[i+k],1);
			if(i-k>1)
			change(1,bk[i-k-1],-1);
			if(sum1(1,1,a[i]-1)==0)
			pre[a[i]]=a[i];
			else
			pre[a[i]]=sum2(1,sum1(1,1,a[i]-1));
		}
		for(int i=1;i<=n;i++)
		ans[i]=ans[pre[i]]+1;
		for(int i=1;i<=n;i++)
		printf("%d%c",ans[i],i==n?'\n':' ');
	}
}
0%