AtCoder Beginner Contest 267
A - Saturday
Problem Statement
题意:问你给定的天到礼拜六还要几天。
思路:直接算。
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
if(s=="Monday")cout<<6-1<<endl;
else if(s=="Tuesday")cout<<6-2<<endl;
else if(s=="Wednesday")cout<<6-3<<endl;
else if(s=="Thursday")cout<<6-4<<endl;
else cout<<6-5<<endl;
return 0;
}
B - Split?
Problem Statement
emmm..藕是bd,看题意看了半天hh
题意:我们让相邻两个虚线构成一个柱子,柱子上订了别针,编号\(1\)到\(10\),告诉你每个钉子的是否被打掉的情况,问你是不是满足以下条件:
- 一号钉子被打掉
- 存在两个相邻的有钉子的柱子之间的钉子全被打掉。
Solution
思路:按题意模拟
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
string s;
set<char>v[N];
int main()
{
cin>>s;
s = "?"+s;
for(int i = 1;i<=10;i++)
{
if(i==7)v[1].insert(s[i]);
if(i==4)v[2].insert(s[i]);
if(i==8||i==2)v[3].insert(s[i]);
if(i==5||i==1)v[4].insert(s[i]);
if(i==9||i==3)v[5].insert(s[i]);
if(i==6)v[6].insert(s[i]);
else if(i==10)v[7].insert(s[i]);
}
if(s[1]=='1')
{
cout<<"No\n";
return 0;
}
// for(int i = 1;i<=7;i++)
// {
// for(auto x:v[i])
// cout<<x<<" ";
// cout<<endl;
// }
bool ok = false;
for(int i = 1;i<=7;i++)
{
for(int j = i+2;j<=7;j++)
{
ok = false;
//cout<<"i = "<<i<<" j ="<<j<<endl;
//cout<<v[i].count('1')<<" "<<v[j].count('1')<<endl;
if(v[i].count('1')&&v[j].count('1'))
{
ok = true;
for(int k = i+1;k<=j-1;k++)
{
if(v[k].count('1'))
{
//cout<<"k = "<<k<<endl;
ok = false;
}
}
if(ok)
{
cout<<"Yes\n";
return 0;
}
}
}
}
cout<<"No\n";
return 0;
}
C - Index × A(Continuous ver.)
Problem Statement
题意:给你一个长度为n的序列\(A\),对于一段连续\(A\)的找到最大长度为\(M\)的\(\sum_{i = 1}^{M}i\times Bi\)的值
Solution
思路:双指针+前缀和思想。
\(ps\)数组记录连续的\(M\)个的数的和。每次移动,对于新的长度为\(M\)的连续段,我们发现第一个数字会离开,我们要减去它,并且恰好是一倍的它,我们发现剩下的\(M-1\)个数是我们要的,但是倍数不对,我们应该从\(1\)开始乘,但现在变成了从\(2\)开始了,也是多了一倍,那么我们只需要对当前的\(ps\)减去\(ps[i-1]\)再加上\(M*(a[i+M-1])\)。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
ll n,m,ps[N],a[N];
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i = 1;i<=n;i++)
cin>>a[i];
for(int i = 1;i<=m;i++)
ps[1] += a[i];
for(int j = 2,i = 1;j<=n-m+1;j++,i++)
ps[j] = ps[j-1]+a[i+m]-a[i];
ll sum = 0;
for(int i = 1;i<=m;i++)
sum+=a[i]*i;
ll ans = sum;
for(int i = 2;i<=n-m+1;i++)
{
sum -= ps[i-1];
sum += a[i+m-1]*m;
ans = max(ans,sum);
}
cout<<ans<<endl;
return 0;
}
D - Index × A(Not Continuous ver.)
Problem Statement
题意:和上题一样,不过不要求取连续的\(A\)作为\(B\).
Solution
思路:DP。01背包,价值是\(a[i]*j\)
\(dp[i][j]\)表示前\(i\)个选了\(j\)个的最大价值。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2100;
const ll inf = 1e18;
ll a[N],dp[N][N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 0;i<n;i++)cin>>a[i];
for(int i = 0;i<n+10;i++)
for(int j = 0;j<m+10;j++)
dp[i][j] = -inf;
dp[0][0] = 0;
for(int i = 0;i<n;i++)
{
for(int j = 0;j<=m;j++)
{
dp[i+1][j] = max(dp[i][j],dp[i][j-1]+a[i]*j);
}
}
cout<<dp[n][m]<<endl;
}
E - Erasing Vertices 2
Problem Statement
题意:给你一个\(N\)个点\(M\)条边的简单无向图。每个点\(i\)有一个正整数\(Ai\)写在上面。
你将重复以下操作\(N\)次:
选择一个还没被选过的点\(x\),删除\(x\)和与\(x\)直接相连的边,代价是与\(x\)直接相连的点的权值和。问:把整张图删完,最大操作代价的最小值是多少?
Solution
思路:求最大值最小,又因为答案满足单调性,所以考虑二分答案。
\(check\)部分写法:
设最大代价是\(maxx\)
把权值和\(<=maxx\)的加入队列中,然后开始\(bfs\),遇到没被删的点,去除删掉的边,得到现在删掉所需代价,若\(<=maxx\)加入队列,直到队列为空。
因为我们要判断是不是把整个图删完了,最后判一下是不是全删了就行。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
ll n,m;
vector<ll>edge[N];
ll w[N],a[N],val[N];
bool vis[N];
queue<ll>q;
bool judge(ll maxx)
{
ll cnt = 0;
for(int i = 1;i<=n;i++)w[i] = val[i],vis[i] = false;
for(int i = 1;i<=n;i++)
{
if(w[i]<=maxx)
q.push(i),++cnt,vis[i] = true;
}
while(!q.empty())
{
ll x = q.front();
q.pop();
for(auto y:edge[x])
{
if(!vis[y])
{
w[y]-=a[x];
if(w[y]<=maxx)
q.push(y),++cnt,vis[y] = true;
}
}
}
return cnt == n;
}
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;i++)
cin>>a[i];
for(int i = 1;i<=m;i++)
{
int x,y;
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
val[x] += a[y],val[y]+=a[x];
}
ll l = 0,r = 1e18;
while(l<=r)
{
ll mid = (l+r)>>1;
if(judge(mid))r = mid-1;
else l = mid+1;
}
cout<<r+1<<endl;
return 0;
}
- Beginner AtCoder Contest ABCDE 267beginner atcoder contest abcde beginner atcoder contest 267 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315