[考试反思]0920csp-s模拟测试48：弱小
发布时间：2020-12-14 05:06:40 所属栏目：大数据 来源：网络整理
导读：注：T1全场46个人里42个AC了。 %%%zkt也AK了呢越来越强啊 我是真的越来越弱了吗？ 我到底在干什么。。。 在难度递增的题里分数递增。。。 考试过程大体还好，但是如此快速地WA掉T1也真是蠢得不行了。 T2没想到bitset，对1500这种数据范围还是不敏感。 T3想出
|
注：T1全场46个人里42个AC了。 %%%zkt也AK了呢越来越强啊 我是真的越来越弱了吗？ 我到底在干什么。。。 在难度递增的题里分数递增。。。 考试过程大体还好，但是如此快速地WA掉T1也真是蠢得不行了。 T2没想到bitset，对1500这种数据范围还是不敏感。 T3想出来还是挺快的，注意观察数据范围就万事大吉。（二进制相关的题我的得分平时都不太低，是撞大运了？） 然后给T2和T3都上了个对拍，T3出锅了剩30分幸亏改过来了。 然而感觉T1实在太傻逼了暴力和正解是一个复杂度的就没打，手模几个样例就结束了。 题目的样例和手模的样例都在字串和子序列下答案相同。。。 但是这次不是看错题了，我也知道是子串，但是打到一半没过脑子就飘移到子序列上了。（因为原来做过一个那个题） 我，傻子，太弱了。 不要轻视最简单的题，你A不掉的！该打对拍还是要对拍。 bitset是出题人很喜欢的一个考点，1500的数据范围可能指向n3/32 ? T1： 简单dp或硬匹配。 自行找不同？EXP++
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 char a[305],b[305];int n,k,dp[305][305][305]; 5 int main(){ 6 scanf("%d%d%s%s",&n,&k,a+1,b+1); 7 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)for(int l=0;l<=k;++l){ 8 if(a[i]==b[j])dp[i][j][l]=max(dp[i][j][l],dp[i-1][j-1][l]+1); 9 if(l)dp[i][j][l]=max(dp[i][j][l],dp[i-1][j-1][l-1]+1); 10 dp[i][j][l]=max(dp[i][j][l],max(dp[i-1][j][l],dp[i][j-1][l])); 11 }printf("%dn",dp[n][n][k]); 12 }
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 char a[305],dp[305][305][305],ans; 5 int main(){ 6 scanf("%d%d%s%s",dp[i-1][j-1][l-1]+1); 10 ans=max(dp[i][j][l],ans); 11 }printf("%dn",ans); 12 } 思路积累：
? T2： 容斥。所有路径-第1，3个点相同的路径-第2，4个点相同的路径+第13和24分别相同的路径-三元环数×6。
1 #include<cstdio> 2 int n,d[1505];long long dp[5][1505],ans;char s[1505][1505]; 3 int main(){ 4 scanf("%d",&n); 5 for(int i=1;i<=n;++i)scanf("%s",s[i]+1); 6 for(int i=1;i<=n;++i)dp[1][i]=1; 7 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]==‘1‘)d[i]++; 8 for(int t=2;t<=4;++t)for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]==‘1‘)dp[t][i]+=dp[t-1][j]; 9 for(int i=1;i<=n;++i)ans+=dp[4][i]; 10 for(int i=1;i<=n;++i)ans-=d[i]*d[i]*2; 11 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]==‘1‘)ans++; 12 for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(s[i][j]==‘1‘) 13 for(int k=j+1;k<=n;++k)if(s[i][k]==‘1‘&&s[j][k]==‘1‘)ans-=6; 14 printf("%lldn",ans); 15 }
1 #include<cstdio> 2 #include<bitset> 3 using namespace std; 4 bitset<1501>b[1501]; 5 int n,ans;char s[1505][1505]; 6 int main(){ 7 scanf("%d",&n); 8 for(int i=1;i<=n;++i)scanf("%s",s[i]+1); 9 for(int i=1;i<=n;++i)dp[1][i]=1; 10 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]==‘1‘)d[i]++; 11 for(int t=2;t<=4;++t)for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]==‘1‘)dp[t][i]+=dp[t-1][j]; 12 for(int i=1;i<=n;++i)ans+=dp[4][i]; 13 for(int i=1;i<=n;++i)ans-=d[i]*d[i]*2; 14 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]==‘1‘)ans++; 15 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]==‘1‘)b[i][j]=1; 16 for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(b[i][j])ans-=(b[i]&b[j]).count()*2; 17 printf("%lldn",ans); 18 } 思路积累：
? T3： 观察数据范围，权值小于220，大约是1048576。既然没有出到230显然复杂度与之有关。 题目里有特殊性质，边权都是1，那么就是一个BFS而不是Dijkstra。（然而并没有卡Dijkstra的log复杂度） 那么每一个点只会被更新一次，那1048576也只会各被更新一次。 存进vector里面用dfs更新即可。
1 #include<cstdio> 2 #include<vector> 3 using namespace std; 4 vector<int>v[1048578]; 5 int n,val[200005],dt[200005],m,fir[200005],l[600005],to[600005],cnt,al[1048588]; 6 int q[200005],qt; 7 void link(int a,int b){l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;} 8 inline void read(register int &p,register char ch=getchar()){p=0; 9 while(ch<‘0‘||ch>‘9‘)ch=getchar(); 10 while(ch>=‘0‘&&ch<=‘9‘)p=(p<<3)+(p<<1)+ch-48,ch=getchar(); 11 } 12 void update(register const int num,register const int d){ 13 al[num]=1; 14 for(register int i=0;i<v[num].size();++i)if(dt[v[num][i]]>d)dt[v[num][i]]=d,q[++qt]=v[num][i]; 15 for(register int j=num;j;j-=j&-j)if(!al[num^(j&-j)])update(num^(j&-j),d); 16 } 17 int main(){//freopen("t3.in","r",stdin);freopen("t3.out","w",stdout); 18 read(n);read(m); 19 for(int i=1;i<=n;++i)read(val[i]),v[val[i]].push_back(i); 20 for(int i=1,x,y;i<=m;++i)read(x),read(y),link(x,y); 21 for(int i=2;i<=n;++i)dt[i]=200001; 22 q[qt=1]=1; 23 for(int qh=1;qh<=qt;++qh){ 24 for(int i=fir[q[qh]];i;i=l[i])if(dt[to[i]]>dt[q[qh]]+1)dt[to[i]]=dt[q[qh]]+1,q[++qt]=to[i]; 25 if(!al[val[q[qh]]])update(val[q[qh]],dt[q[qh]]+1); 26 } 27 for(int i=1;i<=n;++i)printf("%dn",dt[i]==200001?-1:dt[i]); 28 } ?思路积累：
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
