题解与反思

做这套题最大的感触就是前几道题没有思路，题目问的都是最少或者至少操作几次，我会往贪心方面去想，怎样才能让操作次数最少，其实不然，题目的意思只是防止重复操作而已。。

班级活动

我们我编号分为两类：
a[i]，出现了一次，这个编号可以改或者不改。
a[i], 出现了两次，这两个编号已经符合题意了，不需要再修改。
a[i], 出现大于两次，这个编号的前两个不需要修改，后边剩下的cnt - 2 个一定要修改，因为之前的a[i]编号已经不能使用。
所以我们统计出现一次的编号数量sum1, 出现大于等于两次的编号-2，剩余的编号数sum2, sum1 和 sum2 都是要修改的。如果sum1 >= sum2, 我们可以先把，sum2 的改为和 sum1 中的编号配对，sum1 剩下的编号再两两配对， res += sum2 + (sum1 - sum2)/2; 如果sum2 >= sum1, 我们只需要把sum2 的编号与sum1中的编号配对，剩下的再改为其他的即可，res += sum2;

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

const int N = 1e5 + 10;
int st[N], sum[N];
vector<int> a;
signed main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        sum[x] ++;
    }
    int s1 = 0, s2 = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(sum[i] >= 2) s1 += sum[i] - 2;
        else s2 += sum[i];
    }
    if(s1 >= s2)
    {
        cout << s1 << endl;
    }
    else
    {
        cout << s1 + (s2 - s1) / 2 << endl;
    }
    return 0;
}

合并序列

因为最后的结果是两个序列一模一样，所以我们在遍历到两个数组不一样的时候，其中较小的那个数组一定要进行合并操作，使得和另一个数组相同。
所以我们可以用队列或者其他数据结构来实现这种操做。
看了一个大佬写的题解用的是前缀和 + 二分的思想，每遍历到前缀和不同的时候，我们就二分找一下，前缀和相同的在哪里，合并的次数就是l - i（j）;

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

const int N = 1e5 + 10;
int a[N], b[N];
int sum1[N], sum2[N];
signed main()
{

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i], sum1[i] = sum1[i - 1] + a[i];
    for(int i = 1; i <= m; i ++) cin >> b[i], sum2[i] = sum2[i - 1] + b[i];
    int res = 0;
    for(int i = 1, j = 1; i <= n && j <= m; )
    {
        //cout << sum1[i] << " " << sum2[j] << endl;
        if(sum1[i] == sum2[j])
        {
            i ++, j ++;
        }
        else if(sum1[i] > sum2[j])
        {
            //对sum2进行合并
            int x = sum1[i];
            int l = j, r = m;
            while(l < r)
            {
                int mid = (l + r) / 2;
                if(sum2[mid] >= x) r = mid;
                else l = mid + 1;
            }
            res += l - j;
            //cout << l << " " << j << endl;
            j = l;
            //res += j - i;
        }
        else
        {
            int l = i, r = n;
            int x = sum2[j];
            while(l < r)
            {
                int mid = (l + r) / 2;
                if(sum1[mid] >= x) r = mid;
                else l = mid + 1;
            }
            res += l - i;
            i = l;
        }
    }
    cout << res << endl;
    return 0;
}

数三角

直接暴力枚举任意三个点，判断能否组成合法的等腰三角形即可，可以拿20分。
我们发现枚举的有些点是没有意义的，对于某个点来说，要组成等腰三角形，那么另外两个点到它的距离应该是一样的，所以我们可以记录一下到每个点距离相同的点有哪些，然后从这些点里面选两个点，判断三点不在一条线上就可以构成合法的等腰三角形。
我们可以用一个map<int, vector> ma; doule是到这个点的距离为d，vetor存距离为d的点有哪些，然后我们可以从这里面选。
如何判断三点是否共线和，我们可以用向量的思想：AB = (x1,y1), CD = (x2,y2) 如果两者平行有，x1 * y2 = x2 * y1, 当有一个公共点是及共线。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2005;
// 存储每个点
struct node
{
    int x, y;

} p[N];
// 计算两个点距离的平方，开根号会影响进度，只要判断相等即可所以不开根号也没问题
int dist(int i, int j)
{
    int res = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) *(p[i].y - p[j].y);
    return res;
}
bool check(int i, int j, int k)
{
    //判断三点是否共线，向量交叉相乘
    int d1 = (p[j].x - p[i].x) * (p[k].y - p[i].y);
    int d2 = (p[k].x - p[i].x) * (p[j].y - p[i].y);
    if(d1 != d2) return true;
    return false;
}
signed main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> p[i].x >> p[i].y;
    }
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        map<int, vector<int>> mp;
        for(int j = 0; j < n; j ++)
        {
            if(i == j) continue;
            int d = dist(i, j);
            mp[d].push_back(j);
        }
        
        for(auto it : mp)
        {
            int n = it.second.size();
            auto v = it.second;
            for(int ii = 0; ii < n; ii ++)
            {
                for(int jj = ii + 1; jj < n; jj ++)
                {
                    //从vector中拿出两个点，和顶点判断一下是否共线
                    int pp1 = v[ii];
                    int pp2 = v[jj];
                    if(check(i, pp1, pp2)) res ++;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}

AB路线

刚开始以为就是一个简单的bfs(), 后来看了题解确实是bfs(), 但是不同的是，每个点可以重复访问，而不是访问一次就结束了，因为每个A或B要走k次，如果图中的A或B的数量小于k，那么我们肯定要重复走的。
重复走，我们应该限制不能走重复的路径，所以st[i][j][k]可以加一维，表示我们走到i，j，经过了几个重复的A或B，如果st[i][j][k], 之前已经出现过了，我们就不要在进行这种情况了，不然会重复计算这样路径肯定会更大。
我们在进行bfs()时候，嵌套了两层，其实就是我们用当前的结点更新完所有可到达的结点后，再把res++, 这样res 就是最后的答案。

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

struct node
{
    int x, y, step;
    //step,表示到达(x,y), 经过了几个连续的A或B
};
const int N = 1005;
int st[N][N][12];
int dx[] = {0,0, 1,-1};
int dy[] = {1,-1,0,0};
string s[N];
int res,n,m,k;
int bfs()
{
    queue<node> q;
    q.push({0, 0, 1});
    st[0][0][1] = 1;
    while(q.size())
    {
        int len = q.size();
        while(len --)
        {
            auto h = q.front();
            q.pop();
            int x = h.x, y = h.y, step = h.step;
            if(x == n - 1 && y == m - 1)
            {
                return res;
            }
            for(int i = 0; i < 4; i ++)
            {
                int nex = x + dx[i];
                int ney = y + dy[i];
                
                if(nex < 0 || ney < 0 || nex >= n || ney >= m) continue;//越界
                if(step < k)
                {
                    //连续的个数<k, 应该走一样的
                    if(s[nex][ney] == s[x][y] && st[nex][ney][step + 1] == 0)
                    {
                        st[nex][ney][step + 1] = 1;
                        q.push({nex, ney, step + 1});
                    }
                }
                else
                {
                    //连续的个数==k, 应该走不一样的
                    if(s[nex][ney] != s[x][y] && st[nex][ney][1] == 0)
                    {
                        st[nex][ney][1] = 1;
                        q.push({nex, ney, 1});
                    }
                }
            }
        }
        res ++;
    }
    return -1;
}
signed main()
{

    cin >> n >> m >> k;
    for(int i = 0; i < n; i ++)
    {
        cin >> s[i];
    }
    cout << bfs();
    return 0;
}

抓娃娃

直接暴力枚举每个线段时候被包含在区间之中，20分。
看了大佬的思路豁然开朗，因为题目里给了一个条件就是区间的长度一定大于等于线段的长度，所以就不会出现线段包含区间的情况了。
要求区间要包含线段至少二分之一，我们可以画一下符合条件的情况找一下规律：
我们发现，只要线段的终点在区间里面，就可以保证区间包含线段至少二分之一。
基于以上思想，我们可以用sum[i]，来表示在[1, i]里面包含多少个线段的终点，所以对于每个区间就是 res = sum[y] - sum[x - 1]。
算终点坐标的时候要除以2，为了避免精度损失，我们把都乘以2.

#include<bits/stdc++.h>
//#define int long long
#define LL __int128_t
using namespace std;
const int N = 2e6 + 10;
int a[N];
int sum[N], cnt[N];
//map<int, int> cnt;
//map<int, int> sum;
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0), cout.tie(0);
   int n, m;
   cin >> n >> m;
   for(int i = 1; i <= n; i ++)
   {
       int x, y;
       cin >> x >> y;
       a[i] = x + y;
       cnt[x + y] ++;
   }
   for(int i = 1; i <= 2e6; i ++)
   {
       sum[i] = sum[i - 1];
       if(cnt[i] > 0) sum[i] += cnt[i];
   }
   while(m --)
   {
       int x, y;
       cin >> x >> y;
       x *= 2, y *= 2;
       int res = sum[y] - sum[x - 1];
       cout << res << endl;
   }
   return 0;
}

第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 B 组

题解与反思

班级活动

合并序列

数三角

AB路线

抓娃娃