西安做公司网站,wordpress支持pdo,新乐市建设银行网站,制作网站怎样找公司来帮做D题
F题
F题#xff1a; 因为是连续的且都要选#xff0c;我们直接从左到右去取每个区间到不合法的情况即可#xff0c;可以在n1的位置添加一个x来结束区间判断。因为是要乘积为x#xff0c;那么我们只需要放x的因子进去#xff0c;不然会超时#xff0c;同时也可以用v…D题
F题
F题 因为是连续的且都要选我们直接从左到右去取每个区间到不合法的情况即可可以在n1的位置添加一个x来结束区间判断。因为是要乘积为x那么我们只需要放x的因子进去不然会超时同时也可以用vis数组来标记可以不放重复的元素在找到不合法区间的时候要清空vector且将vector里有的元素的vis值重新置0.记得判断元素大小不然会re或者用map。 代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pairll,ll pii;
const int inf0x3f3f3f3f;
const int N2e510;
const int mod1e97;
const ll INF2e910;
mt19937_64 rd(23333);
uniform_real_distributiondouble drd(0.000001,0.99999);int n,x;
int vis[N],a[N];void solve(){cinnx;for(int i0;ix;i)vis[i]0;for(int i1;in;i){cina[i];}a[n1]x;int ans0;vectorint t;for(int r1;rn1;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{vectorint 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]);}}}coutansendl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t1;cint;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种武器每次都会用到相同的贪心策略其实就是预处理这些贪心策略然后o1查询比如a【i】-b【i】1的时候每次都是on的复杂度再乘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值即可。
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pairll,ll pii;
const int inf0x3f3f3f3f;
const int N2e510;
const int mod1e97;
const ll INF2e910;
mt19937_64 rd(23333);
uniform_real_distributiondouble drd(0.000001,0.99999);void solve(){int n,m,b,c;cinnm;vectorinta(n);for(int i0;in;i){cina[i];}vectorint f(1e610,INT_MAX);for(int i0;in;i){cinb;f[a[i]]min(f[a[i]],a[i]-b);//记录从当前base cost值开始的最小花费会损坏值 }for(int i1;i1e6;i){f[i]min(f[i-1],f[i]);}vectorint dp(1e610,0);for(int i1;i1e6;i){if(f[i]i){dp[i]dp[i-f[i]]1;}}int ans0;for(int i0;im;i){cinc;if(c1e6){int t(c-1e6)/f[1e6]1;anst;c-t*f[1e6];}ansdp[c];}coutans*2endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
