Codeforces Round 957 (Div. 3) D，F

D. Test of Love

很容易想到dp，对于dp的转移方程也比较好写，当前点只能从当前点前面m个点转移过来，那么思考转移的条件，对于前面的点 $j$ ，如果 $j$ 是水并且 $i$ 和 $j$ 不相邻，那么不能进行转移，如果相邻，则可以转移，如果 $j$是木头，那么也可以进行转移。
同时要注意初始化的问题，因为0和n+1都是存在的点，所以不妨将其都设置为木头即可。

#include <bits/stdc++.h>

using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"



void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    string s;
    cin>>s;
    s="L"+s+"L";
    vector<int> dp(n+5,1e9);
    dp[0]=0;
    for(int i=1;i<=n+1;i++){
        if(s[i]=='C') continue;
        for(int j=1;j<=m;j++){
            if(i-j>=0){
                if(s[i-j]=='C') continue;
                if(j==1||s[i-j]=='L') dp[i]=min(dp[i],dp[i-j]+(s[i]=='W'));
            }
        }
    }
    if(dp[n+1]==1e9||dp[n+1]>k) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;

} 


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t=1;
    cin>>t;
    while(t--){
        solve();
    }
    system("pause");
    return 0;
}

F. Valuable Cards

很容易想到和因数方面的内容有关，我们使用set去存，因为去重的原因，再加上数据范围最多就只有1e5，所以次数必然不会很多，所以注意一些剪枝然后暴力跑即可。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
#define endl "\n"

bool st[N];

void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    set<int> se;
    int ans = 1;
    se.insert(1);
    for (int i = 1; i <= n; i++) {
        set<int> t = se;//这里使用set存，后续有一个交换操作，set的交换是O（1）的
        if (k % a[i] != 0) {
            continue;
        }
        for (int x : se) {
            ll tt = 1LL * x * a[i];
            if (k % tt == 0) {
                t.insert(tt);
            }
        }
        se.swap(t);
        if (*se.rbegin() == k) {
            ans++;
            se.clear();
            se.insert(1);
            se.insert(a[i]);
        }
    }
    cout << ans << "\n";
} 


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t=1;
    cin>>t;
    while(t--){
        solve();
    }
    system("pause");
    return 0;
}