AcWing周赛37

写在前面

排名：141/1605
过题数：3/3 AK!
比赛时间是2.5，但是现在已经是2.13..噢不是，现在是2.14了（刚刚打王者去了哈哈哈），情人节快乐（bushi
这是第一次AcWing周赛AK，似乎也是我第一次打比赛AK？哈哈哈，其实第三题是个图论题，还是问了我的队友——曹·图论大师·佬，慢慢推推出来了一个结论，是个好题！
前两题wa了很多次，说是小细节吧，确实，比如第一题没有看到是“非负整数”，第二题是边界没考虑清楚，判断的条件应该是l<r-1
那就来看看我的总结吧

A.合适数对（签到）

题意

题目链接：AcWing 4296. 合适数对 - AcWing

给定三个正整数 $n,a,b$，请你找到两个非负整数 $x,y$，使得 $ax+by=n$ 成立。
数据范围：$1\leq n,a,b \leq 1000$

思路

签到题，直接枚举，注意是“非负整数”，所以要包括0的时候

代码

inline void Case_Test()
{
    cin>>n>>a>>b;
    for (int x=0;x<=1000;x++)
        for (int y=0;y<=1000;y++)
            if (a*x+b*y==n) {cout<<"YES\n"<<x<<" "<<y;return;}
    cout<<"NO";
}

B.截断数组（双指针/哈希+前缀和）

题意

题目链接：AcWing 4297. 截断数组 - AcWing
给你一个数组$d$，要求分为三段，可以为空，每段的和从左到右为$sum1,sum2,sum3$，要求是$sum1=sum3$，问这个值的最大值是多少
数据范围:$1≤n≤2×10^5$，$1≤d_i≤109$。

思路

1）贪心+双指针

一开始l=1,r=n，然后开始往中间扫，这么想，每次都维护sum1和sum3，如果sum1>sum3说明左边多了，那么右指针需要往左边移动，这样才能往二者相等靠，另外一边同理。只要相等就维护最大值即可.时间复杂度是$O(n)$
那注意我这里的边界一定是while(l<r-1)不然l=r-1那里会出错...
对了，这个题一定有解，当左右两边没有元素的时候，就是0

2）哈希方法：

我才发现y总的方法是hash+前缀和
直接枚举每一段的值看看之前有没有

代码

1）贪心+双指针

inline void Case_Test()
{
    cin>>n;
    if (n==1) {cout<<0;return;}
    for (int i=1;i<=n;i++)
    {
        cin>>d[i];
    }
    l=1;r=n;
    suma=d[l];
    sumc=d[r];
    ans=(suma==sumc)?suma:0;//初始值，这里好像也wa了一发，一开始处理好
    while (l<r-1)//这个条件！！注意！！
    {
        if (suma<sumc) suma+=d[++l];//l往右边移
        else sumc+=d[--r];//r往左边移
        if (suma==sumc) ans=suma;//维护ans
    }
    cout<<ans;
}

2）hash+前缀和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 200010;
int n;
LL s[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] + x;
    }
    unordered_set<LL> hash;
    hash.insert(s[1]);
    for (int i = 2; i <= n; i ++ )
    {
        LL s3 = s[n] - s[i - 1];
        if (hash.count(s3))
        {
            printf("%lld\n", s3);
            return 0;
        }
        hash.insert(s[i]);
    }
    puts("0");
    return 0;
}

/*作者：yxc
链接：https://www.acwing.com/activity/content/code/content/2513373/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

C.搭档（二分图/贪心+双指针）

题意

题目链接：AcWing 4298. 搭档 - AcWing
给出$n$个男孩，魅力值为$a_i$;$m$个女孩，魅力值为$b_i$，当魅力值相差不大于1的时候，我们就可以连起来组成搭档，问最多能组成多少对？

思路

1）匈牙利算法

这个不就是典型的匈牙利算法吗？两两匹配，问最大匹配数...直接套板子过了..但是我看到了y总代码..

2）贪心+双指针

魅力值双方直接sort，然后双指针扫一遍...如果能搭档，那就最好，不然就下一个，确实正确，从小到大排序之后...

代码

1）匈牙利算法

inline bool Hdfs(int x)
{
  for (int i=head[x];i;i=edge[i].next)
    {
      int y=edge[i].to;
      if (chw[y])
    {
        chw[y]=false;
      if (!match[y] || Hdfs(match[y]))
        {
          match[y]=x;
          return 1;
        }
    }
    }
  return 0;
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for (int i=1;i<=m;i++) cin>>b[i];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (Abs(a[i]-b[j])<=1) add(i,j);//建边
    for (int i=1;i<=n;i++)
    {
      memset(chw,1,sizeof(chw));
      if (Hdfs(i)) ans++;//套板子
    }
    printf("%d",ans);
}

2）贪心+双指针

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int a[N], b[N];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    cin >> m;
    for (int i = 0; i < m; i ++ ) cin >> b[i];
    sort(a, a + n);
    sort(b, b + m);
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        while (j < m && a[i] > b[j] + 1) j ++ ;
        if (j < m && a[i] >= b[j] - 1)
        {
            res ++ ;
            j ++ ;
        }
    }
    cout << res << endl;
    return 0;
}
/*作者：yxc
链接：https://www.acwing.com/activity/content/code/content/2513672/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/