差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:die_java:front_page_summertrain2 [2020/07/17 17:23]
mychael
+++ 2020-2021:teams:die_java:front_page_summertrain2 [2020/10/17 23:02] (当前版本)
fyhssgss
@@ 行 11: / 行 11: @@
 ===== 题解 =====
-===== 题目名字 =====
+===== B.Boundary =====
 === 题意 ===
+给了n个点，画一个过原点的圆，问最多能有多少个点在圆上。
 === 题解 ===
+我们固定原点和一个点，枚举剩下的点，求出这三个点的圆心，答案即为重合最多的圆心数加一。题目有点卡常，用分数计算会超时，无奈只能用double记录点玄学通过。
+<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;
+typedef pair<double,double> PDD;
+#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 N=2000055;
+const int maxn=2010;
+PII A[maxn];
+LL aa[N];
+int n,ans,sum;
+map<PDD,int> mp;
+LL gcd(LL a,LL b){return b==0 ? a : gcd(b,a%b);}
+int main()
+{
+    n=read();
+    for(int i=1;i<=n;i++)scanf("%lld%lld",&A[i].X,&A[i].Y);
+    for(int i=1;i<n;i++)
+    {
+        mp.clear();
+        for(int j=i+1;j<=n;j++)
+        {
+            LL a=A[i].X,b=A[i].Y,c=A[j].X,d=A[j].Y;
+            if(b*c-a*d==0) continue;
+            LL p=a*a+b*b,q=c*c+d*d,r=b*c-a*d;
+            LL x1=q*b-p*d,x2=r;
+            LL y1=p*c-q*a,y2=r;
+//          LL xx=gcd(abs(x1),abs(x2)),yy=gcd(abs(y1),abs(y2));
+            double xx=1.*x1/x2;
+            double yy=1.*y1/y2;
+/*            if(x1<0)   分数做法
+            {
+                x1*=-1;x2*=-1;
+            }
+            else if(x1==0)
+            {
+                x2=1;xx=1;
+            }
+            if(y1<0)
+            {
+                y1*=-1;y2*=-1;
+            }
+            else if(y1==0)
+            {
+                y2=1;yy=1;
+            }
+            x1/=xx;x2/=xx;y1/=yy;y2/=yy;
+            LL hs2=0;
+            hs2=hs2*998244353+x1;hs2=hs2*998244353+x2;
+            hs2=hs2*998244353+y1;hs2=hs2*998244353+y2;
+//          printf("%d %d %lld %lld %lld %lld\n",i,j,x1,x2,y1,y2);
+//          aa[++sum]=hs2;*/
+            ans=max(ans,++mp[PDD(xx,yy)]);
+        }
+    }
+/*  sort(aa+1,aa+1+sum);
+    for(int i=1;i<=sum;i++)
+    {
+        int tot=1;
+        for(int j=i+1;j<=sum;j++)
+        {
+            if(aa[j]==aa[i]) tot++;
+            else break;
+        }
+        ans=max(ans,tot);
+        i+=tot-1;
+    }*/
+     printf("%d\n",++ans);
+    return 0;
+}
 </code>
+</hidden>
+===== C.Cover the Tree =====
+=== 题意 ===
+用尽量少的路径覆盖一棵树的所有边
+=== 题解 ===
+solved by hxm
+路径显然最优时从一个叶子出发，到另一个叶子结束。记叶子节点个数为$m$，那么答案应该就是$\lceil \frac{m}{2} \rceil$
+问题是如何找到一组解
+选一个点作为根节点，如果能将不同子树里的叶子匹配，就能做到完全覆盖。那么只需要每次选剩余叶子最多的两个子树匹配。
+容易发现，这样操作，只需要最大的子树里叶子节点个数不超过总个数的一半。
+只需要随意选一个点，如果不满足条件，就往那个叶子最多的子树走，最后一定能走到一个合法的点。
+<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 = 400005,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,h[maxn],ne,de[maxn];
+struct EDGE{
+	int to,nxt;
+}ed[maxm];
+void build(int u,int v){
+	ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;
+	ed[++ne] = (EDGE){u,h[v]}; h[v] = ne;
+	de[u]++; de[v]++;
+}
+int siz[maxn],rt,tot;
+void dfs1(int u,int ff){
+	if (de[u] == 1) siz[u] = 1;
+	else {
+		Redge(u) if ((to = ed[k].to) != ff){
+			dfs1(to,u);
+			siz[u] += siz[to];
+		}
+	}
+}
+void dfs2(int u,int ff){
+	int flag = 1;
+	Redge(u) if ((to = ed[k].to) != ff){
+		if (siz[to] * 2 > tot){
+			flag = 0;
+			dfs2(to,u);
+		}
+		if (!flag) break;
+	}
+	if (flag) rt = u;
+}
+int m,pos[maxn],len[maxn];
+vector<int> leaf[maxn];
+struct node{
+	int i;
+};
+inline bool operator <(const node& a,const node& b){
+	return len[a.i] - pos[a.i] < len[b.i] - pos[b.i];
+}
+priority_queue<node> q;
+void dfs3(int u,int ff){
+	if (de[u] == 1) leaf[m].push_back(u),len[m]++;
+	else {
+		Redge(u) if ((to = ed[k].to) != ff){
+			dfs3(to,u);
+		}
+	}
+}
+int main(){
+	n = read();
+	if (n == 1){printf("1\n1 1\n"); return 0;}
+	if (n == 2){printf("1\n1 2\n"); return 0;}
+	for (int i = 1; i < n; i++) build(read(),read());
+	for (int i = 1; i <= n; i++){
+		if (de[i] == 1) tot++;
+		else rt = i;
+	}
+	dfs1(rt,0);
+	dfs2(rt,0);
+	//cout << rt << endl;
+	Redge(rt){
+		m++;
+		dfs3(to = ed[k].to,rt);
+	}
+	//REP(i,m) cout << len[i] << endl;
+	REP(i,m) q.push((node){i});
+	printf("%d\n",(tot + 1) / 2);
+	int cnt = 0,a,b;
+	while (tot - cnt > 1){
+		a = q.top().i; q.pop();
+		b = q.top().i; q.pop();
+		printf("%d %d\n",leaf[a][pos[a]++],leaf[b][pos[b]++]);
+		if (pos[a] < len[a]) q.push((node){a});
+		if (pos[b] < len[b]) q.push((node){b});
+		cnt += 2;
+	}
+	if (tot & 1){
+		a = q.top().i;
+		printf("%d %d\n",leaf[a][pos[a]++],rt);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== D.Duration =====
+solved by hxm
+水题
+===== E.Exclusive OR =====
+=== 题意 ===
+给了 $n$ 个数，让你求 $1 \le i \le n$ ,选 $i$ 个数（可以选相同的数）异或和的最大值。
+=== 题解 ===
+发现 $i$ 在19之后答案和 $i-2$ 一致，原理参考线性基。所以我们只需求前19个的答案，用FWT即可完成。
+<hidden 代码>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<algorithm>
+#include<cstring>
+#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 M=1050000;
+int n,N,a[M],b[M],c[M],ans[M];
+void FWT(int *a,int opt)
+{
+    for(int i=1;i<N;i<<=1)
+        for(int p=i<<1,j=0;j<N;j+=p)
+            for(int k=0;k<i;++k)
+            {
+                int X=a[j+k],Y=a[i+j+k];
+                a[j+k]=(X+Y);a[i+j+k]=(X-Y);
+                if(opt==-1)a[j+k]=1ll*a[j+k]/2,a[i+j+k]=1ll*a[i+j+k]/2;
+            }
+}
+int main()
+{
+    n=read();int mx=0,x;
+    for(int i=1;i<=n;i++)
+    {
+        x=read();
+        a[x]=1;b[x]=1;mx=max(mx,x);
+    }
+    for(N=1;N<=mx;N<<=1);
+    ans[1]=mx;
+    FWT(b,1);
+    for(int i=2;i<=min(25,n);i++)
+    {
+        for(int j=0;j<N;j++)
+            if(a[j]) a[j]=1;
+        FWT(a,1);
+        for(int j=0;j<N;j++)
+            a[j]=a[j]*b[j];
+        FWT(a,-1);
+        for(int j=N-1;j>=0;j--)
+        {
+            if(a[j]) {ans[i]=j;break;}
+        }
+//      for(int j=0;j<N;j++)
+//          cout<<a[j]<<" ";
+//      cout<<endl;
+    }
+    for(int i=1;i<=n;i++)
+    {
+        if(i>25)
+        {
+            if(i&1) printf("%d ",ans[25]);
+            else printf("%d ",ans[24]);
+        }
+        else printf("%d ",ans[i]);
+    }
+    puts("");
+    return 0;
+}
+</code>
+</hidden>
+===== F.Fake Maxpooling =====
+=== 题意 ===
+一个$n \times m$的网格，每个格子$(x,y)$里写着$lcm(x,y)$。
+现在用一个$k \times k$的框去选中一些格子，得到其中最大值。
+求所有选取方法最大值的总和。
+=== 题解 ===
+solved by hxm
+暴力$O(nmlogn)$求出$lcm$，然后竖着用$m$个单调队列维护最大值，然后再用一个单调队列维护单调队列的最大值，即可求出当前区域的最大值。
+<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 = 5005,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 gcd(int a,int b) {
+	return !b ? a : gcd(b,a % b);
+}
+int A[maxn][maxn],n,m,K;
+int Q[maxn][maxn],H[maxn],T[maxn];
+int q[maxn],pos[maxn],head,tail;
+int main(){
+	n = read(); m = read(); K = read();
+	REP(i,n) REP(j,m) A[i][j] = i * j / gcd(i,j);
+	REP(i,m) H[i] = 1;
+	LL ans = 0;
+	for (int i = 1; i <= n; i++){
+		for (int j = 1; j <= m; j++){
+			while (H[j] <= T[j] && i - Q[j][H[j]] >= K) H[j]++;
+			while (T[j] >= H[j] && A[i][j] >= A[Q[j][T[j]]][j]) T[j]--;
+			Q[j][++T[j]] = i;
+		}
+		if (i >= K){
+			head = 1; tail = 0;
+			for (int j = 1; j <= m; j++){
+				while (head <= tail && j - pos[head] >= K) head++;
+				while (head <= tail && A[Q[j][H[j]]][j] >= q[tail]) tail--;
+				q[++tail] = A[Q[j][H[j]]][j];
+				pos[tail] = j;
+				if (j >= K) ans += q[head];
+			}
+		}
+	}
+	printf("%lld\n",ans);
+	return 0;
+}
+</code>
+</hidden>
 ===== H.Happy Triangle =====
@@ 行 167: / 行 540: @@
 </code>
 </hidden>
-===== 题目名字 =====
-=== 题意 ===
-=== 题解 ===
-<code cpp>
-</code>
 ===== J.Just Shuffle =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具