DAY 10 TJ

· · 个人记录

DAY 10 TJ

魔法商店

【题目描述】

把n件物品逐一编上了从1到n的序号，其中第 件商品的魔力值被标记为a[i]。
共接收了m份来自四面八方的订单。每份订单上都详细记录着客户的姓名、尊贵级别、收货地址以及至关重要的魔法能力值b[i] 。根据魔法世界的规则，客户仅能驾驭魔力值不超过其自身魔法能力的物品 计算出他最多能够满足多少份订单的需求，以确保他的魔法商店能够持续赢得顾客的欢心与信赖

错因

把问题想的太复杂，写了一个毫无意义的二分，并且没有证明自己的贪法是正确的。

正解：

数组排序后比较是否b[k]≥a[i].

::::info[AC CODE:]

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long a[200005],b[200005],ans,k;
long long l,r,mi;
int main(){
// freopen("shop.in","r",stdin);
// freopen("shop.out","w",stdout);
  std::ios::sync_with_stdio(false);
  cin>>n>>m;
  for(int i=1;i<=n;i++){
      cin>>a[i];
  }
  for(int i=1;i<=m;i++){
      cin>>b[i];
  }
  sort(a+1,a+n+1);
  sort(b+1,b+m+1);
  k=m;
  for(int i=n;i&&k;i--){
      if(b[k]>=a[i]){
          ans++;
          k--;
      }
  }
  cout<<ans;
  return 0;
}

::::

解锁手机

【题目描述】

Pin码是一个 位的纯数字码,每一位数字都由0至9之一的数字组成。
用字符串s描述,字符串中包含S1、S2、S3……、S9，s长度固定为10。
其中Si只可能是 y 、 n 与 ? 三个字符之一，其中 为 y 代表 Pin码中必然存在数字 ， 为 n 代表Pin码中必然没有数字 ，为 ? 代表Pin码中可能有也可能没有数字 。Z老师为了打开他的鸭梨手机，找到了懂编程的你，帮他计算一下Z老师最少需要尝试多少次才能够打开他的鸭梨手机。如果不能打开则输出 。

错因：

相信自己的数学，结果理论及代码均错误。。

正解：

记录 '?'及 'y'暴力枚举，因为数据很小。我好菜awa ::::info[AC CODE:]

#include<bits/stdc++.h>
using namespace std;
string ans,s;
int sum,sy,sa;
vector<int >y,aa;
void dfs(int a){
  if(a==6){
      bool flag[10]={0};
      for(int i=0;6>i;i++)
          flag[ans[i]-'0']=1;
      for(auto it:y) 
          if(flag[it]==0) return ;
      sum++;  
      return ;        
  }
  for(auto it:y){
      string now=ans;
      ans+=char(it+'0');
      dfs(a+1);
      ans=now;
  }
  for(auto it:aa){
      string now=ans;
      ans+=char(it+'0');
      dfs(a+1);
      ans=now;
  }
}
int main(){
  //freopen("unlock.in","r",stdin);
  //freopen("unlock.out","w",stdout);
  cin>>s;
  for(int i=0;s.size()>i;i++){
      if(s[i]=='y') sy++,y.push_back(i);
      if(s[i]=='?') sa++,aa.push_back(i);
  }
  if(sy>6){
      cout<<'0';
      return 0;
  }
  dfs(0); 
  cout<<sum;
  return 0;
}

::::

深境螺旋

【题目描述】

深渊A：有n层，从上至下每层需要打a[i]分钟。
深渊B：有m层，从上至下每层需要打b[i]分钟。
请输出，在k分钟内，最多总共能打多少层（深渊A与深渊B一起）。

错因：

我爱贪心用贪心贪了60分

正解：

用前缀和与贪心比较a[i]与b[i] ::::info[AC CODE:]


#include<bits/stdc++.h>
using namespace std;
long long ans,n,m,k,a[200010],b[200010],sum2[200010],sum1[200010];
int main(){
//freopen("abyss.in","r",stdin);
//freopen("abyss.out","w",stdout);
cin>>n>>m>>k;
for(int i=1;n>=i;i++){
scanf("%d",&a[i]);
sum1[i]=sum1[i-1]+a[i];
}
for(int i=1;m>=i;i++){
scanf("%d",&b[i]);
sum2[i]=sum2[i-1]+b[i];
}   
for(int i=1;n>=i;i++){
if(k<sum1[i]) break;
k-=sum1[i];
long long l=1,r=m,mid;
while(l<=r){
mid=(l+r)/2;
if(k>=sum2[mid]){
ans=max(ans,i+mid);
l=mid+1;
}
else{
r=mid-1;
}
}
k+=sum1[i];
}
for(int i=1;m>=i;i++){
if(k<=sum2[i]) break;
k-=sum2[i];
long long l=1,r=n,mid;
while(l<=r){
mid=(l+r)/2;
if(k>=sum1[mid]){
ans=max(ans,i+mid);
l=mid+1;
}
else{
r=mid-1;
}
}
k+=sum2[i];
}
cout<<ans;
return 0;
}
::::
## 数字积木
>>【题目描述】
>
>小酷拥有n块独特的数字积木，每块积木上都刻有一个数字。小爱，这位数字艺术家，决定从小酷的积木堆中挑选出k块，利用它们来构建出各种新颖的数字串。小爱的创造力无限，她可以将选中的积木按照任意顺序排列，创造出独一无二的数字作品。  
>现在，我们面临一个挑战：要计算出在所有可能的 块积木组合中，小爱能够创造出多少种独一无二的数字串。
>>错因：
>
>没有思路，骗了30分。
>>正解：
>
>暴力枚举(???第五题出现这个正常吗
::::info[*AC CODE:*]

include<bits/stdc++.h>

using namespace std; int n,m,ans; map<string ,bool >mp; string sum,s[15]; bool flag[15]; void dfs(int a){ if(a==m){ if(mp.count(sum)==0){ mp[sum]=1; ans++; } return; } for(int i=1;n>=i;i++){ if(flag[i]==0){ flag[i]=1; string now=sum; sum+=s[i]; dfs(a+1); sum=now; flag[i]=0; } } } int main(){ //freopen("splice.in","r",stdin); //freopen("splice.out","w",stdout); cin>>n>>m; for(int i=1;n>=i;i++) cin>>s[i]; dfs(0); cout<<ans; return 0; }

::::
* * *
## 然气管道
>>【题目描述】
>
>您负责沿道路安装天然气管道，让我们将道路视为x轴上[0,n]的一个部分。道路可以有多个十字路口，但为简单起见，我们将每个十字路口表示为一个间隔，其中0表示非十字路口，1表示十字路口。  
>通常，我们可以沿着道路高度安装高度为1的支撑柱，每个整数点中都有支撑柱（因此，如果我们负责[0，n]路，我们必须安装N+1个支撑柱）。但是在十字路口，我们应该将管道提升到高度2，这样管道不会阻碍汽车的道路。
>每个单位的管道（红色部分）需要花费a元，每个单位的支柱（黑色部分）需要花费b元，因此，将整个管道放在高度2上并不总是最佳的，请以尽可能低的成本找到管道的形状并计算该成本。  
>请注意，开始和结束时的管道铺设高度必然为1。
>>错因：
>
>不会，贪了60分。
>>正解：
>
>DP~~哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈~~  
>公式：

dp[i][1]=a+b+min(dp[i−1][1],dp[i][2]+a) (当下面不是十字路口时) dp[i][2]=2∗b+a+min(dp[i−1][1]+a+b,dp[i−1][2])

::::info[*AC CODE:*]

include<bits/stdc++.h>

using namespace std; long long n,a,b,ans,k[200005][5]; char s[200005]; int main(){ // freopen("gas.in","r",stdin); // freopen("gas.out","w",stdout); std::ios::sync_with_stdio(false); cin>>n>>a>>b; for(int i=1;i<=n;i++){ cin>>s[i]; } for(int i=0;i<=n;i++){ k[i][1]=1e18; k[i][2]=1e18; } k[0][1]=b; for(int i=1;i<=n;i++){ if(s[i]=='1'){ k[i][2]=2b+a+min(k[i-1][1]+b+a,k[i-1][2]); } else{ k[i][1]=b+a+min(k[i-1][1],k[i-1][2]+a); k[i][2]=2b+a+min(k[i-1][2],k[i-1][1]+a+b); } } cout<<k[n][1]; return 0; }


::::
收尾！