感觉这场简单了一些。

小红的整数转换

如果 x y，显然无解；否则直接输出 即可。

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

int main()
{
    int T;
    cin>>T;
    while(T--){
        int x,y;
        cin>>x>>y;
        if(x>=y) cout<<"-1 -1\n";
        else cout<<"1 "<<y-x<<'\n';
    }
}

小红打O

观察一下可以发现分为三层，上面和下面两层是上下对称的，然后按图案的样式打印即可。

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

int main()
{
    int n;
    cin>>n;
    int m = 4*n;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=i;j++) cout<<'.';
        for(int j=1;j<=m-2*i;j++) cout<<'*';
        for(int j=1;j<=i;j++) cout<<'.';
        cout<<'\n';
    }
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=n;j++) cout<<'*';
        for(int j=1;j<=2*n;j++) cout<<'.';
        for(int j=1;j<=n;j++) cout<<'*';
        cout<<'\n';
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++) cout<<'.';
        for(int j=1;j<=m-2*i;j++) cout<<'*';
        for(int j=1;j<=i;j++) cout<<'.';
        cout<<'\n';
    }
}

小红的完全二叉树构造

这题猜了一个规律，按层奇偶交替放数一定有一种合法方案，如果放数时其中一种不够就只能放另一种。

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

const int N = 1e5+5;

int a[N];

int solve(int n,int op)
{
    queue<array<int,2>>q;
    q.push({0,1});
    vector<array<int,2>>arr;
    while(q.size()){
        auto it = q.front(); q.pop();
        arr.push_back(it);
        if(it[1]*2<=n) q.push({it[0]+1,it[1]*2});
        if(it[1]*2+1<=n) q.push({it[0]+1,it[1]*2+1});
    }
    sort(arr.begin(),arr.end(),greater<array<int,2>>());
    int x1 = 1,x2 = 2;
    for(int i=0;i<arr.size();i++){
        int j = i;
        while(j<arr.size() && arr[i][0]==arr[j][0]){
            if(!op){
                if(x1<=n) a[arr[j][1]] = x1,x1+=2;
                else a[arr[j][1]] = x2,x2 += 2;
            }else{
                if(x2<=n) a[arr[j][1]] = x2,x2+=2;
                else a[arr[j][1]] = x1,x1 += 2;
            }
            j++;
        }
        op = !op;
        i = j-1;
    }
  
    queue<int>pq;
    //第一次bfs判断是否合法
    pq.push(1);
    while(pq.size()){
        int t = pq.front(); pq.pop();
        if(t>1 && (a[t]*a[t/2])%2!=0){
            return 0;
        }
        if(t*2<=n) pq.push(t*2);
        if(t*2+1<=n) pq.push(t*2+1);
    }
    pq.push(1);
    //第二次bfs进行输出
    while(pq.size()){
        int t = pq.front(); pq.pop();
        cout<<a[t]<<' ';
        if(t*2<=n) pq.push(t*2);
        if(t*2+1<=n) pq.push(t*2+1);
    }
    return 1;
}

int main()
{
    int n;
    cin>>n;
    if(!solve(n,0)) solve(n,1);
}

小红的红蓝硬币

• 因为 的数据范围不大，所以直接考虑背包。
• 在背包的基础上多出一维表示当前含有的硬币颜色状态,表示没有,表示只有红色,表示只有蓝色,表示两种都有。
• 如果当前硬币为红色，则可以使得 转换到，转换到。
• 如果当前硬币为蓝色，则可以使得 转换到，转换到。
• 同时,都可以由上一层的同一状态转移而来。

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

const int N = 1e3+5,M = 1e4+5,mod = 1e9+7;

#define int long long

int n,m;
string str;
int f[M][4];
int g[M][4];
//滚动数组优化,否则会MLE!!!

signed main()
{
    cin>>n>>m;
    cin>>str;
    str = ' '+str;
    f[0][0] = 1;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        memcpy(g,f,sizeof(f));
        for(int j=0;j<=m;j++){
            if(j>=x){
                if(str[i]=='R'){
                    f[j][1] = (g[j-x][1] + g[j-x][0] + f[j][1])%mod;
                    f[j][3] = (g[j-x][3] + g[j-x][2] + f[j][3])%mod;
                }else{
                    f[j][2] = (g[j-x][2] + g[j-x][0] + f[j][2])%mod;
                    f[j][3] = (g[j-x][3] + g[j-x][1] + f[j][3])%mod;
                }
            }
        }
    }
    cout<<f[m][3];
}