TCO 2014 Round 1A

顺利搞出  A B 两题,然后压线晋级了,手速场。

A 题 , 求排列最小的,肯定从后往前来做,维护一个最小的set,只是第一个字母要特判一下。

   1:  #line 5 "EllysSortingTrimmer.cpp"
   2:  #include <vector>
   3:  #include <list>
   4:  #include <map>
   5:  #include <set>
   6:  #include <deque>
   7:  #include <stack>
   8:  #include <bitset>
   9:  #include <algorithm>
  10:  #include <functional>
  11:  #include <numeric>
  12:  #include <utility>
  13:  #include <sstream>
  14:  #include <iostream>
  15:  #include <iomanip>
  16:  #include <cstdio>
  17:  #include <cmath>
  18:  #include <cstdlib>
  19:  #include <ctime>
  20:  #include <cstring>
  21:  using namespace std;
  22:  int i,j,k;
  23:  #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
  24:  #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  25:   
  26:   
  27:  class EllysSortingTrimmer
  28:  {
  29:  public:
  30:  string getMin(string S, int L)
  31:  {
  32:      vector<char> s;
  33:      for(int i=1; i<S.size(); i++) s.push_back(S[i]);
  34:      sort(s.begin(),s.end());
  35:      vector<char> t;
  36:      for(int i=0; i<L-1; i++) t.push_back(s[i]);
  37:      t.push_back(S[0]);
  38:      sort(t.begin(), t.end());
  39:      string ret;
  40:      for(int i=0; i<L; i++) ret += t[i];
  41:      return ret;
  42:  }
  43:   
  44:   
  45:  };
  46:   

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

B题  不要搞成匹配的问题,每一个字母都有一个位置范围,所以只要维护一个set,保证其能够被写入,其余时间都插入最小就OK

   1:  #line 5 "EllysScrabble.cpp"
   2:  #include <vector>
   3:  #include <list>
   4:  #include <map>
   5:  #include <set>
   6:  #include <deque>
   7:  #include <stack>
   8:  #include <bitset>
   9:  #include <algorithm>
  10:  #include <functional>
  11:  #include <numeric>
  12:  #include <utility>
  13:  #include <sstream>
  14:  #include <iostream>
  15:  #include <iomanip>
  16:  #include <cstdio>
  17:  #include <cmath>
  18:  #include <cstdlib>
  19:  #include <ctime>
  20:  #include <cstring>
  21:  using namespace std;
  22:  int i,j,k;
  23:  #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
  24:  #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  25:   
  26:   
  27:  class EllysScrabble
  28:  {
  29:  public:
  30:  string getMin(string letters, int maxDistance)
  31:  {
  32:      pair<char, int> X;
  33:      vector<pair<char, int> > S;
  34:      for(int i=0; i<letters.size(); i++)
  35:      {
  36:          S.push_back( make_pair(letters[i], i));
  37:      }
  38:   
  39:      string ret;
  40:   
  41:      vector<pair<char, int> > tmp;
  42:      for(int i=0; i<  min(letters.size() *1.0,maxDistance + 1.0); i++) tmp.push_back(make_pair(letters[i], i));
  43:      for(int i=0; i<letters.size(); i++)
  44:      {
  45:          // search
  46:          sort(tmp.begin(), tmp.end());
  47:          bool flag = 0;
  48:          for(int j=0; j< tmp.size(); j++)
  49:          {
  50:              if(i - tmp[j].second == maxDistance)
  51:              {
  52:                  ret += tmp[j].first;
  53:                  tmp.erase(tmp.begin() + j);
  54:                  flag = true;
  55:                  break;
  56:              }
  57:          }
  58:          if(flag == false)
  59:          {
  60:              ret += tmp[0].first;
  61:              tmp.erase(tmp.begin());
  62:          }
  63:   
  64:          // push
  65:          if(i + maxDistance + 1 < letters.size())
  66:          {
  67:              tmp.push_back(S[ i+ maxDistance +1]);
  68:          }
  69:      }
  70:      return ret;
  71:  }
  72:   
  73:   
  74:  };
  75:   

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

C题   这个题目开始的时候没搞出来,其实当时已经发下了 YYY, NY YN3种情况肯定会有一个是亮的。但是没有仔细想。这个为什么贪心是对的呢?给出每一个序列,NY YN YYY一定是最大的,这个仔细推了一下好像是对的!但是有没有严格证明出来。

#line 5 "EllysLamps.cpp"
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
int i,j,k;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) class EllysLamps
{
public:
int getMin(string lamps)
{
int num = 0; for(int i=0; i<lamps.size();)
{
if(i+1 < lamps.size() && lamps[i] != lamps[i+1])
{
i+=2;
num++;
}else if(i+2 < lamps.size() && lamps[i] == lamps[i+1] && lamps[i] == lamps[i+2] && lamps[i]== 'Y')
{
i+=3;
num++;
}else i++;
}
return num;
} };

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

上一篇:linux下的shell脚本的使用


下一篇:VUE环境搭建、创建项目、vue调试工具