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;}//nlognint ans=0;forr(k,1,n){ans++;// cout<<k<<' ';for(int i=k;i<=n;i+=k){//這里的復雜度是lognif(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;//?盡量變成1else 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 04 2114 514 1919 8106 3121 117 114 105 107 111
*/

H 貪心

題意：取的數個數相等，為k，讓取的每個數四舍五入后盡量小/大

• min：盡量四舍
  • 任何小數部分<0.5的數都可舍去，策略可以是每次分出$0.5?\delta$，分k-1個
  • 剩下的數也要盡量小，取得$0.5?\delta$盡量大，那么$\delta \to 0,1e9?\delta \to 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;}}
}