CoreJava CGLib动态代理 PyCharm 循环 javafx knockoutjs view uicollectionview Ractivejs web前端开发实战项目 list获取最后一个元素 jquery获取元素宽度 mysql默认密码 bootstrap日历控件 maya曲线建模 python查找指定字符 javaswitch java编译 javaforeach java开发学习 学java基础 javasocket java抛出自定义异常 java当前日期 java游戏开发教程 python视频教程 球中的小鬼 德鲁伊武器 咪咕客户端下载 三维看图软件 fireworks8 魔兽改图工具 微信砍价活动怎么做 说话不算数的经典语句 js关闭当前页面 流程图工具 抖音代码 1500左右性价比最高的手机 qq流览器下载 复仇之矛天赋
当前位置: 首页 > 学习教程  > 编程语言

C. Ayoub‘s function(思维+组合数学取补集)

2021/2/13 18:31:17 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

https://codeforces.com/problemset/problem/1301/C 题意:给出一个字符串中1的个数,和它的长度,其余都是0,然后构造一个字符串,使得f(s)最大,f(s)表示有多少个点对,使得这个点对的区间中至少包含…

https://codeforces.com/problemset/problem/1301/C


题意:给出一个字符串中1的个数,和它的长度,其余都是0,然后构造一个字符串,使得f(s)最大,f(s)表示有多少个点对,使得这个点对的区间中至少包含一个1。

思路:取反,考虑只有0串的情况,然后拿总数-只有0串的情况。

1有m个,那么0有n-m个。于是要使1多,那么0串总数要尽量小。00的0串总数是3,而010的0串总数是2.所以构造的思路就是均摊,将0尽量插到1的间隔之间平均分配。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL t;cin>>t;
  while(t--){
    LL n,m;cin>>n>>m;
    LL ans=n*(n+1)/2;
    LL num0=n-m;
    LL k=num0/(m+1);
    LL mod=num0%(m+1);
    LL sum1=(m+1-mod)*(k*(k+1)/2);
    LL sum2=mod*((k+1)*(k+1+1)/2);
    cout<<ans-(sum1+sum2)<<"\n";
  }
return 0;
}

 


本文链接: http://www.dtmao.cc/news_show_700260.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?