前言：

• 真 && 小白月赛

• 主要题解参考:

  • 小白赛出题人题解
  • 牛客竞赛官方视频讲解

A - 超级闪光牛可乐

思路：

• 输出一个字符串，它所代表的数之和大于x即可

以下是代码部分， 代码参考来源——牛客288141082号

#include<bits/stdc++.h>
using namespace std;
int n, m;
string s;
int main() {
	cin>>n>>m>>s;
	cout<<string(1000,s[0]);
    return 0;
}

B - 人列计算机

思路：

• 模拟判断即可

以下是代码部分

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

#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;

void solve()
{
    string s[5];
    int a, b;
    for(int i = 0; i < 5; i ++)
        getline(cin, s[i]);
    if(isdigit(s[1][0]) && isdigit(s[3][0]))
    {
        a = s[1][0] - '0', b = s[3][0] - '0';
        if(s[2][5] == '&')
            cout << (a&b) << endl;
        else
            cout << (a|b) << endl;
    }
    else
    {
        a = s[2][0] - '0';
        cout << (!a) << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

C - 时间管理大师

思路：

• 先把单位统一，分别存入-1， -3， -5的状态，后统一输出即可

以下是代码部分，代码参考来源——牛客288141082号

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

int i,j,k,n,m,t;
set<int> s;

int main(){
	cin>>t;
	while(t--){
		cin>>i>>j;
		k=i*60+j;
		s.insert(k-1);
		s.insert(k-3);
		s.insert(k-5);
	}
	cout<<s.size()<<endl;
	for(auto i:s){
		j = i/60; k=i%60;
		cout<<j<<' '<<k<<endl;
	}
}

D - 我不是大富翁

思路：

• 动态规划题
• 设
  • i 代表回合数
  • j 代表地块的序号
  • dp[i][j]代表是否可以被走到
• 可得状态转移方程
• （记得取模）
  • 第 轮的第 地块的状态由第 轮的第 状态转移过来
• 因为取模的时候会有 ， 所以题目设定的, 更改为 ~
  • 此操作对结果无影响

以下是代码部分, 代码参考来源——出题人题解

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


int main() {
    int n, m;
    cin >> n >> m;

    vector dp(m + 1, vector(n, false));
    dp[0][0] = true;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
      //取模，防止数组越界段错误
        x %= n;
      //状态转移
        for (int j = 0; j < n; j++)
            dp[i][j] = dp[i - 1][(j + x) % n] | dp[i - 1][(j - x + n) % n];
    }
    cout << (dp[m][0] ? "YES" : "NO") << "\n";
}

E - 多重映射

思路1：

• 逆向思考， 后面的操作受前面的操作影响
  • 也就是说，后面的操作会覆盖前面的操作，比如：操作为 and 。
  • 所以可以逆向存储，防止后面的被前面的覆盖掉
• 存储之后，遍历 输出即可。
• 注意重新更改 to[i] 的值，防止影响到下一轮的数据。
  • 需要注意的是：
  • 重新更改to[]中的值的时候不可以直接：

for(int i = 0; i < N; i ++) to[i] = i;

此方式会

• 所以逆转回to[]的值，可以使用参考代码里的方法，只初始化已经被改变的值
  • 此方法可有效减少循环次数

以下是代码部分，代码参考来源——ReservoirDog

• 写法1：

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

const int N = 1e6 + 10, M = 1e5 + 10;
//to[]处理映射关系, a[]储存最初的数据, u[], v[]储存操作
int to[N], a[M], u[M], v[M];

void solve()
{
    int n, m;
    cin >> n >> m;
    //输入
    for(int i = 0; i < n; i ++) cin >> a[i];
    //储存操作
    for(int i = 0; i < m; i ++)
        cin >> u[i] >> v[i];
    //逆向存储
    for(int i = m - 1; i >= 0; i --)
        to[u[i]] = to[v[i]];
    //正向对映
    for(int i = 0; i < n; i ++)
        cout << to[a[i]] << " \n"[i == n - 1];
    //处理to[]防止影响到下一组数据
    for(int i = m - 1; i >= 0; i --)
    {
        to[u[i]] = u[i];
        to[v[i]] = v[i];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    // 初始化对应关系
    for(int i = 0; i < N; i ++) to[i] = i;

    int t;
    cin >> t;
    while(t --)
        solve();

    return 0;
}

以下是代码部分，代码参考来源——出题人题解

• 写法2：

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

void solve()
{
    int n, m;
    cin >> n >> m;
    //创建数组
    vector<int> a(n), u(m), v(m);
    //相当于写法1中的to[]
    map<int, int> mp;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < m; i ++)
        cin >> u[i] >> v[i];
    for(int i = m - 1; i >= 0; i --)
    {
        //如果mp中的元素中有v[i]
        //映射串联起来
        if(mp.count(v[i])) mp[u[i]] = mp[v[i]];
        //否则，直接赋值
        else mp[u[i]] = v[i];
    }
    //如果mp[]中没有对映的映射，则为它本身
    // 否则输出对映的映射
    for(int i = 0; i < n; i ++)
        cout << (mp[a[i]] ? mp[a[i]] : a[i]) << " \n"[i == n - 1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t --)
        solve();

    return 0;
}

思路2：

• 启发式合并

以下是代码部分， 代码参考来源——出题人题解

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

//二维数组，第一维代表数值大小，第二维代表坐标
vector<vector<int>> dic(1E6 + 5);

void solve()
{
    int n, m;
    cin >> n >> m;
    //创建储存输入的数组
    vector<int> in(n), ans;
    for(int i = 0; i < n; i ++)
    {
        cin >> in[i];
        //输入的值存入ans中
        ans.push_back(in[i]);
        //把坐标存入二维数组dic中
        dic[in[i]].push_back(i);
    }

    for(int i = 0; i < m; i++)
    {
        int l, r;
        //输入操作
        cin >> l >> r;
        if(l == r) continue;
        //if，以及else语句用来减少程序运行时间
        //      insert（）时间复杂度为O(n)，n与后面的长度有关
        if(dic[l].size() < dic[r].size())
        {
            //l的坐标全部接入到r的尾部
            dic[r].insert(dic[r].end(), dic[l].begin(), dic[l].end());
            //删除l中的坐标
            dic[l].clear();
        }
        else
        {
            //r的坐标全部接入到l的尾部
            dic[l].insert(dic[l].end(), dic[r].begin(), dic[r].end());
            //删除r中的坐标
            dic[r].clear();
            //交换
            swap(dic[l], dic[r]);
        }
        ans.push_back(r);
    }
    for(int i : ans)
    {
        for(int j : dic[i])
            in[j] = i;
        dic[i].clear();
    }
    for(int i = 0; i < n; i ++)
        cout << in[i] << " n"[i == n - 1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t --)
        solve();

    return 0;
}

F - 现在是消消乐时间

建议：

• 直接观看出题人题解

思路：

• 对于这里的讲解，可以观看牛客官方视频

1. 容易发现，一个方块在被穿透时，仅仅只有两种穿透方法
2. 只需要枚举其中一个方块能否被两种方式的其中一种穿透即可

以下是代码部分，代码参考来源——出题人题解

• 1.过程优化的暴力搜索

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

const int N = 2e3 + 10;
bool vis[N][N][4];
//储存方向
vector<int> mx = {1, 1, -1, -1};
vector<int> my = {1, -1, 1, -1};
//储存输出结果
vector<string> str = {"UR", "UL", "DR", "DL"};
int n, m, d;

bool clac(int x, int y, int k)
{
    int sum = 0;
    //当这个状态被判断过时，直接退出，返回false
    while(!vis[x][y][k])
    {
        //光线走过
        vis[x][y][k] = true;
        //沿着方向模拟前进
        int dx = x + mx[k], dy = y + my[k];
        //判断时候到达矩形的顶角
        if ((dx < 0) + (n < dx) + (dy < 0) + (m < dy) == 2) break;
        //向下变向上
        if (dx < 0) k -= 2;
        //向上变向下
        else if (n < dx) k += 2;
        //向左变向右
        else if (dy < 0) k -= 1;
        //向右变向左
        else if (m < dy) k += 1;
        //只有当行序号大于d的时候，才开始真正消除方块
        sum += max(x, x + mx[k]) > d;
        //模拟光线的移动
        x += mx[k], y += my[k];
    }
    //如果相等，则代表全都遍历到了。
    return sum == (n - d) * m;
}

void solve()
{
    cin >> n >> m >> d;
    //i代表初始选择的行位置
    for(int i = 0; i <= n; i ++)
        //j代表初始选择的列位置
        for(int j = 0; j <= m; j ++)
            //k代表方向
            for(int k = 0; k <= 3; k ++)
            {
                //当返回false， 则跳过。
                if(!clac(i, j, k)) continue;
                cout << "YES\n";
                cout << i << ' ' << j << '\n';
                cout << str[k] << '\n';
                return ;
            }
    cout << "NO\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

以下是代码部分，代码参考来源——出题人题解

• 起点优化的暴力搜索

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

int n, m, d;
//判断是否合法
bool clac(int sx, int sy)
{
    vector vis(n + 1, vector(m + 1, false));
    int x = sx, y = sy;
    int dx = 1, dy = 1, cnt = 0;
    while(cnt++ <= n * m)
    {
        vis[x][y] = true;
        int bounce = 0;
        //没有越界
        if(x + dx < 0 || n < x + dx)
        {
            dx *= -1;
            bounce ++;
        }
        //没有越界
        if(y + dy < 0 || m < y + dy)
        {
            dy *= -1;
            bounce ++;
        }
        //代表到达了矩形的角落处
        if(bounce == 2) break;
        x += dx, y += dy;
    }
    bool flag = true;
    for (int i = d; i < n; i++)
        for (int j = 0; j < m; j++)
            //判断是否都遍历过了， 并且排除了越界的情况
            if (vis[i][j] + vis[i + 1][j] + vis[i][j + 1] + vis[i + 1][j + 1] < 2)
                flag = false;
    return flag;
}

void solve()
{
    cin >> n >> m >> d;
    //从左下角发射
    if (clac(0, 0)) cout << "YES\n0 0\nUR\n";
    //从右下角发射
    else if (clac(0, 1)) cout << "YES\n0 1\nUL\n";

    else cout << "NO\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

G - 三点不共线

• 建议观看：出题人题解

思路1：

图：

以下是代码部分，代码参考来源——出题人题解

• 平面几何 + 三角函数

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

const double PI = acos(-1);
//角度转弧度
double toArc(double x)
{
    return PI * x / 180;
}
//两点之间距离公式
double dis(double x1, double y1, double x2, double y2)
{
    double val = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return sqrt(val);
}

void solve()
{
    double x1, y1, x2, y2, alpha;
    //保留小数点后10位
    cout << fixed << setprecision(10);
    //输入
    cin >> x1 >> y1 >> x2 >> y2 >> alpha;
    //求 α/2 并转化为弧度
    alpha = toArc(alpha / 2);
    //判断H和G的位置关系
    double k = 0;
    if(x1 != x2)
        k = (y1 - y2) / (x1 - x2);
    //求AB线段的中垂线的垂点
    double xM = (x1 + x2) / 2;
    double yM = (y1 + y2) / 2;

    double angle = atan(abs(yM - y1) / abs(xM - x1));
    double line = dis(x1, y1, xM, yM);
    //此时line 代表MC线段
    line /= tan(alpha);
    if(k < 0)
        cout << xM + line * sin(angle) << ' ' << yM + line * cos(angle) << '\n';
    else
        cout << xM - line * sin(angle) << ' ' << yM + line * cos(angle) << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t --)
        solve();

    return 0;
}

思路2：

• 向量做法

以下是代码部分