BZOJ乱炖
HJWJBSR
posted @ 2015年11月01日 23:53
in 题解
, 650 阅读
感觉CF单子上面的题目到后面越来越做不动
英文的题面、题解啃得人效率低下，时间一长就越来越萎
现在简直有种稍微要注意点细节的题都会挂的感觉
于是赶紧补一波BZOJ乱炖，感觉去年省选题很好玩的样子于是来一波好了
主要还是要找状态，找智商
现在完成了：
50/50
[UPD 11.10]：进度又要缓一缓了，决定现在去复习一下以前学的东西还有做过的题目，然后把CC打掉再回来继续填。感觉很多基础的东西学过都忘记了。
BZOJ4032：简直有毒啊这题，脑洞了好久终于把四问全部搞出来了。。跪拜考场还可以A掉这题的ZRT大爷。。第一问，SAM上面跑一跑。第二问枚举左端点然后每次右端点移一位，判断O(n)暴力。第三问，建出B串trie树然后遍历一遍，一开始觉得不行但是只要枚举不能到达的字符然后看A串这个点后面有没有对应字符就好了。第四问，DP求出A串每个位置能够对应B串哪些位置，而且两者都必须尽量往左靠，转移是O(n)的对于每个节点，因为要往左靠所以最多26个可达状态。。然后就可以搞一搞了。。（话说序列自动机呢。。）话说除了SAM还有少特判一些情况都一遍写对了真是感动啊。。把代码放上来好了。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 2050
#define M 2000050
#define P 26
struct Node
{
Node *suf,*go[P];int val,mi;bool b;
} statePool[N*2],*cur,*root,*last;
struct Point
{Point *go[P];int h;} StatePool[M],*Root,*Cur;
char a[N],b[N];int n,m,nA[N][P],nB[N][P],s[N][N];bool c[N][N];
void Pretreat()
{
for (int i=1;i<=n;i++) a[i]-='a';
for (int i=1;i<=m;i++) b[i]-='a';
for (int i=n-1;i>=0;i--)
memcpy(nA[i],nA[i+1],sizeof nA[i+1]),nA[i][a[i+1]]=i+1;
for (int i=m-1;i>=0;i--)
memcpy(nB[i],nB[i+1],sizeof nB[i+1]),nB[i][b[i+1]]=i+1;
for (int i=0;i<P;i++)
if (nA[0][i]&&!nB[0][i])
{puts("1\n1\n1\n1");exit(0);}
}
struct Get_Ans1
{
void extend(int w)
{
Node *p=last,*np=cur++;
np->val=p->val+1;
while (p!=NULL&&!p->go[w])
p->go[w]=np,p=p->suf;
if (p==NULL)
np->suf=root; else
{
Node *q=p->go[w];
if (q->val==p->val+1)
np->suf=q; else
{
Node *nq=cur++;
memcpy(nq->go,q->go,sizeof q->go);
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
while (p!=NULL&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;
}
void Get_Mi()
{
Node* li[N*2];int le=1,ri=1;
li[1]=root;
for (;le<=ri;le++)
for (int i=0;i<P;i++)
if (li[le]->go[i]&&!li[le]->go[i]->b)
li[++ri]=li[le]->go[i],li[ri]->b=true,
li[ri]->mi=li[le]->mi+1;
}
int Solve()
{
cur=statePool;root=last=cur++;
for (int i=1;i<=m;i++) extend(b[i]);
Get_Mi();int ri=0,ans=M;Node* now=root;
for (int i=1;i<=n;i++)
{
while (ri<n&&now->go[a[ri+1]])
now=now->go[a[++ri]];
if (ri==n) break;
ans=min(ans,ri-i+2);
if (now!=root&&now->mi==ri-i+1)
now=now->suf;
if (ri<i) ri=i;
}
return ans==M?-1:ans;
}
} GA1;
struct Get_Ans2
{
bool Check(char* a,int len)
{
for (int i=1,now=0;i<=len;i++)
if (!nB[now][a[i]]) return false; else
now=nB[now][a[i]];
return true;
}
int Solve()
{
int ri=0,ans=M;
for (int i=1;i<=n;i++)
{
while (ri<n&&Check(&a[i-1],ri-i+2)) ri++;
if (ri==n) break;ans=min(ans,ri-i+2);
}
return ans==M?-1:ans;
}
} GA2;
struct Get_Ans3
{
void Set(char* a,int len)
{
Point* now=Root;
for (int i=1;i<=len;i++)
{
if (!now->go[a[i]])
now->go[a[i]]=Cur,Cur->h=now->h+1,Cur++;
now=now->go[a[i]];
}
return;
}
int DFS(Point* now,int Now)
{
int ans=M;
for (int i=0;i<P;i++)
if (now->go[i]&&nA[Now][i])
ans=min(DFS(now->go[i],nA[Now][i]),ans); else
if (now->go[i]==NULL&&nA[Now][i])
ans=min(ans,now->h+1);
return ans;
}
int Solve()
{
Cur=StatePool;Root=Cur++;
for (int i=1;i<=m;i++) Set(&b[i-1],m-i+1);
int ans=DFS(Root,0);return ans==M?-1:ans;
}
} GA3;
struct Get_Ans4
{
inline void Update(int &x,int y)
{x=!x?y:min(x,y);}
int Solve()
{
int ans=M;
for (int i=0;i<P;i++)
c[nA[0][i]][nB[0][i]]=true,s[nA[0][i]][nB[0][i]]=1;
for (int i=1;i<n;i++)
for (int j=0;j<P;j++)
if (nA[i][j])
for (int k=1;k<=m;k++)
if (c[i][k])
if (nB[k][j])
c[nA[i][j]][nB[k][j]]=true,
Update(s[nA[i][j]][nB[k][j]],s[i][k]+1); else
ans=min(ans,s[i][k]+1);
return ans==M?-1:ans;
}
} GA4;
int main()
{
gets(a+1);gets(b+1);n=strlen(a+1);m=strlen(b+1);Pretreat();
printf("%d\n%d\n%d\n%d\n",GA1.Solve(),GA2.Solve(),GA3.Solve(),GA4.Solve());
return 0;
}
BZOJ4030：首先把妹计划必须要是升序的，这个显然，而且也证明的出来：首先可以把0位置上面放一个0还有第n+1位置上面放一个1答案不会改变，这是方便运算用的。i从1到n扫一遍当第i小的数不在位置i的时候它两边肯定都比它大（因为已经处理了1~i-1了），然后把它放到位置i答案肯定会变优，这个推下式子一下就可以很看出这个操作对答案的贡献是非正的。因为除了从小到大排序之外总可以找到这样的i所以只有从小到大排序是最优的2333。剩下不会了，当然我还是会喜闻乐见猜结论，写了个暴力玩了玩感觉答案是1~i和j~n的并，然后就是扫一遍的事情了。。（跟过了的大爷们的做法明明是一样的）写起来蛋疼的一笔。。我想我已经调到极限了，我拍了很久都没有错，可能是些特殊情况吧。。总之虽然没过代码先放上来好了。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 200050
#define fr first
#define sc second
#define ll long long
#define ld long double
ld ans;int n,m,t;ll Aha,s[N][2];
pair <ld,int> li[N],Emp;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline ld min(ld x,ld y)
{return x<y?x:y;}
inline ll min(ll x,ll y)
{return x<y?x:y;}
inline ld Calc(ld x,ld y)
{return x*(1-y);}
int main()
{
//freopen("input.txt","r",stdin);
t=Read();
while (t--)
{
n=Read();m=Read();Aha=0;
int st=0;
for (int i=1;i<=n;i++)
{
int k=Read(),l=Read();st++;
li[i].fr=1-(ld)(k)/l;
Aha+=(li[i].sc=Read());
if (!li[i].sc) st--;
}
li[n+1]=Emp;
n=st;sort(li+1,li+n+1);s[n+1][1]=0;
for (int i=1;i<=n;i++) s[i][0]=s[i-1][0]+li[i].sc;
for (int i=n;i>=1;i--) s[i][1]=s[i+1][1]+li[i].sc;
int le=0,cnt=0,ri=n+1;ld Ans=0;
while (s[ri][1]<m)
{
ri--;
if (ri!=n) Ans+=Calc(li[ri].fr,li[ri+1].fr);
Ans+=(min(s[ri][1],m)-s[ri+1][1]-1)*
Calc(li[ri].fr,li[ri].fr);
}
ans=Ans;
while (cnt!=m)
{
int k;
if (s[le][0]==cnt||s[ri+1][1]+1==m-cnt) k=1; else
k=min(m-cnt,min(s[le][0]-cnt,m-cnt-s[ri+1][1]-1));
if (s[le][0]==cnt)
Ans+=Calc(li[le].fr,li[le+1].fr),le++; else
Ans+=k*Calc(li[le].fr,li[le].fr);
if (s[ri+1][1]+1==m-cnt)
Ans-=ri==n?0:Calc(li[ri].fr,li[ri+1].fr),ri++; else
Ans-=k*Calc(li[ri].fr,li[ri].fr);
cnt+=k;
ans=min(ans,Ans+Calc(cnt==m?0:li[le].fr,li[ri].fr));
}
printf("%.6lf\n",(double)fabs(ans));
}
return 0;
}
BZOJ4028：简直smg。。开始搞了好久发现看错题了。。想了一想感觉复杂度好玄学。。这smg题啊劳资弃坑了！！
HEOI终于完结，贵省考的真瘠薄。（所以还是要膜这种狗哔题目能屠场的ZRT大爷啊
BZOJ4004：虽然不知道线性基这种高端东西，不过还是成功YY粗了做法。玛德eps开小了wa了n遍简直日。。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 505
#define eps 1e-5
double v[N][N],Aha[N][N];
int n,m,t[N],sg[N],st,ans;bool b[N];
inline bool cmp(int x,int y)
{return t[x]<t[y];}
void Solve(int x)
{
for (int i=1;i<=m;i++)
if (fabs(v[x][i])>eps)
if (!b[i])
{
for (int j=i;j<=m;j++) Aha[i][j]=v[x][j];
st++;b[i]=true;ans+=t[x];return;
} else
{
double k=v[x][i]/Aha[i][i];
for (int j=i;j<=m;j++) v[x][j]-=Aha[i][j]*k;
}
return;
}
int main()
{
cin >>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) scanf("%lf",&v[i][j]);
for (int i=1;i<=n;i++)
scanf("%d",&t[i]),sg[i]=i;
sort(sg+1,sg+n+1,cmp);st=0;
for (int i=1;i<=n&&st!=m;i++) Solve(sg[i]);
cout <<st<<' '<<ans<<endl;
return 0;
}
BZOJ4002：看完题解才发现其实提示都还是蛮明显的= =主要是看那个下取整就不敢做了以为要用到一些特别高妙的方法。其实只要跟斐波那契数列递推式联系一下就会发现求的这东西是通项公式的一部分，另外一部分是小于1的。模数好诡异，乘二爆long long？
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll unsigned long long
const ll P=7528443412579576937LL;
ll n,m,p;
struct Point {ll a[2][2];} Ans,C;
ll Quick_Multi(ll x,ll y)
{
ll z=0;
while (y)
{
if (y&1) z=(z+x)%P;
x=(x+x)%P;y >>= 1;
}
return z;
}
inline void Add(ll &x,ll y)
{x+=y;if (x>=P) x-=P;}
Point operator* (const Point &x,const Point &y)
{
memset(C.a,0,sizeof(C.a));
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
for (int k=0;k<2;k++)
Add(C.a[i][k],Quick_Multi(x.a[i][j],y.a[j][k]));
return C;
}
void Quick_Power(ll y)
{
Point x=(Point){{{0,(m-n*n)/4},{1,n}}},
z=(Point){{{2,n},{0,0}}};
while (y)
{
if (y&1) z=z*x;
x=x*x;y >>= 1;
}
Ans=z;
}
int main()
{
cin >>n>>m>>p;
if (p==0) {puts("1");return 0;}
Quick_Power(p-1);
cout <<(Ans.a[0][1]+P-(m!=n*n&&!(p&1)))%P<<endl;
return 0;
}
BZOJ4007：萎爆了= =没想出来= =。直接DP就好了，设状态设的是所有父亲的状态，就是状压一下然后从下往上扫一遍就好了= =哦还有层限制，那就只要加一维状态当前子树有多少个打仗的就好了。日BZOJ上面的题面误我青春，我还以为说的是m<=2*n。总复杂度随便算下发现是2^(2*n)*n左右的，虚虚的但也不是不能过。恶心不过卡内存！也就是说重写了三次：第一次被狗哔题面卡住了，第二次脑洞大开写了个map真是2333，第三次用2^2n个vector存了这东西但是发现就算释放内存还是挂掉的真尼玛愉快啊2333。换成递归形式就能过？空间还只用了9M？难道递归完了里面的空间会回收的？
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define N 1050
#define M 22
int a2[M],n,m,a[N][N][2],A2[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
vector <int> Get_Ans(int x,int y,int z)
{
vector <int> s;
if (x>=a2[n-1])
{s.push_back(a[x][y][0]);s.push_back(a[x][y][1]);return s;}
vector <int> q,w,e,r;
q=Get_Ans(x*2,y*2,z+1);w=Get_Ans(x*2,y*2+1,z+1);
e=Get_Ans(x*2+1,y*2,z+1);r=Get_Ans(x*2+1,y*2+1,z+1);
int sz=a2[n-z]+1,len1=q.size(),len2=w.size(),len3=e.size(),len4=r.size();
for (int i=0;i<sz;i++) s.push_back(0);
for (int i=0;i<len1;i++)
for (int j=0;j<len3;j++) s[i+j]=max(s[i+j],q[i]+e[j]);
for (int i=0;i<len2;i++)
for (int j=0;j<len4;j++) s[i+j]=max(s[i+j],w[i]+r[j]);
return s;
}
int main()
{
n=Read();m=Read();a2[0]=1;
for (int i=1;i<=n;i++) A2[a2[i]=a2[i-1] << 1]=i;
for (int t=1;t>=0;t--)
for (int i=a2[n-1];i<a2[n];i++)
{
for (int j=1;j<n;j++)
{
int e=Read(),l=a2[n-1]-1-a2[j-1];
for (int k=l;k;k=(k-1)&l) a[i][k+a2[j-1]*t][t]+=e;
a[i][a2[j-1]*t][t]+=e;
}
}
vector <int> Ans=Get_Ans(1,0,0);int ans=0;
for (int i=0;i<=m;i++) ans=max(ans,Ans[i]);
cout <<ans<<endl;
return 0;
}
BZOJ4006：斯坦纳树显然，多出来的条件直接套个DP就好了。。复杂度很虚？管它的能过就行。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define N 1050
#define M 6050
#define P 12
#define INF 0x3f7f7f7f
int fi[N],c[M][3],ss=1,mi[N][N],n,m,p,a[N],Sg[P],a2[P],v[P];
queue <int> li;bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int z,int y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
void Solve_Stainer()
{
for (int i=1;i<a2[p];i++)
{
for (int j=1;j<=n;j++) mi[i][j]=INF;
if (i-(i&(-i))==0)
for (int j=0;j<p;j++)
if (a2[j]==i) mi[i][Sg[j+1]]=0;
for (int j=(i-1)&i;j*2>=i;j=(j-1)&i)
for (int k=1;k<=n;k++)
mi[i][k]=min(mi[i][k],mi[j][k]+mi[i-j][k]);
for (int j=1;j<=n;j++)
if (mi[i][j]!=INF) li.push(j),b[j]=true;
while (!li.empty())
{
int k=li.front();li.pop();
for (int j=fi[k];j;j=c[j][1])
if (mi[i][k]+c[j][2]<mi[i][c[j][0]])
{
mi[i][c[j][0]]=c[j][2]+mi[i][k];
if (!b[c[j][0]])
b[c[j][0]]=true,li.push(c[j][0]);
}
b[k]=false;
}
}
return;
}
void Solve_DP()
{
for (int i=1;i<a2[p];i++)
{
int k=0;a[i]=INF;
for (int j=1;j<=p;j++) if (i&a2[j-1]) k|=v[j];
for (int j=1;j<=n;j++) a[i]=min(a[i],mi[k][j]);
for (int j=(i-1)&i;j;j=(j-1)&i)
a[i]=min(a[i],a[j]+a[i-j]);
}
return;
}
int main()
{
n=Read();m=Read();p=Read();a2[0]=1;
for (int i=1;i<=p;i++) a2[i]=a2[i-1] << 1;
for (int i=1;i<=m;i++) Line(Read(),Read(),Read());
for (int i=1;i<=p;i++)
v[Read()]|=a2[i-1],Sg[i]=Read();
Solve_Stainer();Solve_DP();
cout <<a[a2[p]-1]<<endl;
return 0;
}
JLOI还剩下一个神题找个时间填掉好了。。贵省考的真厉害。
BZOJ3996：玛德好久没做网络流什么建模的题都做不出了。调了好久发现是一个优化没加：如果这条路增广不了就把那个点的深度重置。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 505
#define M 260050
#define INF 0x3f7f7f7f
int sg[N][N],n,m,S=M-1,T=M-2,fi[M],c[M*10][3],li[M],h[M],ans,ss=1,st;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=0;fi[y]=ss;
}
bool BFS()
{
for (int i=1;i<=st;i++) h[i]=0;h[T]=0;
int le=1,ri=1;li[1]=S;h[S]=1;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!h[c[i][0]]&&c[i][2])
h[c[i][0]]=h[li[le]]+1,li[++ri]=c[i][0];
return h[T]>0;
}
int DFS(int x,int y)
{
int k,l=0;
if (x==T) return y;
for (int i=fi[x];i&&y;i=c[i][1])
if (c[i][2]&&h[c[i][0]]==h[x]+1)
{
k=DFS(c[i][0],min(y,c[i][2]));
if (k) y-=k,l+=k,c[i][2]-=k,c[i^1][2]+=k; else
h[c[i][0]]=0;
}
return l;
}
int main()
{
n=st=Read();
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
int k=Read();ans+=k;
Line(S,sg[i][j]=++st,k);
Line(sg[i][j],i,INF);
if (i!=j) Line(sg[i][j],j,INF);
}
for (int i=1;i<=n;i++) Line(i,T,Read());
while (BFS()) ans-=DFS(S,INF);
cout <<ans<<endl;
return 0;
}
BZOJ3997：脑洞了一个结论，答案就是最长的反链，猜了之后才发现这个确实可以对应到最小链覆盖问题的，有个Dilworth吧好像就是证明这个东西的。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
int n,m,v[N][N],t;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int main()
{
t=Read();
while (t--)
{
n=Read();m=Read();
memset(v,0,sizeof(v));
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) v[i][j]=Read();
for (int i=1;i<=n;i++)
for (int j=m;j>=1;j--)
v[i][j]=max(max(v[i-1][j],v[i][j+1]),v[i][j]+v[i-1][j+1]);
cout <<v[n][1]<<endl;
}
return 0;
}
BZOJ3998：一眼SAM。时间卡的人好虚
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 500050
#define M 26
#define ll long long
struct State
{
State *go[M],*suf;int val,s,d;ll cnt;
} statePool[N*2],*cur,*root,*last,*li[N*2];
int n,m,P,ans;char b[N];
void extend(int w)
{
State *p=last,*np=cur++;
np->val=p->val+1;
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p) np->suf=root; else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q; else
{
State* nq=cur++;
memcpy(nq->go,q->go,sizeof q->go);
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
while (p&&p->go[w]==q) p->go[w]=nq,p=p->suf;
}
}
last=np;np->s++;
}
void Pretreat()
{
int le=1,ri=0;
if (P==1)
{
for (State* i=root;i!=cur;i++)
if (i->suf) i->suf->d++;
for (State* i=root;i!=cur;i++)
if (!i->d) li[++ri]=i;
for (;le<=ri&&li[le]!=root;le++)
{
li[le]->suf->s+=li[le]->s;
if (!(--li[le]->suf->d))
li[++ri]=li[le]->suf;
}
}
root->s=0;le=1;ri=0;
for (State* i=root;i!=cur;i++)
for (int j=0;j<M;j++)
if (i->go[j]) i->go[j]->d++;
for (State* i=root;i!=cur;i++)
if (!i->d) li[++ri]=i;
for (;le<=ri;le++)
for (int i=0;i<M;i++)
if (li[le]->go[i]&&((--(li[le]->go[i]->d))==0))
li[++ri]=li[le]->go[i];
for (int i=ri;i>=1;i--)
{
if (!P) li[i]->s=1;
li[i]->cnt=li[i]->s;
for (int j=0;j<M;j++)
if (li[i]->go[j])
li[i]->cnt+=li[i]->go[j]->cnt;
}
root->cnt--;root->s=0;
if (root->cnt<m) {puts("-1");exit(0);};
return;
}
bool Solve(State* x,ll y)
{
y-=x->s;if (y<=0) return true;
for (int i=0;i<M;i++)
if (x->go[i])
if (x->go[i]->cnt>=y&&Solve(x->go[i],y))
{b[++ans]='a'+i;return true;} else
y-=x->go[i]->cnt;
}
int main()
{
gets(b+1);cin >>P>>m;n=strlen(b+1);
cur=statePool;root=last=cur++;
for (int i=1;i<=n;i++) extend(b[i]-'a');
Pretreat();Solve(root,m);
for (int i=ans;i>=1;i--) putchar(b[i]);
puts("");
return 0;
}
BZOJ4001：看了看。。狗哔概率题窝毫无思路。。再顺便看看代码长度。。！！！表一发然后就过了。。结论是n*(n+1)/(4n-2)
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
long double n;
cin >>n;
printf("%.9lf\n",(double)(n*(n+1)/(4*n-2)));
return 0;
}
BZOJ4000：在看懂题棋子位置是在第二行而不是第一行之前怎么搞不出，看懂题之后就是个裸裸的DP+矩阵快速幂优化了
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 10
#define M 70
#define ui unsigned int
struct Matrix
{ui a[M][M];} A,B,C;
int n,m,p,s,c[N],a2[N],st;ui ans;bool b[M];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
Matrix operator* (const Matrix &x,const Matrix &y)
{
memset(C.a,0,sizeof(C.a));
for (int i=0;i<st;i++)
for (int j=0;j<st;j++)
for (int k=0;k<st;k++)
C.a[i][k]+=x.a[i][j]*y.a[j][k];
return C;
}
void Quick_Power(int x)
{
for (int i=0;i<st;i++) B.a[i][i]=1;
while (x)
{
if (x&1) B=B*A;
A=A*A;x >>= 1;
}
return;
}
bool Intersect(int x,int y,int z)
{
for (int i=0;i<m;i++)
if (x&a2[i])
{
int k=z;
if (s<i) k <<= i-s; else
k >>= s-i;
if (k&y) return true;
}
return false;
}
void Pretreat()
{
for (int i=0;i<st;i++)
if (!Intersect(i,i,c[1])) b[i]=true;
for (int i=0;i<st;i++)
if (b[i])
for (int j=0;j<st;j++)
if (b[j]&&!Intersect(i,j,c[2])&&!Intersect(j,i,c[0]))
A.a[i][j]=true;
return;
}
int main()
{
n=Read();m=Read();p=Read();s=Read();a2[0]=1;st=1 << m;
for (int i=1;i<N;i++) a2[i]=a2[i-1] << 1;
for (int i=0;i<3;i++)
for (int j=0;j<p;j++)
c[i]|=Read() << j;
if (c[1]&a2[s]) c[1]-=a2[s];
Pretreat();Quick_Power(n);
for (int i=0;i<st;i++) ans+=B.a[0][i];
cout <<ans<<endl;
return 0;
}
TJOI还剩下一道SB数据结构题，既然BZOJ不屑于贴题面我也懒得写了。。（所以就完结了，e感觉TJOI考的好水= =）
BZOJ3930：一眼神题，后来发现H-L<=10^5所以只要暴力容斥就好了n log n的。之前交了一发才发现自己犯逗了。首先全部都除以k，GCD最多只会有2*(H-L)种情况：GCD=L~H的就是n个数全部为那一个数的情况。GCD=1~H-L+1的直接容斥一下就好了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define P 1000000007
#define ll long long
ll n,m,Le,Ri,a[N];
inline ll Quick_Power(ll x,ll y)
{
ll z=1;
while (y) {if (y&1) z=z*x%P;x=x*x%P;y >>= 1;}
return z;
}
int main()
{
cin >>n>>m>>Le>>Ri;Le=(Le-1)/m+1;Ri/=m;m=Ri-Le+1;
for (int i=m-1;i>=1;i--)
{
a[i]=Quick_Power((Ri/i)-(Le-1)/i,n);
for (int j=i+i;j<m;j+=i) a[i]=(a[i]+P-a[j])%P;
a[i]=(a[i]+P-(Ri/i-max((Le-1)/i,(m-1)/i)))%P;
}
cout <<a[1]<<endl;
return 0;
}
CQOI除去之前写过的两题还有两题一个像是花式乱搞一个像是花式DP感觉题目并不好玩已经不想写了= =贵省考的好良心= =
BZOJ3990：首先很容易看出如果找到了一个操作序列则答案等于(|操作序列|)!。因为操作只有覆盖关系而没有相交关系所以操作是互不影响的。然后求出其中一组操作序列可以从小到大看每一种操作，因为当前操作能够改变的只有两种情况21也就是交换的两个交换之后在同一个整体里面或者是1423这样不在同一个整体里面的。后者有的时候还要分两种情况比如1432的情况所以搜索一下就好了。复杂度：总共有2^n种操作方式，因为还要交换总共复杂度是差不多2^2n左右吧。。当然因为很多情况半路就不行了所以实际上跑的飞起。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 15
#define M 4100
#define ll long long
#define fr first
#define sc second
pair <int,int> li[N];
int v[M],n,m,JC[N],PX[N];ll ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Calc(int x,int y,int z,int o)
{
li[1]=make_pair(v[x+1],1);li[2]=make_pair(v[y+1],2);
li[3]=make_pair(v[z+1],3);li[4]=make_pair(v[o+1],4);
sort(li+1,li+5);PX[li[1].sc]=1;PX[li[2].sc]=2;
PX[li[3].sc]=3;PX[li[4].sc]=4;
}
void Swap(int x,int y,int z,int o)
{
void Solve(int x,int y);
for (int i=1;i<=z;i++) swap(v[x+i],v[y+i]);
Solve(o,z*2);
for (int i=1;i<=z;i++) swap(v[x+i],v[y+i]);
return;
}
void Solve(int x,int y)
{
int k=0,l=0;
if (y==m) {ans+=JC[x];return;}
for (int i=1;i<=m/y;i+=2)
if (v[i*y]!=v[(i+1)*y]-y||v[i*y]%(2*y)!=y)
{if (!k) k=i; else if (!l) l=i; else return;}
if (!k) Solve(x,y*2); else
if (!l)
Swap((k-1)*y,k*y,y,x+1); else
{
Calc((k-1)*y,k*y,(l-1)*y,l*y);
if ((PX[1]==1&&PX[4]==4)||(PX[1]==3&&PX[2]==1&&PX[3]==4))
Swap(k*y,(l-1)*y,y,x+1); else
if ((PX[2]==2&&PX[3]==3)||(PX[1]==2&&PX[2]==4&&PX[3]==1))
Swap((k-1)*y,l*y,y,x+1); else
if ((PX[1]==1&&PX[3]==3)||(PX[2]==2&&PX[4]==4))
Swap((k-1)*y,(l-1)*y,y,x+1),Swap(k*y,l*y,y,x+1);
}
return;
}
int main()
{
n=Read();m=1 << n;JC[0]=1;
for (int i=1;i<N-2;i++) JC[i]=JC[i-1]*i;
for (int i=1;i<=m;i++) v[i]=Read();
Solve(0,1);
cout <<ans<<endl;
return 0;
}
BZOJ3991：脑洞了好久动态树做法发现好麻烦= =突然发现脑抽了只要DFS序就可做了，就只要维护一个set然后倍增搞一搞就好了。一开始以为线段树是可以维护出树上任意两点距离写完之后才发现犯逗了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
#define M 17
#define ll long long
multiset <int> li;
set <int> :: iterator it,ti;
int sg[N][2],nd[N*2],fi[N],c[N*2][3],fa[N][M],a2[M];
int Cnt,n,m,st,ss=1;ll up[N][M],h[N],ans,H[N];bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int z,int y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
void DFS(int x)
{
nd[sg[x][0]=++st]=x;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
fa[c[i][0]][0]=x,
h[c[i][0]]=h[x]+(up[c[i][0]][0]=c[i][2]),
H[c[i][0]]=H[x]+1,DFS(c[i][0]);
nd[sg[x][1]=++st]=x;
}
void Pretreat()
{
for (int i=1;i<M;i++)
for (int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1],
up[j][i]=up[j][i-1]+up[fa[j][i-1]][i-1];
}
ll Dis(int x,int y)
{
x=nd[x];y=nd[y];
ll cnt=h[x]+h[y];
if (H[x]<H[y]) swap(x,y);
for (int i=M-1;i>=0&&H[x]!=H[y];i--)
if (H[x]-a2[i]>=H[y]) x=fa[x][i];
if (x!=y)
{
for (int i=M-1;i>=0;i--)
if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
x=fa[x][0];
}
return cnt-2*h[x];
}
void Delete(int x)
{
for (int i=0;i<2;i++)
{
it=ti=li.lower_bound(sg[x][i]);bool flag=false;
if (it!=li.begin())
ans-=Dis(*(--it),sg[x][i]),flag=true;ti++;
if (ti!=li.end())
{
ans-=Dis(sg[x][i],*ti);
if (flag) ans+=Dis(*it,*ti);
}
li.erase(sg[x][i]);
}
b[x]=false;Cnt--;return;
}
void Insert(int x)
{
for (int i=0;i<2;i++)
{
it=ti=li.lower_bound(sg[x][i]);bool flag=false;
if (it!=li.end())
ans+=Dis(sg[x][i],*it),flag=true;
if (ti!=li.begin())
{
ans+=Dis(sg[x][i],*(--ti));
if (flag)
ans-=Dis(*ti,*it);
}
li.insert(sg[x][i]);
}
b[x]=true;Cnt++;return;
}
ll Aha()
{
if (!Cnt) return 0;
it=li.begin();ti=li.end();return Dis(*it,*(--ti));
}
int main()
{
n=Read();m=Read();a2[0]=1;
for (int i=1;i<M;i++) a2[i]=a2[i-1] << 1;
for (int i=1;i<n;i++) Line(Read(),Read(),Read());
DFS(1);Pretreat();
while (m--)
{
int k=Read();
if (b[k]) Delete(k); else Insert(k);
printf("%lld\n",ans+Aha());
}
return 0;
}
BZOJ3992：求个原根然后将集合里面每个数用原根的幂表示出来。最后倍增一下NTT一下就好了。（我什么板子都不记得了~
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 32200
#define P 1004535809
#define G 3
#define ll long long
int n,m,p,s,v[N],rt,sg[N],rev[N],len,bit;ll wn[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline ll Quick_Power(ll x,ll y,ll z)
{
ll s=1;
while (y)
{if (y&1) s=s*x%z;x=x*x%z;y >>= 1;}
return s;
}
void Find_Rt()
{
if (m==2) {rt=1;return;}
for (rt=2;rt<m;rt++)
{
bool flag=false;
for (int i=2;i*i<m;i++)
if ((m-1)%i==0&&(Quick_Power(rt,i,m)==1
||Quick_Power(rt,(m-1)/i,m)==1)) {flag=true;break;}
if (!flag) break;
}
}
void Sign()
{int cnt=rt;for (int i=1;i<m-1;i++) sg[cnt]=i,cnt=cnt*rt%m;}
void Solve(ll* a,int n,int f)
{
for (int i=0;i<n-1;i++)
if (i<rev[i]) swap(a[i],a[rev[i]]);
int now=0;
for (int p=1;p<n;p <<= 1)
{
now++;
for (int i=0;i<n;i+=p << 1)
{
ll e=1;
for (int j=0;j<p;j++,e=e*wn[now]%P)
{
ll x=a[i+j],y=e*a[i+j+p]%P;
a[i+j]=(x+y)%P;a[i+j+p]=(x-y+P)%P;
}
}
}
if (f==-1)
{
for (int i=1;i<n >> 1;i++) swap(a[i],a[n-i]);
ll Inv=Quick_Power(n,P-2,P);
for (int i=0;i<n;i++) a[i]=a[i]*Inv%P;
}
}
struct NTT {ll a[N];} A,B,C;
void Multi(NTT &x,NTT &y)
{
memcpy(C.a,y.a,sizeof y.a);
Solve(x.a,len,1);Solve(C.a,len,1);
for (int i=0;i<len;i++) x.a[i]=x.a[i]*C.a[i]%P;
Solve(x.a,len,-1);
for (int i=m-1;i<=m-2<<1;i++) (x.a[i-(m-1)]+=x.a[i])%=P,x.a[i]=0;
}
void Quick_Powor(int y)
{while (y) {if (y&1) Multi(B,A);Multi(A,A);y >>= 1;}}
int main()
{
n=Read();m=Read();p=Read();s=Read();
for (int i=1;i<=s;i++) v[i]=Read();
Find_Rt();Sign();
for (int i=1;i<=s;i++)
if (v[i]) A.a[sg[v[i]]]=true;
len=1;
while (len<m*2-1) len <<= 1,bit++;
for (int i = 1;i < len;i ++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
for (int i=0;i<=20;i++)
wn[i]=Quick_Power(G,P - 1 >> i,P);
B.a[0]=1;Quick_Powor(n);
cout <<B.a[sg[p]]<<endl;
return 0;
}
BZOJ3993：二分+网络流，也没卡精度= =
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 105
#define M 6050
#define eps 1e-6
#define INF 0x3f7f7f7f
int S=N-1,T=N-2,fi[N],c[M][2],n,m,ss=1,sg[N],t[N],h[N],li[N];
double v[M],cnt;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline int Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];v[ss]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];v[ss]=0;fi[y]=ss;
return ss-1;
}
bool BFS()
{
memset(h,0,sizeof(h));
h[li[1]=S]=1;int le=1,ri=1;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!h[c[i][0]]&&fabs(v[i])>eps)
h[li[++ri]=c[i][0]]=h[li[le]]+1;
return h[T]>0;
}
inline double min(double x,double y)
{return x<y?x:y;}
double DFS(int x,double y)
{
if (x==T) return y;
double k,l=0;
for (int i=fi[x];i&&fabs(y)>eps;i=c[i][1])
if (h[c[i][0]]==h[x]+1&&fabs(v[i])>eps)
{
k=DFS(c[i][0],min(y,v[i]));
if (fabs(k)<eps) continue;
l+=k;y-=k;v[i^1]+=k;v[i]-=k;
}
return l;
}
bool Check(double x)
{
for (int i=1;i<=m;i++) v[sg[i]]=t[i]*x;
double k=0;
while (BFS()) k+=DFS(S,INF);
for (int i=2;i<ss;i+=2) v[i]+=v[i+1],v[i+1]=0;
return fabs(k-cnt)<eps;
}
double Half_Find(double x,double y)
{
double i=(x+y)/2;
if (fabs(x-y)<eps) return x;
if (Check(i)) return Half_Find(x,i); else
return Half_Find(i,y);
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
{
int k=Read();cnt+=k;
Line(i,T,k);
}
for (int i=1;i<=m;i++)
sg[i]=Line(S,i+n,0),t[i]=Read();
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
if (Read()) Line(i+n,j,INF);
printf("%.6lf\n",Half_Find(0,(int)1e7));
return 0;
}
BZOJ3994：搞完这一波真心要回去搞搞数论相关了。。好久都没做这种题现在没点手感= =推倒过程可以看这里好了。然后那个神结论的证明就看这里。感觉这题简直恶心。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 50050
#define ll long long
ll miu[N],mis[N],F[N],ans;int t,n,m,st,Prime[N];bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
miu[1]=mis[1]=1;
for (int i=2;i<N;i++)
{
if (!b[i]) miu[Prime[++st]=i]=-1;
for (int j=1;j<=st&&Prime[j]*i<N;j++)
{
b[i*Prime[j]]=true;
if (i%Prime[j]==0) break;
miu[i*Prime[j]]=-miu[i];
}
mis[i]=mis[i-1]+miu[i];
}
for (int i=1;i<=N;i++)
{
int k=sqrt(i);
for (int j=1;j<=k;j++)
{
int ri=i/j,le=i/(j+1)+1;
F[i]+=(ri-le+1)*j;
}
k=i/(k+1);
for (int j=1;j<=k;j++)
F[i]+=i/j;
}
return;
}
void Solve()
{
if (n>m) swap(n,m);
int rt=sqrt(n),now=m/n,Ri=n;
for (int i=1;i<=rt;i++)
while (true)
{
int le=max(n/(i+1)+1,m/(now+1)+1);
ans+=F[i]*F[now]*(mis[Ri]-mis[le-1]);Ri=le-1;
now=le==1?0:m/Ri;
if (Ri==n/(i+1)) break;
}
for (int i=1;i<=Ri;i++)
ans+=miu[i]*F[n/i]*F[m/i];
printf("%lld\n",ans);
return;
}
int main()
{
t=Read();Pretreat();
while (t--) n=Read(),m=Read(),ans=0,Solve();
return 0;
}
BZOJ3995：智商癌，并没有做出来= =。明明只要分类讨论维护一棵线段树就好了。那个分类讨论感觉很要死的样子。玛德状态这种东西真是玄学，都不知道什么时候会好的。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 60050
#define INF 0x3f7f7f7f
struct Node
{
int a0,a1,a2,a3,a4;
void Set() {a0=a1=a2=a3=a4=INF;}
} a[N*4];
int n,m,col[N],row[N][2];char b[20];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Set(int x,int z)
{a[z].Set();a[z].a0=col[x];a[z].a1=0;}
inline void Mi(int &x,int y)
{x=min(x,y);}
Node Merge(Node x,Node y,int z)
{
Node k;k.Set();
int q=row[z][0],w=row[z][1],e=q+w;q=min(q,w);
Mi(k.a0,x.a0+y.a0+q);Mi(k.a0,x.a0+y.a2+e);
Mi(k.a0,x.a0+y.a1+e);Mi(k.a3,x.a0+y.a1+q);
Mi(k.a3,x.a0+y.a3+q);Mi(k.a3,x.a0+y.a4+e);
Mi(k.a0,x.a1+y.a0+e);Mi(k.a2,x.a1+y.a0+q);
Mi(k.a1,x.a1+y.a1+e);Mi(k.a4,x.a1+y.a1+q);
Mi(k.a2,x.a1+y.a2+e);Mi(k.a3,x.a1+y.a3+e);
Mi(k.a4,x.a1+y.a3+q);Mi(k.a4,x.a1+y.a4+e);
Mi(k.a2,x.a2+y.a0+q);Mi(k.a2,x.a2+y.a1+e);
Mi(k.a4,x.a2+y.a1+q);Mi(k.a2,x.a2+y.a2+e);
Mi(k.a4,x.a2+y.a3+q);Mi(k.a4,x.a2+y.a4+e);
Mi(k.a0,x.a3+y.a0+e);Mi(k.a3,x.a3+y.a1+e);
Mi(k.a3,x.a3+y.a3+e);Mi(k.a2,x.a4+y.a0+e);
Mi(k.a4,x.a4+y.a1+e);Mi(k.a4,x.a4+y.a3+e);
return k;
}
void Set_up(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
if (x==y) {Set(x,z);return;}
Set_up(x,i,j);Set_up(i+1,y,j+1);
a[z]=Merge(a[j],a[j+1],i);
return;
}
Node Query(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;
if (x==o&&y==p) return a[z];
if (p<=i) return Query(x,i,j,o,p); else
if (o>i) return Query(i+1,y,j+1,o,p); else
return Merge(Query(x,i,j,o,i),Query(i+1,y,j+1,i+1,p),i);
}
void Modify(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1;
if (x==y) {Set(x,z);return;}
if (o<=i) Modify(x,i,j,o); else Modify(i+1,y,j+1,o);
a[z]=Merge(a[j],a[j+1],i);
return;
}
int main()
{
n=Read();m=Read();
for (int t=0;t<2;t++)
for (int i=1;i<n;i++) row[i][t]=Read();
for (int i=1;i<=n;i++) col[i]=Read();
Set_up(1,n,1);
while (m--)
{
scanf("%s",b);
if (b[0]=='Q')
{
int k=Read(),l=Read();
printf("%d\n",Query(1,n,1,k,l).a0);
} else
{
int k=Read(),l=Read(),q=Read(),w=Read(),e=Read();
if (k>q) swap(k,q); else
if (l>w) swap(l,w);
if (k==q) row[l][k-1]=e; else col[l]=e;
Modify(1,n,1,l);
}
}
return 0;
}
SDOI Round1完结！感觉题目质量还是蛮好的。
BZOJ4034：NOI Day1T2即视感。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define ll long long
int n,m,ss=1,st,fi[N],c[N*2][2],v[N],sg[N][2];
int fa[N],gf[N],li[N],sz[N];ll s[N*4],ad[N*4];
inline int Read()
{
int x=0;char y;bool z=false;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
sz[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
fa[c[i][0]]=x,DFS(c[i][0]),sz[x]+=sz[c[i][0]];
return;
}
void DSF(int x,int y)
{
int k=0;li[sg[x][0]=++st]=x;gf[x]=y;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&sz[c[i][0]]>sz[k]) k=c[i][0];
if (k) DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&c[i][0]!=k) DSF(c[i][0],c[i][0]);
sg[x][1]=st;
}
void Set_up(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
if (x==y) {s[z]=v[li[x]];return;}
Set_up(x,i,j);Set_up(i+1,y,j+1);
s[z]=s[j]+s[j+1];
}
inline void adj(int x,int y,int z)
{
int j=z << 1;
s[z]+=ad[z]*(y-x+1);
if (x!=y) ad[j]+=ad[z],ad[j+1]+=ad[z];
ad[z]=0;
}
void Modify(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==o&&y==p) {ad[z]=u;adj(x,y,z);return;}
if (p<=i) Modify(x,i,j,o,p,u),adj(i+1,y,j+1); else
if (o>i) Modify(i+1,y,j+1,o,p,u),adj(x,i,j); else
Modify(x,i,j,o,i,u),Modify(i+1,y,j+1,i+1,p,u);
s[z]=s[j]+s[j+1];
}
ll Query(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==o&&y==p) return s[z];
if (p<=i) return Query(x,i,j,o,p); else
if (o>i) return Query(i+1,y,j+1,o,p); else
return Query(x,i,j,o,i)+Query(i+1,y,j+1,i+1,p);
}
ll GetAns(int x)
{
ll cnt=0;
while (x)
cnt+=Query(1,n,1,sg[gf[x]][0],sg[x][0]),x=fa[gf[x]];
return cnt;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
DFS(1);DSF(1,1);Set_up(1,n,1);
while (m--)
{
int q,w,e=Read();
if (e<3)
q=Read(),w=Read(),
Modify(1,n,1,sg[q][0],sg[q][e-1],w); else
printf("%lld\n",GetAns(Read()));
}
return 0;
}
BZOJ4033：还是很水= =，n^2的树形DP一下就好了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 2050
#define ll long long
#define INF 12345678987654321LL
int n,m,ss=1,fi[N],c[N*2][3],sz[N];ll mi[N][N],b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int z,int y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
inline ll max(ll x,ll y)
{return x<y?y:x;}
void Merge(int x,int y,ll z)
{
int cnt=sz[x]+sz[y];
memset(b,0,sizeof(b));
for (int i=0;i<=sz[x];i++)
for (int j=0;j<=sz[y];j++)
b[i+j]=max(b[i+j],
mi[x][i]+mi[y][j]+(j*(m-j)+(sz[y]-j)*(n-m-sz[y]+j))*z);
memcpy(mi[x],b,sizeof b);
sz[x]=cnt;
return;
}
void DFS(int x,int fa)
{
sz[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa) DFS(c[i][0],x),Merge(x,c[i][0],c[i][2]);
return;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<n;i++) Line(Read(),Read(),Read());
DFS(1,0);
cout <<mi[1][m]<<endl;
return 0;
}
BZOJ4035：日，这题猜了个结论证了好久发现证明从一开始就是错的= =后来弃疗去看题解很久不知道是在干什么，反正是个玄学题我还是早早弃坑的好。
BZOJ4036：论文题。。简直smg。。
BZOJ4037：en明显这东西可以DP。首先建出递推矩阵，然后设Ai代表前i个数的答案，就可以用A0~i-1转移了。
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
#define P 998244353
#define N 505
#define M 6
struct Matrix
{ll a[M][M];} C,a[10][N],ans[N],I,Emp,a10;
char c[N];int n,m;
Matrix operator* (const Matrix &x,const Matrix &y)
{
memset(C.a,0,sizeof(C.a));
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=m;k++)
C.a[i][k]=(C.a[i][k]+x.a[i][j]*y.a[j][k]%P)%P;
return C;
}
Matrix operator+ (const Matrix &x,const Matrix &y)
{
memset(C.a,0,sizeof(C.a));
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
C.a[i][j]=(C.a[i][j]+x.a[i][j]+y.a[i][j])%P;
return C;
}
void Set_up()
{
for (int i=1;i<=n;i++) c[i]-='0';
for (int i=1;i<=m;i++) ans[0].a[i][i]=1;
for (int i=1;i<=m;i++) I.a[i][m]=I.a[i][i-1]=1;
a10=a[0][0]=ans[0];
for (int i=1;i<=9;i++) a10=a10*I,a[i][0]=a10;a10=a10*I;
for (int i=1;i<=n;i++)
{
a[0][i]=ans[0];a[1][i]=a[9][i-1]*a[1][i-1];
for (int j=2;j<10;j++)
a[j][i]=a[j-1][i]*a[1][i];
}
return;
}
int main()
{
cin >>c+1;n=strlen(c+1);cin >>m;
Set_up();
for (int i=1;i<=n;i++)
{
Matrix k=ans[0];
for (int j=i;j>=1;j--)
k=a[c[j]][i-j]*k,ans[i]=ans[i]+k*ans[j-1];
}
cout <<ans[n].a[m][m]<<endl;
return 0;
}
这届HAOI感觉比往届要凶。。
BZOJ4085：直接搞出递推矩阵然后线段树维护一下就好了？感觉既麻烦也好像会卡常的样子。。
BZOJ4084：感觉首先设长点的那个为S，S里面的串先提出前一半的那部分复制一份接在后面，对这部分建出SAM，再对S中多出来的那部分KMP一下看哪些位置可以匹配的。并在SAM里面对应的位置打上标记。然后T的每个串进去跑一遍就好了。画风不对啊，时限只有一秒是smg，O(26n)明显会爆啊。出题人好心态啊。其实感觉也不要变什么地方只要把SAM的部分换成Hash就好了？调的人不行了，感觉应该没什么问题啊。又没有数据这种东西怎么调= =只能理解为是哈希取模的值不够大的锅吧。管他的。。先把代码放上来好了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 5000050
#define M +10086
#define P 10000003
#define ll long long
char a[N],b[N];int fail[N],n,m,lena,lenb,now[P],s[P],mid;
ll ans,Power[N],val[N];
inline void GetHash(int ri,int x)
{
ri-=lena-mid;int le=ri-lenb+1;
if (le<0) return;
ll cnt=(val[ri]-(!le?0:val[le-1])*Power[ri-le+1]%P+P)%P;
if (now[cnt]!=x)
now[cnt]=x,s[cnt]++;
}
void Solve()
{
Power[0]=1;
for (int i=1;i<N;i++) Power[i]=Power[i-1]*M%P;
for (int i=1;i<=n;i++)
{
char *c=a+(i-1)*lena;
fail[0]=-1;
for (int j=mid+1;j<lena;j++)
{
fail[j-mid]=fail[j-1-mid];
while (fail[j-mid]!=-1&&c[fail[j-mid]+1+mid]!=c[j])
fail[j-mid]=fail[fail[j-mid]];
if (c[fail[j-mid]+1+mid]==c[j]) fail[j-mid]++;
}
val[0]=c[0];
for (int j=1;j<mid*2;j++)
val[j]=(val[j-1]*M+c[j%mid]*c[j%mid])%P;
if (mid==lena)
{
for (int j=0;j<mid;j++)
GetHash(mid+j,i);
continue;
}
int Now=-1;
for (int j=0;j<mid*2;j++)
{
if (Now==lena-mid-1) Now=fail[Now];
while (Now!=-1&&c[Now+mid+1]!=c[j%mid])
Now=fail[Now];
if (c[Now+mid+1]==c[j%mid]) Now++;
if (Now==lena-mid-1) GetHash(j,i);
}
}
for (int i=1;i<=m;i++)
{
ll cnt=0;char *c=b+(i-1)*lenb;
for (int j=0;j<lenb;j++)
cnt=(cnt*M%P+c[j]*c[j])%P;
ans+=s[cnt];
}
return;
}
void Swap()
{
swap(a,b);swap(n,m);swap(lena,lenb);
for (int i=1;i<=n;i++)
{
char *c=a+(i-1)*lena;
for (int j=0,k=lena-1;j!=k;j++,k--) swap(c[j],c[k]);
}
for (int i=1;i<=m;i++)
{
char *c=b+(i-1)*lenb;
for (int j=0,k=lenb-1;j!=k;j++,k--) swap(c[j],c[k]);
}
}
int main()
{
cin >>n>>m>>lena>>lenb;mid=lena + lenb >> 1;
for (int i=1;i<=n;i++) scanf("%s",a+(i-1)*lena);
for (int i=1;i<=m;i++) scanf("%s",b+(i-1)*lenb);
if (lena<lenb) Swap();
Solve();cout <<ans<<endl;
return 0;
}
BZOJ4086：这题什么鬼。。en我想说我会暴力我自豪。。正解是容斥+分类讨论？不明觉厉
玛德SDOI Round1还正常，Round2D1D2简直smg。弃坑了弃坑了！！
剩下的里面FJOI看通过人数就已经弃疗了。最近看的这几套题简直啃的人愉悦异常啊。
BZOJ3926：感觉可以枚举叶子节点的n-1个排列使得这些排列每个数的后继各不相同？然后建出来的SAM应该就是O(20cn)的吧。。标算好像是总的建出一棵trie树看起来比我的节点数应该要优些。。无脑背板果然被D了，get新姿势，last是可以替换成另外一个节点的，所以直接在trie树某个父亲节点对应的SAM节点下面直接插就好了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define M 4000050
#define ll long long
#define P 10
int n,m,fi[N],c[N*2][2],cl[N],ss=1,d[N];ll ans;
struct SAM
{
int go[M][P],suf[M],val[M],root,cur;
SAM() {cur=1;root=cur++;}
int extend(int p,int w)
{
int np=cur++;val[np]=val[p]+1;
while (p&&!go[p][w]) go[p][w]=np,p=suf[p];
if (!p) suf[np]=root; else
{
int q=go[p][w];
if (val[q]==val[p]+1)
suf[np]=q; else
{
int nq=cur++;
memcpy(go[nq],go[q],sizeof go[q]);
suf[nq]=suf[q];suf[q]=suf[np]=nq;
val[nq]=val[p]+1;
while (p&&go[p][w]==q)
go[p][w]=nq,p=suf[p];
}
}
return np;
}
void Solve()
{for (int i=2;i<cur;i++) ans+=val[i]-val[suf[i]];}
} Aha;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;d[x]++;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;d[y]++;
}
void DFS(int x,int y,int z)
{
int k=Aha.extend(z,cl[x]);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=y) DFS(c[i][0],x,k);
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++) cl[i]=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
for (int i=1;i<=n;i++)
if (d[i]==1) DFS(i,0,1);
Aha.Solve();
cout <<ans<<endl;
return 0;
}
BZOJ3925：尼玛去年线性回归今年考求导是要组ZJ数学队么。。不会不会
BZOJ3924：感觉我简直数据结构无能= =en度数最大为20，满满的点分治即视感。但是尼玛就是搞不懂到底怎么搞的，为什么能在分治树上面移动来求出重心啊。。其实后来回来看的时候才发现之前一直脑抽了，en这肯定是可以做的啊。。感觉自己没救了。。首先找带权重心就是动态点分治，每次修改的时候树剖/LCT搞一搞，每个点维护子树和，然后找重心就是log层每层对比权值总和的一半和这个节点的子树和。log^2的。然后怎么求路径和呢？是的，怎么求呢？。。所以还是太弱。。只要把移动的时候的子树外的节点信息都放到子树内跟它第一个相连的节点那里，然后回溯的时候再删除就好了。。所以是O(n log^2 n)的。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 20
#define ll long long
ll Ans[N],Sub[N][M],ans;
int dis[N][M],gf[N][M],cnt[N],fi[N],c[N*2][3],s[N],n,m,ss;
bool b[N],vis[N];int li[N],sg[N],Up[N][M],tot;
inline int Read()
{
int x=0;char y;bool z=false;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void Line(int z,int y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
int DFS(int x,int y)
{
int le=1,ri=1;
li[1]=x;b[x]=true;dis[x][y]=0;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!b[c[i][0]]&&!vis[c[i][0]])
{
b[c[i][0]]=true;
dis[c[i][0]][y]=dis[li[le]][y]+c[i][2];
li[++ri]=c[i][0];
}
for (int i=1;i<=ri;i++) b[li[i]]=false;
return ri;
}
int Get_Root(int x,int Cnt)
{
for (int i=Cnt;i>=1;i--)
{
s[li[i]]=true;
for (int j=fi[li[i]];j;j=c[j][1])
if (!vis[c[j][0]]) s[li[i]]+=s[c[j][0]];
}
int rt=li[1];
while (true)
{
bool flag=false;
for (int i=fi[rt];i;i=c[i][1])
if (!vis[c[i][0]]&&s[c[i][0]]<s[rt]&&s[c[i][0]]*2>=Cnt)
{flag=true;rt=c[i][0];break;}
if (!flag) break;
}
for (int i=1;i<=Cnt;i++) s[li[i]]=false;
return rt;
}
void Set_up(int x,int y)
{
int Cnt=DFS(x,y),rt=Get_Root(x,Cnt);DFS(rt,y);
for (int i=1;i<=Cnt;i++) gf[li[i]][y]=rt;
sg[rt]=y;vis[rt]=true;
for (int i=fi[rt];i;i=c[i][1]) Up[c[i][0]][y]=c[i][0];
for (int i=2;i<=Cnt;i++)
for (int j=fi[li[i]];j;j=c[j][1])
if (!vis[c[j][0]]&&!Up[c[j][0]][y])
Up[c[j][0]][y]=Up[li[i]][y];
for (int i=fi[rt];i;i=c[i][1])
if (!vis[c[i][0]]) Set_up(c[i][0],y+1);
return;
}
void Modify(int x,int y,int z)
{
for (int i=z;i<=sg[x];i++)
cnt[gf[x][i]]+=y,Ans[gf[x][i]]+=1LL*y*dis[x][i],
Sub[Up[x][i]][i]+=1LL*y*(dis[x][i]-dis[Up[x][i]][i]);
return;
}
void Get_Ans(int x)
{
int k=0,l=sg[x],e,w;
for (int i=fi[x];i;i=c[i][1])
if (sg[c[i][0]]>l&&cnt[gf[c[i][0]][l+1]]*2>=tot)
{k=c[i][0];w=c[i][2];break;}
if (!k) {printf("%lld\n",ans+Ans[x]);return;}
e=cnt[x]-cnt[gf[k][l+1]];
ans+=Ans[x]-Sub[k][l]+1LL*(e-cnt[gf[k][l+1]])*w;
Modify(k,e,l+1);
Get_Ans(gf[k][l+1]);
Modify(k,-e,l+1);
return;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<n;i++) Line(Read(),Read(),Read());
Set_up(1,1);
while (m--)
{
int k=Read(),l=Read();tot+=l;ans=0;
Modify(k,l,1);Get_Ans(gf[1][1]);
}
return 0;
}
下面就做一做数学相关冷静一下
BZOJ1101：水题。。反演一下然后分成根号n段然后就可以了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 50050
int t,n,m,d,st,Prime[N],miu[N],mis[N];bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
miu[1]=mis[1]=1;
for (int i=2;i<=N-50;i++)
{
if (!b[i]) miu[Prime[++st]=i]=-1;
for (int j=1;Prime[j]*i<N;j++)
{
b[Prime[j]*i]=true;
if (i%Prime[j]==0) break;
miu[i*Prime[j]]=-miu[i];
}
mis[i]=mis[i-1]+miu[i];
}
return;
}
int Solve()
{
if (n>m) swap(n,m);n/=d;m/=d;
int cnt=0,rt=sqrt(n),ri=n,now=m/n;
for (int i=1;i<=rt;i++)
do
{
int le=max(n/(i+1)+1,m/(now+1)+1);
cnt+=(mis[ri]-mis[le-1])*(n/le)*(m/le);
ri=le-1;now=ri?m/ri:0;
} while (ri!=n/(i+1));
for (int i=1;i<=ri;i++)
cnt+=miu[i]*(n/i)*(m/i);
return cnt;
}
int main()
{
t=Read();Pretreat();
while (t--)
n=Read(),m=Read(),d=Read(),printf("%d\n",Solve());
return 0;
}
BZOJ2693：感觉自己在一顿乱推，然后莫名其妙地就推出来了。首先把lcm化成gcd，然后提出gcd。变成：Σ(k=1 to n)Σ(i=1 to n/k)Σ(j=1 to m/k)i*j*k*[gcd(i,j)==1]。然后后面东西反演一下把式子变一下型：Σ(k=1 to n)kΣ(t=1 to n/k)μ(t)*t^2*Sum(n/kt)*Sum(m/kt)，其中Sum(x)就是1到x的和。接着把kt提到前面来变成：Σ(i=1 to n)Sum(n/i)*Sum(m/i)*i*Σ(k|i)μ(k)*k，后面的东西因为是积性函数所以直接O(n)预处理，至于证明就是因为μ是积性函数，然后y=x也是积性函数，所以μ(k)*k也是积性函数，然后后面那个Σ我们可以套入Dirichlet卷积里面，en，因为y=1也是积性函数。前面的东西也明显分块一下就好了。。然后就是O(T*sqrt(N)+N)的了。。en话说一个东西我连续推错两次我是不是要废？然后拍的时候还get了新的分块技巧。感觉短多了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 10000050
#define P 100000009
#define ll long long
int Prime[N],st,t,n,m;ll F[N],s[N],ans;bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
F[1]=s[1]=1;
for (int i=2;i<=N-50;i++)
{
if (!b[i]) Prime[++st]=i,F[i]=((ll)i*(1-i)%P+P)%P;
for (int j=1;j<=st&&Prime[j]*i<N;j++)
if (i%Prime[j])
F[Prime[j]*i]=F[Prime[j]]*F[i]%P,
b[Prime[j]*i]=true; else
{
F[Prime[j]*i]=Prime[j]*F[i]%P;
b[Prime[j]*i]=true;
break;
}
s[i]=(s[i-1]+F[i])%P;
}
return;
}
inline ll Sum(ll x)
{return x*(x+1)/2%P;}
ll Solve()
{
if (n>m) swap(n,m);
int ri;ans=0;
for(int i=1;i<=n;i=ri+1)
ri=min(n/(n/i),m/(m/i)),
ans=(ans+Sum(n/i)*Sum(m/i)%P*(s[ri]-s[i-1]+P)%P)%P;
return ans;
}
int main()
{
t=Read();Pretreat();
while (t--)
n=Read(),m=Read(),printf("%lld\n",Solve());
return 0;
}
BZOJ2111：式子很水，组合数随便搞搞。虽然知道会有n>p的情况但是忘记了有卢卡斯定理了。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1000050
#define fr first
#define sc second
#define ll long long
int n,P;ll JC[N],INV[N];
void Pretreat()
{
JC[0]=INV[0]=JC[1]=INV[1]=1;
for (int i=2;i<=min(N-50,P-1);i++)
JC[i]=JC[i-1]*i%P,INV[i]=(P-P/i)*INV[P%i]%P;
for (int i=2;i<=min(N-50,P-1);i++) INV[i]=INV[i-1]*INV[i]%P;
}
inline ll C(int x,int y)
{return JC[x]*INV[y]%P*INV[x-y]%P;}
inline ll ZHS(int x,int y)
{
ll cnt=1;
while (x) cnt=(cnt*C(x%P,y%P))%P,x/=P,y/=P;
return cnt;
}
pair <ll,int> DFS(int x)
{
if (x*2>=n) return make_pair(1,x*2==n?2:1);
pair <ll,int> le=DFS(x*2),ri=DFS(x*2+1);
int cnt=le.sc+ri.sc+1;
return make_pair(le.fr*ri.fr%P*ZHS(cnt-1,le.sc)%P,cnt);
}
int main()
{
cin >>n>>P;Pretreat();
cout <<DFS(1).fr<<endl;
return 0;
}
BZOJ3142：枚举所求序列的差分算出每个差分的可出现位置数加起来，这个式子化下简就好了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
ll n,t,m,P;
ll Quick_Power(ll x,ll y)
{
ll z=1;
while (y)
z=y&1?z*x%P:z,x=x*x%P,y >>= 1;
return z;
}
int main()
{
cin >>n>>t>>m>>P;n%=P;
if (!m) cout <<0<<endl; else
if (m==1) cout <<n<<endl; else
cout <<Quick_Power(m,t-2)*(n*m%P-m*(m+1)/2%P*(t-1)%P+P)%P<<endl;
return 0;
}
BZOJ3309：式子随便反演一下变成两个下取整和一个Dirichlet卷积的乘积的求和。但是卷积并不是积性函数。所以打表找规律可以发现：除了F(0)=0之外其余的质因数次数不相同的卷积值都为0，相同的值为(-1)^(质数个数+1)。然后线性筛随便搞搞就好了。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10000050
#define ll long long
ll ans,s[N];int F[N],Prime[N],n,m,st,t,a[N],c[N];bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
for (int i=2;i<=N-50;i++)
{
if (!b[i]) F[Prime[++st]=a[i]=i]=1,c[i]=1;
for (int j=1;j<=st&&i*Prime[j]<N;j++)
{
b[i*Prime[j]]=true;
if (i%Prime[j]==0)
{
a[i*Prime[j]]=a[i];
c[i*Prime[j]]=c[i]*Prime[j];
if (c[i*Prime[j]]%a[i]==0)
c[i*Prime[j]]/=a[i];
if (c[i*Prime[j]]==1)
F[i*Prime[j]]=F[a[i]];
break;
} else
{
a[i*Prime[j]]=a[i]*Prime[j];
c[i*Prime[j]]=i/a[i];
if (c[i*Prime[j]]==1) F[i*Prime[j]]=-F[i];
}
}
s[i]=s[i-1]+F[i];
}
return;
}
ll Solve()
{
if (n>m) swap(n,m);
int ri;ans=0;
for (int i=1;i<=n;i=ri+1)
ri=min(n/(n/i),m/(m/i)),
ans+=n/i*(ll)(m/i)*(s[ri]-s[i-1]);
return ans;
}
int main()
{
t=Read();Pretreat();
while (t--)
n=Read(),m=Read(),printf("%lld\n",Solve());
return 0;
}
然后，换上口味清淡的HNOI赶快把这个坑填完好了。。
BZOJ3571：第一题就不会了。后来才知道是生成树姿势不够，赶快补一波论文。可以看唐文斌2012年的冬令营课件。这题虽然不是最小乘积生成树但是都一样的做法。首先按A和按B分别求一次最小权匹配。然后更改权值再递归求最远点。递归到距离非正。复杂度好玄学的样子。。好久没写过费用流了。。调都没调一遍写过也是挺爽，就是TM式子搞错了刚了好久才知道。。出现过几次这种情况了。。下次尼玛真的要先检查思路。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 160
#define INF 0x3f7f7f7f
#define ll long long
#define fr first
#define sc second
queue <int> li;bool b[N];
int la[N],c[N*N][4],fi[N],v[N][N][2],h[N],ss,n,m,t,S,T,ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z,int o)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;c[ss][3]=o;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=0;c[ss][3]=-o;fi[y]=ss;
}
void Rebuild(int x,int y)
{
int e=2;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++,e+=2)
c[e^1][3]=-(c[e][3]=x*v[i][j][0]+y*v[i][j][1]);
return;
}
bool SPFA()
{
for (int i=1;i<=n*2;i++) h[i]=INF;h[T]=INF;
h[S]=0;b[S]=true;li.push(S);
while (!li.empty())
{
int k=li.front();b[k]=false;li.pop();
for (int i=fi[k];i;i=c[i][1])
if (c[i][2]&&c[i][3]+h[k]<h[c[i][0]])
{
h[c[i][0]]=h[k]+c[i][3];la[c[i][0]]=i;
if (!b[c[i][0]])
b[c[i][0]]=true,li.push(c[i][0]);
}
}
return h[T]!=INF;
}
void Solve()
{
int q=T,w=INF;
while (q!=S)
w=min(w,c[la[q]][2]),q=c[la[q]^1][0];q=T;
while (q!=S)
c[la[q]][2]-=w,c[la[q]^1][2]+=w,q=c[la[q]^1][0];
return;
}
pair <int,int> Flow()
{
while (SPFA()) Solve();int e=2,s0=0,s1=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++,e+=2)
if (!c[e][2])
c[e][2]=1,c[e^1][2]=0,s0+=v[i][j][0],s1+=v[i][j][1];
ans=min(ans,s0*s1);
for (;e<=ss;e+=2) c[e][2]+=c[e^1][2],c[e^1][2]=0;
return make_pair(s0,s1);
}
void DFS(pair <int,int> x,pair <int,int> y)
{
int q=x.sc-y.sc,w=y.fr-x.fr,e=2;Rebuild(q,w);
pair <int,int> k=Flow();
if (-k.fr*(ll)q-k.sc*w-x.fr*y.sc+x.sc*y.fr>0)
DFS(x,k),DFS(k,y);
return;
}
int main()
{
t=Read();S=N-1;T=N-2;
while (t--)
{
ss=1;memset(fi,0,sizeof(fi));
n=Read();ans=INF;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
Line(i,j+n,1,v[i][j][0]=Read());
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) v[i][j][1]=Read();
for (int i=1;i<=n;i++)
Line(S,i,1,0),Line(i+n,T,1,0);
pair <int,int> k=Flow(),l;Rebuild(0,1);
l=Flow();DFS(k,l);
cout <<ans<<endl;
}
return 0;
}
BZOJ3572：感觉像是每次建出一棵虚树然后询问什么的就是BFS求出虚树每个节点最近节点还有距离。询问什么的倍增搞搞？SB东西调我好久。真是手贱的快感。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 300050
#define M 20
#define INF 0x3f7f7f7f
int s[N][M],h[N],fa[N][M],sg[N],qu[N],fi[N],c[N*2][2];
int Ans[N],mi[N][2],sz[N],rf[N][2],Stack[N],sn,m,n,Qu[N];
int Fi[N],C[N*2][2],a2[M],li[N],rt,st,ss=1,cnt;bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
h[x]=h[fa[x][0]]+1;sz[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
fa[c[i][0]][0]=x,DFS(c[i][0]),sz[x]+=sz[c[i][0]];
sg[x]=++st;return;
}
void Pretreat()
{
DFS(1);
for (int i=2;i<=n;i++)
s[i][0]=sz[fa[i][0]]-sz[i];
for (int i=1;i<M;i++)
for (int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1],
s[j][i]=s[j][i-1]+s[fa[j][i-1]][i-1];
}
inline bool cmp(int x,int y)
{return sg[x]<sg[y];}
int LCA(int x,int y)
{
if (h[x]<h[y]) swap(x,y);
for (int i=M-1;i>=0&&h[x]!=h[y];i--)
if (h[fa[x][i]]>=h[y]) x=fa[x][i];
if (x!=y)
{
for (int i=M-1;i>=0;i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
x=fa[x][0];
}
return x;
}
inline void line(int x,int y)
{
rf[x][0]=y;rf[x][1]=h[x]-h[y];
C[++ss][0]=y;C[ss][1]=Fi[x];Fi[x]=ss;
C[++ss][0]=x;C[ss][1]=Fi[y];Fi[y]=ss;
}
void Set_up()
{
int ri=1;Stack[ri]=qu[1];ss=1;st=0;
for (int i=2;i<=cnt;i++)
{
int k=LCA(qu[i-1],qu[i]);
while (ri&&h[Stack[ri]]>h[k])
line(Stack[ri],ri>1&&h[Stack[ri-1]]>h[k]?
Stack[ri-1]:k),li[++st]=Stack[ri--];
if (Stack[ri]!=k) Stack[++ri]=k;
if (Stack[ri]!=qu[i]) Stack[++ri]=qu[i];
}
while (--ri) line(Stack[ri+1],Stack[ri]),
li[++st]=Stack[ri+1];li[++st]=rt=Stack[1];
rf[rt][0]=0;rf[rt][1]=N;
return;
}
inline void Update(int x,int y,int z)
{
if (mi[x][1]>mi[y][1]+z||(mi[x][1]==mi[y][1]+z&&
mi[x][0]>mi[y][0]))
mi[x][0]=mi[y][0],mi[x][1]=mi[y][1]+z;
}
void DSF(int x)
{
if (b[x]) mi[x][0]=x,mi[x][1]=0; else mi[x][1]=INF;
for (int i=Fi[x];i;i=C[i][1])
if (C[i][0]!=rf[x][0])
DSF(C[i][0]),Update(x,C[i][0],rf[C[i][0]][1]);
}
void DSS(int x)
{
if (x!=rt) Update(x,rf[x][0],rf[x][1]);
for (int i=Fi[x];i;i=C[i][1])
if (C[i][0]!=rf[x][0]) DSS(C[i][0]);
return;
}
inline bool Check(int x,int y,int z)
{
int k=mi[y][1]+h[y]-h[x],l=mi[z][1]+h[x]-h[z];
return k<l||(k==l&&mi[y][0]<mi[z][0]);
}
int Get_Ans(int x)
{
int Cnt=sz[x],now=x,tot=0;
for (int i=Fi[x];i;i=C[i][1])
if (C[i][0]!=rf[x][0])
tot+=Get_Ans(C[i][0]);Cnt-=tot;
if (x!=rt)
for (int i=M-1;i>=0;i--)
if (h[fa[now][i]]>h[rf[x][0]]&&Check(fa[now][i],x,rf[x][0]))
Cnt+=s[now][i],now=fa[now][i];
Ans[mi[x][0]]+=Cnt;
return Cnt+tot;
}
void Solve()
{
DSF(rt);DSS(rt);Get_Ans(rt);
Ans[mi[rt][0]]+=sz[1]-sz[rt];
for (int i=1;i<=st;i++) Fi[li[i]]=0;
return;
}
int main()
{
n=Read();a2[0]=1;
for (int i=1;i<M;i++) a2[i]=a2[i-1] << 1;
for (int i=1;i<n;i++) Line(Read(),Read());
m=Read();Pretreat();
int Tot=0;
while (m--)
{
cnt=Read();Tot+=cnt;
for (int i=1;i<=cnt;i++) b[qu[i]=Qu[i]=Read()]=true;
sort(qu+1,qu+cnt+1,cmp);
Set_up();Solve();
for (int i=1;i<=cnt;i++)
printf("%d ",Ans[Qu[i]]),b[Qu[i]]=false,
Ans[Qu[i]]=0;
puts("");
}
return 0;
}
BZOJ3573：题面长的一笔。如果没理解错题意我感觉就只要每个节点存下其到一号节点的所有节点儿子数乘积，这东西随便模两个数就好了。然后乘以自身的值最后排个序判个重？
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 500050
#define P 998244353
#define M 1000000007
#define ll long long
#define fr first
#define sc second
pair <int,int> li[N];
int ans,n,m,ss=1,d[N],fi[N],c[N*2][2],v[N];ll h[N][2];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;d[x]++;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;d[y]++;
}
void DFS(int x,int fa)
{
d[x]-=fa>0;
h[x][0]=h[fa][0]*d[x]%P;h[x][1]=h[fa][1]*d[x]%M;
li[x].fr=h[fa][0]*v[x]%P;li[x].sc=h[fa][1]*v[x]%M;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa) DFS(c[i][0],x);
}
int main()
{
n=Read();
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
h[0][1]=h[0][0]=1;DFS(1,0);
sort(li+1,li+n+1);ans=n;
for (int i=1;i<=n;i++)
{
int k=i;
while (k<n&&li[k+1]==li[k]) k++;
ans=min(ans,n-k+i-1);i=k;
}
cout <<ans<<endl;
return 0;
}
BZOJ3574：为什么我感觉只要判断前缀后缀相不相同？就是每个字符串从前数从后数不到*的部分。感觉这东西能证：去掉前后缀每个字符串就只剩下一些*号开头*号结尾的东西了，所以我们就构造一个字符串是所有字符串的中间这东西拼起来的串。en貌似还要特判掉中间没有*号的一些情况，也就是一波KMP。话说BZOJ上面的题面能看。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 30000050
char b[M],*a[N],c[M];int n,m,t,fail[M],len[N],bg[N],ed[N];
bool Check_Pre(int x,int y)
{
for (int i=0;i<bg[x];i++)
if (a[x][i]!=a[y][i]) return false;
return true;
}
bool Check_Suf(int x,int y)
{
for (int i=len[x]-1;i>=ed[x];i--)
if (a[x][i]!=a[y][len[y]-len[x]+i]) return false;
return true;
}
bool Solve0(int x,int y)
{
for (int i=1;i<=n;i++)
if (!Check_Pre(i,x)||!Check_Suf(i,y)) return false;
return true;
}
bool Solve1(int x)
{
for (int i=1;i<=n;i++)
if (ed[i]==-1)
{
if (len[i]!=len[x]) return false;
for (int j=0;j<len[i];j++)
if (a[i][j]!=a[x][j]) return false;
} else
{
if (bg[i]>=len[x]||!Check_Pre(i,x)||
len[i]-ed[i]>len[x]||!Check_Suf(i,x))
return false;
int le=bg[i]+1,now=bg[i]+1;
while (true)
{
while (le<len[i]&&a[i][le]=='*') le++;
if (le>=ed[i]) break;
int k=le,l=-1;
while (a[i][k+1]!='*') k++;
if (now+k-le+1>len[x]) return false;
fail[0]=-1;
for (int j=1;j<=k-le;j++)
{
fail[j]=fail[j-1];
while (fail[j]!=-1&&a[i][j+le]!=
a[i][fail[j]+1+le]) fail[j]=fail[fail[j]];
if (a[i][j+le]==a[i][fail[j]+1+le])
fail[j]++;
}
for (;now<len[x];now++)
if (l==k-le) break; else
{
while (l!=-1&&a[i][l+le+1]!=a[x][now])
l=fail[l];
if (a[i][l+le+1]==a[x][now]) l++;
}
if (l!=k-le||now>len[x]-(len[i]-ed[i]))
return false;
le=k+1;
}
}
return true;
}
bool Solve()
{
int rt=0,ma0=0,ma1=0;
for (int i=1;i<=n;i++)
{
bg[i]=len[i];ed[i]=-1;
for (int j=0;j<len[i];j++)
if (a[i][j]=='*')
bg[i]=min(bg[i],j-1),ed[i]=max(ed[i],j+1);
if (ed[i]==-1) rt=i; else
{
if (!ma0||bg[i]+1>bg[ma0]+1) ma0=i;
if (!ma1||len[i]-ed[i]>len[ma1]-ed[ma1]) ma1=i;
}
}
if (!rt) return Solve0(ma0,ma1); else return Solve1(rt);
}
int main()
{
cin >>t;
while (t--)
{
cin >>n;a[1]=&b[0];
for (int i=1;i<=n;i++)
scanf("%s",a[i]),len[i]=strlen(a[i]),
a[i+1]=a[i]+len[i];
puts(Solve()?"Y":"N");
}
return 0;
}
BZOJ3575：不行了，调了好久，感觉我的做法确实是有问题的。后来Orz了ydc的做法，感觉ydc真是太神了。en具体细节就看他的题解吧。只不过复杂度确实是个大玄学，我反正不知道复杂度，但是感觉随机情况下应该比较快吧。至于这样玩SPFA的正确性，因为反正那些最短路径边碰到就会停止所以正确性是没有问题的。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 200050
#define INF 0x3f7f7f7f
struct Node
{int x,y;};
priority_queue <Node> Aha;
queue <int> li;bool b[N],d[N];
int n,m,p,ss,t,fi[N],c[M][3],dis[N],ln[N],pre[N],suf[N];
int cur[N],Po[N],sg[N],Li[N];
bool operator< (const Node &A,const Node &B)
{return A.x>B.x;}
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int z,int y,int x)
{c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;}
void SPFA(int x)
{
int ri=0;
li.push(x);dis[x]=pre[x];b[x]=true;
while (!li.empty())
{
int k=li.front();b[k]=false;li.pop();
for (int i=fi[k];i;i=c[i][1])
if (d[c[i][0]])
{
if (dis[k]+c[i][2]+suf[c[i][0]]<dis[c[i][0]]&&
sg[c[i][0]]>sg[x]&&i!=ln[t])
{
dis[c[i][0]]=suf[c[i][0]]+c[i][2]+dis[k];
if (cur[c[i][0]]!=t)
cur[Li[++ri]=c[i][0]]=t;
}
} else
if (dis[k]+c[i][2]<dis[c[i][0]])
{
dis[c[i][0]]=dis[k]+c[i][2];
if (!b[c[i][0]])
b[c[i][0]]=true,li.push(c[i][0]);
}
}
for (int i=1;i<=ri;i++)
Aha.push((Node){dis[Li[i]],sg[Li[i]]});
return;
}
int main()
{
n=Read();m=Read();p=Read();d[sg[Po[1]=1]=1]=true;
for (int i=1;i<=m;i++) Line(Read(),Read(),Read());
for (int i=1;i<=p;i++)
sg[Po[i+1]=c[ln[i]=Read()][0]]=i+1,d[Po[i+1]]=true;
for (int i=1;i<=n;i++) dis[i]=INF;
for (int i=1;i<=p;i++) pre[Po[i+1]]=pre[Po[i]]+c[ln[i]][2];
for (int i=p;i>=1;i--) suf[Po[i]]=suf[Po[i+1]]+c[ln[i]][2];
for (t=1;t<=p;t++)
{
SPFA(Po[t]);
while (!Aha.empty()&&Aha.top().y<=t) Aha.pop();
if (Aha.empty()) puts("-1"); else
printf("%d\n",Aha.top().x);
}
return 0;
}
BZOJ3576：半年前的我都会做！我记得好像是SG函数搞搞，然后还有个什么分块吧。因为很早以前做过了所以就不放上来了。
HNOI2014完结。
果然HNOI的画风才是最好的。不像浙江那样，人类何苦互相伤害嘛。（好吧其实事实是窝只会刷水= =
下面找些看上去比较好玩的题目好了。
BZOJ3622：一开始以为是之前NOIP考过的一个DP题，于是一开始wa了n遍，后来做这题的时候意识比较模糊了，结果犯逗没想出正解= =。明明只要在那个做法上面改动一点点就好了的。总有种把这题浪费了的感觉
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 2050
#define P 1000000009
#define ll long long
ll s[N][N],JC[N],C[N][N];int v[N],t[N],n,m;
inline int Read()
{
int x=0;char y;bool z=false;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
int main()
{
n=Read();m=Read();JC[0]=1;
for (int i=0;i<N;i++) C[i][0]=1;
for (int i=1;i<N;i++)
for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
for (int i=1;i<N;i++) JC[i]=JC[i-1]*i%P;
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=n;i++) t[i]=Read();
if ((n-m)&1) {puts("0");return 0;}
m=m+(n - m >> 1);
sort(v+1,v+n+1);sort(t+1,t+n+1);
int ri=0;s[0][0]=1;
for (int i=1;i<=n;i++)
{
while (ri<n&&v[i]>t[ri+1]) ri++;s[i][0]=1;
for (int j=1;j<=ri;j++)
s[i][j]=(s[i-1][j]+s[i-1][j-1]*(ri-j+1))%P;
}
for (int i=0;i<=n;i++) s[n][i]=s[n][i]*JC[n-i]%P;
for (int i=n-1;i>=0;i--)
for (int j=i+1;j<=n;j++)
s[n][i]=(s[n][i]-s[n][j]*C[j][i]%P+P)%P;
cout <<s[n][m]<<endl;
return 0;
}
BZOJ3636：一直在想些奇怪的东西但是并没有想出来，TM无脑分治就好了啊。为毛每次我写东西总是会刚那种最麻烦最容易出错的写法然后调又调不出。代码能力太弱TAT
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define N 100050
#define M 52
#define fr first
#define sc second
vector <pair <int,int> > a[N];
int ma[N][M],n,m,p,v[N],s[N],Ans[N];
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
void Solve(int x,int y)
{
if (x==y) return;
int k=x + y >> 1;
for (int i=1;i<=p;i++) ma[k][i]=0;
for (int i=k-1;i>=x;i--)
for (int j=1;j<=p;j++)
ma[i][j]=max(ma[i+1][j],i+p-1<=k-j?s[i]+ma[i+p][j]:0);
for (int i=k+1;i<=y;i++)
for (int j=1;j<=p;j++)
ma[i][j]=max(ma[i-1][j],i-p+1>=k+j?s[i-p+1]+ma[i-p][j]:0);
for (int i=x;i<=k;i++)
{
int sz=a[i].size();
for (int j=sz-1;j>=0&&a[i][j].fr>k;j--)
{
int sg=a[i][j].sc,ed=a[i][j].fr;
Ans[sg]=ma[i][1]+ma[ed][1];
for (int e=k;e>=max(i,k-p+1);e--)
Ans[sg]=max(Ans[sg],(e+p-1>ed?0:s[e]+ma[ed][p-k+e])+
ma[i][k-e+1]);
a[i].pop_back();
}
}
Solve(x,k);Solve(k+1,y);
return;
}
int main()
{
n=Read();p=Read();
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=n;i++)
for (int j=0;j<p;j++) s[i]+=v[i+j];
m=Read();
for (int i=1;i<=m;i++)
{
int k=Read(),l=Read();
if (k==l) Ans[i]=p==1?max(v[k],0):0; else
a[k].push_back(make_pair(l,i));
}
for (int i=1;i<=n;i++) sort(a[i].begin(),a[i].end());
Solve(1,n);
for (int i=1;i<=m;i++) printf("%d\n",Ans[i]);
return 0;
}
BZOJ3674：en首先可持久化那个father数组，然后按深度启发式合并并查集就好了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define M 10000050
#define fr first
#define sc second
struct Node
{int v;Node* c[2];} *Gf[N],statePool[M],*Cur;
int n,m,t,ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
Node* Set_up(int x,int y)
{
int i=x + y >> 1;Node* j=Cur++;j->v=-1;
if (x!=y) j->c[0]=Set_up(x,i),j->c[1]=Set_up(i+1,y);
return j;
}
int Query(int x,int y,Node* z,int o)
{
int i=x + y >> 1;
if (x==y) return z->v; else
return o>i?Query(i+1,y,z->c[1],o):Query(x,i,z->c[0],o);
}
pair <int,int> Find(int x)
{
while (true)
{
int k=Query(1,n,Gf[t-1],x);
if (k<0) return make_pair(x,k); else x=k;
}
}
Node* Insert(int x,int y,Node* z,int o,int p)
{
int i=x + y >> 1;Node *j=Cur++;
if (x==y) j->v=p; else
if (o>i)
j->c[1]=Insert(i+1,y,z->c[1],o,p),j->c[0]=z->c[0]; else
j->c[0]=Insert(x,i,z->c[0],o,p),j->c[1]=z->c[1];
return j;
}
void Merge(pair <int,int> x,pair <int,int> y)
{
if (x.sc>y.sc) swap(x,y);
Gf[t]=Insert(1,n,Gf[t-1],y.fr,x.fr);
Gf[t]=Insert(1,n,Gf[t],x.fr,min(y.sc-1,x.sc));
return;
}
int main()
{
n=Read();m=Read();
Cur=statePool;Gf[0]=Set_up(1,n);
for (t=1;t<=m;t++)
{
int e=Read();
if (e==1) Merge(Find(Read()^ans),Find(Read()^ans)); else
if (e==2) Gf[t]=Gf[Read()^ans]; else
printf("%d\n",ans=(Find(Read()^ans).fr==
Find(Read()^ans).fr)),Gf[t]=Gf[t-1];
}
return 0;
}
BZOJ3673：en好吧是凑数的，跟上题代码只删掉了那个强制在线
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define M 10000050
#define fr first
#define sc second
struct Node
{int v;Node* c[2];} *Gf[N],statePool[M],*Cur;
int n,m,t,ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
Node* Set_up(int x,int y)
{
int i=x + y >> 1;Node* j=Cur++;j->v=-1;
if (x!=y) j->c[0]=Set_up(x,i),j->c[1]=Set_up(i+1,y);
return j;
}
int Query(int x,int y,Node* z,int o)
{
int i=x + y >> 1;
if (x==y) return z->v; else
return o>i?Query(i+1,y,z->c[1],o):Query(x,i,z->c[0],o);
}
pair <int,int> Find(int x)
{
while (true)
{
int k=Query(1,n,Gf[t-1],x);
if (k<0) return make_pair(x,k); else x=k;
}
}
Node* Insert(int x,int y,Node* z,int o,int p)
{
int i=x + y >> 1;Node *j=Cur++;
if (x==y) j->v=p; else
if (o>i)
j->c[1]=Insert(i+1,y,z->c[1],o,p),j->c[0]=z->c[0]; else
j->c[0]=Insert(x,i,z->c[0],o,p),j->c[1]=z->c[1];
return j;
}
void Merge(pair <int,int> x,pair <int,int> y)
{
if (x.sc>y.sc) swap(x,y);
Gf[t]=Insert(1,n,Gf[t-1],y.fr,x.fr);
Gf[t]=Insert(1,n,Gf[t],x.fr,min(y.sc-1,x.sc));
return;
}
int main()
{
n=Read();m=Read();
Cur=statePool;Gf[0]=Set_up(1,n);
for (t=1;t<=m;t++)
{
int e=Read();
if (e==1) Merge(Find(Read()),Find(Read())); else
if (e==2) Gf[t]=Gf[Read()]; else
printf("%d\n",ans=(Find(Read()).fr==
Find(Read()).fr)),Gf[t]=Gf[t-1];
}
return 0;
}
BZOJ3489：这题脑洞了好久。。太弱。。首先提出每一个数值，数值v的位置是Av,1，Av,2,……，所以我们当Av,i-1<L<=Av,i且Av,i<=R<Av,i+1的时候v对答案是有贡献的，所以就有n个矩形，问题变成我们要求点(L,R)被覆盖上的数值的最大值。如果不是强制在线肯定就可以用扫描线+线段树套堆解决了。但是我们现在强制在线，于是考虑可持久化。对于每个横坐标我们建一棵线段树套线段树，每个矩形的纵坐标[D,H]套到线段树里面的log个节点。每次加入或者删除一段区间就是改变差不多log^2个线段树上面的节点。同时里面的线段树肯定不能直接复制一遍，于是我们里面还要可持久化，同样新建一条链，但是只要改变外层的log个线段树上面的节点所以空间改变也是log^2的。所以时空复杂度都是n log^2。写起来也是比较带感的。(劳资辛苦写的树套树就说MLE？管他的我不会特殊的卡空间卡常技巧。。拍了个小数据好像没问题的样子就弃疗了，以后或许会好雅兴回来填坑的）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
#define M 40000020
struct Set_Tree
{int c[M][2];} A;
struct Ment_Tree
{int c[M][2],sn[M];} B;
int sA,sB,n,m,ans,st,v[N],gf[N],now[N],ne[N],cz[N*2][4],sg[N*2];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void GetIn(int &x,int &y)
{x=(x+ans)%n+1;y=(y+ans)%n+1;if (x>y) swap(x,y);}
int Strick_Out(int x,int y,int z,int o)
{
int i=x + y >> 1,j=0,k,l;
if (x==y) return 0;
if (o<=i) k=Strick_Out(x,i,A.c[z][0],o),l=A.c[z][1]; else
l=Strick_Out(i+1,y,A.c[z][1],o),k=A.c[z][0];
if (k||l) A.c[j=++sA][0]=k,A.c[sA][1]=l;
return j;
}
int Delete(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=0,k,l;
if (x==o&&y==p)
{
k=Strick_Out(1,n,B.sn[z],u);
if (k||B.c[z][0]||B.c[z][1])
B.c[j=++sB][0]=B.c[z][0],B.c[j][1]=B.c[z][1],B.sn[j]=k;
return j;
}
if (i>=p) k=Delete(x,i,B.c[z][0],o,p,u),l=B.c[z][1]; else
if (o>i) k=B.c[z][0],l=Delete(i+1,y,B.c[z][1],o,p,u); else
k=Delete(x,i,B.c[z][0],o,i,u),
l=Delete(i+1,y,B.c[z][1],i+1,p,u);
if (k||l||B.sn[z])
B.c[j=++sB][0]=k,B.c[j][1]=l,B.sn[j]=B.sn[z];
return j;
}
int Infix(int x,int y,int z,int o)
{
int i=x + y >> 1,j=++sA;
if (x==y) return j; else
if (o<=i)
A.c[j][0]=Infix(x,i,A.c[z][0],o),A.c[j][1]=A.c[z][1]; else
A.c[j][1]=Infix(i+1,y,A.c[z][1],o),A.c[j][0]=A.c[z][0];
return j;
}
int Insert(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=++sB;
if (x==o&&y==p)
{
B.c[j][0]=B.c[z][0],B.c[j][1]=B.c[z][1];
B.sn[j]=Infix(1,n,B.sn[z],u);return j;
}
if (p<=i)
B.c[j][0]=Insert(x,i,B.c[z][0],o,p,u),
B.c[j][1]=B.c[z][1]; else
if (o>i)
B.c[j][1]=Insert(i+1,y,B.c[z][1],o,p,u),
B.c[j][0]=B.c[z][0]; else
B.c[j][0]=Insert(x,i,B.c[z][0],o,i,u),
B.c[j][1]=Insert(i+1,y,B.c[z][1],i+1,p,u);
B.sn[j]=B.sn[z];
return j;
}
int Enquiry(int x,int y,int z)
{
int i=x + y >> 1;
if (x==y) return x; else
if (A.c[z][1]) return Enquiry(i+1,y,A.c[z][1]); else
return Enquiry(x,i,A.c[z][0]);
}
int Query(int x,int y,int z,int o)
{
int i=x + y >> 1,Ans=B.sn[z]?Enquiry(1,n,B.sn[z]):0;
if (x==y) return Ans;
if (o<=i) return max(Ans,Query(x,i,B.c[z][0],o)); else
return max(Ans,Query(i+1,y,B.c[z][1],o));
}
inline bool cmp(int x,int y)
{return abs(cz[x][0])<abs(cz[y][0]);}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
ne[now[v[i]=Read()]]=i,now[v[i]]=i;
memset(now,0,sizeof(now));
for (int i=1;i<=n;i++)
{
int k=now[v[i]]+1,l=ne[i]==0?n:ne[i]-1;
cz[sg[++st]=st][0]=k;cz[st][1]=i;cz[st][2]=l;
cz[st][3]=v[i];cz[sg[++st]=st][0]=-i-1;cz[st][1]=i;
cz[st][2]=l;cz[st][3]=v[i];now[v[i]]=i;
}
sort(sg+1,sg+st+1,cmp);
gf[0]=sA=1;int Now=1;
for (int i=1;i<=n;i++)
{
int k=Now-1;while (k<st&&abs(cz[sg[k+1]][0])==i) k++;
gf[i]=gf[i-1];
for (;Now<=k;Now++)
if (cz[sg[Now]][0]<0)
gf[i]=Delete(1,n,gf[i],cz[sg[Now]][1],cz[sg[Now]][2],
cz[sg[Now]][3]); else
gf[i]=Insert(1,n,gf[i],cz[sg[Now]][1],cz[sg[Now]][2],
cz[sg[Now]][3]);
}
for (int i=1;i<=m;i++)
{
int k=Read(),l=Read();GetIn(k,l);
printf("%d\n",ans=Query(1,n,gf[k],l));
}
return 0;
}
BZOJ3809：首先莫队+线段树的做法很明显，也很明显会爆。所以我们考虑加特技！首先块大小为sqrt(n)，然后我们每次如果只覆盖了一块的就直接暴力，这是msqrt(n)的，否则询问右边部分、暴力左边小于sqrt(n)的部分，这是msqrt(n)+n sqrt(n)*log n的。感觉常数好难卡过的样子。。有的做法用分块代替树状数组？并没有想到= =感觉常数好像要比我优的样子。常数卡好死。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 400
int rt,n,m,Ans[N*10],qu[N*10][4],v[N],sg[N*10],s[N],cnt[M];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline int Sg(int x) {return (qu[x][0]-1)/rt;}
inline bool cmp(int x,int y)
{
int k=Sg(x),l=Sg(y);
return k<l||(k==l&&qu[x][1]<qu[y][1]);
}
int GetAns(int x,int y)
{
int ans=0,le=(x+rt-2)/rt,ri=y/rt-1;
if (y-x+1<rt)
{
for (int i=x;i<=y;i++) ans+=s[i]>0;
return ans;
}
for (int i=le;i<=ri;i++) ans+=cnt[i];
for (int i=x;i<=le*rt;i++) ans+=s[i]>0;
for (int i=(ri+1)*rt+1;i<=y;i++) ans+=s[i]>0;
return ans;
}
int main()
{
n=Read();m=Read();rt=sqrt(n);
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=m;i++)
qu[i][0]=Read(),qu[i][1]=Read(),qu[i][2]=Read(),
qu[i][3]=Read(),sg[i]=i;
sort(sg+1,sg+m+1,cmp);
for (int i=1;i<=m;i++)
{
memset(s,0,sizeof(s));memset(cnt,0,sizeof(cnt));
int k=i,le=qu[sg[i]][0],ri=qu[sg[i]][1];
while (k<m&&Sg(sg[k+1])==Sg(sg[i])) k++;
for (int j=le;j<=ri;j++)
if (s[v[j]]++==0) cnt[(v[j]-1)/rt]++;
Ans[sg[i]]=GetAns(qu[sg[i]][2],qu[sg[i]][3]);
for (int j=i+1;j<=k;j++)
{
int Le=qu[sg[j]][0],Ri=qu[sg[j]][1];
for (int l=le-1;l>=Le;l--)
if (s[v[l]]++==0) cnt[(v[l]-1)/rt]++;
for (int l=ri+1;l<=Ri;l++)
if (s[v[l]]++==0) cnt[(v[l]-1)/rt]++;
for (int l=le;l<Le;l++)
if (--s[v[l]]==0) cnt[(v[l]-1)/rt]--;
le=Le;ri=Ri;
Ans[sg[j]]=GetAns(qu[sg[j]][2],qu[sg[j]][3]);
}
i=k;
}
for (int i=1;i<=m;i++)
printf("%d\n",Ans[i]);
return 0;
}
BZOJ3747：从左往右扫一遍，顺便维护左端点到每个点的答案。每次改变也只会改变两个区间的答案。所以随便线段树搞搞。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1000050
#define INF 2333233323332333LL
#define ll long long
ll ma[N*4],ad[N*4],ans;int v[N],f[N],now[N],ne[N],n,m;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline ll max(ll x,ll y)
{return x<y?y:x;}
inline void adj(int x,int y,int z)
{
if (ad[z]==0) return;
if (x!=y) ad[z*2]+=ad[z],ad[z*2+1]+=ad[z];
ma[z]+=ad[z];ad[z]=0;
return;
}
void Insert(int x,int y,int z,int o,ll p)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==y) {ma[z]=p;return;}
if (o<=i) Insert(x,i,j,o,p),adj(i+1,y,j+1); else
Insert(i+1,y,j+1,o,p),adj(x,i,j);
ma[z]=max(ma[j],ma[j+1]);
return;
}
void Modify(int x,int y,int z,int o,int p,ll u)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==o&&y==p) {ad[z]+=u;adj(x,y,z);return;}
if (p<=i) Modify(x,i,j,o,p,u),adj(i+1,y,j+1); else
if (o>i) Modify(i+1,y,j+1,o,p,u),adj(x,i,j); else
Modify(x,i,j,o,i,u),Modify(i+1,y,j+1,i+1,p,u);
ma[z]=max(ma[j],ma[j+1]);
return;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
f[i]=Read(),ne[now[f[i]]]=i,now[f[i]]=i;
memset(now,0,sizeof(now));
for (int i=1;i<=m;i++) v[i]=Read();
ll Now=0;
for (int i=1;i<=n;i++)
{
if (now[f[i]]==0) now[f[i]]=true,Now+=v[f[i]]; else
if (now[f[i]]==1) now[f[i]]=2,Now-=v[f[i]];
Insert(1,n,1,i,Now);
}
ans=ma[1];
for (int i=2;i<=n;i++)
{
Insert(1,n,1,i-1,-INF);
if (!ne[i-1]) Modify(1,n,1,i,n,-v[f[i-1]]); else
Modify(1,n,1,i-1,ne[i-1]-1,-v[f[i-1]]),
Modify(1,n,1,ne[i-1],ne[ne[i-1]]==0?n:ne[ne[i-1]]-1,
v[f[i-1]]);
adj(1,n,1);ans=max(ans,ma[1]);
}
cout <<ans<<endl;
return 0;
}
BZOJ3555：无脑Hash
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 205
#define M 6000050
#define P1 1000000007
#define P2 998244353
#define Base +10086
#define fr first
#define sc second
#define ll long long
pair <int,int> li[M];
int n,m,st;char b[N];ll ans,Power[N][2];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void GetHash()
{
ll cnt0=0,cnt1=0;
for (int i=1;i<=m;i++)
cnt0=(cnt0+b[i]*Power[i][0]%P1)%P1,
cnt1=(cnt1+b[i]*Power[i][1]%P2)%P2;
for (int i=1;i<=m;i++)
li[++st]=make_pair((cnt0+P1-b[i]*Power[i][0]%P1)%P1,
(cnt1+P2-b[i]*Power[i][1]%P2)%P2);
return;
}
int main()
{
n=Read();m=Read();Read();Power[0][0]=Power[0][1]=1;
for (int i=1;i<N;i++)
Power[i][0]=Power[i-1][0]*Base%P1,
Power[i][1]=Power[i-1][1]*Base%P2;
for (int i=1;i<=n;i++)
scanf("%s",b+1),GetHash();
sort(li+1,li+st+1);
for (int i=1;i<=st;i++)
{
int k=i;
while (k<st&&li[k+1]==li[i]) k++;
ans+=(ll)(k-i)*(k-i+1)/2;i=k;
}
cout <<ans<<endl;
return 0;
}
玛德不玩了直接来一波JOI来强行刷进度吧。感觉JOI有的题还是很有趣的。而且代码都不长。
BZOJ4236：无脑map
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
#define N 200050
#define fr first
#define sc second
map <pair <int,int>,int> li;
map <pair <int,int>,int> :: iterator it;
char a[N];int ans,n;
int main()
{
scanf("%d%s",&n,a+1);li[make_pair(0,0)]=0;
int cnt0=0,cnt1=0,cnt2=0;
for (int i=1;i<=n;i++)
{
if (a[i]=='J') cnt0++; else
if (a[i]=='O') cnt1++; else cnt2++;
pair <int,int> k=make_pair(cnt1-cnt0,cnt2-cnt1);
it=li.find(k);
if (li.end()==it) li[k]=i; else ans=max(ans,i-it->sc);
}
cout <<ans<<endl;
return 0;
}
BZOJ4237：按y坐标分治
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 200050
#define fr first
#define sc second
#define ll long long
int li[N],Li[N],n,m,wz[N][2],sg[N],ri,Ri;ll ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline bool cmp(int x,int y)
{return wz[x][1]<wz[y][1];}
inline bool Cmp(int x,int y)
{return wz[x][0]<wz[y][0];}
int Half_Find(int x,int y,int z)
{
int i=x + y >> 1;
if (x>y) return 0;
if (wz[li[i]][0]>z) return max(Half_Find(x,i-1,z),ri-i+1); else
return Half_Find(i+1,y,z);
}
void Solve(int x,int y)
{
if (x==y) return;
int k=x + y >> 1;
sort(sg+x,sg+y+1,cmp);
sort(sg+x,sg+k+1,Cmp);sort(sg+k+1,sg+y+1,Cmp);
int now=x,Now=k+1;
for (int i=x;i<=y;i++)
if (Now==y+1||(now<k+1&&wz[sg[now]][0]<wz[sg[Now]][0]))
{
while (ri&&wz[li[ri]][1]<wz[sg[now]][1]) ri--;
li[++ri]=sg[now++];
} else
{
while (Ri&&wz[Li[Ri]][1]>wz[sg[Now]][1]) Ri--;
ans+=Half_Find(1,ri,Ri?wz[Li[Ri]][0]:-1);
Li[++Ri]=sg[Now++];
}
ri=Ri=0;
Solve(x,k);Solve(k+1,y);
return;
}
int main()
{
n=Read();
for (int i=1;i<=n;i++) wz[i][0]=Read(),wz[i][1]=Read();
for (int i=1;i<=n;i++) sg[i]=i;
Solve(1,n);
cout <<ans<<endl;
return 0;
}
BZOJ4238：找出所有在所有奇环上面但是不在任何一个偶环上面的边，DFS就好。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 200050
#define fr first
#define sc second
bool cl[N],vis[N],b[N],Aha[M];
int fi[N],c[M*2][2],Add[N][2],s[M][2],st,ss=1,n,m,ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
pair <int,int> DFS(int x,int y)
{
vis[x]=b[x]=true;cl[x]=!cl[c[y][0]];
int cnt[2];cnt[0]=cnt[1]=0;Aha[y/2]=true;
for (int i=fi[x];i;i=c[i][1])
if (vis[c[i][0]]&&i!=y&&b[c[i][0]])
{
bool flag=cl[x]^cl[c[i][0]];
if (!flag) st++;
cnt[flag]++;Add[c[i][0]][flag]++;
} else
if (!vis[c[i][0]])
{
pair <int,int> k=DFS(c[i][0],i^1);
cnt[0]+=k.fr,cnt[1]+=k.sc;
}
s[y/2][0]=cnt[0]-Add[x][0];
s[y/2][1]=cnt[1]-Add[x][1];b[x]=false;
return make_pair(s[y/2][0],s[y/2][1]);
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++) Line(Read(),Read());
for (int i=1;i<=n;i++)
if (!vis[i]) DFS(i,0);
for (int i=1;i<=m;i++)
if (!s[i][1]&&s[i][0]==st&&Aha[i]) ans++;
if (st==1) ans++;
cout <<ans<<endl;
return 0;
}
BZOJ4239：询问和边按时间排序，边按时间加入，每次加入就跑一次SPFA，但是只能用那些还没有用来更新过的边，也就是每个点维护一个heap来存所有没更新过的边然后更新。这样就是一个log的复杂度了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 300050
#define INF 0x3f7f7f7f
#define fr first
#define sc second
priority_queue <pair <int,int> > li[N];
pair <int,int> qu[N];queue <int> Li;bool b[N];
int n,m,p,fi[N],c[M*2][4],ss,dis[N],Ans[N],ln[M][3],sg[M];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int o,int z,int y,int x)
{
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;c[ss][3]=o;fi[y]=ss;
ln[ss][0]=o;ln[ss][1]=y;ln[ss][2]=sg[ss]=ss;
}
inline bool cmp(int x,int y)
{return ln[x][0]<ln[y][0];}
void Solve()
{
int cur=1;dis[n]=INF;
for (int i=1;i<=m;i++)
{
int now=ln[sg[i]][0];
while (cur<=p&&qu[cur].fr<now)
Ans[qu[cur++].sc]=dis[1];
li[ln[sg[i]][1]].push(make_pair(-now,ln[sg[i]][2]));
Li.push(ln[sg[i]][1]);b[ln[sg[i]][1]]=true;
while (!Li.empty())
{
int k=Li.front();Li.pop();b[k]=false;
while (!li[k].empty()&&-li[k].top().fr<=dis[k])
{
pair <int,int> l=li[k].top();li[k].pop();
if (dis[c[l.sc][0]]<c[l.sc][2])
{
dis[c[l.sc][0]]=c[l.sc][2];
if (!b[c[l.sc][0]])
b[c[l.sc][0]]=true,Li.push(c[l.sc][0]);
}
}
}
}
while (cur<=p) Ans[qu[cur++].sc]=dis[1];
return;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++) Line(Read(),Read(),Read(),Read());
p=Read();sort(sg+1,sg+m+1,cmp);
for (int i=1;i<=p;i++) qu[i]=make_pair(Read(),i);
for (int i=1;i<n;i++) dis[i]=-1;
sort(qu+1,qu+p+1);
Solve();
for (int i=1;i<=p;i++) printf("%d\n",Ans[i]);
return 0;
}
BZOJ4240：脑洞好大没想出来= =贪心+构造证明
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 300050
#define M 12000050
#define INF 0x3f7f7f7f
#define ll long long
int st,gf,c[M][2],v[N],s[M],Ans[N],n;ll ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int Query(int x,int y,int z,int o,int p)
{
int i=x + y >> 1;
if (x==o&&y==p) return s[z];
if (p<=i) return Query(x,i,c[z][0],o,p); else
if (o>i) return Query(i+1,y,c[z][1],o,p); else
return Query(x,i,c[z][0],o,i)+Query(i+1,y,c[z][1],i+1,p);
}
inline int New()
{st++;c[st][0]=c[st][1]=s[st]=0;return st;}
int Insert(int x,int y,int z,int o)
{
int i=x + y >> 1;
if (!z) z=New();
if (x!=y)
if (o<=i) c[z][0]=Insert(x,i,c[z][0],o); else
c[z][1]=Insert(i+1,y,c[z][1],o);
return s[z]++,z;
}
int main()
{
n=Read();
for (int i=1;i<=n;i++) v[i]=Read();
gf=st=1;
for (int i=1;i<=n;i++)
Ans[i]=Query(1,INF,gf,v[i]+1,INF),Insert(1,INF,gf,v[i]);
st=0;gf=New();
for (int i=n;i>=1;i--)
ans+=min(Ans[i],Query(1,INF,gf,v[i]+1,INF)),
Insert(1,INF,gf,v[i]);
cout <<ans<<endl;
return 0;
}
BZOJ4241：一眼莫队+set，当然时间会挂。于是考虑去掉删除操作，这样就可以直接维护最大值。于是可以每一个询问分成两份：小于sqrt(n)的和其余部分。左边的暴力处理，右边的跟原来一样。貌似直接跑的飞起？
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define fr first
#define sc second
#define ll long long
pair <int,int> li[N];
int v[N],sg[N],s[N],val[N],S[N][2],qu[N][2],Aha[N],n,m,rt,st;
ll ma,Ans[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
for (int i=1;i<=n;i++) li[i]=make_pair(v[i],i);
sort(li+1,li+n+1);
for (int i=1;i<=n;)
{
int k=i;
while (k<n&&li[k+1].fr==li[i].fr) k++;
val[++st]=li[i].fr;
for (;i<=k;i++) v[li[i].sc]=st;
}
return;
}
inline bool cmp(int x,int y)
{return Aha[qu[x][0]]<Aha[qu[y][0]]||
(Aha[qu[x][0]]==Aha[qu[y][0]]&&qu[x][1]<qu[y][1]);}
inline ll max(ll x,ll y)
{return x>y?x:y;}
inline void Add(int x)
{ma=max(ma,(ll)(++s[x])*val[x]);}
void Solve(int x,int y,int z)
{
st++;Ans[z]=ma;
for (int i=x;i<=y;i++)
{
if (S[v[i]][1]!=st)
S[v[i]][1]=st,S[v[i]][0]=s[v[i]]+1; else
S[v[i]][0]++;
Ans[z]=max(Ans[z],(ll)S[v[i]][0]*val[v[i]]);
}
return;
}
int main()
{
n=Read();m=Read();rt=sqrt(n);
for (int i=1;i<=n;i++) v[i]=Read(),Aha[i]=(i-1)/rt;
Pretreat();
for (int i=1;i<=m;i++)
qu[i][0]=Read(),qu[i][1]=Read(),sg[i]=i;
sort(sg+1,sg+m+1,cmp);st=0;
for (int i=1;i<=m;)
{
memset(s,0,sizeof(s));ma=0;
int k=Aha[qu[sg[i]][0]],le=(k+1)*rt+1,ri=le-1;
for (i;i<=m&&Aha[qu[sg[i]][0]]==k;i++)
{
while (ri<qu[sg[i]][1]) Add(v[++ri]);
Solve(qu[sg[i]][0],min(qu[sg[i]][1],le-1),sg[i]);
}
}
for (int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
return 0;
}
BZOJ4242：BFS一遍搜出每块地面最近的建筑物和距离，然后相邻不同的地面可以使对应的建筑物连一条边。然后跑MST。然后查询倍增搞搞。感觉性质显然。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 2050
#define M 200050
#define P 20
#define fr first
#define sc second
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
queue <pair <int,int> > li;
int mi[N][N][2],fa[M][P],h[M],rf[M],ma[M][P],c[M*2][3],fi[M];
int ss=1,sx,sy,st,n,m,sg[2*M*P],ln[2*M*P][3];
char d[N];bool b[N][N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
void BFS()
{
while (!li.empty())
{
pair <int,int> k=li.front();li.pop();
for (int i=0;i<4;i++)
{
int q=k.fr+dir[i][0],w=k.sc+dir[i][1];
if (b[q][w]||!q||!w||q==sx+1||w==sy+1||mi[q][w][1])
continue;
mi[q][w][1]=mi[k.fr][k.sc][1];
mi[q][w][0]=mi[k.fr][k.sc][0]+1;
li.push(make_pair(q,w));
}
}
return;
}
inline bool cmp(int x,int y)
{return ln[x][2]<ln[y][2];}
int Find(int x)
{return rf[x]==x?x:(rf[x]=Find(rf[x]));}
void DFS(int x)
{
h[x]=h[fa[x][0]]+1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
fa[c[i][0]][0]=x,ma[c[i][0]][0]=c[i][2],DFS(c[i][0]);
return;
}
void Pretreat()
{
for (int i=1;i<sx;i++)
for (int j=1;j<=sy;j++)
if (!b[i][j]&&!b[i+1][j]&&mi[i][j][1]!=mi[i+1][j][1])
ln[++st][0]=mi[i][j][1],ln[st][1]=mi[i+1][j][1],
ln[st][2]=mi[i][j][0]+mi[i+1][j][0],sg[st]=st;
for (int i=1;i<=sx;i++)
for (int j=1;j<sy;j++)
if (!b[i][j]&&!b[i][j+1]&&mi[i][j][1]!=mi[i][j+1][1])
ln[++st][0]=mi[i][j][1],ln[st][1]=mi[i][j+1][1],
ln[st][2]=mi[i][j][0]+mi[i][j+1][0],sg[st]=st;
sort(sg+1,sg+st+1,cmp);
for (int i=1;i<=n;i++) rf[i]=i;
for (int i=1;i<=st;i++)
{
int k=Find(ln[sg[i]][0]),l=Find(ln[sg[i]][1]);
if (k==l) continue;rf[k]=l;
Line(ln[sg[i]][0],ln[sg[i]][1],ln[sg[i]][2]);
}
for (int i=1;i<=n;i++)
if (rf[i]==i) DFS(i);
for (int j=1;j<P;j++)
for (int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1],
ma[i][j]=max(ma[i][j-1],ma[fa[i][j-1]][j-1]);
}
int GetAns(int x,int y)
{
int Ma=0;
if (h[x]<h[y]) swap(x,y);
for (int i=P-1;i>=0&&h[x]!=h[y];i--)
if (h[fa[x][i]]>=h[y])
Ma=max(Ma,ma[x][i]),x=fa[x][i];
if (x!=y)
{
for (int i=P-1;i>=0;i--)
if (fa[x][i]!=fa[y][i])
Ma=max(Ma,max(ma[x][i],ma[y][i])),
x=fa[x][i],y=fa[y][i];
Ma=max(Ma,max(ma[x][0],ma[y][0]));
}
return Ma;
}
int main()
{
sx=Read();sy=Read();n=Read();m=Read();
for (int i=1;i<=sx;i++)
{
scanf("%s",d+1);
for (int j=1;j<=sy;j++)
if (d[j]=='#') b[i][j]=true;
}
for (int i=1;i<=n;i++)
{
int k=Read(),l=Read();
li.push(make_pair(k,l));
mi[k][l][1]=i;
}
BFS();Pretreat();
while (m--)
{
int k=Read(),l=Read();
printf("%d\n",Find(k)==Find(l)?GetAns(k,l):-1);
}
return 0;
}
BZOJ4243：感觉像是并查集乱搞搞？
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define M 200050
#define ll long long
ll ans;int fi[N],c[M*2][2],fa[M],s[M],n,m,ss,st;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int y,int x)
{c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;}
int Find(int x)
{return fa[x]==x?x:(fa[x]=Find(fa[x]));}
void DFS(int x,int y)
{
if (fa[x])
{
int k=Find(x);
if (k!=y) fa[k]=y,s[y]+=s[k];
} else
{
fa[x]=y;s[y]++;
for (int i=fi[x];i;i=c[i][1]) DFS(c[i][0],y);
}
return;
}
int main()
{
n=Read();m=Read();st=n;
for (int i=1;i<=m;i++) Line(Read(),Read());
for (int i=1;i<=n;i++)
if (!fa[i]&&c[fi[i]][1])
{
int k=++st;fa[k]=k;
for (int j=fi[i];j;j=c[j][1]) DFS(c[j][0],k);
}
for (int i=1;i<=n;i++)
for (int j=fi[i];j;j=c[j][1])
if (fa[i]&&fa[c[j][0]]&&Find(i)==Find(c[j][0]))
m--;
for (int i=n+1;i<=st;i++)
if (fa[i]==i) ans+=(ll)s[i]*(s[i]-1);
cout <<ans+m<<endl;
return 0;
}
BZOJ4244：想了很久不会= =。完全背包。。真尼玛有道理。果然DP太弱想不到。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 3050
#define ll long long
ll mi[N][N];int u[N],v[N],d[N],e[N],n,m;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
u[i]=Read(),v[i]=Read(),d[i]=Read(),e[i]=Read();
memset(mi,0x3f,sizeof(mi));mi[0][0]=0;
for (int i=1;i<=n;i++)
{
for (int j=0;j<=n;j++)
mi[i-1][j]+=j*m*2;
for (int j=1;j<=n;j++)
mi[i][j]=min(mi[i][j],mi[i-1][j-1]+d[i]+v[i]);
for (int j=0;j<n;j++)
mi[i][j]=min(mi[i][j],mi[i-1][j+1]+u[i]+e[i]);
for (int j=1;j<=n;j++)
mi[i][j]=min(mi[i][j],mi[i-1][j]+d[i]+e[i]);
for (int j=0;j<=n;j++)
mi[i][j]=min(mi[i][j],mi[i-1][j]+v[i]+u[i]);
for (int j=1;j<=n;j++)
mi[i][j]=min(mi[i][j],mi[i][j-1]+d[i]+v[i]);
for (int j=n-1;j>=0;j--)
mi[i][j]=min(mi[i][j],mi[i][j+1]+u[i]+e[i]);
}
cout <<mi[n][0]+m*(n+1)<<endl;
return 0;
}
评论 (0)
