1.盾盾的打字机
差点以为是阿狸的打字机
然后这就是个弱dp
好像我的做法和一般人不太一样。。好像也麻烦些（然后就打萎了）
dp[i][j]表示A中第i个字符匹配到了B的第j个的最小值（此时a[i]==b[j]）
mm[i][j]表示使dp[k][j]+i-k(k<=i)最小的k
那么dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+(a[i])!=b[j]),dp[mm[i-1][j-1]][j-1]+i-mm[i-1][j-1]-1+(a[i]!=b[j]))
依次为插入、直接走/修改、往回退了再走/修改
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
// <drdrd.cpp> - 03/22/16 08:16:44 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=1002; const int INF=1000000000; char a[MAXN],b[MAXN]; int dp[MAXN][MAXN]; //A中第i个字符匹配到了B的第j个的最小值 int mm[MAXN][MAXN]; //A中前i个字符匹配到了B的第j个的最小位 int main(){ freopen("drdrd.in","r",stdin); freopen("drdrd.out","w",stdout); while(~scanf("%s%s",a+1,b+1)){ int la=strlen(a+1),lb=strlen(b+1); for(int i=0;i<=la;i++) for(int j=0;j<=lb;j++)dp[i][j]=INF; for(int i=0;i<=la;i++)dp[i][0]=0; int ANS=INF; for(int i=0;i<=la;i++){ for(int j=1;j<=lb;j++){ if(i)dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[i]!=b[j]));//直接往后走/修改 dp[i][j]=min(dp[i][j],dp[i][j-1]+1);//插入一个 if(i)dp[i][j]=min(dp[i][j],dp[mm[i-1][j-1]][j-1]+i-mm[i-1][j-1]-1+(a[i]!=b[j]));//删除 if(i) if(dp[i][j]<dp[mm[i-1][j]][j]+i-mm[i-1][j])mm[i][j]=i; else mm[i][j]=mm[i-1][j]; } ANS=min(ANS,dp[i][lb]); } printf("%d\n",ANS); } return 0; } |
2.社交网络
打表可知，答案为
$$连通块大小之积\times n^{连通块个数-2}$$
特判一下只有一个联通块
证明的话好像要什么树的prufer编码。。不会
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
// <netrd.cpp> - 03/22/16 08:16:44 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100050; int n,m; lol p,sb; int f[MAXN]; int gf(int x){if(f[x]!=f[f[x]])f[x]=gf(f[x]);return f[x];} lol cnt[MAXN]; lol qpow(lol a,lol b){ lol ans=1; while(b){ if(b&1)ans=(ans*a)%p; a=(a*a)%p; b>>=1; } return ans; } int main(){ freopen("netrd.in","r",stdin); freopen("netrd.out","w",stdout); n=getint();m=getint();p=getint(); for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=m;i++){ int x=getint(),y=getint(); if(x>y)swap(x,y); int fx=gf(x),fy=gf(y); if(fx>fy)swap(fx,fy); f[fy]=fx; } for(int i=1;i<=n;i++){ if(!cnt[gf(i)])sb++; cnt[f[i]]++; } if(sb==1){printf("%d",int(1%p));return 0;} lol xx=qpow(n,sb-2)%p; for(int i=1;i<=n;i++)if(cnt[i]){xx=xx*cnt[i];xx%=p;} printf("%d",int(xx)); return 0; } |
3.中位数
骗分都没写