广工业新生赛

自用笔记算法

广工业新生赛

Problem A


参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
long long fun(long long n)
{
	if(n<=1)
		return 0;
	int i;
	for(i=1;i*2<=n;i*=2);
	return i-1+fun(n-i);
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		long long n;
		cin>>n;
		cout<<fun(n)<<endl;
	}
	return 0;
}

思路

找规律发现2^n的最大高兴值为2^n-1，所以只需找出小于n最大的2^n的数，并递归计算剩下的n-i即可。

Problem B

参考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<iostream>
using namespace std;
long long lowestOne(long long n)  
{  
        long long Ret = 0;  
        while(n)  
        {  
               n>>=1;  
               Ret += n;  
         }  
         return Ret;  
}  
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		long long n,re;
		cin>>n;
		re=lowestOne(n);
		cout<<re<<endl;
	}
	return 0;
}

思路

（一）使用公式

（二）另类公式
N!所含质因子2的个数等于N减去N的二进制表示中1的数目。
计算二进制中1的数目代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//用 n&(n-1) 来消掉n的从右往左数的第1个1   
int count1(int n)  
{  
    int sum = 0;  
    while(n)  
    {  
        n &= (n-1);  
        sum++;  
    }  
    return sum;         
}  
  
//质因子2的个数或最右边一位1的位数  
int lowestOne(int n)  
{  
       return n-count1(n);  
}

Problem C

参考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 <cstring>
#include <climits>
#define LL long long 
using namespace std;
int main()
{
	int T;
	cin>>T;
	LL n,a,b,c;
	while(T--)
	{
		cin>>n>>a>>b>>c;
		int tmp = 4 - (n%4);
		if(tmp==4)
		{
			puts("0");
			continue;
		}
		if(tmp==1)
		{
			LL mn=INT_MAX;
			if(mn>a) mn=a;
			if(mn>(b+c)) mn=b+c;
			if(mn>(c+c+c)) mn=c+c+c;
			cout<<mn<<endl;
		}
		if(tmp==2)
		{
			LL mn=INT_MAX;
			if(mn>b) mn=b;
			if(mn>(a+a)) mn=a+a;
			if(mn>(c+c)) mn=c+c;
			cout<<mn<<endl;
		}
		if(tmp==3)
		{
			LL mn=INT_MAX;
			if(mn>c) mn=c;
			if(mn>(a+a+a)) mn=a+a+a;
			if(mn>(a+b)) mn=a+b;
			cout<<mn<<endl;
		}
	}
	return 0;
}

思路

需要考虑一下特殊情况：
1.差1本的时候除了买一本a，也需考虑b+c以及3c的情况
2.差2本的时候需要考虑2c的情况。
3.其余为可以想到的基本情况。

Problem D

参考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
#include <iostream>
using namespace std;
int a[200];
int main()
{
	int T,n;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		for (int i=1;i<=n;i++) 
			scanf("%d",&a[i]);
		int ans=0;
		for (int i=1;i<=n;i++)
		{
			if (a[i]==0) ans++;
			if (a[i]==3&&i>1)
			{
				if (a[i-1]==1) a[i]=2;
				if (a[i-1]==2) a[i]=1;
			}
			if (a[i]==3&&i==1)
			{
				if (a[i+1]==1) a[i]=2;
				if (a[i+1]==2) a[i]=1;
			}			
			if (a[i]==a[i-1]&&a[i]!=0&&a[i]!=3)
			{
				a[i]=0;
				ans++;
			}
		}
		printf("%d\n",-24*ans);
	}
}

思路

需要注意如果连续2天相等且都是在运动的话，休息天数要加一并且该位置的值需赋为0.因为题目明确说明不会连续2天运动。

Problem H

参考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
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000050];
void FindNumsAppearOnce(int* data, int length)
{
    int OR = 0 ;
    for (int i = 0 ; i < length ; i++)//依次异或数组中的每一个数
        OR = OR ^ data[i] ;
    int index = 1 ;
    while ((OR & 1) != 1 && (index < 8 * sizeof(int)))//从右向左找到异或结果中第一个为1的位的位置
    {
        OR = OR>>1;
        index++;
    }
    int num1 = 0 ;
    int num2 = 0 ;
    for (int j = 0 ; j < length ;j++)
    {
        int temp = data[j];
        temp = temp >> (index - 1) ;//向右移位到index的位置
        if ((temp & 1) == 1) //判断该位是否为1
            num1 = num1 ^ data[j];
        else
            num2 = num2 ^ data[j] ;
    }
    cout<<min(num1,num2)<<" "<<max(num1,num2)<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		FindNumsAppearOnce(a,n);
	}
}

思路

本题的是实质是求出数组中唯一两个只出现过一次的数，且要求时间复杂度为O（n），空间复杂度为O（1）。
使用暴搜时间复杂度O（n²）会超时，使用hash表同样会因为空间复杂度不是O（1）超时，所以为了满足这两点使用位运算即可。

Problem J

参考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
#include <string.h>
#include<iostream>
#include <algorithm>  
using namespace std;  
int T,n,ans;  
bool notPrime[10009];  
int lst[1235],num,index1;   
void init() 
{
    memset(notPrime,false,sizeof(notPrime));  
    notPrime[1]=notPrime[0]=true;  
    for(int i=2;i<=5005;++i)  
        for(int j=2;i*j<10009;++j)  
            notPrime[i*j]=true;  
    num=0;  
    for(int i=0;i<10009;++i)  
        if(!notPrime[i])  
           lst[num++]=i*i;  
}  
int main() 
{  
    init();  
    cin>>T;
    while(T--)
	{  
        cin>>n; 
        index1=lower_bound(lst,lst+num,n)-lst;         
        if(index1==0||n-lst[index1-1]>lst[index1]-n)   
           cout<<lst[index1]<<endl;  
        else  
           cout<<lst[index1-1]<<endl;  
    }  
    return 0;  
}

思路

打表出所有质数进而打表出所有质数的平方。使用lower_bound找出大于等于查找索引的第一个位置，下面只需判断后一个和前一个哪个离索引近就输出哪个即可。

本文标题:广工业新生赛

文章作者:Hippopmonkey

发布时间:2016-12-05, 22:19:36

最后更新:2016-12-05, 22:57:38

原始链接:http://xuboming8.github.io/2016/12/05/广工业新生赛/

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

文章目录
  1. 1. 广工业新生赛
    1. 1.1. Problem A
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
    2. 1.2. Problem B
      1. 1.2.1. 参考AC代码
      2. 1.2.2. 思路
    3. 1.3. Problem C
      1. 1.3.1. 参考AC代码
      2. 1.3.2. 思路
    4. 1.4. Problem D
      1. 1.4.1. 参考AC代码
      2. 1.4.2. 思路
    5. 1.5. Problem H
      1. 1.5.1. 参考AC代码
      2. 1.5.2. 思路
    6. 1.6. Problem J
      1. 1.6.1. 参考AC代码
      2. 1.6.2. 思路
|