1. 除了第K个数全部打出来即可
int n;
int k;
void solve() {
cin>>n>>k;
for(int i=0;i<n;i++){
int x;
cin>>x;
if(i!=k-1) cout<<x<<" ";
}
cout<<endl;
} 2. 把所有长度小于等于K的子串排序找第K个即可。这样保证前K个字串一定被选择同时不会超时。
string s;
int k;
int n;
void solve() {
cin>>s>>k;
set<string> ss;
n = s.size();
for(int i=0;i<n;i++){
for(int j=1;j<=k&&i+j<=n;j++){
ss.insert(s.substr(i,j));
}
}
for(int i=1;i<k;i++){
ss.erase(ss.begin());
}
cout<<*ss.begin()<<endl;
} 3. 找到小于N的最大的99……9然后拆分即可（我模板用宏#define int long long，没贴进来） int n;
void solve() {
cin>>n;
int x = n;
int d = 0;
int ans = 0;
while(x>=10){
d *= 10;
d += 9;
x /= 10;
ans += 9;
}
int y = n-d;
while(y){
ans += y % 10;
y /= 10;
}
cout<<ans<<endl;
} 4. Top-down dp，dp[l][r]代表解决l到r区间的最小次数。按区间长度遍历，dp[l][r]初始化成(r-l+1)，因为可以对每个木板竖着刷一次。如果横着刷，我们刷arr[l]...arr[r]中最小的次，然后分割成小区间，求和。然后取两者最小值。 int n;
int arr[5001];
int dfs(int l, int r){
if(l==r){
if(arr[l]==0) return 0;
else return 1;
}
int ans = r-l+1;
int minl = INT_MAX;
for(int i=l;i<=r;i++){
minl = min(minl, arr[i]);
}
int ans1 = minl;
int curl = -1;
for(int i=l;i<=r;i++){
arr[i] -= minl;
if(arr[i] > 0){
if(i==0 || arr[i-1]==0){
curl = i;
}
if(i==r){
ans1 += dfs(curl, i);
}
}else{
if(i>0 && arr[i-1] > 0){
ans1 += dfs(curl, i-1);
}
}
}
return min(ans, ans1);
}
void solve() {
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<dfs(0,n-1)<<endl;
} 5. 二维DP。dp[i][j]代表区间i到j的答案。首先检查i到j是否是回文，如果是的话答案是1，如果不是的话遍历所有分割区间方法求和取最小值。 int n;
string s;
int dp[401][401];
int q;
bool check(int i, int j){
for(int k=0;k<(j-i+1)/2;k++){
if(s[i+k] != s[j-k]) return false;
}
return true;
}
void solve() {
cin>>s;
n = s.size();
memset(dp,0x3f,sizeof(dp));
for(int l=0;l<n;l++){
for(int i=0;i+l<n;i++){
int j = i+l;
if(check(i,j)) dp[i][j] = 1;
else{
for(int k=i+1;k<=j;k++){
dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k][j]);
}
}
}
}
cin>>q;
for(int i=0;i<q;i++){
int a,b;
cin>>a>>b;
cout<<dp[a-1][b-1]<<endl;
}
} 
全部评论
(13) 回帖