CodeforcesRound#270DCBA

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

谈论最激烈的莫过于D题了！

看过的两种做法不得不ORZ,特别第二种，简直神一样！！！！！

1th:构造最小生成树。

我们提取所有的边出来按边排序，因为每次我们知道边的权值>0，

之后每次把边加入集合中，不断构造，类似 kruskal算法，构造出边后

再对每个点进行整张图的DFS求距离

复杂度O(N^2lgN)：对所有边排序的复杂度。

  1 #include<bits/stdc++.h>
  2 
  3 #define N 2222
  4 using namespace std;
  5 typedef long long ll;
  6 #define inf 0x3f3f3f
  7 int n;
  8 int f[N],vis[N];
  9 int a[N][N];
 10 
 11 struct node
 12 {
 13     int u,v,w;
 14     node(int uu,int vv,int ww):u(uu),v(vv),w(ww){}
 15 };
 16 
 17 vector<pair<int,int> > G[N];
 18 vector<node> edge;
 19 
 20 int find(int x)
 21 {if (f[x]!=x) return f[x]=find(f[x]);}
 22 
 23 int cmp(node a,node b){return a.w<b.w;}
 24 
 25 ll dis[N];
 26 void dfs(int x)
 27 {
 28    vis[x]=1;
 29  //  cout<<dis[x]<<" ";
 30    for (int i=0;i<G[x].size();i++)
 31    {
 32        int v=G[x][i].first;
 33        int w=G[x][i].second;
 34        if (vis[v]) continue;
 35        dis[v]=dis[x]+w;
 36        dfs(v);
 37    }
 38 }
 39 
 40 int solve()
 41 {
 42     for (int i=1;i<n;i++)
 43     for (int j=i+1;j<=n;j++)
 44          edge.push_back(node(i,j,a[i][j]));
 45 
 46     for (int i=1;i<=n;i++) f[i]=i;
 47 
 48     sort(edge.begin(),edge.end(),cmp);
 49     int t=edge.size();
 50     for (int i=0;i<t;i++)
 51     {
 52         int x=edge[i].u;
 53         int y=edge[i].v;
 54         int tx=find(x);
 55         int ty=find(y);
 56         if (tx!=ty)
 57         {
 58             f[tx]=ty;
 59             G[x].push_back(make_pair(y,edge[i].w));
 60             G[y].push_back(make_pair(x,edge[i].w));
 61         }
 62     }
 63 
 64 
 65     for (int i=1;i<=n;i++)
 66     {
 67         memset(vis,0,sizeof(vis));
 68         memset(dis,0,sizeof(dis));
 69         dfs(i);
 70 
 71         for (int j=1;j<=n;j++)
 72         if (dis[j]!=a[i][j])
 73         {
 74             return 0;
 75         }
 76     }
 77     return 1;
 78 }
 79 
 80 int main()
 81 {
 82 
 83    scanf("%d",&n);
 84     for (int i=1;i<=n;i++)
 85     for (int j=1;j<=n;j++)
 86       scanf("%d",&a[i][j]);
 87 
 88     for (int i=1;i<=n;i++)
 89     for (int j=1;j<=n;j++)
 90     {
 91        if (a[i][j]!=a[j][i]||i==j&&a[i][j]!=0)
 92        {
 93            puts("NO");
 94            return 0;
 95        }
 96        if (i!=j&&a[i][j]==0)
 97            {
 98             puts("NO");
 99            return 0;
100            }
101     }
102 
103  if (solve())  puts("YES");
104  else  puts("NO");
105  return 0;
106 }

代码可能更好说明思路，关键一点是：我们每次把最短的边加入集合。我们确定这是一颗最小生成树！所以加边次序是和MST是一样的。

第二种做法不得不佩服！1

这个特种点很难在比赛中发现啊

关键点：我们知道一个点到其他所有点都有一条最小距离的边--假设A到其他点最小距离的点是B，A-B一定是直接连接的。假设距离是X。

然后假设一个点C，C到B点要么比C到A点近X，要么C到A点远X。具体可以画图。

通过这个方法可以判断数据是否合法！

代码超级短

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 #define N 2222
 5 
 6 
 7 int a[N][N];
 8 int n;
 9 int main()
10 {
11     scanf("%d",&n);
12     for (int i=1;i<=n;i++)
13     for (int j=1;j<=n;j++)
14     scanf("%d",&a[i][j]);
15     
16     //预处理判断
17     int flag=0;
18     for (int i=1;i<=n;i++)
19     for (int j=1;j<=n;j++)
20     {
21        if (i!=j&&a[i][j]==0) flag=1;
22        if (i==j&&a[i][j]!=0)   flag=1;
23        if (i!=j&&a[i][j]!=a[j][i]) flag=1;
24        }
25        
26        if (flag)
27        {
28            puts("NO");
29            return 0;
30         }
31 
32     for (int i=1;i<=n;i++)
33     {
34         int inf= 1900000000;//初始的值要比较大些
35         int pos=-1;
36         for (int j=1;j<=n;j++){
37         if (i==j) continue;
38         if (a[i][j]<inf)
39         {
40             inf =a[i][j];
41             pos=j;
42             }
43         }
44         for (int j=1;j<=n;j++)
45         {
46             if (i==j||j==pos) continue;
47             if (abs(a[i][j]-a[pos][j])!=inf)
48             {
49                 puts("NO");
50                 return 0;
51             }
52         }
53     }
54 
55    puts("YES");
56    return 0;
57 }

后面的基本是水体了：
C：贪心：
从第一的判断每次找合理值，矛盾就错误！
B:
我是用贪心的做法！
想想我们最后电梯还是要回到第一层！对吧！
也要走到最高层，当前有人想去的最高层！
那么我们每次把前K高层的先送上去！就能满足答案最小！

 1 #define N 111111
 2 using namespace std;
 3 
 4 
 5 int a[2222];
 6 int cmp(int x,int y)
 7 {
 8     return x>y;
 9 }
10 int main()
11 {
12     int n,k;
13     cin>>n>>k;
14     
15     for (int i=1;i<=n;i++) cin>>a[i];
16     sort(a+1,a+n+1,cmp);
17     int ans=0;
18     for (int i=1;i<=n;i+=k)
19         ans+=(a[i]-1)*2;
20 
21     cout<<ans<<endl;
22     return 0;