AtCoder Beginner Contest 327 A-F

本文主要是介绍AtCoder Beginner Contest 327 A-F，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - ab

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"void solve()
{int n;cin>>n;string s;cin>>s;if(s.find("ab")!=-1||s.find("ba")!=-1){cout<<"Yes"<<endl;}else cout<<"No"<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;// cin>>t;while(t--){solve();}system("pause");return 0;
}

B - A^A

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"void solve()
{ll n;cin>>n;for(ll i=1;i<=64;i++){ll tar=1;int f=0;for(int j=1;j<=i;j++){tar=tar*i;if(tar>n){f=1;break;}}if(f==0&&tar==n){cout<<i<<endl;return ;}}cout<<-1<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;// cin>>t;while(t--){solve();}system("pause");return 0;
}

C - Number Place

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"int a[15][15];void solve()
{for(int i=1;i<=9;i++){for(int j=1;j<=9;j++) cin>>a[i][j];}for(int i=1;i<=9;i++){vector<int> st(15);for(int j=1;j<=9;j++){st[a[i][j]]=1;}for(int j=1;j<=9;j++){if(!st[j]){//cout<<i<<endl;cout<<"No"<<endl;return ;}}}for(int i=1;i<=9;i++){vector<int> st(15);for(int j=1;j<=9;j++){st[a[j][i]]=1;}for(int j=1;j<=9;j++){if(!st[j]){//cout<<i<<endl;cout<<"No"<<endl;return;}}}for(int i=1;i<=9;i+=3){for(int j=1;j<=9;j+=3){vector<int> st(15);for(int l=i;l<i+3;l++){for(int r=j;r<j+3;r++){st[a[l][r]]=1;}}for(int k=1;k<=9;k++){if(!st[k]){//cout<<i<<" "<<j<<endl;cout<<"No"<<endl;return ;}}}}cout<<"Yes"<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;// cin>>t;while(t--){solve();}system("pause");return 0;
}

D - Good Tuple Problem

二分图判定。
题读懂第一想法是并查集，但是好像只有两个矛盾对立的部分，想到二分图。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"vector<int> e[N];
vector<int> c(N);bool dfs(int x)
{for(auto u: e[x]){if(!c[u]){c[u]=3-c[x];if(!dfs(u)) return  false;}else{if(c[x]==c[u]) return false;}}return true;
}void solve()
{int n,m;cin>>n>>m;vector<int> a(m+5),b(m+5);for(int i=1;i<=m;i++){cin>>a[i];}for(int i=1;i<=m;i++) cin>>b[i];for(int i=1;i<=m;i++){int u=a[i],v=b[i];e[u].push_back(v);e[v].push_back(u);}for(int i=1;i<=n;i++){if(!c[i]){c[i]=1;if(!dfs(i)){//cout<<i<<endl;cout<<"No"<<endl;return ;}}}cout<<"Yes"<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;// cin>>t;while(t--){solve();}system("pause");return 0;
}

E - Maximize Rating

看了眼数据范围，一眼dp，但是题读错了，以为可以随意选。
言归正传，因为必须要按照给定的顺序继续选，再加上数据范围，很容易想到dp，考虑状态设计，对于每一个 k ,当其大小确定时，
$$R=\frac{{\sum }_{i=1}^k(0.9{)}^{k-i}{Q}_i}{{\sum }_{i=1}^k(0.9{)}^{k-i}}-\frac{1200}{\sqrt{k}}.$$
我们可以发现对于式子，只有
$$\sum _{i=1}^k(0.9{)}^{k-i}{Q}_i$$
该式子的值不为定值，所以考虑求出该式子的最值，现在即转化为了，我们在前 i 个数字中选出 j 个，让该式子的值最大，对于此说法很容易联想到背包，于是跑个背包然后枚举k即可。
具体看注释

#include <bits/stdc++.h>using namespace std;
const int N = 2e7 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"double dp[N];void solve()
{int n;cin>>n;vector<int> a(n+5);for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++) dp[i]=-1e9;//dp初始化，因为可能出现负数，所以要初始化为-1e9for(int i=1;i<=n;i++){//01背包for(int j=i;j>=1;j--){dp[j]=max(dp[j],dp[j-1]*0.9+a[i]);}}double ans=-0x3f3f3f3f;double dx=1;for(int i=1;i<=n;i++){//用01背包去更新答案，即枚举kans=max(ans,dp[i]/dx-1200/sqrt(i));dx=dx*0.9+1;}printf("%.10lf",ans);}int main()
{// ios::sync_with_stdio(0);// cin.tie(0);// cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

F - Apples

经典扫描线+二维偏序。
对于这种问题，对其中一维进行排序，然后使用数据结构去维护另一维。
对于此题，我们可以将时间看作一维，坐标看作另一维，该题就成了给定一个指定大小的矩形，问该矩形中最多存在多少点。
对于点$(x,y)$,我们令其为左下端点，很容易知道其右上端点为$(x+w,y+d)$,考虑这个点什么时候会产生贡献，若对其纵坐标进行排序，，我们可以想象此时有一条线从 y=0 ，开始向上进行扫描，则其在区间$[y,y+d)$会产生贡献，而其对应产生贡献的区间为$[x,x+w-1]$，所以很容易使用线段树去进行维护，对于在位置 y 的线段，其贡献为 1 ，对于位置在 y+d 的线段，其贡献为 -1，所以使用线段树进行区间修改和最大值查询即可。

#include <bits/stdc++.h>using namespace std;
const int N = 4e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"int n,d,w,cnt;struct node
{int l,r,w,v;
}b[N];struct seg
{ll l,r,sum,add;#define l(x) tr[x].l#define r(x) tr[x].r#define sum(x) tr[x].sum#define add(x) tr[x].add
}tr[N*4];void update(int p)
{sum(p)=max(sum(p*2),sum(p*2+1));
}void build(int p,int l,int r)
{if(l==r){tr[p]={l,r,0,0};return ;}l(p)=l,r(p)=r;int mid=(l+r)/2;build(p*2,l,mid);build(p*2+1,mid+1,r);update(p);
}void pushdown(int p)
{if(add(p)){sum(p*2)+=add(p);sum(p*2+1)+=add(p);add(p*2)+=add(p);add(p*2+1)+=add(p);add(p)=0;}
}void modify(int p,int l,int r,int tag)
{if(l<=l(p)&&r(p)<=r){add(p)+=tag;sum(p)+=tag;return ;}pushdown(p);int mid=(l(p)+r(p))/2;if(l<=mid) modify(p*2,l,r,tag);if(r>mid) modify(p*2+1,l,r,tag);update(p);}int query(int p,int l,int r)
{if(l<=l(p)&&r(p)<=r){//cout<<l<<" "<<r<<" "<<sum(p)<<endl;return sum(p);}pushdown(p);int mid=(l(p)+r(p))/2;int res=0;if(l<=mid) res=query(p*2,l,r);if(r>mid) res=max(res,query(p*2+1,l,r));return res;
}void solve()
{cin>>n>>d>>w;int len=0;for(int i=1;i<=n;i++){int c,l;cin>>c>>l;b[i].l=b[i+n].l=l;b[i].r=b[i+n].r=l+w-1;b[i].w=1;b[i].v=c;b[i+n].w=-1;b[i+n].v=c+d;len=max(len,l+w-1);}sort(b+1,b+n*2+1,[](node x,node y){if(x.v==y.v) return x.w<y.w;return x.v<y.v;});build(1,1,len);int ans=0;for(int i=1;i<=2*n;i++){auto [l,r,w,v]=b[i];modify(1,l,r,w);ans=max(ans,query(1,1,len));}cout<<ans<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

这篇关于AtCoder Beginner Contest 327 A-F的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---