题解:

Rudolf and the Ball Game

滚动数组确定上一次传球谁有可能拿球，这一次传球谁有可能拿球

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl "\n"
const int maxn=2e5+5;
#define PII pair<int,int>
signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m,x;
        cin>>n>>m>>x;
        vector<int>last(n);//上一次传球有哪些人有机会摸球
        vector<int>now(n);//这一次传球有哪些人有机会摸球
        //因为接下来是取模求位置 所以用0-(n-1) 表示位置
        x--;
        last[x]=1;
        for(int i=1;i<=m;i++){
            for(int j=0;j<n;j++){
                now[j]=0;
            }
            int dis;char op;
            cin>>dis>>op;
            if(op=='0'){
                //顺
                for(int j=0;j<n;j++){
                    if(last[j]==1){
                        now[(j+dis)%n]=1;
                    }
                }
            }
            else if(op=='1'){
                //逆
                for(int j=0;j<n;j++){
                    if(last[j]==1){
                        now[(j-dis+n)%n]=1;
                    }
                }
            }
            else{
                //不知道方向？
                for(int j=0;j<n;j++){
                    if(last[j]==1){
                        now[(j+dis)%n]=1;
                        now[(j-dis+n)%n]=1;
                    }
                }
            }
            last=now;
        }
        int cnt=0;
        for(int i=0;i<n;i++){
            if(now[i]==1)cnt++;
        }
        cout<<cnt<<endl;
        for(int i=0;i<n;i++)
        {
            if(now[i]==1){
                cout<<i+1<<" ";
            }
        }
        cout<<endl;
    }
}

Seraphim the Owl

考点动态规划，因为之后没时间来教这个了，所以提前讲一点。上一题也就动态规划思路，动态规划就是求解出上一个状态的最优，然后推出当前状态的最优。

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl "\n"
const int maxn=2e5+5;
#define PII pair<int,int>
int a[maxn],b[maxn];
int dp[maxn][2];
/*
记录走到i位置花费的最小代价
dp[i][0]代表第i个人我们选择用bi代价，dp[i][1]代表第i个人我们选择用ai代价

上一个状态 也就是dp[i+1][0]和dp[i+1][1]
当前状态也就是 dp[i][0]和dp[i][1]

考虑状态转移
dp[i][0]代表走到i位置 但是不与i做换位置的交易 就当是暂且走到i 的最小代价
dp[i][1]代表走到i位置 也就是与i做交换 的最小代价
那么dp[i][0]=min(dp[i+1][0],dp[i+1][1])+b[i]
暂且走到i位置的最小花费为 上一个状态的两种最小花费的最小值+b[i]
走到i位置的最小花费为     上一个状态的两种最小花费的最小值+a[i]
最终我们要在 1-m中找到 走到i位置的最小花费
*/
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];
        }
        dp[n+1][0]=0;
        dp[n+1][1]=0;
        for(int i=n;i>=1;i--){
            dp[i][0]=min(dp[i+1][1],dp[i+1][0])+b[i];
            dp[i][1]=min(dp[i+1][1],dp[i+1][0])+a[i];
        }
        int ans=1e15;
        for(int i=1;i<=m;i++){
            ans=min(ans,dp[i][1]);
        }
        cout<<ans<<endl;
    }
}

Fireworks

设T=LCM(a,b)那么两个装置会在T同时发射烟花，持续到m+1分钟。贪心的来说此时的m+1分钟能看到最多的烟花。样例3其实给到了隐藏提示，我们会在k*（LCM(a,b)+m），时刻看到最多的烟花,k是任意整数。
m/a代表装置一m时刻前发射的烟花数，还有一个是m时刻发射的 那么答案就是m/a+m/b+2;