差别

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

--- 2020-2021:teams:wangzai_milk:weekly3 [2020/05/20 22:43]
zars19 [题目]
+++ 2020-2021:teams:wangzai_milk:weekly3 [2020/05/25 10:34] (当前版本)
wzx27
@@ 行 8: / 行 8: @@
 ===== _wzx27 =====
-[[2020-2021:teams:wangzai_milk:_wzx27:Combinatorial mathematics|$P\acute{o}lya定理$]]
+[[2020-2021:teams:wangzai_milk:_wzx27:Combinatorial mathematics:Polya|$P\acute{o}lya定理$]]
 ===== Infinity37 =====
+==== 专题 ====
+[[一些敲简单的博弈论]]
+==== 题目 ====
+[[20200520比赛记录#b-permutation_bo|B-permutation_bo]]
+[[20200520比赛记录#j-rower_bo|J-rower_bo]]
+[[20200520比赛记录#k-teacher_bo|K-teacher_bo]]
+==== 比赛 ====
+暂无
 ===== Zars19 =====
+==== 专题 ====
+这周做做计算几何。
+**[[20200513比赛记录#M-Code]] 判断凸包相交**
 ==== 题目 ====
-[[20200520比赛记录#D-Gambler_bo]]
+**[[20200520比赛记录#D-Gambler_bo]] 模意义下高斯消元**
+**[[http://poj.org/problem?id=1054|POJ1054 The Troublesome Frog]] 奇技淫巧**
+青蛙从田野外跳到田野外的另一端，步长均等，路径是直线，每跳一步都会留下痕迹。给出$N$个痕迹的坐标，问痕迹最多的一条青蛙路径有几个痕迹。$3\leq N\leq 5000,1\leq R,C\leq 5000$
+题解：不知道为什么乱入DP专题，其实是暴力+剪枝优化。先把点按照横坐标排序，这样二重循环只一个方向即可。然后剪枝，先减掉逆方向跳一次跳不出田野的情况，然后减掉沿着个方向一直到跳出去都无法更新当前答案的情况。然后验证。
+<hidden>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<cstdlib>
+#include<cmath>
+#include<algorithm>
+#define LL long long
+using namespace std;
+const int N=5005;
+int read()
+{
+	int x=0,f=1;char c=getchar();
+	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
+	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
+	return x*f;
+}
+int r,c,n,frog[N][N],vis[N][N],res=2;
+struct Node{int x,y;}dot[N];
+bool cmp(Node o1,Node o2){return (o1.x==o2.x)?(o1.y<o2.y):(o1.x<o2.x);}
+bool in(int x,int y){return x>=1&&x<=r&&y>=1&&y<=c;}
+int main()
+{
+	r=read(),c=read(),n=read();
+	for(int i=1;i<=n;i++)
+	{
+		dot[i].x=read(),dot[i].y=read();
+		frog[dot[i].x][dot[i].y]=1;
+	}
+	sort(dot+1,dot+1+n,cmp);
+	for(int i=1;i<=n;i++)
+	{
+		for(int j=i+1;j<=n;j++)
+		{
+			if(vis[dot[j].x][dot[j].y]==i)continue;
+			vis[dot[j].x][dot[j].y]=i;
+			int dx=dot[j].x-dot[i].x,dy=dot[j].y-dot[i].y;
+			int tx=dot[i].x-dx,ty=dot[i].y-dy;
+			if(in(tx,ty))continue;
+			if(!in(dot[i].x+(res-1)*dx,dot[i].y+(res-1)*dy))continue;
+			tx=dot[j].x,ty=dot[j].y;
+			int num=1;
+			while(in(tx,ty))
+			{
+				num++;
+				if(!frog[tx][ty]){num=0;break;}
+				tx+=dx,ty+=dy;
+			}
+			res=max(res,num);
+		}
+	}
+	printf("%d\n",res<3?0:res);
+	return 0;
+}
+</code>
+</hidden>
+\\
+**[[http://poj.org/problem?id=1925|POJ 1925 Spiderman]] DP**
+$n$幢楼，蜘蛛侠在第一幢要荡到最后一幢的横坐标那里，每幢楼可以抽象成$(x_i,0)$到$(x_i,y_i)$的线段，摆荡时绳子不能长于挂绳建筑的高度。问最少摆荡次数。
+题解：坐标范围是$1000000$，可以以此dp，用$f[i]$表示荡到横坐标为$i$的位置最少荡几次。这里要注意到的是由于对称性空中停驻点的纵坐标永远是$y_1$。于是可以扫一遍楼用$f[x[i]-j]$更新$f[x[i]+j]$
+<hidden>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<cstdlib>
+#include<cmath>
+#include<algorithm>
+#define LL long long
+#define INF 0x3f3f3f3f
+using namespace std;
+const int N=5005;
+int read()
+{
+	int x=0,f=1;char c=getchar();
+	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
+	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
+	return x*f;
+}
+LL x[N],y[N];
+int f[1000005];
+LL p(LL a){return a*a;}
+int main()
+{
+	int T=read();
+	while(T--)
+	{
+		memset(f,0x3f,sizeof(f));
+		int n=read();
+		for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();
+		f[x[1]]=0;
+		for(int i=2;i<=n;i++)
+		{
+			int d=sqrt(p(y[i])-p(y[i]-y[1]));
+			for(int j=1;j<=d;j++)
+			{
+				if(x[i]-j<x[1])continue;
+				if(x[i]+j>x[n])f[x[n]]=min(f[x[i]-j]+1,f[x[n]]);
+				else f[x[i]+j]=min(f[x[i]-j]+1,f[x[i]+j]);
+			}
+		}
+		printf("%d\n",f[x[n]]==INF?-1:f[x[n]]);
+	}
+	return 0;
+}
+</code>
+</hidden>
+\\
 ==== 比赛 ====
+暂无
 ===== 本周推荐 =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具