Codeforces Round #303 (Div. 2)

题目出乎意外的比较简单:

D：贪心，只要我们sort();然后从小到大枚举，能得到的拿到，不能的忽视。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<string.h>
 5 #include<string>
 6 #include<iostream>
 7 #include<vector>
 8 #include<map>
 9 #include<vector>
10 
11 #define N 123456
12 #define inf 0x3f3f3f
13 using namespace std;
14 typedef long long ll;
15 
16 int a[N],b[N];
17 int main()
18 {
19   int n;
20   cin>>n;
21   for (int i=1;i<=n;i++) cin>>a[i];
22   sort(a+1,a+n+1);
23 
24   int  ans=0;
25   ll tmp=0;
26   for (int i=1;i<=n;i++)
27   {
28       if (a[i]>=tmp)
29       {
30       ans++;
31       tmp+=a[i];
32       }
33   }
34   cout<<ans<<endl;
35   return 0;
36 }

View Code

C：dp：

dp[i][0]：第i颗树向左边倒最大的数目。

dp[i][1]: 第i颗树不倒，产生的最大数目。

dp[i][2]: 第i棵树倒右边，产生的最大数目。

//第i颗树倒左边

    if (a[i-1]+b[i]<a[i])          dp[i][0]=max(dp[i][0],dp[i-1][0]+1);
    if (a[i-1]+b[i]<a[i])          dp[i][0]=max(dp[i][0],dp[i-1][1]+1);
    if (a[i-1]+b[i-1]<a[i]-b[i])   dp[i][0]=max(dp[i][0],dp[i-1][2]+1);

  //第i颗树中立
    dp[i][1]=max(dp[i-1][0],dp[i-1][1]);
    if (a[i-1]+b[i-1]<a[i])        dp[i][1]=max(dp[i][1],dp[i-1][2]);
 //第i颗树倒右边
    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+1;
    if (a[i-1]+b[i-1]<a[i])          dp[i][2]=dp[i-1][2]+1;

完整代码：

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string.h>
#include<string>
#include<iostream>
#include<vector>
#include<map>
#include<vector>

#define N 123456
#define inf 0x3f3f3f
using namespace std;
typedef long long ll;

int a[N],b[N];

int dp[N][3];

int main()
{
  int n;
  cin>>n;
  for (int i=1;i<=n;i++) cin>>a[i]>>b[i];
  dp[1][0]=1;
  dp[1][1]=0;
  dp[1][2]=1;

  int ans=0;

  for (int i=2;i<=n;i++)
  {
    if (a[i-1]+b[i]<a[i])          dp[i][0]=max(dp[i][0],dp[i-1][0]+1);
    if (a[i-1]+b[i]<a[i])          dp[i][0]=max(dp[i][0],dp[i-1][1]+1);
    if (a[i-1]+b[i-1]<a[i]-b[i])   dp[i][0]=max(dp[i][0],dp[i-1][2]+1);

    dp[i][1]=max(dp[i-1][0],dp[i-1][1]);
    if (a[i-1]+b[i-1]<a[i])        dp[i][1]=max(dp[i][1],dp[i-1][2]);

    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+1;
    if (a[i-1]+b[i-1]<a[i])          dp[i][2]=dp[i-1][2]+1;
  }
  ans=max(dp[n][0],max(dp[n][1],dp[n][2]));
  cout<<ans<<endl;
  
E：
   做法：先求u到每个点的最短。假如dis[v] ->  u 到v 的最短路。
   然后对于每个点v,如果前一个点mp[u][v]的路径，满足最短路，并且加入当前是v连图中边权值最小，则贪心加入。{证明大概是：反正加入u->v 这条边权 不会影响最短路，
   并且不会影后面的更新。
所以可以贪心处理：

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cmath>
  4 #include<string.h>
  5 #include<string>
  6 #include<iostream>
  7 #include<vector>
  8 #include<map>
  9 #include<vector>
 10 #include<queue>
 11 
 12 #define N 323456
 13 #define inf 323456789123450ll
 14 
 15 using namespace std;
 16 typedef long long ll;
 17 struct edge
 18 {
 19     int v,next,id,c;
 20 }e[N<<2];
 21 int head[N];
 22 int n,m;
 23 int tot;
 24 ll cost[N];
 25 
 26 
 27 void add(int u,int v,int c,int id)
 28 {
 29     e[tot].v=v;
 30     e[tot].c=c;
 31     e[tot].id=id;
 32     e[tot].next=head[u];
 33 
 34     head[u]=tot++;
 35     e[tot].v=u;
 36     e[tot].c=c;
 37     e[tot].id=id;
 38     e[tot].next=head[v];
 39     head[v]=tot++;
 40 }
 41 
 42 ll dis[N];
 43 int b[N];
 44 
 45 void spfa(int s)
 46 {
 47     queue<int>q;
 48     q.push(s);
 49     for (int i=1;i<=n;i++) dis[i]=inf;
 50     dis[s]=0;
 51 
 52     while (!q.empty())
 53     {
 54         int u=q.front();
 55         q.pop();
 56         b[u]=0;
 57         for (int i=head[u];i!=-1;i=e[i].next)
 58         {
 59             int v=e[i].v;
 60             if (dis[v]>dis[u]+e[i].c)
 61             {
 62                 dis[v]=dis[u]+e[i].c;
 63                 if (!b[v])
 64                 {
 65                     b[v]=1;
 66                     q.push(v);
 67                 }
 68             }
 69         }
 70     }
 71 }
 72 
 73 int aa[N];
 74 
 75 void bfs(int s)
 76 {
 77   queue<int>q;
 78   q.push(s);
 79   for (int i=1;i<=n;i++) cost[i]=inf;
 80   aa[s]=0;
 81   while (!q.empty())
 82   {
 83     int u=q.front();
 84         q.pop();
 85         for (int i=head[u];i!=-1;i=e[i].next)
 86         {
 87           int v=e[i].v;
 88           if (dis[v]==dis[u]+e[i].c)
 89           {
 90            if (cost[v]>e[i].c) {
 91                   cost[v]=e[i].c;
 92                   aa[v]=e[i].id;
 93                   q.push(v);
 94             }
 95           }
 96         }
 97    }
 98 }
 99 
100 void debug()
101 {
102     for (int i=1;i<=n;i++) cout<<dis[i]<<" ";
103 }
104 
105 int main()
106 {
107 
108     cin>>n>>m;
109     memset(head,-1,sizeof(head));
110     for (int i=1;i<=m;i++)
111     {
112         int x,y,z;
113         scanf("%d%d%d",&x,&y,&z);
114         add(x,y,z,i);
115         add(y,x,z,i);
116     }
117     int s;
118     scanf("%d",&s);
119     spfa(s);
120     bfs(s);
121 
122     ll ans=0;
123     for (int i=1;i<=n;i++)
124     if (i!=s)
125     ans+=cost[i];
126 
127     sort(aa+1,aa+n+1);
128     cout<<ans<<endl;
129     for (int i=2;i<=n;i++) cout<<aa[i]<<" ";
130     return 0;
131 }

View Code



我的做法：是先SPFA最短路，然后BFS找路径。