1.bzoj3211: 花神游历各国
由于$10^9$以内的数最多只会被开方$10$次，所以我们可以用线段树维护然后剪枝..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
const LL Maxn = 100010;
LL p[Maxn][31], nochange[Maxn][31];
LL sum[Maxn*4], la[Maxn*4]; bool isone[Maxn*4];
LL n, m;
void bulid_tree ( LL now, LL L, LL R ){
if ( L < R ){
LL mid = ( L + R ) >> 1, lc = now*2, rc = now*2+1;
bulid_tree ( lc, L, mid );
bulid_tree ( rc, mid+1, R );
sum[now] = sum[lc]+sum[rc];
la[now] = 0;
if ( isone[lc] && isone[rc] ) isone[now] = true;
}
else {
sum[now] = p[L][0]-p[L-1][0];
la[now] = 0;
if ( sum[now] <= 1 ) isone[now] = true;
}
}
void push_down ( LL now, LL L, LL R ){
LL mid = ( L + R ) >> 1, lc = now*2, rc = now*2+1;
if ( la[now] >= 0 ){
la[lc] = la[rc] = la[now];
sum[lc] = p[mid][la[lc]]-p[L-1][la[lc]];
if ( nochange[mid][la[lc]]-nochange[L-1][la[lc]] == mid-L+1 ) isone[lc] = true;
sum[rc] = p[R][la[rc]]-p[mid][la[rc]];
if ( nochange[R][la[rc]]-nochange[mid][la[rc]] == R-mid ) isone[rc] = true;
}
}
void change ( LL now, LL L, LL R, LL l, LL r ){
if ( isone[now] ) return;
if ( L == l && R == r && la[now] != -1 ){
la[now] ++;
sum[now] = p[R][la[now]]-p[L-1][la[now]];
if ( nochange[R][la[now]]-nochange[L-1][la[now]] == (R-L+1) ) isone[now] = true;
return;
}
push_down ( now, L, R );
LL mid = ( L + R ) >> 1, lc = now*2, rc = now*2+1;
if ( r <= mid ) change ( lc, L, mid, l, r );
else if ( l > mid ) change ( rc, mid+1, R, l, r );
else change ( lc, L, mid, l, mid ), change ( rc, mid+1, R, mid+1, r );
sum[now] = sum[lc]+sum[rc];
if ( la[lc] == la[rc] ) la[now] = la[lc]; else la[now] = -1;
if ( isone[lc] && isone[rc] ) isone[now] = true;
}
LL query ( LL now, LL L, LL R, LL l, LL r ){
if ( L == l && R == r ) return sum[now];
push_down ( now, L, R );
LL mid = ( L + R ) >> 1, lc = now*2, rc = now*2+1;
if ( r <= mid ) return query ( lc, L, mid, l, r );
else if ( l > mid ) return query ( rc, mid+1, R, l, r );
else return query ( lc, L, mid, l, mid ) + query ( rc, mid+1, R, mid+1, r );
}
int main (){
LL i, j, k;
scanf ( "%lld", &n );
for ( i = 1; i <= n; i ++ ){
scanf ( "%lld", &p[i][0] );
if ( p[i][0] <= 1 ) nochange[i][0] = 1;
for ( j = 1; j <= 10; j ++ ){
p[i][j] = (LL)sqrt(p[i][j-1]);
if ( p[i][j] <= 1 ) nochange[i][j] = 1;
}
}
for ( j = 0; j <= 10; j ++ ){
for ( i = 1; i <= n; i ++ ) p[i][j] += p[i-1][j], nochange[i][j] += nochange[i-1][j];
}
bulid_tree ( 1, 1, n );
scanf ( "%lld", &m );
for ( i = 1; i <= m; i ++ ){
LL fl, l, r;
scanf ( "%lld%lld%lld", &fl, &l, &r );
if ( fl == 1 ){
printf ( "%lld\n", query ( 1, 1, n, l, r ) );
}
else {
change ( 1, 1, n, l, r );
}
}
return 0;
}
2.bzoj4240: 有趣的家庭菜园
考虑一个贪心策略，从小到大移动，小的数肯定放两边（哪边近放哪边）
那么对于某个数能够影响他的也就只有比他大的数了
然后就从大到小插入然后树状数组判断一下就好了..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const LL Maxn = 300010;
struct node {
int x, pos;
}list[Maxn];
bool cmp ( node x, node y ){ return x.x > y.x; }
LL sum[Maxn], n;
LL lowbit ( LL x ){ return x & (-x); }
void add ( LL x ){ while ( x <= n ){ sum[x] ++; x += lowbit (x); } }
LL query ( LL x ){ LL ret = 0; while ( x > 0 ){ ret += sum[x]; x -= lowbit (x); } return ret; }
LL _min ( LL x, LL y ){ return x < y ? x : y; }
int main (){
LL i, j, k;
scanf ( "%lld", &n );
for ( i = 1; i <= n; i ++ ) scanf ( "%lld", &list[i].x ), list[i].pos = i;
sort ( list+1, list+n+1, cmp );
memset ( sum, 0, sizeof (sum) );
LL ans = 0;
LL num = 1;
for ( i = 1; i <= n; i ++ ){
if ( list[i].x != list[i-1].x ){
while ( num < i ) add (list[num].pos), num ++;
}
LL s = query (list[i].pos);
ans += _min ( s, num-s-1 );
}
printf ( "%lld\n", ans );
return 0;
}
3.bzoj3232: 圈地游戏
二分答案，然后用网络流判断，是一个比较经典的最小割模型..
像这种小数流量的，可以先把这个数扩大$10^6$最后再缩小..
听说这种做法叫做分数规划（雾）
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define LL long long
using namespace std;
const LL Maxn = 55;
const LL Maxm = 55*55;
const LL inf = 0x7fffffff;
struct node {
LL y, next, opp; LL c;
}a[Maxm*20]; LL first[Maxm], len;
void ins ( LL x, LL y, LL c ){
len ++; LL k1 = len;
a[len].y = y; a[len].c = c;
a[len].next = first[x]; first[x] = len;
len ++; LL k2 = len;
a[len].y = x; a[len].c = 0;
a[len].next = first[y]; first[y] = len;
a[k1].opp = k2;
a[k2].opp = k1;
}
LL n, m;
LL st, ed, h[Maxm];
LL getnum ( LL x, LL y ){ return (x-1)*m+y; }
LL map[Maxn][Maxn];
LL row[Maxn][Maxn], col[Maxn][Maxn];
LL _min ( LL x, LL y ){ return x < y ? x : y; }
LL dfs ( LL x, LL flow ){
if ( x == ed ) return flow;
LL delta = 0;
for ( LL k = first[x]; k; k = a[k].next ){
LL y = a[k].y;
if ( h[y] == h[x]+1 && a[k].c > 0 && flow-delta > 0 ){
LL minf = dfs ( y, _min ( a[k].c, flow-delta ) );
delta += minf;
a[k].c -= minf;
a[a[k].opp].c += minf;
}
}
if ( delta == 0 ) h[x] = -1;
return delta;
}
bool bfs (){
queue <LL> q;
memset ( h, -1, sizeof (h) );
q.push (st); h[st] = 0;
while ( !q.empty () ){
LL x = q.front (); q.pop ();
for ( LL k = first[x]; k; k = a[k].next ){
LL y = a[k].y;
if ( h[y] == -1 && a[k].c > 0 ){
h[y] = h[x]+1;
q.push (y);
}
}
}
return h[ed] > 0;
}
int main (){
LL i, j, k;
scanf ( "%lld%lld", &n, &m );
LL sum = 0;
for ( i = 1; i <= n; i ++ ) for ( j = 1; j <= m; j ++ ){ scanf ( "%lld", &map[i][j] ); sum += map[i][j]; }
sum *= 1e6;
for ( i = 1; i <= n+1; i ++ ) for ( j = 1; j <= m; j ++ ) scanf ( "%lld", &row[i][j] );
for ( i = 1; i <= n; i ++ ) for ( j = 1; j <= m+1; j ++ ) scanf ( "%lld", &col[i][j] );
LL l = 0, r = 100*1e6, ret;
st = 0; ed = n*m+1;
while ( l <= r ){
LL mid = (l+r)>>1;
len = 0; memset ( first, 0, sizeof (first) );
for ( i = 1; i <= n; i ++ ){
for ( j = 1; j <= m; j ++ ){
LL x = getnum (i,j);
if ( i == 1 ) ins ( st, x, row[1][j]*mid );
if ( i == n ) ins ( st, x, row[n+1][j]*mid );
if ( j == 1 ) ins ( st, x, col[i][1]*mid );
if ( j == m ) ins ( st, x, col[i][m+1]*mid );
ins ( x, ed, map[i][j]*1e6 );
LL ii = i, jj = j+1;
if ( ii >= 1 && ii <= n && jj >= 1 && jj <= m ){
ins ( x, getnum(ii,jj), col[i][j+1]*mid );
ins ( getnum(ii,jj), x, col[i][j+1]*mid );
}
ii = i+1; jj = j;
if ( ii >= 1 && ii <= n && jj >= 1 && jj <= m ){
ins ( x, getnum(ii,jj), row[i+1][j]*mid );
ins ( getnum(ii,jj), x, row[i+1][j]*mid );
}
}
}
LL delta = 0;
while ( bfs () ){
delta += dfs ( st, inf*1e6 );
}
if ( sum-delta > 0 ){ ret = mid; l = mid+1; }
else r = mid-1;
}
printf ( "%.3lf\n", (double)ret/1e6 );
return 0;
}
4.bzoj3162: 独钓寒江雪
先找重心，因为重心肯定是刚好对应的（如果有两个重心就新建一个重心练到这两个点然后再乱搞..）
那么剩下的肯定只有是在交换子树下才有可能同形异构..
这个东西就是一个可重复排列..
代码先挖个坑..