\(A. Gift Carpet\)
void solve(){
int n=read(),m=read();
char a[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
string s="vika";
int cnt=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a[j][i]==s[cnt]){
cnt++;
break;
}
}
}
puts(cnt==4?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(B. Sequence Game\)
int a[N];
void solve(){
int n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
vector<int>ans;
ans.push_back(a[1]);
for(int i=2;i<=n;i++){
if(a[i]>=a[i-1])ans.push_back(a[i]);
else{
ans.push_back(1);
ans.push_back(a[i]);
}
}
cout<<ans.size()<<'\n';
for(auto x:ans){
cout<<x<<' ';
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(C. Flower City Fence\)
int a[N],cnt[N];
map<int,int>mp;
void solve(){
int n=read();
mp.clear();
for(int i=1;i<=n;i++){
a[i]=read();
mp[a[i]]++;
cnt[i]=0;
}
if(a[1]>n){
cout<<"NO\n";
return ;
}
cnt[n+1]=0;
for(int i=n;i>=1;i--){
cnt[i]=cnt[i+1]+mp[i];
}
int ans=1;
for(int i=1;i<=n;i++){
if(a[i]!=cnt[i]){
ans=0;
}
}
puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(D. Ice Cream Balls\)
int n;
bool check(int x) {
int tmp=x*(x-1)/2;
// cout<<x<<" "<<tmp<<'\n';
return tmp<=n;
}
int bs1(int l, int r){ //左偏二分
while (l < r){
int mid = (l + r )>> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int bs2(int l, int r){ //右偏二分
while (l < r){
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
void solve(){
n=read();
int ans=bs2(0,2648956421);
ans+=(n-ans*(ans-1)/2);
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(E. Kolya and Movie Theatre\)
void solve(){
while(pq.size())pq.pop();
int n=read(),m=read(),d=read();
vector<PII>a;
for(int i=1;i<=n;i++){
int x=read();
if(x>0)a.push_back(make_pair(x,i));
}
int sum=0,ans=0;
for(int i=0;i<a.size();i++){
int x=a[i].first,y=a[i].second;
pq.push(x);
sum+=x;
while(pq.size()>m){
int t=pq.top();
pq.pop();
sum-=t;
}
ans=max(ans,sum-d*(y));
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(F. Magic Will Save the World\)
先用 \(dp\) 的方式预处理出所有可能的数对，然后对数对遍历。
复杂度为 \(O(n*\sum a_i)\) 。
void solve(){
int w=read(),f=read(),n=read();
vector<int>a(n+1);
int sum=0;
for(int i=1;i<=n;i++){
a[i]=read();
sum+=a[i];
}
vector<int>dp(sum+1);
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=sum;j>=a[i];j--){
dp[j]|=dp[j-a[i]];
}
}
int ans=sum;
for(int i=0;i<=sum;i++){
if(dp[i]){
ans=min(ans,max((i-1+w)/w,(sum-i-1+f)/f));
}
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(G. The Great Equalizer\)
一次操作不会改变数字的相对位置，而最大值 \(+1\) ，所以最后的答案一定是 \(a_{max}+d_{max}\) ，其中 \(d\) 是相邻值的差（有序时）。
可以用 \(multiset\) 完成对数集的处理。
void solve(){
int n=read();
vector<int>a(n+1);
multiset<int> s, d{0};
auto add = [&](int x) {
auto it = s.insert(x);
auto r = next(it);
if (it != s.begin()) {
d.insert(x - *prev(it));
}
if (r != s.end()) {
d.insert(*r - x);
}
if (it != s.begin() && r != s.end()) {
d.extract(*r - *prev(it));
}
};
auto del = [&](int x) {
auto it = s.find(x);
auto r = next(it);
if (it != s.begin()) {
d.extract(x - *std::prev(it));
}
if (r != s.end()) {
d.extract(*r - x);
}
if (it != s.begin() && r != s.end()) {
d.insert(*r - *prev(it));
}
s.erase(it);
};
for(int i=1;i<=n;i++){
a[i]=read();
add(a[i]);
}
int q=read();
while(q--){
int x=read(),y=read();
del(a[x]);
a[x]=y;
add(a[x]);
cout<< *s.rbegin()+*d.rbegin()<<' ';
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}