首页 > 代码库 > Codeforces_822
Codeforces_822
A.小的那个数的阶乘。
#include<bits/stdc++.h> using namespace std; int a,b; int main() { ios::sync_with_stdio(0); cin >> a >> b; int t = min(a,b); int ans = 1; for(int i = 1;i <= t;i++) ans *= i; cout << ans << endl; return 0; }
B.暴力t串的起始位置,比较两个串。
#include<bits/stdc++.h> using namespace std; int n,m; string s1,s2; vector<int> v; int main() { ios::sync_with_stdio(0); cin >> n >> m >> s1 >> s2; s1 = ‘ ‘+s1; s2 = ‘ ‘+s2; int ans = 1e9; for(int i = 0;i <= m-n;i++) { int cnt = 0; for(int j = 1;j <= n;j++) { if(s1[j] != s2[i+j]) cnt++; } if(cnt < ans) { ans = cnt; v.clear(); for(int j = 1;j <= n;j++) { if(s1[j] != s2[i+j]) v.push_back(j); } } } cout << ans << endl; for(int i = 0;i < v.size();i++) cout << v[i] << " "; cout << endl; return 0; }
C.先按l排序,遍历每一段,维护一个优先队列,每次把当前之前的段从优先队列中拿出来,更新对应长度的最小花费,然后把该段放进优先队列。
#include<bits/stdc++.h> using namespace std; int n,x; map<int,int> mp; struct xx { int l,r,c; friend bool operator <(xx a,xx b) { return a.l < b.l; } }a[200005]; struct yy { int r,len,c; yy(int a,int b,int cc):r(a),len(b),c(cc){}; friend bool operator <(yy a,yy b) { return a.r > b.r; } }; priority_queue<yy> q; int main() { ios::sync_with_stdio(0); cin >> n >> x; for(int i = 1;i <= n;i++) cin >> a[i].l >> a[i].r >> a[i].c; sort(a+1,a+1+n); int ans = 2e9+5; for(int i = 1;i <= n;i++) { while(!q.empty() && q.top().r < a[i].l) { if(!mp.count(q.top().len)) mp[q.top().len] = q.top().c; else mp[q.top().len] = min(mp[q.top().len],q.top().c); q.pop(); } int len = a[i].r-a[i].l+1; if(mp.count(x-len)) ans = min(ans,a[i].c+mp[x-len]); q.push(yy(a[i].r,len,a[i].c)); } if(ans == 2e9+5) cout << -1 << endl; else cout << ans << endl; return 0; }
D.暴力dp刚好卡过。
#include<bits/stdc++.h> #define MOD 1000000007 using namespace std; int t,l,r; long long dp[5000005],f[5000005]; int main() { ios::sync_with_stdio(0); cin >> t >> l >> r; for(int i = 1;i <= r;i++) { f[i] = (long long)i*(i-1)/2; dp[i] = f[i]; } for(int i = 2;i <= r;i++) { for(int j = i,k = 1;j <= r;j += i,k++) dp[j] = min(dp[j],dp[i]*k+f[k]); } long long tt = 1,ans = 0;; for(int i = l;i <= r;i++) { ans = (ans+dp[i]%MOD*tt)%MOD; tt = tt*t%MOD; } cout << ans << endl; return 0; }
Codeforces_822
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。