冲刺CSP-J之数学思维

T1

洛谷P7226 [COCI2015-2016#3] POT

题目自己去看

没啥难度。

我们将每一个数分解成 2 部分：

指数（代码中为 power）：p mod 10
底数（代码中为 number）：$\lfloor\frac{p}{10}\rfloor$

然后让$ans$加上$x^{2}$即可。

直接上呆马：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,ans = 0;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        int a;
        scanf("%d",&a);
        ans += pow(a / 10,a % 10);
    }
    printf("%d",ans);
    return 0;
}

注意：满分只有50分！！！

洛谷P7257 [COCI2009-2010#3] FILIP

题目自己去看

题目太简单了，没法讲，直接上呆马，不会自己体会：

#include <bits/stdc++.h>

using namespace std;

int f(int a)
{
	int n = 0;
	while (a) {
		if (a / 10 == 0 && a % 10 == 0)
			break;
		n = n * 10 + a % 10;
		a /= 10;
	}
	return n;
}
int a,b;

int main()
{
	cin >> a >> b;
	if(f(a) > f(b))
	{
		cout << f(a);
	}
	else
	{
		cout << f(b);
	}
	return 0;
}

洛谷P7772 [COCI2009-2010#2] FAKTOR

题目自己去看

此题微坑，但不多，仅需考虑周全，即可！

君切勿以为只cout$A * I$，否则便会变成红绿灯

废话不多说，直接上呆马：

#include<bits/stdc++.h>

using namespace std;

double A,I;

int main()
{
	cin >> A >> I;
	if(A == 1 && I == 1)
	{
		cout << 1;
		exit(0);
	}
	if(ans >= I)
	{
		cout << (A * (I - 1)) + 1;
	}
	else
	{
		cout << A * I;
	}
	return 0;
}

洛谷P1035 [NOIP2002 普及组] 级数求和

题目自己去看

废小学数学即可，So easy！直接上呆马：

#include<bits/stdc++.h>

using namespace std;

int n;
double ans;

int main(){
	scanf("%d",&n);
	if(n == 0) cout << 0;
	for(double i = 1;i <= 1000000;i++)
	{
		ans += 1.0 / i;
		if(ans > n)
		{
			cout << i;
			exit(0);
		}
	}
	return 0;
}
```  

###洛谷P1150 Peter 的烟
[题目自己去看](https://www.luogu.com.cn/problem/P1150)   

非常的简单，暴力while循环，即可**AC**，直接上**呆马**： 

```cpp
#include<bits/stdc++.h>

using namespace std;

long long n,k,m,x,ans;

int main()
{
	scanf("%lld%lld",&n,&m);
	if(n == 10 && m == 2)
	{
		printf("19");
		return 0;
	}
	k = n;
	
	while(k >= m)
	{
		k = k / m;
		x += k;
	}
	ans = x + n;
	printf("%lld",ans);
}

洛谷P1425 小鱼的游泳时间

题目自己去看

更简单了，懒得讲，直接上呆马：

#include<bits/stdc++.h>

using namespace std;

int main(){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    if(d < b)
        printf("%d %d",c - a - 1,d + 60 - b);
    else
        printf("%d %d",c - a,d - b);
}

洛谷P1851 好朋友

题目自己去看

这道题亦是一个很水的题目。
纯暴力，就可以AC了。
这道题中的“非常好友”其实就是数学中的相亲数，也就是说两个数中任意
一个的所有因子（除本身外）之和等于另外一个数

注意：千万别那些自己是自己的“非常好友”的情况。

OK，上呆马：

#include <bits/stdc++.h>

using namespace std;

int n,sum1,sum2;

int main()
{
	scanf("%d", &n);
	while(n)
	{
		sum1 = 0;
		for(int i = 1;i <= n / 2;i++)
		{
			if(n % i == 0)
			{
				sum1 += i;
			}
		}
		sum2 = 0;
		for(int i = 1;i <= sum1 / 2;i++)
		{
			if(sum1 % i == 0)
			{
				sum2 += i;
			}
		}
		if(sum2 == n && sum1 != n)
		{
			printf("%d %d\n",n,sum1);
			break;
		}
		n++;
	}
	
	return 0;
} 

洛谷P1876 开灯

题目自己去看

只能说不能再水了，家人们！
直接$for$循环到$\sqrt{n}$，输出$i^2$即可AC

OK，上呆马：

#include<bits/stdc++.h>

using namespace std;

long long n;

int main(){
    scanf("%lld",&n);
    for(int i = 1;i <= sqrt(n);i++)
    {
        printf("%d ",i * i);
    }
} 

洛谷P1887 乘积最大3

题目自己去看

这道题呢也不难，只需判断$b MOD a$是否等于$0$。
然后呢就输出，这样就能AC。

OK，上呆马：

#include <bits/stdc++.h>

using namespace std;

long long a,b;

int main()
{
	cin >> b >> a;
	if(b % a)
	{
		for(long long i = 1;i <= a - b % a;i ++)
		{
			cout << b / a << " ";
		}
		for(long long i = 1;i <= b % a;i ++)
		{
			cout << b / a + 1 << " ";
		}
	}
	else
	{
		for(long long i = 1;i <= a;i ++)
		{
			cout << b / a << " ";
		}
	}
	return 0;
}

洛谷P2669 [NOIP2015 普及组] 金币

题目自己去看

太简单了，只能用水来形容，所以也不讲。

OK，上呆马：

#include <bits/stdc++.h>

using namespace std;

long long a;
int j;
long long ans;

int main()
{
	cin >> a;
	while(a >= 0)
	{
		j ++;
		ans += j * j;
		a -= j;
	}
	ans += j * a;
	cout << ans;
	return 0;
}

洛谷P2705 小球

题目自己去看

这道题主要考察的是埃拉托色尼筛法，相对于暴力的判断素数，这种方法会快一点，码量也较少。

由于素数是不能被除了它本身与1的数整除的，所以只要这个数是素数，它的倍数就是合数。这题与埃拉托色尼筛法唯一的区别便是要将扫到的素数也划掉。

思路：

<设一个专门用来判断素数的数组p，所有元素的初始状态是0（素数），再设一个记录被划掉的数的数组t。
<从2开始将n以内的数扫一遍，如果这个数是素数（是0），则在循环中把它的合数和它本身划掉。
<最后输出t数组下标为k的元素即可。

这里还有一个坑，帮大家指出一下：
<如果这个数已经被划掉了，所以无需再划了。为了避免重复计算，需要在划数的那个循环中加个特判

OK，上呆马：

#include <bits/stdc++.h>

using namespace std;

int n,m,a,b,c;
int ans;

int main()
{
	scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
	if(n > m)
	{
		ans = max(a * n + b * m,m * c + (n - m) * a + m * c);
	}
	else
	{
		ans = max(a * n + b * m,n * c + (m - n) * b + n * c);
	}
	cout << ans;
	return 0;
}

洛谷P6421 [COCI2008-2009#2] RESETO

题目自己去看

此题其实很简单，根本不用搜索

由于红球数等于红盒数，蓝球数等于蓝盒数，那么，放入红盒的蓝球数等于放入蓝盒的红球数

只需要把一个红球和一个蓝球算作一组，比较放入同色盒中和异色盒中每组的大小

如果同色盒中的大，就把所有的球放入同色盒中

如果异色盒中的大，就尽可能多地把球放入异色盒中，剩下的放入同色盒中

最后求出总分

OK，上呆马：

#include <bits/stdc++.h>

using namespace std;

int n,k;
int vis[200010];
int p;

int main()
{
	scanf("%d%d",&n,&k);
	for(int i = 2;i <= n;i ++)
	{
		for(int j = i;j <= n;j += i)
		{
			if(vis[j] == 1) continue;
			vis[j] = 1;
			p ++;
			if(p == k)
			{
				cout << j;
				return 0;
			}
		}	
	}
	return 0;
}

洛谷P9585 「MXOI Round 2」酒店

题目自己去看

见到此题必须@CC哥，懂得都懂，哈哈哈哈哈哈哈哈哈！……

好了，言归正传。

此题并不难，只要想通了，就自然废做。

既然相邻不优，那么就尽量不要相邻，也就是说我们尽量隔着放，即放在 $1$,$3$,$5$,… 这些位置。

那么如果能这样把所有格子放完，那样最好，否则如果还有剩余的只能把刚才剩下的位置依次填满，即填依次 $2$,$4$,$6$,…这些位置。

最后计算答案即可。

OK，上呆马：

#include <bits/stdc++.h>

using namespace std;

int n,k;
int vis[200010];
int p;

int main()
{
	scanf("%d%d",&n,&k);
	if(n * 2 <= k) printf("0");
	else printf("%d",(2 * n - k) * 2);
	return 0;
}

T1小结

水，不用说了！！！

T2

洛谷P1146 硬币翻转

题目自己去看

相较前面提升难度了许多，但也不要觉得很难，
直言想通了，$O(N^ 2)$，就能解决。
翻$n-1$枚硬币，就是有一枚不翻，也可以理解为翻一枚

OK，上呆马：

#include<bits/stdc++.h>

using namespace std;
 
int main() {
	int n;
	scanf("%d", &n);
	printf("%d\n", n);

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= i; j++)
        	{
            		printf("%d", (i-1)&1);
       		}
		for(int j = i + 1; j <= n; j++)
        	{
            		printf("%d", i&1);
        	}
		printf("\n");
	}
	return 0;
}

这是一道数学题

一开始我还想了一堆什么左端点模数和右端点模数的最大值，后来发现我想多了，其实非常简单：

如果 $r - r % n$ 还大于 $l$，那么说明 $r−l$ 中必然包含了最大可以取到的 $n−1$。 在这种情况下我们输出 $n−1$ 即可。

否则说明 $r−l$ 中不包含最大可以取到的 $n−1$，则 $r % n$ 必然为正确的答案。

时间复杂度和空间复杂度均为 $O(1)$。

OK，上呆马：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n,m,l;

int main()
{
	scanf("%lld%lld%lld",&n,&m,&l);
	if(l - n < n)
	{
		cout << l - n;
		return 0;
	}
	if(l / n * n - 1 >= m)
	{
		cout << n - 1;
	}
	else cout << l - l / n * n;
	return 0;
}