游游的整数翻转

思路

倒过来输出前k位，然后再正着输出k位之后的数字。
设置一个变量 flag 来表示是否遇到过非 0 数字，如果遇到过则可以直接输出当前遍历的数字，否则就不输出，这样可以不输出前导零。不过如果数字为 0 则需要特判输出。

复杂度为 O(n) 

代码实现 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string t;
    int k;
    cin>>t>>k;
    int flag = 0;
    for(int i=k-1;i>=0;i--){
        if(t[i]!='0') flag = 1;
        if(flag) cout<<t[i];
    }
    for(int i=k;t[i];i++){
        if(t[i]!='0') flag = 1;
        if(flag) cout<<t[i];
    }
    if(!flag) cout<<0;
}

游游的排列统计

思路

dfs 枚举 所有的排列情况，然后统计有哪些排列满足条件即可。
复杂度为 O(n!*n)

代码实现 

#include <bits/stdc++.h>
using namespace std;

int n;
int cnt;
int op[100];
int st[100];

//判断素数
int isprime(int x)
{
    if(x<=2) return x==2;
    for(int i=2;i<=x/i;i++){
        if(x%i==0) return 0;
    }
    return 1;
}

void dfs(int u)
{
    if(u>n){
        for(int i=1;i<n;i++){
            int x = op[i] + op[i+1];
            //如果相邻和为素数则不满足条件,直接return
            if(isprime(x)) return;
        }
        cnt++;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            op[u] = i;
            st[i] = 1;
            dfs(u+1);
            st[i] = 0;
        }
    }
}

int main()
{
    cin>>n;
    dfs(1);
    cout<<cnt;
}

游游刷题

思路

将所有的数对 k 取模。
如果对 k 取模后为 0，则直接为 k 的倍数，直接占据一天。
否则，如果对 k 取模为 x ，那么需要找对 k 取模为 k-x 的数值搭配才能为 k 的倍数。
设 cnt_x 为对 k 取模为 x 的数的数量，其能对答案产生的贡献为 min(cnt_x,cnt_{k-x})，（要注意统计了 x 后不需要再统计 k-x 的贡献）
特判：如果 k-x = x ，那么此时的贡献为\lfloor \frac{cnt_x}{2} \rfloor。
时间复杂度为 O(nlog_n)

代码实现 

#include <bits/stdc++.h>
using namespace std;

#define int long long 

int n,k;
set<int>st;
map<int,int>cnt;

signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        cnt[x%k]++;
    }
    int ans = 0;
    for(auto it:cnt){
        if(it.first==0) continue;
        if(st.count(it.first)) continue;
        int x1 = it.first,x2 = (k-x1)%k;
        if(!cnt.count(x2)) continue;
        st.insert(x1),st.insert(x2); // 防止重复统计
        if(x1!=x2)ans += min(cnt[x1],cnt[x2]);
        else ans += cnt[x1]/2;
    }
    ans += cnt[0]; // 直接为k的倍数可以直接占据一天,贡献为cnt[0]
    cout<<ans;
}

游游买商品

思路

感觉是类似背包然后分状态讨论的动态规划。
f_{i,j,0} 表示在前 i 个商品中选择，不买第 i 个商品能取得的最大喜爱度总和。
f_{i,j,1} 表示在前 i 个商品中选择，原价买第 i 个商品能取的的最大喜爱度总和。
f_{i,j,2} 表示在前 i 个商品中选择，半价买第 i 个商品能取得的最大喜爱度总和。

状态转移

f_{i,j,0} = max(f_{i-1,j,0/1/2})
f_{i,j,1} = max(f_{i-1,j-a_i,0},f_{i-1,j-a_i,1},f_{i-1,j-a_i,2}) + b_i (j \ge a_i)
f_{i,j,2} = f_{i-1,j-\frac{a_i}{2},1} + b_i (j \ge \frac{a_i}{2})

时间复杂度为 O(n*m)，空间复杂度可以通过滚动数组优化到 O(m)

代码实现 

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3+5;

#define int long long 

int n,m;
int a[N],b[N];
int f[N][N][3];
// f[i][j][0] = f[i-1][j][0/1/2]
// f[i][j][1] = f[i-1][j-ai][0/1/2] + bi
// f[i][j][2] = f[i-1][j-ai/2][1] + bi

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    
    for(int i=0;i<=m;i++){
        f[0][i][0] = f[0][i][1] = -1e18;
    }
    f[0][0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j][0] = max(max(0ll,f[i-1][j][0]),max(f[i-1][j][1],f[i-1][j][2]));
            f[i][j][1] = -1e18;
            if(j>=a[i]){
                f[i][j][1] = max(f[i-1][j-a[i]][0],max(f[i-1][j-a[i]][1],f[i-1][j-a[i]][2])) + b[i];
            }
            f[i][j][2] = -1e18;
            if(j>=a[i]/2){
                f[i][j][2] = f[i-1][j-a[i]/2][1] + b[i];
            }
        }
    }
    int ans = max(f[n][m][0],max(f[n][m][1],f[n][m][2]));
    cout<<ans;
}
//滚动数组优化
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3+5;

#define int long long 

int n,m;
int a[N],b[N],f[N][3];

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    
    int ans = 0;
    for(int i=0;i<=m;i++){
        f[i][0] = f[i][1] = f[i][2] = -1e18;
    }
    f[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            f[j][0] = max(f[j][0],max(f[j][1],f[j][2]));
            f[j][1] = -1e18;
            if(j>=a[i]){
                f[j][1] = max(f[j-a[i]][0],
                    max(f[j-a[i]][1],f[j-a[i]][2])) + b[i];
            }
            f[j][2] = -1e18;
            if(j>=a[i]/2){
                f[j][2] = f[j-a[i]/2][1] + b[i];
            }
            ans = max(max(ans,f[j][0]),max(f[j][1],f[j][2]));
        }
    }
    cout<<ans;
}