跟着金主席的步伐，一步两步，一步两步，一步两步似poi~
嘿嘿嘿， 看着 金主席做$poi$，然后看了看我以前做过的$poi$，想想把能做的做完好辣
现在做了 几道： 19/20
$4.6$ $qiancl:$一半辣一半辣
$4.7$ $qiancl:$拿了一血好开心啊
$2938: [Poi2000]病毒$
询问是否无限就应该先想到有没有合法的环，先构出$AC$自动机，再把$fail$建好，然后就$dfs$找一不经过病毒环，有就有解
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 30030
int i,j,k,m,l,r,n,x,y,cnt,f;char s[N];bool vis[N],mrk[N];
struct node{node*ch[2],*f;int ed;}C[N],*c=C,Null,*null=&Null,*q[N];
inline void insert(char*s){node*o=C;for(o->f=C;*s;o=o->ch[*s-48],o->f=C,++s)if(o->ch[*s-48]==NULL)o->ch[*s-48]=++c;o->ed=1;}
inline void build(){
node*o=C;
for(l=1,i=0;i<=1;++i)if(o->ch[i]!=NULL)q[++r]=o->ch[i];
while(l<=r){
node*x=q[l++];
for(i=0;i<2;++i)if(x->ch[i]==NULL)x->ch[i]=x->f->ch[i];
else x->ch[i]->f=x->f->ch[i],x->ch[i]->ed|=x->f->ch[i]->ed,q[++r]=x->ch[i];
}
}
void dfs(node*o){
if(f)return;if(o!=C)vis[o-C]=1;
for(int i=0;i<2;++i){
node*x=o->ch[i];if(vis[x-C]){f=1;return;}
if(mrk[x-C]||x->ed)continue;
mrk[x-C]=1,dfs(x);
}
vis[o-C]=0;
}
int main(){
for(scanf("%d",&n),i=1;i<=n;++i)scanf("%s",s),insert(s);
(build(),dfs(C),f)?puts("TAK"):puts("NIE");
}
$KDtree$模板题，不能$1A$就会显得有些奇怪，别问我为什么不释放空间，你应该出门右转找金主席，比我写的短到不知道哪里去了
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
if(ch=='-')f=-1,ch=nc();for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define N 100010
const int oo=1<<29;
int i,j,k,m,n,f,x,y,t,cnt,z;
struct poi{int p[5];}P,a[N],ans[N];
priority_queue<poi>q;
inline void Mx(int&a,int b){if(b>a)a=b;}
inline void Mn(int&a,int b){if(b<a)a=b;}
inline double dist(const poi&a,const poi&b){double ret=0;for(int i=0;i<k;++i)ret+=(a.p[i]-b.p[i])*(a.p[i]-b.p[i]);return ret;}
struct kd{
kd*ch[2];int mx[5],mn[5];poi p;
inline void up(){for(int i=0,j;i<k;++i)for(mx[i]=mn[i]=p.p[i],j=0;j<2;++j)if(ch[j]!=NULL)Mx(mx[i],ch[j]->mx[i]),Mn(mn[i],ch[j]->mn[i]);}
inline double dis(const poi&x){
double ret=0.;
for(int i=0;i<k;++i)if(x.p[i]<mn[i])ret+=(x.p[i]-mn[i])*(x.p[i]-mn[i]);
else if(x.p[i]>mx[i])ret+=(x.p[i]-mx[i])*(x.p[i]-mx[i]);
return ret;
}
}C[N<<4],*c=C;
inline bool cmp(const poi&a,const poi&b){return a.p[f]<b.p[f];}
inline bool operator<(const poi&a,const poi&b){return dist(a,P)<dist(b,P);}
void build(kd**o,int l,int r,int flg){
if(l>r)return;*o=c++;
if(l==r){(*o)->p=a[l];for(int i=0;i<k;++i)(*o)->mx[i]=(*o)->mn[i]=a[l].p[i];return;}
int m=l+r>>1;f=flg,nth_element(a+l,a+m,a+r+1,cmp),(*o)->p=a[m];
build(&(*o)->ch[0],l,m-1,(flg+1)%k),build(&(*o)->ch[1],m+1,r,(flg+1)%k),(*o)->up();
}
void ask(kd*o){
double ds=dist(o->p,P),Ds[2]={oo,oo};
if(q.size()<m)q.push(o->p);else if(dist(q.top(),P)>ds)q.pop(),q.push(o->p);
for(int i=0;i<2;++i)if(o->ch[i]!=NULL)Ds[i]=o->ch[i]->dis(P);
bool fl=Ds[0]>Ds[1];
if((q.size()<m||Ds[fl]<dist(q.top(),P))&&o->ch[fl]!=NULL)ask(o->ch[fl]);fl^=1;
if((q.size()<m||Ds[fl]<dist(q.top(),P))&&o->ch[fl]!=NULL)ask(o->ch[fl]);
}
int main(){
while(~scanf("%d%d",&n,&k)){
for(i=1;i<=n;++i)for(j=0;j<k;++j)a[i].p[j]=read();
kd*root;for(build(&root,1,n,0),t=read(),i=1;i<=t;++i){
for(j=0;j<k;++j)P.p[j]=read();
for(m=read();!q.empty();)q.pop();
for(ask(root),cnt=0;!q.empty();ans[++cnt]=q.top(),q.pop());
printf("the closest %d points are:\n",m);
for(j=cnt;j>=1;--j)for(z=0;z<k;++z)printf("%d%c",ans[j].p[z],z==k-1?'\n':' ');
}
}
}
出了点小差错...这题不是$poi$的题_(:зゝ∠)_，是我搜$poi$搜到的..不用在意这些细节辣
谁都不想移到$m$-$1$，也就是移到$m-1$是必败的，把连续有棋子的格子当做石子，连续的空格数-$1$就是空位的个数，转化成阶梯博弈，然后就可以上$nim$了！奇数位异或起来为$c$，如果$c$=$0$就表示先手必败（以$m$-$1$做终点）
获胜的方案数，对于奇数位异或上$c$小于这一位，就是可行的;
偶数位$(c$ $xor$ $nim[i-1])>nim[i-1]$ $and$ $(nim[i-1]$ $xor$ $c)<=nim[i]+nim[i-1]$那就是可行的
我不知道发生了什么，运行速度似乎出了一点偏差
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000010
int i,j,k,m,n,lc[N],ans,l,nim[N],c;
int main(){
for(m=read(),n=read(),i=1;i<=n;++i)lc[i]=read();
if(lc[n]==m-1){for(i=n;i>1&&lc[i]-lc[i-1]==1;--i)++ans;return printf("%d\n",ans+1),0;}
for(lc[n+1]=m-1,i=n;i>=1;--i)if(lc[i+1]-lc[i]==1)++nim[l];
else if(lc[i+1]-lc[i]==2)nim[++l]=1;else if((lc[i+1]-lc[i]-1)&1)nim[l+=3]=1;else nim[l+=2]=1;
for(i=1;i<=l;i+=2)c^=nim[i];
if(!c)return puts("0"),0;
else{
for(i=1;i<=l;i+=2)if((c^nim[i])<nim[i])++ans;
for(i=2;i<=l;i+=2)if((c^nim[i-1])>nim[i-1]&&(nim[i-1]^c)<=nim[i]+nim[i-1])++ans;
}
printf("%d\n",ans);
}
$2216: [Poi2011]Lightning Conductor$
$f_{i}=max(a_{j}+\sqrt{\left | i-j \right |})-a_{i}$，然后因为单调吓几拔搞一下就行了
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 500050
int i,j,k,m,n,x,y,t,a[N],l,r;double f[N],g[N];
struct node{int id,l,r;}q[N];
inline double dis(int x,int y){return a[y]+sqrt(abs(x-y));}
inline int ef(int l,int r,int x,int y){for(int m;l<r;m=l+r>>1,(dis(m,x)<dis(m,y)?l=m+1:r=m));return l;}
inline void Dp(double*o){
for(l=1,r=0,i=1;i<=n;++i){
if(l<=r&&++q[l].l>q[l].r)++l;
if(l>r||dis(n,i)>dis(n,q[r].id)){
while(l<=r&&dis(q[r].l,i)>dis(q[r].l,q[r].id))--r;
if(l>r)q[++r]=(node){i,i,n};
else q[r].r=(t=ef(q[r].l,q[r].r,i,q[r].id))-1,q[++r]=(node){i,t,n};
}
*(o+i)=dis(i,q[l].id);
}
}
int main(){
for(n=read(),i=1;i<=n;++i)a[i]=read();
Dp(f),reverse(a+1,a+n+1),Dp(g),reverse(a+1,a+n+1),reverse(g+1,g+n+1);
for(i=1;i<=n;++i)printf("%d\n",(int)ceil(max(f[i],g[i])-a[i]));
}
二分是很明显的，但是怎么判二分后构出的图存不存在欧拉回路呢。。首先随便定向无向边，如果出入度的差是奇数，那显然不存在，建一个源$s$，对于出大于入的点，$s$向这个点连容量为出入度差除以二的边，建出汇$t$就反一反，剩下的图里把有向边省去，无向边就按定向的连，看是不是满流就行了，嘛比较显然
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 100010
const int oo=1<<30;
int i,j,k,m,n,x,y,S,T,cnt=1,sum,l=oo,p[N],flow,d[N],r=-oo,last[N],in[N],ot[N],ans;
struct edge{int to,next,s;}e[N];
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct bridge{
int a,b,c,d;
inline void in(){
a=read(),b=read(),c=read(),d=read();
if(c>d)swap(c,d),swap(a,b);l=min(l,c),r=max(r,d);
}
}q[N<<1];
inline void add(int u,int v,int w){
e[++cnt]=(edge){v,last[u],w},last[u]=cnt;
e[++cnt]=(edge){u,last[v],0},last[v]=cnt;
}
inline bool build(){
for(int i=1;i<=T;++i)d[i]=-1;
p[1]=S,d[S]=0;
for(int x,y,l=1,r=1;l<=r;){
x=p[l++];
for(int i=last[x];i;i=e[i].next)if(e[i].s&&d[y=e[i].to]==-1){
d[y]=d[x]+1,p[++r]=y;if(y==T)return 1;
}
}return 0;
}
int find(int now,int flow){
int ret,y,w=0;
if(now==T)return flow;
for(int i=last[now];i&&w<flow;i=e[i].next)
if(e[i].s&&d[y=e[i].to]==d[now]+1&&(ret=find(y,min(flow-w,e[i].s))))e[i].s-=ret,e[i^1].s+=ret,w+=ret;
if(!w)d[now]=-1;return w;
}
inline bool check(int x){
for(memset(last,0,sizeof last),i=1;i<=n;++i)in[i]=ot[i]=0;
for(cnt=1,S=n+1,T=S+1,i=1;i<=m;++i){
if(q[i].c<=x)++ot[q[i].a],++in[q[i].b];
if(q[i].d<=x)add(q[i].b,q[i].a,1);
}
for(i=1;i<=n;++i)if(abs(in[i]-ot[i])&1)return 0;
for(sum=ans=0,i=1;i<=n;++i){
y=in[i]-ot[i],sum+=y>0?y>>1:0;
if(y>0)add(S,i,y>>1);if(y<0)add(i,T,(-y)>>1);
}
while(build())while(1){flow=find(S,oo);if(!flow)break;ans+=flow;}
return sum==ans;
}
int main(){
for(n=read(),m=read(),i=1;i<=m;++i)q[i].in();
for(int mid;l<=r;check(mid=l+r>>1)?r=mid-1:l=mid+1);
if(!check(l))puts("NIE");else printf("%d\n",l);
}
因为 是对称轴。。 复制一份_(:зゝ∠)_找回文串。。然后就没了_(:зゝ∠)_，什么$kmp$，好高深啊。。一时冲动刷了rank
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define N 400400
const int oo=1<<30;int i,j,k,m,n,x,y,f[N],T,o,mx,ans;
struct point{int x,y;}p[N];struct sgl{double p,x;}c[N];
inline point operator-(const point&a,const point&b){return(point){a.x-b.x,a.y-b.y};}
inline bool operator==(const sgl&a,const sgl&b){return(fabs(a.p-b.p)<1e-8)&&(fabs(a.x-b.x)<1e-8);}
inline double poix(const point&a,const point&b){return a.x*b.x+a.y*b.y;}
inline double Xx(const point&a,const point&b){return a.x*b.y-a.y*b.x;}
int main(){
for(T=read();T--;){
for(ans=0,memset(f,0,sizeof f),memset(c,0,sizeof c),n=read(),i=1;i<=n;++i)p[i].x=read(),p[i].y=read();
for(p[0]=p[n],p[n+1]=p[1],c[0].p=c[0].x=oo,i=1;i<=n;++i){
c[(i<<1)-1].p=poix(p[i-1]-p[i],p[i+1]-p[i]);
c[(i<<1)-1].x=Xx(p[i-1]-p[i],p[i+1]-p[i]),c[(i<<1)-1+(n<<1)]=c[(i<<1)-1];
}
for(f[1]=o=mx=i=1,m=(n<<2)-1;i<=m;++i){
for(mx>i?f[i]=min(f[(o<<1)-i],mx-i):f[i]=1;c[i+f[i]]==c[i-f[i]];++f[i]);
if(f[i]+i>mx)mx=f[i]+i,o=i;
}
for(i=n+1;i<=n*3;++i)if(f[i]>=n-(!(n&1)))++ans;
printf("%d\n",ans>>1);
}
}
辣鸡题目毁我青春
一定是建在城市里，一定从低往高造，直接$bfs$就行了，我$vector$一个$pop$写晚害我足足多调了半小时
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
if(ch=='-')f=-1,ch=nc();for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define N 1010
#define pb push_back
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int i,j,k,m,n,x,y,a[N][N],b[N][N],mx,ans;
struct node{int x,y;};vector<node>q1[N],q2[N];
#define max(a,b) ((a)>(b)?(a):(b))
inline void bfs(int x,int y){
for(int i=0;i<4;++i){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||yy<1||xx>n||yy>m||b[xx][yy]!=-1)continue;
b[xx][yy]=max(b[x][y],a[xx][yy]),q2[b[xx][yy]].pb((node){xx,yy});
}
}
int main(){
for(n=read(),m=read(),i=1;i<=n;++i)for(j=1;j<=m;++j)a[i][j]=read(),b[i][j]=-1,a[i][j]>0?(q1[a[i][j]].pb((node){i,j}),mx=max(mx,a[i][j])):(a[i][j]=-a[i][j]);
for(i=1;i<=mx;++i)if(q2[i].size())x=q2[i].back().x,y=q2[i].back().y,q2[i].pop_back(),bfs(x,y),--i;
else if(q1[i].size()){
x=q1[i].back().x,y=q1[i].back().y,q1[i].pop_back();
if(~b[x][y]){--i;continue;}
++ans,b[x][y]=a[x][y],bfs(x,y),--i;
}
printf("%d\n",ans);
}
金主席：没题面的题都能A
题面可以看这-->点这说明金主席很强
很显然可以得到级别是$n^2$的边，把边当做元素，排列$p_{i}$给出了$n^2$级别的等式$i->j=p_{i}->p_{j}$，然后把相同的缩掉剩下$k$条边，$Ans=2^k$
然而这样做是$n^2$的，需要优化，把$i$向$p_{i}$连边，连完后的图一定是由若干个环构成的，假设第$i$个环的大小为$l_{i}$，如果环的大小是偶数那显然就不合法了，否则
$K=\sum \frac{l_{i}}{2}+\sum gcd(l_{i},l_{j})(i<j)$
因为大小不同的环最多是$\sqrt{n}$级别的，所以复杂度是$O(n)$
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 10010
#define mo 1000
int i,j,k,m,n,x,y,cnt,fa[N],last[N],len[N],l,h[N],vis[N],now,p[N],ans;
struct edge{int to,next;}e[N];
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt;}
inline int dfs(int x,int d){vis[x]=1;for(int i=last[x],y;i;i=e[i].next)if(!vis[y=e[i].to])d+=dfs(y,1);return d;}
inline int power(int a,int b){int ret=1;for(;b;a=a*a%mo,b>>=1)if(b&1)ret=ret*a%mo;return ret;}
int main(){
for(n=read(),i=1;i<=n;++i)x=read(),add(i,x),fa[x]=i;
for(i=1;i<=n;++i)if(!vis[i])h[++l]=dfs(i,1);
for(i=1;i<=l;++i)if(!(h[i]&1))return puts("0"),0;
for(i=1;i<=l;++i)++len[h[i]],ans+=h[i]>>1;
for(sort(h+1,h+l+1),p[m=1]=h[1],i=2;i<=l;++i)if(h[i]!=h[i-1])p[++m]=h[i];
for(i=1;i<m;++i)for(j=i+1;j<=m;++j)ans+=__gcd(p[i],p[j])*len[p[i]]*len[p[j]];
for(i=1;i<=m;++i)ans+=((len[p[i]])*(len[p[i]]-1)>>1)*p[i];
printf("%d\n",power(2,ans));
}
考虑从低往高，找相同联通块周围最低那个，然后填满，不能填了就停下
复杂度$O(能过)$ 其实是我不会算
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 10010
#define pb push_back
int i,j,k,m,n,x,y,mp[110][110],ans,now,vis[110][110],mx,p;
struct node{int x,y;}q[N];vector<node>o,h[N];
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
inline void bfs(int x,int y){
int l=1,r=1;q[r]=(node){x,y},o.pb(q[r]),vis[x][y]=i,p=N;
while(l<=r){
int xx=q[l].x,yy=q[l++].y;
for(int i=0;i<4;++i){
int fx=xx+dx[i],fy=yy+dy[i];
if(fx<0||fx>n+1||fy<0||fy>m+1)continue;
if(vis[fx][fy]==::i)continue;
if(mp[fx][fy]!=mp[x][y])p=min(p,mp[fx][fy]);else q[++r]=(node){fx,fy},o.pb(q[r]),vis[fx][fy]=::i;
}
}
if(p>mp[x][y]){
ans+=o.size()*(p-mp[x][y]);
while(o.size()){
int xx=o.back().x,yy=o.back().y;
h[p].pb(o.back()),mp[xx][yy]=p,o.pop_back();
}
}else while(o.size())o.pop_back();
}
int main(){
for(n=read(),m=read(),i=1;i<=n;++i)for(j=1;j<=m;++j)mp[i][j]=read(),mx=max(mp[i][j],mx),h[mp[i][j]].pb((node){i,j});
for(i=1;i<=mx;++i)while(h[i].size()){
x=h[i].back().x,y=h[i].back().y;h[i].pop_back();
if(vis[x][y]==i)continue;bfs(x,y);
}
printf("%d\n",ans);
}
波兰人这么喜欢出欧拉回路这让我有一些惊方
显然是连边，从前往后连有向边，然后问题就是最少加几条边形成一条欧拉路，考虑欧拉回路，减一可以得到欧拉路，形成欧拉回路的话就是入度$-$出度$/2$，但是原图不一定是连通的，所以还得加上原图里存在欧拉回路的联通块数量
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1010
int i,j,k,m,n,x,y,fa[N],in[N],ot[N],ans,a[N];bool vis[N],mk[N],b[N];
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
for(i=1;i<=1000;++i)fa[i]=i;
for(n=read(),i=1;i<=n;++i){
x=read(),y=read(),++ot[x],++in[y],mk[x]=mk[y]=1;
int p=find(x),q=find(y);if(p!=q)fa[q]=p;
}
for(i=1;i<=1000;++i)if(mk[i])a[++k]=i,fa[i]=find(fa[i]);
for(i=1;i<=k;++i)if(in[fa[a[i]]]!=ot[fa[a[i]]])vis[fa[a[i]]]=1;
for(i=1;i<=k;++i)if(!b[fa[a[i]]])if(!vis[fa[a[i]]])++m,b[fa[a[i]]]=1;
for(i=1;i<=k;++i)ans+=abs(in[a[i]]-ot[a[i]]);
printf("%d\n",(ans>>1)+m+n);
}
为什么这题没人去做，难道是懒的写吗？
要我说，题解就两个字：硬上
对于每个矩形，其他矩形都贡献了一个小小的扇形角度，求个并看看是否覆盖完全就行了
代码越写越长
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());}
#define N 1010
#define pi M_PI
#define eps 0
int i,j,k,m,n,x,y,cnt,Flag=1;char ch;double mx,now;
struct Poi{double x,y;inline void in(){x=read(),y=read();}}h[N],no;
inline double dis(const Poi&a,const Poi&b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline Poi midpoi(const Poi&a,const Poi&b){return(Poi){(a.x+b.x)/2,(a.y+b.y)/2};}
struct ju{
Poi a,b,c,d,o,p,L,R;int f;double l,r;
inline double mklen(){
if(f==1)return p=midpoi(b,d),dis(b,d)/2;
if(f==2)return p=midpoi(a,c),dis(a,c)/2;
if(f==3)return p=midpoi(c,d),dis(c,d)/2;
return p=midpoi(a,b),dis(a,b)/2;
}
inline void get(){
double len=mklen()/2;o=midpoi(a,d);
if(f==1){
L.x=p.x,L.y=p.y+len,l=atan2(L.x-o.x,L.y-o.y)*180/pi;
R.x=p.x,R.y=p.y-len,r=atan2(R.x-o.x,R.y-o.y)*180/pi;
}
if(f==2){
L.x=p.x,L.y=p.y-len,l=atan2(L.x-o.x,L.y-o.y)*180/pi;
R.x=p.x,R.y=p.y+len,r=atan2(R.x-o.x,R.y-o.y)*180/pi;
}
if(f==3){
L.x=p.x+len,L.y=p.y,l=atan2(L.x-o.x,L.y-o.y)*180/pi;
R.x=p.x-len,R.y=p.y,r=atan2(R.x-o.x,R.y-o.y)*180/pi;
}
if(f==4){
L.x=p.x-len,L.y=p.y,l=atan2(L.x-o.x,L.y-o.y)*180/pi;
R.x=p.x+len,R.y=p.y,r=atan2(R.x-o.x,R.y-o.y)*180/pi;
}
}
}M[N];
inline int path(char c){
if(c=='E')return 1;if(c=='W')return 2;
if(c=='S')return 3;if(c=='N')return 4;
}
inline double disx(const Poi&a,const Poi&b){return a.x-b.x;}
inline double disy(const Poi&a,const Poi&b){return a.y-b.y;}
inline Poi interval(const ju&o,const ju&p){
double v[4]={atan2(disx(p.a,o.o),disy(p.a,o.o))*180/pi,
atan2(disx(p.b,o.o),disy(p.b,o.o))*180/pi,
atan2(disx(p.c,o.o),disy(p.c,o.o))*180/pi,
atan2(disx(p.d,o.o),disy(p.d,o.o))*180/pi
};
int tot=0;
if(o.f==1){
for(int i=0;i<4;++i)if(v[i]>0)++tot;
if(!tot)return(Poi){-181,-181};
for(int i=0;i<4;++i)if(v[i]>=-90+eps&&v[i]<0)v[i]=0;
else if(v[i]<=-90-eps)v[i]=180;
return sort(v,v+4),(Poi){v[0],v[3]};
}
if(o.f==2){
for(int i=0;i<4;++i)if(v[i]<0)++tot;
if(!tot)return(Poi){-181,-181};
for(int i=0;i<4;++i)if(v[i]<90-eps&&v[i]>0)v[i]=0;
else if(v[i]>90+eps)v[i]=-180;
return sort(v,v+4),(Poi){v[0],v[3]};
}
if(o.f==3){
for(int i=0;i<4;++i)if(v[i]>90+eps||v[i]<-90-eps)++tot;
if(!tot)return(Poi){-181,-181};
for(int i=0;i<4;++i)if(v[i]>-90+eps&&v[i]<0-eps)v[i]=-90;
else if(v[i]>0+eps&&v[i]<90-eps)v[i]=90;
double zz[5],ff[5];int l=0,r=0;
for(int i=0;i<4;++i)if(fabs(v[i])==v[i])zz[++l]=v[i];else ff[++r]=v[i];
sort(zz+1,zz+l+1),sort(ff+1,ff+r+1);
if(l&&r)return(Poi){zz[1],ff[r]};
else if(l)return(Poi){zz[1],zz[l]};
else if(r)return(Poi){ff[1],ff[r]};
}
if(o.f==4){
for(int i=0;i<4;++i)if(v[i]>-90+eps&&v[i]<90-eps)++tot;
if(!tot)return(Poi){-181,-181};
for(int i=0;i<4;++i)if(v[i]<-90-eps)v[i]=-90;
else if(v[i]>90+eps)v[i]=90;
double zz[5],ff[5];int l=0,r=0;
for(int i=0;i<4;++i)if(fabs(v[i])==v[i])zz[++l]=v[i];else ff[++r]=v[i];
sort(zz+1,zz+l+1),sort(ff+1,ff+r+1);
if(l&&r)return(Poi){ff[1],zz[l]};
else if(l)return(Poi){zz[1],zz[l]};
else if(r)return(Poi){ff[1],ff[r]};
}
}
inline bool cmp1(const Poi&a,const Poi&b){if(fabs(a.x-b.x)<eps)return a.y<b.y;return a.x<b.x;}
inline void jover(double&x){
if(fabs(x)==x)x=x-90;
else x=180-(fabs(x-90)-180);
}
inline void rover(double&x){x+=90;}
int main(){
for(n=read(),i=1;i<=n;++i){
M[i].a.in(),M[i].d.in();
M[i].b.x=M[i].d.x,M[i].b.y=M[i].a.y;
M[i].c.x=M[i].a.x,M[i].c.y=M[i].d.y;
read(ch),M[i].f=path(ch),M[i].get();
}
for(i=1;i<=n;++i){
for(cnt=0,mx=now=-181,j=1;j<=n;++j)if(i!=j){
no=interval(M[i],M[j]);
if(no.x==-181||no.y==-181)continue;
if(M[i].f==1||M[i].f==2)if(no.x<=M[i].r+eps&&no.y>=M[i].l-eps)h[++cnt]=no;
if(M[i].f==3)if((no.y>=M[i].l-eps||no.y<=-90+eps)&&(no.x<=M[i].r+eps||no.x>=90-eps))h[++cnt]=no;
if(M[i].f==4)if((no.x<=M[i].r+eps&&no.x>=-90-eps)&&(no.y>=M[i].l-eps&&no.y<=90+eps))h[++cnt]=no;
}
if(M[i].f==1||M[i].f==2){
sort(h+1,h+cnt+1,cmp1);bool flg=1;
if(h[1].x>M[i].l+eps)flg=0;
for(j=1;j<=cnt;++j)mx=max(mx,h[j].y);
if(mx<M[i].r-eps)flg=0;
for(now=h[1].y,j=2;j<=cnt&&flg;++j)if(h[j].x>now-eps)flg=0;else now=max(now,h[j].y);
if(!flg)printf("%d\n",i),Flag=0;
}
if(M[i].f==3){
bool flg=1;for(j=1;j<=cnt;++j)jover(h[j].x),jover(h[j].y);
jover(M[i].l),jover(M[i].r),sort(h+1,h+cnt+1,cmp1);
if(h[1].x>M[i].l+eps)flg=0;
for(j=1;j<=cnt;++j)mx=max(mx,h[j].y);
if(mx<M[i].r-eps)flg=0;
for(now=h[1].y,j=2;j<=cnt&&flg;++j)if(h[j].x>now-eps)flg=0;else now=max(now,h[j].y);
if(!flg)printf("%d\n",i),Flag=0;
}
if(M[i].f==4){
bool flg=1;for(j=1;j<=cnt;++j)rover(h[j].x),rover(h[j].y);
rover(M[i].l),rover(M[i].r),sort(h+1,h+cnt+1,cmp1);
if(h[1].x>M[i].l+eps)flg=0;
for(j=1;j<=cnt;++j)mx=max(mx,h[j].y);
if(mx<M[i].r-eps)flg=0;
for(now=h[1].y,j=2;j<=cnt&&flg;++j)if(h[j].x>now-eps)flg=0;else now=max(now,h[j].y);
if(!flg)printf("%d\n",i),Flag=0;
}
}
if(Flag)puts("BRAK");
}
先$dfs$构树，然后就是一个裸的树形$DP$
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){char ch=nc();for(;ch==' '||ch=='\n';ch=nc());return ch-48;}
#define N 10010
int i,j,k,m,n,x,y,cnt,last[N],tot,du[N],f[N][4],z[N][4];
struct edge{int to,next;}e[N];
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt;}
void dfsbuild(int x){
if(du[x]==1)add(x,++tot),du[tot]=read(),dfsbuild(tot);
if(du[x]==2)add(x,++tot),du[tot]=read(),dfsbuild(tot),add(x,++tot),du[tot]=read(),dfsbuild(tot);
}
#define oo 0x7f7f7f7f
void Dp(int x){
f[x][1]=f[x][3]=z[x][1]=z[x][3]=0,f[x][2]=z[x][2]=1;
for(int i=last[x];i;i=e[i].next)Dp(e[i].to);
if(du[x]==1){
int v=e[last[x]].to,mx=0,mn=oo;
for(int i=1;i<=3;++i){
mx=0,mn=0x7f7f7f7f;
for(int j=1;j<=3;++j)if(i!=j)mn=min(mn,z[v][j]),mx=max(f[v][j],mx);
f[x][i]+=mx,z[x][i]+=mn;
}
}
if(du[x]==2){
int son[3]={0,0,0},g[4]={0,0,0,0},h[4]={oo,oo,oo,oo};
for(int i=last[x];i;i=e[i].next)son[++*son]=e[i].to;
for(int i=1;i<=3;++i)for(int j=1;j<=3;++j)
if(i!=j)g[6-i-j]=max(g[6-i-j],f[son[1]][i]+f[son[2]][j]),h[6-i-j]=min(h[6-i-j],z[son[1]][i]+z[son[2]][j]);
for(int i=1;i<=3;++i)f[x][i]+=g[i],z[x][i]+=h[i];
}
}
int main(){
du[1]=read(),dfsbuild(++tot),Dp(1),printf("%d %d\n",max(max(f[1][3],f[1][1]),f[1][2]),min(min(z[1][3],z[1][2]),z[1][1]));
}
首先 如果$n$是偶数那先手是必胜的，为什么呢，设和黑色三角相邻的三角形个数有$k$个，那么当$k=1||abs(n-k-3-k)mod$ $2$先手是必胜的，即$n$为偶数
#include<cstdio>
int i,j,n,tot,a,b,c,x,y,z,cnt;
int main(){
for(scanf("%d%d%d%d",&n,&a,&b,&c),i=2;i<n-1;++i){
tot=0,scanf("%d%d%d",&x,&y,&z);
if(x==a||x==b||x==c)++tot;
if(y==a||y==b||y==c)++tot;
if(z==a||z==b||z==c)++tot;
if(tot>=2)++cnt;if(cnt>1)break;
}
if(!(n&1)||(cnt==1))puts("TAK");else puts("NIE");
}
这道题十分有趣，我强烈推荐_(:зゝ∠)_
题目意思也就是传说中的推箱子，要求最小步数，最小步数问题显然就是$bfs$喽，$bfs$的状态显然存的是箱子的位置和人推的方向
但是存在一个问题，扩展的时候会改方向，但是并不知道人能不能走到那个要推方向的格子上，最简单的做法是再$bfs$一遍
然而时间复杂度是$O(n^4*4)$，显然是会$T$的
那有什么快速的办法来判连通性呢？
考虑双连通分量，如果箱子不在割点上，那么只要连通怎样都是能到的，如果箱子在割点上，那么只要通过判断是否在同个双连通分量上，就能得知连通性
在同个双联通分量上的话，箱子挡掉其中一条路，还是有另一条可以走的，于是就先把图中的割点和块都预处理出来就可以$O(1)$判连通辣！
感觉这题实在是很优美，有一些要注意的地方，就是割点是会被多个双联通分量包含的，所以要都记下来
过了之后我还发现了一些 有趣的东西：
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 110
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
char mp[N][N];int i,j,l,r,top,ans,Po[N][N],Now,stx,ex,now,ey,bx,by,sty,k,m,n,x,y,po[N][N],bcc,clock,pre[N][N];
bool cut[N][N],mk[N][N][4];vector<int>bl[N][N];
inline void add(int x,int y,int bcc){
for(int i=0;i<bl[x][y].size();++i)if(bl[x][y][i]==bcc)return;
bl[x][y].push_back(bcc);
}
struct edge{int x1,y1,x2,y2;}S[N*N];
struct node{int x,y,d;}q[N*N*4];
int dfs(int x,int y,int fx,int fy){
int lw=pre[x][y]=++clock,cld=0;Po[x][y]=Now;
for(int i=0;i<4;++i){
int xx=x+dx[i],yy=y+dy[i];
if(mp[xx][yy]=='S'||xx<1||xx>n||yy<1||yy>m||(xx==fx&&yy==fy))continue;
edge e=(edge){x,y,xx,yy};
if(!pre[xx][yy]){
S[++top]=e,++cld;int lv=dfs(xx,yy,x,y);
lw=min(lw,lv);
if(lv>=pre[x][y]){
cut[x][y]=1,++bcc;
for(;;){
edge o=S[top--];
add(o.x1,o.y1,bcc),add(o.x2,o.y2,bcc);
if(o.x1==x&&o.y1==y&&o.x2==xx&&o.y2==yy)break;
}
}
}else if(pre[xx][yy]<pre[x][y])S[++top]=e,lw=min(lw,pre[xx][yy]);
}
if(fx<0&&fy<0&&cld==1)cut[x][y]=0;
return lw;
}
void dfs1(int x,int y){
po[x][y]=now;for(int i=0;i<4;++i){
int xx=x+dx[i],yy=y+dy[i];
if(po[xx][yy]||mp[xx][yy]=='S'||xx<1||xx>n||yy<1||yy>m||mp[xx][yy]=='P')continue;
dfs1(xx,yy);
}
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;++i)scanf("%s",mp[i]+1);
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!pre[i][j]&&mp[i][j]!='S')++Now,dfs(i,j,-1,-1);
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!po[i][j]&&mp[i][j]!='S'&&mp[i][j]!='P')++now,dfs1(i,j);
for(i=1;i<=n;++i)for(j=1;j<=m;++j)
if(mp[i][j]=='M')stx=i,sty=j;
else if(mp[i][j]=='P')bx=i,by=j;
else if(mp[i][j]=='K')ex=i,ey=j;
for(l=1,i=0;i<4;++i)if(po[stx][sty]==po[bx+dx[i]][by+dy[i]])q[++r]=((node){bx,by,i}),mk[bx][by][i]=1;
for(;l<=r;++ans){
int k=r-l+1;
for(j=1;j<=k;++j){
int x=q[l].x,y=q[l].y,d=q[l++].d,xx,yy;
if(x==ex&&y==ey)return printf("%d",ans),0;
for(i=0;i<4;++i){
if(cut[x][y]){
bool flag=0;
for(int p=0;p<bl[x+dx[i]][y+dy[i]].size()&&flag==0;++p)
for(int q=0;q<bl[x+dx[d]][y+dy[d]].size()&&flag==0;++q)if(bl[x+dx[i]][y+dy[i]][p]==bl[x+dx[d]][y+dy[d]][q])flag=1;
if(flag&&mp[xx=x-dx[i]][yy=y-dy[i]]!='S'&&xx>=1&&xx<=n&&yy>=1&&yy<=m)
if(!mk[xx][yy][i])q[++r]=(node){xx,yy,i},mk[xx][yy][i]=1;
}else if((!mk[xx=x-dx[i]][yy=y-dy[i]][i])&&(mp[xx][yy]!='S')&&xx>=1&&xx<=n&&yy>=1&&yy<=m&&Po[x+dx[i]][y+dy[i]]==Po[x+dx[d]][y+dy[d]])q[++r]=(node){xx,yy,i},mk[xx][yy][i]=1;
}
}
}
puts("NO");
}
就$4$种么，对于一碗菜，被左边次，被右边次，被同时次，不被次，然后就转移好辣
#include<bits/stdc++.h>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000010
int i,j,k,m,n,x,y,a[N],f[N][5],ans[N];
inline void work(int x){
for(i=1;i<=n;++i)for(k=1;k<=4;++k)f[i][k]=0;
for(f[1][x]=1,i=2;i<=n;++i){
if(f[i-1][1]&&(a[i-1]<=(a[i]<<1)))f[i][1]=1;
if(f[i-1][4]&&(a[i-1]<=a[i]))f[i][1]=4;
if(f[i-1][2]&&((a[i-1]<<1)>=a[i]))f[i][2]=2;
if(f[i-1][3]&&(a[i-1]>=a[i]))f[i][2]=3;
if(f[i-1][1]&&(a[i-1]<=a[i]))f[i][3]=1;
if(f[i-1][4]&&((a[i-1]<<1)<=a[i]))f[i][3]=4;
if(f[i-1][2]&&(a[i-1]>=a[i]))f[i][4]=2;
if(f[i-1][3]&&(a[i-1]>=(a[i]<<1)))f[i][4]=3;
}
if(f[n][x]==0)return;
for(i=n;i>=1;--i){
if(x==1)ans[i-1]=(i-1)%(n-1)+1;
if(x==2)ans[i]=(i-1)%(n-1)+1;
if(x==3)ans[i-1]=ans[i]=(i-1)%(n-1)+1;
x=f[i][x];
}
for(--n,i=1;i<n;++i)printf("%d ",ans[i]);
printf("%d\n",ans[n]),exit(0);
}
int main(){
for(n=read(),i=1;i<=n;++i)a[i]=read();a[++n]=a[1];
for(j=1;j<=4;++j)work(j);puts("NIE");
}
这是一道思博题，但是没什么人$A$，为什么呢？因为是$bzoj$上的交互，真特么麻烦
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#define nc() getchar()
inline int read(){
int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
if(ch=='-')f=-1,ch=nc();for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define MAGIC_BEGIN -435634223
#define MAGIC_END -324556462
#define MIN_K 1
#define MAX_K 1000000
#define MAX_N 15000000
#define MIN_A 1
#define MAX_A 1000000000
#define MIN_TYP 1
#define MAX_TYP 3
#define MIN_PAR 0
#define MAX_PAR 1000000000
#define ERROR 0
#define CORRECT 1
#define unlikely(x) __builtin_expect(!!(x), 0)
static int init = 0;
static int lib_n;
static int con_k;
static int N, K, A, TYP, PAR;
static int bre, len_sub, bou, is_end;
static int rand2_status = 198402041;
static inline int rand2(int a, int b){
rand2_status = rand2_status * 1103515245 + 12345;
int x = rand2_status;
if (x < 0) x = -x;
x >>= 1;
x = a + x % (b - a + 1);
return x;
}
static inline int random_test(){return rand2(1, A);}
static inline int decreasing_test(){
int tmp;
if(bre == 0) {
bre = rand2(0, (N - lib_n + 1 - len_sub));
tmp = A;
A -= rand2(0, (A - 1) / len_sub);
len_sub--;
}
else {
bre--;
tmp = rand2(1, A);
}
return tmp;
}
static inline int increasing_test()
{
return bou - decreasing_test();
}
static void finish(int res, char *com)
{
if(res == ERROR)
printf("%s\n", com);
exit(0);
}
int inicjuj()
{
if(init == 1)
finish(ERROR, "Program zawodnika moze wywolac funkcje inicjuj tylko raz!!!");
init = 1;
K=read();
if (K > 0){
TYP = 0;
N = MAX_N + 2;
return K;
}
int magic_begin, magic_end;
magic_begin=read(),TYP=read();
if(magic_begin != MAGIC_BEGIN || TYP < MIN_TYP || TYP > MAX_TYP)
finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
N=read(),K=read(),A=read(),PAR=read();
if(N < 1 || N > MAX_N || N < K || K > MAX_K || A < MIN_A || A > MAX_A
|| PAR < MIN_PAR || PAR > MAX_PAR)
finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
magic_end=read();
if(magic_end != MAGIC_END)
finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
con_k = 0;
lib_n = 0;
is_end = 0;
if(TYP == 2 || TYP == 3) {
len_sub = PAR;
bre = 0;
}
if(TYP == 2)
bou = A--;
return K;
}
int wczytaj(){
if(unlikely(init == 0))
finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
if(unlikely(lib_n > N || is_end == 1))
finish(ERROR, "Program zawodnika wywolal funkcje wczytaj po otrzymaniu informacji o koncu ciagu!!!");
if(unlikely(lib_n == N))
return 0;
lib_n++;
switch (TYP) {
case 0:
A=read();
if(A == 0)
is_end = 1;
return A;
break;
case 1: return random_test(); break;
case 2: return increasing_test(); break;
case 3: return decreasing_test(); break;
default:
finish(ERROR, "Nieznany typ testu");
}
return -1;
}
void wypisz(int jakoscProjektu)
{
if(init == 0)
finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
printf("%d\n", jakoscProjektu);
if(++con_k == K)
finish(CORRECT, "");
}
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 15050000
int i,k,n,x,a[N];
struct queue{
int h,r,q[N];
void push(int x){
while((r-h)>=1&&q[r]<x)--r;
if((r-h)<k)q[++r]=x;
}
inline void pop(){q[++h]=0;}
inline int front(){return q[h+1];}
}q;
int main(){
k=inicjuj();
for(n=0;n<k;++n)a[n]=wczytaj();
for(--n;x=wczytaj(),x;)a[++n]=x,q.push(a[n-k]);
for(i=k-1;~i;--i)q.push(a[n-i]),wypisz(q.front()),q.pop();
}
一看到 独立集这种的，首先不就是想到随机吗，命中率很高啊
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
int T,n,i,y,m,x,ans,k,q[N],t,lc[N],dl[N],cnt,last[N],s;
struct edge{int to,next;}e[N*6];
inline void add(int u,int v){
e[++cnt]=(edge){v,last[u]},last[u]=cnt;
e[++cnt]=(edge){u,last[v]},last[v]=cnt;
}
int main(){
for(n=read(),k=read(),m=read();m--;)add(read(),read());
for(T=n>=100000?1:20;T--;){
for(s=0,t=n,i=1;i<=n;++i)q[i]=lc[i]=i,dl[i]=0;
while(t){
y=q[x=rand()%t+1],lc[q[x]=q[t--]]=x,++s;
for(i=last[y];i;i=e[i].next)if(!dl[e[i].to])dl[e[i].to]=1,x=lc[e[i].to],lc[q[x]=q[t--]]=x;
}
ans=max(ans,s);
}
if(ans<k)puts("NIE");else printf("%d",ans);
}
题面有歧义？$f_{i,j}$表示最后一次查到$i$与$i+1$，查了$j$次的最多人数，暴力转移即可
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 606
int K,i,j,k,m,n,x,y,f[N][N],p[N][N],ans[N],loc,sm[N][N];
int main(){
for(n=read(),K=read(),i=1;i<n;++i)for(j=i+1;j<=n;++j)sm[i][j]=read()+sm[i][j-1];
for(i=1;i<n;++i)for(j=1;j<=n;++j)sm[i][j]+=sm[i-1][j];
for(memset(f,-1,sizeof f),f[0][0]=0,i=1;i<n;++i)for(j=1;j<=min(i,K);++j)for(k=0;k<i;++k){
int ret=sm[i][n]-sm[i][i]-sm[k][n]+sm[k][i];
if(f[i][j]<f[k][j-1]+ret)f[i][j]=f[k][j-1]+ret,p[i][j]=k;
}
for(i=1;i<n;++i)if(f[i][K]>f[loc][K])loc=i;
for(i=K;i;--i)ans[i]=loc,loc=p[loc][i];
for(i=1;i<K;++i)printf("%d ",ans[i]);printf("%d\n",ans[K]);
}
$hash$+$tire$直接上好了。。然而跑的好慢，应该有其他做法
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define S 100000
char bf[S],*p1=bf,*p2=bf;
#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,S,stdin),p2==p1)?0:*p1++)
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());}
#define N 2000020
#define uint unsigned int
#define ll long long
int i,j,k,m,n,x,y,len[N];string s[N];char ch[N];uint h,p[N],hs[N];ll ans;
struct tire{tire*go[26];int ct,id;}C[N],*c=C,*rt=C,*o;
inline void insert(){
for(o=rt,j=0;j<len[i];++j){
if(x=ch[j]-'a',!o->go[x])o->go[x]=++c;
o=o->go[x],h=h*131+x+1;
}++o->ct,hs[o->id=i]=h;
}
int main(){
for(p[0]=1,i=1;i<N;++i)p[i]=p[i-1]*131;
for(n=read(),i=1;i<=n;++i){
for(len[i]=read(),j=0;j<len[i];++j)read(ch[j]),s[i].push_back(ch[j]);
h=0,insert();
}
for(i=1;i<=n;++i)for(o=rt,j=0;j<len[i];++j){
if(!o->go[s[i][j]-'a'])break;o=o->go[s[i][j]-'a'];
if(o->ct&&hs[o->id]*p[len[i]]+hs[i]==hs[i]*p[len[o->id]]+hs[o->id])ans+=o->ct;
}
printf("%lld\n",(ans<<1)-n);
}
$updating...$
2022年8月31日 13:53
Bangladesh Education Board DPE has conducted the class 8th grade of Junior School Certificate Exam and Junior Dakhil Certificate Exam on 1st to 15th November 2022 at all centers in division wise under Ministry of Primary and Mass Education (MOPME), and the class 8th grade terminal examination tests are successfully conducted for all eligible JSC/JDC students for the academic year of 2022. JSC Result Dinajpur Board The Bangladesh government Minister of Secondary Education is going to announce the JSC Result 2022 in student wise for division students in education board wise, and the result documents will be submitted to the Prime Minister of the country after then the result with mark sheet will be announced to public to check the individual result.