2899. 上一个遍历的整数
感觉读题比较困难
class Solution {
public:
vector<int> lastVisitedIntegers(vector<string>& words) {
vector<int> res , a ;
for( int i = 0 , cnt = 0 , x ; i < words.size() ; i ++ ){
if( words[i] != "prev" ){
cnt = x = 0;
for( auto j : words[i] ) x = x * 10 + j - '0';
a.push_back(x);
} else {
cnt ++;
if( (int)a.size() - cnt < 0 ) res.push_back(-1);
else res.push_back( a[(int)a.size() - cnt] );
}
}
return res;
}
};
2900. 最长相邻不相等子序列
枚举一下第一位要不要，然后贪心选择即可
class Solution {
public:
vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) {
vector<int> a , b;
a.push_back(0);
for( int i = 1 ; i < n ; i ++ )
if( groups[i] != groups[ a.back() ] ) a.push_back(i);
if( 1 < n ) b.push_back(1);
for( int i = 2 ; i < n ; i ++ )
if( groups[i] != groups[ b.back() ] ) b.push_back(i);
if( a.size() < b.size() ) a.swap(b);
vector<string> res;
for( auto i : a )
res.push_back( words[i] );
return res;
}
};
2901. 最长相邻不相等子序列 II
\(O(n^2)\)的dp转移一下，然后记录转移过来的状态的前驱，然后还原回去
class Solution {
int dis( const string & a , const string &b ){
if( a.size() != b.size() ) return -1;
int cnt = 0;
for( int i = 0 ; i < a.size() ; i ++ )
cnt += a[i] != b[i];
return cnt;
}
public:
vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) {
vector<int> f(n , 1) , fa(n);
iota( fa.begin() , fa.end() , 0);
for( int i = 0 ; i < n ; i ++ ){
for( int j = 0 ; j < i ; j ++ ){
if( groups[i] == groups[j] or dis( words[i] , words[j] ) != 1 ) continue;
if( f[i] > f[j] + 1 ) continue;
f[i] = f[j] + 1 , fa[i] = j;
}
}
int it = max_element( f.begin() , f.end() ) - f.begin();
vector<string> res;
while( it != fa[it] ) res.push_back( words[it] ) , it = fa[it];
res.push_back( words[it] );
reverse( res.begin() , res.end() );
return res;
}
};
2902. 和带限制的子多重集合的数目
多重背包\(f[i][j]\)表示前\(i\)个物品购买价值总和为\(j\)的方案数。
class Solution {
const int mod = 1e9+7;
using vi = vector<int>;
public:
int countSubMultisets(vector<int>& nums, int l, int r) {
unordered_map<int,int> cnt;
int total = 0;
for( auto i : nums )
cnt[i] ++ , total += i;
if( l > total ) return 0;
r = min( r , total );
vi f(r + 1);
f[0] = cnt[0] + 1 , cnt.erase(0);
int sum = 0;
for( const auto &[ x , c ] : cnt ){
auto g = f;
sum = min(sum + x * c , r);
for( int i = x ; i <= sum ; i ++ ){
g[i] = ( g[i] + g[i - x ]) % mod;
if( i >= ( c + 1 ) * x )
g[i] = ( g[i] - f[i - (c+1) * x ] + mod ) % mod;
}
f.swap(g);
}
int res = 0;
for( int i = l ; i <= r ; i ++ )
res = (res + f[i]) % mod;
return res;
}
};