A
const int N=1000100;
int a[N];
signed main(){
int x,y;cin>>x>>y;
if(x==y)cout<<"1\n";
else if(x%2==y%2)cout<<"3\n";
else cout<<"2\n";
}
B
const int N=1000100;
int a[N];
signed main(){
int n;cin>>n;
int cnt=0;
VI l,r;
F(i,1,n){
int x;char o;cin>>x>>o;
if(o=='L')l.eb(x);else r.eb(x);
}
F(i,1,(int)l.size()-1)cnt+=abs(l[i]-l[i-1]);
F(i,1,(int)r.size()-1)cnt+=abs(r[i]-r[i-1]);
cout<<cnt<<'\n';
}
C
发现满足条件的合法连续子序列 \((L,R)\) 必然可以用 \(K\) 个二元组 \((A_1,B_1)\),\((A_2,B_2)\),\(\ldots\),\((A_k,B_k)\) 来表示,其中任意一个合法的连续子序列 \((L,R)\) 均满足 \(\exists\ i\in[1,k]\cap\textbf{N}_+\),\(A_i\le L\le R\le B_i\)。然后还可以发现 \(\forall\ i,j\in [1,K],\ i<j\),\(B_i-A_j\ {\color{red}{=}}\ 1\)。因此答案即为 \(-K+1+\sum\limits_{i=1}^K\frac{(B_i-A_i+1)(B_i-A_i)}{2}\),双指针滑动找出所有满足条件的 \((A_i,B_i)\) 二元组,时间复杂度为 \(O(n)\)。
const int N=1000100;
int a[N];
signed main(){
int n;cin>>n;
F(i,1,n)cin>>a[i];
int cnt=0;
int l=1,r=1;
while(l<=n&&r<=n){
while(r<=n&&(r-l<=1||a[r]-a[r-1]==a[r-1]-a[r-2]))++r;
--r;
int len=r-l+1;cnt+=len*(len+1)/2;
--cnt;
l=r;
if(r==n)break;
}
cout<<cnt+1<<'\n';
}
D
设 \(f_{i,j}\) 表示当前前 \(i\) 只怪物击败了 \(j\) 只怪物最大的贡献,可以发现 \(j\) 对答案的影响只和 \(j\bmod 2\) 的值有关系,因此设 \(f_{i,0/1}\) 表示当前前 \(i\) 只怪物击败了 \(j\) 只怪物的最大贡献,显然有:
- \(f_{i,0}=\max(f_{i-1,0},f_{i-1,1}+2a_i)\)。
- \(f_{i,1}=\max(f_{i-1,1},f_{i-1,0}+a_i)\)。
初始条件为 \(f_{0,0}=0\),\(f_{0,1}=-\infin\)。
时间复杂度为 \(O(n)\)。
const int N=1000100;
int a[N];
int f[N][2];
//f[i][j] 表示当前前 i 只怪物击败了 0/1 奇数/偶数怪物
signed main(){
int n;cin>>n;
F(i,1,n)cin>>a[i];
f[0][1]=-1e18;
F(i,1,n){
f[i][0]=f[i-1][0],f[i][1]=f[i-1][1];
f[i][0]=max({f[i][0],f[i-1][1]+a[i]+a[i]});
f[i][1]=max({f[i][1],f[i-1][0]+a[i]});
}
cout<<max({f[n][0],f[n][1]})<<'\n';
}
E
考虑先跑 \(n\) 遍 dijkstra 求出两两点之间的最短路,然后对于 \(Q\) 组询问,考虑枚举每一个桥梁的顺序,然后枚举每一个桥梁的走向,暴力计算对答案的贡献即可。时间复杂度为 \(O(能过)\)。
const int N=1000100;
VII z[N];
struct qwq{
int u,v,w;
};
struct no{
int u,d;
bool operator<(const no&r)const{
return d>r.d;
}
};
qwq ed[N];
int mp[2010][2010];
void dijk(int s){
priority_queue<no>q;
q.push({s,0});mp[s][s]=0;
while(q.size()){
auto t=q.top();q.pop();
if(mp[s][t.u]>=t.d)
for(auto &[g,w]:z[t.u])
if(mp[s][g]>mp[s][t.u]+w)q.push({g,mp[s][g]=mp[s][t.u]+w});
}
}
signed main(){
int n,m;cin>>n>>m;
F(i,1,m){
int u,v,w;cin>>u>>v>>w;
ed[i]={u,v,w};
addew(u,v,w);
addew(v,u,w);
}
memset(mp,1,sizeof mp);
F(i,1,2005)
dijk(i);
int q;cin>>q;
while(q--){
int k;cin>>k;
int x[10];F(i,0,k-1)cin>>x[i];
sort(x,x+k);
int mi=1e18;
do{
//枚举每一座桥是往哪个方向走的
F(i,0,(1ll<<k)-1){
int cost=0;
//x>>i&1==1 : 选择u[i]-->v[i]
//即 ed[x[i]].u-->x[i]+n-->ed[x[i]].v
//x>>i&1==0 : 选择v[i]-->u[i]
//即 ed[x[i]].v-->x[i]+n+n-->ed[x[i]].u
VI bridge;
F(j,0,k-1){
if(i>>j&1)bridge.eb(ed[x[j]].u),bridge.eb(ed[x[j]].v),cost+=ed[x[j]].w;
else bridge.eb(ed[x[j]].v),bridge.eb(ed[x[j]].u),cost+=ed[x[j]].w;
}
cost+=mp[1][bridge[0]]+mp[bridge.back()][n];
F(i,2,(int)bridge.size()-1){
cost+=mp[bridge[i-1]][bridge[i]];
++i;
if(cost>3e18)break;
}
mi=min(mi,cost);
}
}while(next_permutation(x,x+k));
cout<<mi<<'\n';
}
}
F
二维偏序套路的对 \(x\) 为第一关键字 \(y\) 为第二关键字均从小到大排序,则此时 \(x\) 对答案毫无贡献,只需要考虑 \(y\) 的贡献,变为 LIS 板子。因为要输出路径所以再设 \(g_i\) 表示以 \(i\) 结尾的最大答案是从 \(g_i\) 转移过来的,倒序遍历答案即可。时间复杂度为 \(O(n\log n)\) 瓶颈在于线段树维护最大值和最大值所处的位置。
const int N=600100;
PII z[N];
int f[N];
#define x first
#define y second
//可爱班花yhb天下第一可爱qwq
namespace yhb{
struct qwq{
int l,r,mx,id;
void init(int p){
l=r=p;mx=id=0;
}
}z[N<<2];
qwq operator+(const qwq&l,const qwq&r){
qwq t;
t.l=l.l,t.r=r.r;
if(l.mx<=r.mx)t.mx=r.mx,t.id=r.id;
else t.mx=l.mx,t.id=l.id;
return t;
}
void build(int l,int r,int rt){
if(l==r)
return z[rt].init(l);
int mid=l+r>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
z[rt]=z[rt<<1]+z[rt<<1|1];
}
void modify(int l,int r,int rt,int p,int v,int id){
if(l==r){
if(z[rt].mx<v){
z[rt].mx=v;
z[rt].id=id;
}
return;
}
int mid=l+r>>1;
if(p<=mid)modify(l,mid,rt<<1,p,v,id);
else modify(mid+1,r,rt<<1|1,p,v,id);
z[rt]=z[rt<<1]+z[rt<<1|1];
}
qwq query(int l,int r,int rt,int ll,int rr){
if(ll<=l&&r<=rr)
return z[rt];
int mid=l+r>>1;
if(ll<=mid&&mid<rr)
return query(l,mid,rt<<1,ll,rr)+query(mid+1,r,rt<<1|1,ll,rr);
if(ll<=mid)
return query(l,mid,rt<<1,ll,rr);
return query(mid+1,r,rt<<1|1,ll,rr);
}
}
#define ro 0,200001,1
int g[N];
signed main(){
set<PII>se;
int n,m,k;cin>>n>>m>>k;
F(i,1,k){
int x,y;cin>>x>>y;
se.insert({x,y});
z[i]={x,y};
}
sort(z+1,z+k+1);
f[0]=0;
yhb::build(ro);
F(i,1,k){
f[i]=1;
auto tk=yhb::query(ro,1,z[i].second);
f[i]=max(f[i],tk.mx+1);
g[i]=tk.id;
yhb::modify(ro,z[i].second,f[i],i);
}
cout<<*max_element(f+1,f+k+1)<<'\n';
VII pai;
pai.eb(1,1);
VII t;
int la=-1,mx=*max_element(f+1,f+k+1);
F(i,1,k)if(mx==f[i])la=i;
while(la){
t.eb(z[la]);
la=g[la];
}
reverse(rng(t));
for(auto &x:t)pai.eb(x);
pai.eb(n,m);
F(i,1,pai.size()-1){
int dx=pai[i].first-pai[i-1].first;
int dy=pai[i].second-pai[i-1].second;
F(i,0,dx-1)cout<<"D";
F(i,0,dy-1)cout<<"R";
}
cout<<'\n';
}
G
长剖板子。容易发现一定只会选不同的叶子结点才能对答案产生最大的贡献。因此暴力长剖设 \(g_i\) 表示从 \(Top_i\) 到 \(i\) 结点所有遍的权值的和,其中 \(Top_i\) 表示 \(i\) 所属长链的顶端元素编号。记录所有可能对答案产生贡献的叶子结点,把所有的叶子结点的 \(g_i\) 从大到小排序然后求一遍前缀和即可。时间复杂度为 \(O(n\log n)\),使用基数排序可以做到 \(O(n)\)。
const int N=600100;
VII z[N];
int a[N],vis[N],deg[N],son[N],val[N];
void dfs_(int u,int fa){
for(auto &[v,w]:z[u])
if(v!=fa){
a[v]=w;
dfs_(v,u);
}
}
void dfs(int u,int fa){
for(auto &[v,w]:z[u])
if(v!=fa){
dfs(v,u);
if(val[v]>val[son[u]])son[u]=v;
}
val[u]=val[son[u]]+a[u];
}
int g[N];
signed main(){
int n;cin>>n;
F(i,1,n-1){
int u,v,w;cin>>u>>v>>w;
Addew(u,v,w);
++deg[u],++deg[v];
}
dfs_(1,0);
dfs(1,0);
VI v;
F(i,1,n)vis[son[i]]=1;
F(i,1,n)if(!vis[i])v.eb(val[i]);
sort(rng(v),greater<int>());
int s=0;
F(i,0,n-1){
if(i<=min(761145141413ll,(int)v.size()-1))s+=v[i];
cout<<s*2<<'\n';
}
}
标签:AtCoder,const,Beginner,bridge,int,ed,cin,补题,mp
From: https://www.cnblogs.com/yhbqwq/p/18390900