AtCoder Beginner Contest 318

目录

A - Full Moon

B - Overlapping sheets

C - Blue Spring

D - General Weighted Max Matching

E - Sandwiches

F - Octopus

---

A - Full Moon

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll ;
const int maxv=4e6+5;
typedef pair<ll,ll> pll;void solve()
{int n,m,p;cin>>n>>m>>p;if(m>n) cout<<0<<endl;else {n-=m;int ans=n/p;cout<<ans+1<<endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

B - Overlapping sheets

一眼扫描线，感觉人都魔楞了

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll ;
const int maxv=4e6+5;
typedef pair<ll,ll> pll;int st[105][105];void solve()
{int n;cin>>n;for(int i=1;i<=n;i++){int a,b,c,d;cin>>a>>b>>c>>d;for(int l=a+1;l<=b;l++){for(int r=c+1;r<=d;r++){st[l][r]=1;}}}int cnt=0;for(int i=0;i<105;i++){for(int j=0;j<105;j++){if(st[i][j]) cnt++;}}cout<<cnt<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

C - Blue Spring

思路：贪心，考虑购票乘车票的代价和直接购票的代价即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll ;
const int maxv=4e6+5;
typedef pair<ll,ll> pll;int st[105][105];void solve()
{int n,d,p;cin>>n>>d>>p;vector<ll> a(n+5),s(n+5);for(int i=1;i<=n;i++) cin>>a[i];sort(a.begin()+1,a.begin()+1+n,greater<ll>());for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}ll ans=1e18;for(int i=1;i<=n;i++){ll t=(i+d-1)/d;ll v=t*p;if(v<s[i]){ans=min(ans,v+s[n]-s[i]);}}ans=min(ans,s[n]);cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

D - General Weighted Max Matching

思路：搜索，思路和全排列搜索比较类似。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll ;
const int maxv=4e6+5;
typedef pair<ll,ll> pll;int n;ll g[20][20];
int st[20];
ll res;
ll ans;
void dfs(int x)
{if(x>n){ans=max(ans,res);return ;}if(st[x]){dfs(x+1);return ;}for(int i=x+1;i<=n;i++){if(!st[i]&&!st[x]){st[i]=st[x]=1;res+=g[x][i];dfs(x+1);res-=g[x][i];st[i]=st[x]=0;}}dfs(x+1);
}void solve()
{//int n;cin>>n;for(int i=1;i<=n-1;i++){for(int j=i+1;j<=n;j++){int w;cin>>w;//cout<<i<<" "<<j<<" "<<w<<" "<<endl;g[i][j]=w;}}dfs(1);cout<<ans<<endl;}   int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

E - Sandwiches

思路：因为要求和相同，考虑,使用桶去记录每个相同数字的下标，然后对每个数字进行枚举中间量,对于中间量的枚举，如果我们对每个桶中的每个下标进行枚举，肯定会超时，考虑优化：我们发现，对于一个桶，我们计算到当前量j，那么其对答案的贡献为,s表示的个数，所以我们可以对这个前缀和再求一遍前缀和即可。

具体注释看代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll ;
const int maxv=4e6+5;
typedef pair<ll,ll> pll;
typedef array<ll,3> p3;
const int mod=1e9+7;vector<ll> mp[N];void solve()
{int n;cin>>n;ll res=0;vector<int> a(n+5);for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]].push_back(i);}for(int i=1;i<=n;i++){auto v=mp[i];vector<ll> b(v.size()+5),s(v.size()+5);for(int j=1;j<v.size();j++){int cur=v[j]-v[j-1]-1;b[j]=cur;//记录两个相同数之间的数字个数}for(int j=1;j<v.size();j++){s[j]=b[j]+s[j-1];//前缀和}vector<ll> ss(v.size()+5);for(int j=1;j<v.size();j++){ss[j]=ss[j-1]+s[j];//对前缀和再求一遍前缀和}int sz=v.size()-1;for(int j=0;j<v.size();j++){res+=ss[sz]-ss[j]-s[j]*(sz-j);//计算贡献}}cout<<res<<endl;}   int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

F - Octopus

思路：对于一个位置k，我们考虑其是否合法，贪心的去想，我们将坐标和k的绝对值按升序排序，若每一个能和排序后的一一对应（即其都在的那个区间内）。但因为k所能选的点的范围为1e18，我们不能去一一枚举，那么我们就考虑去寻找区间。

在寻找区间前，我们考虑当位于k时合法，位于k+1时不合法的情况，那么我们会发现仅有符合条件。

同样，我们考虑位于k时不合法，位于k+1合法的情况，仅有。符合条件。

所以我们一共会得到2*n*n个点，我们去检查每个点是否合法即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll ;
const int maxv=4e6+5;
typedef pair<ll,ll> pll;
typedef array<ll,3> p3;
const int mod=1e9+7;int n;
vector<ll> x(205),l(205);bool check(ll k)
{sort(x.begin()+1,x.begin()+1+n,[&](ll x,ll y){return abs(k-x)<abs(k-y);});for(int i=1;i<=n;i++){if(abs(k-x[i])>l[i]) return false;}return true;
}void solve()
{// int n;cin>>n;for(int i=1;i<=n;i++){cin>>x[i];}for(int i=1;i<=n;i++) cin>>l[i];vector<ll> s;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){s.push_back(x[i]+l[j]);s.push_back(x[i]-l[j]-1);}}sort(s.begin(),s.end());sort(l.begin()+1,l.begin()+1+n);ll ans=0;for(int i=1;i<s.size();i++){if(check(s[i])){ans+=s[i]-s[i-1];}}cout<<ans<<endl;}   int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}