《凉宫春日的忧郁》专场

T1

考试的时候连题面都没看懂，都没往图论这方面想，更别提最小生成树。

正解：

最小生成树prim，好像是什么欧几里得生成树，寒假时候的东西了，我直接找的blog看，没看见这么玩意，果然还是太菜了

平面欧几里得最小生成树（EMST）来自wiki百科

直接prim，套板子就好，把上下边界压成一个点，注意，在prim过程中，第一个for循环找出的点如果为压缩后的上边界，此时直接break就好，

prim跟点有关，kruskal跟边有关，此图为完全图，边数达到了 \(n^{2}\)，显然用prim更优，用kruskal也可，就是慢很多。

Code 
#include<cmath>

#include<cstdio>

#include<iostream>

#define MAX 6010

#define INF 114514810

#define re register

namespace OMA

{

   int n,m,k;

   bool vis[MAX];

   double ans,dis[MAX];

   double x[MAX],y[MAX];

   inline double Dis(int i,int j)

   { return (i>k||j>k||!i||!j)?sqrt((y[i]-y[j])*(y[i]-y[j])):sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); }

   inline void prim()

   {

     for(re int i=0; i<=k+1; i++)

     { dis[i] = INF; }

     dis[0] = 0;

     for(re int i=0; i<=k+1; i++)

     {

       int tmp = 0,top = INF;

       for(re int j=0; j<=k+1; j++)

       {

         if(!vis[j]&&dis[j]<top)

         { tmp = j,top = dis[j]; }

       }

       if(tmp==k+1)

       { break ; }

       vis[tmp] = true;

       ans = std::max(ans,dis[tmp]);

       for(re int j=0; j<=k+1; j++)

       { dis[j] = std::min(dis[j],Dis(j,tmp)); }

     }

   }

   signed main()

   {

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

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

     { scanf("%lf%lf",&x[i],&y[i]); }

     y[k+1] = m,prim();

     printf("%0.9lf\n",ans/2);

     return 0;

   }

}

signed main()

{ return OMA::main(); }

T2

不会dp，所以考试的时候，写的贪心，又写假贪心，改后的贪心没交上，假的骗了10pts，不要脸的说一下假贪心

将左边的点跟右边连起来的点用结构体存起来，按差值排一下序，差值越大，则交线越多，然后就从1开始暴搜，再多开一个二维数组 \(line_{i,j}\)，表示此时是以i这条线开始删的，第j条线被删掉了，暴搜下一条线时，转移一下状态，转移答案时，判断是否全删完了，再转移。复杂度，应该是\(O(n^{3})\)

贪心 
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAX 10010

#define re register

namespace OMA

{

   int n,ans=0x3f3f3f3f;

   int c[MAX];

   inline int abs(int a)

   { return a>=0?a:-a; }

   struct node

   {

     int l,r,c;

     friend inline bool operator <(const node &a,const node &b)

     { return abs(a.l-a.r)>abs(b.l-b.r); }

   }p[MAX];

   int lr[MAX],rl[MAX];

   bool line[MAX][MAX];

   inline int read()

   {

     int s=0,w=1; char ch=getchar();

     while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }

     while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }

     return s*w;

   }

   inline int min(int a,int b)

   { return a<b?a:b; }

   inline void dfs(int i,int res,int cast)

   {

     line[i][p[i].r] = true;

     res -= abs(p[i].r-p[i].l)+1;

     cast += p[i].c;

     if(p[i].l>p[i].r)

     {

       for(re int j=p[i].r; j<=n; j++)

       { line[i][j] = true; }

     }

     else

     {

       for(re int j=1; j<=p[i].r; j++)

       { line[i][j] = true; }

     }

     bool flag = true;

     for(re int j=1; j<=n; j++)

     {

       if(!line[i][j])

       { flag =  false; }

     }

     if(flag&&res<=0)

     { ans = min(ans,cast); return ; }

     for(re int j=1; j<=n; j++)

     {

       if(!line[i][p[j].r])

       {

         for(re int k=1; k<=n; k++)

         { line[j][k] = line[i][k]; }

         dfs(j,res,cast);

       }

     }

   }

   inline void clear()

   { memset(line,0,sizeof(line)); }

   signed main()

   {

     n = read();

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

     { p[i] = (node){i,read()}; }

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

     { p[i].c = read(); }

     std::sort(p+1,p+1+n);

     for(re int i=1; i<=n/2; i++)

     { dfs(i,n,0),clear(); }

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

     return 0;

   }

}

signed main()

{ return OMA::main(); }

正解线段树维护上升序列，咕了。

T3

暴力跳爹50pts。

50pts 
#include<cstdio>

#define MAX 500010

#define re register

namespace OMA

{

   int n;

   struct Graph

   {

     int next;

     int to;

   }edge[MAX<<1];

   int dep[MAX];

   int cnt=1,head[MAX];

   int fa[MAX],bin[MAX];

   double ans[MAX];

   int c[MAX],dis[MAX];

   inline int read()

   {

     int s=0,w=1; char ch=getchar();

     while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }

     while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }

     return s*w;

   }

   inline void add(int u,int v)

   {

     edge[++cnt].next = head[u];

     edge[cnt].to = v;

     head[u] = cnt;

   }

   inline double min(double a,double b)

   { return a<b?a:b; }

   inline void dfs(int u,int fat)

   {

     fa[u] = fat;

     int tmp = fa[u];

     while(tmp)

     {

       ans[u] = min(ans[u],1.0*(c[tmp]-c[u])/(1.0*(dis[u]+dis[tmp]-2*dis[tmp])));

       tmp = fa[tmp];

     }

     for(re int i=head[u]; i; i=edge[i].next)

     {

       int v = edge[i].to;

       if(v!=fat)

       {

         dis[v] = dis[u]+1;

         dfs(v,u);

       }

     }

   }

   signed main()

   {

     n = read();

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

     { bin[i] = bin[i>>1]+1; }

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

     { c[i] = read(); }

     for(re int v=2; v<=n; v++)

     {

       ans[v] = 0x3f3f3f3f;

       int u = read();

       add(u,v),add(v,u);

     }

     dfs(1,0);

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

     { printf("%0.10lf\n",ans[i]); }

     return 0;

   }

}

signed main()

{ return OMA::main(); }

/*

正解：

我们先将原式子转换一下

\[\frac{c_{anc}-c_{u}}{dis(u,v)}=\frac{c_{anc}-c_{u}}{dep_{u}-dep_{anc}}=-\frac{c_{u}-c_{anc}}{dep_{u}-dep_{anc}}
\]

然后以c为y轴，dep为x轴，建立坐标系，发现这个式子其实就是在求斜率，那么考虑维护凸包，且只用维护下凸包，上凸包对答案造不成贡献。

暴力弹栈的话，会t成80pts精心构造的数据，所以考虑倍增弹栈

或者说这叫可持久化栈

看了一个早上几何里的凸包

Code 
#include<cstdio>

#define MAX 500010

#define re register

namespace OMA

{

   int n;

   struct Graph

   {

     int next;

     int to;

   }edge[MAX<<1];

   int cnt=1,head[MAX];

   double ans[MAX];

   int c[MAX],dep[MAX];

   int fa[MAX][30],bin[MAX];

   inline int read()

   {

     int s=0,w=1; char ch=getchar();

     while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }

     while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }

     return s*w;

   }

   inline void add(int u,int v)

   {

     edge[++cnt].next = head[u];

     edge[cnt].to = v;

     head[u] = cnt;

   }

   inline double work(int u,int v)

   { return 1.0*(c[u]-c[v])/(1.0*(dep[v]-dep[u])); }

   inline void dfs(int u,int fat)

   {

     int anc = fat;

     dep[u] = dep[fat]+1;

     for(re int i=bin[dep[u]]; ~i; i--)

     {

       if(fa[anc][i]<=1)

       { continue ; }

       if(work(fa[fa[anc][i]][0],u)<=work(fa[anc][i],u))

       { anc = fa[anc][i]; }

     }

     if(anc>1&&work(fa[anc][0],u)<=work(anc,u))

     { anc = fa[anc][0]; }

     fa[u][0] = anc;

     for(re int i=1; i<=bin[dep[u]]; i++)

     { fa[u][i] = fa[fa[u][i-1]][i-1]; }

     for(re int i=head[u]; i; i=edge[i].next)

     {

       int v = edge[i].to;

       if(v!=fat)

       { dfs(v,u); }

     }

   }

   signed main()

   {

     n = read();

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

     { c[i] = read(); }

     for(re int v=2; v<=n; v++)

     {

       bin[v] = bin[v>>1]+1;

       int u = read();

       add(u,v),add(v,u);

     }

     dfs(1,0);

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

     { printf("%0.10lf\n",work(fa[i][0],i)); }

     return 0;

   }

}

signed main()

{ return OMA::main(); }

最新文章

  1. SQL Server 统计信息更新时采样百分比对数据预估准确性的影响
  2. 虚幻引擎4笔记20160821 - 使用GPU粒子做雪花旋转镜头雪花忽有忽无的问题
  3. faker image
  4. 20145211 《Java程序设计》课程总结——桃花流水窅然去
  5. 161028、Nginx负载均衡实现tomcat集群方案简要小结
  6. json 序列化的两种方式
  7. Arduino Nano + WIZ550io = 简易上网
  8. python之字符串
  9. ios移动端原生滚动条滚动不灵敏问题
  10. 学大伟业 国庆Day2
  11. EF|CodeFirst数据并发管理
  12. 《修炼之道:.NET开发要点精讲》读书笔记（二）
  13. Forth 采用CODE定义新词
  14. VS未能正确加载包
  15. Centos/Linux下调整分区大小（以home和根分区为例）
  16. 20145326 《Java程序设计》第4周学习总结
  17. PHP 利用文件锁处理高并发
  18. return 与 exit() 的区别
  19. A simple greedy problem（hdu 4976）
  20. mooc_java 集合框架下

热门文章

  1. 单片机与PLC的区别？
  2. 将gitlab内置node_exporter提供外部prometheus使用
  3. Codeforces Round #139 (Div. 2) 题解
  4. MySQL数据库性能优化该如何入手
  5. python 得到变量名的结果为名的变量的值locals()
  6. mysql 修改my.ini
  7. 手把手教你在Modelarts平台上进行视频推理
  8. 备战- Java虚拟机
  9. facade层,service 层,domain层，dao 层设计
  10. MYSQL一个设备上的主从复制实现-windows