泸州市建设厅官方网站,国家高新技术企业专利要求,百度一下就知道,wordpress重置后密码是多少旋转子段 连60分都没想#xff0c;考试一直肝t3#xff0c;t2#xff0c;没想到t1最简单 我一直以为t1很难#xff0c;看了题解发现也就那样 题解 性质1 一个包含a[i]旋转区间值域范围最多为min(a[i],i)----max(a[i],i) 感性理解 举个例子,例如3 7 1 4 5 6 2 这个子段包含a… 旋转子段 连60分都没想考试一直肝t3t2没想到t1最简单 我一直以为t1很难看了题解发现也就那样 题解 性质1 一个包含a[i]旋转区间值域范围最多为min(a[i],i)----max(a[i],i) 感性理解 举个例子,例如3 7 1 4 5 6 2 这个子段包含a[2]的最大为值域范围2----7 具体证明我不会 性质2 翻转后满足固定点对的点满足 a[i]ia[j]j 证明 因为翻转之前a[i]ja[j]i才满足翻转之后都构成点对 移项得到a[i]ia[j]j 有了这两条性质我们可以得到一个$n^2$算法 for(ll i1;in;i){tot0;for(ll jmin(i,a[i]);jmax(i,a[i]);j)if(a[j]ja[i]i)tot;
} 得到tot最大值输出即可 70分代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 1010101
ll f[A],a[A],sum[A];
ll n,ans-1,tot0;
vectorlltoo[501010];
int main(){scanf(%lld,n);for(ll i1;in;i){scanf(%lld,a[i]);sum[i]sum[i-1];if(a[i]i) sum[i];}for(ll i1;in;i){tot0;for(ll jmin(i,a[i]);jmax(i,a[i]);j){if(a[j]ja[i]i){tot;}}
// printf(n%lld max%lld min%lld i%lld tot%lld\n,n,max(i,a[i]),min(i,a[i]),i,tot);ansmax(totsum[n]-sum[max(i,a[i])]sum[min(i,a[i])-1],ans);}printf(%lld\n,ans);
} View Code 100分 莫队维护一下询问,需要卡常,卡常到自闭,fh卡常大师 分块0.53最优 #includebits/stdc.h
using namespace std;
#define ll int
const int A1010101,L120|1;
#define getchar() ((ST(T(Sbuf)fread(buf,1,L,stdin),ST))?EOF:*S)
ll f[A],a[A],sum[A],tong[A],belong[A];
ll n,ans-1,l1,r0,ou0,block;
char buf[L],*S,*T;
struct moo{ll zhong,r,l,a;friend bool operator (moo a,moo b){return ((belong[a.l]^belong[b.l]))?a.lb.l:((belong[a.l]1)?a.rb.r:a.rb.r);}
}mo[A];
inline ll read(){ll x0;char cgetchar();while(!isdigit(c))cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();return x;
}
int main(){nread();blockpow(n,0.53);for(register ll i1;in;i){a[i]read();sum[i]sum[i-1];if(!(a[i]^i)) sum[i];belong[i](i-1)/block1;}for(register ll i1;in;i){mo[i].zhongi;mo[i].rmax(i,a[i]);mo[i].lmin(i,a[i]);mo[i].aa[i];}sort(mo1,mon1);for(register ll i1;in;i){while(lmo[i].l) tong[l-1a[l-1]],l--;while(lmo[i].l) tong[la[l]]--,l;while(rmo[i].r) tong[ra[r]]--,r--;while(rmo[i].r) tong[r1a[r1]],r;ansmax(tong[mo[i].zhongmo[i].a]sum[n]-sum[mo[i].r]sum[mo[i].l-1],ans);}printf(%d,ans);
} View Code 走格子 显然贪心有门走门不对一个稍简单的数据就可以卡掉你 7 8
########
##.F#..#
#...C..#
##..#..#
##.....#
#..#...#
######## 那怎么办,只能走八个方向爆搜吗? 显然可以最短路! 从每个墙开始搜直接得到每个点到墙最短距离,然后每两相邻点之间建边,点墙之间建边 例如 (墙) | 50 | (墙)-----21------Q-------------500000000-------(墙) | | 600 | (墙) 我们只需要将Q与四个墙方向边权都设置为21即可.(例如可以在2打传送门 然后在4打传送门从2传送到4,那么所有最小代价都为21) 很简单对不对,直接跑最短路就行了 保证最短路会松弛掉一些不可行解 例如 (墙) | 50 (墙)| (墙)------21--Q-------500000--(墙) | 50 | (终点) 向上走一步再打传送门会松弛掉21这条边 代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 5010101
#define py printf(toot\n)
#define fr first
#define se second
#define mp(x,y) make_pair(x,y)
ll zh[610][610],top[610][610],low[610][610],zuo[610][610],you[610][610],bs[610][610],head[A],nxt[A],ver[A],edg[A],dis[A];
const ll nowx[5]{0,0,0,1,-1};
const ll nowy[5]{0,1,-1,0,0};
bool vis[A];
ll n,m,zhongx,zhongy,qix,qiy,ttt0,tot0;
dequepairll,ll q,toot;
char s[610][610];
ll id(ll i,ll j){return (i-1)*mj;
}
void add(ll x,ll y,ll z){nxt[tot]head[x],head[x]tot,ver[tot]y,edg[tot]z;return ;
}
void ins(ll x,ll y,ll d){if(!bs[x][y]s[x][y].){bs[x][y]d;q.push_back(mp(x,y));}
}
void bfs(){while(!q.empty()){ll kxq.front().fr,kyq.front().se;q.pop_front();
// py;for(ll i1;i4;i){ins(kxnowx[i],kynowy[i],bs[kx][ky]1);}}
}
void init(){for(ll i1;in;i)for(ll j1;jm;j){if(s[i][j]#) continue;if(s[i][j-1]#) zuo[i][j]id(i,j);else zuo[i][j]zuo[i][j-1];if(s[i-1][j]#) top[i][j]id(i,j);else top[i][j]top[i-1][j];}for(ll in;i1;i--)for(ll jm;j1;j--){if(s[i][j]#) continue;if(s[i][j1]#) you[i][j]id(i,j);else you[i][j]you[i][j1];if(s[i1][j]#) low[i][j]id(i,j);else low[i][j]low[i1][j];}
}
void addb(){for(ll i1;in;i)for(ll j1;jm;j){if(s[i][j]#) continue;ll did(i,j);if(s[i1][j].) add(d,id(i1,j),1),add(id(i1,j),d,1);if(s[i][j1].) add(d,id(i,j1),1),add(id(i,j1),d,1);if(zuo[i][j]!d)add(d,zuo[i][j],bs[i][j]);if(you[i][j]!d)add(d,you[i][j],bs[i][j]);if(top[i][j]!d)add(d,top[i][j],bs[i][j]);if(low[i][j]!d)add(d,low[i][j],bs[i][j]);}
}
void spfa(ll o){vis[o]1;memset(dis,0x7f,sizeof(dis));dis[o]0;dequell toot;toot.push_back(o);while(!toot.empty()){ll xtoot.front();toot.pop_front();for(ll ihead[x];i;inxt[i]){ll yver[i];if(dis[y]dis[x]edg[i]){dis[y]dis[x]edg[i];if(!vis[y]){vis[y]1;toot.push_back(y);}}}vis[x]0;}
}
int main(){scanf(%lld%lld,n,m);for(ll i1;in;i){scanf(%s,s[i]1);for(ll j1;jm;j){if(s[i][j]#){q.push_back(mp(i,j));}else if(s[i][j]C){s[i][j].;qixi;qiyj;}if(s[i][j]F){s[i][j].;zhongxi;zhongyj;}}}bfs(),init(),addb(),spfa(id(qix,qiy));if(dis[id(zhongx,zhongy)]1202134)printf(no\n);else printf(%lld\n,dis[id(zhongx,zhongy)]);
} View Code 柱状图 模拟退火板子题,非常板子 模拟退火最吼了 即使是板子我也要说说 首先关于 nth_element(s1,smid,sn1); 为什么要求出中位数, 前置知识 坐标轴上有很多点,点与点之间有一个距离,你将所有点移到同一个点最小花费 显然是移到中位数的点 那么应用到这个题呢? 你可以将题目要求转化,首先全部移到同一水平线上,然后再加出值 比它高的降低,比它矮的升高,换成坐标轴我们就用到了中位数 然后 if(tmpansnowans||exp(-D/T)*RAND_MAXrand()) 为什么是 exp(-D/T)*RAND_MAXrand() 不是 exp(D/T)*RAND_MAXrand() 问的好啊! 首先我们如果当前解优那么你会通过tmpansnowans跳过 然后如果当前解不优D一定是负的,如果D为负的那么D越小-D越大.D小代表当前解非常差,让它变成其他解概率更大 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 1010101
const double eps1e-5;
const double delta0.98;
const double fj1;
ll n,ans0x7ffffffffffffff;
ll s[A],h[A];
ll check(ll pos){for(ll j1;jn;j)s[j]h[j]abs(pos-j);ll midn11;nth_element(s1,smid,sn1);ll vals[mid];ll tot0;if(valmax(pos,n-pos1))valmax(pos,n-pos1);for(ll i1;in;i)totabs(s[i]-val);return tot;
}
int main(){srand(time(0));scanf(%lld,n);for(ll i1;in;i){scanf(%lld,h[i]);}double T1000;ll now(n1)1;ll nowanscheck(now);while(Teps){ll tmpnow(2ll*rand()-RAND_MAX)*T*0.000001;tmp(tmp%nn-1)%n1;ll tmpanscheck(tmp),Dtmpans-nowans;if(tmpansnowans||exp(-D/T)*RAND_MAXrand())nowanstmpans,nowtmp;if(tmpansans) anstmpans;T*delta;}printf(%lld\n,ans);
} View Code 转载于:https://www.cnblogs.com/znsbc-13/p/11319578.html
