题意：蜗牛爬树问题；值得一提的是在第n天如果恰好在天黑时爬到END，则恰好整除，不用再+1；
day = (End - Begin - day0)/(12*(up-down))+1;
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 50005 const double PI = acos(-1.0);
typedef long long LL ; int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
int Begin, End, up, down;
scanf("%d%d%d%d", &Begin, &End, &up, &down);
int day0 = *up;
int day;
if(up-down <= ){
if(End - Begin - day0 <=) day = ;
else day = -;
}else{
if(End - Begin - day0 <=) day = ;
else {
if((End - Begin - day0)%(*(up-down)) == )
day = (End - Begin - day0)/(*(up-down));
else
day = (End - Begin - day0)/(*(up-down))+;
}
}
cout<<day;
return ;
}
B:z-sort
题意：排序题；
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 10005 const double PI = acos(-1.0);
typedef long long LL ; int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
int n, a[N], t[N];
scanf("%d", &n);
for(int i = ; i < n; i++){
scanf("%d" ,&a[i]);
}
sort(a, a+n);
int i = , j = ;
for(; i < n; i+=, j++)
t[i] = a[j];
for(i = ; i < n; i+=, j++)
t[i] = a[j];
for(int k = ; k < n ; k++) printf("%d ", t[k]);
return ;
}
ans=总区间数−非法的
经典离线；
所有区间如下：
(1,1),(2,2),(3,3),(4,4),(5,5)……(n,n)
(1,2),(2,3),(3,4),(4,5)……(n-1,n)
(1,3),(2,4),(3,5) ……(n-2,n)
(1,4),(2,5)……(n-3,n)
(1,5)……(n-4,n)
(1,n)
若给出非法对(2,4)
则非法区间是(1,4)与(2,4)以及其下方的所有区间；总数为:(n - 4+1)*(2);
要想在计算区间是不出现重复，则对于所有right值相同的非法对，只取left值最大的；
然后再对right值进行枚举：for：1->n;
ans += 1LL*(z[i]-pos) * (n - i +1);
pos = z[i];
也可以对left枚举；（此时的排序方法与上述不同）
时间复杂度O(nlogn)
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 300005 const double PI = acos(-1.0);
typedef long long LL ;
int a[N], z[N], m, n; int main(){
//reopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
scanf("%d%d", &n, &m);
zero(a);zero(z);
int x;
for(int i = ; i <= n ; i++){
scanf("%d", &x);
a[x] = i;
}
int c,v;
for(int i = ; i <= m; i++){
scanf("%d%d", &c, &v);
int t = max(a[c], a[v]);
z[t] = max(z[t], min(a[c], a[v]));
}
LL ans = , pos = ;
for(int i = ; i<= n ;i++){
if(z[i] -pos >){
ans += 1LL*(z[i]-pos) * (n - i +);
pos = z[i];
}
}
printf("%I64d\n", 1LL*n*(n+)/-ans);
return ;
}
思路: 离散化+树状数组
离散化：如果数据是2，10，1000，100000；则存储所需空间是1e5*4；而离散化存储只需要5*4，
数据只需要保证其位置不变即可，将2，10，1000，100000用1，2，3，4代替；
其位置关系，大小关系都不变，但是存储空间变小了；
这样更方便存储，使得使用树状数组成为可能；
剩下的就是树状数组了：按左区间排下序，然后累计右区间数内区间数；（按左区间从大到小累计，否则，嘿嘿）
时间复杂度：O(nlgn);
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 200005
#define lowbit(k) k&(-k)
const double PI = acos(-1.0);
typedef long long LL ; struct BIT{int l, r, id;};
int bit[N],ANS[N],n;
BIT num[N];
void update(int s, int k){
for(int j = s; j <= n; j +=lowbit(j))
bit[j] += k;
}
int query(int k){
int ans = ;
for(int i = k; i > ; i -=lowbit(i))
ans += bit[i];
return ans;
}
bool compL(BIT a, BIT b){return a.l<b.l;}
bool compR(BIT a, BIT b){return a.r<b.r;}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
scanf("%d",&n);
for(int i = ; i <= n; i++){
scanf("%d%d", &num[i].l, &num[i].r);
num[i].id = i;
}
sort(num+, num+n+, compR);
//for(int i = 1; i <= n; i++) cout<<num[i].l<<" "<<num[i].r<<" "<<num[i].id<<endl;
for(int i = ; i <= n; i++) num[i].r = i;
sort(num+, num+n+, compL);
//for(int i = 1; i <= n; i++) cout<<num[i].l<<" "<<num[i].r<<" "<<num[i].id<<endl;
for(int i = n;i>=; i--){
ANS[num[i].id] = query(num[i].r);
update(num[i].r, );
}
for(int i = ; i <= n; i++) printf("%d\n", ANS[i]);
return ;
}
思路：强连通分量
智商太低，无法理解，还是滚去看书去了；
题解连接：
http://www.cnblogs.com/Recoder/p/5323546.html
思路：先做了poj 1852再说；