写在前面
排名：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
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/