CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:die_java:front_page_summertrain5 [2020/07/24 18:23]
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>
@@ 行 56: / 行 250: @@
 === 题意 ===
+构造一个长度为$n$的数字序列(从数字1开始)，使得满足一定的条件下字典序最小。
+条件：对于每个位置$i$，给定之后的一些位置$p_j$，该位置$p_j$上的数字是$i$位置之后第一次出现
 === 题解 ===
+要字典序最小，当然是使用当前能使用最小的数字
+每次走到一个位置，如果这个位置没有被之前任意一个位置限制，那么就放$1$
+否则，只需要查找最早限制的位置到这个位置之间最小的没被用过的数字
+这个可以用可持久化线段树维护
+建立一个权值线段树，记录每个权值最后出现的位置，维护区间最小值，对于区间$[l,r]$，只需要在$r$位置线段树中通过左右区间最小值判断区间内是否有合法权值，然后尽量往左走即可。
 <hidden 代码>
 <code cpp>
+#include<algorithm>
+#include<iostream>
+#include<cstdlib>
+#include<cstring>
+#include<cstdio>
+#include<vector>
+#include<queue>
+#include<cmath>
+#include<map>
+#include<set>
+#define LL long long int
+#define REP(i,n) for (int i = 1; i <= (n); i++)
+#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
+#define cls(s,v) memset(s,v,sizeof(s))
+#define mp(a,b) make_pair<int,int>(a,b)
+#define cp pair<int,int>
+using namespace std;
+const int maxn = 300005,maxm = 10000005,INF = 0x3f3f3f3f;
+inline int read(){
+	int out = 0,flag = 1; char c = getchar();
+	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
+	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
+	return flag ? out : -out;
+}
+int n,pre[maxn],ans[maxn];
+int mn[maxm],ls[maxm],rs[maxm],rt[maxn],cnt,L,R;
+void modify(int& u,int v,int l,int r,int V){
+	if (!u) {u = ++cnt; ls[u] = ls[v]; rs[u] = rs[v]; mn[u] = mn[v];}
+	if (l == r) {mn[u] = V; return;}
+	int mid = (l + r) >> 1;
+	if (mid >= L) modify(ls[u],ls[v],l,mid,V);
+	else modify(rs[u],rs[v],mid + 1,r,V);
+	mn[u] = min(mn[ls[u]],mn[rs[u]]);
+}
+int query(int u,int l,int r){
+	if (l == r) return l;
+	int mid = (l + r) >> 1;
+	if (mn[ls[u]] < L) return query(ls[u],l,mid);
+	return query(rs[u],mid + 1,r);
+}
+int main(){
+	n = read();
+	for (int i = 1; i <= n; i++){
+		if (!pre[i] || pre[i] == i - 1) ans[i] = 1;
+		else {L = pre[i] + 1; ans[i] = query(rt[i - 1],1,n);}
+		L = ans[i];
+		modify(rt[i],rt[i - 1],1,n,i);
+		int m = read(),u;
+		for (int j = 1; j <= m; j++){
+			u = read();
+			if (!pre[u]) pre[u] = i;
+		}
+	}
+	printf("%d",ans[1]);
+	for (int i = 2; i <= n; i++) printf(" %d",ans[i]); puts("");
+	return 0;
+}
 </code>
@@ 行 71: / 行 333: @@
 === 题意 ===
+有$n$个插排$m$个设备和一个插口，每个插排有各自的插口个数$a_i$，每个设备有各自的性能$b_j$，$b_j$表示该设备正常运行最多能经过的插排个数，求最多能使多少设备正常运行
 === 题解 ===
+容易发现，插排一定是越大越要先用，设备一定是$b_j$越大越先用
+那么就二分使用的设备个数，贪心地分层插入插排。如果当前层有必须使用的设备，就使用之，否则尽量插插排。最后看能否合法插入完。
+<hidden 代码>
+<code cpp>
+#include<algorithm>
+#include<iostream>
+#include<cstdlib>
+#include<cstring>
+#include<cstdio>
+#include<vector>
+#include<queue>
+#include<cmath>
+#include<map>
+#include<set>
+#define LL long long int
+#define REP(i,n) for (int i = 1; i <= (n); i++)
+#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
+#define cls(s,v) memset(s,v,sizeof(s))
+#define mp(a,b) make_pair<int,int>(a,b)
+#define cp pair<int,int>
+using namespace std;
+const int maxn = 200005,maxm = 100005,INF = 0x3f3f3f3f;
+inline int read(){
+	int out = 0,flag = 1; char c = getchar();
+	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
+	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
+	return flag ? out : -out;
+}
+int n,m;
+int A[maxn],B[maxn];
+bool cmp(int a,int b){return a > b;}
+bool check(int M){
+	//cout << M << endl;
+	LL left = 1; int pos = 1,dep = 0;
+	while (true){
+		while (M && left && B[M] == dep) M--,left--;
+		if (!left && M) return false;
+		LL tmp = 0;
+		while (pos <= n && left) left--,tmp += A[pos++];
+		while (M && left) M--,left--;
+		if (!M) return true;
+		left += tmp;
+		dep++;
+		if (pos > n) break;
+	}
+	while (M && left && B[M] >= dep) left--,M--;
+	return M == 0;
+}
+int main(){
+	n = read(); m = read();
+	REP(i,n) A[i] = read();
+	REP(j,m) B[j] = read();
+	sort(A + 1,A + 1 + n,cmp);
+	sort(B + 1,B + 1 + m,cmp);
+	int l = 1,r = m,mid;
+	while (l < r){
+		mid = (l + r + 1) >> 1;
+		if (check(mid)) l = mid;
+		else r = mid - 1;
+	}
+	printf("%d\n",l);
+	return 0;
+}
+</code>
+</hidden>
+===== K.Toll Roads =====
+=== 题意 ===
+填坑
+=== 题解 ===
+填坑
 <hidden 代码>
@@ 行 81: / 行 420: @@
 </code>
 </hidden>
 ===== 训练实况 =====
-第五场：
+开局hxm看**A**，wxg看**G**，wxg开写**G**
-开局hxm看A，wxg看G，wxg开写G
+fyh和hxm讨论**A**无果，fyh继续想**A**，hxm想**J**
-fyh和hxm讨论A无果，fyh继续想A，hxm想J
+:38 wxg过**G**
-:38 wxg过G
+hxm和wxg讨论出**J**做法
-hxm和wxg讨论出J做法
+:07hxm过**J**
-:07hxm过J
+fyh wxg想**H**，fyh开写**H**，中间目测调题，wxg尝试乱搞**A**
-fyh wxg想H，fyh开写H，中间目测调题，wxg尝试乱搞A
+:28 fyh过**H**，hxm想**I**，想出做法
-: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

用户工具

站点工具

页面工具