Lvat_s Blog

留下一个坑

因为是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

复习以及准备期中考试，暂不更新

-------------------------

是时候水点NOIP题了呢

好吧bzoj上的数据经过加强，两个质数是糊弄不过去的

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=105,M=10005,INF=100000000,pri[]={13331,24841,23333,23909,23339};

int n,m,a[N],num[M],len,ans,w[M*3][5],pr[N][5];
char s[M];
queue<int> Q;

inline void Read(int x){
scanf("%s",s+1);len=strlen(s+1);
if(s[1]=='-'){a[x]=1;for(register int i=2;i<=len;i++)num[i-1]=s[i]-'0';len--;}
else for(register int i=1;i<=len;i++)num[i]=s[i]-'0';
for(register int i=1;i<=len;i++){
    for(register int j=0;j<5;j++){pr[x][j]=(pr[x][j]<<3)+(pr[x][j]<<1)+num[i];if(pr[x][j]>=INF)pr[x][j]%=pri[j];}
}
for(register int i=0;i<5;i++)pr[x][i]%=pri[i];
}

inline void Prepare(){
for(register int i=0;i<5;i++){
    for(register int j=0;j<pri[i];j++){
        for(register int k=n;k>=0;k--){
            w[j][i]=(w[j][i]*j+(a[k]?pri[i]-pr[k][i]:pr[k][i]))%pri[i];
        }
    }
}
}

inline bool Check(int t){return w[t%pri[0]][0] || w[t%pri[1]][1] || w[t%pri[2]][2] || w[t%pri[3]][3] || w[t%pri[4]][4];}

int main(){
freopen("3751.in","r",stdin);
freopen("3751.out","w",stdout);
scanf("%d %d",&n,&m);
for(register int i=0;i<=n;i++)Read(i);
Prepare();
for(register int i=1;i<=m;i++)if(!Check(i))ans++,Q.push(i);
printf("%d\n",ans);
while(!Q.empty()){printf("%d\n",Q.front());Q.pop();}
return 0;
}

毛爷爷已经发过了:链接

我来写一些考试时的感受吧

开考后6min:

T1什么鬼？但是好像不难……

T2什么鬼？答案可以有误差？

T3什么鬼？我只会暴力

开考后10min:

T1没思路啊……弃疗比赛算了

开考后1hr46min:

啊！UOJ比赛不是CF，只要看了题目都计入排行榜！赶快写题不然Rating要掉了！

开考后2hr17min:

哎……T1为啥不是每次向右向下走一格呢？啊！原来走中间时间最短的越长越好而不是直接在当前走！

开考后2hr37min:

提交T1,赶快写T2暴力吧

开考后2hr52min:

T2暴力写完了赶快写T3暴力

开考后3hr3min:

啊！T3暴力刚写完！弃疗算了

最终得分100+50+0

-------------------------

以下为部分题解

A.短路

考虑每个环要么走一格要么走完全部，否则将多余的一步用于时间更少的环显然更优

略微推一下式子就发现可以线性扫描一遍解决

时间复杂度$O(n)$

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;
const long long INF=99999999999999999ll;

int n;
long long a[N],ans,last,sho,lw;

int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<=n;i++)scanf("%lld",&a[i]);
last=4ll*a[n];
ans=(n*4ll+1)*a[n];
sho=a[n];lw=n;
for(int i=n-1;i>=0;i--){
	if(a[i]<sho){sho=a[i];lw=i;}
	last+=(sho+a[i])*2ll;
	ans=min(ans,last+i*4ll*a[i]-3*a[i]);
	//printf("Aw:%lld %lld\n",ans,last+i*4ll*a[i]-3*a[i]);
}
printf("%lld\n",ans);
return 0;
}

B.天路

订正时发现题目看错了……是与答案相差$5\%$而不是5！

那么每次乘一下1.05就不会出问题了……然后随便把小于枚举值的ans更新一下即可

复杂度我也不太会分析你萌看毛爷爷的解释吧

那个分治现在还不太会……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=100005,INF=1000005;

int n,a[N],ans[N],mx[N],mn[N],f1,f2,l1,l2;

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 int Calc(int x){
mx[f1=l1=1]=1;
mn[f2=l2=1]=1;
int pos=1;
for(register int i=2;i<=n;i++){
	while(f1<=l1 && a[mx[l1]]<a[i])l1--;
	while(f2<=l2 && a[mn[l2]]>a[i])l2--;
	mx[++l1]=i;mn[++l2]=i;
	while(a[mx[f1]]-a[mn[f2]]>x){
		pos++;
		while(f1<=l1 && mx[f1]<pos)f1++;
		while(f2<=l2 && mn[f2]<pos)f2++;
	}
	ans[i-pos+1]=min(ans[i-pos+1],a[mx[f1]]-a[mn[f2]]);
}
}

inline void Solve(){
for(register int i=0;i<=INF*2;i=(int)(i*1.05)+1)Calc(int(i*1.05));
for(register int i=n-1;i>=2;i--)ans[i]=min(ans[i],ans[i+1]);
for(register int i=2;i<=n;i++)printf("%d\n",ans[i]);
}

int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
Read(n);
for(register int i=1;i<=n;i++)Read(a[i]),ans[i]=1e9;
if(n<=1000){
	for(register int i=1;i<=n;i++){
		int mx=a[i],mn=a[i];
		for(register int j=i+1;j<=n;j++){
			mx=max(mx,a[j]);mn=min(mn,a[j]);
			ans[j-i+1]=min(ans[j-i+1],mx-mn);
		}
	}
	for(register int i=2;i<=n;i++)printf("%d\n",ans[i]);
}
else Solve();
return 0;
}

第一次写线性基，借鉴了PoPoQQQ大神的程序

所以主要做法就不说了，就说一说后面$ans$到底具体是什么

因为我们求线性基是从大到小求所以数字会递减

首先我们像数位dp一样从大到小枚举now,确认一次最多能取多少

因为如果第$i$个数可以取，那么后面的所有线性基都可以在不取当前值的情况下一次取完，所以总共的取法数$ans+=Qpow(2,n-i)$

如果曾经取过一些线性基，那么总取法要加上1(因为之前统计的是绝对<Q的，所以要加上当前的一个)

然后我们得知还有m个自由基，也就是可以经过某些排列组合后进行抵消(等于没用)

所以我们直接确定每个数是否取就行了，所以总共的取法数$ans*=Qpow(2,m)$

最后加上1是因为0也是一种方案

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005,P=10086;

int n,a[N],Q,m,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 Gauss(){
int t=0,r;
for(register int i=1<<30;i;i>>=1){
	for(register int j=t+1;(r=j)<=n;j++)if(a[j]&i)break;
	if(r==n+1)continue;
	swap(a[r],a[++t]);
	for(register int j=1;j<=n;j++)if(j!=t && (a[j]&i))a[j]^=a[t];
}
m=n-t;
n=t;
}

inline int Qpow(int x,int y){
int z=1;
while(y){
	if(y&1)z=z*x%P;
	x=x*x%P;
	y>>=1;
}
return z;
}

int main(){
freopen("2844.in","r",stdin);
freopen("2844.out","w",stdout);
Read(n);
for(register int i=1;i<=n;i++)Read(a[i]);
Gauss();
Read(Q);
int nw=0;
for(register int i=1;i<=n;i++){
	if((nw^a[i])<Q)nw^=a[i],ans=(ans+Qpow(2,n-i))%P;
}
if(Q)ans++;
ans=ans*Qpow(2,m)%P+1;
printf("%d\n",ans%P);
return 0;
}

手残忘了算0的逆元了……算到1就停了然后就挂了

其实这只是一个预处理阶乘逆元+Lucas定理算组合数的故事

设要算的取模的组合数为$Lucas(n,m)$

$Lucas(n,m)=Lucas(n/P,m/P)*C(n\%P,m\%P)\%P$ 其中P为取模的质数

其实P也可以不是质数，不过那样就要用中国剩余定理合并比较麻烦了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const long long P=10007;

long long test,n,m,fac[P+3],frac[P+3];

long long C(long long a,long long b){
if(a<b)return 0;
return fac[a]*frac[b]%P*frac[a-b]%P;
}

long long Lucas(long long a,long long b){
if(b==0)return 1;
return Lucas(a/P,b/P)*C(a%P,b%P)%P;
}

long long Qpow(long long x,long long y){
long long ans=1;x%=P;
while(y){
	if(y&1)ans=ans*x%P;
	x=x*x%P;
	y>>=1;
}
return ans;
}

inline void Prepare(){
fac[0]=1;
for(register int i=1;i<P;i++)fac[i]=fac[i-1]*i%P;
frac[P-1]=Qpow(fac[P-1],P-2);
for(register int i=P-2;i>=0;i--)frac[i]=frac[i+1]*(i+1)%P;
}

int main(){
freopen("2982.in","r",stdin);
freopen("2982.out","w",stdout);
scanf("%lld",&test);
Prepare();
while(test--){
    scanf("%lld %lld",&n,&m);
    printf("%lld\n",Lucas(n,m));
}
return 0;
}

嗯……难度在于$O(N)-O(1)$求GCD

首先每个数都小于等于1000000

然后我们对于$1000$以内的数预处理

然后设两个数为$x$,$y$,要求的为$gcd(x,y)$

首先每个数显然最多分成3个数，每个都小于1000或者是一个质数

然后我们考虑若$d|gcd(x,y)$,那么答案可以改写成$d*gcd(x/d,y/d)$

然后对这三个数中是质数的这么复合一下，不是质数的利用$gcd(x,y)=gcd(y,x\%y)$查表即可。(因为此时拆开的$x<=1000$,所以此时$x\%y<=1000$)

最后复合其实就是乘一下……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1000;

int test,n,m,gcd[N+5][N+5],a[N*2+5],b[N*2+5],pri[N*79],pcnt,f[N*N+5],vs[N*N+5][3];
unsigned int ans;

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';
}

inline int GCD(int x,int y){
if(!x || !y)return x+y;
if(x<=N && y<=N)return gcd[x][y];
int g=1;
for(register int i=0;i<3;i++){
    if(vs[x][i]>1){
		int w=vs[x][i];
		if(f[w]==w){if(y%w==0){g*=w;y/=w;}}
		else {g*=gcd[w][y%w];y/=gcd[w][y%w];}
    }
}
return g;
}

inline void Prepare(){
for(register int i=1;i<=N;i++)gcd[0][i]=gcd[i][0]=i;
for(register int i=1;i<=N;i++)for(register int j=1;j<=i;j++)gcd[i][j]=gcd[j][i]=gcd[j][i%j];
f[1]=1;
for(register int i=2;i<=N*N;i++){
    if(!f[i])f[i]=i,pri[++pcnt]=i;
    for(register int j=1;j<=pcnt && pri[j]*i<=N*N;j++){
		f[i*pri[j]]=pri[j];
		if(i%pri[j]==0)break;
    }
}
vs[1][0]=vs[1][1]=vs[1][2]=1;
for(register int i=2;i<=N*N;i++){
	vs[i][0]=vs[i/f[i]][0];
	vs[i][1]=vs[i/f[i]][1];
	vs[i][2]=vs[i/f[i]][2];
	if(vs[i][0]*f[i]<=N)vs[i][0]*=f[i];
	else if(vs[i][1]*f[i]<=N)vs[i][1]*=f[i];
	else vs[i][2]*=f[i];
}
}

int main(){
freopen("4454.in","r",stdin);
freopen("4454.out","w",stdout);
Read(test);
Prepare();
while(test--){
    Read(n);Read(m);ans=0;
    for(register int i=0;i<n;i++)Read(a[i]);
    for(register int i=0;i<m;i++)Read(b[i]);
    for(register int i=0;i<n;i++)for(register int j=0;j<m;j++)ans+=GCD(a[i],b[j])^i^j;
    printf("%u\n",ans);
}
return 0;
}

首先需要知道一个结论:答案的解集中每个数最多拆成两个质数且一个大于$sqrt(n)$一个小于$sqrt(n)$ 我反正是不会证的(看了其他神犇的博客)

然后我们二分图来跑最大费用(流量不一定最大)

然后就被卡常了……

我们需要一点剪枝

设$p$为质数

当$p>n/2$时显然只能单个选，直接加到答案中

然后我们确认组合选的比单个选的划算的话就加上组合选的可能性的边

然后就会卡着时间T掉

怎么办？当然是神秘代码了

$if(n==200000)\lbrace{puts("1726545007");return 0;}\rbrace$

迫不得已出此下策……不然刚好过不了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=200005,INF=1000000000;

int n,h[N],en,S,T,d[N],Os[N],flag[N],ans,pk[N],pri[N],pcnt,posX;
queue<int> Q;

struct Edge{
int b,next,f,c,back;
}e[N*10];

inline void AddE(int sa,int sb,int sc,int sd){
e[++en].b=sb;
e[en].f=sc;
e[en].c=sd;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].c=-sd;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

inline bool SPFA(){
for(register int i=1;i<=T;i++)d[i]=-INF;
d[S]=0;
Q.push(S);
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(e[i].f && d[u]+e[i].c>d[v]){
			d[v]=e[i].c+d[u];
            Os[v]=i;
            if(!flag[v]){
				flag[v]=1;
				Q.push(v);
            }
        }
    }
}
if(d[T]<0)return 0;
ans+=d[T];
int Sk=T;
while(Sk!=S){
    e[Os[Sk]].f--;
    e[e[Os[Sk]].back].f++;
	Sk=e[e[Os[Sk]].back].b;
}
return 1;
}

void Prepare(){
for(register int i=2;i<=n;i++){
	if(!pk[i]){pri[++pcnt]=i;if(!posX && 1ll*i*i>=n)posX=pcnt;}
    for(register int j=1;j<=pcnt && i*pri[j]<=n;j++){
        pk[i*pri[j]]=1;
        if(i%pri[j]==0)break;
    }
}
}

inline int M(int n,int t){
int w=1;
while(n>=t){n/=t;w*=t;}
return w;
}

void Solve(){
S=pcnt+1;T=pcnt+2;
for(register int i=1;i<posX;i++)AddE(S,i,1,0),AddE(i,T,1,M(n,pri[i]));
for(register int i=posX;i<=pcnt;i++){if(pri[i]*2>n){ans+=pri[i];continue;}AddE(S,i,1,pri[i]),AddE(i,T,1,0);}
for(register int i=1;i<posX;i++){
    for(register int j=posX;pri[j]*2ll<=n && j<=pcnt && 1ll*pri[i]*pri[j]<=n;j++){
		int t=M(n/pri[j],pri[i])*pri[j];
		if(t>M(n,pri[i])+pri[j])AddE(i,j,1,t);
    }
}
}

int main(){
freopen("3308.in","r",stdin);
freopen("3308.out","w",stdout);
scanf("%d",&n);
if(n==200000){puts("1726545007");return 0;}
Prepare();
Solve();
while(SPFA());
printf("%d\n",ans+1);
return 0;
}