星期一：
板刷树形dp 牛客传送门
思路：dp【x】【j】表示以 x为根子树上保留 j条边的最大苹果树，答案即 dp【1】【q】
数据范围很小，n和q都在100以内，dfs完后直接背包转移
代码如下：
ll n;
vector<PII>ve[110];
int dp[110][110],q;
void dfs(int x,int f){for(auto [ap,v]:ve[x]) if(v!=f){dfs(v,x);for(int j=q;j;j--)for(int k=0;k<j;k++) dp[x][j]=max(dp[x][j-k-1]+dp[v][k]+ap,1ll*dp[x][j]);} //减一是因为保留x到v的这条边
}
void solve(){cin >> n >> q;for(int i=1;i<n;i++){int u,v,ap; cin >> u >> v >> ap;ve[u].push_back({ap,v});ve[v].push_back({ap,u});}dfs(1,0);cout << dp[1][q];
}板刷树形dp 牛客传送门
思路：dp【i】【0/1/2】表示以 i为根，含自己，一条子链，两条子链的最大权值
因为有负数权值，所以记得初始化dp数组为-inf
写拉了一个很捞的点，ma取最大值时没和ma自己比。之前写炮兵阵地也犯过这个失误，导致耽搁了挺多时间，事不过三
代码如下：
const int N=2e6+10,M=210;
ll n;
ll a[N],dp[N][3];
vector<int>ve[N];
ll ma;
void dfs(int x,int f){ma=max(dp[x][0],ma);for(int v:ve[x]) if(v!=f){dfs(v,x);dp[x][2]=max(dp[x][1]+max(dp[v][1],dp[v][0]),dp[x][2]);dp[x][1]=max(dp[x][0]+max(dp[v][1],dp[v][0]),dp[x][1]);ma=max(*max_element(dp[x],dp[x]+2+1),ma); //和ma自己取max！！！}
}
void solve(){cin >> n;for(int i=1;i<=n;i++) dp[i][1]=dp[i][2]=-1e18;for(int i=1;i<=n;i++) cin >> a[i],dp[i][0]=a[i];for(int i=1;i<n;i++){int u,v; cin >> u >> v;ve[u].push_back(v);ve[v].push_back(u);}ma=-1e18;dfs(1,0);cout << ma << "\n";
}补 cf edu round 168 C cf传送门
思路：贪心地构造即为最优解，第一个必放左括号，存入栈内，放置时若栈不为空，就用右括号和栈顶匹配，否则压入左括号
代码如下：
ll n;
void solve(){string s; cin >> n >> s; s=" "+s;stack<int>sk;ll ans=0;sk.push(1);for(int i=2;i<=n;i++){if(!(i&1)){if(s[i]=='(') sk.push(i);else ans+=i-sk.top(),sk.pop();}else{if(sk.empty()) sk.push(i);else ans+=i-sk.top(),sk.pop();}}cout << ans << "\n";
}补 D cf传送门
思路：二分+dfs，二分根节点能加上的值，然后从根开始dfs，ned表示此节点要求的最小值，若 av >=ned，那么 v为根子树节点的ned不变，否则所有子节点都需要补上 av缺的值，即 ned-av
此题有一坑点，即使 ned为 ll型，也要即使return，因为每次补值都可能近似于*2，ll也会爆
代码如下：
const int N=2e6+10,M=210;
ll n;
vector<int>ve[N];
ll a[N],ma;
bool dfs(int x,int f,ll ned){if(ned>ma) return 0; //及时returnif(ve[x].empty()) return a[x]>=ned;bool res=1;for(int v:ve[x]) if(v!=f){if(a[v]>=ned) res&=dfs(v,x,ned);else res&=dfs(v,x,ned+ned-a[v]);}return res;
}
void solve(){cin >> n;ma=0;for(int i=1;i<=n;i++) cin >> a[i],ma=max(a[i],ma),ve[i].clear(); //记得清空vefor(int i=2;i<=n;i++){int p; cin >> p;ve[p].push_back(i);}ll l=0,r=1e9,res=0;while(l<=r){ll mid=l+r>>1;if(dfs(1,0,mid)) res=mid,l=mid+1;else r=mid-1;}cout << res+a[1] << "\n";
}补 E cf传送门
题意：有n个怪兽，每个战力为 ai，勇者初始战力为1，从1到n挨个打，每打 k个升一级，若当前怪兽战力严格小于勇者战力，怪兽就会run，不会触发战斗，给q次询问，每次给出 p和 x，问 k为 x时，是否会与第 p个怪兽触发战斗
思路：对于怪兽 i，其 k具有单调性，即若 k>=ne【i】，则能触发战斗，否则不能，可以考虑二分求出每个怪兽的 ne【i】，然后 O(1)处理询问
若对于每个怪兽，都嗯跑遍 nlog的二分，复杂度是不能接受的，那么对于一个 k，能否快速知道在前 i-1个能触发几场战斗呢，实际上是可以的。若怪兽 j的最低 k即 ne【j】已知，那么对于任意 i>j,二分的 k值若 >=ne【j】，就会触发战斗，否则不会。那么如何快速得知有多少怪兽 ne【j】小于等于 k呢，可以使用权值树状数组，每次二分求出 ne【i】时，就给 ne【i】权值加一，ask( k )即可得知打了多少怪，从而比较等级
代码如下：
const int N=2e6+10,M=210;
ll n;
ll t[N];
int ne[N];
int lowbit(int x){return x&-x;}
void add(int x){for(int i=x;i<=n;i+=lowbit(i)) t[i]++;
}
ll ask(int x){ll res=0;for(int i=x;i;i-=lowbit(i)) res+=t[i];return res;
}
void solve(){int q; cin >> n >> q;for(int i=1;i<=n;i++){ll a; cin >> a;ll l=1,r=n,res=0;while(l<=r){ll mid=l+r>>1;ll ned=a*mid; //要让当前怪逃跑所需的最少战斗次数if(ask(mid)<ned) res=mid,r=mid-1;else l=mid+1;}ne[i]=res;add(res);}while(q--){int p,x; cin >> p >> x;if(ne[p]<=x) cout << "YES\n";else cout << "NO\n";}
}板刷初级数据结构 I 牛客传送门
思路:注意年份的范围比较大,这里使用了动态开点来处理
然后就是情况的讨论有丢丢复杂,可以先讨论必假和必真的情况,其余眉笔
代码如下:
const int N=5e4+10;
ll n;
const ll MAXN=2e9+10;
struct seg_Tree{
#define lc(p) t[p].ch[0]
#define rc(p) t[p].ch[1]struct nod{int ch[2];ll sum,ma; //年份数和最大降雨量}t[N*66];int root,tot;void pushup(int p){t[p].sum=t[lc(p)].sum+t[rc(p)].sum;t[p].ma=max(t[lc(p)].ma,t[rc(p)].ma);}void update(int &p,ll l,ll r,ll ql,ll qr,ll v){if(!p) p=++tot;if(l==r){t[p].sum=1;t[p].ma=v;return ;}ll mid=l+r>>1;if(ql<=mid) update(lc(p),l,mid,ql,qr,v);if(qr>mid) update(rc(p),mid+1,r,ql,qr,v);pushup(p);}ll ask_sum(int p,ll l,ll r,ll ql,ll qr){if(!p) return 0;if(ql<=l && qr>=r) return t[p].sum;ll mid=l+r>>1;ll res=0;if(ql<=mid) res+=ask_sum(lc(p),l,mid,ql,qr);if(qr>mid) res+=ask_sum(rc(p),mid+1,r,ql,qr);return res;}ll ask_ma(int p,ll l,ll r,ll ql,ll qr){if(!p) return 0;if(ql<=l && qr>=r) return t[p].ma;ll mid=l+r>>1;ll res=0;if(ql<=mid) res=max(ask_ma(lc(p),l,mid,ql,qr),res);if(qr>mid) res=max(ask_ma(rc(p),mid+1,r,ql,qr),res);return res;}
}tr;
void solve(){cin >> n;map<ll,int>mp;const int add=1e9+10; //防止出现负值for(int i=1;i<=n;i++){ll y,r; cin >> y >> r; y+=add;tr.update(tr.root,1,MAXN,y,y,r);mp[y]=r;}int q; cin >> q;while(q--){ll y,x; cin >> y >> x; y+=add,x+=add;ll ry=mp[y],rx=mp[x],rma=0;if(x-y>1) rma=tr.ask_ma(tr.root,1,MAXN,y+1,x-1);if(ry && rx){if(rx>ry){cout << "false\n"; continue;}if(rma && rma>=rx){cout << "false\n"; continue;}}else if(!ry && rma && rx && rma>=rx){cout << "false\n"; continue;}else if(!rx && rma && ry && rma>=ry){cout << "false\n"; continue;}ll num=tr.ask_sum(tr.root,1,MAXN,y+1,x-1);if(ry && rx && num==x-y-1) cout << "true\n";else cout << "maybe\n";}
}星期二：
补 24上海市赛 G cf传送门
dp的转移思路很简单，但调TLE和MLE调了一上午
思路：dp【i】【j】【mask】表示走到 ( i, j )，马的存活状态为 mask的方案数
注意到 n^2枚举已经是1e4了，若再枚举所有 mask，乘上1e3的复杂度，就是1e7，很难不T，但还是头铁交了好几发。后来发现要优化只能从枚举的mask里下手
注意到我们如果在每个坐标都枚举所有状态，而有些马的位置，此时枚举的 ( i, j )还不可能碰上，那么枚举此马存活与否的状态是无意义的，例如对于起点有效的状态只有全1，那么可以预处理出每个坐标的有效状态，就能在转移中大幅降低复杂度
代码如下：
const int mod=998244353;
ll n;
int m;
PII h[11];
int vi[110][110];
int dp[110][110][1030];
inline bool safe(int x,int y,int mask){ //根据马的状态判断此坐标是否可达map<PII,bool>mp;for(int i=1;i<=m;i++) if(mask&1<<i-1) mp[{h[i].first,h[i].second}]=1;if(mp.count({x,y})) return 0;if(!mp.count({x-1,y-1}) && (mp.count({x-2,y-1}) || mp.count({x-1,y-2}))) return 0;if(!mp.count({x-1,y+1}) && (mp.count({x-2,y+1}) || mp.count({x-1,y+2}))) return 0;if(!mp.count({x+1,y-1}) && (mp.count({x+1,y-2}) || mp.count({x+2,y-1}))) return 0;if(!mp.count({x+1,y+1}) && (mp.count({x+1,y+2}) || mp.count({x+2,y+1}))) return 0;return 1;
}
void solve(){cin >> n >> m; n++;for(int i=1;i<=m;i++){cin >> h[i].first >> h[i].second;h[i].first++,h[i].second++;vi[h[i].first][h[i].second]=i;}if(!safe(1,1,(1<<m)-1)){cout << 0; return ;} //特判开局GGset<int>ve[110][110];ve[1][1].insert((1<<m)-1);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) if(i!=1 || j!=1){for(int mask:ve[i-1][j]) ve[i][j].insert(mask);for(int mask:ve[i][j-1]) ve[i][j].insert(mask);if(!vi[i][j]) continue;vector<int>tv;for(int mask:ve[i][j]) tv.push_back(mask^(1<<vi[i][j]-1));for(int mask:tv) ve[i][j].insert(mask);}}dp[1][1][(1<<m)-1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==1 && j==1) continue;for(int mask:ve[i][j]) if(safe(i,j,mask)){if(!vi[i][j]) dp[i][j][mask]=(dp[i-1][j][mask]+dp[i][j-1][mask])%mod;else{ //此点无马,直接转移int nmask=mask^(1<<vi[i][j]-1);dp[i][j][mask]=(dp[i-1][j][nmask]+dp[i][j-1][nmask])%mod;} //此点有马,无此马的状态从有此马的状态转移}}}ll ans=0;for(int mask=0;mask<1<<m;mask++) (ans+=dp[n][n][mask])%=mod;cout << ans;
}下午牛客多校7，经典两题签到下班，第二题还因为漏了个特判耽误巨久
晚上cf div4，把 F组合数当成 dp了，组合数这块确实是弱项
星期三：
24河南萌新联赛 四
星期四：
补河南萌新赛 C 初级组合数 牛客传送门
又复习了下高中组合数学 高中数学—排列组合中的隔板法 - 哔哩哔哩 (bilibili.com)
思路：考虑把题目转换为隔板法的基本情况，即将 n个球放入 m个盒子，盒子非空
题目现在的情况是，将 n个球放入 m个盒子（这里将题意的n，m调换意义），第 i个盒子要求球的数量>= a【i】，可以有多余的球，那我们视为多余的球在另一个可为空的盒子里
现在盒子数变为了 m+1个，前 m个要求每个的球数>=a【i】，最后一个可为空，我们可以把对球的数量的要求全部转换为基本情况，也就是至少一个，对于 >=a【i】的，将要求和总球数都减去 a【i】-1，对于可空盒子，将要求和球数都加上1，那么就成了最基本的隔板法的情况
代码如下：
const int N=2e6+10,M=210;
const int mod=998244353;
ll n;
ll inv[N],fac[N];
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1) (res*=a)%=mod;(a*=a)%=mod;n>>=1;}return res;
}
void init(int x){fac[0]=1;for(int i=1;i<=x;i++) fac[i]=fac[i-1]*i%mod;inv[x]=qpow(fac[x],mod-2);for(int i=x-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll c(int n,int m){if(m>n) return 0;if(!m) return 1;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int a[1010];
void solve(){int m; cin >> n >> m; m++;init(2020);for(int i=1;i<=n;i++){cin >> a[i];m-=a[i]-1;}cout << c(m-1,n);
}下午牛客多校8，签到第二题没出，因为特判return前忘记清空数组了，典
补多校1 I 模拟镜子 牛客传送门
思路：ac跨度比较长的一道题,初看时就觉得是道不错的模拟,但因思路不甚清晰,没有直接下手
ans[ i ][ j ][ dir ]表示在 ( i, j)点被射入一条方向为 dir的光线的答案,注意此意义需要处理输入
观察下光线反射的路径,会发现只有链和闭环两种情况,不会出现链接在环上的情况,且链一定会射出矩阵,那么可以对于链和环作dfs,分别处理,这里对链和环的处理比较需要手法
因为链一定会射出矩阵,那反着来,从矩阵外面射进去,就能得到一条光链,在dfs时标记上状态,然后再枚举没有出现过的状态,就必定是在环内
遍历路径,用set存反射过的镜子,环内状态的答案都是一样的,为set的大小,而链内的状态则是边遍历边赋答案,这里注意遍历前需要把路径翻转,因为一个状态的答案是在它之后dfs到的镜子数
代码如下：
ll n;
int m;
char c[1010][1010];
int ans[1010][1010][4];
bool ifr(int x,int y,int dir){ //判断镜子是否参与反射char ch=c[x][y];if(ch=='\\' || ch=='/') return 1;if(ch=='-' && (dir==0 || dir==1)) return 1;if(ch=='|' && (dir==2 || dir==3)) return 1;return 0;
}
bool vi[1010][1010][4];
vector<tuple<int,int,int>>pa;
void dfs(int x,int y,int dir){if(x<1 || x>n || y<1 || y>m) return ;if(vi[x][y][dir]) return ;vi[x][y][dir]=1;pa.push_back({x,y,dir});char ch=c[x][y];if(ch=='-'){ //模拟反射if(dir==0) dfs(x+1,y,1);if(dir==1) dfs(x-1,y,0);if(dir==2) dfs(x,y-1,2);if(dir==3) dfs(x,y+1,3);}if(ch=='|'){if(dir==0) dfs(x-1,y,0);if(dir==1) dfs(x+1,y,1);if(dir==2) dfs(x,y+1,3);if(dir==3) dfs(x,y-1,2);}if(ch=='/'){if(dir==0) dfs(x,y+1,3);if(dir==1) dfs(x,y-1,2);if(dir==2) dfs(x+1,y,1);if(dir==3) dfs(x-1,y,0);}if(ch=='\\'){if(dir==0) dfs(x,y-1,2);if(dir==1) dfs(x,y+1,3);if(dir==2) dfs(x-1,y,0);if(dir==3) dfs(x+1,y,1);}
}
void getl(int x,int y,int dir){ //处理光链pa.clear();dfs(x,y,dir);reverse(pa.begin(),pa.end()); //记得翻转路径set<PII>mr;for(auto [a,b,d]:pa){if(ifr(a,b,d)) mr.insert({a,b});ans[a][b][d]=mr.size();}
}
void geth(int x,int y,int dir){ //处理光环pa.clear();dfs(x,y,dir);set<PII>mr;for(auto [a,b,d]:pa) if(ifr(a,b,d)) mr.insert({a,b});for(auto [a,b,d]:pa) ans[a][b][d]=mr.size();
}
void solve(){cin >> n >> m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin >> c[i][j];for(int i=1;i<=n;i++) getl(i,1,3),getl(i,m,2);for(int j=1;j<=m;j++) getl(1,j,1),getl(n,j,0); //从外面射进,可得到所有光链for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int dir=0;dir<4;dir++)if(!vi[i][j][dir]) geth(i,j,dir); //未出现过的状态即为环int q; cin >> q;map<string,int>mp;mp["above"]=0,mp["below"]=1,mp["left"]=2,mp["right"]=3;while(q--){int x,y; string s; cin >> x >> y >> s;int dir=mp[s]; //处理输入if(dir==0) x--;if(dir==1) x++;if(dir==2) y--;if(dir==3) y++;cout << ans[x][y][dir] << "\n";}
}星期五：
补 河南赛 E 牛客传送门
思路：注意到合法区间必包含2，因为质数中只有2的第一位为0
然后就是线性筛的问题，这里需要用vector存质数，因为开不了两个1e8的数组
然后还有二分找质数的范围，如果只筛到1e8用lower_bound会出错，需要多筛一个比1e8大的质数因为如果y为1e8，lower会返回 p.end()，减去 p.begin()后的下标会越界，p【r】的值就会乱来
代码如下：
const int N=1e8+10,M=210;
ll n;
vector<int>p;
bool vi[N];
void getp(int x){for(int i=2;i<=x;i++){if(!vi[i]) p.push_back(i);for(int j=0;1ll*i*p[j]<=x;j++){vi[i*p[j]]=1;if(i%p[j]==0) break;}}
}
void solve(){getp(1e8+8);int t; cin >> t;while(t--){int x,y; cin >> x >> y;int l=lower_bound(p.begin(),p.end(),x)-p.begin();int r=lower_bound(p.begin(),p.end(),y)-p.begin();if(p[r]>y) r--;cout << r-l+1 << " ";if(l>=r) cout << "0\n";else if(l) cout << "0\n";else if(r>1) cout << r-1 << "\n";else cout << "0\n";}
}补24 河南 K 牛客传送门
思路：容易想到分开两次计算，把每个数左边大于等于它的乘上右边小于等于它的，再加上左边小于等于它的乘上右边大于等于它的，但这样算会有重复，需对每个数减去一次左边相等乘右相等（容斥：什么?在想我的事？
代码如下：
const int N=2e6+10,M=210;
ll n;
int a[N],t[N];
int l[N],lc[N];
int lowbit(int x){return x&-x;}
void add(int x){for(int i=x;i<=1e5;i+=lowbit(i)) t[i]++;
}
ll ask(int x){ll res=0;for(int i=x;i;i-=lowbit(i)) res+=t[i];return res;
}
void solve(){cin >> n;int rc=0;for(int i=1;i<=1e5;i++) t[i]=0;for(int i=1;i<=n;i++){cin >> a[i];l[i]=ask(a[i]);lc[i]=l[i]-ask(a[i]-1);add(a[i]);}for(int i=1;i<=1e5;i++) t[i]=0;ll ans=0;for(int i=n;i;i--){int r=ask(1e5)-ask(a[i]-1);rc=ask(a[i])-ask(a[i]-1);ans-=lc[i]*rc; //减去重复计算的部分ans+=1ll*l[i]*r;add(a[i]);}for(int i=1;i<=1e5;i++) t[i]=0;for(int i=1;i<=n;i++){l[i]=ask(1e5)-ask(a[i]-1);add(a[i]);}for(int i=1;i<=1e5;i++) t[i]=0;for(int i=n;i;i--){int r=ask(a[i]);ans+=1ll*l[i]*r;add(a[i]);}cout << ans << "\n";
}星期六：
xcpc热身赛，三人集体破防
晚上cf div2，前俩题手速挺快，但C没写对
周日：
补 cf round 964 div4 F cf传送门
初见还以为是个挺高深的dp，结果是初级组合数题
思路：1的总数为sum1，若长为k的子序列有贡献，则需至少有 k/2+1个1，从 k/2+1到sum1，枚举选 1的个数，答案加上组合数方案，组合数 O(n)预处理后就能 O(1)求
代码如下：
const int N=2e6+10,M=210;
const int mod=1e9+7;
ll n;
bool a[N];
ll inv[N],fac[N];
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1) (res*=a)%=mod;(a*=a)%=mod;n>>=1;}return res;
}
void init(int x){fac[0]=1;for(int i=1;i<=x;i++) fac[i]=fac[i-1]*i%mod;inv[x]=qpow(fac[x],mod-2);for(int i=x-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll c(int n,int m){if(m>n) return 0;if(!m) return 1;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void solve(){int k; cin >> n >> k;ll sum1=0,sum0=0;for(int i=1;i<=n;i++){cin >> a[i];sum1+=(a[i]);sum0+=(!a[i]);}ll ans=0;for(int i=k/2+1;i<=sum1;i++) (ans+=c(sum1,i)*c(sum0,k-i)%mod)%=mod;cout << ans << "\n";
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int O_o=1;cin >> O_o;init(2e5+10);while(O_o--) solve();return 0;
}补 abc366 E atc传送门
读错题意两次了,然后读对后还是做不来
题意:给二维平面上 n个点,(x1,y1)...(xn,yn),和 D,求满足到n个点的曼哈顿距离之和 <=D的点的数量
贴个大佬的题解 : AtCoder Beginner Contest 366 - ~Lanly~ - 博客园 (cnblogs.com)
思路：最开始有个朴素的思路是 bfs,但这样光是搜一个点距离D以内的所有点就已经很慢了
此题需将 x和 y分开考虑,,观察此式,可将所有满足
的 x和满足
的 y找出,然后俩俩匹配
如何分别处理出 x和 y呢?观察到坐标值域在 1e6内,D也在1e6内,那么有效坐标即在[ -2e6,2e6 ]此区间,可通过4e6枚举,处理出所有x点的曼哈顿距离和,如何处理呢? 这个是可以 O(1)转换的,先处理出最左边也就是-2e6此点的曼哈顿距离和,然后用一个变量cntx记录小于 i 的x点, i每加1,对于左边的 cntx个点, i到它们的距离都会+1,对于右边的 n-cntx个点, i到它们的距离减一, y的处理和x相同
处理出所有x的曼哈顿距离和,和y的之后,将其排序,枚举 x,可二分找出能与其匹配的 y点数量
代码如下：
const int N=4e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
ll x[N],y[N];
ll disx[N],disy[N];
void solve(){ll d; cin >> n >> d;for(int i=1;i<=n;i++) cin >> x[i] >> y[i];const int py=2e6+1; //偏移量for(int i=1;i<=n;i++){ll xx=1-py;disx[1]+=abs(xx-x[i]);ll yy=1-py;disy[1]+=abs(yy-y[i]); //处理出最左点的曼哈顿距离和}sort(x+1,x+n+1);sort(y+1,y+n+1);int cntx=0,idx=1,cnty=0,idy=1;for(int i=-2e6+1;i<=2e6;i++){ll xx=i+py;disx[xx]=disx[xx-1];disx[xx]-=(n-cntx);disx[xx]+=cntx;while(idx<=n && i==x[idx]) idx++,cntx++; //更新多少点<=i,需要whilell yy=i+py;disy[yy]=disy[yy-1];disy[yy]-=(n-cnty);disy[yy]+=cnty;while(idy<=n && i==y[idy]) idy++,cnty++;}sort(disx+1,disx+py*2);sort(disy+1,disy+py*2);ll ans=0;for(int i=1;i<=4e6+1;i++){if(disx[i]>d) break; //若单x已不满足条件,可直接退出int idx=upper_bound(disy,disy+py*2,d-disx[i])-disy; //二分查找此x能与多少y点匹配ans+=idx-1;}cout << ans;
}补 cf round 965 div2 cf传送门
思路: 情况有两种:
第一种是将所有 k都给最大的 b为1的数,答案为 a[ i ] + k加上中位数
第二种是用 k来使中位数最大,答案为 b为0的最大 a[ i ] + 最大可能中位数
思路并不难想,代码实现也很简单,但赛时想漏了一个点,那就是二分中位数时,应该贪心地从大到小地填中位数,如果顺着遍历的话,很可能不能得到最优中位数,因为先填了很小的数,到后面 k就不够用了
算是赛时的疏忽,也是经验的缺失
代码如下:
const int N=2e6+10;
const int mod=1e9+7;
ll n;
ll a[N];
bool b[N];
void solve(){ll k; cin >> n >> k;ll idma1=0,ma1=0;ll idma0=0,ma0=0;for(int i=1;i<=n;i++) cin >> a[i];for(int i=1;i<=n;i++){cin >> b[i];if(b[i] && a[i]>ma1) idma1=i,ma1=a[i];if(!b[i] && a[i]>ma0) idma0=i,ma0=a[i];}vector<ll>ve;for(int i=1;i<=n;i++) if(i!=idma1) ve.push_back(a[i]);sort(ve.begin(),ve.end());ll ans=0;if(ma1){ans=ma1+k;if(ve.size()&1) ans+=ve[ve.size()/2];else ans+=ve[ve.size()/2-1];}else{ans=ve.back(); ve.pop_back();if(ve.size()&1) ans+=ve[ve.size()/2];else ans+=ve[ve.size()/2-1];}ve.clear();ve.push_back(0);for(int i=1;i<=n;i++) ve.push_back(a[i]);ll l=1,r=2e9,res=0;while(l<=r){ll mid=l+r>>1;ll tk=k,ned=0;ned=(n-1)/2+1;vector<PII>tmp;for(int i=1;i<=n;i++) if(i!=idma0) tmp.push_back({ve[i],b[i]});sort(tmp.begin(),tmp.end(),greater<>()); //贪心地补中位数for(auto [i,ifb]:tmp){if(i>=mid) ned--;else if(ifb && tk>=mid-i) tk-=mid-i,ned--;if(!ned) break;}if(!ned) res=mid,l=mid+1;else r=mid-1;}ans=max(res+ma0,ans);cout << ans << "\n";
}