差别

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

--- 2020-2021:teams:no_morning_training:weekly:week8 [2020/07/24 13:48]
nomansland [王瑞琦]
+++ 2020-2021:teams:no_morning_training:weekly:week8 [2020/07/29 09:01] (当前版本)
shaco
@@ 行 10: / 行 10: @@
 无
 ===== 冯宇扬 =====
-===比赛===
+没有
-===专题===
 ===== 常程 =====
 ===比赛===
@@ 行 21: / 行 20: @@
 ===== 本周推荐 =====
 ==== 王瑞琦 ====
+翻出来以前写的一道模拟退火入门题，温习了一下。
+===来源===
+洛谷P1337：[[https://www.luogu.com.cn/problem/P1337|平衡点]]
+===标签===
+模拟退火，数学
+===题意===
+给出桌面上n个洞的坐标，n个重物系绳分别穿过n个洞，求绳结最后的平衡位置。
+===题解===
+绳结平衡，即所受n个力达到平衡。\\
+而当绳结处于一个非平衡点时，其所受合力方向必指向最后的平衡点，因此我们将绳结向该方向移动一段距离。\\
+循环上述过程，每次移动的距离逐渐减少，最终绳结将“逼近”最后的平衡点。\\
+<hidden 代码>
+<code c>
+#include <stdio.h>
+#include <math.h>
+#define abs(x) ((x) >= 0 ? (x) : (-(x)))
+#define true 1
+#define false 0
+int main()
+{
+	int a[34][1001]={0};
+	int n;
+	int XF=true, YF=true;
+	scanf("%d",&n);
+	for (int i=1;i<=n;i++)
+		scanf("%d%d%d",&a[1][i],&a[2][i],&a[3][i]);
+	double t=5000,tx,ty;
+	double x=1,y=1;
+	while (true)
+	{
+		tx=x;
+		ty=y;
+		double lx=0,ly=0,dist;
+		for (int i=1;i<=n;i++)
+		{
+			dist=sqrt((a[2][i]-y)*(a[2][i]-y)+(a[1][i]-x)*(a[1][i]-x));
+			if (dist==0) continue;
+			lx=lx+a[3][i]/dist*(a[1][i]-x);
+			ly=ly+a[3][i]/dist*(a[2][i]-y);
+		}
+		dist=sqrt(lx*lx+ly*ly);
+		x=x+t/dist*lx;
+		y=y+t/dist*ly;
+		if (abs(tx-x)<0.00001&&abs( ty - y)<0.00001) break;
+		if ((XF!=(x>tx))||(YF!=(y>ty))){
+			XF=1-(x>tx);
+			YF=1-(y>ty);
+			t=t*0.9;
+		}
+	}
+	printf("%.3lf %.3lf",x,y);
+	getchar();
+	getchar();
+	return 0;
+}
+</code>
+</hidden>
+===comment===
+比较入门的一道题，复习的时候却调了好久=。=\\
+关于模拟退火还在学习当中...
 ==== 冯宇扬 ====
+本周完全摸鱼
 ==== 常程 ====
-推荐一道AC自动机的题吧
+=== 来源 ===
-[[2020-2021:teams:no_morning_training:shaco:知识点:数据结构:ac自动机|文本生成器]]
+[[https://www.luogu.com.cn/problem/P4052|p4052 文本生成器]]
+=== 标签 ===
+AC自动机 DP
+=== 题意 ===
+给出一些模式串和一个长度，求出给定长度下至少包含一个给出的模式串的文本串数量。
+=== 思路 ===
+这道题可以通过计算不包含任何一个模式串的文本串数量间接求解。\\
+主要是在Trie树上运用dp。
+在这里我想做题的人需要对文本串在Trie树上匹配的过程有一个直观而清晰的认识——匹配到当前的树上的位置代表一切其fail一串上的均可以匹配，但以该点为fail的位置不能被匹配。\\
+运用dp，dp[i][j]表示 长度为i、结点序号为j的位置不包含任何一个模式串的文本串数量。\\
+状态转移方程为：dp[i+1][son[j][k]]+=dp[i][j] (!flag[son[j][k])\\
+这里面需要注意的是，如果一个结点是一个模式串的末尾，那么以其为fail关系的子孙的结点都要标记flag，原因如上。
+<hidden code>
+<code cpp>
+#include<cstdio>
+#include<queue>
+using namespace std;
+int n,m,tot=1,dp[6005][105],mod=10007;
+char s[105];
+struct unit{int s[27],fail,flag;}T[6005];
+void Insert()
+{
+    int root=1,id;
+    for(int i=0;s[i];i++)
+    {
+        id=s[i]-65;
+        if(!T[root].s[id])
+            T[root].s[id]=++tot;
+        root=T[root].s[id];
+    }
+    T[root].flag=1;
+}
+void get_fail()
+{
+    for(int i=0;i<26;i++)
+        T[0].s[i]=1;
+    T[1].fail=0;
+    queue<int>q;
+    q.push(1);
+    int m=1,head;
+    while(m--)
+    {
+        head=q.front();
+        q.pop();
+        for(int i=0,v,fafail;i<26;i++)
+        {
+            v=T[head].s[i];
+            fafail=T[head].fail;
+            if(!v) T[head].s[i]=T[fafail].s[i];
+            else
+            {
+                T[v].fail=T[fafail].s[i];
+                T[v].flag|=T[T[v].fail].flag;
+                q.push(v);
+                m++;
+            }
+        }
+    }
+}
+int main()
+{
+    scanf("%d%d",&n,&m);
+    for(int i=1;i<=n;i++)
+    {
+        scanf("%s",s);
+        Insert();
+    }
+    get_fail();
+    dp[1][0]=1;
+    for(int i=1;i<=m;i++)
+        for(int j=1;j<=tot;j++)
+            for(int k=0;k<26;k++)
+                if(!T[T[j].s[k]].flag)
+                    dp[T[j].s[k]][i]=(dp[T[j].s[k]][i]+dp[j][i-1])%mod;
+    int ans=1;
+    for(int i=26,j=m;j;j>>=1,i=(i*i)%mod)
+        if(j&1)
+            ans=(ans*i)%mod;
+    for(int i=1;i<=tot;i++)
+        ans=(ans-dp[i][m]+mod)%mod;
+    printf("%d",ans);
+    return 0;
+}
+</code>
+</hidden>
+=== comment ===
+还算是有点复杂的，当时调了一段时间。

CVBB ACM Team

用户工具

站点工具

差别

页面工具