前言
初中了没法打小学生比赛了。膜拜小学但是吊打我的巨佬。但是虽然初中仍然能写炸 T1 并且只能口胡到 T2。
T1 矩形纸片
题目链接
来源 CZOJ。
题目思路
题面中的 $10^9$ 完全吓唬人用的。
考虑到 $1\leq a,b,c,d,x,y\leq 1000$，最暴力的方法开个 $2000\times 2000$ 大小的数组存每个位置是否覆盖。
时间复杂度 $\mathcal O(a\times b+c\times d+2000^2)$。
或者考虑容斥，用第一个的覆盖面积加上第二个的覆盖面积减去重合面积。特判如果 $(x,y)$ 与第一个纸片没有重合就没有重合面积。
Solution by @cyx2009
完整代码
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,d,x,y;
cin>>a>>b>>c>>d>>x>>y;
cout<<(a*b)+(c*d)-(x>a||y>b?0:min(a-x+1,c)*min(b-y+1,d))<<endl;
return 0;
}Code by @cyx2009
T2 奶牛农场
题目链接
来源 CZOJ。
题目思路
考虑贪心，对于每个为 $0$ 的位置只设置比前面高 $1$，尽可能的让后面的位置选的高度数量更多。
Solution by @cyx2009
完整代码
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int ans[100020];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>ans[i];
if(ans[i]==0)ans[i]=ans[i-1]+1;
}
for(int i=1;i<=n;i++)
{
if(ans[i]<=ans[i-1]||ans[i]>1000000000||ans[i]<=0)
{
puts("NO");
return 0;
}
}
puts("YES");
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}Code by @cyx2009
2 条评论
aaa
aaa