题意:给你一个序列,和标准序列连线,求交点数。

题解:就是求逆序对个数,用树状数组优化就行了。具体过程就是按照顺序往树状数组了插点(根据点的大小),因为第i大的点应该排在第i位,插进去的时候他前面本该是有i-1个点的,如果少了,那么一定就和这个元素构成了逆序对。

#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cstring> using namespace std; //#define local
typedef long long ll;
const int maxn = +;
#define lowbit(x) ((x)&-(x))
ll C[maxn];
ll n,a,b;
void add(ll x,ll d)
{
while(x <= n) {
C[x]+=d; x+=lowbit(x);
}
} ll sum(ll x)
{
ll ret = ;
while(x > ){
ret += C[x]; x-=lowbit(x);
}
return ret;
} ll Count()
{
ll res = ;
ll ele = b;
for(int i = ; i < n; i++){
ll pre = sum(ele+);
res += ele - pre;
add(ele+,);
ele = (ele+a)%n;
}
return res;
} int main()
{
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif // local
int cas = ;
while(~scanf("%I64d%I64d%I64d",&n,&a,&b)&&n){
memset(C,,sizeof(C));
printf("Case %d: %I64d\n",++cas,Count());
} return ;
}

最新文章

  1. Effective C++ -----条款33:避免遮掩继承而来的名称
  2. SNF开发平台WinForm之四-开发-主细表管理页面-SNF快速开发平台3.3-Spring.Net.Framework
  3. WCF 扩展一:格式化Web服务请求XML
  4. CSS3中渐变gradient详解
  5. Good practice release jar to Nexus
  6. EF的四种开发模式
  7. 程序点滴001_Python模拟点阵数字
  8. 谈一谈applet踩过的坑
  9. Java进程和线程关系及区别
  10. Echars鼠标点击事件多次触发
  11. bzoj1531: [POI2005]Bank notes(多重背包)
  12. 雷林鹏分享:jQuery EasyUI 表单 - 创建树形下拉框
  13. Flask系列07--Flask中的CBV, 蓝图的CBV
  14. (转载)How browsers work--Behind the scenes of modern web browsers (前端必读)
  15. LeetCode--226--翻转二叉树
  16. scala sparseVetor, SprseMatrix 实现
  17. ubuntu系统:插入优盘read-only file system
  18. asp.net状态保持
  19. Python 开发
  20. 关于Koala 中文编译出错

热门文章

  1. C# 移除string[] 数组中的指定元素
  2. 在windwo server2008服务器上配置ftp服务器、及配置phpstrom工具、实现项目同步。
  3. HTML5学习笔记(二)新元素和功能
  4. 网络编程demo之Udp和URL
  5. unity3d各种OpenFileDialog操作
  6. String,StringBuffer和StringBuilder
  7. CodeForces - 361A-Levko and Table (思维)
  8. Function.prototype.apply.call
  9. (转)Nginx的https配置记录以及http强制跳转到https的方法梳理
  10. 牛客网Java刷题知识点之关键字static、static成员变量、static成员方法、static代码块和static内部类