C_SUNSHINE's Blog
一个萌萌哒AH哒OIer
C_SUNSHINE
窝是萌萌哒lzz……
音乐
分类
最新评论
最新留言
链接
标签云
计数器
11083
TJOI2015
只想看代码的直接翻到最下面
BZOJ3996: [TJOI2015]线性代数
一眼最小割，首先计算出答案 [tex]ans=\left ( \sum_{i=1}^{n}\sum_{i=1}^{n}A_iA_jB_{j,i}\right )-\sum_{i=1}^{n}A_iC_i [/tex] 然后对于所有[tex]i<j[/tex]，连边[tex]<S,i,B{i,j}+B{j,i}>[/tex],[tex]<S,j,B{i,j}+B{j,i}>[/tex],[tex]<i,j,B{i,j}+B{j,i}>[/tex],[tex]<j,i,B{i,j}+B{j,i}>[/tex]
对于所有[tex]i[/tex]，连边：[tex]<i,T,C_i*2>[/tex]
做最小割得到[tex]c[/tex]，则[tex]ans=\left ( \sum B_{i,j} \right )-\frac{c}{2}[/tex]
BZOJ3997: [TJOI2015]组合数学
Dilworth定理：有向无环图(DAG)的最小链覆盖=最大点独立集
于是只要从左下角到右上角DP就可以了
时间复杂度：[tex]O(nm)[/tex]
BZOJ3998: [TJOI2015]弦论
先构造出后缀自动机(SAM)，然后统计一下以某个点开始的子串数目，最后从root开始26分查找就行了。
时间复杂度[tex]O(n*\left | \Sigma \right |)[/tex]
BZOJ3999: [TJOI2015]旅游
树链剖分裸题树链剖分不会的看这个
线段树节点维护：[tex]mn=min\{p_i\}[/tex], [tex]mx=max\{p_i\}[/tex] ,[tex]m1=max\{p_j-p_i\}(i<j)[/tex] ,[tex]m2=max\{p_j-p_i\}(i>j)[/tex]
合并也很简单
struct msg
{
LL mn,mx,m1,m2;
msg(const LL &_mn=0,const LL &_mx=0,const LL &_m1=0,const LL &_m2=0):mn(_mn),mx(_mx),m1(_m1),m2(_m2){}
friend inline msg operator+(const msg &a,const msg &b)
{return msg(min(a.mn,b.mn),max(a.mx,b.mx),max(max(a.m1,b.m1),b.mx-a.mn),max(max(a.m2,b.m2),a.mx-b.mn));}
};
复杂度[tex]O(nlog^2n)[/tex]
具体看代码吧。
BZOJ4000: [TJOI2015]棋盘
BZOJ4000: [TJOI2015]棋盘
题面略坑，行列编号是从0开始的。
题目里说[tex]1\leq p \leq m[/tex]，样例秒打脸。
说解法吧：显然一行的方案是否合法只跟上一行有关，设[tex]f_{i,j}[/tex]表示第i行，状态为j时的方案数，那么转移时枚举上一行状态是[tex]O(2^m)[/tex]的，如果使用矩阵乘法优化DP，可以做到[tex]O(2^{3m}logn)[/tex]
BZOJ4001: [TJOI2015]概率论
BZOJ4001: [TJOI2015]概率论
首先递推出n个节点所有形态的二叉树的叶子节点的总数，发现是[tex]n*Catalan_{n-1}[/tex]个，而n个节点的二叉树有[tex]Catalan_n[/tex]个，用通项公式展开，得到公式[tex]E=\frac {n(n+1)} {4n-2}[/tex].
精度是个大问题，我用的是手写高精度除法。。。就不用考虑精度误差啦！
如果是在BZOJ上交的话，由于标程本身精度不够，所以跟std交一样的：
long long n; cin>>n; cout<<fixed<<setprecision(9)<<1.0*n*(n+1)/(4*n-2)<<endl;
TJOI2015就这么做完啦。。。水不水呢……
TJOI2015就这么做完啦。。。水不水呢……
代码：
代码：
BZOJ3996: [TJOI2015]线性代数
BZOJ3996: [TJOI2015]线性代数
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
inline void readi(int &x);
const int maxn=555,maxm=3333333,inf=(1<<30)-1;
int n;
int B[maxn][maxn];
int C[maxn],SF[maxn];
int ans,maxflow;
int head[maxn],adj[maxm],f[maxm],next[maxm],tot=1;
int S,T,level[maxn],q[maxn],qh,qt;
void addedge(int u,int v,int w)
{tot++;adj[tot]=v;f[tot]=w;next[tot]=head[u];head[u]=tot;
tot++;adj[tot]=u;f[tot]=0;next[tot]=head[v];head[v]=tot;}
bool bfs()
{
qh=0,q[qt=1]=S;
memset(level,-1,T+1<<2);
level[S]=0;
for(int u,i;qh<qt;)
{
u=q[++qh];
for(i=head[u];i;i=next[i])
if(f[i]>0&&level[adj[i]]==-1)
{
level[adj[i]]=level[u]+1;
if(adj[i]==T)return 1;
q[++qt]=adj[i];
}
}
return 0;
}
int aug(int u,int flow)
{
if(u==T)return maxflow+=flow,flow;
int left=flow,t;
for(int i=head[u];i&&left;i=next[i])
if(level[adj[i]]==level[u]+1&&f[i]>0)
{
t=aug(adj[i],min(left,f[i]));
left-=t;
f[i]-=t;
f[i^1]+=t;
}
if(left==flow)level[u]=-1;
return flow-left;
}
void init()
{
readi(n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
readi(B[j][i]),ans+=B[j][i]<<1;
for(int i=1;i<=n;i++)
readi(C[i]);
S=n+1,T=n+2;
}
void work()
{
for(int i=1;i<=n;i++)
addedge(i,T,C[i]<<1);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
addedge(i,j,B[i][j]+B[j][i]);
addedge(j,i,B[i][j]+B[j][i]);
SF[i]+=B[i][j]+B[j][i];
SF[j]+=B[i][j]+B[j][i];
}
SF[i]+=B[i][i]<<1;
}
for(int i=1;i<=n;i++)
addedge(S,i,SF[i]);
while(bfs())
aug(S,inf);
printf("%d\n",ans-maxflow>>1);
}
int main()
{
init();
work();
return 0;
}
inline void readi(int &x)
{char c;while(c=getchar(),c<'0'||c>'9');
x=c^'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');}
BZOJBZOJ3997: [TJOI2015]组合数学
BZOJBZOJ3997: [TJOI2015]组合数学
#include<cstdio>
#include<algorithm>
using namespace std;
inline void readi(int &x);
const int maxn=1005;
int n,m;
int a[maxn][maxn];
long long f[maxn][maxn];
void init()
{
readi(n),readi(m);
for(int i=n;i>0;i--)
for(int j=1;j<=m;j++)
readi(a[i][j]);
}
void work()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j-1]+a[i][j],max(f[i][j-1],f[i-1][j]));
printf("%lld\n",f[n][m]);
}
int main()
{
int T;
for(readi(T);T--;)
{
init();
work();
}
return 0;
}
inline void readi(int &x)
{char c;while(c=getchar(),c<'0'||c>'9');
x=c^'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');}
```
BZOJ3998: [TJOI2015]弦论
BZOJ3998: [TJOI2015]弦论
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn=1000005;
int T,K;
char s[maxn],ans[maxn];
int len;
int Q[maxn],W[maxn];
namespace Suffix_Automaton
{
struct Sam
{
Sam *nex[26],*pre;
int dep;
LL w,s;
}P[maxn],*root=P+1,*last=root,*ns=root;
void Extend(int x)
{
Sam *p=last,*np=++ns;
np->dep=p->dep+1;
np->w=1;
last=np;
for(;p&&!p->nex[x];p=p->pre)
p->nex[x]=np;
if(!p)np->pre=root;
else
{
Sam *q=p->nex[x];
if(q->dep==p->dep+1)
np->pre=q;
else
{
Sam *nq=++ns;
memcpy(nq->nex,q->nex,sizeof(q->nex));
nq->pre=q->pre;
nq->dep=p->dep+1;
np->pre=q->pre=nq;
for(;p&&p->nex[x]==q;p=p->pre)
p->nex[x]=nq;
}
}
}
void work()
{
int L=ns-P;
for(int i=1;i<=L;i++)
W[P[i].dep]++;
for(int i=1;s[i];i++)
W[i]+=W[i-1];
for(int i=L;i;i--)
Q[W[P[i].dep]--]=i;
for(int i=L;i>1;i--)
if(T)
P[Q[i]].pre->w+=P[Q[i]].w;
else P[Q[i]].w=1;
P[1].w=0;
for(int i=L;i;i--)
{
Sam &p=P[Q[i]];
p.s=p.w;
for(int j=0;j<26;j++)
if(p.nex[j])
p.s+=p.nex[j]->s;
}
}
void solve()
{
Sam *p=root;
while(K)
{
if(K<=p->w)return;
K-=p->w;
for(int i=0;i<26;i++)
if(p->nex[i])
if(K<=p->nex[i]->s)
{
ans[len++]=i+'a';
p=p->nex[i];
break;
}
else K-=p->nex[i]->s;
}
}
}
int main()
{
using namespace Suffix_Automaton;
scanf("%s%d%d",s+1,&T,&K);
for(int i=1;s[i];i++)
Extend(s[i]-'a');
work();
if(K<=root->s)
solve(),puts(ans);
else puts("-1\n");
return 0;
}
BZOJ3999: [TJOI2015]旅游
BZOJ3999: [TJOI2015]旅游
#include<cstdio>
#include<algorithm>
using namespace std;
#define all 1,n
typedef long long LL;
inline void readi(int &x);
const int maxn=50005;
const LL inf=(1LL<<60)-1;
int n,Q;
int a[maxn];
int head[maxn],adj[maxn*2],next[maxn*2],tot;
int siz[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn];
int dfn[maxn],dfa[maxn],idx;
inline void addedge(const int &u,const int &v)
{tot++;adj[tot]=v;next[tot]=head[u];head[u]=tot;
tot++;adj[tot]=u;next[tot]=head[v];head[v]=tot;}
struct msg
{
LL mn,mx,m1,m2;
msg(const LL &_mn=0,const LL &_mx=0,const LL &_m1=0,const LL &_m2=0):mn(_mn),mx(_mx),m1(_m1),m2(_m2){}
friend inline msg operator+(const msg &a,const msg &b)
{return msg(min(a.mn,b.mn),max(a.mx,b.mx),max(max(a.m1,b.m1),b.mx-a.mn),max(max(a.m2,b.m2),a.mx-b.mn));}
};
struct node
{
LL dta;
msg c;
node *lc,*rc;
inline void tagdta(const LL &x)
{c.mn+=x,c.mx+=x,dta+=x;}
inline void update()
{c=lc->c+rc->c;}
inline void downdate()
{
if(dta)
{
lc->tagdta(dta);
rc->tagdta(dta);
dta=0;
}
}
msg add(int l,int r,const int &a,const int &b,const int &d)
{
msg ret;
if(l>=a&&r<=b)
{
ret=c;
return tagdta(d),ret;
}
else
{
int mid=l+r>>1;
downdate();
if(a>mid)ret=rc->add(mid+1,r,a,b,d);
else if(b<=mid)ret=lc->add(l,mid,a,b,d);
else ret=lc->add(l,mid,a,b,d)+rc->add(mid+1,r,a,b,d);
update();
return ret;
}
}
}ndl[maxn*3],*root;
int ns=1;
node *build(int l,int r)
{
node *x=ndl+ns++;
if(l==r)return x->c=msg(a[dfa[l]],a[dfa[r]],0,0),x;
x->lc=build(l,l+r>>1);
x->rc=build(l+r+2>>1,r);
x->update();
return x;
}
void tdfs(const int &x)
{
siz[x]=1;
dep[x]=dep[fa[x]]+1;
for(int i=head[x];i;i=next[i])
if(adj[i]!=fa[x])
{
fa[adj[i]]=x;
tdfs(adj[i]);
siz[x]+=siz[adj[i]];
if(siz[adj[i]]>siz[son[x]])son[x]=adj[i];
}
}
void divide(int x,int tp)
{
dfa[dfn[x]=++idx]=x;
top[x]=tp;
if(son[x])divide(son[x],tp);
for(int i=head[x];i;i=next[i])
if(adj[i]!=fa[x]&&adj[i]!=son[x])
divide(adj[i],adj[i]);
}
void init()
{
readi(n);
for(int i=1;i<=n;i++)
readi(a[i]);
for(int i=1,u,v;i<n;i++)
{
readi(u),readi(v);
addedge(u,v);
}
readi(Q);
tdfs(1);
divide(1,1);
root=build(1,n);
}
LL query(int u,int v,int d)
{
msg su(inf,-inf,0,0),sv(inf,-inf,0,0);
for(int fu,fv;(fu=top[u])!=(fv=top[v]);)
{
if(dep[fu]>dep[fv])
{
su=root->add(all,dfn[fu],dfn[u],d)+su;
u=fa[fu];
}
else
{
sv=root->add(all,dfn[fv],dfn[v],d)+sv;
v=fa[fv];
}
}
if(dep[u]>dep[v])
su=root->add(all,dfn[v],dfn[u],d)+su;
else
sv=root->add(all,dfn[u],dfn[v],d)+sv;
swap(su.m1,su.m2);
return (su+sv).m1;
}
void work()
{
for(int u,v,d;Q--;)
{
readi(u),readi(v),readi(d);
printf("%lld\n",query(u,v,d));
}
}
int main()
{
init();
work();
return 0;
}
inline void readi(int &x)
{char c;while(c=getchar(),c<'0'||c>'9');
x=c^'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');}
BZOJ4000: [TJOI2015]棋盘
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=100005,B=20;
typedef unsigned Mat[67][67];
int n,m,N;
int P,K;
int ak[B+B][B+B];
Mat temp,tb,X,A;
void mult(Mat &a,Mat &b,Mat &c)
{
for(short i=0;i<N;i++)
for(short j=0;j<N;j++)
temp[i][j]=0,tb[i][j]=b[j][i];
for(short i=0;i<N;i++)
for(short j=0;j<N;j++)
for(short k=0;k<N;k++)
temp[i][j]+=a[i][k]*tb[j][k];
for(short i=0;i<N;i++)
for(short j=0;j<N;j++)
c[i][j]=temp[i][j];
}
int attack(const int &x,const int &y)
{return ak[B+x+1][B+y+K];}
void init()
{
scanf("%d%d%d%d",&n,&m,&P,&K);
N=1<<m;
for(int i=0;i<3;i++)
for(int j=0;j<P;j++)
scanf("%1d",&ak[B+i][B+j]);
}
unsigned check(const int &a,const int &b)
{
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
{
if(i!=j&&(1<<i&a)&&(1<<j&a))
if(attack(0,j-i)||attack(0,i-j))return 0;
if(i!=j&&(1<<i&b)&&(1<<j&b))
if(attack(0,j-i)||attack(0,i-j))return 0;
if((1<<i&a)&&(1<<j&b))
if(attack(1,j-i)||attack(-1,i-j))return 0;
}
return 1;
}
void build()
{
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
X[i][j]=check(i,j);
for(int i=0;i<N;i++)
A[i][i]=1;
}
void work()
{
for(;n;n>>=1,mult(X,X,X))
if(n&1)mult(A,X,A);
unsigned ans=0;
for(int i=0;i<N;i++)
ans+=A[0][i];
printf("%u\n",ans);
}
int main()
{
init();
build();
work();
return 0;
}
BZOJ4001: [TJOI2015]概率论
BZOJ4001: [TJOI2015]概率论
#include<cstdio>
const int E=9;
int main()
{
long long n,z,m;
scanf("%lld",&n);
z=n*(n+1),m=n*4-2;
printf("%lld.",z/m);z%=m;
for(int i=1;i<E;i++)
printf("%d",(int)(z*10/m)),z=z*10%m;
printf("%d\n",(int)((z*10+m/2)/m));
return 0;
}
2022年11月24日 12:40
This problem is about finding the determinant of a square matrix. The determinant is a number associated with every square matrix. It is used to solve for cheap real diamond rings online the inverse of a matrix, and to calculate the areas of certain geometric figures. The challenge in this problem is to calculate the determinant of a matrix without using any complex numbers. This is called the cofactor expansion method.
2022年12月24日 15:41
Thanks for sharing the code below. I appreciate your willingness to help out others and contribute to the community. Bicoastal Life And Business Sourabh Sharma This code will certainly be helpful to many people. Keep up the good work!