[数据结构与算法]Acwing 第37场周赛

AcWing 4296. 合适数对

暴力枚举 $O(n^2)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,a,b;
int main()
{
    cin>>n>>a>>b;
    for(int i=0;i<=1000;i++){
        for(int j=0;j<=1000;j++){
            if(a*i+b*j==n){
                cout<<"YES"<<endl;
                cout<<i<<" "<<j<<endl;
                return 0;
            }
        }
    }
    cout<<"NO"<<endl;
}

AcWing 4297. 截断数组

给定一个数组，将数组从中间截断，得到三个子数组(可以为空)，让第一段和第三段的元素和相等， 求第一段元素和的最大值。
经典看了视频之后会了，然后再自己写就不会了
本质原因就是自己Hash思想不成熟。
数据范围: $1\le n\le 2e5,1\le d_i\le 10^9。$
这种截断类型的题目一定是枚举，枚举什么呢？可能枚举分界点或者是枚举元素和。
枚举分界点是 $O(n^2)$ 考虑枚举元素和。
使用前缀和线性优化，使用Hash。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int N = 2e5+10;

typedef long long ll;
int n;ll s[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        s[i]=s[i-1]+x;
    }
    unordered_set<ll>hash;
    hash.insert(s[1]);
    for(int i=2;i<=n;i++){
        ll tar=s[n]-s[i-1];
        if(hash.count(tar)){
            cout<<tar<<endl;
            return 0;
        }
        hash.insert(s[i]);
    }
    puts("0");
}

AcWing 4298. 搭档

经典的二分图最大匹配问题，匈牙利算法的时间复杂度是 $O(n?m)$ ，网络流的时间复杂度是 $O(n?\sqrt{m})$,如果使用网络流的话就是中间的所有点的容量都是1，S，T流向各个点的容量是 $\infty$ ，男生和女生拆点处理，跑个dinic。

/*
A: 10min
B: 20min
C: 30min
D: 40min
*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;
ll n,m,_;
int a[110],b[110];
int h[110],e[N],ne[N],idx;
bool st[110];//表示这个女生有没有被配对
int ans;
int match[110];//每个女生的男朋友的编号
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool find(int u){//男生u能否找到合适的对象。
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(st[j]){//如果女生已经有对象了，那么就跳过
			continue;
		}
		st[j]=1;
		
		if(!match[j]||find(match[j])){
			match[j]=u;
			//如果这个男生还是没有找到对象，但是发现可以去挖墙角
			return true;
		}
	}
	return false;
	
}

void solve(){
	mem(h,-1);
	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);
			}
		}
	}
	// cout<<idx<<endl;
	for(int i=1;i<=n;i++){
		memset(st,0,sizeof st);
		//如果当前男生可以找到一个女生配对
		if(find(i))ans++;
		
	}
	cout<<ans<<endl;
}

int main(){
	solve();
	return 0;
}