2016-11-02

10-30 热身赛

周赛（三）

Bits

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

求给定范围内数字的二进制表示中1最多的并输出该数字。

参考AC代码

#include<iostream>
using namespace std;
int main()
{
    long long a, b;
    int n;
    cin>>n;
    while(n--)
	{
        cin>>a>>b;
        for(long long i=1; (a|i) <= b; i<<=1)
            a |= i;
        cout<<a<<endl; 
    }
    return 0; 
}

思路

因为本题的数据量很大，所以一般的操作是不能过的，使用位运算可以快速解答。从低位开始把0变为1，判断是够小于上限b，循环结束后输出1个数最多的二进制数。

注意事项

或|运算的作用是把0“变为”1，与&运算符的作用是把1“变为”0。

Function

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

给定数组An的值后给定l与r的值求出表达式的值。

参考AC代码

#include<iostream>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m,a[100050],next[100050];
		scanf("%d",&n); 
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);  
		for(int i=1;i<=n;i++)
		{
			next[i]=-1;
			for(int j=i+1;j<=n;j++)
				if(a[j]<=a[i])
				{
					next[i]=j;
					break;
				}
		}
		 scanf("%d",&m);  
		while(m--)
		{
			int l,r;
		    scanf("%d%d",&l,&r);  
			int F=a[l];
			for(int i=next[l];i<=r;i=next[i])
			{
				if(i==-1)
					break;
				F%=a[i];
			}
			 printf("%d\n",F);  
		}
	}
	return 0;
}

思路

题目最后可以划为A(l)%A(l+1)%~~~%A(r)。由于正常的暴力遍历会超时，所以在计算前先计算每一个An的next值：下一个小于等于该数的第一个位置。只有除数小于
被除数经过%运算才不等于被除数本身，所以最后实现的时候表现为跳着进行%运算。

注意事项

如果挨个进行%运算会超时，考虑的%运算的特点即可写出每一位置的next值，即可AC。

Ball

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

给定数组a和数组b和若干段区间，数组a在区间内可以任意交换，问最后交换后数组a可否等于数组b

参考AC代码

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
	int x,id;
}a[1050];
int b[1050];
bool cmp(node x,node y)
{
	return x.id<y.id;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m,flag=1;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].x;
			a[i].id=-1;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>b[i];
			for(int j=1;j<=n;j++)
				if(a[j].x==b[i]&&a[j].id==-1)
				{
					a[j].id=i;
					break;
				}
		}
		for(int i=1;i<=m;i++)
		{
			int s,e;
			cin>>s>>e;
			sort(a+s,a+e+1,cmp);
		}
		for(int i=1;i<=n;i++)
			if(a[i].x!=b[i])
			{
				flag=0;
				break;
			}
		if(flag)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}

思路

记录下数组a的每一个数字在数组b中出现的位置id（未找到初始化为-1），最后区间的交换实际为位置id的sort升序排序，排序后判断a是否等于b即可。

注意事项

使用贪心算法才是正确的解法，交换实际为id的排序。

Chilly Willy

Problem Description

Input

Output

Sample Input && output

题目要求

找出n位数中能被2，3，5，7同时整除的最小数

参考AC代码

#include <iostream>   
using namespace std;  
int main()  
{  
    int n,p,i;  
    scanf("%d",&n);  
    if(n<3)  
    {  
        printf("-1");  
    }  
    else if(n==3)  
    {  
        printf("210");  
    }  
    else  
    {  
        printf("1");  
        for(i=0,p=50;i<n-4;i++)  
        {  
            printf("0");  
            p=p*10%210;  
        }  
        printf("%03d\n",p);  
    }  
    return 0;  
}

思路

找规律题。后面三个数每6个是一个循环，只需在中间添0即可。

Pagodas

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

有编号为1-N的N座塔，其实两人位置为a和b开始修塔，每次修塔的位置要满足i=j+k||i=j-k，某个人先开始，最后谁无法修塔谁输，求谁赢

参考AC代码

#include <iostream>
using namespace std;
int main()
{
    int T,n,a,b;
    cin>>T;
    for(int i=1;i<=T;i++)
	{
        scanf("%d%d%d",&n,&a,&b);   
        while(b)
		{
            if(a>b) swap(a,b);
            b%=a;
        }
        if(n/a%2) printf("Case #%d: Yuwgna\n",i);
        else printf("Case #%d: Iaka\n",i);
    }
    return 0;
}

思路

归纳可发现最后剩下塔的数量一定是一个以gcd（a，b）为差的等差数列（或者全部修完，可以看成差为0的等差数列），N/gcd（a，b）就是可以修的全部塔的个数，只需判
断它的奇偶性即可。

本文标题:10-30 热身赛

文章作者:Hippopmonkey

发布时间:2016-11-02, 00:02:09

最后更新:2017-02-03, 20:38:00

原始链接:http://xuboming8.github.io/2016/11/02/10-30-热身赛/

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