哈理工新生赛

自用笔记算法

哈理工热身赛题解

棋盘村

Problem Description

Input

Output

Sample Input

Sample Output

参考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
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long  
using namespace std;
const int dx[]={1,1,2,2,-1,-1,-2,-2};
const int dy[]={2,-2,1,-1,2,-2,1,-1};
LL f[21][21];
bool map[21][21];
int main()
{
	int t,n,m,x,y;
	cin>>t;
	while(t--)
	{
		memset(f,0,sizeof(f));
		memset(map,0,sizeof(map));
		scanf("%d%d%d%d",&n,&m,&x,&y);
		map[x][y]=1;
		for(int i=0;i<=7;i++)
		{
			if(x+dx[i]<0||x+dx[i]>n) 
				continue;
			if(y+dy[i]<0||y+dy[i]>m)
				continue;
			map[x+dx[i]][y+dy[i]]=1;
		}
		f[0][0]=1;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
			{
				if(i==0&&j==0)
					continue;
				if(i==0) 
					f[i][j]=f[i][j-1];
				if(j==0) 
					f[i][j]=f[i-1][j];
				if(i&&j) 
					f[i][j]=f[i-1][j]+f[i][j-1];
				if(map[i][j]) 
					f[i][j]=0;				
			}
		cout<<f[n][m]<<endl;
	}
	return 0;
}

思路

递推。把所有强盗可能经过的点找出来dp赋为0，需额外考虑边上的情况，接着用递推关系得到答案。

FBI Tree

Problem Description

Input

Output

Sample Input

Sample Output

参考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
#include<iostream>
#include<math.h>
using namespace std;
char s[1100];
void dg(int x,int y)
{
    int cnt0,cnt1;
    if(x==y)
    {
        if(s[x]=='0') printf("B");
        else printf("I");
    }
    else
    {
        int mid=(y-x-1)/2;
        dg(x,x+mid);
        dg(y-mid,y);
        cnt0=cnt1=0;
        for(int i=x;i<=y;i++)
            if(s[i]=='0') 
				cnt0++;
            else  
				cnt1++;
        if(cnt0==0) 
			printf("I");
        else if(cnt1==0) 
			printf("B");
        else 
			printf("F");
    }
}
int main()
{
    int t,n,m;
	cin>>t;
    while(t--)
    {
        cin>>n;
		scanf("%s",s);
        m=(int)pow(2.0,n);
        dg(0,m-1);
        printf("\n");
    }
    return 0;
}

思路

类似于线段树的求解。二分+递归即可。

Nine Digits

Problem Description

Input

Output

Sample Input

Sample Output

参考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
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
#include<iostream>
#include<queue>
#include<string.h>
#define max 500000
using namespace std;
int len[max];
int vis[max];
int s[9]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
int jie[9]={0,1,2,6,24,120,720,5040,40320};     //n!
int four[4];
int start=123456789,str[9];
int temp;
int transform1(int num)
{
	int result;
	result = num%s[4];
	result += ((num / s[5]) % 10)*s[4];
	result += num / s[8] * s[5];
	result += ((num / s[6]) % 10)*s[6];
	result += ((num / s[4]) % 10)*s[7];
	result += ((num / s[7]) % 10)*s[8];
	return result;
}
int transform2(int num)
{
	int result = num / s[5] * s[5];
	result += num / s[1] % 10;
	result += num / s[4] % 10 * s[1];
	result += num / s[2] % 10 * s[2];
	result += num % 10 * s[3];
	result += num / s[3] % 10 * s[4];
	return result;
}
int transform3(int num)
{
	int result = num / s[6] * s[6] + num % 10;
	result += num / s[2] % 10 * s[1];
	result += num / s[5] % 10 * s[2];
	result += num / s[3] % 10 * s[3];
	result += num / s[1] % 10 * s[4];
	result += num / s[4] % 10 * s[5];
	return result;
}
int transform4(int num)
{
	int result = num % s[3] + num / s[8] * s[8];
	result += num / s[4] % 10 * s[3];
	result += num / s[7] % 10 * s[4];
	result += num / s[5] % 10 * s[5];
	result += num / s[3] % 10 * s[6];
	result += num / s[6] % 10 * s[7];
	return result;
}
int cantor(int key)
{
	int result, temp[9];
	for (int i = 8; i >= 0; i--)
	{
		temp[i] = key % 10;
		key = key / 10;
	}
	result = 0;
	for (int i = 0; i<8; i++)
	{
		int tot = 0;
		for (int j = i + 1; j<9; j++)
			if (temp[j]<temp[i])
				tot++;
		result += tot*jie[8 - i];
	}
	return result;
}
int main()
{
	queue<int>que;
	int key1,key2[4],top;
	len[0]=0;
	memset(vis,0,sizeof(vis));
	vis[0]=1;
	que.push(start);
	while(que.size())
	{
		top=que.front();
		que.pop();
		key1=cantor(top);
		four[0]=transform1(top);
		four[1]=transform2(top);
		four[2]=transform3(top);
		four[3]=transform4(top);
		for(int i=0;i<4;i++)
		{
			key2[i]=cantor(four[i]);
			if(!vis[key2[i]])
			{
				vis[key2[i]]=1;
				que.push(four[i]);
				len[key2[i]]=len[key1]+1;
			}
		}
	}
	while(~scanf("%d",&str[0]))
	{
		temp=str[0];
		for(int i=1;i<9;i++)
		{
			scanf("%d",&str[i]);
			temp=str[i]+temp*10;
		}
		printf("%d\n", len[cantor(temp)]);
	}
	return 0;
}

思路

类似于魔板的三种变化。使用康拓展开，把每个状态划为一个整数使用DFS搜索直到找出答案。

陈月亮的数学题

Problem Description

Input

Output

Sample Input

Sample Output

参考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
55
56
57
58
59
60
61
#include<iostream>
#include <cstring>
using namespace std;
int prime[65536];
int s[100000],ans;
bool isprime(int x)
{
	for(int i=2;i*i<=x;i++)
		if(x%i==0) return 0;
	return 1;
}
void printprime()
{
	for(int i=2;i<=65536*2;i++)
		if(isprime(i))
			prime[++prime[0]]=i;
}
int main()
{
	memset(prime,0,sizeof(prime));
	printprime();
	/*cout<<prime[0]<<endl;*/               //12251
	int a,b,cnt,top,T;
	cnt=0;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&a);
		b=1;
		memset(s,0,sizeof(s));
		int tmp=a;
		top=0;
		for(int i=1;i<=prime[0];i++)
		{
			top++;
			if(tmp%prime[i]!=0) 
				continue;
			while(tmp%prime[i]==0)
			{
				s[top]++;
				tmp/=prime[i];
				if(tmp==1) 
					break;
			}
		}
		if(tmp>1)
		{
			top++;
			s[top]++;
		}
		ans=1;
		for(int i=1;i<=top;i++)
		{
			int bb=(s[i]+2)*(s[i]+1)/2;
			int tt=bb*bb;
			ans=ans*tt;
		}
	    printf("%d\n",ans);
	}
	return 0;
}

思路

数论题。打表出所有的质数，把输入的数字分解成若干个质数的乘积，算出每个质数的个数，分别带入连续自然数立方和公式后做积运算即为结果。

本文标题:哈理工新生赛

文章作者:Hippopmonkey

发布时间:2016-11-28, 20:33:19

最后更新:2016-11-28, 21:25:21

原始链接:http://xuboming8.github.io/2016/11/28/哈理工新人赛/

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

文章目录
  1. 1. 哈理工热身赛题解
    1. 1.1. 棋盘村
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
    2. 1.2. FBI Tree
      1. 1.2.1. 参考AC代码
      2. 1.2.2. 思路
    3. 1.3. Nine Digits
      1. 1.3.1. 参考AC代码
      2. 1.3.2. 思路
    4. 1.4. 陈月亮的数学题
      1. 1.4.1. 参考AC代码
      2. 1.4.2. 思路
|