首页 > 代码库 > CONTEST36 小Z的模拟赛（2）
CONTEST36 小Z的模拟赛（2）
A.小Z的可恶路障
题目：http://www.luogu.org/problem/show?pid=U126
题解：暴力也可以过吧。我为了保险先求了一次最短路，然后枚举这条最短路上的所有边。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxm 10000014 #define eps 1e-1015 #define ll long long16 #define pa pair<int,int>17 #define for0(i,n) for(int i=0;i<=(n);i++)18 #define for1(i,n) for(int i=1;i<=(n);i++)19 #define for2(i,x,y) for(int i=(x);i<=(y);i++)20 #define for3(i,x,y) for(int i=(x);i>=(y);i--)21 #define mod 100000000722 using namespace std;23 inline int read()24 {25 int x=0,f=1;char ch=getchar();26 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}27 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}28 return x*f;29 }30 struct edge{int go,next,w,from;}e[2*maxm];31 int n,m,tot=1,q[maxm],d[maxm],head[maxm],pre[maxm];32 bool v[maxm],can[maxm];33 void ins(int x,int y,int z)34 {35 e[++tot].go=y;e[tot].from=x;e[tot].w=z;e[tot].next=head[x];head[x]=tot;36 }37 void insert(int x,int y,int z)38 {39 ins(x,y,z);ins(y,x,z);40 }41 void spfa()42 {43 for(int i=1;i<=n;++i) d[i]=inf;44 memset(v,0,sizeof(v));45 int l=0,r=1,x,y;q[1]=1;d[1]=0;46 while(l!=r)47 {48 x=q[++l];if(l==maxm-1)l=0;v[x]=0;49 for(int i=head[x];i;i=e[i].next)50 if(d[x]+e[i].w<d[y=e[i].go])51 {52 d[y]=d[x]+e[i].w;53 pre[y]=i;54 if(!v[y]){v[y]=1;q[++r]=y;if(r==maxm-1)r=0;}55 }56 }57 }58 int main()59 {60 freopen("input.txt","r",stdin);61 freopen("output.txt","w",stdout);62 n=read();m=read();int x,y,z;63 for1(i,m)x=read(),y=read(),z=read(),insert(x,y,z);64 spfa();65 for(int i=pre[n];i;i=pre[e[i].from])can[i]=1;66 int ans=0,tmp=d[n];67 for1(i,tot)68 if(can[i])69 {70 e[i].w<<=1;71 e[i^1].w<<=1;72 spfa();73 ans=max(ans,d[n]-tmp);74 e[i].w>>=1;75 e[i^1].w>>=1;76 }77 printf("%d\n",ans);78 return 0;79 }
B.小Z的游戏分队
题目：http://www.luogu.org/problem/show?pid=U127
题解：这题我做的比较满意，说一下我的做法：
首先i 不愿意与 j 在一组，那么我们就merge(i,j+n) merge(j+n,i) （做过食物链、关押罪犯的都知道什么意思吧。。。）
然后执行完之后整个图就分为了好多个块块，有些块之间有边相连，代表这两块一定不能在同一组里。
当然一个块最多只会和一个块相连，否则这两个块一定已经被缩成了一个块
然后怎么做呢？类似与搭建双塔，我们可以用一个二维可行性背包DP，当然应为总人数是确定的，所以可以缩成1维
状态如何转移呢？
1 f[0]=1; 2 for1(i,n) 3 if(s[i]) 4 { 5 if(can[i]) 6 { 7 for3(j,n-s[i],0) 8 if(f[j])f[j+s[i]]=1; 9 }10 else if(b[i])11 {12 for3(j,n,0)13 if(f[j])14 {15 f[j]=0;16 if(j+s[i]<=n)f[j+s[i]]=1;17 if(j+s[b[i]]<=n)f[j+s[b[i]]]=1;18 }19 }20 }
应该很清楚了吧。如果 i 块没有边与其他块相连，那么它可以选择加进 a 组，或者不加进 a 组
否则 它与它相连的块要么一个在 a 组，要么 另一个在 a 组。
最后统计一下就ok了。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 100000 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26 int x=0,f=1;char ch=getchar(); 27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 29 return x*f; 30 } 31 int n,fa[maxn],a[maxn],b[maxn],s[maxn]; 32 bool can[maxn],f[maxn]; 33 inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} 34 inline void merge(int x,int y) 35 { 36 int xx=find(x),yy=find(y); 37 if(xx!=yy)fa[yy]=xx; 38 } 39 int main() 40 { 41 freopen("input.txt","r",stdin); 42 freopen("output.txt","w",stdout); 43 n=read(); 44 for1(i,n*2)fa[i]=i; 45 for1(i,n) 46 { 47 int x=read(); 48 while(x){can[x]=1;x=read();}; 49 for1(j,n) 50 { 51 if(!can[j]&&j!=i) 52 { 53 if(find(j)==find(i)||find(j+n)==find(i+n)) 54 {printf("No solution\n");return 0;} 55 merge(i,j+n); 56 merge(j,i+n); 57 } 58 can[j]=0; 59 } 60 } 61 for1(i,n)if(find(i)==find(i+n)){printf("No solution\n");return 0;} 62 for1(i,n)s[find(i)]++; 63 for1(i,n)can[i]=1; 64 for1(i,n) 65 for1(j,n) 66 if(find(i)==find(j+n)) 67 { 68 int x=find(i),y=find(j); 69 b[min(x,y)]=max(x,y); 70 can[x]=can[y]=0; 71 } 72 f[0]=1; 73 for1(i,n) 74 if(s[i]) 75 { 76 if(can[i]) 77 { 78 for3(j,n-s[i],0) 79 if(f[j])f[j+s[i]]=1; 80 } 81 else if(b[i]) 82 { 83 for3(j,n,0) 84 if(f[j]) 85 { 86 f[j]=0; 87 if(j+s[i]<=n)f[j+s[i]]=1; 88 if(j+s[b[i]]<=n)f[j+s[b[i]]]=1; 89 } 90 } 91 } 92 int ans=n,x=0,y=n; 93 for1(i,n) 94 if(f[i]) 95 { 96 int j=n-i; 97 if(abs(i-j)<ans)ans=abs(i-j),x=i,y=j; 98 } 99 printf("%d %d\n",min(x,y),max(x,y));100 return 0;101 }
C.小Z的神奇数列
题目：http://www.luogu.org/problem/show?pid=U129
题解：SXBK的出题人，硬是把我的线段树卡到和暴力一个分T_T
线段树的做法应该是显然的吧，先将数组排序，然后每次二分到要删的位置，线段树单点修改一下。
不知道出题人的标程是什么神奇的做法。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 1000000+1000014 #define maxm 5000000+1000015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 31784719123 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 int n,m,a[maxn],mx[maxm],mi[maxm],ret[maxm];32 bool b[maxn];33 int find(int x)34 {35 int l=1,r=n,mid;36 while(l<=r)37 {38 mid=(l+r)>>1;39 if(a[mid]>x||(a[mid]==x&&b[mid]))r=mid-1;40 else l=mid+1;41 }42 b[l]=0;43 return l;44 }45 inline void pushup(int k)46 {47 mx[k]=max(mx[k<<1],mx[k<<1|1]);48 mi[k]=min(mi[k<<1],mi[k<<1|1]);49 ll tmp=ret[k<<1];50 tmp=(tmp*ret[k<<1|1])%mod;51 ret[k]=tmp;52 }53 inline void build(int k,int l,int r)54 {55 int mid=(l+r)>>1;56 if(l==r){mx[k]=mi[k]=ret[k]=a[l];return;}57 build(k<<1,l,mid);build(k<<1|1,mid+1,r);58 pushup(k);59 }60 inline void del(int k,int l,int r,int x)61 {62 int mid=(l+r)>>1;63 if(l==r){mx[k]=-inf;mi[k]=inf;ret[k]=1;return;}64 if(x<=mid)del(k<<1,l,mid,x);else del(k<<1|1,mid+1,r,x);65 pushup(k);66 }67 int main()68 {69 freopen("input.txt","r",stdin);70 freopen("output.txt","w",stdout);71 n=read();m=read();72 for1(i,n)a[i]=read();73 sort(a+1,a+n+1);74 for1(i,n)b[i]=1;75 build(1,1,n);76 ll ans,x,y;77 while(m--)78 {79 char ch[2];80 scanf("%s",ch);81 if(ch[0]==‘D‘)del(1,1,n,find(read()));82 else if(ch[0]==‘B‘)printf("%d\n",mx[1]);83 else if(ch[0]==‘S‘)printf("%d\n",mi[1]);84 else if(ch[0]==‘M‘)85 {86 for(ans=1,x=mx[1],y=mi[1];y;y>>=1,x=(x*x)%mod)87 if(y&1)ans=(ans*x)%mod;88 printf("%d\n",ans);89 }90 else printf("%d\n",ret[1]);91 }92 return 0;93 }
D.小Z的迷之阶梯
题目：http://www.luogu.org/problem/show?pid=U130
题解：出题人的声明就是在告诉我们这是道大水题吧。。。
n=200的数据范围很容易让我们想到n^3的算法，枚举上一个点o(n)，枚举从该点向下退的次数o(n)，
状态数o（n），n^3水过。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 10000014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 int n,a[maxn],f[maxn];32 int main()33 {34 freopen("input.txt","r",stdin);35 freopen("output.txt","w",stdout);36 n=read();37 for1(i,n)a[i]=read();38 f[1]=0;39 for2(i,2,n)f[i]=inf;40 for2(i,2,n)41 for1(j,i-1)42 for0(k,j-1)43 if(a[j-k]+(1<<k)>=a[i])44 f[i]=min(f[i],f[j]+k+1);45 printf("%d\n",f[n]==inf?-1:f[n]);46 return 0;47 }
CONTEST36 小Z的模拟赛（2）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。