CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:die_java:front_page_summertrain5 [2020/07/24 18:32]
mychael
+++ 2020-2021:teams:die_java:front_page_summertrain5 [2020/07/24 23:50] (当前版本)
wxg [训练总结]
@@ 行 14: / 行 14: @@
 === 题意 ===
+给了 n 个水杯，可以把水杯装满水或倒完，也可以向另外的杯子倒直至一个杯满或空，问你能否倒出指定体积的水。
 === 题解 ===
+首先最大的被子都装不下就不可能实现。我们把最大的杯子当成容器，然后让别的杯子往里倒水，这就变成了一个模意义下的完全背包问题。
 <hidden 代码>
 <code cpp>
+#include<iostream>
+#include<cstdio>
+#include<algorithm>
+#include<cstring>
+#include<queue>
+#define ll long long
+using namespace std;
+int read()
+{
+	int k=0,f=1;char c=getchar();
+	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
+	for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
+}
+const int N=20055;
+int n,A,a[N],f[N],pre[N],P,pos;
+queue<int> q;
+void print(int x,int cnt)
+{
+	if(!pre[x]) {printf("%d\n",cnt);return;}
+	if(a[pre[x]]<=x)
+	{
+		print(x-a[pre[x]],cnt+2);
+		printf("1 %d\n",pre[x]);
+		printf("3 %d %d\n",pre[x],pos);
+	}
+	else
+	{
+		print(x-a[pre[x]]+P,cnt+4);
+		printf("1 %d\n",pre[x]);
+		printf("3 %d %d\n",pre[x],pos);
+		printf("2 %d\n",pos);
+		printf("3 %d %d\n",pre[x],pos);
+	}
+}
+int main()
+{
+	n=read();A=read();
+	f[0]=1;
+	for(int i=1;i<=n;i++)
+	{
+		a[i]=read();
+		if(a[i]>P)
+			P=a[i],pos=i;
+	}
+	if(A==P)
+	{
+		puts("1");
+		printf("1 %d\n",pos);
+		return 0;
+	}
+	q.push(0);
+	while(!q.empty())
+	{
+		int u=q.front();q.pop();
+		for(int i=1;i<=n;i++)
+			if(!f[(u+a[i])%P])
+				f[(u+a[i])%P]=1,pre[(u+a[i])%P]=i,q.push((u+a[i])%P);
+	}
+	if(!f[A]) puts("-1");
+	else print(A,0);
+	return 0;
+}
 </code>
@@ 行 27: / 行 89: @@
 === 题意 ===
+求区间里一个数，使数的每一位的乘积最大。
 === 题解 ===
+答案一定为最高几位和右区间的相同，后面就是某一位减一之后全是九，枚举这一位出现的位置求出最大乘积的值。
 <hidden 代码>
 <code cpp>
+#include<iostream>
+#include<cstdio>
+#include<algorithm>
+#include<cstring>
+#include<cmath>
+#define ll long long
+using namespace std;
+int read()
+{
+	int k=0,f=1;char c=getchar();
+	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
+	for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
+}
+ll n,m,sum=1,a[20],b[20],ans[105][105],vis[20];
+int main()
+{
+	scanf("%lld%lld",&n,&m);
+	while(n) a[++a[0]]=n%10,n/=10;
+	while(m) b[++b[0]]=m%10,m/=10;
+	int fl=0,fl2=0;
+	for(int i=b[0];i;i--)
+	{
+		if(!fl)
+		{
+			if(a[i]==b[i]) ans[1][i]=a[i];
+			else
+			{
+				fl=1;
+				ans[1][i]=b[i],vis[i]=1;
+			}
+		}
+		else ans[1][i]=b[i],vis[i]=1;
+	}
+	for(int i=b[0];i;i--)
+	{
+		if(vis[i])
+		{
+			if(b[i]=0) break;
+			sum++;
+			for(int j=b[0];j>i;j--)
+				ans[sum][j]=b[j];
+			ans[sum][i]=b[i]-1;
+			for(int j=i-1;j;j--)
+				ans[sum][j]=9;
+		}
+	}
+//	cout<<sum<<endl;
+	ll res=-1,pos;
+	for(int i=1;i<=sum;i++)
+	{
+		int st=b[0];ll as=1;
+		while(ans[i][st]==0) st--;
+		for(;st;st--)
+			as*=ans[i][st];
+		if(as>res) res=as,pos=i;
+	}
+	int st=b[0];
+	while(ans[pos][st]==0) st--;
+	for(;st;st--)
+		printf("%d",ans[pos][st]);
+	return 0;
+}
 </code>
 </hidden>
@@ 行 43: / 行 165: @@
 === 题意 ===
+有$n$组$(a,b)$,$m$组$(c,d)$，对于每一个组$(a_i,b_i)$，选出一个$(c_j,d_j)$,使得$a_i*c_j+b_i*d_j$最小。
 === 题解 ===
+首先按$c_i$升序，$d_i$降序排序，把一些没意义的组删去，接下来推一波式子得到$\frac{a_i}{b_i}>\frac{d_k-d_j}{c_j-c_k}$。这个式子的意思是，如果$j,k$满足这个式子，那么对于第$i$组，选$j$就比$k$更优，于是我们对第二类维护一个下凸壳，按照$\frac{a_i}{b_i}$降序排列，然后一个个扫描，取最优值即可。
 <hidden 代码>
 <code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+#define mem(a,b) memset(a,b,sizeof(a))
+typedef long long LL;
+typedef pair<LL,LL> PII;
+#define X first
+#define Y second
+inline int read()
+{
+	int x=0,f=1;char c=getchar();
+	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
+	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
+	return x*f;
+}
+const int maxn=500010;
+struct Item
+{
+	LL x,y;
+	int id;
+	Item() {}
+	Item(LL _1,LL _2,int _3):x(_1),y(_2),id(_3) {}
+}A[maxn],D[maxn],B[maxn],C[maxn],sta[maxn];
+int n,m,M,len,a,b,top;
+LL ans[maxn];
+bool cmp1(Item a,Item b)
+{
+	return (double)(a.x)/(double)(a.y)>(double)(b.x)/(double)(b.y);
+}
+bool cmp2(Item a,Item b)
+{
+	return b.x==a.x ? a.y<b.y : a.x<b.x;
+}
+double K(Item i,Item j){return (double)(i.y-j.y)/(double)(j.x-i.x);}//保证i<j xi<xj yi>yj
+int main()
+{
+	n=read();
+	for(int i=1;i<=n;i++)a=read(),b=read(),A[i]=Item(a,b,i);
+	sort(A+1,A+n+1,cmp1);
+	m=read();
+	for(int i=1;i<=m;i++)a=read(),b=read(),B[i]=Item(a,b,i);
+	sort(B+1,B+m+1,cmp2);
+	for(int i=1;i<=m;)
+	{
+		C[++M]=B[i];
+		while(i<=m && B[i].y>=C[M].y)i++;
+	}
+	if(M==1)
+	{
+		for(int i=1;i<=n;i++)ans[A[i].id]=A[i].x*C[1].x+A[i].y*C[1].y;
+	}
+	else
+	{
+		sta[++top]=C[1];
+		sta[++top]=C[2];
+		for(int i=3;i<=M;i++)
+		{
+			while(top>1 && K(sta[top-1],sta[top])<K(sta[top-1],C[i]))top--;
+			sta[++top]=C[i];
+		}
+		int now=1;
+		for(int i=1;i<=n;i++)
+		{
+			while(now<top && (double)(A[i].x)/(double)(A[i].y)<K(sta[now],sta[now+1]))now++;
+			ans[A[i].id]=A[i].x*sta[now].x+A[i].y*sta[now].y;
+		}
+	}
+	for(int i=1;i<n;i++)printf("%lld ",ans[i]);
+	printf("%lld\n",ans[n]);
+	return 0;
+}
 </code>
 </hidden>
@@ 行 211: / 行 405: @@
 </code>
 </hidden>
-===== 训练实况 =====
-第五场：
-开局hxm看A，wxg看G，wxg开写G
+===== K.Toll Roads =====
-fyh和hxm讨论A无果，fyh继续想A，hxm想J
+=== 题意 ===
-:38 wxg过G
+填坑
-hxm和wxg讨论出J做法
+=== 题解 ===
+填坑
-:07hxm过J
+<hidden 代码>
+<code cpp>
-fyh wxg想H，fyh开写H，中间目测调题，wxg尝试乱搞A
+</code>
+</hidden>
-:28 fyh过H，hxm想I，想出做法
+===== 训练实况 =====
+开局hxm看**A**，wxg看**G**，wxg开写**G**
+fyh和hxm讨论**A**无果，fyh继续想**A**，hxm想**J**
+:38 wxg过**G**
+hxm和wxg讨论出**J**做法
+:07hxm过**J**
+fyh wxg想**H**，fyh开写**H**，中间目测调题，wxg尝试乱搞**A**
+:28 fyh过**H**，hxm想**I**，想出做法
 hxm用错数据结构，和wxg讨论后修改
-wxg wa A 放弃A
+wxg wa **A** 放弃**A**
-:06 hxm过I，wxg想出F，fyh尝试D
+:06 hxm过**I**，wxg想出**F**，fyh尝试**D**
-:40 wxg过F
+:40 wxg过**F**
 =====训练总结=====
+fyh:本次比赛我们队的罚时得到了很大的进步，大部分题都能1A,我在推H的时候不等号忘记变号，导致输不对答案，肉眼调了一小会，耽误了一点点时间，算是一个易错点。
+\\ hxm:
+\\ wxg:G题写的有点慢，A的乱搞没有搞过去。

CVBB ACM Team

用户工具

站点工具

页面工具