T1 x
今天唯一一道没有用骗分方法的题目,然而还是由于一个小细节写挂了orz
显然的是,如果两个数不互质,显然他们必须在一个集合里,于是我们可以将不互质的数连边,最后看有多少个联通块,答案就是\(2^{s}-2\)其中s就是联通块的个数.如果用暴力的方法来实现的话,时间复杂度是\(O(n^2)\)的.
我们可以只枚举每个数的质因子,来降低这一复杂度.
|
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 58 59 60 |
#include<bits/stdc++.h> using namespace std; const int MAXN=1e5+10,MAXA=1e6+10,mod=1e9+7; int prime[MAXA],p[MAXA],cnt,minp[MAXA],las[MAXA]; vector<int>g[MAXN]; bool v[MAXN]; void prework(){ for(int i=2;i<MAXA;i++){ if(!p[i]){ prime[++cnt]=i; minp[i]=i; } for(int j=1;j<=cnt&&i*prime[j]<MAXA;j++){ p[i*prime[j]]=1; minp[i*prime[j]]=prime[j];//考试的时候我这里写成了i if(i%prime[j]==0)break; } } } void dfs(int x){ v[x]=1; for(int i=0;i<(int)g[x].size();i++){ if(v[g[x][i]])continue; dfs(g[x][i]); } } int main(){ prework(); int t;scanf("%d",&t); while(t--){ int n;scanf("%d",&n); memset(las,0,sizeof(las)); memset(v,0,sizeof(v)); for(int i=1;i<=n;i++)g[i].clear(); for(int i=1;i<=n;i++){ int x;scanf("%d",&x); while(x>1){ int fac=minp[x]; while(x%fac==0)x/=fac; if(las[fac]){ g[las[fac]].push_back(i); g[i].push_back(las[fac]); } las[fac]=i; } } int ans=1; for(int i=1;i<=n;i++){ if(!v[i]){ ans=ans*2%mod;dfs(i); } } printf("%d\n",(ans+mod-2)%mod); } return 0; } |
T2 y
考试的时候用的是dfs枚举,骗了30分,可以不枚举状态转而判断状态的存在性,可以骗到90分,然而还是过不了.
正解是动态规划,
出题人说:f[i][j][mask] 表示从 i 出发，j 结束，是否存在一条表示为 mask 的路径。
然而这样会T,得分甚至不如dfs,于是出题人又说
meet in the middle，对于每种可能的路径，枚举中间的那个位置判断。时间复杂度为\(O(2^\frac{d}{2} \times n \times (n + m) + 2^d \times n)\)
用了bitset,先放个表格方便理解代码:
| 变量名 | 变量类型 | 变量作用 |
|---|---|---|
| g0[i] | bitset | 表示i点与哪些节点连权值为0的边 |
| g1[i] | bitset | 表示i点与哪些节点连权值为1的边 |
| dp[i] | bitset | 表示i状态可以以哪些点为终点 |
| f[i] | bitset | 表示i状态可以以哪些点为起点 |
|
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 |
#include<bits/stdc++.h> using namespace std; const int N=105; const int MAXN=2048;//2的20/2+1次方 int n,m,d; bitset<N>g0[N],g1[N],dp[MAXN],f[MAXN]; int main(){ scanf("%d%d%d",&n,&m,&d); for(int i=1,u,v,c;i<=m;i++){ scanf("%d%d%d",&u,&v,&c); if(c){g1[u][v]=g1[v][u]=1;} else {g0[u][v]=g0[v][u]=1;} } int d2=d/2,d1=d-d2; for(int u=n;u>=1;u--){//倒序枚举每一个点 for(int i=0;i<MAXN;i++)dp[i].reset();//清空 dp[1][u]=1;//以u为结尾状态是否存在，最开始的1是为了避免前导0 for(int x=1;x<(1<<d1);x++){//枚举状态 for(int y=1;y<=n;y++){//枚举点 if(dp[x][y]){//如果当前状态可以以枚举的点为终点 dp[x<<1]|=g0[y];//拓展出新的状态并且边权为0,用g0[y]去更新 dp[x<<1|1]|=g1[y];//拓展出新的状态并且边权为1,用g1[y]去更新 } } } for(int x=0;x<(1<<d1);x++){//一个由u拓展的状态以任何一个结尾都说明以u开头的这个状态是存在的 f[x][u]=dp[1<<d1|x].any();//f数组是以u为开头的状态是否存在 } } int ans=0; for(int i=0;i<(1<<d1);i++){ for(int j=0;j<(1<<d2);j++){//最后的dp数组状态都是由1为开头拓展而来的 if((dp[1<<d2|j]&f[i]).any())ans++;//有任意一个接上就可以累计答案 } } cout<<ans<<endl; return 0; } |
?config=TeX-MML-AM_CHTML
连个点赞的地方都没有，差评！
评论就是赞许！d=====(￣▽￣*)b