奇迹之流WonderfloW

Nothing Replaces Hard Work!

ZOJ1245 && ZOJ1298 && ZOJ1301

| Comments

这三题都比较简单,就放在一起了。

ZOJ1245《Triangles》是一个DP,转移就是看三角形的顶点,从上面一层它的左边和右边两个顶点转移的。或者从下面一层左右顶点转移的。 要注意的是奇偶时三角形的方向是不一样的,DP的时候,只能从是它方向的三角形转移过来。然后还有注意一下数组大小,今天就是这样WA了一下午。

ZOJ1298《Domino Effect》是一个有意思的题,问多米诺效应产生到结束一共需要的时间。其实就是个最短路,但是你不知道最终会在那条边上终止还是在点上终止,这个时候就需要枚举边,再算出结果找出一个耗时最大的,就是答案了。

ZOJ1301《The New Villa》是一个宽搜,要把因为点只有10个,可以用一个int按位存取操作。本身很基础,就是状态压缩的思想很值得借鉴。 然后这个是个speacial judge的题,需要输出路径。以前我写宽搜的时候,喜欢出队的时候,再把vis数组值1,这样一开始的时候可以少写一次,但是这样好像会出现状态的覆盖和重复入队,以后还是把这个习惯改回来,换成每次入队的时候把vis数组赋值吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[210][210];
int dp[210][210];
int main()
{
  int n;
  int icase = 0;
  while(scanf("%d",&n)&&n)
  {

      icase++;
      gets(str[0]);
      memset(str,0,sizeof(str));
      for(int i=0;i<n;i++)
          gets(str[i]);
      memset(dp,0,sizeof(dp));
      int ans = 0;
      for(int i=0;i<n;i++)
      {
          for(int j=i%2;j<2*n-1;j+=2)
          {
              if(str[i][j] == '-')
              {
                  dp[i][j] = 1;
                  ans = max(ans,dp[i][j]);
                  if(i<1||j<1||j>=2*n-2)continue;
                  if(str[i-1][j] == '-')dp[i][j] = min(dp[i-1][j-1],dp[i-1][j+1])+1;
                  //  cout<<i<<" "<<j<<endl;
                  //  cout<<dp[i][j]<<endl;
                  ans = max(ans,dp[i][j]);
              }
          }
      }
      memset(dp,0,sizeof(dp));
      for(int i=n-1;i>=0;i--)
      {
          for(int j=!(i%2);j<2*n-1;j+=2)
          {
              if(str[i][j] == '-')
              {
                  dp[i][j] = 1;
                  ans = max(ans,dp[i][j]);
                  if(j<1||j>=2*n-2||i>=n-1)continue;
                  if(str[i+1][j] == '-')dp[i][j] = min(dp[i+1][j-1],dp[i+1][j+1])+1;
                  ans = max(ans,dp[i][j]);
              }
          }
      }
      printf("Triangle #%d\n",icase);
      printf("The largest triangle area is %d.\n\n",ans*ans);
  }
}
n

[cpp title="Domino Effect"]
#include<iostream>
#include<memory.h>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define NODE 510
#define INF ((1<<30)-1)
int dist[NODE];
bool vis[NODE];
struct Node
{
  int v,dis;
  Node(){}
  Node(int a,int b)
  {
      v = a;
      dis = b;
  }
  bool operator <(Node a)const
  {
      return dis>a.dis;
  }
};
vector<Node>edge[NODE];
priority_queue<Node>myque;
int n,m;

int dij()
{
  for(int i=0;i<=n;i++)dist[i] = INF;
  dist[1] = 0;
  while(!myque.empty())myque.pop();
  memset(vis,0,sizeof(vis));
  myque.push(Node(1,0));
  Node index;
  while(!myque.empty())
  {
      index = myque.top();
      myque.pop();
      if(vis[index.v])continue;
      vis[index.v] = true;
      for(int i=0;i<edge[index.v].size();i++)
      {
          int v = edge[index.v][i].v;
          int dis = edge[index.v][i].dis;
          if(!vis[v]&&dist[v]>dist[index.v]+dis)
          {
              dist[v] = dist[index.v]+dis;
              myque.push(Node(v,dist[v]));
          }
      }
  }
}

int main()
{
  int a,b,c;
  int icase = 0;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
      icase++;
      if(n+m==0)break;
      if(!m)
      {

          printf("System #%d\n",icase);
          printf("The last domino falls after 0.0 seconds, ");
          printf("at key domino 1.\n");
          printf("\n");
          continue;
      }
      for(int i=0;i<=n;i++)edge[i].clear();
      for(int i=0;i<m;i++)
      {
          scanf("%d%d%d",&a,&b,&c);
          edge[a].push_back(Node(b,c));
          edge[b].push_back(Node(a,c));
      }
      dij();

      double ans = -1;
      int pas;
      int pas2;
      int f = 0;
      for(int k=1;k<=n;k++)
          for(int i=0;i<edge[k].size();i++)
          {
              int v = edge[k][i].v;
              int dis = edge[k][i].dis;
              double dd = double(dist[k]+dist[v]+dis)/2;
              if(dd<=ans)continue;
              ans = dd;
              pas = k;pas2 = v;
              if(!dis)
              {
                  f = 2;
                  continue;
              }
              if(dist[k]>dist[v])
              {
                  if(dist[k]-dist[v]==dis)
                  {
                      f = 1;
                      pas = k;
                  }
                  else
                  {
                      f = 2;
                  }
              }
              else 
              {
                  if(dist[v]-dist[k] == dis)
                  {
                      f = 1;
                      pas = v;
                  }
                  else
                  {
                      f = 2;
                  }
              }
          }
      printf("System #%d\n",icase);
      printf("The last domino falls after %.1lf seconds, ",ans);
      if(f==1)printf("at key domino %d.\n",pas);
      else printf("between key dominoes %d and %d.\n",pas,pas2);
      printf("\n");
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

vector<int>edge[110],swit[110];
bool vis[2050][11];
struct Node
{
  int x,v;
  int stp;
  bool flag;//0->move;1->switch light
  int on;//1->on,0->off
  Node(){}
  Node(int xx,int vv,int sstp,int fflag)
  {
      x = xx;v = vv;
      stp = sstp;flag = fflag;
  }
}node[2050][11];
queue<Node>myque;
int n,m,e,icase = 0;
int bfs(int srcls,int src,int desls,int des)
{
  while(!myque.empty())myque.pop();
  myque.push(Node(srcls,src,0,0));
  vis[srcls][src] = true;
  while(!myque.empty())
  {
      Node p = myque.front();
      myque.pop();
      if(p.x==desls&&p.v==des)return p.stp;
      for(int i=0;i<edge[p.v].size();i++)
      {
          int v = edge[p.v][i];
          if((p.x&(1<<(v-1)))&&!vis[p.x][v])
          {
              node[p.x][v] = Node(p.x,p.v,-1,0);
          //  cout<<"from "<<p.x<<" "<<p.v<<" (";
          //  cout<<v<<" moved )";
              vis[p.x][v]=true;
              myque.push(Node(p.x,v,p.stp+1,0));

          //  cout<<"to "<<p.x<<" "<<v<<endl;
          }
      }
      for(int i=0;i<swit[p.v].size();i++)
      {
          int v = swit[p.v][i];
          int t = (p.x^(1<<(v-1)));
          if(!vis[t][p.v])
          {
              node[t][p.v] = Node(p.x,p.v,v,1);
          //  cout<<"from "<<p.x<<" "<<p.v<<" ";
              if(p.x&(1<<(v-1)))
              {
          //      cout<<"("<<v<<" off)";
                  node[t][p.v].on = 0;
              }
              else
              {
          //      cout<<"("<<v<<" lighted)";
                  node[t][p.v].on = 1;
              }
              vis[t][p.v] = true;
              myque.push(Node(t,p.v,p.stp+1,0));
          //  cout<<"to "<<t<<" "<<p.v<<endl;
          }
      }

  }
  return -1;

}
char ligstr[2][5] = {"off","on"};

void print(int ss,int v)
{
  if(ss==1&&v==1)return;
  print(node[ss][v].x,node[ss][v].v);
  if(node[ss][v].flag)
  {
      printf("- Switch %s light in room %d.\n",ligstr[node[ss][v].on],node[ss][v].stp);
  }
  else printf("- Move to room %d.\n",v);
}

int main()
{
  int a,b;
  while(scanf("%d%d%d",&n,&m,&e)!=EOF)
  {
      if(n+m+e==0)break;
      icase++;
      for(int i=0;i<=n;i++)
      {
          edge[i].clear();
          swit[i].clear();
      }
      for(int i=0;i<m;i++)
      {
          scanf("%d%d",&a,&b);
          edge[a].push_back(b);
          edge[b].push_back(a);
      }
      for(int i=0;i<e;i++)
      {
          scanf("%d%d",&a,&b);
          if(a==b)continue;
          swit[a].push_back(b);
      }
      for(int i=1;i<=n;i++)
      {
          sort(swit[i].begin(),swit[i].end());
          sort(edge[i].begin(),edge[i].end());
      }
      memset(vis,0,sizeof(vis));
      int ans = bfs(1,1,1<<(n-1),n);
      printf("Villa #%d\n",icase);
      if(ans<0)printf("The problem cannot be solved.\n");
      else
      {
          printf("The problem can be solved in %d steps:\n",ans);
          print(1<<(n-1),n);
      }
      puts("");

  }

  return 0;
}