Topcoder SRM 756 (Div.2)

第一次参加Topcoder的比赛233(主要是时间正合适)。

A. CinderellaGirls

数据范围实在太小了,模拟即可。

class CinderellaGirls
{
 public:
  int count(vector<int>talent,vector<int>skill)
  {
   int a[55],ans=0;
   memset(a,0,sizeof(a));
   int n=skill.size();
   for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
     if(talent[i]>talent[j]&&skill[i]>skill[j])a[j]=1;
   for(int i=0;i<n;i++)
    if(!a[i])ans++;
   return ans;
  }
};

B. PAndPuns

如果能找到一个串\(S\)满足在给出的字符串中出现两次以上的条件,那么\(S\)的任意一个长度大于等于\(2\)的子串都会满足这个条件。

所以我们只用枚举长度为\(2\)的串进行检验即可。

class PAndPuns
{
 public:
  string check(string text)
  {
   int a[2505];
   int len=text.length();
   for(int i=1;i<len;i++)//字符串哈希
    a[i]=(text[i-1]-'a')*26+(text[i]-'a');
   for(int i=1;i<len;i++)
    for(int j=i+2;j<len;j++)
     if(a[i]==a[j])return "pun";
   return "not a pun";
  }
};

C. NewBanknote

询问的面额实在太大,传统的背包做法显然无法解决本题,搜索显然也要TLE。

让我们从数据范围下手。我们可以枚举新钞票的使用张数,扣除这部分面额后贪心处理剩下的面额即可。

为什么这样是高效正确的呢?

可以证明新钞票的使用量不会超过\(50000\)张。原因很简单:如果新钞票面额超过\(50000\),那使用\(50000\)张钞票早已经超过了要询问的面额上限;否则,\(50000\)张新钞票还不如全部替换成\(50000\)的钞票,这样还能使解更优。

class NewBanknote
{
 public:
  vector<int> fewestPieces(int newBanknote, vector<int> amountsToPay)
  {
   int money[]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000};
   int t=amountsToPay.size();
   vector<int> res;
   for(int i=0;i<t;i++)
   {
    res.push_back(amountsToPay[i]);
    for(int j=0;j<=50000;j++)
    {
     long long num=(long long)amountsToPay[i]-newBanknote*j;
     if(num<0)break;
     int cnt=j;
     for(int k=14;k>=0;k--)
     {
      cnt+=num/money[k];
      num%=money[k];
     }
     res[i]=min(res[i],cnt);
    }
   }
   return res;
  }
};

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注