Problem
T1
遍历字符串，拿一个桶统计即可。
T2
当 \(x\) 为中位数时，我们应当尽量的让整个数列的和变小，然后直接在最后一个上加即可。
为了让整个数列有序，和最小的构造的数列应当是 \(0,0,\cdot \cdot \cdot,x,x,\cdot \cdot \cdot,x\)，此时的和应是 \(\lfloor \dfrac{n+1}{2} \rfloor \times x\)。
因为 \(x\) 的值具有单调性，于是我们二分 \(x\) 的值，取最大值即可。时间复杂度 \(O(n \log n)\)。
但是wssb，\(\lfloor \dfrac{n+1}{2} \rfloor \times x\) 显然是 \(=S\) 的，于是答案即为 \(\dfrac{S}{\lfloor \dfrac{n+1}{2} \rfloor}\)，时间复杂度 \(O(n)\)。
下面是考场二分代码。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,s;
signed main(){
//freopen("median.in","r",stdin);
//freopen("median.out","w",stdout);
cin>>t;
while(t--){
cin>>n>>s;
int l=-1,r=s+1;
while(l+1<r){
int mid=(l+r)>>1;
if((n/2+1)*mid<=s) l=mid;
else r=mid;
}
cout<<l<<'\n';
}
return 0;
}
T3
直接记忆化即可。
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,m;
int a[231],b[231];
namespace sol1{
void solve(){
int res=a[1]&b[1];
for(int i=2;i<=n;i++) res|=(a[i]&b[1]);
cout<<res;
}
}
namespace sol2{ //正解
int res=-1e9,tmp[231]={0},mem[531][531];
void dfs(int x,int s){
if(mem[x][s]) return;
mem[x][s]=1;
if(x==n+1){
res=max(res,s); return;
}
for(int i=1;i<=m;i++) dfs(x+1,s|(a[x]&b[i]));
}
void solve(){
dfs(1,0);
cout<<res;
}
}
signed main(){
//freopen("xor.in","r",stdin);
//freopen("xor.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
if(m==1) sol1::solve();
else sol2::solve();
return 0;
}
T4
状态：令 \(dp_i\) 表示买前 \(i\) 个商品的最小价格。
转移：
\[dp_i=\max(dp_{i-1}+a_i,dp_{i-k}+a_i \times 2) \]注意需要将 \(a_i\) 排序。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,nn,ans,ss,p,k;
int dp[200031];
int c[200031];
signed main(){
//freopen("shop.in","r",stdin);
//freopen("shop.out","w",stdout);
cin>>n>>p>>k;
for(int i=1;i<=n;i++) cin>>c[i];
sort(c+1,c+n+1);
for(int i=1;i<=n;i++){
dp[i]=dp[i-1]+c[i];
if(i>=k) dp[i]=min(dp[i],dp[i-k]+c[i]*2);
}
for(int i=n;i>=0;i--){
if(dp[i]<=p){ cout<<i; break; }
}
return 0;
}