专门做悬疑推理小说的阅读网站,wordpress插件的安装目录,珠宝公司网站模版,东莞 企业 网站制作星期一#xff1a;
dp题单 背包 第四题 混可乐 cf传送门 思路#xff1a;条件可演化为每种可乐值为 ai-n#xff0c;选最少的可乐使总和为0#xff08;具体可看官方题解 到这会发现背包并不适合了#xff0c;其实这是道bfs伪装的背包…星期一
dp题单 背包 第四题 混可乐 cf传送门 思路条件可演化为每种可乐值为 ai-n选最少的可乐使总和为0具体可看官方题解 到这会发现背包并不适合了其实这是道bfs伪装的背包和牛客周赛39 D很像 牛客传送门
代码如下
ll n;
int k;
int dis[2020];
void solve(){cin n k;memset(dis,-1,sizeof dis);queueintqu;mapint,intmp;for(int i1;ik;i){int x; cin x;xx-n1000;if(dis[x]-1) dis[x]1,qu.push(x),mp[x]1;}while(!qu.empty()){int tqu.front(); qu.pop();
// for(int i0;i2000;i){
// if(it-10000 || it-10002000) continue;
// if(dis[ti-1000]!-1 || dis[i]!1) continue;
// dis[ti-1000]dis[t]1;
// qu.push(ti-1000);
// }for(auto [x,y]:mp){if(xt-10000 || xt-10002000) continue; //x和t都经过了一次偏移if(dis[xt-1000]!-1) continue; //所以加起来后需要减一次偏移量dis[xt-1000]dis[t]1; //新到达的点qu.push(xt-1000);}}if(dis[1000]-1) cout -1\n;else cout dis[1000] \n;
} 晚cfC是dp没出 星期二
cf edu 165 补C cf传送门 思路贪心证伪后用dp考虑状态设计及转移大致如下 这里提一点卡我很久很久的地方第一重循环 i 需要从0开始枚举
因为状态转移并不是由 i之前推到 i而是从 i往后面推 i从1开始的话有些状态无法转移出来这点在以后也需要注意
代码如下
const int N2e610,M210;
const int mod1e97;
ll n;
int k;
int a[N];
ll dp[N][11];
void solve(){cin n k;for(int i1;in;i){cin a[i];dp[i][0]dp[i-1][0]a[i];for(int j1;jk;j) dp[i][j]1e18;}for(int i0;in;i){int mia[i1];for(int j0;jk;j){mimin(a[ij1],mi);for(int o0;ojk;o){dp[ij1][oj]min(dp[i][o]1ll*mi*(j1),dp[ij1][oj]);}}}cout dp[n][k] \n;
} 晚cf round942 div2最后十分钟出C又被permutation拿下了 星期三
上午vp牛客周赛28
E 牛客传送门 思路三个连续数的和为偶数组合形式有限分别为偶偶偶偶奇奇奇偶奇奇奇偶数组最先三个数的奇偶性确定后整个数组的每个数的奇偶性都确定了
算出k以内的数能选的奇数和偶数个数n个位置中奇数和偶数各有多少个乘法原理和快速幂计算
代码如下
const int mod1e97;
ll n;
ll k;
ll qpow(int a,int n){if(n0) return 1;if(n1) return a;ll sqpow(a,n/2);ss*s%mod;if(n1) ss*a%mod;return s;
}
void solve(){cin n k;int num00,num10;num0k/2,num1k/2(k1);ll ansqpow(num0,n); //全偶int n0n/3,n1n/3*2;if(n%30) ans3*qpow(num1,n1)*qpow(num0,n0)%mod,ans%mod;if(n%31)ans2*qpow(num1,n11)*qpow(num0,n0)%mod,ansqpow(num1,n1)*qpow(num0,n01),ans%mod;if(n%32)ans2*qpow(num1,n11)*qpow(num0,n01)%mod,ansqpow(num1,n12)*qpow(num0,n0),ans%mod;cout ans;
} 下午牛客五一 1很难看情况补题 周赛28 F题离散化树状数组先复习下树状数组刚好趁五一假期学点数据结构
洛谷树状数组板子题其一单点修改区间查询 洛谷传送门 代码如下
const int N2e610,M210;
const int mod1e97;
ll n;
ll m;
ll a[N];
ll t[N];
int lowbit(int x){return x-x;}
void ad(int x,int v){for(int ix;in;ilowbit(i)) t[i]v;
}
ll ask(int x){ll res0;for(int ix;i;i-lowbit(i)) rest[i];return res;
}
void solve(){cin n m;for(int i1;in;i){cin a[i];ad(i,a[i]); //nlogn构造树状数组}while(m--){int op,x,y; cin op x y;if(op1) ad(x,y);else cout ask(y)-ask(x-1) \n;}
} 树状数组板子题其二区间修改单点查询 洛谷传送门 代码如下
const int N2e610,M210;
const int mod1e97;
ll n;
ll m;
ll a[N];
ll t[N];
int lowbit(int x){return x-x;}
void ad(int x,int v){for(int ix;in;ilowbit(i)) t[i]v;
}
ll ask(int x){ll res0;for(int ix;i;i-lowbit(i)) rest[i];return res;
}
void solve(){cin n m;for(int i1;in;i) cin a[i];while(m--){int op,x; cin op x;if(op1){int y,k; cin y k;ad(x,k); ad(y1,-k); //差分思想,x到y这段区间加上了k}else cout a[x]ask(x) \n; //t数组维护的是修改值}
} 星期四
补牛客周赛28 F 牛客传送门 思路因为前缀和不再有单调性所以easy版本二分和双指针的做法失效用离散化树状数组
区间元素和大于等于k即 a【l-1】 a【r】- k我们可以枚举右端点然后查询有多少个左端点小于等于这个值枚举后将此右端点加入左端点的集合这里用权值树状数组来实现
权值树状数组单点修改区间查询修改的意义是值为x的数多了1查询的意义即为 x的值个数类似于用树状数组维护桶数组
不过由于值的范围能到达1e14需要离散化处理即按照原值的大小关系映射为紧密连续的值这里需要用到的值不仅有 a【i】还有 a【i】- k 用于查询所以离散化后数据范围最多 2e5
最后一个需要注意的点是add函数的 i n需改为 i 离散化后映射的最大值因为这才是 离散化后权值树的最大下标
代码如下
const int N2e610,M210;
const int mod1e97;
ll n;
ll a[N],k;
ll t[N],cnt;
mapll,intto;
int lowbit(int x){return x-x;}
void add(int x,int v){for(int ix;icnt;ilowbit(i)) t[i]v; //注意下标并不为 n
}
ll ask(int x){ll res0;for(int ix;i;i-lowbit(i)) rest[i];return res;
}
void solve(){cin n k;for(int i1;in;i){cin a[i];a[i]a[i-1];to[a[i]]1,to[a[i]-k]1;}to[0]1;for(auto [x,y]:to) ycnt; //离散化处理ll ans0;add(to[0],1); //因为查询的是a[l-1],a[0]0的值先加上for(int i1;in;i){ansask(to[a[i]-k]); //查询add(to[a[i]],1); //权值1}cout ans;
} 牛客五一集训 1 补B斐波那契字符串 牛客传送门 思路n 比较小可以递归求解f 数组储存此字符串的长度
代码如下
ll n;
ll f[550];
const ll MA1e1210;
inline char fnd(int n,ll k){if(n1) return COFFEE[k-1];if(n2) return CHICKEN[k-1];if(kf[n-2]) return fnd(n-2,k); //此字符属于第i-2个字符串else return fnd(n-1,k-f[n-2]); //否则属于第i-1个
}
void solve(){f[1]6,f[2]7;for(int i3;i510;i) f[i]min(MA,f[i-2]f[i-1]);int t; cin t;while(t--){ll k; cin n k;for(ll ik;imin(k10,f[n]1);i) cout fnd(n,i);//i注意开llcout \n;}
}
其他题都不是很好补先放会 准备补牛客寒假集训营2的两道线段树题过程可能会比较漫长期望在4号内完成
晚cf round 943B题翻车题数4题 星期五
先敲个线段树板子复习下
代码如下区间修改区间查询
const int N2e610,M210;
const int mod1e97;
ll n;
#define lc p1
#define rc p1|1
int m;
struct nod{ll l,r,sum,add; //左端点右端点区间总和懒标记
}t[N]; //要开原数组 4倍大小
ll a[N];
void pushup(int p){ //向上更新t[p].sumt[lc].sumt[rc].sum;
}
void pushdn(int p){ //向下更新if(!t[p].add) return ;t[lc].sum(t[lc].r-t[lc].l1)*t[p].add;t[rc].sum(t[rc].r-t[rc].l1)*t[p].add;t[lc].addt[p].add;t[rc].addt[p].add;t[p].add0;
}
void bd(int p,int l,int r){t[p]{l,r,a[l],0};if(lr) return ; //叶子节点int mlr1;bd(lc,l,m);bd(rc,m1,r);pushup(p);
}
ll ask(int p,int x,int y){ //区间查询if(xt[p].l yt[p].r) return t[p].sum; //被查询区间完全覆盖则直接返回sumll sum0;int mt[p].lt[p].r1;pushdn(p); //向下查前先向下更新if(xm) sumask(lc,x,y); //有覆盖到左子节点if(ym) sumask(rc,x,y); //有覆盖到右子节点return sum;
}
void updt(int p,int x,int y,int k){if(xt[p].l yt[p].r){t[p].sum(t[p].r-t[p].l1)*k;t[p].addk;return ; //打上懒标记直接返回}int mt[p].lt[p].r1;pushdn(p); //记得先向下更新if(xm) updt(lc,x,y,k);if(ym) updt(rc,x,y,k);pushup(p); //再向上更新
}
void solve(){cin n m;for(int i1;in;i) cin a[i];bd(1,1,n);while(m--){int op,x,y; cin op x y;if(op1){int k; cin k;updt(1,x,y,k);}else cout ask(1,x,y) \n;}
} 补牛客寒假营2 G 牛客传送门 思路线段树维护两个信息区间最大值( suma【i】- 2*a【i】) 和区间和但区间和不需要区间修改区间最大值需要(a【x】变化会使 x到n的前缀和改变)所以一个懒标记给区间最大值用就行
官方题解【题解】2024牛客寒假算法基础集训营2_牛客网 (nowcoder.com)
还有一个我de了半个下午需要注意的一点是求区间信息时一定要确保 l r
代码如下魔改的比较随意
const int N2e610,M210;
const int mod1e97;
ll n;
#define lc p1
#define rc p1|1
struct nod{ll l,r,sum,add,ma;
}t[N];
ll a[N],suma[N];
void pushup(int p){t[p].sumt[lc].sumt[rc].sum;t[p].mamax(t[lc].ma,t[rc].ma);
}
void pushdn(int p){if(!t[p].add) return ;t[lc].mat[p].add; //懒标记只需给最大值用t[rc].mat[p].add;t[lc].addt[p].add;t[rc].addt[p].add;t[p].add0;
}
void bd(int p,int l,int r){t[p]{l,r,a[l],0,suma[l]-2*a[l]};if(lr) return ;int mlr1;bd(lc,l,m);bd(rc,m1,r);pushup(p);
}
ll ask(int p,int x,int y,int op){ //op为1求区间和为2求区间最大值if(xt[p].l yt[p].r){if(op1) return t[p].sum;else return t[p].ma;}ll res0;int mt[p].lt[p].r1;pushdn(p); //记得向下更新if(op1){res0;if(xm) resask(lc,x,y,1);if(ym) resask(rc,x,y,1);}else{res-1e18;if(xm) resmax(ask(lc,x,y,2),res);if(ym) resmax(ask(rc,x,y,2),res);}return res;
}
void updt(int p,int x,int y,int k,int op){ //op为1改区间最大值为2改区间和(单点修改)if(xt[p].l yt[p].r){if(op1){t[p].mak;t[p].addk;}else t[p].sumk;return ;}int mt[p].lt[p].r1;pushdn(p);if(xm) updt(lc,x,y,k,op);if(ym) updt(rc,x,y,k,op);pushup(p);
}
void solve(){int q; cin n q;for(int i1;in;i){cin a[i];suma[i]suma[i-1]a[i];}bd(1,1,n);while(q--){int op,x,y; cin op x y;if(op1){updt(1,x,x,2*a[x]-2*y,1); //将 sum[i]-2*a[x]改为 sum[i]-2*yupdt(1,x,n,y-a[x],1); //x-n的区间最大值全减a[x]加y (前缀和改变)updt(1,x,x,y,2);a[x]y;}else{
// cout ask(1,x1,y,2)-ask(1,1,x-1,1) \n;ll resask(1,x1,y,2);if(x-11) res-ask(1,1,x-1,1); // 特判x-1cout res \n;}}
} 星期六
线段树维护区间最大子段和板子题 洛谷传送门 代码如下
const int N2e610,M210;
const int mod1e97;
ll n;
struct seg_Tree{#define lc p1#define rc p1|1struct nod{int l,r;ll sum,maxl,maxr,ma;}t[N];int ql,qr; //查询区间nod merge(nod a,nod b){nod res;res.la.l,res.rb.r;res.suma.sumb.sum;;res.maxlmax(a.maxl,a.sumb.maxl);res.maxrmax(b.maxr,a.maxrb.sum);res.mamax({a.maxrb.maxl,a.ma,b.ma});return res;}void pushup(int p){t[p]merge(t[lc],t[rc]);} //向上更新void bd(int p,int l,int r){ //bd里处理输入if(lr){t[p]{l,r,0,-0x3f3f3f3f,-0x3f3f3f3f,-0x3f3f3f3f};cin t[p].sum;t[p].maxlt[p].maxrt[p].mat[p].sum;return ;}int mlr1;bd(lc,l,m);bd(rc,m1,r);pushup(p);}void update(int p,int v){if(qlt[p].l qrt[p].r){t[p].sumt[p].maxlt[p].maxrt[p].mav; //叶子节点的所有信息都要改return ;}int mt[p].lt[p].r1;if(qlm) update(lc,v);if(qrm) update(rc,v);pushup(p); //向上更新}nod query(int p){if(qlt[p].l qrt[p].r) return t[p];int mt[p].lt[p].r1;if(qlm) return query(rc);if(qrm) return query(lc);return merge(query(lc),query(rc));}void updt(int l,int r,int v){qll;qrr;
// qopop;update(1,v);}ll ask(int l,int r){qll,qrr;return query(1).ma;}#undef lc#undef rc
}tr;
void solve(){int m; cin n m;tr.bd(1,1,n);while(m--){int k,a,b; cin k a b;if(k1){if(ab) swap(a,b);cout tr.ask(a,b) \n;}else tr.updt(a,a,b);}
} 周日
川大校赛初赛输
补牛客寒假营2 H 牛客传送门 思路easy版本的贪心失效在线段树维护区间最大子段和的基础上修改一下
官方题解很详细【题解】2024牛客寒假算法基础集训营2_牛客网 (nowcoder.com)
代码如下
const int N2e610,M210;
const ll INF0x3f3f3f3f3f3f3f3f; //必须得开ll
const int mod1e97;
ll n;
struct seg_Tree{#define lc p1#define rc p1|1struct nod{int l,r;ll sum,maxr,minl,ansl,ansr,segans,ans;}t[N];int ql,qr,qop,a[N];nod merge(nod a,nod b){nod res;res.la.l,res.rb.r;res.suma.sumb.sum;res.maxrmax(b.maxr,a.maxrb.sum);res.minlmin(a.minl,a.sumb.minl);res.anslmax({a.ansl,a.sumb.ansl,a.sum-b.minl,a.segans-b.minl});res.ansrmax({b.ansr,a.ansr-b.sum,a.maxr-b.sum,a.maxrb.segans});res.segansmax({a.sum-b.sum,a.segans-b.sum,a.sumb.segans});res.ansmax({a.ans,b.ans,a.maxr-b.minl,a.ansr-b.minl,a.maxrb.ansl});return res;}void pushup(int p){t[p]merge(t[lc],t[rc]);}void bd(int p,int l,int r){t[p]{l,r,a[l],-INF,INF,-INF,-INF,-INF,-INF};if(lr){t[p].maxrt[p].minlt[p].sum;return ;}int mlr1;bd(lc,l,m);bd(rc,m1,r);pushup(p);}void update(int p,int v){if(qlt[p].l qrt[p].r){t[p].maxrt[p].minlt[p].sumv;return ;}int mt[p].lt[p].r1;if(qlm) update(lc,v);if(qrm) update(rc,v);pushup(p);}nod query(int p){if(qlt[p].l qrt[p].r) return t[p];int mt[p].lt[p].r1;if(qlm) return query(rc);if(qrm) return query(lc);return merge(query(lc),query(rc));}void updt(int l,int r,int v){qll;qrr;
// qopop;update(1,v);}ll ask(int l,int r){qll,qrr;return query(1).ans;}#undef lc#undef rc
}tr;
void solve(){int q; cin n q;for(int i1;in;i) cin tr.a[i];tr.bd(1,1,n);while(q--){int op,x,y; cin op x y;if(op1) tr.updt(x,x,y);else cout tr.ask(x,y) \n;}
}
