留下一个坑
因为是NOIP，所以都是些非常简单的题呢
所以都是一句话题解
懒得放在博客里面了
看看到NOIP前能A掉多少道呢？
对了还有一个题单
都是目前没有AC的比较好的题,有些可能A掉忘了删掉了
反正都要做
-------------------------
10.25
1.[BZOJ3100] 排列
考虑选中的排列里面没有重复的数字然后和为一个定值随便扫描一下
时间复杂度$O(n)$
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000005;
int n,m,a[N],nex[N],ne[N],ans;
inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
inline void Prepare(){
memset(ne,0,sizeof(nex));
for(register int i=n;i>=1;i--){
if(ne[a[i]]==0)nex[i]=n+1;
else nex[i]=ne[a[i]];
ne[a[i]]=i;
}
}
inline void Solve(){
Prepare();
m=0;
for(register int i=1;i<=n;i++)if(a[i]==1)ne[++m]=i;
if(m==0)return;
else ans=max(ans,1);
for(register int i=1;i<=m;i++){
int mx=0,pos=ne[i],mn=nex[ne[i]];long long sum=0;
for(register int j=ne[i]-1;j>ne[i-1];j--){
mn=min(mn,nex[j]);
sum+=a[j];
if(a[j]<=mx){if(pos==j+mx+1)sum-=a[--pos];}
else {mx=a[j];while(pos<mn && pos<=j+mx-1)sum+=a[pos++];}
if(j+mx<=mn && sum==1ll*mx*(mx+1)/2)ans=max(mx,ans);
}
}
}
int main(){
freopen("3100.in","r",stdin);
freopen("3100.out","w",stdout);
Read(n);
for(register int i=1;i<=n;i++)Read(a[i]);
Solve();
for(register int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);
Solve();
printf("%d\n",ans);
return 0;
}
2.[BZOJ1195] [HNOI2006]最短母串
把互相包含的串缩一下然后状压dp,注意使用string类型来压空间
时间复杂度$O(2^n*n^2*len)$,len表示比较的串的长度
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=14,M=52,INF=999999999;
int n;
char sr[M];
struct String{
string str;
int len;
String(){}
String(int lw){len=lw;}
friend inline bool operator<(const String &A,const String &B){
int mn=min(A.len,B.len);
for(register int i=1;i<=mn;i++){
if(A.str[i-1]>B.str[i-1])return 0;
if(A.str[i-1]<B.str[i-1])return 1;
}
return A.len<B.len;
}
friend inline String operator+(const String &A,const String &B){
String C=String(0);
if(A.len==INF){C.len=INF;return C;}
for(register int i=min(A.len,B.len);i>=0;i--){
int diff=0;
for(register int j=1;j<=i;j++){
if(A.str[A.len-i+j-1]!=B.str[j-1]){diff=1;break;}
}
if(!diff){
C.str=A.str;
for(register int j=i+1;j<=B.len;j++)C.str+=B.str[j-1];
C.len=A.len+B.len-i;
//printf("%d\n",C.len);
return C;
}
}
return C;
}
}str[N],dp[1<<N][M],ans;
inline bool Cmp(const String &A,const String &B){
return A.len<B.len || (A.len==B.len && A<B);
}
int main(){
freopen("1195.in","r",stdin);
freopen("1195.out","w",stdout);
scanf("%d",&n);
for(register int i=1;i<=n;i++){scanf("%s",sr+1);str[i].str=sr+1;str[i].len=strlen(sr+1);}
sort(str+1,str+n+1);
for(register int i=1;i<n;i++){
if(str[i].len<str[i+1].len){
int diff=0;
for(register int j=1;j<=str[i].len;j++){
if(str[i].str[j-1]!=str[i+1].str[j-1]){diff=1;break;}
}
if(!diff){
for(register int j=i;j<n;j++)str[j]=str[j+1];
i--;n--;
}
}
}
for(register int i=1;i<=n;i++)dp[1<<(i-1)][i]=str[i];
for(register int i=1;i<(1<<n);i++){
for(register int j=0;j<n;j++){
if(dp[i][j+1].len)continue;
if(((i>>j)&1)==0)continue;
dp[i][j+1].len=INF;
for(register int k=0;k<n;k++){
if(j==k || ((i>>k)&1)==0)continue;
if(Cmp(dp[i-(1<<j)][k+1]+str[j+1],dp[i][j+1]))dp[i][j+1]=dp[i-(1<<j)][k+1]+str[j+1];
}
}
}
ans=dp[(1<<n)-1][1];
for(register int i=2;i<=n;i++)ans=min(ans,dp[(1<<n)-1][i],Cmp);
for(register int i=0;i<ans.len;i++)putchar(ans.str[i]);
putchar('\n');
return 0;
}
3.[BZOJ3754] Tree之最小方差树
考虑平均数一定在已经排序好的边权中间的两数之间的某个区间，这样的话树的形态是不改变的。
因为边权只有100而且是整数，所以我们每0.25枚举一下就好了，一定满足要求
时间复杂度$O(400nlogn)$,其中$nlogn$是排序复杂度，$400$是枚举复杂度。
另：我一开始搞了一个最大最小生成树的优化但是显然没搞对，其实就是确定范围而已懒得改了反正不改也能过
想改的话就是把Solve先跑两遍一个输入是0一个输入是100然后把结果当作Mn Mx跑循环而已
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=105,M=2005;
struct Edge{
int a,b,u;
double v;
friend bool inline operator<(const Edge &A,const Edge &B){return A.v<B.v;}
}e[M];
int n,m,f[N];
double Mn,Mx,ans=9999999999.0;
inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
inline void Clear(){for(register int i=1;i<=n;i++)f[i]=i;}
int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}
inline void Union(int sa,int sb){if(sa>sb)f[sa]=sb;else f[sb]=sa;}
inline bool Mi(const Edge &A,const Edge &B){return A.u<B.u;}
inline bool Ma(const Edge &A,const Edge &B){return A.u>B.u;}
/*
inline void Mini(){
Clear();
double fx=0.0,fy=0.0;
sort(e+1,e+m+1,Mi);
for(register int i=1;i<=m;i++){
if(Find(e[i].a)!=Find(e[i].b)){
Union(Find(e[i].a),Find(e[i].b));
fx+=e[i].u;
}
}
fx/=n-1;
Clear();
for(register int i=1;i<=m;i++){
if(Find(e[i].a)!=Find(e[i].b)){
Union(Find(e[i].a),Find(e[i].b));
fy+=(e[i].u-fx)*(e[i].u-fx);
}
}
fy/=n-1;
Mn=sqrt(fy);
}
inline void Maxi(){
Clear();
double fx=0.0,fy=0.0;
sort(e+1,e+m+1,Ma);
for(register int i=1;i<=m;i++){
if(Find(e[i].a)!=Find(e[i].b)){
Union(Find(e[i].a),Find(e[i].b));
fx+=e[i].u;
}
}
fx/=n-1;
Clear();
for(register int i=1;i<=m;i++){
if(Find(e[i].a)!=Find(e[i].b)){
Union(Find(e[i].a),Find(e[i].b));
fy+=(e[i].u-fx)*(e[i].u-fx);
}
}
fy/=n-1;
Mx=sqrt(fy);
}
*/
inline void Solve(double x){
for(register int i=1;i<=m;i++)e[i].v=(x-e[i].u)*(x-e[i].u);
Clear();
double fx=0.0,fy=0.0;
sort(e+1,e+m+1);
for(register int i=1;i<=m;i++){
if(Find(e[i].a)!=Find(e[i].b)){
Union(Find(e[i].a),Find(e[i].b));
fx+=e[i].u;
}
}
fx/=n-1;
Clear();
for(register int i=1;i<=m;i++){
if(Find(e[i].a)!=Find(e[i].b)){
Union(Find(e[i].a),Find(e[i].b));
fy+=(e[i].u-fx)*(e[i].u-fx);
}
}
fy/=n-1;
ans=min(ans,sqrt(fy));
}
int main(){
freopen("3754.in","r",stdin);
freopen("3754.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=m;i++){
Read(e[i].a);Read(e[i].b);Read(e[i].u);
}
//Mini();Maxi();
//if(Mn>Mx)swap(Mn,Mx);
Mn=0.0;Mx=100.0;
for(double i=Mn;i<=Mx;i+=0.25)Solve(i);
printf("%.4f\n",ans);
return 0;
}
4.[BZOJ3110] [Zjoi2013]K大数查询
差点忘了怎么做了……不过树套树的整体思想是清晰的
显然一个树是权值线段树，一个树是区间线段树
这题的新颖之处在于是权值套区间
以前写了爆int了没过，今天改了下unsigned int就过了
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,cnt,root[500005];
struct SegTree{
int nl,nr,l,r;
unsigned int sum,tag;
}tree[20000005];
void Pushdown(int rt){
if(tree[rt].tag && tree[rt].l!=tree[rt].r){
int mid=tree[rt].l+tree[rt].r>>1;
if(!tree[rt].nl){tree[rt].nl=++cnt;tree[tree[rt].nl].l=tree[rt].l;tree[tree[rt].nl].r=mid;}
if(!tree[rt].nr){tree[rt].nr=++cnt;tree[tree[rt].nr].l=mid+1;tree[tree[rt].nr].r=tree[rt].r;}
tree[tree[rt].nl].tag+=tree[rt].tag;
tree[tree[rt].nr].tag+=tree[rt].tag;
tree[tree[rt].nl].sum+=(tree[tree[rt].nl].r-tree[tree[rt].nl].l+1)*tree[rt].tag;
tree[tree[rt].nr].sum+=(tree[tree[rt].nr].r-tree[tree[rt].nr].l+1)*tree[rt].tag;
tree[rt].tag=0;
}
}
void Pushup(int rt){
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}
void Modify(int &rt,int l,int r,int L,int R){
if(!rt){rt=++cnt;tree[rt].l=l;tree[rt].r=r;}
Pushdown(rt);
if(L<=tree[rt].l && tree[rt].r<=R){
tree[rt].sum+=tree[rt].r-tree[rt].l+1;
tree[rt].tag++;
return;
}
int mid=tree[rt].l+tree[rt].r>>1;
if(L<=mid)Modify(tree[rt].nl,l,mid,L,R);
if(R>mid)Modify(tree[rt].nr,mid+1,r,L,R);
Pushup(rt);
}
unsigned int Query(int rt,int l,int r){
if(!rt)return 0;
Pushdown(rt);
if(l<=tree[rt].l && tree[rt].r<=r){return tree[rt].sum;}
int mid=tree[rt].l+tree[rt].r>>1;
unsigned int ans=0;
if(l<=mid)ans+=Query(tree[rt].nl,l,r);
if(r>mid)ans+=Query(tree[rt].nr,l,r);
Pushup(rt);
return ans;
}
void Insert(int l,int r,int v){
int L=1,R=n,rt=1;
while(L!=R){
int mid=L+R>>1;
Modify(root[rt],1,n,l,r);
if(v<=mid){R=mid;rt*=2;}
else {L=mid+1;rt=rt*2+1;}
}
Modify(root[rt],1,n,l,r);
}
int Ask(int l,int r,int k){
int L=1,R=n,rt=1;
while(L!=R){
int mid=L+R>>1;
unsigned int ans=Query(root[rt*2],l,r);
if(ans>=k){R=mid;rt*=2;}
else {L=mid+1;rt=rt*2+1;k-=ans;}
}
return L;
}
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main(){
freopen("3110.in","r",stdin);
freopen("3110.out","w",stdout);
n=read();m=read();
for(int i=1;i<=m;i++){
int opt,a,b,c;
opt=read();a=read();b=read();c=read();
if(opt==1)Insert(a,b,n-c+1);
if(opt==2)printf("%d\n",n-Ask(a,b,c)+1);
}
return 0;
}
小结:今天一共做了5题，修改了1题，包括一道不能放上来的题目,UER7B,和上面这4题。
1:考察了对于题目的审题能力以及观察题目性质的能力，比如我在一开始没有想到排列的和这个性质导致无从下手。
2:直接做困难的dp应考虑怎么简化状态表示和选择合适的状态表示。
3:观察题目数据范围发现问题和性质。
4:注意极限情况下的数据值可能会爆int
UER7B:考虑划分答案。蒟蒻我表示很难想到啊
不能放上来的题:考虑正负号对答案的影响或许是相同的，所以要特判。
总的来说收获还是挺多的，希望在接下来的一段时间内能够总结更多的知识，不然复赛退役可不是闹着玩的(毕竟我已经高二了)
-------------------------
10.26
考了试然后瞬间爆炸
3题只有几十分
NOIP拿不到1=咯
-------------------------
10.27
休息一天?(其实我忘了我在干啥)
-------------------------
10.28
休息一天?(其实我忘了我在干啥)
-------------------------
10.29
考了一天试只有190拿不到1=咯
-------------------------
10.30
考了一天试只有180拿不到1=咯
-------------------------
10.31
被黑了一整天于是休息一天?(其实我忘了我在干啥)
好吧还是在bzoj上交了一个题
1.[BZOJ3304] [Shoi2005]带限制的最长公共子序列
状态加一维表示匹配到z串的哪个地方直接转移即可
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=505;
int dp[2][N][N],n1,n2,n3;
char s1[N],s2[N],s3[N];
int main(){
freopen("3304.in","r",stdin);
freopen("3304.out","w",stdout);
scanf("%s",s1+1);n1=strlen(s1+1);
scanf("%s",s2+1);n2=strlen(s2+1);
scanf("%s",s3);n3=strlen(s3);
for(register int i=1;i<=n1;i++){
int now=i&1,pre=now^1;
memset(dp[now],0,sizeof(dp[now]));
for(register int j=1;j<=n2;j++){
for(register int k=0;k<=n3;k++){
dp[now][j][k]=max(dp[now][j][k],max(dp[pre][j][k],dp[now][j-1][k]));
if(s1[i]==s2[j] && (k==0 || dp[pre][j-1][k])){
if(s1[i]==s3[k])dp[now][j][k+1]=max(dp[now][j][k+1],dp[pre][j-1][k]+1);
else dp[now][j][k]=max(dp[now][j][k],dp[pre][j-1][k]+1);
}
//printf("%d\n",dp[now][j][k]);
}
}
}
if(dp[n1&1][n2][n3]==0)puts("NO SOLUTION");
else printf("%d\n",dp[n1&1][n2][n3]);
return 0;
}
嗯，bzoj1009很有趣得在几天内A掉
-------------------------
11.1
睡觉睡掉了，最近需要好好休息一下
对了rky小号也上紫名了……这让大号还没紫的我情何以堪……
-------------------------
11.2
考试
爆炸
看着一个个神犇越来越强我却越来越弱的现实，却懒得去改变……难道真的要在NOIP2016直接退役吗
ZOJ挂了刷不了题目
只好做点简单题了
1.[BZOJ4326] NOIP2015 运输计划
我本来想用树链剖分，后来想了想还是看了下线性的神奇方法
好吧二分还是要二分的，只是判断线性
最近思维越来越差了
我的思路:二分答案$ans$，把所有大于$ans$的路径利用树链剖分实现路径加和路径取最大值
打标记实现，线段树节点保存当前最大次数和当前最大次数情况下的最大值
合并先比较次数，次数一样再取最大值
然后查询整棵树即可
但是这样单次判断是$O(mlogn)$的，总时间复杂度为$O(logmx\_len*mlogn)$
在CCF老爷机上就别想跑过去了
所以学习了一下树上前缀和
其实就是sum[u]++,sum[v]++,sum[lca]-=2;
然后dfs扫描一下就行
时间复杂度$O(logmx\_len*(logm+m+n))$
1A,总算缓解了一下考砸后糟糕的心情
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=300005;
int n,m,h[N],en,fa[N][20],sum[N],dfn[N],cnt,mx_len,dis[N][20],dep[N];
inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
struct Queries{
int l,r,v,lca;
friend inline bool operator<(const Queries &A,const Queries &B){return A.v<B.v;}
}que[N];
struct Edge{
int b,v,next;
}e[N<<1];
inline void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
void dfs(int u){
dfn[u]=++cnt;
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v==fa[u][0])continue;
fa[v][0]=u;
dis[v][0]=e[i].v;
dep[v]=dep[u]+1;
dfs(v);
}
}
inline void prepare(){
for(register int i=1;i<=19;i++){
for(register int j=1;j<=n;j++){
fa[j][i]=fa[fa[j][i-1]][i-1];
dis[j][i]=dis[j][i-1]+dis[fa[j][i-1]][i-1];
}
}
}
inline pair<int,int> dist(int u,int v){
int ans=0;
if(dep[u]<dep[v])swap(u,v);
int deep=dep[u]-dep[v];
for(int i=0;i<=19;i++)if((deep>>i)&1){ans+=dis[u][i];u=fa[u][i];}
for(int i=19;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
ans+=dis[u][i]+dis[v][i];
u=fa[u][i];
v=fa[v][i];
}
}
return u==v?make_pair(u,ans):make_pair(fa[u][0],ans+dis[u][0]+dis[v][0]);
}
int update(int u){
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v==fa[u][0])continue;
sum[u]+=update(v);
}
//printf("Smu:%d\n",sum[u]);
return sum[u];
}
inline bool solve(int x){
int l=1,r=m,mt=0,aw=0;
while(l<=r){
int mid=l+r>>1;
if(que[mid].v>x)r=mid-1;
else l=mid+1;
}
//printf("L:%d %d\n",l,x);
for(register int i=1;i<=n;i++)sum[i]=0;
for(register int i=l;i<=m;i++){
sum[que[i].l]++;
sum[que[i].r]++;
sum[que[i].lca]-=2;
mt=max(mt,que[i].v-x);
}
update(1);
for(register int i=1;i<=n;i++)if(sum[i]==(m-l+1))aw=max(aw,dis[i][0]);
//printf("mt:%d %d\n",mt,aw);
return mt<=aw;
}
void div2(){
int l=0,r=mx_len;
while(l<=r){
int mid=l+r>>1;
if(solve(mid))r=mid-1;
else l=mid+1;
}
printf("%d\n",l);
}
int main(){
freopen("4326.in","r",stdin);
freopen("4326.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<n;i++){
static int u,v,w;
Read(u);Read(v);Read(w);
AddEdge(u,v,w);AddEdge(v,u,w);
}
for(register int i=1;i<=m;i++){Read(que[i].l);Read(que[i].r);}
dfs(1);
prepare();
for(register int i=1;i<=m;i++){
pair<int,int> Pr=dist(que[i].l,que[i].r);
que[i].v=Pr.second;
que[i].lca=Pr.first;
mx_len=max(mx_len,que[i].v);
}
sort(que+1,que+m+1);
div2();
return 0;
}
-------------------------
11.3
日常颓废
1.[BZOJ4066] 简单题
啊……为了调试方便把x^=lastans注释掉了……然后提交时一直忘了加上去
最后就创下了单题提交12次的记录……最后一次才发现……
本身是裸KD树
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200005,INF=2100000000;
int n,sort_tag,cnt,root;
long long lastans;
struct KDTree{
int l,r,d[2],mx[2],mn[2];
long long sum,v;
KDTree(){l=r=d[0]=d[1]=mx[0]=mn[0]=mx[1]=mn[1]=sum=v=0;}
friend inline bool operator<(const KDTree &A,const KDTree &B){return A.d[sort_tag]<B.d[sort_tag];}
}tree[N];
inline void Pushup(int rt){
tree[rt].mx[0]=tree[rt].mn[0]=tree[rt].d[0];
tree[rt].mx[1]=tree[rt].mn[1]=tree[rt].d[1];
tree[rt].sum=tree[rt].v;
if(tree[rt].l){
tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].l].mx[0]);
tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].l].mx[1]);
tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].l].mn[0]);
tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].l].mn[1]);
tree[rt].sum+=tree[tree[rt].l].sum;
}
if(tree[rt].r){
tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].r].mx[0]);
tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].r].mx[1]);
tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].r].mn[0]);
tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].r].mn[1]);
tree[rt].sum+=tree[tree[rt].r].sum;
}
}
int Rebuild(int l,int r,int D){
sort_tag=D;
int mid=l+r>>1;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mx[0]=tree[mid].mn[0]=tree[mid].d[0];
tree[mid].mx[1]=tree[mid].mn[1]=tree[mid].d[1];
tree[mid].l=tree[mid].r=0;
if(l<mid)tree[mid].l=Rebuild(l,mid-1,!D);
if(r>mid)tree[mid].r=Rebuild(mid+1,r,!D);
Pushup(mid);
return mid;
}
template<typename T>inline void ReadO(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
template<typename T>inline void Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
x^=lastans;
}
inline int AddKDNode(int x,int y,int z){
tree[++cnt].d[0]=x;
tree[cnt].d[1]=y;
tree[cnt].v=z;
Pushup(cnt);
return cnt;
}
int Add(int rt,int d0,int d1,int val,bool D){
if(!rt)return AddKDNode(d0,d1,val);
if(tree[rt].d[0]==d0 && tree[rt].d[1]==d1){tree[rt].v+=val;tree[rt].sum+=val;return rt;}
if(D){
if(d1<tree[rt].d[D])tree[rt].l=Add(tree[rt].l,d0,d1,val,!D);
else tree[rt].r=Add(tree[rt].r,d0,d1,val,!D);
}
else {
if(d0<tree[rt].d[D])tree[rt].l=Add(tree[rt].l,d0,d1,val,!D);
else tree[rt].r=Add(tree[rt].r,d0,d1,val,!D);
}
Pushup(rt);
return rt;
}
long long Sum(int rt,int x1,int y1,int x2,int y2,int D){
if(!rt)return 0ll;
long long ans=0;
if(y1>tree[rt].mx[1] || y2<tree[rt].mn[1] || x1>tree[rt].mx[0] || x2<tree[rt].mn[0])return 0ll;
if(y1<=tree[rt].mn[1] && tree[rt].mx[1]<=y2 && x1<=tree[rt].mn[0] && tree[rt].mx[0]<=x2)return tree[rt].sum;
if(y1<=tree[rt].d[1] && tree[rt].d[1]<=y2 && x1<=tree[rt].d[0] && tree[rt].d[0]<=x2)ans+=tree[rt].v;
ans+=Sum(tree[rt].l,x1,y1,x2,y2,!D)+Sum(tree[rt].r,x1,y1,x2,y2,!D);
return ans;
}
int main(){
freopen("4066.in","r",stdin);
freopen("4066.out","w",stdout);
ReadO(n);tree[0].d[0]=tree[0].d[1]=INF;
while(1){
static int opt,x1,y1,x2,y2;
ReadO(opt);
if(opt==1){Read(x1);Read(y1);Read(x2);root=Add(root,x1,y1,x2,0);if(cnt%10000==0)root=Rebuild(1,cnt,0);}
if(opt==2){Read(x1);Read(y1);Read(x2);Read(y2);printf("%lld\n",lastans=Sum(root,x1,y1,x2,y2,0));}
if(opt==3)return 0;
}
return 0;
}
2.[BZOJ1013] [JSOI2008]球形空间产生器sphere
画一下式子发现拆开来就是一堆方程，半径什么的都可以消掉
直接高斯消元解方程即可
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15;
const double eps=1e-9;
int n;
double px[N];
struct Equa{
double p[N];
Equa(){for(register int i=0;i<N;i++)p[i]=0.0;}
}poi[N];
inline double Abs(const double &x){return x>0?x:-x;}
inline void Gauss(){
int j;
for(register int i=1;i<=n;i++){
for(j=i;j<=n;j++)if(Abs(poi[j].p[i])>eps)break;
if(i!=j)for(register int k=1;k<=n+1;k++)swap(poi[i].p[k],poi[j].p[k]);
double w=poi[i].p[i];
for(register int k=1;k<=n+1;k++)poi[i].p[k]/=w;
for(register int k=1;k<=n;k++){
if(k==i)continue;
w=poi[k].p[i];
for(register int l=1;l<=n+1;l++)poi[k].p[l]-=w*poi[i].p[l];
}
}
}
int main(){
freopen("1013.in","r",stdin);
freopen("1013.out","w",stdout);
scanf("%d",&n);
for(register int i=1;i<=n;i++)scanf("%lf",&px[i]);
for(register int i=1;i<=n;i++){
for(register int j=1;j<=n;j++){
static double x;
scanf("%lf",&x);
poi[i].p[j]=2.0*(x-px[j]);
poi[i].p[n+1]+=x*x-px[j]*px[j];
}
}
Gauss();
for(register int i=1;i<n;i++)printf("%.3lf ",poi[i].p[n+1]);
printf("%.3lf\n",poi[n].p[n+1]);
return 0;
}
3.[BZOJ1831] [AHOI2008]逆序对
难得的看出来的题目……
总之选择的数成一个不下降序列
所以直接dp就行
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=10005,K=105;
int n,k,a[N],pos[N],pcnt;
long long dp[N][K],g[N][K],f[N][K],ans;
int main(){
freopen("1831.in","r",stdin);
freopen("1831.out","w",stdout);
scanf("%d %d",&n,&k);
for(register int i=1;i<=n;i++)scanf("%d",&a[i]);
for(register int i=1;i<=n;i++){
if(a[i]==-1)pos[++pcnt]=i;
else for(register int j=1;j<a[i];j++)g[i][j]++;
for(register int j=1;j<=k;j++)g[i][j]+=g[i-1][j];
if(a[i]!=-1)ans+=g[i][a[i]];
}
for(register int i=n;i>=1;i--){
if(a[i]!=-1)for(register int j=a[i]+1;j<=k;j++)f[i][j]++;
for(register int j=1;j<=k;j++)f[i][j]+=f[i+1][j];
}
for(register int i=1;i<=pcnt;i++){
long long d=1ll<<62;
for(register int j=1;j<=k;j++){
d=min(d,dp[i-1][j]);
dp[i][j]=d+f[pos[i]][j]+g[pos[i]][j];
}
}
long long d=1ll<<62;
for(register int i=1;i<=k;i++)d=min(d,dp[pcnt][i]);
printf("%lld\n",d+ans);
return 0;
}
11.4-11.9
复习以及准备期中考试，暂不更新
-------------------------
