杂题专选-二

自用笔记算法

杂题专选-二

集合操作

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main(){
	vector<int>e1,e2;
	e1.push_back(2),e1.push_back(3);
	e2.push_back(3),e2.push_back(4);e2.push_back(1);
	set_union(e1.begin(),e1.end(),e2.begin(),e2.end(),ostream_iterator<int>(cout," "));  cout<<endl;
	set_intersection(e1.begin(),e1.end(),e2.begin(),e2.end(),ostream_iterator<int>(cout," "));  cout<<endl;
	set_difference(e1.begin(),e1.end(),e2.begin(),e2.end(),ostream_iterator<int>(cout," "));  cout<<endl;
	set_symmetric_difference(e1.begin(),e1.end(),e2.begin(),e2.end(),ostream_iterator<int>(cout," "));  cout<<endl;
	sort(e1.begin(),e1.end()); sort(e2.begin(),e2.end());
	merge(e1.begin(),e1.end(),e2.begin(),e2.end(),ostream_iterator<int>(cout," "));  cout<<endl;
	return 0;
}

详解

集合的并：set_union
集合的交：set_intersection
集合的差:set_difference
集合的标准差：set_symmetric_difference
集合的有序合并:merge
注意stl使用的5个参数

cf 803c

题目要求

寻找一个递增序列满足k个数和为n 使他们的gcd最大

参考AC代码

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
#include<bits/stdc++.h>
#define LL long long 
using namespace std;
int main(){
//	freopen("input.txt","r",stdin);
	LL n,k,kk;
	scanf("%lld%lld",&n,&k);
	kk=k;
	if(k>=200000){
		printf("-1\n");
		return 0;
	}
	if(k==1){
		printf("%lld\n",n);
		return 0;
	}
	k=(k+1)*k/2;
	LL ans=-1;
	for(LL d=1;d*d<=n;d++){
		if(k*d>n) break;
		if(n%d!=0) continue;
		ans=d;
		if(k<=d){
			ans=n/d;
			break;
		}
	}
	if(ans==-1) printf("-1\n");
	else{
		for(LL i=1;i<kk;i++){
			printf("%lld ",ans*i);
			n-=ans*i;
		}
		printf("%lld\n",n);
	}
	return 0;
}

思路

假设当前的因数为d 那么可以构造出一个序列d 2d 3d···(k-1)d 他们的和用等差数列求和公式求出为s=d*k(k-1)/2
剩下的一个数为n-s 需要满足n-s>(k-1)d
因为我们求因数的时候上限开到根号n 所以需要考虑d和n/d两种情况的公差
k大于20万为计算出的数字 需要满足前k-1项小于n

cf_Igor and his way to work

题目要求

带转弯的dfs 注意开三维或思维数组 空间换时间即可

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1050
using namespace std;
int n,m;
int g[maxn][maxn];
int vis[maxn][maxn][5][3];
int dirx[4]={1,-1,0,0};
int diry[4]={0,0,1,-1};
int si,sj,ei,ej;
int flag=0;
void dfs(int x,int y,int pre,int cnt){
	if(flag) return;
	if(cnt>2) return ;
	if(x<1||x>n||y<1||y>m||g[x][y]==-1) return;
	if(x==ei&&y==ej){
		flag=1;
		return;
	}
	if(vis[x][y][pre][cnt]) return;
	vis[x][y][pre][cnt]=1;
	for(int i=0;i<4;i++) dfs(x+dirx[i],y+diry[i],i,cnt+(pre!=4&&pre!=i));
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	memset(g,0,sizeof(g));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		string s; cin>>s;
		for(int j=0;j<s.length();j++){
			if(s[j]=='.') g[i][j+1]=1;
			else if(s[j]=='*') g[i][j+1]=-1;
			else if(s[j]=='S'){
				g[i][j+1]=1;
				si=i,sj=j+1;
			}
			else if(s[j]=='T'){
				g[i][j+1]=1;
				ei=i,ej=j+1;
			}
		}
	}
	dfs(si,sj,4,0);
	if(flag) printf("YES\n");
	else printf("NO\n");
	return 0;
}

cf_Mice problem

题目要求

有一个矩形范围的捕鼠夹 有若干个老鼠以x轴和y轴恒定的速度运动 问某一时间捕鼠夹里是否可以抓到所有的老鼠

参考AC代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define MAXN 1e5
const double EPS=3e-15;
double x1,x2;
double y11,y2;
bool flag;
double s1,s2;
void f(double x,double vx,bool fg){
    double l,r;
    if(fg) {l=x1;r=x2;}
	else {l=y11;r=y2;}
    if(vx==0){
        if(!(l<x&&x<r)) flag=false;
        return;
    }
    if(vx<0){
        x=-x,vx=-vx,l=-l,r=-r;
        swap(l,r);
    }
    if(x>r){
        flag=false;
        return;
    }
    if(x<=l) s1=max(s1,(l-x)/vx);
    s2=min(s2,(r-x)/vx);
    return;
}
int main()
{
//	freopen("input.txt","r",stdin);
    int n;
    flag=true;
    s1=0;
    s2=INF*1.0;
    scanf("%d",&n);
    scanf("%lf%lf%lf%lf",&x1,&y11,&x2,&y2);
    double x,y,vx,vy;
    while(n--){
        scanf("%lf%lf%lf%lf",&x,&y,&vx,&vy);
        if(flag){
            f(x,vx,true);
            f(y,vy,false);
        }
    }
    if(flag&&s2>=s1+EPS){
        printf("%.10f\n",s1);
    }else{
        printf("-1\n");
    }
    return 0;
}

注意事项

高精度计算 求出严格和非严格的答案 判断误差精度是否在要求之内

cf_Presents in Bankopolis

题目要求

一条路每次来回不能越过已走过的最远的边界
类似于不断缩小范围的搜索

参考AC代码

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
#include<bits/stdc++.h>
#define inf 0x7f7f7f7f
#define maxn 82
using namespace std;
int g[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];
int n,m,k;
int M_search(int l,int r,int cur,int k)
{
	if(dp[l][r][cur][k]!=-1) return dp[l][r][cur][k];
	if(k==1){
		dp[l][r][cur][k]=0;
		return 0;
	}
	int ans=inf;
	for(int i=1;i<=n;i++){
		if(g[cur][i]!=inf){
			if(i>l&&i<r){
				if(i>cur) ans=min(ans,g[cur][i]+M_search(cur,r,i,k-1));
				else ans=min(ans,g[cur][i]+M_search(l,cur,i,k-1));
			}
		}
	}
	dp[l][r][cur][k]=ans;
	return dp[l][r][cur][k];
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d%d",&n,&k,&m);
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=n;j++) g[i][j]=inf;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u][v]=min(g[u][v],w);
	}
	int ans=inf;
	for(int i=1;i<=n;i++) ans=min(ans,M_search(0,n+1,i,k));
	if(ans>=inf) ans=-1;
	printf("%d\n",ans);
	return 0;
}

思路

记忆化搜索+dp的状态转移方程
k=1时dp置为0
注意记忆化搜索的格式

ATcoder——01背包变形

题目要求

背包容量10^9 无法用数组保存
单件物品的消耗满足w1<=wi<=w1+3四种情况

参考AC代码

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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
vector<LL>w0,w1,w2,w3;
int main(){
//	freopen("input.txt","r",stdin);
	LL n,W;
	scanf("%lld%lld",&n,&W);
	LL w,v,pw;
	scanf("%lld%lld",&w,&v);
	w0.push_back(v);
	pw=w;
	for(int i=2;i<=n;i++){
		scanf("%lld%lld",&w,&v);
		if(w==pw) w0.push_back(v);
		else if(w==pw+1) w1.push_back(v);
		else if(w==pw+2) w2.push_back(v);
		else if(w==pw+3) w3.push_back(v);
	}
	sort(w0.begin(),w0.end(),greater<LL>());
	sort(w1.begin(),w1.end(),greater<LL>());
	sort(w2.begin(),w2.end(),greater<LL>());
	sort(w3.begin(),w3.end(),greater<LL>());
//	for(int i=0;i<w3.size();i++) cout<<w3[i]<<endl;
	LL ans=-1;
	for(int i=0;i<=w0.size();i++){
		for(int j=0;j<=w1.size();j++){
			for(int k=0;k<=w2.size();k++){
				for(int p=0;p<=w3.size();p++){
					if(pw*i+(pw+1)*j+(pw+2)*k+(pw+3)*p>W) continue;
					LL x=accumulate(w0.begin(),w0.begin()+i,0LL)+accumulate(w1.begin(),w1.begin()+j,0LL)+accumulate(w2.begin(),w2.begin()+k,0LL)+accumulate(w3.begin(),w3.begin()+p,0LL);
					ans=max(ans,x);
				}
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}

思路

贪心
vector保存四种w的物品 每种w的物品按照价值的降序排列
暴力即可 使用accumulate函数可以增加代码可读性 注意条件判断

ATcoder——Ball Coloring

题目要求

每个箱子有两个给定编号的白色气球 每次可以把箱子里的一个气球涂成红色另一个涂成蓝色
求红色气球编号的最大值-最小值×蓝色气球编号的最大值减最小值的最小值

参考AC代码

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>
#define maxn 200050
#define LL long long
using namespace std;
struct node
{
	LL fi,se;
}a[maxn];
multiset<LL>m1,m2;
int cmp(node a,node b){
	if(a.fi==b.fi) return a.se<b.se;
	return a.fi<b.fi;
}
int main(){
//	freopen("input.txt","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].fi,&a[i].se);
		if(a[i].fi>a[i].se) swap(a[i].fi,a[i].se);
		m1.insert(a[i].fi),m2.insert(a[i].se);
	}
	sort(a+1,a+1+n,cmp);
	LL ans=(*m1.rbegin()-*m1.begin())*(*m2.rbegin()-*m2.begin());
	for(int i=1;i<=n;i++){
		m1.erase(m1.find(a[i].fi)),m2.erase(m2.find(a[i].se));
		m1.insert(a[i].se),m2.insert(a[i].fi);
		ans=min(ans,(*m1.rbegin()-*m1.begin())*(*m2.rbegin()-*m2.begin()));
	}
	printf("%lld\n",ans);
	return 0;
}

思路

stl 贪心
把每组气球中编号的小的放入multiset容器中 编号大的放进另一个
保证小-小×大-大是最优解(最小)
a数组也需要排序
确保找到并交换的第一个最小值是逐渐变大的 贪心保证全局最优解
从a数组的第一个开始(最小) 每次在容器中找到对应的值交换 更新答案

本文标题:杂题专选-二

文章作者:Hippopmonkey

发布时间:2017-04-26, 10:13:35

最后更新:2017-04-30, 23:54:43

原始链接:http://xuboming8.github.io/2017/04/26/杂题专选-二/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 杂题专选-二
    1. 1.1. 集合操作
      1. 1.1.1. 参考代码
      2. 1.1.2. 详解
    2. 1.2. cf 803c
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. cf_Igor and his way to work
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
    4. 1.4. cf_Mice problem
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 注意事项
    5. 1.5. cf_Presents in Bankopolis
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. ATcoder——01背包变形
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. ATcoder——Ball Coloring
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
|