A
Educational Codeforces Round 52 (Rated for Div. 2)
还没做，待补。
B
Codeforces Round #514 (Div. 2)
待补……
C
Educational Codeforces Round 52 (Rated for Div. 2)
题目大意
给出一个数组，如上图，a[x] = y表示在第x列中有y个1x1的正方形，我们每次可以沿着平行于x轴切一刀，舍弃上面部分，且舍弃部分的面积要小于k，求最少多少步可以切到所有列正方形数相同。
思路
简单的模拟，我们按照题意从上往下切就好了。用前缀和预处理出每一行的正方形数，因为只能平行于x轴切，所以这一行要么整体能切掉，要么就不能切掉。而且相同的正方形数一定是n。
代码
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
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
int n,k,a[maxn],sum[maxn],maxx=0;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
maxx=max(maxx,a[i]);
sum[a[i]]++;
}
for(int i=maxx;i;i--) sum[i]+=sum[i+1];
int res=0,ans=0;
for(int i=maxx;i;i--)
{
if(sum[i]==n)
{
printf("%d\n",ans);
return 0;
}
if(res<sum[i]) ans++,res=k-sum[i];
else res-=sum[i];
}
return 0;
}
|
D
Codeforces Round #514 (Div. 2)
待补……
E
Educational Codeforces Round 52 (Rated for Div. 2))
题目大意
给出n个点和m条边，构成若干个图，每个图不能有重边和自环，求最多和最少的孤立顶点。
思路
- 最少：既然要求孤立顶点最少，那么就要求每加入一个点，要用去最多的边。其实就是保证尽可能构成完全图，所以找到k*(k-1)/2>=m的最小k，剩下的点都是孤立顶点了。
- 最多：一条边可以连2个点，2条边最多只能连3个点，……，显然每条边都连2个没有与其他边相连的点消耗的边最多。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
int main()
{
long long n,m;
scanf("%lld%lld",&n,&m);
long long minn=max(n-m*2,0ll),maxx;
if(!m) maxx=n;
else
{
long long now=1;
while(m>0)
{
m-=now;
now++;
}
maxx=n-now;
}
printf("%lld %lld\n",minn,maxx);
return 0;
}
|
F
Codeforces Round #514 (Div. 2)
题目大意
模拟，用形如下图的印章，再给出一个由“.”和"x"组成的形状，判断能否用下图的印章印出给定的形状（可以印无数次）（“ . ”代表“空”）
xxxx.xxxx
思路
另开一张图，对于原图的一个点（无论是".“还是"x”，只要它周围八个点都是"x"，那就在新图上以这个点的坐标为中心盖一个章，最后判断新图和原图是否相同，若相同，那么就可以；反之则不行。
代码
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< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=2005;
char a[maxn][maxn],map[maxn][maxn];
int n,m;
int dx[9]={0,0,0,1,1,1,-1,-1,-1};
int dy[9]={0,1,-1,0,1,-1,0,1,-1};
bool judge(int x,int y)
{
for(int i=1;i<=8;i++)
if(a[x+dx[i]][y+dy[i]]!='#') return false;
return true;
}
void work(int x,int y)
{
for(int i=1;i<=8;i++) map[x+dx[i]][y+dy[i]]='#';
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) map[i][j]='.';
for(int i=2;i<n;i++)
for(int j=2;j<m;j++)
if(judge(i,j)) work(i,j);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]!=map[i][j]) return printf("NO\n"),0;
printf("YES\n");
return 0;
}
|
G
Codeforces Round #514 (Div. 2)
题目大意
定义一天的长度为L,每次休息的时间为a,有n个客人，t_i表示他在这一天到来的时间，l_i表示他到来以后持续占用的时间。保证
ti+li≤ti+1
问最多能休息的次数。
思路
程序设计入门题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
long long n,l,a,b[maxn],c[maxn],ans=0;
int main()
{
scanf("%lld%lld%lld",&n,&l,&a);
for(int i=1;i<=n;i++) scanf("%lld%lld",&b[i],&c[i]);
b[n+1]=l;
for(int i=0;i<=n;i++)
{
long long t=b[i+1]-b[i]-c[i];
ans+=t/a;
}
printf("%lld\n",ans);
return 0;
}
|
H
Educational Codeforces Round 52 (Rated for Div. 2)
题目大意
在一个超市，顾客每购买a个巧克力棒，就会送b个巧克力棒。现在Vasya有s卢布，每个巧克力棒的价格是c卢布。求Vasya最多可以得到多少个巧克力棒。
思路
程序设计入门题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
long long s,a,b,c;
scanf("%lld%lld%lld%lld",&s,&a,&b,&c);
long long ans=s/(a*c)*b;
ans+=s/c;
printf("%lld\n",ans);
}
return 0;
}
|
总结
题目顺序和难度真的是一点关系都没有。
