A题 简答模拟题
#include <iostream>
#include<stdio.h>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int a[],b[]; int main()
{
freopen("/Users/zjg/CLionProjects/ac/A-large-practice.in","r",stdin);
freopen("/Users/zjg/CLionProjects/ac/A-large-practice.out","w",stdout);
int TT;
cin>>TT;
for(int t=;t<=TT;t++)
{
memset(a,,sizeof(a));
memset(b,,sizeof(b));
vector<int> v;
int n,k;
cin>>n>>k;
for(int i=;i<n;i++)
cin>>a[i];
sort(a,a+n);
int T=;
for(int i=;i<n;i++)
{
if(i==)
{
b[T]++;
v.push_back(a[i]);
}
else if(a[i]==a[i-])b[T]++;
else if(a[i]!=a[i-])
{
b[++T]++;
v.push_back(a[i]);
}
}
long long num=;
long long ans=; for(int i=v[T];i>;i--)
{
if(T>=&&i==v[T])
num+=b[T--];
ans+=num<k?num:k;
if(num>k)num-=k;
else num=;
}
cout<<"Case #"<<t<<": "<<ans<<endl;
}
return ;
}
B题
正解是按照bit构造。因为只有M个constraint，所以只要找到complaint最小的前M+1个二进制数，一定有一个是符合条件的。假设s[0,...,p+1]位于前M+1个，那么s[0,..,p]一定也是前M+1个。Proof by contradiction: 如果s[0,...,p+1](表示长度为p+1)是前M+1个而s[0,...,p]不是，假设s[p+1]增加的complaint是x，那么排在s[0,...,p]之前的s'[0,...,p]增加一个相同的bit (s[p+1])，构成的新的二进制数的complaint一定比s[0,...,p+1]小，如此可以产生多于M+1个complaint比s[0,..,p+1]小的二进制数，和s[p+1]位于前M+1矛盾。
Then 如果s[0,...,p]不是前M+1个，s[0,..,p+1]一定也不是前M+1个，无论新增的bit是0 or 1.所以对于每个bit p，维护前M个s[0,..,p]，对下一个bit增加0 or 1，再对bit p+1排序找出前M+1个……
可以预处理求出N个二进制数bit p的1的个数之和，这样从bit p to bit p+1可以O(1)求出新增的complaint。
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include <set>
#include<algorithm>
#include<cstring> using namespace std; int main(){
freopen("/Users/zjg/CLionProjects/ac/B-large-practice.in","r",stdin);
freopen("/Users/zjg/CLionProjects/ac/B-large-practice.out","w",stdout);
int kase;
cin>>kase;
for(int k=;k<kase;k++){
int n,m,p;
cin>>n>>m>>p;
vector<int> cnt(p);
for(int i=;i<n;i++){
string s;
cin>>s;
for(int j=;j<p;j++)if(s[j]=='') ++cnt[j];
}
vector<string> ban(m);
for(int i=;i<m;i++) cin>>ban[i];
priority_queue<pair<int,string>> que; que.emplace(,"");
for(int i=;i<p;i++){
int a=cnt[i];
int b=n-a;
auto tmp=que;
while(que.size()) que.pop();
while(tmp.size()){
int t;
string s;
tie(t,s)=tmp.top(); tmp.pop();
que.emplace(t+a,s+"");
que.emplace(t+b,s+"");
while(que.size()>) que.pop();
}
}
int re;
set<string> st(ban.begin(),ban.end());
while(que.size()){
int t;
string s;
tie(t,s)=que.top(); que.pop();
if(st.count(s)) continue;
re=t;
}
cout<<"Case #"<<k+<<": "<<re<<endl;
}
return ;
}