POI19填坑计划
等了好久终于可以开始填POI这种神坑了。。感觉如果能静下心来想的话其实有些题推起来也不算太过艰难。但我的智商是个大玄学。。打到一半才上线。。
[UPD 11.30] 因为感冒还有一些奇怪的事情再次推迟2天= =
现在完成了:
16
[Letters]:NOIP某题即视感。就是求个逆序对数。
[Distance]:大暴力?对于每个数处理出它所有因数打上标记,然后再每个数枚举因数求答案就好了
[Rendezvous]:一个环套树森林,随便乱搞搞就好了
[Well]:想了很久不会。。后来发现是有个玄学姿势没有get:二分答案的时候要从左往右扫一遍然后从右往左扫一遍使相邻的两个不超过x。其余部分就是比较愉快了,很容易发现以每个点为0点左右边界一定是单调的。所以是O(n log n)
[Vouchers]:n log n大暴力
[Tour de Byteotia]:把所有大于k的点的连通分量缩掉然后用剩下的总边数减去生成森林的边数就是答案。
[A Horrible Poem]:直接哈希就好了= =,一直在想些奇怪的东西= =,真是naive。我数了下因数个数naive地以为是n log n级别的。。然后T了。据说有两种特技可以加,一个是所有字母出现次数gcd一下,一个是这里。感觉第二种比较优美。改完之后果然跑的飞起。
[Fibonacci Representation]:首先很明显一个数只会出现一次。因为两个相同的这个数是可以分解成另外两个不同的Fibonacci数的。然后还有个性质就是肯定会包含值跟它相邻的两个数之一。所以直接上爆搜大力出奇迹?还有那个输入小于1e17是个坑= =应该是小于1e18
[Warehouse Store]:很明显是贪心从小到大取,每次取一个非0量。随便找个什么东西维护一下就是n log n的了。还要注意后面取的点对前面答案的影响。
[Squarks]:构造题。。TAT脑抽不会。。直接枚举第二个和第三个是哪个数就好了的。。n^3 log n真是厉害,事实是可以加很多剪枝所以根本就不会摸到上界。
[Salaries]:只会乱搞= =后来wa了以为不是正解= =别人做法都死麻烦= =后来才发现是正解,但是被我写的奇丑无比= =调好久发现处理上界的时候不能直接是父亲上界减一= =真是日
[Festival]:YY很久。首先差分约束系统显然,建出图来之后强连通分量之间答案独立显然。然后剩下的里面都是没有负环的强连通分量,我猜是里面的Max最短路的长度+1?感觉复杂度是个大玄学。还有判负环应该就是看a[i][i]是不是负数吧。wa了几个点调了好久最后发现我用了一年的我自己YY的Tarjan是错的TAT,不知道为什么一直都没错过。
[Cloakroom]:有人说n^2*k/32能过?真是厉害。。貌似只要改变设的状态就可以nk了?改为设b的最大值就好了。
[Bidding]:hehe,x可能的值只有不到100个。貌似BZOJ上面交这个有bug?
[Prefixuffix]:记得这题被数国队出到过NOIP模拟题里面。真是sxbk。。从中间往两边扫,左起点往左移一位答案的范围是原来答案范围+2以内。
[Minimalist Security]:这题放到后面才动。。主要是一开始被吓到了,看顶标什么的以为是权匹配相关。。于是感觉比较报警。。结果现在看是个SB题。。直接每个连通块设个x代表其中一个点应该减去多少,然后就可以得出整张图的量了,然后就是m个不等式求个交。如果图不可以黑白染色肯定就是解唯一。反正随便搞。。BZOJ上面的题面把背景省了我还以为z可以带小数TAT。
[Leveling Ground]:好神啊不会啊弃疗了留坑吧下次填好了。
所以就算完结了?
接下来一段时间准备把高一naive的时候参加过的培训资料过一遍好了,所以暂时不会开新坑。
BZOJ乱炖
感觉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; }
Codeforces开坑
于是开始被虐了= =不知道能撑多久,有的题目还真是sxbk。尤其是乱搞题智商有限没办法= =
玛德英文题面看起来真尼玛蛋疼啊
计数器应该是手动计数的吧。。
UPD 10.14 一直颓废到现在才差不多半百,接下来效率++吧。
UPD 11.1 感觉做到现在状态越来越萎废,于是先来一波BZOJ找找状态好了。
UPD 11.25 玛德不管了。弃坑了弃坑了= =
464E:毛子脑洞还真是大,一开始乱搞了一个搞法并没有过,膜了一发题解原来是用主席树搞高精度。还要加什么优化感觉就很蛋痛于是先留坑好了= =
464D:一开始还设期望和概率DP,因为i比较大的时候概率基本上没有所以直接设一个范围就好了。结果T地爽爽的。后来膜了一发Tourist的卡常技巧才过。
301D:对数只有n log n个,所以询问和关系都变成点然后排个序用树状数组维护一下扫一遍就好了
463E:之前还一直在想些奇怪的做法但是并弄不出来。原来是DFS一遍顺便每个质数维护一个栈,复杂度50*n log n,因为单点时限10s所以不虚。
319D:暴力能A实在厉害。正解分段搞?不明觉厉,然而sxbk出题人题解都没有贴出来= =
342D:裸状压DP
273E:首先把SG函数值打出来发现段数不多,于是暴力预处理出每一段,然后算出值为0~2的SG值分别有多少个,就可以矩阵快速幂搞了。
257E:裸的模拟题,搞几个set就好了
305E:看错题了,结果一直卡在第二问,后来重新看题才发现好水= =
316E3:线段树维护所需答案,合并用矩阵乘法。常数卡的好紧
263E:花式前缀和乱搞
293B:一种奇怪的爆搜姿势,想了很久状压、爆搜还有其它奇怪的东西都没搞出来。后来还是膜了tourist的code= =
关键的剪枝是没出现过的颜色用组合数算
325E:奇怪的结论题,不会捉= =
241B:奇怪的乱搞题,不过最后还是搞出来了= =
260E:主席树。
338E:Splay裸题。
249E:python写这个常数真是大,连T6次爽爽爽
306B:水
339E:记得以前有人讲课讲过吧。反正乱搞就好了,反正可以作为翻转的端点的一定是什么断点,然后设个常数什么的,如果断点超过一定个数就退出,否则枚举端点然后递归。
286E:颓了很久题面勉强看懂了点,然后颓了很久都不会做。看了代码我才知道一个袋子最多只能装两个的,a set of原来是一对而不是一堆的意思。真是报警。题意懂了就是个比较明显的FFT
332D:题意艹蛋,式子很水,但是一开始低估了long double的范围,以为还要用高精度除法或者要用python写,感觉不管哪一个都很虚啊,没想到ld是存的下600位的数的,不过也应该是没保证精度的吧。
261D:想很久没想出来,后来get了个新DP姿势才A:设一个f数组,f数组中值为k的最小的下标i代表扫到目前这个位置的时候长度为k的最长上升子序列的最右边元素的最小值为i,于是把t*n个元素扫一遍,同时如果当前元素的值减一的f值等于当前元素的f值就暴力往右更新f数组。题目里面的限制保证了t在一定范围内所以枚举t并不会爆,复杂度最多也就是f数组的数值和也就是O(min(maxb^2,n*maxb))的样子。
335D:由于坐标大小被限制,所以有很多个量都被限制在一定范围内所以就可以花式前缀和乱搞了。
235C:首先对于每个xi KMP一下求出最长循环节,预处理出母串的SAM和每个节点的ri集合大小和最短长度,然后放到母串的SAM上面跑,ans加上此节点的ri集合大小,调整位置就是如果当前状态是当前节点的最短长度就调整到pre位置否则不动,然后再加上一个字符。玛德隔了个把月已经不会写SAM了TAT。
311E:最小割= =就是每个富人和狗都建个点,然后分别跟S或T连对应权值边,两者之间连INF,具体连哪边需要根据0/1判断
295D:DP
258D:没想到设a[i][j]为ti>tj的概率,全程在想些奇怪的搞法。人弱智商低没办法
286D:set、heap一起乱搞
273D:小狗好像也讲过,反正花式乱搞。真是写的人想☀狗
283E:好萎,没想出来= =比赛结果是一个n*n的矩阵,每次翻转一个子矩阵中的值,所以是扫描线+线段树维护求出每个人赢了多少场,最后答案是C(n,3)减去每个人赢得场数k的C(k,2)(因为一个非环的结果有且仅有一个人赢了两盘)
305D:乱搞
261E:满足要求的数个数有限,所以求出来之后DP出每个数的最小次数。复杂度虽然是很虚但是还是能过
253E:二分答案
243C:一开始没睡醒的时候想了很久平面图还有扫描线相关做法。看到数据范围之后就是离散化之后暴力矩阵染色+BFS了。
316G3:一开始没想到把所有串建在一个SAM上面而是准备让两个指针在两个SAM上面一起跑,但是母串的SAM每个节点还要维护可行集合,感觉虽然貌似可以卡过的样子但是写到一半100行还是弃疗了,果然还是有更优美的做法= =
256D:N^4DP,还要打表真是差评
303D:狗哔结论题= =首先n+1必须是质数,然后从大到小枚举b,b必须不是n+1的倍数,如果不存在任何n的因子k使得b^k%(n+1)==1||b^(n/k)%(n+1)==1就输出b。你问我怎么证我怎么知道
338D:范围艹蛋
266E:线段树维护每段区间六种值。
332E:乱搞,但是要注意细节,在160+的测试点wa了也真是爽快
584E:考场上一直naive地以为这个就是把环上面最长的边去掉,但其实答案就是每个点到目标点的距离和。构造方法是:枚举目标位置从1~n的点,然后让其与一直往前面扫,如果遇到一个目标位置在其后面的点就与其交换,这样的最大交换次数是n^2的。由于其前面总会有目标位置在其后面的点所以其总能够移动到目标点。
333C:恶心乱搞,很久没有搞出来。
240F:裸线段树
235D:一棵树上的情况就是分别算对于每个点i,删第i个点的时候j点对它的贡献就是1/(dis(i,j)+1),环套树就是如果有的点有两个距离就1/len1+1/len2-2/(len1+len2+R-2),len1、len2、R分别为路径1、路径2、环的点数。但是犯逗了很多次
301C:英语弱看不懂题(话说后来问了英语大神还是看不懂TAT),看代码更看不懂,毛子语文题真是厉害
301E:182这场这两题怎么这么神啊,有的人n^5时间还能在100ms内实在厉害,而且DP也好神。按数值从小到大DP,然后方案总数只跟上一个数值的个数有关,所以预处理出组合数,DP设的是算到第i个数、这一个数值有j个、一共用了k个并且有s种方案的时候的方法数。当然以上都是在一个前提下:把所有从上往下的路径除了最下面那个数其它的数全部删掉。
309B:预处理出每个单词最多能到后面哪个单词都能组成一行,然后就O(n)乱搞了。有点卡常
309D:推了个式子,但是各种被卡常,看了标程维护方程解的姿势还真是厉害,没有实数运算所以能卡过
277D:英语果弱看漏了条件,更神奇的是样例也看错了于是想了很久想不出来,后来看到条件推下式子之后就是很显然的贪心+背包。不过好像在一些奇怪的地方卡了精度
341E:完全没有头绪。。。感觉这种弃疗状态下做不了智商题= =正解是任意三个数都可以通过倍增+辗转相消变成两个
323B:奇数情况很快想出来了,就是每个点i连向i+1然后i+2到i-1交替连向i、连向i+k,但是被偶数情况卡住了TATQAQ2333,原来只要多出来那个点连向1和2就可以了。。。
325C:有印象小狗讲过,翻课件还翻到了翻译感觉真是良心,只是记得讲课的时候好像全程在颓。。不过纯码农题没听思路也没什么关系。首先求无法停止的分裂方式就是先找出所有无后继的分裂方式,对于每个怪物如果可停止的方式这个怪物也是可停止的,如此BFS求出。则得出所有无法停止的怪物,删掉这些点及相关方案。剩下点求SCC,用所有被缩的点更新其所有前驱,被标记点都是最大值无穷大的。剩下点的最大值可以拓扑排序求出最大值。所有点的最小值就是SPFA了。做这题简直像是NOIP图论四合一,不过没调多久还是很开心的。(en不对为什么CF上面的代码都写得这么短)
266D:Floyd之后枚举每条边,每个点在这条边上面的最短距离可以看作一条两段共端点的斜率为1、-1的射线,排序之后扫一遍就可以统计答案了
311C:1操作就是模k之后SPFA,另外两个操作用个set就好了。
316D3:推公式推的人萌萌哒,发现了同一置换中最多只能有两个1,通过优化时空都是n^2的,然后就不会了。。。题解里面的自行证明简直厉害。看老司机的博客这题的题解发现了“不求甚解”这句话,感觉真是很有道理。
323C:离线有个经典做法扫描线+线段树,在线直接主席树好了。第二种方法好像代码比第一种短好多。分块做法因为复杂度跟n无关所以常数要小些。
343E:en就是ZJOI那个题,最小割互不相交,于是求n次最小割然后建出树贪心就好了。有个地方的标记打错了调了好久TAT
267C:一开始被题意卡了好久,思路也是好神的高斯消元,并没有想到。。对于每个顶点设从1到它的最短距离为未知数,则可以通过每个点入流量和出流量相等列方程。最后得出来的答案再缩放一下就好了。精度还有细节都有点卡。
314E:我说怎么神题这么多,TM又看错题了TATQAQ2333。以为输入里面大小写字母都有的。首先所有小写字母都是一样的显然。然后设a[i][j]为前i个字符处理完了之后又j的多出来的左括号。常数艹蛋
240E:看了好久不会= =后来才发现是朱刘裸题,不过好像有一些很明显是错误的算法都过了而且n和m都是10w的朱刘算法O(VN)的都过的毫无压力,数据是有多弱。话说朱刘这种东西还要输出方案写起来还真是异常爽快。我真是不会写了。。。
303E:真是不明白为什么什么不科学的复杂度都有,正解n^5还真是爽快。。
285E:好狗哔神,并没想出来= =容斥+DP,直接DP不知道可不可做,但是可做也好麻烦的样子= =首先状态是前i个数造了j个GN,其它的数都无视的方案数,然后就可以求出至少有j个GN的方案数,然后容斥一下就好了。。
331C3:人弱没想到这种DP。。。贪心选最大数位减去显然。设a[i][j][k]为后面i位为999..k,前面位的最大值为i的时候把后面i位减完的总次数。
293E:一眼点分治,对于每次计算答案将所有节点按权值和排序,然后在树状数组里面维护到重心长度。这煞笔东西调了好久都是肥爷的锅。最后发现有个地方爆long long了。。。我个煞笔。。。
288E:花式数位DP,细节好多。。
241F:什么狗哔题面啊。。。
274C:这题的题解的结论都是错的,是锐角三角形和能够任意能够构成至少两个直角三角形的四边形。
319E:en线段相交但不重合之后是可以并成一条线段的,至于找相交线段明显转换成二维平面问题之后K-D Tree搞一搞就可以了。至于线段树解法好像是离散化之后线段树每个节点维护个vector,然后每次插入的时候就合并,询问就是并查集。感觉很厉害,并没有想到。
235E:DP,DP[i,j,k,p]代表a<=i&&b<=j&&c<=k且用到第1~p个质数的时候的答案。则其等于sum DP[i/p^a1,j/p^a2,k/p^a3,p-1]。
306C:组合数学,水
241E:差分约束系统,但是不知道哪里看错题了一直在wa。。
268D:DP。。开始设状态的时候完全没考虑怎么写起来方便。。
254D:先判掉rats>=327的点,然后所有ratsBFS一遍找出所有可以到达rats个数至少为总数一半的点,然后剩下的ratsBFS一遍找出可以覆盖剩下rats的点即为答案。简直跑的飞起。
269D:按高度排序之后用set维护水平区间被覆盖的情况。感觉最近写什么都跑的飞起?
264D:一开始想维护左端点右端点发现不对劲,转换成二维平面之后维护斜线上的左右端点发现也不对,还想了些奇怪的东西,然后就不会了。。原来只要判掉所有后缀分别为AB-BA的情况就好了。。感觉好厉害。。
总感觉后面的题会很愉悦啊。。。
280C:先玩个C冷静一下,虽然是看D题解的时候看这题的所以被剧透了一脸,但是感觉还是比较显然,因为对于每个点只要它和它的父亲都在的时候先选择它而不是它的祖先的概率都是1/(h[1][i]+1)。
280D:岛娘场简直SXBK。。。线段树维护费用流?。。。感觉用费用流建模证明贪心有点不明所以啊。感觉我有证明?:对于选取k块和k+1块的两种最优状态,如果两者不是能由一次翻转得到的则其中必定能选取一段被翻转的连续部分使得只翻转这一部分能增加块数为1,因为翻转一部分的状态这部分连通块数改变的绝对值最大为1。其余部分不跟这个相连而且选取了能使答案更优肯定在只有k块的时候就选取肯定能使答案更优,由此k块的状态不是最优状态,由此相邻块数的两种最优状态肯定是由一次翻转得到的。en比想象中好写。。
590E:这题我真是做的好感动。一开始并不知道怎么做,而且没有题解,于是膜拜标程发现是用AC自动机上面标记每个字符串的结束位置,然后求fail还有最近的带标记的fail祖先,于是就可以n个字符串在上面跑一遍通过带标记fail求出两两之间的关系。至于求最长反链是很水只要一个dinic,但是还要求方案就sxbk了吧。。。我看了半天真心没看懂他求方案的操作的原理。。。留坑好了。然后准备不求甚解先写了再说的时候TM总是TLE在第66个test。最后爆了10+次终于知道了Dinic跑二分稠密图爆炸了。。(但是为什么我记得这是msqrt(n)的比其它姿势都要快啊)。。总之这题终于A了。。。。。。(UPD:好像有人贴出证明来了?戳这里)
329D:en思路当然就肯定是要重复利用。。。
335F:第一眼SB贪心,看了样例感觉神神的,看完standing不敢做了。。感觉思路确实脑洞,总感觉不会证明。。。
294D:en有结论:边上所有点都走过的时候刚好完成任务。感觉怎么搞都可以?暴力建图然后直接搞?有点恶心= =
241D:狗哔结论题,只要管小于等于二十几的就能过?
249D:缩放坐标变成直角?并没有想到= =而且数学弱不会推公式= =
274E:像是294D去掉了结论?将所有点黑白染色之后发现所有点只会走同色的格子,所以说不会出现两次路径相交的情况,所以长度不用去重。然后就是把所有的边界上面的点还有黑格子上面的点排序之后维护一些东西连下边就好了?细节比294D恶心多了。。。我竟然A了。。感觉整个人真是愉快。。
317E:想到一个做法:先一直往影子靠近,然后如果到了外面就通过四个顶点调整。但是感觉好虚总感觉除了不连通之外是不是还存在什么-1情况?关键是这做法感觉一点都不优美= =然后膜拜正解发现就是这样我真是naive。。。感觉乱搞模拟题什么的真是够了。。
后面的题目怎么都这么丧病啊,老湿我可以弃疗了么TAT
325D:en感觉做的时候智商并不在线= =复制一遍原图然后判断两点能否在八连通图里面互相到达= =实在不知道把八连通格子的并查集root标记然后看两个点有没有重复标记是怎么错的。。最后发现还是自己犯逗了= =
360D:感觉要去补数学了= =首先推导一下就可以发现第i项的集合是一个等比数列,比是所有b值还有p-1的gcd,循环节的长度一定是p-1的因数,所以就可以枚举最小的循环节长度leni,则leni、2leni……p-1都在这个集合里面了。一开始求这东西我还想用BSGS。。然后很明显就是个容斥一开始我还想枚举子集求答案我真是naive,这种容斥明显是n^2。
264E:这题不会我是不是要废。。维护两棵线段树分别以高度和位置为下标,然后两种操作就是暴力乱搞。第一个测试点TLE的人不知道什么鬼。。明明就是样例数据本机上面怎么跑怎么过,爆了几发OJ发现h数组值在我还什么事情都没干的情况下就改变值了?反正在上面坑了几组数据没问题之后就弃坑了= =UPD:后来借了个号子在tsinsen上面测了可能是常数原因吧,除了T了三个点之外其他的都是过的。。管他的。。
329E:神题。。不会。。一开始猜了个结论是错的,后来弃疗看题解也都是些smg。。
346E:为什么随便挑了个又是结论题。看了还是感觉不明觉厉。。代码长度应该是唯一良心的地方吧。。
251D:犯逗了。。一开始看到10w数据范围就没往高斯消元方向想。
248E:关键在于数据范围很小。。于是可以记录每个点记录下有i个满罐子的概率。然后暴力枚举取出的满罐子个数转移。
351D:首先我们要求的问题是:询问区间内不同数个数。还有判断区间内存不存在某一个数使得所有这个数的位置是个等差数列。前者就是DQUERY,主席树搞搞。后者我们扫一遍处理出n个矩形之后扫描线+线段树搞搞。基本上一遍写对还是挺爽的。
HEOI2015乱做
我已经不好意思把这个东西叫做题解了
这东西我记得之前CTSC的时候被XL叫去推HEOI,结果当时就smg都没搞出来,只弄出来Day1T3。感觉吧现在看起来还是很艹蛋
Day1T1兔子和樱花
不会做,还是看这里磨出来的代码。
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 2000050 int sg[N][2],c[N],n,m,st,s[N],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 s[x]<s[y];} void DFS(int x) { for (int i=sg[x][0];i<=sg[x][1];i++) DFS(c[i]); sort(c+sg[x][0],c+sg[x][1]+1,cmp); s[x]+=sg[x][1]-sg[x][0]+1; for (int i=sg[x][0];i<=sg[x][1];i++) if (s[x]+s[c[i]]-1<=m) s[x]+=s[c[i]]-1,ans++;else break; } int main() { n=Read();m=Read(); for (int i=1;i<=n;i++) s[i]=Read(); for (int i=1;i<=n;i++) { int k=Read();sg[i][0]=st+1; while (k--) c[++st]=Read()+1; sg[i][1]=st; } DFS(1); cout <<ans<<endl; return 0; }
Day1T3
当时的我都能做出来的煞笔题
#include <iostream> #include <string.h> #include <cmath> #include <cstdio> #include <algorithm> #define ll long long using namespace std; int n,m,t,v; ll mi; inline int ans(ll x) { int i=0; while (x%10==0) x/=10; if (x%10==5) i=-1; while (x) x/=10,i+=2; return i; } inline void Try(ll x) { if (x<n||x>m) return; int i=ans(x); if (v<=i||(v==i&&x>mi)) return; v=i;mi=x; return; } void aa(ll x,ll y) { ll i; if (x>m) return; if (x%y==0) aa(x,y*10);else { if ((x%y)/(y/10)<5) { i=x-x%y;i+=y/10*5;Try(i); }else { i=x-x%y;i+=y/10*5+y;Try(i); } i=x;i-=x%y;i+=y;Try(i); aa(i,y*10); } return; } int main() { int i,j,k,l,q,w,e; scanf("%d",&t); while (t--) { scanf("%d%d",&n,&m); mi=n;v=ans(n); aa(n,10); printf("%lld\n",mi); } return 0; }
Day2T2
一眼Matrix-Tree(然而当时并不知道这种东西),当然也可以用插头DP(现在都不会这种狗哔东西)
需要注意的是模数是合数,妈蛋在这里被卡了。后来突然发现算行列式并不需要真的去除而是两行相消所以是辗转相除就行了。
我真是个煞笔。
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define N 105 #define M 1000000000 #define ll long long ll t[N][N],ans=1;bool b[N][N];int sg[N][N],st,n,m;char c[N]; inline void Check(int x,int y,int z,int o) { if (!z||!o||b[z][o]) return; t[sg[x][y]][sg[z][o]]=t[sg[z][o]][sg[x][y]]=M-1; t[sg[x][y]][sg[x][y]]++;t[sg[z][o]][sg[z][o]]++; } inline ll abs(ll x) {return x<0?-x:x;} void Gauss() { for (int i=1;i<st;i++) { ll k=i,l; while (k<st&&!t[k][i]) k++; if (k==st) {ans=0;return;} if (k!=i) swap(t[k],t[i]),ans=-ans; for (int j=i+1;j<st;j++) if (t[j][i]) { k=t[i][i];l=t[j][i]; while (l) { ll e=k/l; for (int q=1;q<st;q++) t[i][q]=(t[i][q]-t[j][q]*e%M+M)%M; k%=l;swap(k,l);swap(t[i],t[j]);ans=-ans; } } } ans+=M; for (int i=1;i<st;i++) ans=ans*t[i][i]%M; return; } int main() { cin >>n>>m; for (int i=1;i<=n;i++) { scanf("%s",c); for (int j=0;j<m;j++) if (c[j]=='*') b[i][j+1]=1;else sg[i][j+1]=++st; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (!b[i][j]) Check(i,j,i-1,j),Check(i,j,i,j-1); Gauss(); cout <<ans<<endl; return 0; }
剩下题目都在后面接着的那个BZOJ乱做里面放粗来了
BZOJ 2595 游览计划
斯坦纳树早在6月份吧小狗就讲过了然而当时并没有填这个坑
感觉写起来还是很轻松愉快的不过虽然这么说还是被细节卡了好久
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 13 #define M 1024 #define INF 0x3f7f7f7f int v[N][N],st,S,la[N][N][M][4],li[M*M][3]; int s[N][N][M],a[N][2],n,m;bool b[N][N][M]; const int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; 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 Trans(int x,int y,int z,int o,int p,int *ri) { if (!o||!p||o>n||p>m||v[o][p]+s[x][y][z]>=s[o][p][z]) return; s[o][p][z]=v[o][p]+s[x][y][z]; la[o][p][z][0]=x;la[o][p][z][1]=y;la[o][p][z][2]=z; la[o][p][z][3]=0; if (!b[o][p][z]) (*ri)++,b[li[*ri][0]=o][li[*ri][1]=p][li[*ri][2]=z]=1; } void SPFA(int t) { int le=1,ri=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (s[i][j][t]!=INF) li[++ri][0]=i,li[ri][1]=j,li[ri][2]=t, b[i][j][t]=1; for (;le<=ri;le++) { int q=li[le][0],w=li[le][1],e=li[le][2]; for (int i=0;i<4;i++) Trans(q,w,e,dir[i][0]+q,dir[i][1]+w,&ri); b[q][w][e]=0; } return; } void Solve() { for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<S;k++) s[i][j][k]=INF; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) s[i][j][0]=v[i][j]; for (int i=1;i<=st;i++) s[a[i][0]][a[i][1]][1 << i - 1]=0; for (int t=0;t<S;t++) { for (int i=(t-1)&t;i;i=(i-1)&t) for (int j=1;j<=n;j++) for (int k=1;k<=m;k++) if (s[j][k][t]>s[j][k][i]+s[j][k][t-i]-v[j][k]) { s[j][k][t]=s[j][k][i]+s[j][k][t-i]-v[j][k]; la[j][k][t][0]=j;la[j][k][t][1]=k; la[j][k][t][2]=i;la[j][k][t][3]=t-i; } SPFA(t); } } void DFS(int x,int y,int z) { if (v[x][y]) v[x][y]=-1; if (!la[x][y][z][0]) return; if (la[x][y][z][3]) DFS(x,y,la[x][y][z][2]),DFS(x,y,la[x][y][z][3]);else DFS(la[x][y][z][0],la[x][y][z][1],la[x][y][z][2]); } void Print() { DFS(a[1][0],a[1][1],S-1); printf("%d\n",s[a[1][0]][a[1][1]][S-1]); for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) if (!v[i][j]) putchar('x');else if (v[i][j]==-1) putchar('o');else putchar('_'); puts(""); } } int main() { n=Read();m=Read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { v[i][j]=Read(); if (!v[i][j]) a[++st][0]=i,a[st][1]=j; } S=1 << st; Solve(); Print(); return 0; }