A
题意
n*m的矩阵 可以在任意一条边上放灯 灯可以照到边连着的小矩形 问最少需要几盏灯能点亮整个矩阵
题解
实际上推理一下就可以看出来了 每两个小矩形需要一盏灯 如果最后是单个的还需要一盏
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
int ans=n*m/2;
if((n*m)%2){
++ans;
}
printf("%d\n",ans);
}
return 0;
}
|
B
题意
有n+1个granny 一开始只有一个granny在场地 她可以一次叫任意个granny 但每个granny有自己的人数要求 如果她来的时候人数不达标她就会走 人数包括同时喊来的其他人但不包括她自己 问最多能聚集几个granny
题解
也很简单 按照要求聚集人数来存 然后逐个求sum 如果sum[i]>i那么就说明是能够达到这个数字的 求满足条件的最大的sum[i]
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
| #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gran[200020],su[200020];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
int tmp;
memset(gran,0,sizeof(gran));
memset(su,0,sizeof(su));
gran[0]=su[0]=1;
for(int i=0;i<n;++i){
scanf("%d",&tmp);
++gran[tmp];
}
int ans=1;
for(int i=1;i<=n;++i){
su[i]=su[i-1]+gran[i];
if(su[i]>i){
ans=su[i];
}
}
printf("%d\n",ans);
}
return 0;
}
|
C
题意
给一个矩阵 定义方式见题 问从x1,y1到x2,y2的的路径和有多少种可能 只能向下或向右走
题解
给的矩阵很容易看出 向下的值比向右的值大1 也就是一次向下和向右操作的颠倒会差1 推理一下很容易发现 可能的路径和是下限到上限的所有值 下限是一直向右最后向下 上限是一直向下最后向右 再计算一下就能推出差值实际上就是(x2-x1)*(y2-y1) 宽度决定一个差1会积累几次 高度决定积累几个差1 最后答案就是差值+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
long long x1,x2,y1,y2;
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
long long tmp=(x2-x1)*(y2-y1);
long long res=tmp+1;
printf("%lld\n",res);
}
return 0;
}
|
D
题意
一年n个月 一个月ki天 每天的拥抱值是所在月份的天数 要选连续的x天 问怎么选能让拥抱值最大 可以跨年
题解
跨年问题很好解决 我们计算两年的就可以了 而后我们可以证明 答案的右边界一定是卡着月份结束的 反证法可以推出来 当然做题时候就是靠感觉了 然后只要试每个边界就完了
然而我写的tle了。。用了二分查找依旧tle。。方法写的还是不太好看起来。。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
long long month[400020],su[400020];
long long last(int t){
long long tmpindex;
while(tmpindex=(upper_bound(su,su+n+1,t)-su),tmpindex!=(n+1)){
return su[tmpindex]-t;
}
return 0;
}
long long val(long long start,long long len){
long long res=0,las=0,tmpindex;
while(tmpindex=(upper_bound(su,su+n+1,start)-su),tmpindex!=(n+1)){
if(len==0){
break;
}
int i=tmpindex;
long long tmplen=min(len,su[i]-start);
las=0;
if(i!=0){
las=su[i-1];
}
long long calst=start-las+1;
res+=(calst+calst+tmplen-1)*tmplen/2;
start+=tmplen;
len-=tmplen;
}
return res;
}
int main(){
int x;
scanf("%d%d",&n,&x);
for(int i=0;i<n;++i){
scanf("%lld",&month[i]);
month[n+i]=month[i];
}
n=n*2;
su[0]=month[0];
for(int i=0;i<n;++i){
su[i+1]=su[i]+month[i+1];
}
long long ans=val(0,x),start=0,las=x;
long long res=ans;
long long tmp=0;
while(tmp=last(las)){
ans-=val(start,tmp);
ans+=val(las,tmp);
res=max(res,ans);
start+=tmp;
las+=tmp;
}
printf("%lld\n",res);
return 0;
}
|