第一題： 盾盾的打字機?(drdrd)?
【題目描述】?
盾盾有一個非常有意思的打字機，現在盾哥要用這臺打字機來打出一段文章。?
由于有了上次的經驗，盾盾預先準備好了一段模板 A 存在了內存中，并以此為基礎來?
打出文章 B。盾盾每次操作可以將內存中的某一個字符改成另一個字符，或者在某一個位置?
插入一個字符，或者刪除某一個位置上的字符。另外，為了避免自己預存的模板太腿反而浪?
費時間，盾哥在所有操作之前會斟酌一下選擇留下模板 A 的某一個最優的子串以保證操作?
次數盡量少（當然盾盾也可以全保留或一個都不留），這一步不計入操作次數。?
試求盾盾要打出文章 B 的最少操作次數。?
子串是指母串中連續的一段。?
【輸入數據】?
輸入包含多組數據。?
對于每組數據，兩行，分別表示 A 和 B。?
【輸出數據】?
每組數據一行，一個數，表示最少操作次數。?
【輸入樣例】?
aaaaa?
aaa?
abcabc?
bcd?
abcdef?
klmnopq?
【輸出樣例】?
0 1 7?
【 數據約定】?
30% ： |A|, |B| <= 10?
100% ： 1 <= |A|, |B| <= 1000, 數據組數 <= 10, 輸入的串中只包含小寫字?
母?

?

用狀態 f[i][j]表示第一個串到了第 i 位，第二個串到了第 j 為的最優值，轉移就枚舉下一
位怎么做。
注意邊界條件。

?

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long LL;

#define INF 0x7fffffff
#define MAXN 1010

int dp[MAXN][MAXN];

char a[MAXN],b[MAXN];

int lena,lenb;

int check(int x,int y)
{
if (x!=y)
return 1;
return 0;
}

bool work()
{
for (int i=0;i<=lena-lenb;i++)
if (strncmp(a+i,b,lenb)==0)
return true;
return false;
}

int main()
{
freopen("drdrd.in","r",stdin);freopen("drdrd.out","w",stdout);
while (scanf("%s",a)!=EOF)
{
memset(dp,127/3,sizeof(dp));
scanf("%s",b);
lena=strlen(a);
lenb=strlen(b);
if (lena>=lenb && work())
{
printf("0\n");
continue;
}
for (int i=0;i<=lena;i++)
{
dp[i][0]=0;
for (int j=0;j<=lenb;j++)
{
dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+check(a[i],b[j]));
dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1);
dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1);
}
}
int ans=INF;
for (int i=0;i<=lena;i++)
ans=min(ans,dp[i][lenb]);
printf("%d\n",ans);
}
return 0;
}

第二題：社交網絡(netrd)
【題目描述】
給定一個 N 個點 M 條邊的無向圖，你要連最少的邊使得圖連通。求方案數 mod P 的值。
【輸入數據】
第一行三個數， N,M,P。
接下來 M 行，每行兩個數 x,y，表示 x 和 y 之間有一條邊。
【輸出數據】
僅一行， 一個數，即方案數。
【輸入樣例】
4 1 1000000000
1 4
【輸出樣例】
8
【樣例解釋】
{(1, 2), (1, 3)} {(1, 2), (2, 3)} {(1, 2), (4, 3)} {(1, 3), (3, 2)}
{(1, 3), (4, 2)} {(4, 2), (2, 3)} {(4, 2), (4, 3)} {(4, 3), (3, 2)}
【數據約定】
30% : N <= 10
另 20% ： M = 0
100 : N <= 10 ^ 5, M <= 10 ^ 5, 1 <= P <= 10 ^ 9

?

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long LL;

#define N 100010

LL n,m,p;
LL ans;

int t;
int x,y;
int f[N],g[N];

int find(int x)
{
return f[x]==x ? x : f[x]=find(f[x]);
}

int PowerMod(int a, int b, int c)
{

LL ans=1;
LL k=a%c;
while (b)
{
if (b&1)
ans=1LL*ans*k%c;
b>>=1;
k=1LL*k*k%c;
}
return ans;
}

int main()
{
freopen("netrd.in","r",stdin);freopen("netrd.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&p);
if (!m)
{
LL ans=PowerMod(n,n-2,p);
printf("%lld\n",ans);
return 0;
}
for (int i=1;i<=n;i++)
f[i]=i;
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
f[find(x)]=find(y);
}
for (int i=1;i<=n;i++)
g[find(i)]++,t+=(f[i]==i);
if (t==1)
{
printf("%d",1%p);
return 0;
}
LL ans=PowerMod(n,t-2,p);
for (int i=1;i<=n;i++)
if (g[i])
ans=1LL*ans*g[i]%p;
printf("%lld",ans);
return 0;
}

樹的 prufer 編碼
如果把一開始就連在一起的點縮在一起，我們相當于要求一個帶“點權”的圖的生成樹
方案數。
用樹的 prufer 編碼來考慮。在 prufer 序列中，每個點的度數就是它在其中的出現次數+1，
而每個點的每個度數都可以分配給他真正包含的點中的任意一個，用 a 表示包含的點數，
d 表示度數，所以最后的方案數就是π (a[i] ^ d[i])，在序列中每次考慮往后加一個數，都
有∑d[i] = n 種選擇，所以最后的答案就是 n ^ (n-2) * π (a[i])。

?

?

轉載于:https://www.cnblogs.com/yangjiyuan/p/5320194.html

總結

以上是生活随笔為你收集整理的HNOI模拟 Day3.22的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。