hiho杂选

自用笔记算法

hiho杂选

1319

题目要求

描述
给定一个包含 N × M 个单位正方形的矩阵，矩阵中每个正方形上都写有一个数字。
对于两个单位正方形 a 和 b ，如果 a 和 b 有一条共同的边，并且它们的数字相等，那么 a 和 b 是相连的。
相连还具有传递性，如果 a 和 b 相连，b 和 c 相连，那么 a 和 c 也相连。
给定一个单位正方形 s，s 和与 s 相连的所有单位正方形会组成一个区域 R 。小Hi想知道 R 的周长是多少？

输入
第一行包含4个整数 N , M ，x 和 y ， N 和 M 是矩阵的大小， x 和 y 是给定的单位正方形 s 的坐标。(1 ≤ N , M ≤ 100, 0 ≤ x < N , 0 ≤ y < M )
以下是一个 N × M 的矩阵 A，Aij 表示相应的正方形上的数字。(0 ≤ Aij ≤ 100)

输出
输出一个整数表示 R 的周长。

样例输入
6 5 2 1
0 0 1 2 2
3 1 1 3 7
4 3 1 3 7
4 3 0 3 2
4 3 3 0 1
4 5 5 5 5

样例输出
10

参考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
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int dirx[4]={0,0,1,-1};
int diry[4]={1,-1,0,0};
int n,m,r,ans=0;
int g[maxn][maxn];
int vis[maxn][maxn];
void dfs(int x,int y){
	if(x<0 || x>=n || y<0 || y>=m || g[x][y]!=r){
		ans++;
		return;
	}
	if(vis[x][y]) return ;
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int nextx=x+dirx[i];
		int nexty=y+diry[i];
		dfs(nextx,nexty);
	}
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int x,y;
	cin>>n>>m>>x>>y;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++) cin>>g[i][j];
	}
	mm(vis,0);
	r=g[x][y];
	dfs(x,y);
	cout<<ans<<endl;
	return 0;
}

思路

dfs
关键是只有在越界或者下一个访问的数字不等于g[x][y]时 ans++ 否则经过相同的数字不计算边长

1318

题目要求

描述
如果一个二进制数包含连续的两个1，我们就称这个二进制数是非法的。
小Hi想知道在所有 n 位二进制数（一共有2n个）中，非法二进制数有多少个。
例如对于 n = 3,有 011, 110, 111 三个非法二进制数。
由于结果可能很大，你只需要输出模109+7的余数。

输入
一个整数 n (1 ≤ n ≤ 100)。

输出
n 位非法二进制数的数目模109+7的余数。

样例输入
3

样例输出
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 maxn 105
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
LL dp[maxn];
LL solve(int x){
	LL re=1;
	for(int i=1;i<=x;i++) re=(re*2LL)%mod;
	return re;
} 
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	mm(dp,0);
	dp[0]=0,dp[1]=0;
	for(int i=2;i<=n;i++){
		dp[i]=(dp[i-1]+dp[i-2]+solve(i-2))%mod;
	}
	cout<<dp[n]<<endl;
	return 0;
}

思路

数位dp
dp[i]表示到i位的非法数字
如果第i位是0 那么前i-1位必须是非法数字 为dp[i-1]
如果第i位是1 那么第i-1位有2种情况 如果是0 那么前i-2位必须是非法数字 这部分是dp[i-2] 如果是1 那么第i和第i-1位
已经构成了非法数字 前i-2位一共有2^(i-2)种排序 注意该运算要边移位边取模
dp方程：dp[i]=dp[i-1]+dp[i-2]+2^(i-2)

1523

题目要求

描述
给定一个1-N的排列A1, A2, … AN，每次操作小Hi可以选择一个数，把它放到数组的最左边。
请计算小Hi最少进行几次操作就能使得新数组是递增排列的。

输入
第一行包含一个整数N。
第二行包含N个两两不同整数A1, A2, … AN。(1 <= Ai <= N)
对于60%的数据 1 <= N <= 20
对于100%的数据 1 <= N <= 100000

输出
一个整数代表答案

样例输入
5
2 3 1 4 5

样例输出
1

参考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 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int a[maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=n;i>=1;i--){
		if(a[i]==n) n--; 
	}
	cout<<n<<endl;
	return 0;
}

思路

思维题
最多移动n次 从末尾开始遍历 找到从n开始逐一下降的最远距离是数字几 其余的数字都应移动 答案为自减后的n

1330

题目要求

描述
小Hi想知道，如果他每次都按照一种固定的顺序重排数组，那么最少经过几次重排之后数组会恢复初始的顺序？
具体来讲，给定一个1 - N 的排列 P，小Hi每次重排都是把第 i 个元素放到第 Pi个位置上。例如对于 P = (2, 3, 1)，假设初始数组是(1, 2, 3)，重排一次之后变为(3, 1, 2)，重排两次之后变为(2, 3, 1)，重排三次之后变回(1, 2, 3)。
被排数组中的元素可以认为是两两不同的。

输入
第一行一个整数 N ，代表数组的长度。 (1 ≤ N ≤ 100)
第二行N个整数，代表1 - N 的一个排列 P 。

输出
输出最少重排的次数。

样例输入
3
2 3 1

样例输出
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
40
41
42
43
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int a[maxn];
LL lcm(LL a,LL b){
	return a*b/gcd(a,b);
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=1;
	for(int i=1;i<=n;i++){
		if(i==a[i]) continue;
		int len=1;
		int p=a[i];
		while(i!=p){
			p=a[p];
			len++;
		}
		ans=lcm(ans,len);
	}
	cout<<ans<<endl;
	return 0;
}

思路

如果该位置i=a[i]无需判断
其余位置求循环次数的最小公倍数

hihocoder 1564

题目要求

H公司有 N 台服务器，编号1~N，组成了一个树形结构。其中中央服务器处于根节点，终端服务器处于叶子节点。
中央服务器会向终端服务器发送消息。一条消息会通过中间节点，到达所有的终端服务器。消息每经过一台服务器(包括根节点的中央服务器和叶子节点的终端服务器)
就会被处理并存储下来，其中编号为 i 的服务器，执行处理和存储这个过程会花费 Ai 毫秒的时间。消息从一台服务器传输到另一台服务器的时间可以忽略不计。
由于 Ai 各不相同，从中央服务器发出消息到各个终端处理并储存完毕的时间也是不相同的。例如如下的网络，假设1是中央服务器，而2和4是终端服务器。
1
/ \
2 3
|
4
如果A1=1, A2=4, A3=3, A4=2，那么假设1发出消息的时刻是0，终端2处理完的时刻是A1+A2=5，而终端4处理完的时刻是A1+A3+A4=6。
CEO交给小Ho一个任务，要求每台终端处理完消息的时间是完全一致的。小Ho想到了一个天才的解决方案：强行增加某些服务器的处理时间 Ai。例如在上例中，
将 A2从4增加到5即可使所有终端都在6毫秒后处理完毕。
当然小Ho希望所有服务器增加的处理时间总和最少。你能帮助小Ho吗？

第一行包含一个整数 N。
第二行包含N个整数，A1, A2, … AN，表示每个节点处理信息花费的时间。
以下 N-1行每行包含两个整数 a 和 b，表示 a 是 b 的父节点。
对于30%的数据，满足 1 ≤ N ≤ 103
对于100%的数据，满足1 ≤ N ≤ 105, 1 ≤ Ai ≤ 105

输出一个整数表示增加的处理时间之和最小是多少。

参考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
#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
vector<int>e[maxn];
LL ans,b[maxn];
int a[maxn];
int in[maxn];
void dfs(int x){
	if(e[x].size()==0){
		b[x]=(LL)a[x];
		return;
	}
	LL mx=-1;
	int len=e[x].size();
	for(int i=0;i<len;i++){
		int next=e[x][i];
		dfs(next);
		mx=max(mx,b[next]);
	}
	for(int i=0;i<len;i++){
		int next=e[x][i];
		ans+=mx-b[next];
	}
	b[x]=a[x]+mx;
}
int main(){
//	freopen("input.txt","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	mm(in,0);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		in[v]++;
	}
	int root=1;
	for(int i=1;i<=n;i++){
		if(!in[i]){
			root=i;
			break;
		}
	}
	dfs(root);
	printf("%lld\n",ans);
	return 0;
}

思路

b维护子树结点修改后的值(实际为最大值 包括这棵子树的跟)
in数组是为了找到根 mx数组记录子树下结点的dist最大值
dfs从叶子结点开始向上遍历 把所有子树的结点都修改成最大值 就可以确保这一棵树的dist相等
一层一层遍历上去 随着子树的合并 不断更新b数组来维护修改的后子树的最大值 即可

本文标题:hiho杂选

文章作者:Hippopmonkey

发布时间:2017-07-26, 22:07:13

最后更新:2017-08-27, 18:48:18

原始链接:http://xuboming8.github.io/2017/07/26/hiho杂选/

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

文章目录
  1. 1. hiho杂选
    1. 1.1. 1319
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. 1318
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. 1523
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. 1330
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. hihocoder 1564
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|