AtCoder Beginner Contest 373 (A-F)
A - September
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int ans=0;
for(int i=1;i<=12;i++){
string s;
cin>>s;
ans+=((int)s.size()==i);
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
B - 1D Keyboard
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
string s;
cin>>s;
vector<int> p(26);
for(int i=0;i<26;i++){
p[s[i]-'A']=i;
}
int ans=0;
for(int i=1;i<26;i++){
ans+=abs(p[i]-p[i-1]);
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
C - Max Ai+Bj
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int n;
cin>>n;
vector<int> a(n),b(n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
cout<<*max_element(a.begin(),a.end())+*max_element(b.begin(),b.end());
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
D - Hidden Weights 图论+构造
思路：
直接建一条等价的反向边，然后DFS构造即可。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int n,m;
cin>>n>>m;
vector<vector<array<i64,2>>> e(n);
while(m--){
int u,v,w;
cin>>u>>v>>w;
u--;
v--;
e[u].push_back({v,w});
e[v].push_back({u,-w});
}
vector<i64> vis(n),ans(n);
function<void(int)> dfs=[&](int u){
if(vis[u]) return;
vis[u]=1;
for(auto [v,w]:e[u]){
ans[v]=ans[u]+w;
dfs(v);
}
};
for(int i=0;i<n;i++) dfs(i);
for(auto x:ans) cout<<x<<" ";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
E - How to Win the Election 二分答案
思路：
考虑二分答案，令 \(w\) 表示当前候选人的选票数量，\(check\) 函数判断大于等于 \(w+1\) 的数量是否大于等于 \(m\) 即可。如果已经有 \(m\) 个选票大于 \(w+1\) 那么直接 \(return false\)。否则，我们判断将剩下的补够 \(m\) 个选票数量是否足够即可。排序后，前缀和可以快速求出所需选票数量。注意，如果当前候选人也属于最大的 \(m\) 个选票时，需要筛除掉。特判一下即可。具体实现看代码。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
i64 n,m,k;
cin>>n>>m>>k;
vector<i64> a(n+1),b(n+1),p(n+1),s(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
p[i]=i;
}
if(m==n){
for(int i=1;i<=n;i++){
cout<<0<<" ";
}
return;
}
sort(p.begin()+1,p.end(),[&](int x,int y){
return a[x]<a[y];
});
for(int i=1;i<=n;i++) s[i]=s[i-1]+(b[i]=a[p[i]]);
auto check=[&](int i,i64 mid)->bool{
i64 w=a[p[i]]+mid+1;
if(w<=b[n-m+1]) return false;
int l=n-m+1,r=n;
while(l<r){
int mid=l+r+1>>1;
if(b[mid]<w) l=mid;
else r=mid-1;
}
i64 v=k-s[n]-mid;
if(i>n-m){
v-=w*(l-(n-m))-(s[l]-s[n-m-1]-b[i]);
}else{
v-=w*(l-(n-m))-(s[l]-s[n-m]);
}
return v<0;
};
vector<i64> ans(n+1);
for(int i=1;i<=n;i++){
i64 l=0,r=k-s[n];
while(l<r){
i64 mid=l+r>>1;
if(check(i,mid)) r=mid;
else l=mid+1;
}
ans[p[i]]=(check(i,l)?l:-1);
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
F - Knapsack with Diminishing Values DP+思维
思路：
考虑 \(dp\)，类似背包。
令 \(f_{i,j}\) 表示前 \(i\) 个物品中，体积为 \(j\) 时的最大价值。
状态转移：\(f_{i,j}=max(f_{i-1,j-w_i*k_i+v_i*k_i-k_i*k_i})\)
时间复杂度为 ：\(O(n^3)\) 。考虑优化，我们发现如果每个 \(w_i\) 都不相等的情况下，那么 \(w_i=1\) 时就会跑 \(W\) 次，
\(w_i=2\) 时，跑 \(W/2\) 次，这是一个调和级数，时间复杂度就是 \(O(n^2log\) \(n\)) 。
所以我们考虑把相同体积的物品进行合并考虑，令 \(g_{i,j}\) 表示体积为 \(i\) 的物品选了 \(j\) 件的最大价值，转移需要我们求出单独取物品的价值，因为取 \(k\) 个相同的物品价值为 \(v*k-k^2\)。那么取 \(k+1\) 个相同的物品价值为 \(v*(k+1)-(k+1)^2\) ，作差我们发现，比取 \(k\) 个多了 \(v-2*k-1\) 。因此这就是第 \(k+1\) 次取物品的价值。
所以，我们可以把所有体积相同的物品放到优先队列中，贪心取出最大值转移即可。
得到 \(g_{i,j}\) 后，我们就可以进行转移了。
\(f_{i,j}=max(f_{i,j},f_{i-1,j-k*i}+g_{i,k})\)
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int n,W;
cin>>n>>W;
vector<i64> v(n+1);
vector<vector<i64>> w(W+1);
for(int i=1;i<=n;i++){
int x;
cin>>x>>v[i];
w[x].push_back(i);
}
vector<vector<i64>> f(W+1,vector<i64>(W+1));
auto g=f;
priority_queue<i64> pq;
for(int i=1;i<=W;i++){
int h=W/i;
while(!pq.empty()) pq.pop();
for(auto j:w[i]){
pq.push(v[j]-1);
}
for(int j=1;j<=h;j++){
if(pq.empty()) break;
i64 vv=pq.top();
pq.pop();
g[i][j]=g[i][j-1]+vv;
vv-=2;
pq.push(vv);
}
for(int j=1;j<=W;j++){
f[i][j]=f[i-1][j];
for(int k=1;k<=h;k++){
if(j<k*i) break;
f[i][j]=max(f[i][j],f[i-1][j-k*i]+g[i][k]);
}
f[i][j]=max(f[i][j-1],f[i][j]);
}
}
cout<<f[W][W]<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}