[ABC369C] Count Arithmetic Subarrays
题意：
判断有多少个区间是等差数列（不能重排）。
\(1 \le n \times 10^5\)。
思路：
赛时看错题了，以为这个区间可以重排，卡了 8min，小丑了。
首先容易注意到，对于一个区间 \([l,r]\)，若其是等差数列，则这个区间的子区间 \([l',r']\) 肯定也是子序列，造成的贡献是 \(\frac{(r-l+1)(r-l+2)}{2}\)。
那么考虑求出所有极长等差区间，设 \(d_i = a_{i+1} - a_i\)，若 \(i\) 能加入 \(i-1\) 的等差区间，当且仅当 \(d_i = d_{i-1}\)；否则就要新开一个等差子区间。
注意最后答案要加 \(n-1\)。
时间复杂度为 \(O(N)\)。
完整代码：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(A) memset(A,0,sizeof(A))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N=2e5+6;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
ll n,s,ans;
ll a[N],d[N];
int main(){
n=read();
For(i,1,n)
a[i]=read();
For(i,1,n)
d[i]=a[i+1]-a[i];
For(i,1,n){
if(d[i]!=d[i-1]){
ans+=s*(s+1)/2;
s=1;
}
else
s++;
}
ans+=s*(s+1)/2;
write(ans+n-1);
return 0;
}
[ABC369D] Bonus EXP
题意：
有 \(n\) 个物品依次从你身边经过，第 \(i\) 个物品的贡献为 \(a_i\)。
若你选择的第 \(j\) 个物品是 \(i\)：
-
当 \(j\) 为偶数时：收益为 \(a_i \times 2\)。
-
否则收益为 \(a_i\)。
问最大收益。
\(1 \le n \times 10^5\)。
思路：
考虑动态规划算法。
注意到当前位置的取值只跟当前取的个数的奇偶性有关，则定义 \(dp_{i,0/1}\) 表示对于前 \(i\) 个物品取的物品个数对 \(2\) 取余的结果为 \(0/1\) 的最大权值，则状态转移方程为：
\[dp_{i,0} = \max(dp_{i-1,1} + 2a_i,dp_{i-1,0}) \]
\[dp_{i,1} = \max(dp_{i-1,1},dp_{i-1,0} + a_i) \]
最后的答案是 \(\max(dp_{n,0},dp_{n,1})\)，时间复杂度为 \(O(N)\)。
完整代码：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=2e5+10;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
ll n;
ll a[N],dp[N][2];
int main(){
n=read();
For(i,1,n)
a[i]=read();
dp[1][1]=a[1],dp[1][0]=0;
For(i,2,n){
dp[i][0]=max(dp[i-1][1]+a[i]*2,dp[i-1][0]);
dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
}
write(max(dp[n][0],dp[n][1]));
return 0;
}
[ABC369E] Sightseeing Tour
题意：
给定一个 \(n\) 个节点的无向图，共 \(q\) 次询问，每次给定 \(k\) 个必须经过的边，问从 \(1 \sim n\) 的最短路径是多少。
\(1 \le n \le 500,1 \le q \le 3000,1 \le k \le 5\)。
思路：
考虑先求出任意两点的最短路径 \(dis_{i,j}\)，因为 \(n \le 500\)，可以使用 Floyd 算法 \(n^3\) 跑出。
然后对于每组询问，必须要经过编号为 \(a_1,a_2,a_3,\cdots,a_k\) 的桥，定义编号为 \(i\) 的桥为 \((u_i,v_i,w_i)\)。
同时注意到 \(k \le 5\) 非常小，考虑全排列出依次经过哪些桥，同时爆搜是先到达这个桥的左端还是右端即可。
时间复杂度为 \(O(N^3 + QK!2^K)\)。
完整代码：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=505,M=2e5+10;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
ll n,m,q,k,x,y,w,ans;
ll a[N],p[N],A[M],B[M],W[M];
ll dis[N][N];
void dfs(ll pos,ll pre,ll sum){
if(sum>ans)
return ;
if(pos==k+1){
ans=min(ans,sum+dis[pre][n]);
return ;
}
dfs(pos+1,A[a[p[pos]]],sum+dis[pre][B[a[p[pos]]]]+W[a[p[pos]]]);
dfs(pos+1,B[a[p[pos]]],sum+dis[pre][A[a[p[pos]]]]+W[a[p[pos]]]);
}
int main(){
n=read(),m=read();
For(i,1,n){
For(j,1,n){
if(i==j)
continue;
dis[i][j]=1e18;
}
}
For(i,1,m){
x=read(),y=read(),w=read();
dis[x][y]=min(dis[x][y],w);
dis[y][x]=min(dis[y][x],w);
A[i]=x,B[i]=y,W[i]=w;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
q=read();
while(q--){
ans=1e18;
k=read();
For(i,1,k){
a[i]=read();
p[i]=i;
}
while(1){
dfs(1,1,0);
if(!next_permutation(p+1,p+k+1))
break;
}
write(ans);
putchar('\n');
}
return 0;
}
[ABC369F] Gather Coins
题意：
给定一个 \(h \times w\) 的棋牌，有 \(n\) 个位置上有一个棋子，其它位置没有棋子，人每次可以往下或往左走，问从 \((1,1)\) 走到 \((n,n)\) 能收集到的最多的棋子数量。
\(1 \le h,w \le 2 \times 10^5,1 \le n \le \min(hw-2,2 \times 10^5)\)。
思路：
考虑动态规划，令 \(dp_i\) 表示到达第 \(i\) 个棋子最大权值，则状态转移方程为：
\[dp_i = \max [x_j \le x_i] [y_j \le y_i ] dp_j + 1 \]
这是二维偏序优化动态规划问题，考虑先按 \(x\) 从小到大排序，若 \(x\) 相同则按 \(y\) 从小到大排序，那么这样对于 \(j < i\)，自然都满足 \(x_j \le x_i\)，则状态转移方程降了一维：
\[dp_i = \max [y_j \le y_i] dp_j +1 \]
相当于询问 \([1,y_i]\) 区间内的最大值，因为需要输出路径，所以我们还需要记录一下最大值的位置，使用线段树维护即可。
时间复杂度为 \(O(N \log N)\)。
完整代码：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=2e5+10;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
struct Node{
ll x,y;
bool operator<(const Node&rhs)const{
if(x^rhs.x)
return x<rhs.x;
return y<rhs.y;
}
}a[N];
struct St{
ll l,r;
ll Max,id;
}X[N<<2];
ll h,w,n,id,cnt,ans;
ll dp[N],pre[N];
string S[N];
void pushup(ll k){
X[k].Max=max(X[k<<1].Max,X[k<<1|1].Max);
if(X[k].Max==X[k<<1].Max)
X[k].id=X[k<<1].id;
else
X[k].id=X[k<<1|1].id;
}
void build(ll k,ll l,ll r){
X[k].l=l,X[k].r=r;
if(l==r)
return ;
ll mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void add(ll k,ll i,ll v,ll id){
if(X[k].l==i&&i==X[k].r){
if(v>X[k].Max){
X[k].Max=v;
X[k].id=id;
}
return ;
}
ll mid=(X[k].l+X[k].r)>>1;
if(i<=mid)
add(k<<1,i,v,id);
else
add(k<<1|1,i,v,id);
pushup(k);
}
pi query(ll k,ll l,ll r){
if(X[k].l==l&&r==X[k].r)
return {X[k].Max,X[k].id};
ll mid=(X[k].l+X[k].r)>>1;
if(r<=mid)
return query(k<<1,l,r);
else if(l>mid)
return query(k<<1|1,l,r);
else{
auto x=query(k<<1,l,mid),y=query(k<<1|1,mid+1,r);
pi ans;
ans.fi=max(x.fi,y.fi);
if(ans.fi==x.fi)
ans.se=x.se;
else
ans.se=y.se;
return ans;
}
}
int main(){
h=read(),w=read(),n=read();
a[0]={1,1};
a[n+1]={h,w};
For(i,1,n)
a[i]={read(),read()};
build(1,1,w);
sort(a+1,a+n+1);
dp[1]=ans=id=1;
add(1,a[1].y,1,1);
For(i,2,n){
auto t=query(1,1,a[i].y);
dp[i]=t.fi+1;
pre[i]=t.se;
add(1,a[i].y,dp[i],i);
if(dp[i]>ans){
ans=dp[i];
id=i;
}
}
pre[n+1]=id;
id=n+1;
while(1){
ll x=pre[id];
++cnt;
ll sx=a[x].x,sy=a[x].y,tx=a[id].x,ty=a[id].y;
For(i,1,tx-sx)
S[cnt]+='D';
For(i,1,ty-sy)
S[cnt]+='R';
id=x;
if(!x)
break;
}
write(ans);
putchar('\n');
_For(i,1,cnt)
for(auto c:S[i])
putchar(c);
return 0;
}
[ABC369G] As far as possible
题意：
给定一个 \(n\) 个节点且有边权的树，对于每个 \(k \in [1,n]\) 求：
- 选取 \(k\) 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。
\(1 \le n \le 2 \times 10^5\)。
思路：
明显有一个贪心的思路：
-
每次取叶子到根的路径权值和最大的。
-
清空该链上的点的点权。
模拟 \(n\) 次即可，但是复杂度不可取，考虑数据结构优化。
将叶子节点按 dfn 序从小到大编号，令 \(l_u,r_u\) 表示 \(u\) 子树内叶子节点的编号在 \([l_u,r_u]\) 间。
每次找到路径权值和最大的那个叶子节点，可以直接暴力跳父亲清空路径上的点，每次清空就是将区间 \([l_u,r_u]\) 内的叶子结点到根的权值和减去 \(w_u\)。
若遇到一个点已经被清空了，故该点到根节点路径上的点肯定也被清空了，就可以直接退出了；这样每个点做多只会清空一次。
考虑使用线段树维护上述操作，时间复杂度均摊为 \(O(N \log N)\)。
完整代码：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=2e5+10;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
struct Node{
ll l,r;
ll tag;
ll Max;
ll id;
}X[N<<2];
ll n,k,cnt,ans;
ll a[N],Ans[N],l[N],r[N],d[N],id[N],fa[N];
vector<pi> E[N];
map<pi,ll> F;
bool f[N];
void add(ll u,ll v,ll w){
E[u].push_back({v,w});
E[v].push_back({u,w});
}
void dfs(ll u,ll f){
l[u]=n,r[u]=1;
bool F=1;
for(auto t:E[u]){
ll v=t.fi,w=t.se;
if(v==f)
continue;
fa[v]=u;
d[v]=d[u]+w;
dfs(v,u);
l[u]=min(l[u],l[v]);
r[u]=max(r[u],r[v]);
F=0;
}
if(F){
id[++cnt]=u;
l[u]=r[u]=cnt;
a[cnt]=d[u];
}
}
void pushup(ll k){
X[k].Max=max(X[k<<1].Max,X[k<<1|1].Max);
if(X[k].Max==X[k<<1].Max)
X[k].id=X[k<<1].id;
else
X[k].id=X[k<<1|1].id;
}
void update(ll k,ll v){
X[k].Max+=v;
X[k].tag+=v;
}
void push_down(ll k){
if(X[k].tag){
update(k<<1,X[k].tag);
update(k<<1|1,X[k].tag);
X[k].tag=0;
}
}
void build(ll k,ll l,ll r){
X[k].l=l,X[k].r=r;
if(l==r){
X[k].Max=a[l];
X[k].id=l;
return ;
}
ll mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
void update(ll k,ll l,ll r,ll v){
if(X[k].l==l&&r==X[k].r){
update(k,v);
return ;
}
push_down(k);
ll mid=(X[k].l+X[k].r)>>1;
if(r<=mid)
update(k<<1,l,r,v);
else if(l>mid)
update(k<<1|1,l,r,v);
else{
update(k<<1,l,mid,v);
update(k<<1|1,mid+1,r,v);
}
pushup(k);
}
void solve(ll u){
while(!f[u]&&fa[u]){
f[u]=1;
update(1,l[u],r[u],-F[{u,fa[u]}]);
u=fa[u];
}
}
int main(){
n=read();
for(int u,v,w,i=1;i<n;i++){
u=read(),v=read(),w=read();
F[{u,v}]=F[{v,u}]=w;
add(u,v,w);
}
dfs(1,0);
build(1,1,cnt);
For(i,1,n){
if(X[1].Max>0)
ans+=X[1].Max;
if(X[1].Max>0)
solve(id[X[1].id]);
write(ans*2);
putchar('\n');
}
return 0;
}