T1
我只能说 它是一个比较暴力的dp，需要人力讨论...
所以考试觉得讨论太麻烦，直接内心崩溃了....(好像这也是我考炸的原因吧)
教训：以后要勤快一些，代码能力 唉唉唉
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#define mem(a,b) memset(a,b,sizeof(a))#define ll long longusing namespace std;const int N=2000006;const int mod=1000000007;char s[N];int n;ll ans;ll f[N][10];void dp(){if(s[1]=='0')f[1][0]=1;elseif(s[1]=='1')f[1][3]=1;elseif(s[1]=='*')f[1][4]=1;elseif(s[1]=='?'){f[1][0]=1;f[1][3]=1;f[1][4]=1;}for(int i=2;i<=n;++i){if(s[i]=='0'){f[i][0]+=f[i-1][0];f[i][0]%=mod;f[i][0]+=f[i-1][1];f[i][0]%=mod;}elseif(s[i]=='1'){f[i][3]+=f[i-1][0];f[i][3]%=mod;f[i][3]+=f[i-1][1];f[i][3]%=mod;f[i][1]+=f[i-1][4];f[i][1]%=mod;}elseif(s[i]=='2'){f[i][2]+=f[i-1][4];f[i][2]%=mod;}elseif(s[i]=='*'){f[i][4]+=f[i-1][3];f[i][4]%=mod;f[i][4]+=f[i-1][2];f[i][4]%=mod;f[i][4]+=f[i-1][4];f[i][4]%=mod;}else{f[i][0]+=f[i-1][0];f[i][0]%=mod;f[i][0]+=f[i-1][1];f[i][0]%=mod;f[i][3]+=f[i-1][0];f[i][3]%=mod;f[i][3]+=f[i-1][1];f[i][3]%=mod;f[i][1]+=f[i-1][4];f[i][1]%=mod;f[i][2]+=f[i-1][4];f[i][2]%=mod;f[i][4]+=f[i-1][3];f[i][4]%=mod;f[i][4]+=f[i-1][2];f[i][4]%=mod;f[i][4]+=f[i-1][4];f[i][4]%=mod;}}}int main(){scanf("%s",s);n=strlen(s);for(int i=n;i>=1;--i)s[i]=s[i-1];dp();ll ans=0;for(int i=0;i<=4;++i){if(i==2||i==3)continue;ans=(ans+f[n][i])%mod;}cout<<ans;}
T1
T2
这个结论 其实考试的时候已经很接近了
就是 每个点到所有边界点的所有路径中最高山的最小值
然后 可以求个最小生成树，在跑bfs
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#define mem(a,b) memset(a,b,sizeof(a))#define ll long longusing namespace std;const int N=316;struct son{int v,next,w;}a1[N*N*3];int first[N*N*3],e;void addbian(int u,int v,int w){a1[e].v=v;a1[e].w=w;a1[e].next=first[u];first[u]=e++;}struct JI{int u,v,w;bool friend operator < (JI a,JI b){return a.w<b.w;}}ji[N*N*3];int con;int n,m;int h[N][N];int dui[N][N];int ccc;int fa[N*N*3];int fin(int x){if(fa[x]==-1)return x;fa[x]=fin(fa[x]);return fa[x];}void kru(){sort(ji+1,ji+1+con);int now=0,x,y;for(int i=1;i<=con;++i){x=fin(ji[i].u);y=fin(ji[i].v);if(x!=y){fa[x]=y;//printf("%d\n",ji[i].w);addbian(ji[i].u,ji[i].v,ji[i].w);addbian(ji[i].v,ji[i].u,ji[i].w);++now;}if(now==ccc-1)break;}}int du[10000006],he,en;int d[N*N*3];bool flag[N*N*3];void work(){mem(d,60);int now;he=1;en=0;for(int i=n*m+1;i<=ccc;++i){d[i]=0;du[++en]=i;flag[i]=1;}int temp,temp1;while(en>=he){now=du[he++];flag[now]=0;//printf("now=%d\n",now);for(int i=first[now];i!=-1;i=a1[i].next){temp=a1[i].v;temp1=max(d[now],a1[i].w);if(d[temp]>temp1){d[temp]=temp1;if(!flag[temp]){flag[temp]=1;du[++en]=temp;}}}}}int main(){//freopen("T2.in","r",stdin);mem(fa,-1);mem(first,-1);scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&h[i][j]),dui[i][j]=(i-1)*m+j;ccc=n*m;for(int i=1;i<=n;++i)dui[i][0]=++ccc,dui[i][m+1]=++ccc;for(int j=1;j<=m;++j)dui[0][j]=++ccc,dui[n+1][j]=++ccc;for(int i=0;i<=n;++i)for(int j=1;j<=m;++j)ji[++con]=(JI){dui[i][j],dui[i+1][j],max(h[i][j],h[i+1][j])};//ji[++con]=(JI){dui[i+1][j],dui[i][j],max(h[i][j],h[i+1][j])};for(int j=0;j<=m;++j)for(int i=1;i<=n;++i)ji[++con]=(JI){dui[i][j],dui[i][j+1],max(h[i][j],h[i][j+1])};//ji[++con]=(JI){dui[i][j+1],dui[i][j],max(h[i][j],h[i][j+1])};kru();work();/*printf("\n");for(int i=1;i<=ccc;++i)printf("i=%d %d\n",i,d[i]);printf("\n");*/for(int i=1;i<=n;++i){for(int j=1;j<=m;++j)printf("%d ",d[dui[i][j]]-h[i][j]);printf("\n");}}
T2
T3
这个题 考试也是很接近，但是无奈，以前懒，根本没有学莫比乌斯函数的性质
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#define C(n) ((ll)(n)*((n)-1)/2)#define mem(a,b) memset(a,b,sizeof(a))#define ll long longusing namespace std;const int N=200006;const int MAXVAL=500006;struct son{int v,next;}a1[N*(1<<6)];int first[N*(1<<6)],e;void addbian(int u,int v){a1[e].v=v;a1[e].next=first[u];first[u]=e++;}int mu[MAXVAL],prime[MAXVAL],con;bool he[MAXVAL];void get_mu(){mu[1]=1;for(int i=2;i<MAXVAL;++i){if(!he[i]){prime[++con]=i;mu[i]=-1;}for(int j=1;j<=con&&prime[j]*i<MAXVAL;++j){he[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;break;}elsemu[i*prime[j]]=-mu[i];}}}int n,m;int a[N];bool flag[N];ll sum[MAXVAL];int main(){//freopen("gcd1.in","r",stdin);//freopen("T3.out","w",stdout);mem(first,-1);scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%d",&a[i]);get_mu();for(int i=1;i<=n;++i)for(int j=1;j*j<=a[i];++j)if(a[i]%j==0){addbian(i,j);if(j!=a[i]/j)addbian(i,a[i]/j);}int tin;ll now=0;for(int i=1;i<=m;++i){scanf("%d",&tin);if(flag[tin])for(int j=first[tin];j!=-1;j=a1[j].next){now-=((ll)mu[a1[j].v]*C(sum[a1[j].v]));--sum[a1[j].v];now+=((ll)mu[a1[j].v]*C(sum[a1[j].v]));}elsefor(int j=first[tin];j!=-1;j=a1[j].next){now-=((ll)mu[a1[j].v]*C(sum[a1[j].v]));++sum[a1[j].v];now+=((ll)mu[a1[j].v]*C(sum[a1[j].v]));}flag[tin]^=1;printf("%lld\n",now);}}
T3
至此，可以总结了:
1.考试不要慌，不要嫌麻烦
2.做人要勤快...
