这场全是数学题啊。。
A
题意
给你一个数n，对它进行k次操作，问结果是多少 每次操作n加上它用十进制表示的每一位最小值乘最大值
题解
给的n和k非常大，乍看起来以为是要什么公式来做。。但实际运算了一下 很容易看到如果结果包含一个0 那么每次操作之后数其实都不会变了 因为最小值0 自己尝试一下就会发现 这种运算很容易出现含0的结果 当然最后题解证明了一下81次内一定可以 我们写的时候就猜就好了。
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
| #include<cstdio>
#include<algorithm>
using namespace std;
int maxdig,mindig;
void finddig(long long res){
maxdig=0,mindig=9;
while(res){
int tmp=res%10;
maxdig=max(maxdig,tmp);
mindig=min(mindig,tmp);
if(mindig==0){
return;
}
res/=10;
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
long long a,k;
scanf("%lld%lld",&a,&k);
for(long long i=1;i<k;++i){
finddig(a);
if(mindig==0){
break;
}
a+=(maxdig*mindig);
}
printf("%lld\n",a);
}
return 0;
}
|
B
题意
n个人取野营 每个人有一个参数e 对这个人必须e个人以上组队才可以成一组 问最多分几组 允许有人没有组
题解
和之前有一轮老奶奶的题很像。。很明显我们这个要尽可能少人组队 因为要求是最多组 所以实际上就是只要可能就组队 把人数排个序然后依次计算只要人够了就组队就成
还有一个问题是需要稍稍优化一下。。一开始整个遍历tle了。。如果剩余人数已经比当前的系数小那么剩下的人肯定组不了队直接结束即可 截掉之后瞬间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<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int coun[200010];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
int tmp;
for(int i=0;i<n;++i){
scanf("%d",&coun[i]);
}
sort(coun,coun+n);
int res=0,remai=0,last=0;
for(int i=0;i<n;++i){
if(coun[i]!=last){
if(last!=0){
res+=remai/last;
remai=remai%last;
}
last=coun[i];
}
if((n-i+remai)<last){
break;
}
++remai;
}
res+=remai/last;
printf("%d\n",res);
}
return 0;
}
|
C
题意
给四个数A，B，C，D 四个数划分出中间的三个闭区间 从三个区间分别取值作为一条边，能拼成三角形的有几种
题解
显然这种取值方法我们不需要考虑重复的问题 因为不可能会出现第一个数比第二个数大的情况 然后分两个问题来考虑
组成三角形的条件我们都很清楚 检验两边之和是不是大于第三边即可 对于某一个固定的两小边之和 我们可以直接得出第三边可能的取值 而每一个固定的两小边之和会出现几次是我们要考虑的下一个问题
仔细思考一下可以看出 两小边取值的区间从最低值到最高值是连续的 而且是类似 1 2 3 3 3 2 1 这样的递增再递减序列 它的规律是递增的最大值只能取到两个小边区间长度的小值，而递增的长度是两个小边区间长度的大值，如果不能递增就是维持不变 而后递减至1 这样我们就有了规律 结合起来就能够算出答案
有一个问题要注意的是 题目给的范围实际上在某一个两小边值得次数乘上第三边可能得取值这一次乘法就会爆int。。所以一开始wa了一次。。后面全改longlong就没事了。。
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
| #include<cstdio>
#include<algorithm>
using namespace std;
int main(){
long long a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
long long x=b-a+1,y=c-b+1,z=d-c+1;
long long minnum=min(x,y),maxnum=max(x,y);
long long maxval=d;
long long res=0;
long long tmpnum=0,tmpval=a+b;
for(long long i=0;i<maxnum;++i){
if(tmpnum<minnum){
++tmpnum;
}
if(tmpval>maxval){
long long tmp=z*tmpnum;
res+=tmp;
}else{
long long tmp=tmpnum*max(0LL,tmpval-c);
res+=tmp;
}
++tmpval;
}
while(tmpnum){
--tmpnum;
if(tmpval>maxval){
long long tmp=z*tmpnum;
res+=tmp;
}else{
long long tmp=tmpnum*max(0LL,tmpval-c);
res+=tmp;
}
++tmpval;
}
printf("%lld\n",res);
return 0;
}
|
D
题意
给n和s 要你想办法给n个正整数其和为s 并给出一个其中的数k 如果对方不能够从这n个数中挑出一部分令其和为k或s-k 那么你就赢了 问对于给定的n和s有没有必胜策略
题解
严谨的证明一样需要看题解。。做题的时候我的思路大概是这样想的 如果s<2*n 那么我们选的序列n一定会带有元素1，而且这种时候无论怎么选都会让每一种和都能得到 而s>=2*n的时候 我们可以让n-1个元素都是2 最后一个元素是剩下的值也是大于等于2的 那么这时候无论如何都拼不出1来 就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int n,s;
scanf("%d%d",&n,&s);
if(n*2>s){
printf("NO\n");
}else{
printf("YES\n");
for(int i=1;i<n;++i){
printf("2 ");
}
printf("%d\n1\n",s-(n-1)*2);
}
return 0;
}
|
E
题意
n个墙 我们想要让墙的高度一致 可以有三种操作 加一个砖块 减一个砖块 挪一个砖块 有分别的花费 问最小的花费
题解
我看到这题的时候已经没时间了。。看来一下题解 大致思路倒是很简单 假设我们想要达到的高度是已知的 我们只需要看差的高度和以及多的高度和即可 然后一部分可以移动另一部分需要加或减 这样我们统计过前缀和之后用二分查找可以logn时间确定花费 遍历可能的高度即可
以及一个小问题 挪砖块的花费要先处理成挪或者是加砖块减砖块花费之和的最小值 也很好理解就不多说了