A——最少回文数

分析

显然由题意可得，连续的重复字符回文数是最少的。
那对于 $n$ 可以均分给每一个字母，超出部分可以
从第一个字母累加其数量，这样就模拟出题意了。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define tep(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
typedef pair<int,int>P;
const int N=1e5+10;
int n,a[N];
string s="aeiou";
void solve()
{
    cin>>n;
    rep(i,0,5)a[i]=(n/5);
    rep(i,0,n%5)a[i]++;
    rep(i,0,5)
    rep(j,0,a[i])
    cout<<s[i];
    cout<<endl; 
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

jly代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define tep(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
typedef pair<int,int>P;
const int N=1e5+10;
int n;
void solve()
{
    cin>>n;
    string s="aeiou";
    string ans;
    rep(i,0,5)
    {
        int x=n/(5-i);
        ans+=string(x,s[i]);//将x个数量的字符加到ans中
        n-=x;
    }
    cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

分析：

这个代码，是直接去分配每个字符应该出现的次数，关键在循环中。$x$ 变量是每个字符的数量，具体来说，对于第一个字符，其数量是平均分配的，然后将这 $x$ 个字符添加到答案上去，$n$ 相应的减少，之后 $5-i$ 自然是总字母数减少了，平均数计算也跟着变化。

拓展——求回文子序列的数量

ps：按理说，空字符串不是回文字符串的……

#include <iostream>
using namespace std;
int dp[200][200];

string str;

int solve(){
    int l=str.length();
    for(int j=0;j<l;++j){
        dp[j][j]=1;
        for(int i=j-1;i>=0;--i){
            if(str[i]==str[j]) dp[i][j]=dp[i+1][j]+dp[i][j-1]+1;
            else dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
        }
    }
    return dp[0][l-1];
}

int main(){
    while(cin>>str){
        cout<<solve()<<endl;
    }
    return 0;
}

B——老师追学生

分析：

分类讨论，没啥好说的，需要注意的是 $upper_bound$ 好久没用了都用错了，还有第三种情况的讨论中，按照题意老师是可以同时移动的，因此/2即可。

回顾：

upper_bound(v.begin(),v.end(),x)-v.begin()

//能找到，就返回第一个大于x的下标的地址，
//不能找到则返回最后一个元素的下一个位置的地址，即n+1。

代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define tep(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
typedef pair<int,int>P;
const int N=2e5+10;
int n,x,m,q; 
void solve()
{
 cin>>n>>m>>q;
 vector<int>a(m);
 for(auto &w:a)cin>>w;
 sort(a.begin(),a.end());
 rep(i,0,q)
 {
    cin>>x;
    int id=upper_bound(a.begin(),a.end(),x)-a.begin();
    if(!id)cout<<a[0]-1<<endl;
    else if(id==m)cout<<n-a[m-1]<<endl;
    else cout<<(a[id]-a[id-1])/2<<endl;//x就在其中，据题意老师可同时移动 
 }

}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

牛客——C

分析：

这道题做的时候一直想着用map或者结构体排序，实际上看好元素范围数组的下标完全可以使用。

代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m;
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    vector<int>rmin(n+1,n+1),rmax(n+1,0);
    vector<int>cmin(n+1,n+1),cmax(n+1,0);
    for(int i=0,x,y;i<m;i++)
    {
        cin>>x>>y;
        rmin[x]=min(rmin[x],y);
        rmax[x]=max(rmax[x],y);
        cmin[y]=min(cmin[y],x);
        cmax[y]=max(cmax[y],x);
    }
    //遍历坐标
    int ans=-1;
    for(int i=1;i<=n;i++)
    if(rmax[i])
    {
        int m1=rmax[i]-rmin[i];
        ans=max(ans,m1);
    }
    for(int i=1;i<=n;i++)
    if(cmax[i])
    {
        int m2=cmax[i]-cmin[i];
        ans=max(ans,m2);
    }
    cout<<ans;
        return 0;
}

牛客——D

分析：

这道题，看数据范围用 $dp$ 是会超时的，所以正解应该是贪心。既然题目说的是从 [1,n] 的数字都可以表示，不妨将数组排序，设定初始值为1开始贪，如果当前的数组值大于初始值，则一定会遗漏掉某个数字（因为初始值设为1不是数组的值造成的，所以遗漏掉的这个数字其实就是这个初始值），最后检查的时候看初始值是否大于 $n$ 即可（注意一定是大于n才行，原因同前）。

代码：

//dp会超时，贪心是正解
//贪心猜到的结论要会证明，[1,n]所有数字都可以表示，从最小的1开始，那数组也一定要排序，自己多想想！
//有意识，因为排过序，所以到ai>n便可以结束了，只有res>n这样才算表示完，为何是>n.因为一开始res值是1，加到n也并非只有数组内的数字出力
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,t=1;
void solve()
{
   int k=1;
    cin>>n;
    vector<int>a(n);
    for(auto &x:a)cin>>x;
    sort(a.begin(),a.end());
    for(auto &x:a)
    {
        if(x>k)break;
        k+=x;
        if(k>n)break;
    }
    if(k>n)cout<<"Cool!"<<endl;
    else cout<<k<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)solve();
    return 0;
}

01背包的超时代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
int a[N];
bool dp[N];
int n,t=1;
void solve()
{
    memset(dp,false,sizeof dp);
   int sum=0;
   cin>>n;
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
       sum+=a[i];
   }
   int V=min(sum,n);
    dp[0]=true;
   for(int i=0;i<n;i++)
   {
   for(int j=V;j>=a[i];j--)
   {
       dp[j]|=dp[j-a[i]];
   }
   }
   for(int i=1;i<=n;i++)
   {
       if(!dp[i])
       {
           cout<<i<<endl;
           return;
       }
   }
    cout<<"Cool!"<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)solve();
    return 0;
}