其实只有day1辣。。。day2还没放出来。。。day2放出来辣
线性代数:
Ci是Ai为1付出的代价,Bij+Bji是AiAj同时为1的价值。。。
真·裸·最小割。。。
#include<algorithm> #include <iostream> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <math.h> #include <time.h> #include <vector> #include <queue> #include <map> #include <set> using namespace std; #define Clear(_,__) memset(_,__,sizeof _) const int N=555,M=1000005,oo=1e9; int f[M],e[M],next[M],G[N],Le[N],tot=1,n,B[N][N],C[N],S,T,SB[N],Sum; void adde(int u,int v,int c,int nc) { e[++tot]=v;next[tot]=G[u];G[u]=tot;f[tot]=c; e[++tot]=u;next[tot]=G[v];G[v]=tot;f[tot]=nc; } bool bfs() { queue<int> Q; Clear(Le,-1); Q.push(S); Le[S]=1; while(!Q.empty()&&Le[T]==-1) { int u=Q.front(); Q.pop(); for(int i=G[u];i;i=next[i]) { int v=e[i]; if(Le[v]==-1&&f[i]>0) Q.push(v), Le[v]=Le[u]+1; } } return Le[T]!=-1; } int dfs(int u,int delta) { if(u==T) return delta; int w=0,t,i,v; for(i=G[u];i&&w<delta;i=next[i]) { v=e[i]; if(Le[v]==Le[u]+1&&f[i]>0) t=dfs(v,min(delta-w,f[i])), w+=t, f[i]-=t, f[i^1]+=t; } if(!w) Le[u]=-1; return w; } int Maxflow() { int Maxf=0; while(bfs()) Maxf+=dfs(S,oo); return Maxf; } int main() { scanf("%d",&n); S=0;T=n+1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&B[i][j]); for(int i=1;i<=n;i++) for(int j=i+1,t;j<=n;j++) SB[i]+=t=B[i][j]+B[j][i], SB[j]+=t, adde(i,j,t,t); for(int i=1;i<=n;i++) Sum+=SB[i]+(B[i][i]<<1), adde(S,i,SB[i]+(B[i][i]<<1),0), scanf("%d",&C[i]), adde(i,T,C[i]<<1,0); printf("%d\n",Sum-Maxflow()>>1); return 0; }
组合数学:
Dilworth定理:DAG的最小链覆盖=最大点独立集
没了。。最大点独立集显然就是一条斜线。。。
#include<algorithm> #include <iostream> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <math.h> #include <time.h> #include <vector> #include <queue> #include <map> #include <set> using namespace std; const int N=1005; int f[N][N],t,n,m,a[N][N],Ans; int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(f,0,sizeof f); Ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=m;i++) { for(int j=n;j;j--) f[j][i]=max(f[j][i-1],f[j+1][i-1]+a[j][i]); for(int j=n;j;j--) f[j][i]=max(f[j][i],f[j+1][i]); Ans=max(Ans,f[1][i]); } cout<<Ans<<endl; } return 0; }
弦论:
裸·真·sam= =spoj即视感= =没了。。。
#include <iostream> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <math.h> #include <time.h> #include <vector> #include <queue> #include <map> #include <set> using namespace std; const int N=500500; struct Node { Node *Son[26],*pre; int l,w,s; }T[N*2],*root=T+1,*last=T+1,*Now=T+1; char s[N]; int type,k,Num[N],Q[N*2]; void Extend(int x) { Node *p=last,*np=++Now; np->l=p->l+1; np->w=1; last=np; for(;p&&!p->Son[x];p=p->pre) p->Son[x]=np; if(!p) np->pre=root; else { Node *q=p->Son[x]; if(q->l==p->l+1) np->pre=q; else { Node *nq=++Now; memcpy(nq->Son,q->Son,sizeof q->Son); nq->l=p->l+1; nq->pre=q->pre; np->pre=q->pre=nq; for(;p&&p->Son[x]==q;p=p->pre) p->Son[x]=nq; } } } void work() { int L=Now-T; for(int i=1;i<=L;i++) Num[T[i].l]++; for(int i=1;s[i];i++) Num[i]+=Num[i-1]; for(int i=L;i;i--) Q[Num[T[i].l]--]=i; for(int i=L;i>1;i--) if(type) T[Q[i]].pre->w+=T[Q[i]].w; else T[Q[i]].w=1; T[1].w=0; for(int i=L;i;i--) { Node &p=T[Q[i]]; p.s=p.w; for(int j=0;j<26;j++) if(p.Son[j]) p.s+=p.Son[j]->s; } } void out() { Node *p=root; while(k) { if(k<=p->w) return; k-=p->w; for(int i=0;i<26;i++) if(p->Son[i]) { if(k<=p->Son[i]->s) { putchar(i+'a'); p=p->Son[i]; break; } k-=p->Son[i]->s; } } } int main() { gets(s+1); scanf("%d%d",&type,&k); for(int i=1;s[i];i++) Extend(s[i]-'a'); work(); if(root->s<k) puts("-1"); else out(); return 0; }
旅游:
树剖裸题。。。
#include<algorithm> #include <iostream> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <math.h> #include <time.h> #include <vector> #include <queue> #include <map> #include <set> using namespace std; typedef long long LL; const int N=200005; struct Sta { LL Max,Min,Ans1,Ans2; Sta():Max(-(1LL<<60)),Min(1LL<<60),Ans1(0),Ans2(0){} }T[N]; Sta operator+(const Sta& a,const Sta& b) { Sta c; c.Max=max(a.Max,b.Max); c.Min=min(a.Min,b.Min); c.Ans1=max(max(a.Ans1,b.Ans1),a.Max-b.Min); c.Ans2=max(max(a.Ans2,b.Ans2),b.Max-a.Min); return c; } int n,q,tot,G[N],e[N],next[N],top[N],son[N],sz[N],pre[N],pos[N],Index,fp[N],dep[N],w[N]; LL tag[N]; void adde(int u,int v) { e[++tot]=v;next[tot]=G[u];G[u]=tot; e[++tot]=u;next[tot]=G[v];G[v]=tot; } void dfs1(int u,int p) { pre[u]=p; dep[u]=dep[p]+1; sz[u]=1; for(int i=G[u];i;i=next[i]) if(e[i]!=p) { dfs1(e[i],u); sz[u]+=sz[e[i]]; if(sz[e[i]]>sz[son[u]]) son[u]=e[i]; } } void dfs2(int u,int p) { top[u]=p; pos[u]=++Index; fp[Index]=u; if(son[u]) dfs2(son[u],p); for(int i=G[u];i;i=next[i]) if(e[i]!=pre[u]&&e[i]!=son[u]) dfs2(e[i],e[i]); } #define Lc (x<<1) #define Rc (x<<1|1) #define Mid (l+r>>1) void Add(int x,LL v) { if(x) T[x].Max+=v, T[x].Min+=v, tag[x]+=v; } void pd(int x) { if(tag[x]) Add(Lc,tag[x]), Add(Rc,tag[x]), tag[x]=0; } void pu(int x) { T[x]=T[Lc]+T[Rc]; } void build(int x,int l,int r) { if(l==r) T[x].Max=T[x].Min=w[fp[l]]; else build(Lc,l,Mid), build(Rc,Mid+1,r), pu(x); } Sta Ask(int x,int l,int r,int L,int R,LL v) { Sta w; if(L<=l&&r<=R) w=T[x], Add(x,v); else { pd(x); if(R<=Mid) w=Ask(Lc,l,Mid,L,R,v); else if(L>Mid) w=Ask(Rc,Mid+1,r,L,R,v); else w=Ask(Lc,l,Mid,L,R,v)+Ask(Rc,Mid+1,r,L,R,v); pu(x); } return w; } LL Ask(int u,int v,LL val) { int fu=top[u],fv=top[v],flagu=1,flagv=0; Sta Ans1,Ans2,Ans; while(fu!=fv) { if(dep[fu]<dep[fv]) swap(fu,fv), swap(u,v), swap(flagu,flagv); Sta Lzz=Ask(1,1,n,pos[fu],pos[u],val); if(flagu) swap(Lzz.Ans1,Lzz.Ans2), Ans1=Ans1+Lzz; else Ans2=Lzz+Ans2; u=pre[fu]; fu=top[u]; } if(dep[u]>dep[v]) swap(u,v),swap(flagu,flagv); Sta Lzz=Ask(1,1,n,pos[u],pos[v],val); if(flagu) Ans1=Ans1+Lzz; else swap(Lzz.Ans1,Lzz.Ans2), Ans2=Lzz+Ans2; Ans=Ans1+Ans2; return Ans.Ans2; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v), adde(u,v); dfs1(1,0); dfs2(1,1); build(1,1,n); scanf("%d",&q); while(q--) { int u,v; LL l; scanf("%d%d%lld",&u,&v,&l); printf("%lld\n",Ask(u,v,l)); } return 0; }
棋盘:
也蛮简单的了。。按行装压dp,没了。。。矩阵乘。。。
#include<algorithm> #include <iostream> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <math.h> #include <time.h> #include <bitset> #include <vector> #include <queue> #include <map> #include <set> using namespace std; typedef unsigned Ud; int n,m,w,k,p,ok[20][20]; struct MAT { Ud t[64][64]; MAT(){memset(t,0,sizeof(t));} }D,I; MAT operator*(const MAT& A,const MAT& B) { MAT C; for(int i=0;i<m;i++) for(int j=0;j<m;j++) for(int k=0;k<m;k++) C.t[i][j]+=A.t[i][k]*B.t[k][j]; return C; } MAT operator^(MAT A,int B) { MAT C=I; while(B) { if(B&1) C=C*A; A=A*A; B>>=1; } return C; } int check(int i,int j) { bool vis[2][20]={}; for(int k=0;k<w;k++) vis[0][k]=i&(1<<k); for(int k=0;k<w;k++) vis[1][k]=j&(1<<k); for(int l=0;l<2;l++) for(int r=0;r<w;r++) if(vis[l][r]) for(int i=0;i<3;i++) for(int j=0;j<p;j++) if(ok[i][j]&&(i!=1||j!=k)) { int x=l+i-1,y=r+j-k; if(x>=0&&x<2&&y>=0&&y<w&&vis[x][y]) return 0; } return 1; } int main() { scanf("%d%d%d%d",&n,&w,&p,&k); for(int i=0;i<3;i++) for(int j=0;j<p;j++) scanf("%d",&ok[i][j]); m=1<<w; for(int i=0;i<m;i++) I.t[i][i]=1; for(int i=0;i<m;i++) for(int j=0;j<m;j++) D.t[i][j]=check(i,j); cout<<(D^n+1).t[0][0]; return 0; }
概率论:
推下公式(打表找规律)就会发现是$\frac{n(n+1)}{4n-2}$,没了。。。
标程你挂精度你知道么
这个程序的精度是挂的。。。
#include<algorithm> #include <iostream> #include <string.h> #include <stdlib.h> #include <iomanip> #include <stdio.h> #include <math.h> #include <time.h> #include <vector> #include <queue> #include <map> #include <set> using namespace std; int main() { long long n; cin>>n; printf("%.9lf",1.0*n*(n+1)/(4*n-2)); return 0; }
2023年6月15日 15:01
CG in films show us a new magical world. Have you ever wonder about the real heights of actors who play Hobbits in Lord of the Rings? You can find the answer on <a href="https://www.celebheightwiki.com/" title="celeb height wiki">celeb height wiki</a> with some clicks.