关键词：
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
", 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
", 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
", (double)ret/1e6 );
return 0;
}
4.bzoj3162: 独钓寒江雪
先找重心，因为重心肯定是刚好对应的（如果有两个重心就新建一个重心练到这两个点然后再乱搞..）
那么剩下的肯定只有是在交换子树下才有可能同形异构..
这个东西就是一个可重复排列..
代码先挖个坑..
pythion第二弹
################################第二节################################################python中数据类型的常见的方法第一个数据类型字符串str字符串里面有很多的功能,叫方法.只要是字符串,就可以用里面的方法,方法有很多,不用刻意的去记住,因为... 查看详情
深入理解threadpoolexecutor第二弹(代码片段)
从源头解析ThreadPoolExecutor第二弹—ThreadPoolExecutor的内部类ThreadPoolExecutor主要包括如下内部类：其中AbortPolicy、CallerRunsPolicy、DiscardOldestPolicy、DiscardPolicy表示任务的拒绝策略，当线程池的线程数量达到最大值并且阻塞队列已... 查看详情
表单练习第二弹
---恢复内容开始---<bodytext="#33FF00"bgcolor="#33FF33"background="150358666450342800_a580xH.jpg">body里面加属性，字体颜色、背景色、背景图片。在body里面输入的属性是针对在body里面所有内容的属性。<formaction="../10.9表单/www.baidu.html"method=" 查看详情
线段树＋rmq问题第二弹
线段树＋RMQ问题第二弹 上篇文章讲到了基于SparseTable解决RMQ问题，不知道大家还有没有印象，今天我们会从线段树的方法对RMQ问题再一次讨论。正式介绍今天解决RMQ问题的方法之前，我先对RMQ问题的概念再... 查看详情
lca问题第二弹
LCA问题第二弹 上次用二分的方法给大家分享了对LCA问题的处理，各位应该还能回忆起来上次的方法是由子节点向根节点（自下而上）的处理，平时我们遇到的很多问题都是正向思维处理困难而逆向思维处理比较容易，LCA问题... 查看详情
dom事件第二弹（uievent事件）
此文章主要总结UIEvent相关的事件，如有不对的地方，欢迎指正。一、uitls.js(绑定事件公共类)varfixs={‘focusin‘:{standard:‘focus‘,ie:‘focusin‘},‘focusout‘:{standard:‘blur‘,ie:‘foucsout‘},‘input‘:{standard:‘input‘,ie:‘propertychange‘}}v... 查看详情
有趣的网站-第二弹
1.预测您的死亡时间，通过输入出生日期，选择性别、BMI范围（可以通过页面下方输入身高、体重计算出）、生活态度和是否抽烟，点击查看按钮就可以得出结果。我测了我还能活52多年。。不过看着时间越来越少，心理感觉毛... 查看详情
获取免费的gpt网站指南（第二弹）
免费虽好，勿要贪杯前言GPT4free的原理是从大网站的接口中当普罗米修斯，如果换一个思路，公网上很多人都部署了自己的GPT服务，如果能够把他们利用起来，实际上我们平时问问题也够用了 查看详情
cookbook学习第二弹
1.5怎样实现一个按优先级排序的队列？并且在这个队列上面每次pop操作总是返回优先级最高的那个元素带有双下划线的方法，会在需要被调用的位置自动被调用带有单下划线的变量是私有变量 下面利用类heapq模块实现一个简... 查看详情
hbase存取速度为啥快---第二弹
版权声明：本文为CSDN博主「九品下」的原创文章原文链接：https://blog.csdn.net/w892824196/article/HBase能提供实时计算服务主要原因是由其架构和底层的数据结构决定的，即由LSM-Tree(Log-StructuredMerge-Tree)+HTable(region分区)+Cache决定——客户... 查看详情
『pytorch』第二弹_张量
参考：http://www.jianshu.com/p/5ae644748f21#几个数学概念：标量（Scalar）是只有大小，没有方向的量，如1，2，3等向量（Vector）是有大小和方向的量，其实就是一串数字，如(1,2)矩阵（Matrix）是好几个向量拍成一排合并而成的一堆数字... 查看详情
线段树第二弹（区间更新）
上篇文章，我们介绍了线段树的基本概念和单点更新、区间查询，今天，我们来接着上次的线段树问题继续深入研究。在解决线段树问题的过程中，我们会遇到要求修改区间中某一元... 查看详情
scratch编程第二弹
目标效果： 所需要展示的效果就是，天上的女巫飞来飞去，南关不断的眨眼，而猫头鹰也在不断的眨眼，------考察方向：单纯的循环结构的考察------方向，图形化编程循环考察---猫头鹰有两个背景，这种图形编程的效果就是... 查看详情
搭建spark开发环境（第二弹）
😊😊😊欢迎来到本博客😊😊😊 本篇介绍的是Spark环境的准备🛠🛠🛠 预更新📑：体验第一个Spark... 查看详情
codeforces620enewyeartree(线段树的骚操作第二弹)(代码片段)
TheNewYearholidaysareover,butReshadoesn‘twanttothrowawaytheNewYeartree.HeinvitedhisbestfriendsKerimandGuraltohelphimtoredecoratetheNewYeartree.TheNewYeartreeisanundirectedtreewith n vertices 查看详情
ai作画第二弹
上次一次尝试AI作画，还是在6月份，详情可见《AI作画初体验》。那个时候使用的是Google开发的DD(DiscoDiffusion)系统，使用的版本为V5.0。DD作画的确令人惊艳，但没想到，不到两个月的时间，SD(StableDiffusion)斜... 查看详情
compose跨平台第二弹：体验composeforweb(代码片段)
...ompose-jb以及如何使用Compose-jb开发简单的桌面端应用，第二弹，我们就来了解下如何使用Compose-jb开发Web应用。相信看完这一弹之后你会对Compose-jb有新的了解。环境要求与ComposeForDesktop的环境要求一致 查看详情
数据库学习笔记第二弹——mysql的登陆与使用（图文详解2022）(代码片段)
数据库学习笔记第二弹——MySQL的登陆与使用（图文详解2022）文章目录数据库学习笔记第二弹——MySQL的登陆与使用（图文详解2022）1.MySQL的登录1.1服务的启动与停止1.1.1途径1：使用图形界面工具1.1.2途径2：... 查看详情