T1 妹子
70pts
直接比较，若其中一个矩形的较长边大于另一个矩形较长边，较短边大于另一个矩形的较短边，则可以。
100pts
较小的矩形还可以通过旋转放到另一个矩形中，枚举旋转的角度a（0°<a<90°），看是否满足题意。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const double pie=acos(-1);
int n,a1,b1,a2,b2;
int read()
{
int sum=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;
}
int main(){
// freopen("girls.in","r",stdin);
// freopen("girls.out","w",stdout);
n=read();
while(n--){
a1=read();b1=read();a2=read();b2=read();
if(a1<b1)swap(a1,b1);
if(a2<b2)swap(a2,b2);
if(a1<=a2&&b1<=b2){printf("Yes\n");continue;}
if(a1>=a2&&b1>=b2){printf("Yes\n");continue;}
if(a1*b1>a2*b2){
swap(a1,a2);swap(b1,b2);
}
int flag=0;
for(double i=0;i<=90;i+=0.01)
{
if(a1*sin(i*pie/180)+b1*cos(i*pie/180)<=a2&&a1*cos(i*pie/180)+b1*sin(i*pie/180)<=b2)
{
printf("Yes\n");flag=1;break;
}
}
if(!flag)printf("No\n");
}
return 0;
}
T2旅程
100pts
把询问和修改离线保存下来。
先把该删的边删完，最终的图跑一遍 Floyd最短路，然后倒序加边复原，这样我们就把删边转化为了加边。
对于新加的边(x, y)，边权为 w，我们穷举所有的有序点对(i, j)且(i≠j)
若dis[i][x]+w+dis[y][j]<dis[i][j]，则更新 dis[i][j]。
更新所有点对复杂度 O(n2)，不会超 时。
并且由于是最短路，一条边不会重复经过，可以放心更新。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=100005,inf=0x3f3f3f3f3f;
int n,m,c[N],x[N],y[N],ans[N];
int a[205][205],d[N],vis[205][205],tot=0;
int read()
{
int sum=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;
}
void print(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10+'0');
}
int main(){
// freopen("journey.in","r",stdin);
// freopen("journey.out","w",stdout);
n=read();m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
for(int i=1;i<=m;i++)
{
c[i]=read();x[i]=read();y[i]=read();
if(c[i]==1){
vis[x[i]][y[i]]++;
d[i]=a[x[i]][y[i]];
a[x[i]][y[i]]=inf;
}
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];
for(int q=m;q>=1;q--)
{
if(c[q]==1)
{
vis[x[q]][y[q]]--;
if(vis[x[q]][y[q]]>0)continue;
a[x[q]][y[q]]=min(a[x[q]][y[q]],d[q]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][x[q]]+a[y[q]][j]+a[x[q]][y[q]]<a[i][j])
{
a[i][j]=a[i][x[q]]+a[y[q]][j]+a[x[q]][y[q]];
}
}
else {
if(a[x[q]][y[q]]>=inf)ans[++tot]=-1;
else ans[++tot]=a[x[q]][y[q]];
}
}
for(int i=tot;i>=1;i--)
{
print(ans[i]);
if(i!=1)printf("\n");
}
return 0;
}
T3老大
100pts
二分答案d
每次以1为根节点向下dfs，从最深的节点不断向上更新，ma和mi数组分别保存当前节点的子树中最长和最短的链的长度，dis数组代表要向当前节点的父节点连接的链的长度。
（三个数组中的负数代表子树中放置了奖杯覆盖到当前节点还可以覆盖的距离）
当ma+mi>0代表子树中的奖杯不能完全覆盖整个子树，那么子树的最长链就要连向父节点，否则子树中的奖杯还可以继续向上覆盖，就将最短链连向父节点（此时最短链一定为负）。
ma=max(dis[y]+1,ma); mi=min(dis[y]+1,mi);
if(ma+mi>0)dis[x]=ma;else dis[x]=mi;
if(dis[x]>=d){sum++;is[x]=-d;}
当需要的奖杯数大于2，这种情况就不合理，不断二分就好了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=200005,inf=0x3f3f3f3f;
int n,x,y,sum=0;
int dis[N],head[N],tot=0;
struct edge{
int ver,to;
}e[N*2];
void add(int x,int y){
e[++tot].ver=y;
e[tot].to=head[x];
head[x]=tot;
}
int read()
{
int sum=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;
}
void print(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10+'0');
}
void dfs(int x,int fa,int d)
{
if(sum>2)return;
int ma=0,mi=inf;
for(int i=head[x];i;i=e[i].to)
{
int y=e[i].ver;
if(y==fa)continue;
dfs(y,x,d);
ma=max(dis[y]+1,ma);
mi=min(dis[y]+1,mi);
}
if(ma+mi>0)dis[x]=ma;
else dis[x]=mi;
if(dis[x]>=d){
sum++;
dis[x]=-d;
}
if(sum>2)return;
}
bool check(int d)
{
sum=0;
dfs(1,0,d);
if(dis[1]>0)sum++;
if(sum>2)return true;
return false;
}
int main(){
// freopen("ob.in","r",stdin);
// freopen("ob.out","w",stdout);
n=read();
for(int i=1;i<n;i++)
{
x=read();y=read();
add(x,y);
add(y,x);
}
int l=0,r=100000,mid;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))l=mid+1;
else r=mid-1;
}
cout<<l;
return 0;
}