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;
  }
};