# 模板总结

xiaoxiao2021-02-28  8

//bat比较程序 @echo off :loop data.exe >in.txt my.exe < in.txt >myout.txt std.exe <in.txt > stdout.txt fc myout.txt stdout.txt if not errorlevel 1 goto loop pause goto loop //随机程序 #include <cstdio> #include <ctime> #include <cstdlib> #define Ran(a,b) (rand()*rand()%(b-a+1)+a) //a~b 的随机数 int main(){ srand(time(0)); while (1){ printf("%d\n",Ran(1,100)); } }

//举个SPFA例子吧，队列中最多同时有 N 个点，其实就是在移动首尾指针的时候模一下即可。 int q[N],l,r; void SPFA(int x){ f[x]=1,d[x]=0; for (q[l=r=0]=x; l!=(r+1)%n; l=(l+1)%n){ For(q[l]) if (d[q[l]]+w<d[o]){ d[o]=d[q[l]]+w; if (!f[o]) q[r=(r+1)%n]=o,f[o]=1; } f[q[l]]=0; } }

for (l=0,r=Max,mid=l+r>>1; l<=r; mid=l+r>>1){ if (check()){ r=mid-1; ans=mid; continue; } l=mid+1; }

void Add(ll x,l y){ for (; x<=n; x+=lowbit(x)) c[x]+=y; } int query(ll x){ for (ret=0; x; x-=lowbit(x)) ret+=c[x]; return ret; }

#include <cstdio> typedef long long ll; ll n,m,Ha,k,k1,k2,k3; struct segment_tree{ #define X t[x] #define Lx (x<<1) #define Rx (Lx+1) #define L t[Lx] #define R t[Rx] #define Mid ((X.l+X.r)>>1) #define sz(x) (t[x].r-t[x].l+1) struct node{ll s,l,r,T1,T2;} t[2000000]; //[l,r]: 区间*t1+t2 void mer(ll x){ X.s=(L.s*L.T1+sz(Lx)*L.T2)%Ha; X.s=(X.s+R.s*R.T1+sz(Rx)*R.T2)%Ha; } void bui(ll x,ll l,ll r){ X=(node){0,l,r,1,0}; if (l==r) {scanf("%d",&X.s); return;} bui(Lx,l,Mid); bui(Rx,Mid+1,r); mer(x); } void add_tag(ll x,ll t1,ll t2){ //(x*T1+T2)*t1+t2=x*(T1*t1)+T2*t1+t2 X.T1=(X.T1*t1)%Ha; X.T2=(X.T2*t1+t2)%Ha; } void down_tag(ll x){ //sigma(i*T1+T2)=sigma(i)*T1+sz*T2 add_tag(Lx,X.T1,X.T2); add_tag(Rx,X.T1,X.T2); ll sz=X.r-X.l+1; X.s=(X.s*X.T1+sz*X.T2)%Ha; X.T1=1,X.T2=0; } ll que(ll x,ll l,ll r){ //询问 [l,r] down_tag(x); if (l<=X.l && X.r<=r) return X.s; ll ret=0; if (l<=Mid) ret=(ret+que(Lx,l,r))%Ha; if (r>Mid) ret=(ret+que(Rx,l,r))%Ha; return ret; } void upd(ll x,ll l,ll r,ll t1,ll t2){ //[l,r]*t1+t2 if (l<=X.l && X.r<=r){add_tag(x,t1,t2); return;} down_tag(x); if (l<=Mid) upd(Lx,l,r,t1,t2); if (r>Mid) upd(Rx,l,r,t1,t2); mer(x); } } T; int main(){ scanf("%d%d%d",&n,&m,&Ha); T.bui(1,1,n); while (m--){ scanf("%d",&k); if (k==1){ scanf("%d%d%d",&k1,&k2,&k3); T.upd(1,k1,k2,k3,0); continue; } if (k==2){ scanf("%d%d%d",&k1,&k2,&k3); T.upd(1,k1,k2,1,k3); continue; } scanf("%d%d",&k1,&k2); printf("%d\n",T.que(1,k1,k2)); } }

void get_p(){ memset(f,0,sizeof(f)); f[1]=1; for (int i=2; i<=N; i++){ if (!f[i]) p[++num]=i; for (int j=1; j<=num && p[j]*i<=N; j++){ f[p[j]*i]=1; if (i%p[j]==0) break; } } }

LCA (此程序可交Luogu-3379)

#include <cstdio> #include <algorithm> #define Add(x,y) (to[++num]=head[x],head[x]=num,V[num]=y) #define For(x) for(int h=head[x],o=V[h]; h; o=V[h=to[h]]) using namespace std; int head[500005],to[1000005],V[1000005],num; int ST[500005][25],d[500005]; int n,m,s,a,b; void dfs(int x,int Fa,int dep){ d[x]=dep; For(x) if (o!=Fa){ ST[o][0]=x; dfs(o,x,dep+1); } } void getST(){ for (int j=1; j<=20; j++) for (int i=1; i<=n; i++) ST[i][j]=ST[ST[i][j-1]][j-1]; } int FA(int x,int y){ //x 的第 y 代祖先 for (int i=0; y; i++,y>>=1) if (y&1) x=ST[x][i]; return x; } int LCA(int x,int y){ if (d[x]<d[y]) swap(x,y); x=FA(x,d[x]-d[y]); //使得 x 和 y 处于同一深度 if (x==y) return x; //一样就直接返回值 for (int i=20; i>=0; i--) if (ST[x][i]!=ST[y][i]) x=ST[x][i],y=ST[y][i]; //一直将 x,y 往上挪找到最上面那层不一样的 return ST[x][0]; //再往上一层就是答案 } int main(){ freopen("1.txt","r",stdin); scanf("%d%d%d",&n,&m,&s); for (int i=1; i<n; i++) scanf("%d%d",&a,&b),Add(a,b),Add(b,a); dfs(s,0,0); getST(); while (m--){ scanf("%d%d",&a,&b); printf("%d\n",LCA(a,b)); } }

void SPFA(int x){ for (int i=1; i<=n; i++) d[i]=2147483647,f[i]=0; f[x]=1,d[x]=0; for (q[l=r=0]=x; l<=r; l++){ For(q[l]) if (d[q[l]]+w<d[o]){ d[o]=d[q[l]]+w; if (!f[o]) q[++r]=o,f[o]=1; } f[q[l]]=0; } }

struct Vector{ double x,y; bool operator < (vector a) const {return x+y<a.x+a.y;} Vector operator + (Vector a) {return (Vector){x+a.x,y+a.y};} double operator * (Vector a) {return x*a.x+y*a.y;} } A,B,C,D; int main(){ A.x=A.y=1; B.x=B.y=2; C=A+B; printf("%.0f %.0f %.0f",C.x,C.y,A*B); }