2019.11月4日模拟赛（早）

2019.11月5日模拟赛（早）

题目名称	妹子	老大	相交
可执行文件名	girls	ob	inter
输入文件名	girls.in	ob.in	inter.in
输出文件名	girls.out	ob.out	inter.out
每个测试点时限	1 秒	1 秒	1 秒
内存限制	512MB	512MB	512M
测试点数目	10	10	10
每个测试点分值	10	10	10
是否有部分分	否	否	否
题目类型	传统型	传统型	传统型

提交源程序须加后缀

girls.c	ob.c	inter.c
girls.cpp	ob.cpp	inter.cpp

注意事项
文件名（程序名和输入输出文件名）必须使用英文小写。
C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返
回值必须是 0。
注意：最终测试时，所有编译命令均不打开任何优化开关。

1. 妹子

1 问题描述
万人迷皮皮轩收到了很多妹子的礼物，由于皮皮轩觉得每个妹子都不错，所以将她们礼物
的包装盒都好好保存，但长此以往皮皮轩的房间里都堆不下了，所以只能考虑将一些包装盒
放
进其他包装盒里节省空间。
方便起见，我们不考虑包装盒的高度和厚度，只考虑包装盒的长宽。
一句话题意：给出两个矩形，问是否可以将一个矩形放在另一个矩形的内部（含边界），多
测。
2 输入格式
输入文件名为 girls.in。
第一行，一个整数 n，表示数据组数。
对于下面的每一组数据：
第一行，四个整数 a 1 ， b 1 ， a 2 ， b 2 表示两个盒子的长宽。
3 输出格式
输出文件名为 girls.out。
n 行， 每行一个’’ Y es ‘’或’’ No ‘’ （不含引号）， 分别表示其中一个盒子可以放到另一个盒子
中或两个盒子都不能放到另一个盒子中。
4 样例
见下发/girls/girls.in(out)。
5 数据规模与约定
对于 100% 的数据， n ≤ 10， a 1 ,b 1 ,a 2 ,b 2 ≤ 1000

初看此题还以为是一道刚学c++一两天的for循环比较，心想老板不会是放错题了吧。后来在老板提示A题可以用系统自带三角函数后才猛然发觉原来矩形还可以旋转。。。。。。

ps;系统自带三角函数要*pi/180哦

//
#include<stdio.h>
#include<bits/stdc++.h>
#define pi 3.14
using namespace std;
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd()
{
    char ch=nc();
    int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
int n,a1,b1,a2,b2;

int main()
{
//    freopen("girls.in","r",stdin);
    //  freopen("girls.out","w",stdout);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        bool Mark=0;
        cin>>a1>>b1>>a2>>b2;
        /*    if((a1*a1>=(a2*a2+b2*b2))||(b1*b1>=(a2*a2+b2*b2))||(a2*a2>=(a1*a1+b1*b1))||(b2*b2>=(a1*a1+b1*b1)))
            {
                cout<<"No"<<endl;
                continue;
            }*/
        if(a1>b1)swap(a1,b1);
        if(a2>b2)swap(a2,b2);
        if(a1>a2)
        {
            swap(a1,a2),swap(b1,b2);
        }
        if(b1<=b2)
        {
            printf("Yes
");
            continue;
        }
        for(double du=0; du<=90.0; du+=(double)0.01)
            if((b1*sin(du*pi/180)+a1*cos(du*pi/180)<=a2)&&(a1*sin(du*pi/180)+b1*cos(du*pi/180)<=b2))
            {
                cout<<"Yes"<<endl;
                Mark=1;
                break;
            }
        if(!Mark)cout<<"No"<<endl;
    }
}

 

2. 老大

1 问题描述
因为 OB 今年拿下 4 块金牌，学校赞助扩建劳模办公室为劳模办公室群，为了体现 OI 的
特色， 办公室群被设计成了树形（n 个点 n - 1 条边的无向连通图）， 由于新建的办公室太
大
以至于要将奖杯要分放在两个不同的地方以便同学们丢硬币进去开光， OB 想请你帮帮他看
看
奖杯放在哪两个办公室使得在任意一个在劳模办公室做题的小朋友能最快地找到奖杯来开
光。
一句话题意：给出一个 n 个点的树，在两个合适且不同的点放上奖杯，使得每个点到最近
的奖杯距离最大值最小。
2 输入格式
输入文件名为 ob.in。
第一行，一个整数 n。
接下来的 n - 1 行， 每行两个数 x y。
3 输出格式
输出文件名为 ob.out。
三个数，分别表示最小的最大距离，两个奖杯的位置。
4 样例
见下发/ob/ob.in(out)。
5 数据规模与约定
对于前 60% 的数据， n ≤ 100。
对于前 80% 的数据， n ≤ 2000。
对于 80% 的数据，保证树的形态随机。
对于 100% 的数据，保证 3 ≤ n ≤ 200000。

可以发现这道题就是P3523 [POI2011]DYN-Dynamite的弱化版（黄神还是强啊，阅题无数！！）

P3523 [POI2011]DYN-Dynamite

3. 相交

 

题目描述
一棵大树下有 n 个巢穴，由 n-1 条双向道路连接，任意两个城市均可互相到达。
大树附近有两群蚂蚁，每天早上，第一群蚂蚁会派一只蚂蚁到这棵树下，并在第 a 个巢穴
到 第
b 个巢穴间的最短路径上的每个巢穴留下气味。每天傍晚，第二群蚂蚁会派一只蚂蚁到
这
棵树下，并侦查第 c 个巢穴到第 d 个巢穴间的最短路径上是否有蚂蚁留下的气味。
每天蚂蚁留下的气味会在当天深夜消失。
输入
第一行一个正整数 n，含义如题所示。
接下来 n-1 行，每行两个正整数 u,v，表示第 u 个巢穴和第 v 个巢穴间有一条双向道路。
接下来一行一个正整数 q，表示天数。
接下来 q 行，每行四个正整数 a,b,c,d，含义如题所示。
输出
q 行，每行一个字符串。
若第二群派出的蚂蚁侦查到蚂蚁留下的气味，则输出” YES” ,否则输出” NO”
样例输入
样例输入 1
8
1 2
1 3
2 4
2 5
5 6
5 7
3 8
4
2 5 4 3
5 3 8 8
5 4 6 7
4 8 6 7
样例输入 2
15
2 1
3 1
4 2
5 3
6 2
7 2
8 5
9 3
10 6
11 5
12 7
13 11
14 1
15 1
5
1 2 3 4
4 7 1 9
2 3 7 9
2 6 7 8
2 1 6 8
样例输出
样例输出 1
YES
NO
YES
NO
样例输出 2
YES
NO
YES
YES
YES
数据规模
对于 30%的数据 1<=n,q<=3000
对于另外 20%的数据 第 i 条边连接第 i 个巢穴和第 i+个巢穴
对于 100%的数据 1<=n,q<=10000

 

这是 一道比B题水的题（震惊！！！！）

两两LCA就可以过

当然，你要是想树剖做也不拦你

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int To;
    int Next;
} edge[300000];
int head[100005],num;
inline void add(int x,int y)
{
    edge[++num].To=y;
    edge[num].Next=head[x];
    head[x]=num;
}
int dep[100005],fa[100005][17];
int n;
inline void dfs(int u,int Fa)
{
    dep[u]=dep[Fa]+1;
    int k=ceil(log2(dep[u]));
    fa[u][0]=Fa;
    for(int i=1;i<=k;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u]; i; i=edge[i].Next)
    {
        int v=edge[i].To;
        if(v!=Fa)
        {
            dfs(v,u);
        }
    }
}
inline int lca(int x,int y)
{
    int s=ceil(log2(n));
    if(dep[x]<dep[y])swap(x,y);
    int k=dep[x]-dep[y];
    for(int i=0;i<=s;i++)
    {
        if(k&(1<<i))x=fa[x][i];
    }
    if(x==y)return x;
    s=ceil(log2(dep[x]));
    for(int i=s; i>=0; i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}

bool pan(int u,int v,int w)
{
    return (lca(u,w)==w)&&(dep[w]>=dep[v]);
}
inline bool chake(int a,int b,int c,int d)
{
    int l1=lca(a,b),l2=lca(c,d);
//    cout<<"l1__"<<l1<<endl;
//    cout<<"l2__"<<l2<<endl;
    return ((pan(a,l1,l2))||(pan(b,l1,l2))||(pan(c,l2,l1))||pan(d,l2,l1));
}

int q;
int main()
{
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin>>n;
    int a,b,c,d;
    for(int i=1; i<n; i++)
    {
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>a>>b>>c>>d;
        if(chake(a,b,c,d))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}