F. Valuable Cards D. Smithing Skill

D题

F题

F题：

        因为是连续的且都要选，我们直接从左到右去取每个区间到不合法的情况即可，可以在n+1的位置添加一个x来结束区间判断。因为是要乘积为x，那么我们只需要放x的因子进去，不然会超时，同时也可以用vis数组来标记，可以不放重复的元素，在找到不合法区间的时候要清空vector且将vector里有的元素的vis值重新置0.记得判断元素大小，不然会re，或者用map。

        代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
const int mod=1e9+7;
const ll INF=2e9+10;
mt19937_64 rd(23333);
uniform_real_distribution<double> drd(0.000001,0.99999);int n,x;
int vis[N],a[N];void solve(){cin>>n>>x;for(int i=0;i<=x;i++)vis[i]=0;for(int i=1;i<=n;i++){cin>>a[i];}a[n+1]=x;int ans=0;vector<int> t;for(int r=1;r<=n+1;r++){if((((x%a[r])==0)&&vis[x/a[r]])||a[r]==x){ans++;for(auto &y:t)vis[y]=0;t.clear();if(a[r]<=x&&!vis[a[r]]&&x%a[r]==0){t.push_back(a[r]);vis[a[r]]=1;}}else{vector<int> u;for(auto &y:t){if(y*a[r]<=x&&!vis[y*a[r]]&&((x%(y*a[r]))==0)){vis[y*a[r]]=1;//t.push_back(a[r]*y);u.push_back(a[r]*y);}}for(auto &y:u)t.push_back(y);if(a[r]<=x&&!vis[a[r]]&&x%a[r]==0){vis[a[r]]=1;t.push_back(a[r]);}}}cout<<ans<<endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;cin>>t;while(t--){solve();}return 0;
}

D题：

        容易想到贪心，如果a【i】-b【i】很小我们肯定贪心的选这个武器，因为这样花费的金属少。

又因为每次铸造的base cost是a【i】，所以我们需要给每个a【i】-b【i】一个可选的前提条件，就是base cost大于等于a【i】时才可以选，我们可以在读入的时候每次更新f【a【i】】的值，f【a【i】】就表示从a【i】cost以上都可以使用这个最小值a【j】-b【j】。读入好了之后，我们就可以从1到1e6来更新每个base cost可选的最优花费，从小到大更新可以保证后面的每个cost都是大于等于这个a【j】-b【j】的基础花费的（前缀最小值）。

        处理完每个cost的最优选择后，我们考虑dp（我们有m种武器，每次都会用到相同的贪心策略，其实就是预处理这些贪心策略，然后o（1）查询，比如a【i】-b【i】==1的时候每次都是o（n）的复杂度，再乘m就tle了）。因为前面处理完了每个cost的最优选择，也就是说只要有cost，那么一定是选f【cost】这个武器方案，那么也就是说dp【cost】是从dp【cost-f【cost】】+1转移过来的，+1是因为这里我们花费了f【cost】铸造了一个武器。

        当cost大于1e6的时候，我们根据a【i】的范围可知cost一定可以使用f【1e6】的最优选择将cost降到1e6以下，然后直接输出之前算出来的dp值即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
const int mod=1e9+7;
const ll INF=2e9+10;
mt19937_64 rd(23333);
uniform_real_distribution<double> drd(0.000001,0.99999);void solve(){int n,m,b,c;cin>>n>>m;vector<int>a(n);for(int i=0;i<n;++i){cin>>a[i];}vector<int> f(1e6+10,INT_MAX);for(int i=0;i<n;++i){cin>>b;f[a[i]]=min(f[a[i]],a[i]-b);//记录从当前base cost值开始的最小花费（会损坏值） }for(int i=1;i<=1e6;++i){f[i]=min(f[i-1],f[i]);}vector<int> dp(1e6+10,0);for(int i=1;i<=1e6;++i){if(f[i]<=i){dp[i]=dp[i-f[i]]+1;}}int ans=0;for(int i=0;i<m;++i){cin>>c;if(c>1e6){int t=(c-1e6)/f[1e6]+1;ans+=t;c-=t*f[1e6];}ans+=dp[c];}cout<<ans*2<<endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;//cin>>t;while(t--){solve();}return 0;
}