CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:die_java:front_page_summertrain5 [2020/07/24 20:36]
fyhssgss [H.Biathlon 2.0]
+++ 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 代码>
@@ 行 280: / 行 405: @@
 </code>
 </hidden>
+===== K.Toll Roads =====
+=== 题意 ===
+填坑
+=== 题解 ===
+填坑
+<hidden 代码>
+<code cpp>
+</code>
+</hidden>
 ===== 训练实况 =====
 开局hxm看**A**，wxg看**G**，wxg开写**G**
@@ 行 303: / 行 444: @@
 :40 wxg过**F**
 =====训练总结=====
+fyh:本次比赛我们队的罚时得到了很大的进步，大部分题都能1A,我在推H的时候不等号忘记变号，导致输不对答案，肉眼调了一小会，耽误了一点点时间，算是一个易错点。
+\\ hxm:
+\\ wxg:G题写的有点慢，A的乱搞没有搞过去。

CVBB ACM Team

用户工具

站点工具

页面工具