10-16 热身赛

自用笔记算法

周赛（一）

Triangle

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

有n根长度不一的火柴（序号为1-n的火柴长度分别为1-n），要求拿走y根火柴使剩下的长度无法组成三角形并且要求y的数量最小。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
#include<iostream>
using namespace std;  
const int N = 25;   
int s[N]={0,0,0,0,1,1,2,3,3,4,5,6,7,7,8,9,10,11,12,13,14};  
int main()  
{  
    int t,p=1;   
    cin>>t;
    while(t--)  
    {  
        int n;
		cin>>n;
        cout<<"Case #"<<p++<<": "<<s[n]<<endl;
    }  
    return 0;  
}

思路

由于由前三个测试样例为1 1 2，并且算出第四个测试样例为3后可以联想到斐波拉契数列。在斐波拉契数列中，按序任意插入一个数后都一定可以组成三角形。例如abde为
四个菲波拉契数，那么a+b=d，b+d=e。在bd中插入c后必然有a+b>c b+c>d。所以在n个有序递增为1的整数中，只需要去掉菲波拉契数即可，剩下的数不可能组成三角形。

注意事项

联想到斐波拉契数列后应正确使用。由于本题的数据量很小maxsize只有20，所以可以打表暴力求解，无需刻意编写删除菲波拉契数的算法。

Vitya in the Countryside

Problem Description

Input

Output

Sample Input & output

题目要求

题目给出循环数 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1。接下来继续以0循环。要求输入给定个数的
数字后判断最后一个数字的下一个数相比前一个数在循环中为up还是down，如果无法判断则输出-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
33
34
35
36
37
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
	int n,a[100];
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	if(n==1)
	{
		if(a[n]==0)
			cout<<"UP"<<endl;
		if(a[n]==15)
			cout<<"DOWN"<<endl;
		if(a[n]!=0&&a[n]!=15)
			cout<<"-1"<<endl;
	}
	else
	{
		if(a[n]==0)
			cout<<"UP"<<endl;
		else
		{
			if(a[n]==15)
				cout<<"DOWN"<<endl;
			else
			{
				if(a[n]>a[n-1])
					cout<<"UP"<<endl;
				if(a[n]<a[n-1])
					cout<<"DOWN"<<endl;
			}
		}
	}
	return 0;
}

思路

此题的特殊点在于必须特判0和15两个数字，在判断up down或者-1时只需加入这2个特殊情况即可，输入为1个数字的时候也要特判。

注意事项

此题虽然难度小，题意也很好理解，但极易WA，必须在考虑了所有情况后才可AC。

Anatoly and Cockroaches

Problem Description

Input

Output

Sample Input & output

题目要求

给定一个只有r和b的字符串，要求最后操作的结果为rb间隔排列，具体操作为交换任意两个数或把一个位置的r（b）换成b（r），求操作的最小次数。

参考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
#include<cstdio>  
#include<string.h>  
#include<stdlib.h>  
#include<math.h>  
#include<algorithm>  
using namespace std;  
const int maxn = 1e5+ 5;  
char st[maxn];  
int main(){  
    int n;  
    scanf("%d%s",&n,st);  
    int cnt1=0,cnt2=0,cnt3=0,cnt4=0;  
    for(int i=0;i<n;i++){  
        if(i%2==0&&st[i]!='r') cnt1++;  
        else if(i%2==1&&st[i]!='b') cnt2++;  
    }  
    for(int i=0;i<n;i++){  
        if(i%2==0&&st[i]!='b') cnt3++;  
        else if(i%2==1&&st[i]!='r') cnt4++;  
    }  
    int ans1=abs(cnt1-cnt2)+(cnt1+cnt2-abs(cnt1-cnt2))/2;  
    int ans2=abs(cnt3-cnt4)+(cnt3+cnt4-abs(cnt3-cnt4))/2;  
    printf("%d\n",min(ans1,ans2));  
    return 0;  
}

思路

假如有5个字符，那么最后操作完的结果必然为rbrbr或brbrb。分别计算出两种状态下的r需要转换成b和b需要转换成r的位置的个数记为w1和w2，由于在操作过程中要求次
数最少，所以优先考虑交换。因为交换可使两个位置达到要求状态而涂色只可改变一个位置。所以计算出w1-w2，这部分由于没有对应的两两交换的可能，所以必须涂色，
而剩下的可以两两配对，即可交换。再把两种状态下的结果求min即可。最后的表达式为abs(w1-w2)+(w1+w2-abs(w1-w2))/2.

注意事项

从结果出发较为简便，无需考虑每次交换的过程采用搜索。最后的结果一定为间隔排序那么从结果出发即可。求出最后表达式即可ac。

Efim and Strange Grade

Problem Description

Input

Output

Sample Input & output

题目要求

给定一个小数和查询次数，查询时可以随意访问任意一个小数位并进行进位操作，求所有查询过程中的最大值，最后位数的0不可输出。

参考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
#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
#define MAX 200050
int main()  
{  
    char str[MAX];  
    int n,t;  
    int point;  
    memset(str,0,sizeof(str));  
    scanf("%d%d%s",&n,&t,str);    
    for(int i=n+1;i>=1;i--)  
    {  
        str[i]=str[i-1];  
    }  
    str[0]='0';  
    for(int i=1;i<=n;i++)  
        if(str[i]=='.')  
            point = i;  
    int flag = 0;  
    for(int i=point+1;i<strlen(str);i++)  
    {  
        if(str[i]>='5')  
        {  
            flag = i;  
            break;  
        }  
    }   
    while(t--)  
    {  
        if(str[flag]<'5')   
            break;  
        str[flag]='\0';  
        if(str[flag-1]=='.')  
        {  
            for(int i=point-1;i>=0;i--)  
            {  
                if(str[i]=='9')  
                    str[i]='0';  
                else  
                {  
                    str[i]+=1;  
                    break;  
                }  
            } 
			str[point]='\0';
            break;    
        }  
        str[--flag] +=1;   
    }     
    for(int i=strlen(str)-1;i>=point;i--)  
    {  
          
        if(str[i]!='0')  
            break;  
        str[i]='\0';  
    }      
    if(str[0]=='1')  
        printf("1");  
	puts(str+1);
    return 0;  
}

思路

求出小数点后第一个大于4的位数后依次向前判断即可。具体操作如下：输入时留出str[0]的位置防止进位数组越界。之后计算出小数点的位置point和第一个大于4的位置
flag，若所有位置都无需进位那么flag依旧为初始化的0，只执行最后一步的puts（str+1）。在找出第一个进位的position以后执行while循环，需要特判若进位时小数点
左边+1的情况，若为9则+1后变为0，str[0]变为1。只要有一位小于5退出循环它就是最大数。若进位时未牵涉到小数点那么执行str[–flag]+=1的进位操作，继续检查下
一个flag位。再由strlen（str）-1位置开始向前扫面去掉末尾的0后输出结果。若str[0]==1说明整数部位由9变为了10那么输出1，结果剩下的部分由puts输出。

注意事项

此题需要注意会不断的通过赋值’\0’缩减字符串，要正确判断在在什么时候什么位置加上结束符。整数部分可能进位后多产生一位，所以str[0]必须在输入数据的时候空出
来以防溢出。最后输出的时候若用cout或printf均超时，所以用专门的字符串输出函数puts即可。

The more, The Better

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码(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
#include <stdio.h>  
#include <string.h>  
#include <algorithm>  
using namespace std;   
struct node  
{  
    int to,next;  
} tree[205];  
int vis[205],dp[205][205],ans[205][205],head[205],money[205]; 
int len,n,m;    
void add(int a,int b)  
{  
    tree[len].to = b;  
    tree[len].next = head[a];  
    head[a] = len++;  
}   
void dfs(int root)  
{  
    int i,j,k,tem;  
    vis[root] = 1;  
    for(i = head[root]; i!=-1; i = tree[i].next)  
    {  
        tem = tree[i].to;  
        if(!vis[tem])  
        {  
            dfs(tem);  
            for(k = m; k>=0; k--)//01背包  
                for(j = 0; j<=k; j++)  
                    ans[root][k] = max(ans[root][k],ans[root][k-j]+dp[tem][j]);  
        }  
    }  
    for(j = 1; j<=m+1; j++)  
        dp[root][j] = ans[root][j-1]+money[root];  
}    
int main()  
{  
    int i,a,b;  
    while(~scanf("%d%d",&n,&m),n+m)  
    {  
        len = 0;  
        memset(head,-1,sizeof(head));  
        for(i = 1; i<=n; i++)  
        {  
            scanf("%d%d",&a,&b);  
            money[i] = b;  
            add(a,i);  
        }  
        money[0] = 0;  
        memset(vis,0,sizeof(vis));  
        memset(dp,0,sizeof(dp));  
        memset(ans,0,sizeof(ans));  
        dfs(0);  
        printf("%d\n",dp[0][m+1]);  
    }  
    return 0;  
}

参考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
#include <stdio.h>  
#include <string.h>  
#include <algorithm>  
using namespace std;  
int n,m;
int num[255];
int  map[255][255];
int dp[255][255];
bool v[255];
void dfs(int root){
    int i,j,k;
    v[root]=true;
    for(i=1;i<=num[root];i++)
	{
        int t=map[root][i];       //son 
        if(!v[t]) 
		dfs(t);         //若未访问 则跟进 
        for(j=m;j>=2;j--)
		{         //选择1个的状态不用更新了，因为是强制要加进去的，即必须先选择的
            for(k=1;k<j;k++)
			{
				dp[root][j]=max(dp[root][j],dp[root][k]+dp[t][j-k]);
            }
        }
    }
}
int main(){
    int i,j;
    while(scanf("%d%d",&n,&m),n||m)
	{
        int a,b;
        dp[0][1]=0;        //添加一个0号点为根节点，必取，价值为0
        memset(num,0,sizeof(num));
        for(i=1;i<=n;i++)
		{
            scanf("%d%d",&a,&b);
            dp[i][1]=b; 
            map[a][++num[a]]=i;          //边集数组
        }
        m++;        //增加一个点，森林转换成树
        for(i=0;i<=n;i++)
		{
            dp[i][0]=0;
			v[i]=0;
            for(j=2;j<=m;j++)
			{
                dp[i][j]=0;
            }
        }           //初始化 
        dfs(0);
        printf("%d\n",dp[0][m]);
    }
    return 0;
}

参考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
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 205
using namespace std;
int n,m;
int dp[N][N],vis[N],w[N],ans[N][N];
vector<int>e[N];
void init()
{
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
	for(int i=0;i<=n;i++)
		e[i].clear();
}
void dfs(int root)
{
	int next;
	vis[root]=1;
	for(int i=0;i<e[root].size();i++)
	{
		next=e[root][i];
		if(!vis[next])
		{
			dfs(next);
			for(int k=m;k>=0;k--)
				for(int j=0;j<=k;j++)
					ans[root][k]=max(ans[root][k],ans[root][k-j]+dp[next][j]);
		}
	}
	for(int i=1;i<=m+1;i++)
		dp[root][i]=ans[root][i-1]+w[root];
}
int main()
{
	while(cin>>n>>m)
	{
		if(n==0&&m==0)
			break;
		init();
		for(int to=1;to<=n;to++)
		{
			int from,weight;
			cin>>from>>weight;
			e[from].push_back(to);
			w[to]=weight;
		}
		w[0]=0;
		dfs(0);
		cout<<dp[0][m+1]<<endl;
	}
	return 0;
}

思路

AC代码（1）：
使用了前向星这种特殊的边集数组来模拟链表实现对树的遍历。链接中博主对前向星做出了十分详细的介绍，这里不在赘述。
vis数组用来记录走过的位置，dp[root][k]表示必取根节点root访问k个城堡获取的最大价值，ans[root][k]表示不取根节点root访问k个城堡获取的最大价值。在构建好前
向星后，进入dfs进行深搜。注意此时的最大价值类似于01背包问题，所以第一层for循环逆序，正序会使得重复访问得到错误结果。由于dp表示必取根节点，所以在执行遍
历时上限应为m+1,0号结点价值为0必取，这里它也算作了一个城堡，所以最后的输出结果为dp[0][m+1]。在dfs的两层for循环中必须取到0，因为考虑到了根节点未取到的
情况。最后的状态转移方程dp[root][j]=ans[root][j-1]+money[root]意义为：根结点的价值+不取根节点向上遍历j-1个城堡的价值就是dp里遍历j个城堡的最大价值。dp
和ans数组的列始终应保持差1的状态（由数组本身的意义 取不取根节点决定的）。
AC代码（2）：
构建边集数组来存放图。边集数组map[a][b]表示以a为父结点有子节点数b。num[a]表示以a为父结点存放的子节点数，dp[][1]表示只取一个根节点的价值赋值为b，
dp[][0]初始化为0。dfs的遍历过程与一类似，这里只需要注意for循环里的下限即可。由于dp[][0/1]的价值是固定不变的无需更新，所以j的下限只需取到2，由于
dp[][0]并没有意义，所以k的下限只需取到1即可。状态转移方程与一类似。

注意事项

注意对状态转移方程的理解以及如何对树的遍历：上面介绍了两种方法，用数组模拟链表的前向星和用数组存图的边集数组。两种方法中最后的dp中的m均为m+1，因为把0号
结点当作为价值为0的0号结点，方便遍历。dfs中两层for循环的更新顺序与上下限也需要额外注意，由数组本身的意义来确定范围。

Color the ball

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
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define MAX 100005
int c[MAX];
int lowbit(int x)
{
	return x&(-x);
}
void change(int i,int n,int x)
{
	while(i<=n)
	{
		int s=lowbit(i);
		c[i]+=x;
		i+=s;
	}
}
int sum(int idx)
{
	int sum=0;
	while(idx>0)
	{
		int s=lowbit(idx);
		sum+=c[idx];
		idx-=s;
	}
	return sum;
}
int main()
{
	int N,a,b;
	while(cin>>N&&N!=0)
	{
		memset(c,0,sizeof(c));
		for(int i=0;i<N;i++)
		{
			cin>>a>>b;
			change(a,N,1);
			change(b+1,N,-1);
		}
		for(int i=1;i<=N;i++)
		{
			if(i==1)
				cout<<c[i];
			else
				cout<<" "<<sum(i);
		}
		cout<<endl;
	}
	return 0;
}

思路

典型的树状数组问题，由于数据量过大且是区间问题，所以用树状数组可以快速求解。a到b的区间+1可以表示为a到上限+1 b到上限-1.

注意事项

理解树状数组的存储原理。

本文标题:10-16 热身赛

文章作者:Hippopmonkey

发布时间:2016-10-20, 20:33:22

最后更新:2017-02-11, 13:29:10

原始链接:http://xuboming8.github.io/2016/10/20/10-16-热身赛/

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

文章目录
  1. 1. 周赛（一）
    1. 1.1. Triangle
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
      4. 1.1.4. 注意事项
    2. 1.2. Vitya in the Countryside
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
      4. 1.2.4. 注意事项
    3. 1.3. Anatoly and Cockroaches
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
      4. 1.3.4. 注意事项
    4. 1.4. Efim and Strange Grade
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
      4. 1.4.4. 注意事项
    5. 1.5. The more, The Better
      1. 1.5.1. 参考AC代码(1)
      2. 1.5.2. 参考AC代码（二）
      3. 1.5.3. 参考AC代码（三）
      4. 1.5.4. 思路
      5. 1.5.5. 注意事项
    6. 1.6. Color the ball
      1. 1.6.1. 参考AC代码
      2. 1.6.2. 思路
      3. 1.6.3. 注意事项
|