发表于 | 评论数：

题目给定两个数S0,S1问|Si-Si-1|中有多少不同的数
区域赛铜牌题，思维难度是真的有。首先我们要了解辗转相减后的结果是a%b也就是说a-b=c b-c=d…这样减下去的结果就是a%b
然后其中有的个数是floor(a/b)+(a%b==0)
这样我们就可以跟欧几里得算法那样的感觉那样，进行递归计算，这样使得可以一直相减下去最后需要特判一些情况
如果a==b那么是2 如果都是0那么是1 如果是一0一其他数那么是2，如果a<b 那么是f(a,b-a)+1(要加上b) 

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 <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
long long f(long long a,long long b)
{
	if(a<b) swap(a,b);
	if(a%b==0) return a/b+1;
	else return a/b+f(a%b,b);
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int k=1;k<=t;k++)
	{
		long long a,b;
		scanf("%lld%lld",&a,&b);
		printf("Case #%d: ",k);
		if(a==b) 
		{
			if(a==0) puts("1");
			else puts("2");
		}
		else
		{
			if(a==0||b==0) puts("2");
			else if(a>b) printf("%lld\n",f(a,b));
			else printf("%lld\n",f(a,b-a)+1LL);
		}
	}
}

发表于 | 评论数：

题目大意是给定1e5个的数列问你只能改一个数，使得他变成任意的数。之后数列中最长升序列的长度是多少?
我上来觉得是dp，但是没有想清楚后来又尺取，发现要更改的数可能是小于前一个或者大于前一个情况较多于是看了看题解发现确实是dp不过没想到处理两次
做法是正着处理当前数从左边延申的最长上升，倒着处理当前数从右边延申的最长上升。枚举每一个数看他能否更改使得数列连续。
如果能就用左边的加上当前加上右边的
否则就取出左边的或者右边的最长的+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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[100005],l[100005],r[100005];
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int ans=0;
		l[n+1]=r[n+1]=a[n+1]=0;
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
		if(a[i]>a[i-1]) l[i]=l[i-1]+1;
		else l[i]=1;
		for(int i=n;i;i--)
		if(a[i]<a[i+1]) r[i]=r[i+1]+1;
		else r[i]=1;
		for(int i=1;i<=n;i++)
		if(a[i+1]>a[i-1]+1) ans=max(ans,r[i+1]+l[i-1]+1);
		else ans=max(ans,max(r[i+1],l[i-1])+1);
		printf("%d\n",ans);
	}
}

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

有的时候代码底力会从STL运用上显现出来，导致我发现我还有好多STL的运用并不熟练

SET套结构体

set套结构体要重载<运算符 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
struct node
{
	int a,b,c;
	bool operator<(const node& x) const
	{
		return a==x.a?b<x.b:a<x.a;
	}
};
set<node> st;
int main()
{
	st.insert((node){1,2,3});
	st.insert((node){1,3,2});
	for(auto it=st.begin();it!=st.end();it++)
	cout<<it->a<<" "<<it->b<<" "<<it->c<<"\n";
}

MAP套结构体

与set一样需要重载<运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
struct node
{
	int a,b,c;
	bool operator<(const node& x) const
	{
		return a==x.a?b<x.b:a<x.a;
	}
};
set<node> st;
map<node,int> mp;
int main()
{
	mp[(node){1,1,1}]++;
	mp[(node){1,1,1}]++;
	cout<<mp[(node){1,1,1}];
}

优先队列套结构体很常见这里不多赘述 (似乎他的<与普通的定义相反？)

unordered_map套结构体

这个嵌套比较复杂首先需要重载==运算符然后我们还需要自己手写一个hash规则，用结构体里面重载size_t operator()之后再传入参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
struct node
{
	int a,b,c;
	bool operator==(const node& x) const
	{
		return a==x.a&&b==x.b&&c==x.c;
	}
};
struct hs
{
	size_t operator()(const node&x) const
	{
		return x.a*100+x.b*10+x.c;
	}
};
unordered_map<node,int,hs> mp;
int main()
{
	mp[(node){1,1,1}]++;
	mp[(node){1,1,1}]++;
	cout<<mp[(node){1,1,1}];
}

lower_bound or upper_bound

这两个玩意都是二分，所以要先保证序列有序才行，如果我们要找降序序列中第一个小于等于的位置的话我们需要用
lower_bound(a+1,a+1+n,k,[](int a,int b){return a>b;});
结构体的话会有多维所以要先按照一维排序后重载函数即可

发表于 | 评论数：

题目大意是给你5e5条线段，规定相交的线段可以让他们彼此的编号之间连出一条边。注意线段互相包含不算相交，且没有重复的端点，端点都是从1~2n,问你最后练出的图是不是一棵树
根据树的定义我们知道树的边数一定是n-1的，那么我们可以记录一下边数如果不是n-1那么就是NO否则我们再遍历一下图看看是不是可以组成一颗树
这里CF官方题解给了一种叫做sweep line approach的方法可以nlogn判断具体哪两个线段相交
首先，我们把线段的左端点右端点拆分，变成{v,id}v代表值id代表这是输入顺序的第几个例如1 3线段就要拆分成1 1 和 3 1
然后，我们把拆分的线段加入一个vector中再按照第一个值排序从小到大
接着，我们开一个set来记录vector内的元素
算法开始，我们最外层枚举vector内的元素，首先判断当前set内是否有这个元素如果有就删除继续走。因为如果有的话这都是右端点了直接删除可以避免重复计数
否则的话我们就遍历set看看里面有多少值是小于当前的节点编号的右端点值的小于就说明这俩一定相交那么我们就记录上就行了
最后把这个右端点再放入set中即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for(int i=0;i<v.size();i++) //sweep line approach 
{
	if(cnt>=n) //判断如果边数多了就break 
	break;
	if(st.count(v[i])) //如果存在这个右端点了就删除 
	st.erase(v[i]);
	else
	{
		int r=a[v[i].second].second; //找到当前左端点的右端点 
		for(auto it=st.begin();it!=st.end();it++) //遍历set 
		{
			if(it->first>r)//因为set按照第一个元素排序的所以我们如果有大于的就一定后面都大于不满足当前题目的要求 
			break;
			G[v[i].second].push_back(it->second); //vector存图 
			G[it->second].push_back(v[i].second);
			cnt++;
			if(cnt>=n) //继续判断 
			break;	
		}
		st.insert(make_pair(r,v[i].second)); //放入这个右端点			
	}
}
//这里我们可以适用于其他的题目这个对于判断线段相交确实好用

然后我们dfs一遍看看是不是树就行了 

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
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
pair<int,int> a[N];
bool mk[N];
vector<int> G[N];
void dfs(int p,int fa)
{
	mk[p]=1;
	for(int i=0;i<G[p].size();i++)
	if(!mk[G[p][i]])
	dfs(G[p][i],p);
}
int main()
{
	ios::sync_with_stdio(0);
	int n,cnt=0,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i].first>>a[i].second;
	vector<pair<int,int> > v;
	for(int i=1;i<=n;i++)
	{
		v.push_back(make_pair(a[i].first,i));
		v.push_back(make_pair(a[i].second,i));
	}
	sort(v.begin(),v.end());
	set<pair<int,int> > st;
	for(int i=0;i<v.size();i++)
	{
		if(cnt>=n)
		break;
		if(st.count(v[i]))
		st.erase(v[i]);
		else
		{
			int r=a[v[i].second].second;
			for(auto it=st.begin();it!=st.end();it++)
			{
				if(it->first>r)
				break;
				G[v[i].second].push_back(it->second);
				G[it->second].push_back(v[i].second);
				cnt++;
				if(cnt>=n)
				break;	
			}
			st.insert(make_pair(r,v[i].second));			
		}
	}
	dfs(1,1);
	for(int i=1;i<=n;i++)
	ans+=mk[i];
	if(cnt==n-1&&ans==n)
	cout<<"YES";
	else
	cout<<"NO";
}

发表于 | 评论数：

题目大意为给你一个2xN的数列问你从中间开始向左边或者向右边每次移动一个单位吃果酱，最少移动多少次可以吃的使得1号果酱的个数等于2号果酱的个数
首先记录最初的果酱的差值1-2为dif，然后我们发现如果往左边吃一号果酱，那么dif++，吃二号果酱dif–往右边同理。那么我们可以得到最终dif-difl-difr=0也就是说原来的差值减去左边贡献的差值减去右边贡献的差值最后结果为0.这样我们记录一下左边产生的差值在右边遍历寻找左边是否会有dif-difr的然后更新答案。最后注意一下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
#include <bits/stdc++.h>
using namespace std;
map<int,int> mk;
int a[200005];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,s1=0,s2=0,cur=0,s;
		cin>>n;
		mk.clear();
		for(int i=1;i<=2*n;i++)
		cin>>a[i],s1+=(a[i]==1),s2+=(a[i]==2);
		s=s1-s2;
		mk[0]=0;
		for(int i=n;i;i--)
		{
			if(a[i]==1) cur++;
			else cur--;
			if(!mk.count(cur))
			mk[cur]=n-i+1;
		}
		cur=0;
		int ans=2*n;
		for(int i=n+1;i<=2*n;i++)
		{
			if(a[i]==1) cur++;
			else cur--;
			if(mk.count(s-cur))
			ans=min(ans,i-n+mk[s-cur]); 
		}
		if(mk.count(s))
		ans=min(ans,mk[s]);
		cout<<ans<<"\n";
	}
}
0%