蓝桥杯选拔

2024-04-04 09:41:59

蓝桥杯选拔

1.三元一次方程组

三重for循环枚举即可

2.完美的字符串

这是一道dp题，设状态dp[i]为长度为i的完美字符串，所以有：

如果第i个位置选择放Y,则第i-1个位置可以任意放 ( dp[i-1] )
如果第i个位置选择放X,则第i-1个位置只能放X,同理，则第i-2个位置可以任意放

所以状态转移方程：dp[i]=dp[i-1]+dp[i-2].

3.字符串分类

STL大法，将每个字符串放入的集合set里,然后输出集合的大小即可。

4.纸牌游戏

贪心，要这样想，如果你们进行了m个回合，这m个回合你都赢了，且第i回合你出的牌为b1,b2,bm,你的挚友出的牌为a1,a2,am,则有你的得分(b1+b2+,+bm)-(a1+a2+,+am);所以你要最大化尽可能增大(b1+b2+,+bm)的同时要尽可能减小(a1+a2+,+am)。要如何实现这种贪心，只需要将b的逆序和a的正序比较即可。
核心代码：

	sort(a+1,a+1+n);
    sort(b+1,b+1+n,cmp);		//cmp是逆序比较函数
    long long num=0;
    for (int i=1;i<=n;i++)
    {
        if (b[i]>a[i])
        {
            ans+=b[i]-a[i];
        }
    }
    cout<<ans<<endl;

这道题请大家认真分析其贪心思想，我在写这道题解时便忽然怀疑这种解法是错误的，不过后面也证明了其解法的正确性，我想会有人看到这种解法是会出现像我一样的疑惑，此时可以自己去证明一下。

5.跳马游戏

经典的bfs题型，如果是因为不熟悉bfs的实现而导致没能把这道题解出来，那还是能够理解，如果是想不到用bfs或不知道如何去bfs，那你此时就应该去学习一下bfs等相关知识了。
从起始位置一直bfs，如果能走到目标点，便可提前退出bfs，到达某一个点需要的能量是上一个点的能量+1.所以可以开一个数组记录马到达每个点消耗的能量。

int next1[8][2]= {{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};	//马能走的八个方向
struct point		//点
{
    int x,y;
} ;
queue<point>q;		//队列，用于bfs
int arr[405][405];	//记录每个点耗费的能量
q.push({a,b});
arr[a][b]=1;		//将初始位置消耗的能量置为1而不是0，这是一个小技巧，
					//因为bfs需要判断有没有走过重复的点，所以置一则可以避免再开一个数组去记录该点有没有被走过
					//因此，输出时需要输出arr[x][y]-1.
bool f=0;
while (!q.empty())
{
    point p=q.front();
    q.pop();
    for (int i=0; i<8; i++)
    {
        int nx=p.x+next1[i][0];
        int ny=p.y+next1[i][1];
        if (nx<1||nx>n||ny<1||ny>m)
            continue;
        if (arr[nx][ny])
            continue;
        q.push({nx,ny});
        arr[nx][ny]=arr[p.x][p.y]+1;
        if (nx==x&&ny==y)
        {
            f=1;
            break;
        }
    }
    if (f)
    break;
}
cout<<arr[x][y]-1<<endl;

对于没有学好bfs的同学，这个题解几乎天书（狗头保命）。接下来会再花时间讲解bfs和的dfs，自己也要抽时间学习，这个知识点是当前阶段最重要且易学的知识点之一。

6.XY对称日

这是道较为麻烦的模拟题，虽然题目叫做“对称日”，但其实是求回文日期。那么便可以遍历年份，依据年份得到一个日期，该日期是否合法。例如1234年，那么它对应的回文日期理论是12344321，显然这个时期不合法（没有1234年43月21号这个日期），则现在继续遍历直到找到一个合法的日期。而XY对称日则是增加了年份必须为XYXY形式（形如2020，2121，1212）的限定。
所以该题需要解决的问题便是根据年份求出回文日期，判断该日期是否合法。

7.Binary_LIS

因为数据范围的原因，所以不能用最长上升子序列来解（O（n^2）会超时）。当然OI赛制应该还是可以用这个解来骗一些分的（嘻嘻）。那么需要换一种思路，我们观察满足题意的子序列形式，一定为00…0011…11。前面一堆0加后面一堆1。那么我们便需要找到这个0和1的交界点。我们对0求前缀和和对1求后缀和，枚举交界点找出最大的那个。

8.卖箱人

作为压轴题，这道题确实有难度。这道题有兴趣的可以看我的代码自己琢磨一下。后面花时间我讲一下。

#include <iostream>
#include <algorithm>
using namespace std;
int dp[2505];
int main()
{
    int a[50];
    int n;
    int maxn=0;
    cin>>n;
    dp[0]=1;
    for (int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    int ans1=0,ans2=0;
    for (int i=1;i<=2500;i++)
    {
        bool f=false;
        for (int j=0;(j<n)&&(i-a[j]>=0);j++)
        {
            if (dp[i-a[j]]==1)
            {
                f=true;
                dp[i]=1;
                break;
            }
        }
        if (f)
        {
            ans2++;
            maxn=max(maxn,ans2);
        }
        else
        {
            ans1++;
            ans2=0;
        }
    }
    if (maxn<a[0])
    cout<<"INF"<<endl;
    else
    cout<<ans1<<endl;
    return 0;
}

码农公寓