　概要

　　　　本次比赛考的不是很好，400分的题只拿了180分。。。（失误失误）

　题目

　　　　T1：数你太美（预期100　　实际60）

　　　　　　　　　题目大意：

　　　　　　　　　　在两个序列中找两个最小的数进行组合，使这个最小整数最小。

　　　　　　　　解析：

　　　　　　　　　　只要根据题目模拟就可以了。。。。。。。

　　　　　　　　　　（玄学60分！！！）

　　　　　　　　code　：

　　　　　　　　　　　　60分代码

 #include<iostream>

 using namespace std;

 int n,m;

 int a[];

 int b[];

 int main()

 {

     cin>>n>>m;

     int minn=2e9,minm=2e9;

     for(int i=;i<=n;i++)

     {

         cin>>a[i];

         if(minn>a[i])

         {

             minn=a[i];

         }

     }

     for(int j=;j<=m;j++)

     {

         cin>>b[j];

         if(minm>b[j])

         {

             minm=b[j];

         }

     }

     if(minn==minm)

     {

         cout<<minn;

         return ;

     }

     else

     {

         cout<<min(minn*+minm,minm*+minn);

     }

     return ;

 }

　　　　　　　　　　　　AC代码

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int n,m;

 int a[],b[];

 int at[],bt[],ct[];

 int t1,t2;

 void cmp(int x,int y)

 {

     if(x<y)

     {

         printf("%d",x);

     }

     else

     {

         printf("%d",y);

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);

         at[a[i]]=;

     }

     for(int i=;i<=m;i++)

     {

         scanf("%d",&b[i]);

         bt[b[i]]=;

     }

     for(int i=;i<;i++)

     {

         ct[i]=at[i]+bt[i];

     }

     sort(a+,a+n+);

     sort(b+,b+m+);

     for(int i=;i<;i++)

     {

         if(ct[i]==)

         {

             printf("%d",i);

             return ;

         }

     }

     t1=a[]*+b[];

     t2=b[]*+a[];

     cmp(t1,t2);

     return ;

 }

　　　　　　　T2：逃亡（预期100　　实际100）

　　　　　　　　　　　题目大意：

　　　　　　　　　　　　　　在（xi，yi）中找到x或y的最短路

　　　　　　　　　　　解析：

　　　　　　　　　　　　　　如题；

　　　　　　　　　　　　　code

 #include<cstdio>

 using namespace std;

 int n,m,k;

 int x,y;

 double sum=;

 int min(int a,int b)

 {

     if(a<b)

     {

         return a;

     }

     else

     {

         return b;

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&k);

     for(int i=;i<=k;i++)

     {

         scanf("%d%d",&x,&y);

         int t1=min(x,n-x);

         int t2=min(y,m-y);

         sum+=min(t1,t2);

     }

     printf("%.3lf",sum);

     return ;

 }

　　　　　　　　　　　　T3：数数字（预期20　　实际20）

　　　　　　　　　　　　　　　　　　　　　　题目大意：

　　　　　　　　　　　　　　　　第i个蒟蒻会告诉你他看到了ai种数字（定义两个数字不同种当且仅当它们的值不同）

　　　　　　　　　　　　　　　　但是由于蒟蒻太弱了，可能会报错数据，NTF需要核实是否有一种情况使所有蒟蒻说的话都正确。

　　　　　　　　　　　　　　　　　　这是个题；

　　　　　　　　　　　　解析：

　　　　　　　　　　　　　　　　令总的卡片种类为 T，对于每一只蒟蒻，若它的卡片数值唯一则他所看到的卡片种类总
　　　　　　　　　　　　　　　　数为Ｔ－１，否则为Ｔ，我们称卡片数值唯一的蒟蒻是孤独的。
　　　　　　　　　　　　　　　　故若 ai 的最大值和最小值的差大于等于 2 则无解
　　　　　　　　　　　　　　　　下面对最大值和最小值的差进行分类讨论：
　　　　　　　　　　　　　　　　　若 max=min，那么此时每只蒟蒻看到的卡片种类都为 T 或者都为 T-1。如果每只蒟蒻看到的
　　　　　　　　　　　　　　　　卡片种类的总数都是 T-1，则每只蒟蒻都是孤独的，此时 T=n。否则每只蒟蒻所看到的卡片
　　　　　　　　　　　　　　　　　　种类的总数都是 T，由于不存在孤独的蒟蒻，所以 T 至多为⌊n/2⌊。
　　　　　　　　　　　　　　　　　　若 max=min+1，此时我们可以统计孤独的蒟蒻的个数 x，类似上面的推论，数值总数至少为
　　　　　　　　　　　　　　　　　　x+1，至多为 x+⌊(n-x)/2⌊。故当 max=min+1 时， x+1≤T≤x+⌊(n-x)/2⌊　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　code

 #include<cstdio>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 int t;

 int n;

 int a[];

 int only;

 int sum;

 //inline int read(){

 //    char ch=getchar();

 //    ll x=0;

 //    ll f=1;

 //    while(ch<'0'||ch>'9'){

 //        if(ch=='-')

 //            f=-1;

 //        ch=getchar();

 //    }

 //    while('0'<=ch&&ch<='9'){

 //        x=x*10+ch-'0';

 //        ch=getchar();

 //    }

 //    return x*f;

 //}

 int main()

 {

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         int maxn=-;

         int minm=2e9;

         only=;

         sum=;

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

             if(maxn<a[i])

                 maxn=a[i];

             if(minm>a[i])

                 minm=a[i];

         }

         for(int i=;i<=n;i++)

             if(a[i]==minm) only++;

         if(maxn-minm>=)

         {

             printf("no\n");

             continue;

         }

         if(minm==maxn)

         {

             if(maxn<=n/||maxn+==n)

             {

                 printf("yes\n");

                 continue;

             }

             printf("no\n");

             continue;

         }

         if(maxn==minm+)

         {

             if(only+<=maxn&&maxn<=(n-only)/+only)

             {

                 printf("yes\n");

             }

             else

             {

                 printf("no\n");

             }

         }

     }

     return ;

 }

　　　　　　　　T4：tower（期望得分0　　实际得分0）；

　　　　　　　　　　　　　　　　题目大意：

欲穷千里目，更上一层楼。

阿克先生喜欢旅游。某一天，他来到魔法森林旅游。

经过观察，他发现魔法森林一共有n个城市，每个城市有一座高高的魔法塔，第i个城市的魔法塔的高度为hi。这些城市一共由n-1条道路连接，任意两座城市互相可达。

阿克先生想要站在某一座塔上观察尽可能多城市的风景。不幸的是，阿克先生没有透视眼，较高的塔将会遮蔽较低的塔。同时，魔法森林其他地方也被茂林覆盖，他的视线无法穿过茂林（但因为是魔法塔，塔上储存了镜面魔法，可以使阿克先生的视线在城市水平任意角度转弯）。

所以，他只能沿着n-1条道路观察其他的点。

但是，魔法森林的道路蜿蜒曲折，他观看的城市到他所在的点的路径要么互相包含要么两两不交。且从他所在的点开始，到任意它观察的城市，所成的高度序列单调不增。

阿克先生想要知道他最多能观察到多少个城市（包括自身），他快速地秒了这道题，但他懒得写代码了，所以请你帮他算一算。

　　　　　　　　　　　　　　　　　　　　解析：

　　　　30%
　　　　枚举阿克先生在哪个点，然后 dfs，时间复杂度 O(n^2)。
　　　　20%链
　　　　从左往右扫一遍，从右往左扫一遍，计算出每个点向左、向右最长不上升的长度，然后加在
　　　　一起取 max 就是答案了。时间复杂度 O(n)。
　　　　20%h 互不相同
　　　　观察到若 u 能够观察 v，则 v 一定不能观察 u，所以按高度从小到大排序，依次加入，维护
　　　　每个点所能伸出的最长链即可；或者可以直接记忆化搜索。时间复杂度 O(n log n)或 O(n)。
　　　　100%
　　　　先固定一个点为根，可以发现，答案的贡献被分为两类：子树内和子树外， dfs 一次，计算
　　　　出每个点在它子树内能延伸出的最长路径和次长路径，再计算每个点以他为所在节点在子树
　　　　内最多覆盖多少个点，重新 dfs 一次，同时记录它往他父亲延伸最多能延伸多长，每次向下
　　　　走一格，要么是原路径+1，要么是它兄弟的一个路径，取 max，如果父亲>儿子，则伸向父
　　　　亲的长度清零，每个节点的答案就是它子树内的答案+伸向他父亲的最长路径。时间复杂度
　　　　O(n)

　　　　　　code

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 using namespace std;

 int tot=;

 int h[];

 int s[];

 int f[],f1[];

 int a[];

 int ans=;

 struct edge {

     int to,next;

 } e[];

 void add(int x,int y) {

     e[++tot].to=y;

     e[tot].next=h[x];

     h[x]=tot;

 }

 void dfs1(int u,int fa) {

     s[u]=,f[u]=;

     for(int i=h[u]; i!=; i=e[i].next) {

         int v=e[i].to;

         if (v==fa) continue;

         dfs1(v,u);

         if (a[u]>=a[v]) {

             if (f[u]<f[v]+) {

                 f1[u]=f[u];

                 f[u]=f[v]+;

             } else f1[u]=max(f1[u],f[v]+);

             s[u]+=f[v];

         }

     }

 }

 void dfs2(int u,int fa,int up) {

     ans=max(ans,up+s[u]);

     for (int i=h[u]; i!=; i=e[i].next) {

         int v=e[i].to;

         if (v==fa) continue;

         if (a[v]<a[u])

             dfs2(v,u,);

         else {

             if(f[v]+==f[u])

                 dfs2(v,u,max(up+,f1[u]));

             else

                 dfs2(v,u,max(up+,f[u]));

         }

     }

 }

 int main() {

     int n;

     tot=,ans=;

     scanf("%d",&n);

     for (int i=; i<=n; i++)

         scanf("%d",&a[i]);

     for (int i=; i<n; i++) {

         int q,p;

         scanf("%d%d",&q,&p);

         add(q,p),add(p,q);

     }

     dfs1(,);

     dfs2(,,);

     printf("%d\n",ans);

 }

　　　　　　最后附上oj链接：www.gdfzoj.com

巴特西

GALAXY OJ NOIP2019联合测试1-总结

概要

题目

T1：数你太美（预期100　　实际60）

题目大意：

解析：

code　：

T2：逃亡（预期100　　实际100）

题目大意：

解析：

code

T3：数数字（预期20　　实际20）

题目大意：

解析：

code

T4：tower（期望得分0　　实际得分0）；

题目大意：

解析：

code

最新文章

热门文章

巴特西

GALAXY OJ NOIP2019联合测试1-总结

概要

题目

T1：数你太美（预期100 实际60）

题目大意：

解析：

code ：

T2：逃亡（预期100 实际100）

题目大意：

解析：

code

T3：数数字（预期20 实际20）

题目大意：

解析：

code

T4：tower（期望得分0 实际得分0）；

题目大意：

解析：

code

最新文章

热门文章

　概要

　题目

　　　　T1：数你太美（预期100　　实际60）

　　　　　　　　　题目大意：

　　　　　　　　解析：

　　　　　　　　code　：

　　　　　　　T2：逃亡（预期100　　实际100）

　　　　　　　　　　　题目大意：

　　　　　　　　　　　解析：

　　　　　　　　　　　　　code

　　　　　　　　　　　　T3：数数字（预期20　　实际20）

　　　　　　　　　　　　　　　　　　　　　　题目大意：

　　　　　　　　　　　　解析：

　　　　　　　　　　　　　　　　code

　　　　　　　　T4：tower（期望得分0　　实际得分0）；

　　　　　　　　　　　　　　　　题目大意：

　　　　　　　　　　　　　　　　　　　　解析：

　　　　　　code