AtCoder Beginner Contest 369
A - 369
问题陈述
给你两个整数 $A$ 和 $B$ 。
有多少个整数 $x$ 满足以下条件？
- 条件：可以将三个整数 $A$ 、 $B$ 和 $x$ 按一定顺序排列，组成一个算术序列。
当且仅当 $q-p$ 等于 $r-q$ 时，三个整数 $p$ ， $q$ 和 $r$ 按此顺序排列的序列是算术序列。
实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5;
void solve()
{
int a,b;
cin>>a>>b;
if(a==b)
{
cout<<1<<endl;
return ;
}
if(abs(b-a)%2==0) cout<<3<<endl;
else cout<<2<<endl;
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
}
B - Piano 3
问题陈述
高桥有一架钢琴，上面有 $100$ 个排成一行的琴键。从左边开始的第 $i$ 个键叫做 $i$ 键。
他要逐个按下 $N$ 个键来演奏音乐。在按下 $i$ /th键时，他将用左手按下 $A_i$ 键，如果是 $S_i=$ ，则用右手按下 $A_i$ 键。如果按 $S_i=$ 则用左手，如果按 $S_i=$ 则用右手。R.
开始演奏前，他可以将双手放在任意键上，此时他的疲劳度为 0。在演奏过程中，如果他将一只手从键 $x$ 移动到键 $y$ ，疲劳度会增加 $|y-x|$ （反之，除移动双手外，疲劳度不会增加）。用手按下某个键时，该手必须放在该键上。
找出表演结束时可能的最低疲劳度。
实现
简单模拟即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5;
void solve()
{
int n;
cin>>n;
int l=0;
int r=0;
int ans=0;
for(int i=1;i<=n;i++)
{
int x;
char ch;
cin>>x>>ch;
if(ch=='L')
{
if(l==0) l=x;
else ans+=(abs(l-x)),l=x;
}
else
{
if(r==0) r=x;
else ans+=(abs(r-x)),r=x;
}
}
cout<<ans<<endl;
}
signed main()
{
int t=1;
//cin>>t;
while(t--)
{
solve();
}
}
C - Count Arithmetic Subarrays
问题陈述
给你一个由 $N$ 个正整数 $A=(A_1,A_2,\dots,A_N)$ 组成的序列。
求满足 $1\leq l\leq r\leq N$ 的一对整数 $(l,r)$ 中，子序列 $(A_l,A_{l+1},\dots,A_r)$ 构成算术级数的个数。
当且仅当存在一个 $d$ 使得 $x_{i+1}-x_i=d\ (1\leq i < |x|)$ 是算术级数时，序列 $(x_1,x_2,\dots,x_{|x|})$ 才是算术级数。特别地，长度为 $1$ 的序列总是算术级数。
实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5;
int a[N];
int b[N];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++)
{
b[i]=(a[i+1]-a[i]);
}
int r=1;
int ans=n;
for(int l=1;l<n;l++)
{
while(b[r+1]==b[l]&&r+1<n) r++;
int num=r-l+1;
//cout<<num<<' ';
ans+=(num)*(num+1)/2;
l=r;
}
cout<<ans<<endl;
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
}
D - Bonus EXP
问题陈述
高桥将依次遇到 $N$ 只怪物。 $i$ 个怪物 $(1\leq i\leq N)$ 的力量为 $A _ i$ 。
对于每只怪物，他都可以选择放走或打败它。
每次行动都会获得以下经验值：
- 如果放走怪物，他将获得 $0$ 点经验值。
- 如果他以 $X$ 的力量击败了怪物，则会获得 $X$ 点经验值。
如果击败的是偶数怪物(第 2 个、第 4 个……)，他将额外获得 $X$ 点经验值。
求他能从 $N$ 个怪物身上获得的经验值上限。
实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5;
int a[N];
int b[N];
int dp[N][2][2];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][1][1]);
dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][1][0]);
dp[i][1][1]=max(dp[i-1][1][0],dp[i-1][0][0])+a[i];
if(i==1) continue;
dp[i][1][0]=max(dp[i-1][1][1],dp[i-1][0][1])+2*a[i];
}
cout<<max(dp[n][1][0],dp[n][1][1])<<endl;
}
signed main()
{
int t=1;
//cin>>t;
while(t--)
{
solve();
}
}
E - Sightseeing Tour
问题陈述
有 $N$ 个岛屿和 $M$ 座双向桥梁连接两个岛屿。这些岛屿和桥梁的编号分别为 $1$ 、 $2$ 、 $\ldots$ 、 $N$ 和 $1$ 、 $2$ 、 $\ldots$ 、 $M$ 。
大桥 $i$ 连接着岛屿 $U_i$ 和 $V_i$ ，从任一方向穿过大桥所需的时间为 $T_i$ 。
没有一座桥将一个岛屿与它自己连接起来，但是有可能两座岛屿被不止一座桥直接连接起来。
人们可以通过一些桥梁来往于任意两个岛屿之间。
给你 $Q$ 个问题，请逐一回答。 $i$ -th 查询如下：
给出了 $K_i$ 个不同的桥：桥 $B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}$ 。
求从岛屿 $1$ 到岛屿 $N$ 所需的最少时间，每座桥梁至少使用一次。
只考虑过桥的时间。
你可以以任何顺序和方向通过给定的桥梁。
实现
求n遍dijkstral算出各点间的最短路，接着通过全排列枚举必走k个不同桥的走法，要注意不止枚举桥的顺序，还要枚举从u到v还是从v到u，每架桥对应两种状态，因此用01表示，则共2的k次方种选法。
dist[i] [j]表示从上一次走的桥的出口在i，要走到这一次桥的入口j，当选择的是第一架桥时，从1号点出发，到达第x=1架桥的入口,下次循x=2时则要选择从x-1出发，走到x,表示为dist[b[x-1]] [b[x]],所以最后一架桥作为出口时，此时循环了x=k+1次，表示为dist[b[k]] [n]到达n号点
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3;
const int M=2e5+10;
int u[M],v[M],w[M];
int dist[N][N];
vector<int>e[M];
bool st[N][N];
int b[M];
typedef pair<int,int> PII;
void dijkstra(int root)
{
priority_queue<PII, vector<PII>, greater<PII>>heap;
dist[root][root]=0;
heap.push({0,root});
while(heap.size())
{
auto k=heap.top();
heap.pop();
int ver=k.second;
int distence=k.first;
if(st[root][ver]) continue;
st[root][ver]=1;
for(int i=0;i<e[ver].size();i++)
{
if(dist[root][e[ver][i]]>=distence+dist[ver][e[ver][i]])
{
dist[root][e[ver][i]]=distence+dist[ver][e[ver][i]];
heap.push({dist[root][e[ver][i]],e[ver][i]});
}
}
}
}
void solve()
{
int n,m;
cin>>n>>m;
memset(dist,127,sizeof(dist));
for(int i=1;i<=m;i++)
{
cin>>u[i]>>v[i]>>w[i];
if(!st[u[i]][v[i]])
{
st[u[i]][v[i]]=1;
st[v[i]][u[i]]=1;
e[u[i]].push_back(v[i]);
e[v[i]].push_back(u[i]);
}
dist[u[i]][v[i]]=min(dist[u[i]][v[i]],w[i]);
dist[v[i]][u[i]]=min(dist[v[i]][u[i]],w[i]);
}
memset(st,0,sizeof(st));
for(int i=1;i<=n;i++)
{
dijkstra(i);
}
int q;
cin>>q;
while(q--)
{
int k;
cin>>k;
for(int i=1;i<=k;i++) cin>>b[i];
sort(b+1,b+1+k);
int ans=1e12;
do
{
for(int j=0;j<1<<k;j++)
{
int cur=0;
for(int i=1;i<=k;i++)cur+=w[b[i]];
for(int i=1;i<=k+1;i++)cur+=dist[i==1?1:(j>>i-2)&1?v[b[i-1]]:u[b[i-1]]][i>k?n:(j>>i-1)&1?u[b[i]]:v[b[i]]];
ans=min(ans,cur);
}
} while (next_permutation(b+1,b+1+k));
cout<<ans<<endl;
}
}
signed main()
{
int t=1;
//cin>>t;
while(t--)
{
solve();
}
}
