主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
7.31总结
最后更新于 2025-07-31 20:26:36
作者
lrj66666
分类
闲话
复制 Markdown
查看原文
删除文章
更新内容
# T1 T640726 落落的去的围栏 二分题哇 **思路:** 涂色 : 从 $1$ 到 $k$ 涂成一种颜色,从 $k+1$ 到 $n$ 涂成另一种颜色。 可以枚举 $k$ 。 - 左边颜色必须满足 $>=k$ 的条件才可以,二分出有多少 $>=k$ 的颜色 $x$ 。 - 右边颜色必须满足 $>=n-k$ 才可以,二分出有多少 $>=n-k$ 的颜色 $y$ 。 即 $ans += x \times y- min(x,y)$ 。 --- 解释一下为什么是 $ans += x \times y- min(x,y)$ 。 举个例子 , 在记录方案数时: 如果 $x=3$ , $y=3$ , 那么颜色分别就是 $1$ $2$ $3$ 和 $3$ $4$ $5$ , 所以方案数需要两变量相乘。 最后输出 $x \times y$ 减去重复的数字即可。 思路实现 ( 部分代码 ) : ```cpp for(ll i=1;i<n;i++){ ll x=lower_bound(a+1,a+m+1,i)-a; ll y=lower_bound(a+1,a+m+1,n-i)-a; x=m-x+1; y=m-y+1; ans+=x*y-min(x,y); } ``` 由于需要二分,所以要对数组进行排序 !!! 赛时代码是骗分的就不讲了。 **Code:** ```cpp #include <bits/stdc++.h> typedef long long ll; using namespace std; const int N=2e5+10; ll t,n,m,a[N],ans; int main(){ ios::sync_with_stdio(0); cin>>t; while(t--){ cin>>n>>m; ans=0; for(ll i=1;i<=m;i++)cin>>a[i]; sort(a+1,a+m+1); for(ll i=1;i<n;i++){ ll x=lower_bound(a+1,a+m+1,i)-a; ll y=lower_bound(a+1,a+m+1,n-i)-a; x=m-x+1; y=m-y+1; ans+=x*y-min(x,y); } cout<<ans<<'\n'; } return 0; } ``` $$ \huge \text{十年OI一场空,不开long long见祖宗} $$
正在渲染内容...
点赞
0
收藏
0