A 模拟 暴力
对每个合法的前缀，判断后缀是不是合法
int a[29];
void solve(){
string s;
cin>>s;
int t=-1;
if(s.size()==1){
return cout<<"NaN"<<endl,void();
}
for(int i=0;i<=27;i++) a[i]=0;
for(int i=0;i<s.size();i++){
a[s[i]-'a']++;
if(a[s[i]-'a']>1){
t=i;
break;
}else{
string ss=s.substr(i,s.size()-i);
string s1=ss;
reverse(ss.begin(),ss.end());
if(ss==s1){
return cout<<"HE"<<endl,void();
}
else continue;
}
}
if(t==-1)t=s.size()-1;
if(t==s.size()-1){
return cout<<"HE"<<endl,void();
}
string ss=s.substr(t,s.size()-t);
string s1=ss;
reverse(ss.begin(),ss.end());
if(ss==s1) cout<<"HE"<<endl;
else cout<<"NaN"<<endl;
}
B 思维 枚举
题意：每k个数一组，每小组升序排序后能让整个排序变成升序
思路：
- 若要满足题意，那么每个组的最大值要小于等于下一组的最小值，就是前缀最大值小于等于下一个数的后缀最小值，这就是组和组的边界
- 标记每一个边界位置，枚举k，找符合题意的k的个数
void solve()
{
int n;
cin>>n;
vector<int>a(n+1),pmax(n+1,0),smin(n+2,1e9);
forr(i,1,n){
cin>>a[i];
}
reforr(i,1,n){
smin[i]=min(smin[i+1],a[i]);
}
vector<int>rec(n+1,0);
forr(i,1,n){
pmax[i]=max(pmax[i-1],a[i]);
if(pmax[i]<=smin[i+1])rec[i]=1;
}
//nlogn
int ans=0;
forr(k,1,n){
ans++;
// cout<<k<<' ';
for(int i=k;i<=n;i+=k){//这里的复杂度是logn
if(rec[i]==0){
ans--;
// cout<<-1;
break;
}
}
// cout<<endl;
}
cout<<ans<<endl;
// forr(i,1,n)cout<<pmax[i]<<' ';
// cout<<endl;
// forr(i,1,n)cout<<smin[i]<<' ';
// cout<<endl;
}
/*
6
4 1 3 5 2 6
2
*/
E 三维dp 滚动数组
const int N=510,K=1e3+10;
string mp[N];
//空间优化 滚动数组
//要从上面一行转移过来，存两行，奇数行1偶数行0
int dp[2][N][K];
void solve()
{
int n,m,x;cin>>n>>m>>x;
forr(i,0,m){
forr(j,0,x){
dp[0][i][j]=dp[1][i][j]=0;
}
}
forr(i,1,n){
cin>>mp[i];
mp[i]='0'+mp[i];
}
forr(i,1,n){
forr(j,1,m){
forr(k,0,x){
if(mp[i][j]=='1')dp[i&1][j][k]=max(dp[i&1][j-1][k],dp[(i-1)&1][j][k])+1;
else if(mp[i][j]=='0') dp[i&1][j][k]=max(dp[i&1][j-1][k],dp[(i-1)&1][j][k]);
else{//?
if(k>=1)dp[i&1][j][k]=max(dp[i&1][j-1][k-1],dp[(i-1)&1][j][k-1])+1;//?尽量变成1
else dp[i&1][j][0]=max(dp[i&1][j-1][0],dp[(i-1)&1][j][0]);//没有k=-1的状态 原地tp
}
}
}
}
int ans=dp[n&1][m][0];
forr(i,1,x){
ans=max(ans,dp[n&1][m][i]);
}cout<<ans<<endl;
}
F 排序
题意：让min和max尽量小。排序后，min是相邻数之间的值差，max是隔k-2个数的两值之差
vp时对怎么找k-1个值差的最小值有点犯难，枚举判断必超时，一开始想写纯双指针，但是维护最小值太麻烦，于是选择了傻瓜式的multi_set
void solve()
{
int n,k;cin>>n>>k;
vector<int>a(n+1),mind(n),maxd(n);
forr(i,1,n)cin>>a[i];
sort(a.begin()+1,a.end());
forr(i,1,n-1){
mind[i]=a[i+1]-a[i];
// cout<<mind[i]<<' ';
}//cout<<endl;
int l=1,r=k-1;
multiset<int>s;
forr(i,1,k-1)s.insert(mind[i]);
int ans=1e18+100;
forr(i,1,n-k+1){
int minn=(*s.begin());
maxd[i]=a[i+k-1]-a[i];
ans=min(maxd[i]*minn,ans);
r++;
if(r>=n)break;
auto tp=s.lower_bound(mind[l]);//有序数组二分找要扔掉的值
s.erase(tp);
s.insert(mind[r]);
l++;
}
cout<<ans<<endl;
}
/*
13 7
1 1 4 5 1 4 1 9 1 9 8 1 0
4 2
114 514 1919 810
6 3
121 117 114 105 107 111
*/
H 贪心
题意：取的数个数相等，为k，让取的每个数四舍五入后尽量小/大
- min：尽量四舍
- 任何小数部分<0.5的数都可舍去，策略可以是每次分出 0.5 − δ 0.5-\delta 0.5−δ，分k-1个
- 剩下的数也要尽量小，取得 0.5 − δ 0.5-\delta 0.5−δ尽量大，那么 δ → 0 , 1 e 9 ⋅ δ → 0 \delta\rightarrow 0,1e9\cdot\delta \rightarrow 0 δ→0,1e9⋅δ→0，无穷小忽略，就是每次分出0.5，分k-1次剩下的取round
- max：五入
- 能五入的最小是0.5，让剩下的一个数尽量大，其他k-1个数就得取0.5
void solve()
{
int n,k;cin>>n>>k;
double rst1=1.0*n-(k-1)*0.5;
int minn=round(rst1);
minn=max(minn,0ll);
double rst=1.0*n-(k-1)/2;
int maxn=round(rst)+k-1;
maxn=min(2*n,maxn);
cout<<minn<<' '<<maxn<<endl;
}
K 构造
题意：形成一个环，环之间的差值是质数
- 质数：2,3,5,7,11,13…大部分是奇数
- 枚举得到n<=4，输出-1
- 相邻奇/偶数之间的差是2，奇偶之间的差值是奇数，所以可以分奇偶进行构造
belike(n为偶数) 1,3,5,7,…,n-3,n-1,n,n-2,6,4,2 但是2和n-1放错了位置，重新放
2在5和7之间必然合法
n-1在n-4和n-6之间必然合法(差是3,5)
但是应该n-4!=7，并且n应该>6
而且n-1!=7，让5和7位置固定 - 枚举5~10的答案，更大的n分奇偶进行构造
void solve()
{
//分奇偶
int n;cin>>n;
if(n<=4)return cout<<-1<<endl,void();
switch (n)
{
case 5:
cout<<"4 1 3 5 2"<<endl;break;
case 6:
cout<<"4 6 1 3 5 2"<<endl;break;
case 7:
cout<<"4 6 1 3 5 7 2"<<endl;break;
case 8:
cout<<"4 6 8 1 3 5 7 2"<<endl;break;
case 9:
cout<<"4 9 6 8 1 3 5 7 2"<<endl;break;
case 10:
cout<<"4 9 6 8 1 3 10 5 7 2"<<endl;break;
case 11:
cout<<"4 9 6 11 8 1 3 10 5 7 2"<<endl;break;
default:{
vector<int>ans;
if(n&1){//奇数
for(int i=1;i<=n-2;i+=2){
ans.push_back(i);
if(i==5)ans.push_back(2);
if(i==n-6)ans.push_back(n-1);
}
ans.push_back(n);
for(int i=n-3;i>=4;i-=2){
ans.push_back(i);
}
}
else{//偶数
for(int i=4;i<=n-2;i+=2){
ans.push_back(i);
if(i==n-6)ans.push_back(n-1);
}
ans.push_back(n);
for(int i=n-3;i>=1;i-=2){
ans.push_back(i);
if(i==7)ans.push_back(2);
}
}
for(auto i:ans)cout<<i<<' ';
cout<<endl;
}
}
}