2016.3.22考试(HNOI难度)

T1 盾盾的打字机

  盾盾有一个非常有意思的打字机,现在盾哥要用这台打字机来打出一段文章。
   由于有了上次的经验,盾盾预先准备好了一段模板A存在了内存中,并以此为基础来打出文章B。盾盾每次操作可以将内存中的某一个字符改成另一个字符,或者在某一个位置插入一个字符,或者删除某一个位置上的字符。另外,为了避免自己预存的模板太腿反而浪费时间,盾哥在所有操作之前会斟酌一下选择留下模板A的某一个最优的子串以保证操作次数尽量少(当然盾盾也可以全保留或一个都不留),这一步不计入操作次数。
     试求盾盾要打出文章B的最少操作次数。
     子串是指母串中连续的一段。

这是一道字符串编辑距离的DP题,但是题目有特殊的要求,字符串可以在编辑之前删除前一段,或者删除后一段,也可以前后都删(留下模板A的某一个最优的子串)。

   列出DP方程:f[i][j]表示a串的i位匹配到了b串的j位

f[i][j]=min{f[i-1][j-1]+(a[i]!=b[j]),f[i-1][j]+1,f[i][j-1]+1)

边界:

    for(int i=0;i<=l1;i++) f[i][0]=0;//这表示了可以删除原串前面的一段(本来编辑距离边界中为f[i][0]=i)
     for(int i=0;i<=l2;i++) f[0][i]=i;

     答案还需要在f[0--l1][l2]中寻找//这表示了可以删除原串之前的一段.

     AC代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
char a[1001],b[1001];
int i,j,k,x,n,m,f[1010][1010],l1,l2,ans;
int main()
{
while (scanf("%s%s",a+1,b+1)!=EOF)
{
l1=strlen(a+1); l2=strlen(b+1);
memset(f,127,sizeof(f));
for(int i=0;i<=l1;i++) f[i][0]=0;
for(int i=0;i<=l2;i++) f[0][i]=i;
for (i=1;i<=l1;i++)
for (j=1;j<=l2;j++)
f[i][j]=min(min(f[i-1][j-1]+(a[i]!=b[j]),f[i-1][j]+1),f[i][j-1]+1);
ans=0x7fffffff;
for (i=1;i<=l1;i++) ans=min(ans,f[i][l2]);
cout<<f[l1][l2]<<endl;
}
return 0;
}

T2 社交网络

   给定一个N个点M条边的无向图,你要连最少的边使得图连通。求方案数mod P的值。

   做这个题目需要知道一个叫做Purfer Sequence数列的神奇东西。在这个网站学习:http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html

   知道了这个性质之后,我们即可以套用这个模板,自然的想到去用并查集维护一下连通块,并且将其标记为它的度数,就可以了。

AC代码:

#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#define pb push_back
#define mp make_pair
#define ST begin()
#define ED end()
#define XX first
#define YY second
#define elif else if
#define foreach(i,x) for (__typeof((x).ST) i=(x).ST;i!=(x).ED;++i)
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vci;
typedef vector<string> vcs;
typedef pair<int,int> PII;

const int N=1000005;

int n,m,mo;
int f[N],g[N];

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

int main()
{
freopen("netrd.in","r",stdin);
freopen("netrd.out","w",stdout);

scanf("%d%d%d",&n,&m,&mo);
for (int i=1;i<=n;++i) f[i]=i;
for (int i=0;i<m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
f[find(x)]=find(y);
}
int ans=1%mo,t=0;
for (int i=1;i<=n;++i) ++g[find(i)],t+=(i==f[i]);
if (t==1)
{
cout<<1%mo<<endl;
return 0;
}
for (int i=1;i<=t-2;++i) ans=1LL*ans*n%mo;
for (int i=1;i<=n;++i) if (g[i])
ans=1LL*ans*g[i]%mo;
cout<<ans<<endl;
return 0;
}

T3 

    求带边权的树上的长度为L~R的中位数最大的路径(有多个中位数时取最大的那个)。路径的长度是指边的条数。

    这个题目我现在还不会写!!!!需要用到点或者边的分治,加上二分。边分治再用上单调队列可以做到O(nLogn^2)的复杂度

  

上一篇:Java--多线程读取网络图片并保存在本地


下一篇:在同一个表中将varchar2类型的数据转存到blob类型的字段中