考试的时候

T1

给出$n$个矩阵的左上角和右下角的坐标，如果这个矩形和其他矩形没有公共部分，则可以扩展，求最多有几个矩形可以扩展。
第一档数据是$n\le 2500$，不知道算不算什么提示有没有什么暴力的方法是可以卡着这个过的。但是感觉可以先把答案设为$n$，左端点排序，然后标记被覆盖的点，如果这个点已经被覆盖，则$n--;$然后重新看一下最左边那个矩形有没有重的。
突然感觉不是太可行，因为后面的矩形可能会与前面的中间隔一段距离，然后又与其他矩形重合。
可以先把所有覆盖的点扫一遍，每次扫到这个点就让这个点的值$+1$，然后重新再扫一遍，如果该点的值不为$1$，则说明此矩形一定与其他的有公共边，而且突然又注意到矩形不能互相覆盖，所以只扫边框应该就行了。然后就去照着这个思路码了。

#include
using namespace std;
#define N 25010
int read()
{int num=0;bool flag=1;char c=getchar();for(;c<'0'||c>'9';c=getchar()) if(c=='-') flag=0;for(;c>='0'&&c<='9';c=getchar()) num=(num<<1)+(num<<3)+c-'0';return flag?num:-num;
}
int flag[1000][1000],ans,n;bool chong[2];
struct ylsdjx{int a,b,c,d;}yls[N];
int main()
{n=read();ans=n;for(int i=1;i<=n;i++){yls[i].a=read();yls[i].b=read();yls[i].c=read();yls[i].d=read();for(int j=yls[i].a+1;j<yls[i].c;j++) {flag[j][yls[i].b]++;flag[j][yls[i].d]++;}for(int j=yls[i].b;j<=yls[i].d;j++) {flag[yls[i].a][j]++;flag[yls[i].b][j]++;}}for(int i=1;i<=n;i++){chong[0]=0;for(int j=yls[i].a+1;j<yls[i].c;j++) {if((flag[j][yls[i].b]>1)||(flag[j][yls[i].d]>1)) {chong[0]=1;break;}}if(chong[0]==0) for(int j=yls[i].b;j<=yls[i].d;j++) {if((flag[yls[i].a][j]>1)||(flag[yls[i].b][j]>1)) {chong[0]=1;break;}}if(chong[0]==1) ans--;}cout<<ans;
}

写出了极其丑陋的暴力，然而连样例也没过，然后突然发现坐标是在 [ 0 , 1 6 ] [0,1^6] [0,16]的范围内，众所周知，不看数据范围就写代码无异于是耍流氓。这个方法显然会炸掉。所以我觉得还是应该左端点排序然后一个一个扫可能更优。然后就陷进去思考该怎么做细节，没想出来，开始做$T2$。

T2

一摞$n$个圆形喷泉，层给出半径和容积，$q$次询问：向第$i$个里面倒$j$个水，输出水最终会到达哪一层。
先暴力模拟一下。

#include
using namespace std;
#define N 100010
int shang,v[N],r[N],a,b,n,q;
int read()
{int num=0;bool flag=1;char c=getchar();for(;c<'0'||c>'9';c=getchar()) if(c=='-') flag=0;for(;c>='0'&&c<='9';c=getchar()) num=(num<<1)+(num<<3)+c-'0';return flag?num:-num;
}
void ask(int x,int y)
{y-=v[x];shang=x;if(y<=0) {printf("%d\n",x);return ;}for(int i=x;;i++){if(r[i]>r[shang]) {y-=v[i];shang=i;}if(y<=0) {if(i>n)puts("0");else printf

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！