SYC's Blog
Happy coding
JSOI2009 部分简要题解
做了一部分JSOI2009的题，决定来一发题解。。。
difficulty Rating(Just For Those I have Done):
Very Nausea :等差数列(1558)
Meduim:球队收益(1449),火星藏宝图(1560),密码(1559),有趣的游戏(1444)
Easy:Count(1452),瓶子和燃料(2257)
下面是简要题解：
1452:Count
sol:因为c比较小，所以对于每一种颜色开一个二维树状数组即可。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,a[305][305],tree[105][305][305];
int q,opt,x1,y1,x2,y2,x,y,c;
inline int query(int c,int x,int y)
{
int ret=0;
for(int p=x;p;p-=p&(-p))
for(int z=y;z;z-=z&(-z))
{
ret+=tree[c][p][z];
}
return ret;
}
inline void add(int c,int x,int y,int val)
{
for(int p=x;p<=n;p+=p&(-p))
for(int z=y;z<=m;z+=z&(-z))
tree[c][p][z]+=val;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
add(a[i][j],i,j,1);
}
scanf("%d",&q);
while(q--)
{
scanf("%d",&opt);
if(opt==2)
{
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
printf("%d\n",query(c,x2,y2)-query(c,x1-1,y2)-query(c,x2,y1-1)+query(c,x1-1,y1-1));
}else
{
scanf("%d%d%d",&x,&y,&c);
add(a[x][y],x,y,-1);
add(c,x,y,1);
a[x][y]=c;
}
}
return 0;
}
2257:瓶子和燃料;
sol:可以发现，每次选K个体积为v1,v2,v3..vk的瓶子给火星人，最少会返回gcd(v1,v2..vk),于是问题就变为找最大的x，使得x是至少k个数字的约数，Nsqrt(N)枚举+排序即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,ans;
int a[1000005],tot;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
for(int j=1;j*j<=x;j++)
{
if(x%j==0)
{
a[++tot]=j;
if(j!=x/j)a[++tot]=x/j;
}
}
}
sort(a+1,a+tot+1);
for(int i=tot,k=1;i;i--)
{
if(a[i]==a[i-1])k++;
else
{
if(k>=m)
{
printf("%d\n",a[i]);
return 0;
}
k=1;
}
}
printf("%d\n",ans);
return 0;
}
1449:球队收益
sol:费用流的想法应该是比较显然。。。,关键在于如何构图？
考虑到又有赢又有输很难搞，又因为一场球队参加的比赛数是一定的。我们先假定每个队伍全都是输的，然后考虑多赢一场可以取得的贡献即可。
一个已经赢了这场后赢了win场，要比tot场，两个系数分别为c,d时的贡献是：
win^2*c+(tot-win)^2*d-(win-1)^2*c+(tot-win+1)^2*d=(c+d)*(2*win-1)-2*d*tot;
然后给每个球队和每场比赛建一个点。源点向比赛连容量为1，费用为0的边，表示每场比赛只有一个获胜。每场比赛向每个球队连容量为1，费用为0的边，表示每场比赛只能算一次贡献。球队向汇点连P条边,P表示它在后面的比赛中参加的比赛数。每条边的费用为赢一场的贡献，容量为1。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 6005
using namespace std;
struct e
{
int u,v,w,c,pre;
}edge[1000005];
int n,UpperLimit,x,dex=-1,source,target;
int c[maxn],d[maxn],num[maxn];
int dis[maxn],visit[maxn],adj[maxn],pre[maxn],qe[maxn];
int ans_cost,ans,m,win[maxn],lose[maxn];
inline void add(int u,int v,int w,int c)
{
edge[++dex].u=u;
edge[dex].v=v;
edge[dex].w=w;
edge[dex].c=c;
edge[dex].pre=adj[u];
adj[u]=dex;
edge[++dex].u=v;
edge[dex].v=u;
edge[dex].w=0;
edge[dex].c=-c;
edge[dex].pre=adj[v];
adj[v]=dex;
}
inline int spfa(int source,int target)
{
memset(dis,0x7f,sizeof(dis));
memset(visit,0,sizeof(visit));
memset(pre,-1,sizeof(pre));
memset(qe,-1,sizeof(qe));
queue<int>q;
visit[source]=1;dis[source]=0;
q.push(source);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=adj[u];i!=-1;i=edge[i].pre)
if(edge[i].w)
{
int v=edge[i].v;
if(dis[u]+edge[i].c<dis[v])
{
dis[v]=dis[u]+edge[i].c;
pre[v]=u;qe[v]=i;
if(!visit[v])
{
visit[v]=1;
q.push(v);
}
}
}
visit[u]=0;
}
if(dis[target]>10000000)return 0;
return 1;
}
inline int ek(int source,int target)
{
int aug=1<<30;
for(int i=target;i!=source;i=pre[i])
{
aug=min(aug,edge[qe[i]].w);
}
ans_cost+=dis[target]*aug;
for(int i=target;i!=source;i=pre[i])
{
edge[qe[i]].w-=aug;
edge[qe[i]^1].w+=aug;
}
return 1;
}
inline int sqr(int x){return x*x;}
inline void Build_Graph_To_Do_it(int Source,int Target)
{
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&win[i],&lose[i],&c[i],&d[i]);
num[i]=win[i]+lose[i];
}
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(Source,i+n,1,0);
add(i+n,u,1,0);
add(i+n,v,1,0);
++num[u];++num[v];
}
for(int i=1;i<=n;i++)
{
ans+=(c[i]+d[i])*sqr(win[i])+d[i]*sqr(num[i])-2*num[i]*d[i]*win[i];
for(int j=win[i]+1;j<=num[i]-lose[i];j++)
{
add(i,Target,1,(c[i]+d[i])*(2*j-1)-2*num[i]*d[i]);
}
}
source=Source;
target=Target;
//REMEMBER!!!!!!!!!!!!!!!!
}
inline void work(int source,int target)
{
while(spfa(source,target))ek(source,target);
}
int main()
{
scanf("%d%d",&n,&m);
memset(adj,-1,sizeof(adj));
Build_Graph_To_Do_it(0,n+m+1);
work(source,target);
printf("%d\n",ans+ans_cost);
return 0;
}
1560:火星藏宝图
sol:DP比较显然。把所有的点按x,y排序。用F[i]表示到I的最大值，F[i]=max(F[j]-dis(j,i))+a[i];但是这样是N^2的。
如何优化呢，考虑到每列只有行数最大的点才能更新。也就是说每一列只有一个点有用，这样只要枚举列就行了，时间复杂度是NM的。
结论证明：如果某一列上最后一个点为last(坐标(x,y),权为a),不是最后一格的某一点是some((x',y),b),当前点是now((vx,vy),c)
那么路径some->now,贡献为 c+b-(vx-x')^2-(vy-y')^2,路径some->last->now 贡献为 a+b+c-(x-x')^2-(vx-x')^2-(vy-y)^2 ;化出来就会发现后面明显小于前面。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 2100000000
using namespace std;
struct Node
{
int x,y,v;
inline void read()
{
scanf("%d%d%d",&x,&y,&v);
}
inline bool operator <(const Node &e)const
{
return (x!=e.x)?(x<e.x):(y<e.y);
}
}a[200005];
int last[1005],val[1005],n,m;
inline int sqr(int x){return x*x;}
inline int dis(const Node &A,const Node &B)
{
return sqr(A.x-B.x)+sqr(A.y-B.y);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)a[i].read();
sort(a+1,a+n+1);
last[1]=1;val[1]=a[1].v;
for(int i=2;i<=n;i++)
{
int x=a[i].x,y=a[i].y,v=a[i].v;
int ret=-inf;
for(int j=1;j<=y;j++)
{
ret=max(ret,val[j]-dis(a[last[j]],a[i]));
}
ret+=v;
if(i==n)
{
printf("%d\n",ret);
return 0;
}
val[y]=ret;
last[y]=i;
}
return 0;
}
1559:密码
sol:AC自动机+状压DP+DFS
首先对于所有串建立AC自动机并在每个节点上维护一个msk[x],01地表示到达这个点会匹配哪些串;然后用F[i][j][mask]表示长度是I时，AC自动机上有J号点，mask表示匹配了那些串的方案数；F[i][j][k]->F[i][tran[j][w]][k|msk[tran[j][w]];
然后是恶心的输出方案：暴力存每个点所有可能的前驱（用链表解决）然后dfs即可（我用了string）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#define CH getchar()
using namespace std;
int cnt=1,tree[105][30];
int L,n,msk[105],q[105],upl;
int dex,tot,fail[105];
int h[26][105][1027];
int vis[26][105][1027];
long long f[26][105][1027];
long long ans=0;
struct Node
{
int node,w,msk,next;
}e[10005];
string rec[55];
void dfs(int len,int node,int msk,string w)
{
if(!len)
{
rec[++tot]=w;
return;
}
for(int i=h[len][node][msk];i;i=e[i].next)
{
dfs(len-1,e[i].node,e[i].msk,char(e[i].w+'a')+w);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("password.in","r",stdin);
freopen("password.out","w",stdout);
#endif
scanf("%d%d",&L,&n);
for(int i=1;i<=n;i++)
{
char ch=CH;
while(ch<'a'||ch>'z')ch=CH;
int p=1;
while(ch>='a'&&ch<='z')
{
if(!tree[p][ch-'a'])tree[p][ch-'a']=(++cnt);
p=tree[p][ch-'a'];
ch=CH;
}
msk[p]=(1<<(i-1));
}
upl=(1<<n)-1;
int l=1,r=0;
for(int i=0;i<26;i++)
{
if(!tree[1][i])tree[1][i]=1;
else
{
fail[tree[1][i]]=1;
q[++r]=tree[1][i];
}
}
for(;l<=r;l++)
{
int u=q[l];
msk[u]|=msk[fail[u]];
for(int i=0;i<26;i++)
if(tree[u][i])
{
int x=tree[u][i];
fail[x]=tree[fail[u]][i];
q[++r]=x;
}else
tree[u][i]=tree[fail[u]][i];
}
f[0][1][0]=1;
for(int i=0;i<L;i++)
for(int j=1;j<=cnt;j++)
for(int k=0;k<=upl;k++)
if(f[i][j][k])
{
for(int l=0;l<26;l++)
{
int nxt=tree[j][l];
f[i+1][nxt][k|msk[nxt]]+=f[i][j][k];
}
}
for(int i=1;i<=cnt;i++)
if(f[L][i][upl])
{
ans+=f[L][i][upl];
vis[L][i][upl]=1;
}
printf("%lld\n",ans);
if(ans<=42)
{
for(int i=L-1;i+1;i--)
for(int j=1;j<=cnt;j++)
for(int k=0;k<=upl;k++)
if(f[i][j][k])
{
for(int l=0;l<26;l++)
{
int nxt=tree[j][l];
int st=k|msk[nxt];
if(vis[i+1][nxt][k|msk[nxt]])
{
vis[i][j][k]=1;
++dex;
e[dex].msk=k;
e[dex].next=h[i+1][nxt][st];
e[dex].w=l;
e[dex].node=j;
h[i+1][nxt][st]=dex;
}
}
}
for(int i=1;i<=cnt;i++)
if(vis[L][i][upl])
dfs(L,i,upl,"");
sort(rec+1,rec+tot+1);
for(int i=1;i<=tot;i++)
cout<<rec[i]<<endl;
}
return 0;
}
1444:有趣的游戏
sol:还是AC自动机，设X[i]表示AC自动机上到达i号点的概率。那么就可以对于每个点列出方程
X[i]=sigma(X[j]*P[j][i])。P[j][i]表示从J转移到I的概率，且每个串的结尾不转移（因为此时游戏已经结束了）。
但是这个方程是不对的。因为他的解是X[1]=X[2]=..=X[cnt]=0;于是我们要用一个方程来替代其中一个方程：即所有串的结尾的概率和为1.这样就可以高斯消元解了。。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define CH getchar()
using namespace std;
int n,l,m,cnt=1;
double rate[15];
int tree[1005][26];
int fail[1005],gra[1005];
int danger[1005];
double a[1005][1005];
double x[1005];
int q[10005];
inline void build()
{
int l=1,r=0;
for(int i=0;i<m;i++)
if(!tree[1][i])
{
tree[1][i]=1;
}else
{
q[++r]=tree[1][i];
fail[tree[1][i]]=1;
}
for(;l<=r;l++)
{
int u=q[l];
for(int i=0;i<m;i++)
if(tree[u][i])
{
q[++r]=tree[u][i];
fail[q[r]]=tree[fail[u]][i];
}else tree[u][i]=tree[fail[u]][i];
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1444.in","r",stdin);
freopen("1444.out","w",stdout);
#endif
scanf("%d%d%d",&n,&l,&m);
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
rate[i]=1.0*u/v;
}
for(int i=1;i<=n;i++)
{
char ch=CH;
while(ch<'A'||ch>'Z')ch=CH;
int p=1;
while(ch>='A'&&ch<='Z')
{
if(!tree[p][ch-'A'])tree[p][ch-'A']=(++cnt);
p=tree[p][ch-'A'];
ch=CH;
}
gra[i]=p;
danger[p]=1;
}
build();
for(int i=1;i<=cnt;i++)
{
a[i][i]=-1;
if(danger[i])continue;
for(int j=0;j<m;j++)
a[tree[i][j]][i]+=rate[j];
}
for(int i=1;i<=cnt;i++)a[1][i]=danger[i];
a[1][cnt+1]=1;
for(int i=1,k=1;i<=cnt;i++)
{
int p=0;
for(int j=k;j<=cnt;j++)
if(a[j][i]!=0)
{
p=j;
break;
}
if(!p)continue;
for(int l=1;l<=cnt+1;l++)swap(a[p][l],a[k][l]);
for(int j=k+1;j<=cnt;j++)
if(a[j][i])
{
double lamda=a[j][i]/a[k][i];
for(int l=1;l<=cnt+1;l++)
a[j][l]-=lamda*a[k][l];
}
++k;
}
x[cnt]=a[cnt][cnt+1]/a[cnt][cnt];
for(int i=cnt-1;i;i--)
{
for(int j=i+1;j<=cnt;j++)
a[i][cnt+1]-=a[i][j]*x[j];
x[i]=a[i][cnt+1]/a[i][i];
}
for(int i=1;i<=n;i++)
if(x[gra[i]]>0&&x[gra[i]]<=1)
{
printf("%.2lf\n",x[gra[i]]);
}else puts("0.00");
return 0;
}
1558:等差数列
sol:线段树
发现等差数列很难搞，考虑把数列差分，开一个辅助数组b[i]=a[i]-a[i+1]，那么等差数列就是b[i]中连续相等的一段。
但是是不是b[st...ed-1]中的连续相等的段数就是原数列的等差数列数目呢？
显然不是，比如以下序列：0 1 2 4 7 10 14 19 24差分后是 1 1 2 3 3 4 5 5 应该有5段。但是实际会分成几段呢？ (0 1 2) (4 7 10) (14 19 24) 3段就可以了！原来中间的“单独的”(与左右差分值都不相同)的数值可以忽视或合并掉！再探究后会发现：对于中间连续的P个单独的数值要P/2个等差数列。对于边缘的P个单独的数值要(P/2)+1个等差数列。另外还要特判区间全都是单独的值的情况。
于是我们再线段树上维护以下7个值:Ld,Rd,lval,rval,ans,lazy,all，分别表示左右边连续的单独值，左边的数值，右边的数值，去掉左右的单独值的答案，加标记和是否全都是单独值。对于A对L..R的操作，我们只需在L-1的地方加上st,R的地方减去(R-L)*step+st;中间的(L..R-1)区间加step即可。
这题最恐怖的地方是up的时候要很多的分类讨论：主要分以下讨论：1.是否全都是单独值；2.左边的rval和右边的lval是否相等。3.是否存在左右两边连续的单独的值。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls(x) ((x)<<1)
#define rs(x) (((x)<<1)|1)
using namespace std;
struct Node
{
int l,r,lval,rval,lazy;
int ld,rd,ans;
int all;
}tree[400005],Ans;
int a[100005],b[100005];
int n;
void up(Node &x,Node &lef,Node &rig)
{
x.lval=lef.lval;x.rval=rig.rval;
x.ld=lef.ld;x.rd=rig.rd;
if(lef.all)
{
if(lef.rval==rig.lval)x.ld--;
else x.ld+=rig.ld;
}
if(rig.all)
{
if(lef.rval==rig.lval)x.rd--;
else x.rd+=lef.rd;
}
x.ans=lef.ans+rig.ans;
if(lef.all&&rig.all&&(lef.rval!=rig.lval))x.all=1;else x.all=0;
if(lef.all)
{
if(lef.rval==rig.lval)
{
if(rig.all)x.ans++;
else if(rig.ld)x.ans+=(rig.ld-1)/2+1;
}
}else
if(lef.rd)
{
if(lef.rval==rig.lval)
{
if(rig.all)x.ans+=(lef.rd-1)/2+1;else
if(rig.ld)x.ans+=(rig.ld-1)/2+(lef.rd-1)/2+1;
else x.ans+=(lef.rd-1)/2;
}else
{
if(!rig.all)x.ans+=(lef.rd+rig.ld)/2;
}
}else
{
if(lef.rval==rig.lval)
{
if(!rig.all)if(rig.ld)x.ans+=(rig.ld-1)/2;else x.ans--;
}else
{
if(!rig.all&&rig.ld)x.ans+=rig.ld/2;
}
}
}
void build(int x,int L,int R)
{
tree[x].l=L;tree[x].r=R;
if(L==R)
{
tree[x].lval=b[L];
tree[x].rval=b[R];
tree[x].ld=tree[x].rd=tree[x].all=1;
return;
}
int mid=(L+R)>>1;
build(ls(x),L,mid);
build(rs(x),mid+1,R);
up(tree[x],tree[ls(x)],tree[rs(x)]);
}
void Add(int x,int val)
{
tree[x].lval+=val;
tree[x].rval+=val;
tree[x].lazy+=val;
}
void down(int x)
{
if(!tree[x].lazy)return;
Add(ls(x),tree[x].lazy);
Add(rs(x),tree[x].lazy);
tree[x].lazy=0;
}
void change(int x,int G,int val)
{
if(tree[x].l==tree[x].r)
{
Add(x,val);
return;
}
down(x);
int mid=(tree[x].l+tree[x].r)>>1;
if(G<=mid)change(x<<1,G,val);
else change((x<<1)|1,G,val);
up(tree[x],tree[x<<1],tree[(x<<1)|1]);
}
void change(int x,int L,int R,int val)
{
if(L<=tree[x].l&&tree[x].r<=R)
{
Add(x,val);
return ;
}
down(x);
int mid=(tree[x].l+tree[x].r)>>1;
if(L<=mid)change(ls(x),L,R,val);
if(mid<R)change(rs(x),L,R,val);
up(tree[x],tree[ls(x)],tree[rs(x)]);
}
Node query(int x,int L,int R)
{
if(L<=tree[x].l&&tree[x].r<=R)return tree[x];
int mid=(tree[x].l+tree[x].r)>>1;
down(x);
Node lef,rig,now;
if(L<=mid)
{
lef=query(ls(x),L,R);
if(R<=mid)return lef;
}
if(mid<R)
{
rig=query(rs(x),L,R);
if(mid<L)return rig;
}
up(now,lef,rig);
return now;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("arithseq.in","r",stdin);
freopen("arithseq.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
build(1,1,n-1);
int Q;
scanf("%d",&Q);
while(Q--)
{
char x=getchar();
while(!(x>='A'&&x<='B'))x=getchar();
if(x=='A')
{
int L,R,st,val;
scanf("%d%d%d%d",&L,&R,&st,&val);
if(L>1)change(1,L-1,st);
if(R<n)change(1,R,-st-val*(R-L));
if(L<R)change(1,L,R-1,val);
}else
{
int L,R;
scanf("%d%d",&L,&R);
if(L==R)
{
puts("1");
continue;
}
Ans=query(1,L,R-1);
if(Ans.all)
{
printf("%d\n",(R-L+2)/2);
}else
{
printf("%d\n",Ans.ans+(Ans.ld+1)/2+(Ans.rd+1)/2);
}
}
}
return 0;
}
下面是坑:
1443:游戏GAME
1561:去括号
2221:面试的考验
但愿能填好坑。。。。
HNOI2014 BZOJ3571-3576简要题解
最近做了HNOI2014 day1和day2的题目，决定学习skydec来一发题解。。。
3571 画框
sol:类似于最小乘积生成树。。，把(Σa,Σb)看做平面上的一个点，易发现答案在所有的点的下凸壳内，由于点比较多，而下凸壳内的点数期望不会很多，于是分治解决。先找到Σa和Σb最小的点。然后找到离这两个点连成的这条直线最远的点。分治解决就行了。。。，计算用KM解决。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#define inf 21000000000000ll
#define maxn 75
using namespace std;
int visx[maxn],visy[maxn];
long long dx[maxn],dy[maxn];
int link[maxn];
long long slack[maxn];
int a[maxn][maxn],b[maxn][maxn];
long long w[maxn][maxn],ans,n,T;
struct sol
{
int a,b;
sol(int T=0,int C=0){a=T;b=C;}
sol operator -(const sol &e)
{
return sol(a-e.a,b-e.b);
}
long long operator *(const sol &e)
{
return 1ll*a*e.b-1ll*b*e.a;
}
};
int dfs(int x)
{
visx[x]=1;
for(int i=1;i<=n;i++)
{
if(visy[i])continue;
long long t=dx[x]+dy[i]-w[x][i];
if(t==0)
{
visy[i]=1;
if(link[i]==-1||dfs(link[i]))
{
link[i]=x;
return 1;
}
}else
{
if(t<slack[i])slack[i]=t;
}
}
return 0;
}
inline sol KM()
{
memset(dy,0,sizeof(dy));
memset(link,-1,sizeof(link));
for(int i=1;i<=n;i++)
{
dx[i]=-inf;
for(int j=1;j<=n;j++)
if(w[i][j]>dx[i])dx[i]=w[i][j];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)slack[j]=inf;
while(1)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(dfs(i))break;
long long d=inf;
for(int j=1;j<=n;j++)
if(!visy[j]&&slack[j]<d)d=slack[j];
for(int j=1;j<=n;j++)
if(visx[j])dx[j]-=d;
for(int j=1;j<=n;j++)
if(visy[j])dy[j]+=d;else slack[j]-=d;
}
}
int reta=0,retb=0;
for(int i=1;i<=n;i++)
if(link[i]!=-1)
reta+=a[link[i]][i],
retb+=b[link[i]][i];
if(1ll*reta*retb<ans)ans=1ll*reta*retb;
return sol(reta,retb);
}
inline void work(sol L,sol R)
{
int ka=R.a-L.a,kb=R.b-L.b;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
w[i][j]=-1ll*a[i][j]*kb+1ll*b[i][j]*ka;
sol p=KM();
if((p-R)*(L-R)<=0)return;
work(L,p);
work(p,R);
}
int main()
{
scanf("%d",&T);
while(T--)
{
ans=inf;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
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=1;j<=n;j++)
w[i][j]=-a[i][j];
sol ulim=KM();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
w[i][j]=-b[i][j];
sol dlim=KM();
work(dlim,ulim);
printf("%lld\n",ans);
}
}
3572：世界树
sol:学习了一种叫做虚树的高大上的东西
。。。虚树就是包含了所有给定点，并收缩了连续的不分叉的边的树的联通子图。在这道题中，我们需要对所有的点构建一颗虚树。至于虚树的构建么，只需要对给出的点按照dfs序的时间戳排序，然后按照笛卡尔树的思想，用单调栈维护树的最右链，并补上需要的lca节点就可以了。
sort(h+1,h+N+1,cmp);
for(int i=1;i<=N;i++)
{
int x=h[i];
if(!top)
{
stack[++top]=x;
Fa[x]=0;
continue;
}
int anc=lca(x,stack[top]);
while(top)
{
if(dep[stack[top]]<=dep[anc])break;
if(dep[stack[top-1]]<=dep[anc])
Fa[stack[top]]=anc;
top--;
}
if(stack[top]!=anc)
{
t[++tot]=anc;
Fa[anc]=stack[top];
stack[++top]=anc;
g[anc]=mp(inf,0);
}
Fa[x]=anc;
stack[++top]=x;
}
然后我们在虚树上做DP。对于虚树上的一个节点维护把这个点控制的点的编号和这个点到它的距离，然后扫描徐虚树上的每一条边并计算边的贡献。如果控制I和他父亲的点相同，那么I和父亲这一段的虚边显然属于哪个把他们控制的点。否则找到断点分别计算贡献即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 300005
#define pii pair<int,int>
#define mp make_pair
#define inf 2100000000
using namespace std;
struct e
{
int u,v,pre;
e(int U=0,int V=0,int P=0){u=U;v=V;pre=P;}
}edge[maxn<<1];int dex;
int n,adj[maxn],fa[maxn][21],cnt=0;
int dep[maxn],sz[maxn],st[maxn];
void dfs(int x)
{
sz[x]=1;st[x]=(++cnt);
for(int i=adj[x];i;i=edge[i].pre)
{
int v=edge[i].v;
if(v==fa[x][0])continue;
fa[v][0]=x;
for(int j=1;j<=19;j++)
fa[v][j]=fa[fa[v][j-1]][j-1];
dep[v]=dep[x]+1;
dfs(v);
sz[x]+=sz[v];
}
}
inline int cmp(const int &e,const int &f)
{
return st[e]<st[f];
}
inline int get(int x,int d)
{
for(int i=19;i+1;i--)
if(dep[fa[x][i]]>=d)x=fa[x][i];
return x;
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=19;i+1;i--)
if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=19;i+1;i--)
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0];
}
pii g[maxn];
int N,mem[maxn],val[maxn],w[maxn];
int stack[maxn],top,Fa[maxn],ans[maxn];
int h[maxn],t[maxn],tot=0;
inline void work()
{
tot=0;
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&h[i]);
mem[i]=h[i];
t[++tot]=h[i];
ans[h[i]]=0;
g[h[i]]=mp(0,h[i]);
}ans[0]=0;top=0;
sort(h+1,h+N+1,cmp);
for(int i=1;i<=N;i++)
{
int x=h[i];
if(!top)
{
stack[++top]=x;
Fa[x]=0;
continue;
}
int anc=lca(x,stack[top]);
while(top)
{
if(dep[stack[top]]<=dep[anc])break;
if(dep[stack[top-1]]<=dep[anc])
Fa[stack[top]]=anc;
top--;
}
if(stack[top]!=anc)
{
t[++tot]=anc;
Fa[anc]=stack[top];
stack[++top]=anc;
g[anc]=mp(inf,0);
}
Fa[x]=anc;
stack[++top]=x;
}
sort(t+1,t+tot+1,cmp);
for(int i=1;i<=tot;i++)
{
int z=t[i];
val[z]=sz[z];
if(i>1)
w[z]=dep[z]-dep[Fa[z]];
}
for(int i=tot;i>1;i--)
{
int x=t[i];
int father=Fa[x];
g[father]=min(g[father],mp(g[x].first+w[x],g[x].second));
}
for(int i=2;i<=tot;i++)
{
int x=t[i],father=Fa[x];
g[x]=min(g[x],mp(g[father].first+w[x],g[father].second));
}
for(int i=1;i<=tot;i++)
{
int x=t[i],father=Fa[x];
if(i==1)
{
ans[g[x].second]+=n-sz[x];
continue;
}
int G=get(x,dep[father]+1);
int sum=sz[G]-sz[x];
val[father]-=sz[G];
if(g[x].second==g[father].second)
{
ans[g[x].second]+=sum;
continue;
}
int mid=dep[x]-((g[father].first+g[x].first+w[x])/2-g[x].first);
if(!((g[father].first+g[x].first+w[x])&1)&&g[father].second<g[x].second)++mid;
int y=sz[get(x,mid)]-sz[x];
ans[g[x].second]+=y;
ans[g[father].second]+=sum-y;
}
for(int i=1;i<=tot;i++)ans[g[t[i]].second]+=val[t[i]];
for(int i=1;i<=N;i++)printf("%d ",ans[mem[i]]);
puts("");
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("3572.in","r",stdin);
freopen("3572.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
edge[++dex]=e(u,v,adj[u]);adj[u]=dex;
edge[++dex]=e(v,u,adj[v]);adj[v]=dex;
}
dep[1]=1;
dfs(1);
int test;
scanf("%d",&test);
while(test--)
work();
return 0;
}
3573：米特运输
sol:语文好题。。。读懂了题目之后发现如果某个点的值被确定，那么整棵树每个点的权值都会被确定。我们只需计算出这个点被确定时根节点的权值应该是多少，排序取众数即可。这个值会很大，需要hash
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod1 10000000000007ll
#define mod2 999999999997ll
#define maxn 500006
#define unsigned long long u64
using namespace std;
struct e
{
int u,v,pre;
e(int U=0,int V=0,int P=0){u=U;v=V;pre=P;}
}edge[maxn];
struct Node
{
long long x,y;
friend bool operator ==(const Node &e,const Node &f)
{
return (e.x==f.x)&&(e.y==f.y);
}
friend bool operator <(const Node &e,const Node &f)
{
return (e.x<f.x)||((e.x==f.x)&&(e.y<f.y));
}
}c[maxn];
int adj[maxn],dex=-1,size[maxn];
int w[maxn],n;
inline void dfs(int x,long long y,long long z)
{
c[x].x=1ll*y*w[x]%mod1;
c[x].y=1ll*z*w[x]%mod2;
long long newy=1ll*y*size[x]%mod1;
long long newz=1ll*z*size[x]%mod2;
for(int i=adj[x];i!=-1;i=edge[i].pre)
{
int v=edge[i].v;
dfs(v,newy,newz);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
memset(adj,-1,sizeof(adj));
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
edge[++dex]=e(u,v,adj[u]); adj[u]=dex;
size[u]++;
}
dfs(1,1ll,1ll);
sort(c+1,c+n+1);
int ans=2100000000;
for(int i=1,k=0;i<=n;i++)
{
if(c[i]==c[i-1]||i==1)k++;else k=1;
if(n-k<ans)ans=n-k;
}
printf("%d\n",ans);
return 0;
}
3574 抄卡组
sol:太弱的我果断去膜拜了ydc的题解。发现只要hash就行了。。。
不难发现，如果每个点都有通配符。那么只要判断是否所有的字符串的前后缀相等就行了。如果某个单词没有通配符，那么我只要判断是否所有串都可以和他匹配。现在问题就变成了判断一个没有通配符的串和一个有通配符的串是否相等，这部分可以用hash解决。先进行第一个位置到第一个通配符的匹配和最后一个通配符到最后一个位置的匹配，再把通配符作为分割点把有通配符的串分多次去匹配就行了。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxE 100005
#define maxn 11000005
#define base 233
using namespace std;
typedef unsigned long long ULL;
int n,nowlen,com,now;
char str[maxn];
int cnt[maxE];
int from[maxE],to[maxE];
ULL sum[maxn],pow[maxn];
int prev[maxE],next[maxE],head,tail;
inline int check(char x)
{
if(x>='0'&&x<='9')return 1;
if(x>='a'&&x<='z')return 1;
if(x=='*')return 1;
return 0;
}
inline ULL gethash(int L,int R)
{
return sum[R]-sum[L-1]*pow[R-L+1];
}
inline void init()
{
int maxlen=0;
com=-1;now=0;
scanf("%d",&n);
for(int k=1;k<=n;k++)
{
cnt[k]=0;
scanf("%s",str+now+1);
from[k]=now+1;
int mark=1;
for(int i=now+1;check(str[i]);i++)
{
str[++now]=str[i];
if(str[now]=='*')mark=0;
else ++cnt[k];
}
if(mark)com=k;
to[k]=now;
maxlen=max(maxlen,now);
}
if(nowlen<maxlen)
for(int i=nowlen+1;i<=maxlen;i++)
pow[i]=pow[i-1]*base;
if(nowlen<maxlen)maxlen=nowlen;
for(int i=1;i<=now;i++)
sum[i]=sum[i-1]*base+str[i];
}
inline int check(int x,int y)
{
int l=from[y],r=to[y];
while(from[x]<=to[x]&&l<=r&&str[from[x]]!='*')
{
if(str[from[x]]!=str[l])return 0;
++from[x];++l;
}
while(from[x]<=to[x]&&l<=r&&str[to[x]]!='*')
{
if(str[to[x]]!=str[r])return 0;
--to[x];--r;
}
while(from[x]<=to[x])
{
while(str[from[x]]=='*'&&from[x]<=to[x])
++from[x];
if(from[x]>to[x])break;
int st=from[x],ed;
for(ed=st;str[ed]!='*';++ed);
ULL val=gethash(st,ed-1);
int len=ed-st;
for(int i=l;i<=r+1;i++)
{
if(i+len-1>r)return 0;
if(gethash(i,i+len-1)==val)
{
l=i+len;
break;
}
}
from[x]=ed;
}
return 1;
}
inline void work()
{
if(com!=-1)
{
ULL G=gethash(from[com],to[com]);
for(int i=1;i<=n;i++)
{
if(cnt[i]>cnt[com])
{
puts("N");
return;
}
if(cnt[i]==to[i]-from[i]+1)
{
if(gethash(from[i],to[i])!=G)
{
puts("N");
return;
}
}else
{
if(!check(i,com))
{
puts("N");
return;
}
}
}
puts("Y");
return;
}else
{
head=1;tail=n;
for(int i=1;i<=n;i++)
{
prev[i]=i-1;
next[i]=i+1;
}
while(head<=tail)
{
char c=0;
for(int i=head;i<=tail;i=next[i])
{
if(str[from[i]]=='*')
{
prev[next[i]]=prev[i];
next[prev[i]]=next[i];
if(i==head)head=next[i];
if(i==tail)tail=prev[i];
}else
if(c==0)c=str[from[i]];
else
if(c!=str[from[i]])
{
puts("N");
return;
}
++from[i];
}
}
head=1;tail=n;
for(int i=1;i<=n;i++)
{
prev[i]=i-1;
next[i]=i+1;
}
while(head<=tail)
{
char c=0;
for(int i=head;i<=tail;i=next[i])
{
if(str[to[i]]=='*')
{
prev[next[i]]=prev[i];
next[prev[i]]=next[i];
if(i==head)head=next[i];
if(i==tail)tail=prev[i];
}else
if(c==0)c=str[to[i]];
else if(c!=str[to[i]])
{
puts("N");
return;
}
--to[i];
}
}
puts("Y");
return;
}
}
int main()
{
int T;
*pow=1;
scanf("%d",&T);
while(T--)
{
init();
work();
}
return 0;
}
3575：道路阻塞
sol:基本的想法是这样的：如果一条在最短路上的边被删掉了，那么要用一些非最短路上的边来替换原来的最短路，一定是
1号点->最短路上的某个点->不在最短路上的一些点->最短路上的某个点->N号点。也就是说，一条边影响的一定是最短路上的某个区间。如果我们知道每条边影响的区间，那么我们就可以把所有边的代价（即新的路径上一定要包含这条边的代价）压到一个堆中。然后取堆的最小值即可。
想法一：一条边的新权值定义为:ds[fs[u[x]]]+w[x]+dt[ft[v[x]]] ds,dt表示1号点到它的最短路和他到N号点的最短路，fs,ft分别表示他在1~N的最短中最早什么时候离开最短路，然后用线段树区间最小维护即可。但是这个想法是错误的，它无法处理二元环的情况。。。
想法二：想法一的错误主要是对于最短路径上的区间求错。假定我们已经知道了经过前K条最短路边的最短路的情况。那么我们要求删掉第(K+1)条边的最短路，我们暴力更新每条边的区间，再把新的边权丢到堆里取最小值即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x7f7f7f7f
#define INF 21000000000000ll
#define ls(x) ((x)<<1)
#define rs(x) (((x)<<1)|1)
using namespace std;
struct E
{
int u,v,w,pre;
E(int U=0,int V=0,int W=0,int P=0){u=U;v=V;pre=P;w=W;}
}edge[200005];
int dis[100005],pos[200005],pe[200005];
int L,fs[100005];
int ft[100005],adj[100005],deg[100005];
int rt[200005],inr[200005],n,m;
int pre[200005],suf[200005];
int p;
struct Node
{
int x,dis;
bool operator <(const Node &e)const
{
return dis>e.dis;
}
}q[500005];
#define CH getchar()
inline void read(int &x)
{
x=0;
char ch=CH;
while(!(ch>='0'&&ch<='9'))ch=CH;
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=CH;
}
}
int queue[1500005],vis[100005];
int occur[100005],id,stack[100005];
int val[100005],top;
inline void spfa(int ds,int S,int lim)
{
memset(vis,0,sizeof(vis));
++id;dis[S]=ds;
int l=1,r=1;
queue[1]=S;vis[S]=1;
for(;l<=r;l++)
{
int u=queue[l];
for(int i=adj[u];i;i=edge[i].pre)
if(!inr[i])
{
int v=edge[i].v;
if(pos[v]>lim)
{
if(occur[v]!=id)
{
occur[v]=id;
stack[++top]=v;
val[v]=dis[u]+edge[i].w+suf[pos[v]];
}else
{
val[v]=min(val[v],dis[u]+edge[i].w+suf[pos[v]]);
}
}else
if(dis[u]+edge[i].w<dis[v])
{
dis[v]=dis[u]+edge[i].w;
if(vis[v])continue;
queue[++r]=v;
vis[v]=1;
}
}
vis[u]=0;
}
for(;top;top--)
{
++p;
q[p].x=stack[top];
q[p].dis=val[stack[top]];
push_heap(q+1,q+p+1);
}
}
inline void work()
{
memset(dis,0x7f,sizeof(dis));
dis[1]=0;
for(int i=1;i<=L;i++)
{
inr[rt[i]]=1;
spfa(pre[i],pe[i],i);
inr[rt[i]]=0;
while(p&&pos[q[1].x]<=i)
{
pop_heap(q+1,q+p+1);
p--;
}
if(!p)puts("-1");else printf("%d\n",q[1].dis);
}
}
int main()
{
read(n);read(m);read(L);
for(int i=1;i<=m;i++)
{
int u,v,w;
read(u);read(v);read(w);
edge[i]=E(u,v,w,adj[u]);
adj[u]=i;
}
pos[1]=1;pe[1]=1;
for(int i=1;i<=L;i++)
{
read(rt[i]);
pe[i+1]=edge[rt[i]].v;
pos[edge[rt[i]].v]=i+1;
}
for(int i=1;i<=L;i++)
pre[i+1]=pre[i]+edge[rt[i]].w;
for(int i=L;i;i--)
suf[i]=suf[i+1]+edge[rt[i]].w;
work();
return 0;
}
3576：江南乐
70分的SG函数是比较显然的
考虑100分算法。发现对于一个数字x floor(x/i)的取值只有sqrt(x)种。于是考虑分块。对于连续的一段floor(x/i)相等的数字只要考虑块内的第一个数和第二个数即可，具体如下：
设这个块中第一个数为first,floor(x/first)的值为P，x%first=Q.那么当分出first堆时，P堆石子的有first-Q个，(P+1)堆的有Q个。当分出(first+K)堆时，(P+1)堆石子的有(Q-P*K)堆，P堆石子的有((first+P)*K-Q)堆由于我们只关心P堆石子个数和(P+1)堆石子个数的奇偶性，那么当K=K0和K=K0-2时的情况是一样的，于是我们只要求K=0和K=1的情况即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int test,sg[100005],F,vis[100005];
int sG[100005];
void SG()
{
for(int i=0;i<F;i++)sg[i]=0;
for(int i=F;i<=100000;i++)
{
for(int l=2,last=2;l<=i;l=last+1)
{
last=i/(i/l);
int len=i/l,rem=i-len*l,REM=l-rem;
vis[sg[(rem&1)*(len+1)]^sg[(REM&1)*len]]=i;
int now=-1;
if(rem>=len&&l+len+1-rem>=0)
{
if(now<0)now=0;
now^=sg[((rem-len)&1)*(len+1)]^sg[((l+len+1-rem)&1)*len];
}
if(now>=0)vis[now]=i;
}
int e=0;
for(;;e++)if(vis[e]!=i)break;
sg[i]=e;
}
}
void Sg()
{
for(int i=0;i<F;i++)sG[i]=0;
memset(vis,0,sizeof(vis));
for(int i=F;i<=1000;i++)
{
for(int j=2;j<=i;j++)
{
int p=i/j;
int q=i%j;
int x=j-q;
int now=0;
if(q&1)now^=sG[p+1];
if(x&1)now^=sG[p];
vis[now]=i;
}
int e=0;
for(;;e++)if(vis[e]^i)break;
sG[i]=e;
}
}
int main()
{
scanf("%d%d",&test,&F);
SG();
while(test--)
{
int N,M;
scanf("%d",&N);
int ans=0;
for(int i=1;i<=N;i++)scanf("%d",&M),ans^=sg[M];
if(ans)printf("1");else printf("0");
if(test)printf(" ");else puts("");
}
return 0;
}
渣代码跑的慢。。。
Butterfly Theme | Design: HRS Hersteller of mobile Hundeschule.