做题记录
2026-06-06 14:04:43
发布于:浙江
P1198:
绿
期望耗时:20min
耗时:3h
实际耗时:15min 左右
做法:线段树,板板
代码:
//直接板子复制过来的,很多变量都是棍母不用管
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=800005;
int d,n,t,cnt;
vector<int> a(N);
struct node{
int lazy=0,data;
}tree[N];
int left_child(int now){//取左孩子,返回的是索引
return 2*now;
}int right_child(int now){//取右孩子
return 2*now+1;
}long long query(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点,左区间,右区间,所求区间的左右区间
if(ql>r or qr<l)return LLONG_MIN;
if(ql<=l and qr>=r)return tree[now].data;
int mid=l+(r-l)/2;
return max(query(left_child(now),l,mid,ql,qr),query(right_child(now),mid+1,r,ql,qr));
}void update(int now,int l,int r,int idx,int val){//单点更新
if(l==r){
tree[now].data=val;
return ;
}int mid=l+(r-l)/2;
if(idx<=mid){
update(left_child(now),l,mid,idx,val);
}else{
update(right_child(now),mid+1,r,idx,val);
}tree[now].data=max(tree[left_child(now)].data,tree[right_child(now)].data);
}
signed main(){
cin >> n >> d;
t=0,cnt=0;
for(int i=1;i<=n;i++){
char c;
int x;
cin >> c >> x;
if(c=='A'){
cnt++;
update(1,1,n,cnt,(x+t+d)%d);
}else{
t=query(1,1,n,cnt-x+1,cnt);
cout << t << endl;
}
}
return 0;
}
P1775
难度:黄
石子合并弱化,上课学的。直接贴代码
#include <cstdio>
const long long INF=0x3f3f3f3f;
#define enter putchar_unlocked('\n')
inline void read(long long&x){
x=0;
int f=1;
char ch=getchar_unlocked();;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar_unlocked();
}while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar_unlocked();;
}x*=f;
}
inline void write(long long x){
if(x<0){
putchar_unlocked('-');
x=-x;
}if(x>9)write(x/10);
putchar_unlocked(x%10+'0');
}
long long dp[1005][1005],n,a[1005],sum[1005];
long long min(long long a,long long b){
return a>b?b:a;
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
sum[i]=sum[i-1]+a[i];
dp[i][i]=0;
}for(int l=2;l<=n;l++){
for(int i=1,j=l;j<=n;i++,j++){
dp[i][j]=INF;
for(int k=i;k<j;k++){
long long next=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
dp[i][j]=min(dp[i][j],next);
}
}
}write(dp[1][n]);
return 0;
}
P1122
难度:黄
实际用时:1s(
帮 wcqk 调代码顺手 AC,这里贴 wcqk 代码😋😋😋
#include<bits/stdc++.h>
using namespace std;
int a[100010],n;
long long dp[100010];
vector<int> g[100010];
void dfs(int u,int fa){
dp[u]=a[u];
for(int v:g[u]){
if(v==fa)continue;
dfs(v,u);
dp[u]+=max(dp[v],0LL);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
long long maxx=INT_MIN;
for(int i=1;i<=n;i++){maxx=max(maxx,dp[i]);}
cout<<maxx;
}
P1880
石子合并强化版。
难度:绿
做法:
在弱化版的基础上再在后面加一圈,然后开两个 数组存最大值最小值,然后就没了。
#include <cstdio>
const long long INF=0x3f3f3f3f3f;
#define enter putchar_unlocked('\n')
inline void read(long long&x){
x=0;
int f=1;
char ch=getchar_unlocked();;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar_unlocked();
}while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar_unlocked();;
}x*=f;
}
inline void write(long long x){
if(x<0){
putchar_unlocked('-');
x=-x;
}if(x>9)write(x/10);
putchar_unlocked(x%10+'0');
}long long dp[1005][1005],n,a[1005],sum[1005],dp2[1005][1005];
long long min(long long a,long long b){
return a>b?b:a;
}long long max(long long a,long long b){
return a<b?b:a;
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
a[n+i]=a[i];
}int len=(n<<1)-1;
for(int i=1;i<=len;i++){
sum[i]=sum[i-1]+a[i];
}for(int l=2;l<=len;l++){
for(int i=1,j=l;j<=len;i++,j++){
dp[i][j]=INF;
for(int k=i;k<j;k++){
long long next=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
dp[i][j]=min(dp[i][j],next);
next=dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1];
dp2[i][j]=max(dp2[i][j],next);
}
}
}long long mn=INF,mx=-INF;
for(int i=1;i<=n;i++)mn=min(mn,dp[i][i+n-1]),mx=max(dp2[i][i+n-1],mx);
write(mn);
enter;
write(mx);
return 0;
}
P6136
难度:蓝
实际用时:10min
思路:
平衡树板子,就加了个强制在线,根据题意修改即可,不难,10min 杀穿,但是之前我 Treap 为啥老被炸。注意有些变量要开 long long。这里选择了速度较快的红黑树实现。
#include <cstdio>
const int INF=1000000000;
const bool red=1;
const bool black=0;
inline void readll(long long&x){x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}x*=f;}
inline void writell(long long x){if(x<0){putchar('-');x=-x;}if(x>9)writell(x/10);putchar(x%10+'0');}
inline void read(int&x){x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}x*=f;}
inline void write(int x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
template<typename T>
class Redblacktree{
private:
struct rbt{T key,cnt,siz;bool color;rbt*l,*r,*fa;}*root,*nil;
rbt* newnode(T key){
rbt*p=new rbt;
p->key=key,p->cnt=1,p->siz=1,p->color=red;
p->l=p->r=p->fa=nil;
return p;
}void pushup(rbt*u){
u->siz=u->cnt;
if(u->l!=nil)u->siz+=u->l->siz;
if(u->r!=nil)u->siz+=u->r->siz;
}void zig(rbt*u){
rbt*lc=u->l;
u->l=lc->r;
if(lc->r!=nil)lc->r->fa=u;
lc->fa=u->fa;
if(u->fa==nil)root=lc;
else if(u==u->fa->l)u->fa->l=lc;
else u->fa->r=lc;
lc->r=u,u->fa=lc;
pushup(u),pushup(lc);
}void zag(rbt*u){
rbt*rc=u->r;
u->r=rc->l;
if(rc->l!=nil)rc->l->fa=u;
rc->fa=u->fa;
if(u->fa==nil)root=rc;
else if(u==u->fa->l)u->fa->l=rc;
else u->fa->r=rc;
rc->l=u,u->fa=rc;
pushup(u),pushup(rc);
}void insertfix(rbt*x){
while(x->fa->color==red){
if(x->fa==x->fa->fa->l){
rbt*unc=x->fa->fa->r;
if(unc->color==red){
x->fa->color=black;
unc->color=black;
x->fa->fa->color=red;
x=x->fa->fa;
}else{
if(x==x->fa->r){
x=x->fa,zag(x);
}
x->fa->color=black;
x->fa->fa->color=red;
zig(x->fa->fa);
}
}else{
rbt*unc=x->fa->fa->l;
if(unc->color==red){
x->fa->color=black;
unc->color=black;
x->fa->fa->color=red;
x=x->fa->fa;
}else{
if(x==x->fa->l){
x=x->fa,zig(x);
}
x->fa->color=black;
x->fa->fa->color=red;
zag(x->fa->fa);
}
}
}root->color=black;
}void transplant(rbt*u,rbt*v){
if(u->fa==nil)root=v;
else if(u==u->fa->l)u->fa->l=v;
else u->fa->r=v;
v->fa=u->fa;
}rbt* findmin(rbt*u){
while(u->l!=nil)u=u->l;
return u;
}void delfix(rbt*x){
while(x!=root&&x->color==black){
if(x==x->fa->l){
rbt*bro=x->fa->r;
if(bro->color==red){
bro->color=black;
x->fa->color=red;
zag(x->fa);
bro=x->fa->r;
}
if(bro->l->color==black&&bro->r->color==black){
bro->color=red;
x=x->fa;
}else{
if(bro->r->color==black){
bro->l->color=black;
bro->color=red;
zig(bro);
bro=x->fa->r;
}
bro->color=x->fa->color;
x->fa->color=black;
bro->r->color=black;
zag(x->fa);
x=root;
}
}else{
rbt*bro=x->fa->l;
if(bro->color==red){
bro->color=black;
x->fa->color=red;
zig(x->fa);
bro=x->fa->l;
}
if(bro->r->color==black&&bro->l->color==black){
bro->color=red;
x=x->fa;
}else{
if(bro->l->color==black){
bro->r->color=black;
bro->color=red;
zag(bro);
bro=x->fa->l;
}
bro->color=x->fa->color;
x->fa->color=black;
bro->l->color=black;
zig(x->fa);
x=root;
}
}
}x->color=black;
}
public:
void init(){
nil=new rbt;
nil->color=black;
nil->l=nil->r=nil->fa=nil;
nil->cnt=nil->siz=0;
root=nil;
}void push(T key){
rbt*now=root,*last=nil;
while(now!=nil){
last=now;
if(key==now->key){
now->cnt++;
pushup(now);
rbt*cur=now;
while(cur->fa!=nil){
cur=cur->fa;
pushup(cur);
}return;
}else if(key<now->key)now=now->l;
else now=now->r;
}
now=newnode(key);
now->fa=last;
if(last==nil)root=now;
else if(key<last->key)last->l=now;
else last->r=now;
insertfix(now);
rbt*cur=now;
while(cur!=nil){
pushup(cur);
cur=cur->fa;
}
}void del(T key){
rbt*now=root;
while(now!=nil){
if(key==now->key)break;
else if(key<now->key)now=now->l;
else now=now->r;
}if(now==nil)return;
if(now->cnt>1){
now->cnt--;
pushup(now);
rbt*cur=now;
while(cur->fa!=nil){
cur=cur->fa;
pushup(cur);
}return;
}
rbt*y=now,*x;
bool ycol=y->color;
if(now->l==nil){
x=now->r;
transplant(now,now->r);
}else if(now->r==nil){
x=now->l;
transplant(now,now->l);
}else{
y=findmin(now->r),ycol=y->color,x=y->r;
if(y->fa==now)x->fa=y;
else{
transplant(y,y->r);
y->r=now->r,now->r->fa=y;
}
transplant(now,y);
y->l=now->l,now->l->fa=y,y->color=now->color;
}
delete now;
rbt*cur=x->fa;
while(cur!=nil){
pushup(cur);
cur=cur->fa;
}if(ycol==black)delfix(x);
}int getrank(T x){
rbt*u=root;
int res=0;
while(u!=nil){
if(x<u->key)u=u->l;
else if(x>u->key)res+=u->l->siz+u->cnt,u=u->r;
else{res+=u->l->siz;break;}
}
return res;
}T getkth(int k){
rbt*u=root;
while(u!=nil){
int ls=u->l->siz;
if(k<=ls)u=u->l;
else if(k<=ls+u->cnt)return u->key;
else k-=ls+u->cnt,u=u->r;
}
return 0;
}T getpre(T x){
rbt*u=root;
T res=-INF;
while(u!=nil){
if(u->key<x)res=u->key,u=u->r;
else u=u->l;
}
return res;
}T getsuc(T x){
rbt*u=root;
T res=INF;
while(u!=nil){
if(u->key>x)res=u->key,u=u->l;
else u=u->r;
}
return res;
}
};
int main() {
Redblacktree<int> tr;
tr.init();
int t,n;
read(n),read(t);
while(n--){
int x;
read(x);
tr.push(x);
}
long long last=0;
long long ans=0;
while(t--){
int op,x;
read(op),read(x);
x^=last;
if(op==1)tr.push(x);
if(op==2)tr.del(x);
if(op==3)ans^=(tr.getrank(x)+1),last=(tr.getrank(x)+1);
if(op==4)ans^=tr.getkth(x),last=tr.getkth(x);
if(op==5)ans^=tr.getpre(x),last=tr.getpre(x);
if(op==6)ans^=tr.getsuc(x),last=tr.getsuc(x);
}write(ans);
return 0;
}
还是跑了 9.5s,太慢了
P2820
刷到十倍经验看见的,MST 板子。
难度:黄
思路:边权总和减去 MST
实际用时:1min
#include <bits/stdc++.h>
using namespace std;
#define int long long
int sum=0;
const int N=2e5+5;
int n,m,ans=0,k;
struct node{
int u,v,w;
}sz[N];
bool cmp(node a,node b){
return a.w<b.w;
}void Kruskal(){
class FA{
private:
int fa[N],h[N];
public:
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(h[y]<h[x])swap(x,y);
if(h[x]==h[y])h[y]=h[x]+1;
fa[y]=x;
}void init(int n){
for(int i=1;i<=n;i++)fa[i]=i,h[i]=1;
}
};FA fa;
fa.init(n);
sort(sz****z+1+m,cmp);
for(int i=1;i<=m;i++){
int x=fa.find(sz[i].u),y=fa.find(sz[i].v);
if(x!=y){
ans+=sz[i].w;
fa.merge(x,y);
if(++k==n-1){
break;
}
}
}if(k<n-1)cout << "-1";
else cout << sum-ans;
}
signed main(){
cin >> n >> m;
for(int i=1;i<=m;i++){cin >> sz[i].u >> sz[i].v >> sz[i].w;sum+=sz[i].w;}
Kruskal();
return 0;
}
P1669
难度:黄
思路:
最大生成树
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,ans=0,k;
struct node{
int u,v,w;
}sz[N];
bool cmp(node a,node b){
return a.w>b.w;
}void Kruskal(){
class FA{
private:
int fa[N],h[N];
public:
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(h[y]<h[x])swap(x,y);
if(h[x]==h[y])h[y]=h[x]+1;
fa[y]=x;
}void init(int n){
for(int i=1;i<=n;i++)fa[i]=i,h[i]=1;
}
};FA fa;
fa.init(n);
sort(sz****z+1+m,cmp);
for(int i=1;i<=m;i++){
int x=fa.find(sz[i].u),y=fa.find(sz[i].v);
if(x!=y){
ans+=sz[i].w;
fa.merge(x,y);
if(++k==n-1){
break;
}
}
}if(k<n-1)cout << "-1";
else cout << ans;
}
signed main(){
cin >> n >> m;
for(int i=1;i<=m;i++)cin >> sz[i].u >> sz[i].v >> sz[i].w;
Kruskal();
return 0;
}
总结:
黄+=3
绿+=2
蓝++
我的 520 和线段树过。
字面意思,做了一个线段树,只写了一道题我就不管格式了。
思路:单点修改+建树+区间查询的维护最大值的线段树
代码:直接从区间和线段树改过来的,可读性为 ,但是相信这道题不放代码各位也能做对吧。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=4000005;
vector<int> a(N);
class segment_tree{
private:
struct node{
int lazy=0,data;
}tree[N];
int left_child(int now){//取左孩子,返回的是索引
return 2*now;
}int right_child(int now){//取右孩子
return 2*now+1;
}
public:
void build(int now,int l,int r){//递归建树
tree[now].lazy=0;//懒标记的初始化,后面会讲
if(l==r){//叶子节点
tree[now].data=a[l];
return ;
}int mid=l+(r-l)/2;
build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
tree[now].data=max(tree[left_child(now)].data,tree[right_child(now)].data);//赋值该节点为他的左右孩子节点值之和。
}
long long query_add(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点,左区间,右区间,所求区间的左右区间
if(ql>r or qr<l)return 0;
if(ql<=l and qr>=r)return tree[now].data;
int mid=l+(r-l)/2;
return max(query_add(left_child(now),l,mid,ql,qr),query_add(right_child(now),mid+1,r,ql,qr));
}
void update(int now,int l,int r,int idx,int val){//单点更新
if(l==r){
tree[now].data=max(tree[now].data,val);
return ;
}int mid=l+(r-l)/2;
if(idx<=mid){
update(left_child(now),l,mid,idx,val);
}else{
update(right_child(now),mid+1,r,idx,val);
}tree[now].data=max(tree[left_child(now)].data,tree[right_child(now)].data);
}
};
signed main(){
segment_tree Tree;
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++)cin >> a[i];
Tree.build(1,1,n);
while(m--){
char c;
int x,y;
cin >> c >> x >> y;
if(c=='Q')cout << Tree.query_add(1,1,n,x,y) << "\n";
else Tree.update(1,1,n,x,y);
}
return 0;
}
P16597
难度:诈骗题
直接升序排序即可。
代码不放了。
P1821
难度:黄
思路:
一个听常用的 trick了算是,建一个正图一个反图然后各跑一边 spfa 就行。注意答案的计算。
代码,马蜂稀烂:
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int n,m,x;
int ans[10010];
int dis[10010],vis[10010],mp[2010][2010],mp2[2010][2010];
void spfa(int x,int mp[2010][2010]){
for(int i=1;i<=n;i++)dis[i]=1e18;
memset(vis,0,sizeof vis);
dis[x]=0;
vis[x]=1;
queue<int> a;
a.push(x);
while(a.size()){
int u=a.front();
a.pop();
vis[u]=0;
for(int i=1;i<=n;i++){
if(dis[i]>dis[u]+mp[u][i]){
dis[i]=dis[u]+mp[u][i];
if(!vis[i]){
vis[i]=1;
a.push(i);
}
}
}
}
for(int i=1;i<=n;i++)ans[i]+=dis[i];
}
signed main(){
cin >> n >> m >> x;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mp[i][j]=1e18;
mp2[i][j]=1e18;
}
}for(int i=1;i<=m;i++){
int s,t,v;
cin >> s >> t >> v;
mp[s][t]=min(mp[s][t],v);
mp2[t][s]=min(mp2[t][s],v);
}spfa(x,mp);
spfa(x,mp2);
int answ=0;
for(int i=1;i<=n;i++)answ=max(answ,ans[i]);
cout << answ;
return 0;
}
P10491
难度:橙
简单广搜不说。
代码:
#include <bits/stdc++.h>
int n,m,sx,sy,fx,fy,dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1},dis[1005][1005];
char mp[1005][1005];
int vis[1005][1005];
struct node{
int x,y;
}l;
int bfs(){
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis[i][j]=-1;
std::queue<node> q;
q.push({sx,sy});
dis[sx][sy]=0;
while(q.size()){
l=q.front();
q.pop();
if(l.x==fx and l.y==fy){
return dis[fx][fy];
}
for(int i=0;i<8;i++){
int nx=l.x+dx[i],ny=l.y+dy[i];
if(nx>=1 and nx<=n and ny>=1 and ny<=m and vis[nx][ny]==0 and mp[nx][ny]!='*'){
q.push({nx,ny});
vis[nx][ny]=1;
dis[nx][ny]=dis[l.x][l.y]+1;
}
}
}
}
int main(){
std::cin >> m >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
std::cin >> mp[i][j];
if(mp[i][j]=='K')sx=i,sy=j;
else if(mp[i][j]=='H')fx=i,fy=j;
}
}std::cout << bfs();
return 0;
}
全部评论 15
d
2026-05-05 来自 浙江
1d
2026-05-05 来自 山西
0
这次不会烂尾了,写详细点
2026-05-05 来自 浙江
1d
2026-05-22 来自 浙江
0d
2026-05-22 来自 浙江
0d
2026-05-22 来自 浙江
0D

2026-05-22 来自 浙江
0知道了
2026-05-22 来自 浙江
0P6136acgo有没有原题
2026-05-21 来自 广东
0你搜一下不就行
2026-05-21 来自 浙江
0题叫啥
2026-05-21 来自 广东
0p开头的acgo不可能有,只能搜题面
2026-05-21 来自 广东
0
你是和 pzh 同龄吗
2026-05-20 来自 广东
0比他菜好多是吧
2026-05-21 来自 浙江
0你怎么知道我要说什么
2026-05-21 来自 广东
0因为我有自知之明(
2026-05-21 来自 浙江
0
D
2026-05-06 来自 浙江
0daff
2026-05-06 来自 浙江
0asfs
2026-05-06 来自 浙江
0%%%
2026-05-05 来自 浙江
0指针的实现就是又臭又长,暴论
2026-05-05 来自 广东
0我就爱看这种东西😋
2026-05-05 来自 浙江
0
2026-05-05 来自 浙江
0我去艾特错了
2026-05-05 来自 浙江
1







































有帮助,赞一个