A - Feet
直接代入计算。
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>a>>b;cout<<a*12+b;return 0;
}
B - Tombola
直接模拟即可。
#include<bits/stdc++.h>
using namespace std;
int h,w,n,ans;
int a[110][110],cnt[110];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>h>>w>>n;for(int i=1;i<=h;i++){for(int j=1;j<=w;j++) cin>>a[i][j];}for(int i=1;i<=n;i++){int q;cin>>q;for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){if(a[i][j]==q){cnt[i]++;break;} }}}for(int i=1;i<=n;i++) ans=max(ans,cnt[i]);cout<<ans;return 0;
}
C - Reindeer and Sleigh 2
考虑所有鹿都在雪橇上时，总重量为 \(\sum w_i\)，换下第 \(i\) 个鹿，拉力 \(+p_i\)，重量 \(-w_i\)。
题目要求拉力 \(\ge\) 重力，即总重量 \(-\) 拉力 \(\le0\)。根据刚才推得，换下第 \(i\) 个鹿，总重量 \(-\) 拉力变小 \(w_i+p_i\)，则按 \(w_i+p_i\) 从大到小选择拉雪橇的鹿直到该值 \(\le 0\) 即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int T,n,sum,ans;
int w[N],p[N],a[N];
bool cmp(int x,int y){return x>y;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n;sum=ans=0;for(int i=1;i<=n;i++){cin>>w[i]>>p[i];a[i]=p[i]+w[i];sum+=w[i];} sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){if(sum<=0) break;ans++;sum-=a[i];}cout<<n-ans<<'\n';}return 0;
}
D - Sum of Differences
先考虑没有绝对值怎么做。对于每个 \(a_i\)，都要加 \(m\) 次并减去整个 \(b\) 序列的和 \(\sum b_j\)，累加统计答案即可。
接着考虑加上绝对值，则对于 \(>a_i\) 的 \(b_j\)，需要取相反数。二分查找 \(b\) 中 \(\le a_i\) 的位置 \(k\)，维护 \(b\) 的前缀和，则对于 \(a_i\)，其贡献为 \(k\times a_i-sumb_k+sumb_m-sumb_k-(m-k)\times a_i\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
const int p=998244353;
int n,m,ans;
int a[N],b[N];
int sumb[N];
int bfind(int tar){int l=1,r=m,mid;while(l<r){mid=(l+r+1)/2;if(b[mid]<=tar) l=mid;else r=mid-1;}return l;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];sort(b+1,b+1+m);for(int i=1;i<=m;i++) sumb[i]=sumb[i-1]+b[i];for(int i=1;i<=n;i++){int t=upper_bound(b+1,b+1+m,a[i])-b-1;int res=(a[i]*t-2*sumb[t]+sumb[m]-a[i]*(m-t))%p;ans=(ans+res)%p;}cout<<ans;return 0;
}
E - Sort Arrays
向已有序列后接元素形成新序列，不难想到字典树。按字典序排列即字典树的先序遍历，其中同一层的节点按字典序排列。
接着考虑同一大小的元素，如何让其按给定顺序输出。可以把这些元素合并为一个节点，同时维护每个节点包含的编号，按顺序排列。
使用 map 维护每个节点的出边，以及 vector 维护每个节点包含的编号。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n;
int h[N],tot=1;
int a[N],b[N];
map<int,int> G[N];
vector<int> unq[N];
void dfs(int u){for(int i=0;i<unq[u].size();i++) cout<<unq[u][i]<<' ';for(auto i:G[u]) dfs(i.second);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);h[0]=1;cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];int u,v;u=h[a[i]];if(!G[u].count(b[i])) G[u][b[i]]=++tot;v=G[u][b[i]];h[i]=v,unq[v].push_back(i);} dfs(1);return 0;
}