正文索引 [隐藏]

A有趣的数字

我们称一个数是质数，而且数位中出现了 5 的数字是有趣的。
例如 5,59,457 都是有趣的，而 15,7 不是。
求 1 到 100000 中有趣的数的个数。 

没啥好说的，就硬来。
先用筛法打出素数表，再用check函数确认数位里是否含5。时间复杂度肯定是不优的，但填空题嘛能解出来就是AC。
最后答案是3282. 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

typedef long long ll;

const int LIM = 100000;

int p[LIM+1];
bool b[LIM+1];

void findPrimes(int n) 
{
    int cnt = 0;
    for (int i = 2; i <= n; i++)
	{
        if (!b[i])//判断并记录素数 
            p[++cnt] = i;
        for (int j = 1; j <= cnt && i*p[j] <= n; j++)//开始筛 
		{
            b[i*p[j]] = 1;//①
            if (i % p[j] == 0)  break;//②
        }
    }
}

bool check(int x)
{
	bool flag = 0;
	while (x != 0)
	{
		int  p = x % 10;
		if (p == 5)
		{
			flag = 1;
			break;
		}
		x /= 10;
	}
	if (flag == 0) return 0;
	else return 1;
}

int main()
{
	findPrimes(LIM);
	int ans = 0;
	rep(i, 1, LIM-1)
	{		
		if(check(p[i]) == 1) ans++; 
	}
	cout << ans;
	return 0;
}

B爬楼梯

蒜头君要爬楼梯。楼梯一共有 10 层台阶。
因为腿长的限制，每次最多能上 4 层台阶。
但是第 5,7 层楼梯坏掉了不能踩。
求上楼梯的方案数。

经典的爬楼梯问题其实是一个斐波那契数列，因为它一次能跨一步或者跨两步。设爬n级楼梯有f(n)中爬法，那么显然有f(n)=f(n-2)+f(n-1)，因为既可以在第n-2级楼梯上两级、也可以在第n-1级楼梯上一级。
初始状态为f(1)=1,f(2)=2，用dp递归或者递推求数列就行。

这里虽然步长不一样，但思想是同源地。因为第5级和第7级楼梯烂了，所以当n=5 or n=7时返回0就行。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

const int INF = 0X7F7F7F7F;

int ans(int n)
{
	 if(n == 1) return 1;
	 if(n == 2) return 2;
	 if(n == 3) return 4;
	 if(n == 4) return 8;
	 if(n == 5 || n == 7) return 0;
	 return ans(n-1) + ans(n-2) + ans(n-3) + ans(n-4);
}  

int main()
{
   cout << ans(10);
   return 0;
}

C七巧板

求问在以下图案的大三角形内部添加五条直线最多可以将大三角形分成多少个区域。 
例如下图一共有 7 个区域。 请在下图的基础上添加五条直线。 

这是一道数学相关的问题。

首先对于这样的平面划分问题，有这样一个公式：

[latexpage]
f_n=\frac{n*(n-1)}{2}+1

其中f(n)表示：n条直线能将一个平面分成f(n)个部分 。举个例子：

f(1) = 1*2/2+1 = 2 表示 一条直线将一个平面最多切割成两个平面
f(2) = 2*3/2+1 = 4 表示 两条直线将一个平面最多切割成四个平面
f(3) = 3*4/2+1 = 7 表示 三条直线将一个平面最多切割成七个平面
……

由上述公式可以得到，在最优划分情况下：
第一条直线穿过了一个平面
第二条直线穿过了两个平面
第三条直线穿过了三个平面……
那么不难得到，对于第n条直线，它最多穿过n个平面。

再看这道题，在初始情况下第一根直线显然这么画穿过的平面最多

那么答案就出来了，是47。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

const int INF = 0X7F7F7F7F;

int main()
{
	int x = 7, a = 6;
	//x表示初始有7个平面，a表示第一根直线能穿过6个平面 
    rep(i, 1, 5) x += a++;
    cout << x;
    return 0;
}

D苹果

有30个篮子，每个篮子里有若干个苹果，篮子里的苹果数序列已经给出。  现在要把苹果分给小朋友们，每个小朋友要么从一个篮子里拿三个苹果，要么从相邻的三个篮子里 各拿一个苹果。  苹果可以剩余，而且不同的拿法会导致不同的答案。比如对于序列 3 1 3，可以分给两个小朋友 变成 0 1 0；也可以分给一个小朋友变成 2 0 2，此时不能继续再分了。所以答案是2。 求问对于以下序列，最多分给几个小朋友？ 

7 2 12 5 9 9 8 10 7 10 5 4 5 8 4 4 10 11 3 8 7 8 3 2 1 6 3 9 7 1

据说不是贪心，但写贪心真的能过。对每个篮子能拿三个就拿三个，拿不了了就相邻的各拿一个，都不行了就去计算下一个篮子。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

const int INF = 0X7F7F7F7F;

int main()
{   
    int a[30], ans = 0;
    for(int i = 0; i < 30; i++) scanf("%d",&a[i]);
    for(int i = 0; i < 30; i++)
	{
		ans += a[i]/3;
		a[i] %= 3;
  	  	while(a[i] > 0 && a[i+1] > 0 && a[i+2] > 0)
  	  	{
			ans++;
			a[i]--;
		   	a[i+1]--;
		   	a[i+2]--;
	  	}
    }   
    printf("%d", ans); 
    return 0;
}

E方阵

广场上的小朋友们排成了整齐的方阵。具体来说，我们可以把每个小朋友看做是一个点，那么小朋友们就形成了 n×n的点阵。方阵中，小朋友A和小朋友B互相可以看见，当且仅当二人之间的连线不经过别的小朋友，且他们之间的距离不超过k（因为太远就看不见了）。我们想知道有多少对小朋友互相可以看见。(A,B)与(B,A)算同一对。 例如，n=2,k=1时答案为4，n=2,k=2时答案为6（距离为1的有4对，距离为2的有2对），n=3,k=2时答案为20。现在我们想要知道，当 n=1000,k=500时的答案是多少。由于答案过大，请回答对10^9+7取模后的结果。 

其实就是一个gcd。
因为它是一个nxn的点方阵，假设两个点(x1,y1)与(x2,y2)，设 a=|x1-x2|，b=|y1-y2|。
显而易见地，当且仅当gcd(a,b)==1，即二者互质时不会穿过别的点。
点阵中可能存在多对点满足 a=|x1-x2|，b=|y1-y2|，所以这样一对<a,b>对答案的贡献是(n-a)*(n-b)。如果a||b==0，也就是站在一行或一列上，此时给答案加上2n(n-1) 就行了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

typedef long long ll;

const int INF = 0X7F7F7F7F;
const int MOD = 1e9+7;

ll gcds[1001][1001];
ll ans;

ll gcd(ll a, ll b)
{
	if(b == 0) return a;
	return gcd(b, a%b);
}

int main()
{
	int n = 1000;
	int k = 500;
	for(int i = 1; i < n; i++)
		for(int j = 1; j < n; j++)
			if(gcds[i][j] == 0 && gcds[j][i] == 0)
        		{
        			gcds[i][j] = gcd(i, j);
        			gcds[j][i] = gcds[i][j];
        		}
    for(int i = 1; i < n; i++)
    	for(int j = 1; j < n; j++)
        	if(gcds[i][j] == 1 && i*i+j*j <= k*k)
        			ans += (n-i) * (n-j);
    ans = ans*2 + 2*n*(n-1);
    ans %= MOD;
    cout << ans; 
    return 0;
}