雅礼学习10.4

本文主要是介绍雅礼学习10.4，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

雅礼学习10.4

上午考试

各题状况

T1

莫名其妙20分了。

考场上一眼秒掉了这个题目：这不就是个并查集捆绑+快速幂么

然后开开心心这个点如果有这个质因子的话\(fa\)就指向这个质因子，而每个数字有多个质因子。。。

多个质因子在相互指\(fa\)的时候指乱套了。。。。

对拍的时候看出来的，然后用\(1\)个多小时来调这份代码，最后自己都不知道这东西在干嘛了，就凉了。

T2

写了个暴力枚举，期望\(20\)实际\(20\)

T3

看到成绩之后：这题怎么会爆\(long long\)的？？？

然后讲题的时候。。。出题人说第二个部分分里面\(a_i\)的取值范围给错了，少了三个零。。。

凉凉，\(30\)挂没了

题目及考场代码

T1

图片.png

#include <cstdio>
#include <cstring>inline int read()
{int n=0,w=1;register char c=getchar();while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();return n*w;
}
const int N=1e5+1,mod=1e9+7;
int n,tot,a[N],prime[N],head[N*10];
bool notprime[N],vis[N];
struct Edge{int v,nxt;
}edge[N<<1];
inline void add(int u,int v)
{edge[++tot]=(Edge){v,head[u]};head[u]=tot;}inline void Get_prime()
{for(int i=2;i<N;++i){if(!notprime[i])prime[++tot]=i;for(int j=1;i*prime[j]<=N && j<=tot;++j){notprime[i*prime[j]]=true;if(i%prime[j] == 0)break;}}
}inline void work(int now)
{int x=1e5,id=now;now=a[now];while(now^1){++x;if(now%prime[(int)(x-1e5)]==0){while(now%prime[x]==0)now/=x;add(id,x);}}
}void dfs(int now)
{vis[now]=true;for(int i=head[now];i;i=edge[i].nxt)dfs(edge[i].v);
}inline int ksm(long long x,int b)
{long long res=1;for(;b;b>>=1,x=x*x%mod)if(b&1)res=res*x%mod;return res;
}int main()
{freopen("x.in","r",stdin);freopen("x.out","w",stdout);int t=read();Get_prime();tot=0;while(t--){memset(vis,false,sizeof vis);memset(head,0,sizeof head);tot=0;n=read();for(int i=1;i<=n;++i){a[i]=read();work(i);}tot=0;for(int i=1;i<=n;++i)if(!vis[i]){++tot;dfs(i);}printf("%d\n",(ksm(2,tot)-2+mod)%mod);}fclose(stdin),fclose(stdout);return 0;
}

T2

图片.png

/** 这啥题啊。。。* ao原来d是长度啊。。。。** 那不是。。。暴力就很好写了* string+map水一发*/
#include <string>
#include <cstdio>
#include <map>inline int read()
{int n=0,w=1;register char c=getchar();while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();return n*w;
}const int N=91;
int n,m,d,tot,ans,head[N];
std::string s;
std::map<std::string,int> mp;
struct Edge{int v,w,nxt;
}edge[N*(N-1)*2];
inline void add(int u,int v,int w)
{edge[++tot]=(Edge){v,w,head[u]};head[u]=tot;}void dfs(int now,int step)
{if(step==d){if(!mp[s])mp[s]=++ans;return ;}for(int i=head[now];i;i=edge[i].nxt){s.push_back(edge[i].w+'0');dfs(edge[i].v,step+1);s.erase(s.end()-1);}
}int main()
{freopen("y.in","r",stdin);freopen("y.out","w",stdout);n=read(),m=read(),d=read();for(int u,v,w,i=1;i<=m;++i){u=read(),v=read(),w=read();add(u,v,w),add(v,u,w);}dfs(1,0);printf("%d",ans);fclose(stdin);fclose(stdout);return 0;
}

T3

图片.png

/** 我旁边的dalao用一小时切了这个题，然后到处说：哇T3好水我贪心能100啊* 然后有人问他：你复杂度多少的* 他：100啊* 那人：？？？100是个什么复杂度啊，我问的是复杂度* 他：aoao。。。我看看啊。。。 O(n*q)的* 那人：。。。你再去看看数据范围* 他：？？？** 笑死我了hhhhh* 写了个模拟*/
#include <cstdio>inline int read()
{int n=0,w=1;register char c=getchar();while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();return n*w;
}const int N=1e5+1;
int n,q,x[N];int main()
{freopen("z.in","r",stdin);freopen("z.out","w",stdout);n=read(),q=read();for(int i=1;i<=n;++i)x[i]=read();int len,l,r,ans;while(q--){len=read();ans=l=0,r=len;for(int i=1;i<=n;++i){if(x[i]>r){ans+=x[i]-r;l+=x[i]-r;r=x[i];}elseif(x[i]<l){ans+=l-x[i];r-=l-x[i];l=x[i];}}printf("%d\n",ans);}fclose(stdin);fclose(stdout);return 0;
}

正解及代码

T1

对所有\(gcd\ne 1\)的两个数字连边，最后统计联通块数量（假设为\(cnt\)），那么答案为\(2^{cnt}-2\)

#include<bits/stdc++.h>
using namespace std;const int maxn=1e5+10,maxa=1e6+10,mod=1e9+7;
int t,n,last[maxa],ans;
bool vis[maxn];
vector<int> g[maxn];
int pcnt,prime[maxa],minp[maxa];
bool prm[maxa];inline void init(){for(int i=2;i<maxa;++i){if(!prm[i]){prime[++pcnt]=i;minp[i]=i;}for(int j=1;j<=pcnt&&i*prime[j]<maxa;++j){prm[i*prime[j]]=true;minp[i*prime[j]]=prime[j];if(i%prime[j]==0)break;}}
}
void dfs(int pos){vis[pos]=true;for(int i=0;i<g[pos].size();++i)if(!vis[g[pos][i]])dfs(g[pos][i]);
}int main(){freopen("x.in","r",stdin);freopen("x.out","w",stdout);init();scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=pcnt;++i)last[prime[i]]=0;for(int i=1,x;i<=n;++i){vis[i]=false;g[i].clear();scanf("%d",&x);while(x>1){int fac=minp[x];while(x%fac==0)x/=fac;if(last[fac]){g[i].push_back(last[fac]);g[last[fac]].push_back(i);}last[fac]=i;}}ans=1;for(int i=1;i<=n;++i)if(!vis[i])ans=ans*2%mod,dfs(i);printf("%d\n",(ans+mod-2)%mod);}return 0;
}

T2

\(f[i][j][mask]\)表示从\(i\)出发，到\(j\)结束，是否存在一条表示为\(mask\)的路径

但是显然这个复杂度不够优

考虑meet in the middle ，对于每种可能的路径，枚举中间的位置进行判断

\(O(2^{\frac{d}{2}}\times n\times (n+m))+2^d\times n\)

可以用\(bitset\)进行优化，能让整体除以\(64\)，由此可以解决\(N\)更大的问题

#include<bits/stdc++.h>
using namespace std;const int maxn=90+10,maxmask=1<<20/2+1;
int n,m,d,d1,d2,ans;
bitset<maxn> g0[maxn],g1[maxn],dp[maxmask],f[maxmask];int main(){freopen("y.in","r",stdin);freopen("y.out","w",stdout);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]=true;elseg0[u][v]=g0[v][u]=true;}d2=d/2;d1=d-d2;for(int u=n;u;--u){for(int i=0;i<maxmask;++i)dp[i].reset();dp[1][u]=true;for(int x=1;x<1<<d1;++x)for(int v=1;v<=n;++v)if(dp[x][v]){dp[x<<1]|=g0[v];dp[x<<1|1]|=g1[v];}for(int x=0;x<1<<d1;++x)f[x][u]=dp[1<<d1|x].any();}for(int i=0;i<1<<d1;++i)for(int j=0;j<1<<d2;++j)if((dp[1<<d2|j]&f[i]).any())++ans;printf("%d\n",ans);return 0;
}

T3

如果存在一个\(x_i\)使得\(x_{i-1}=x_i\)或者\(x_{i-1}\lt x_i\lt x_{i+1}\)，那么可以删掉它（当完成上一个\(x\)的时候同时完成了这个任务）

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn=1e5+10;
int n,m;
ll tot,ans[maxn];
vector<int> x;
vector<pair<int,int> > a;
map<int,int> mp;inline ll calc(ll k){if(!mp.empty()&&mp.begin()->second<0)return tot-(mp.size()-1)*k;elsereturn tot-mp.size()*k;
}
inline void solve(){priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;int t=0;for(int i=0;i<x.size();++i){tot+=abs(x[i]);mp[i]=x[i];q.push(make_pair(abs(x[i]),i));}while(!q.empty()){int id=q.top().second,tmp=q.top().first;q.pop();map<int,int>::iterator p=mp.lower_bound(id);if(p==mp.end()||p->first!=id||abs(p->second)!=tmp)continue;while(t<a.size()&&abs(p->second)>a[t].first)ans[a[t].second]=calc(a[t].first),++t;if(p!=mp.begin())if(p!=prev(mp.end())){tmp=p->second,tot-=abs(p->second);tmp+=prev(p)->second,tot-=abs(prev(p)->second);tmp+=next(p)->second,tot-=abs(next(p)->second);mp.erase(prev(p));mp.erase(next(p));p->second=tmp,tot+=abs(tmp);q.push(make_pair(abs(tmp),id));}else{tot-=abs(p->second);mp.erase(p);}else if(p->second>0)if(p!=prev(mp.end())){tmp=p->second,tot-=abs(p->second);tmp+=next(p)->second,tot-=abs(next(p)->second);mp.erase(next(p));if(tmp){p->second=tmp,tot+=abs(tmp);q.push(make_pair(abs(tmp),id));}elsemp.erase(p);}else{tot-=abs(p->second);mp.erase(p);}}while(t<a.size())ans[a[t].second]=calc(a[t].first),++t;
}int main(){freopen("z.in","r",stdin);freopen("z.out","w",stdout);scanf("%d%d",&n,&m);for(int i=0,p,last=0;i<n;++i){scanf("%d",&p);if(p==last)continue;if(!x.empty()&&(x.back()<0&&p<last||x.back()>0&&p>last))x.back()+=p-last;elsex.push_back(p-last);last=p;}for(int i=0,l;i<m;++i){scanf("%d",&l);a.push_back(make_pair(l,i));}sort(a.begin(),a.end());solve();for(int i=0;i<m;++i)printf("%lld\n",ans[i]);return 0;
}

下午讲课：图题

例一

一个\(n\)个点\(m\)条边的无向连通图从\(1\)号点开始\(bfs\)，可能得到的\(bfs\)序有很多，取决于出边的访问顺序。现在给出一个\(1\)到\(n\)的排列，判断是否可能是一个\(bfs\)序

\(n,m\le 2\times 10^5\)

解：

先假设给出的这个\(bfs\)序列是合法的，令每个节点的权值为在给定序列中的位置

然后从\(1\)号点开始进行\(bfs\)，出边的访问顺序按照权值从小到大访问

最后将这样跑\(bfs\)得到的\(bfs\)序跟给定的序列进行比较，如果完全一致，那么这个序列是合法的

例二

一个\(n\)个点\(m\)条边的无向连通图中每个点都有一个权值，现在要求给每条边定一个权值，满足每个点的权值等于所有相连的边权之和，权值可负。

解：

如果图是一棵树，那么方案就是唯一的，直接判就可以了。
否则随便搞一棵生成树，先不管其他边，跑一遍。
这时根节点可能还不满足条件。
这时考虑其他的边，一条非树边会形成一个环。
如果是一个偶环，那么无论这条非树边怎么变，都不会对根节点产生影响。
而如果是奇环，那么若给这条非树边增加或减少权值，根节点会发生2 的权值变
化。
那么就可以了。

例三

给定一个\(n\)个点\(m\)条边的有向带权图，对于一条边权为\(w\)的边，经过时将获得\(w\)的收益，之后\(w=\lfloor \frac{w}{2}\rfloor\)

问从\(1\)号点出发最多能获得多少收益

解：

一个强连通分量内部所有的边肯定可以被走到底。
所以缩点后\(dp\)即可

例四

有\(m\)个人，\(n\)张椅子，第\(i\)个人只能坐在第\(u_i\)或第\(v_i\)张椅子上。求有多少种方案满足没有人坐在同一张椅子上。

解：

把椅子当做点，人当做边，变成一个图。
每个连通块可以分开考虑。
假设某个连通块中有\(v\)个点，\(e\)条边，由于连通，有\(v−1\le e\)，并且若\(e\gt v\)则无解，所以\(e\)只有\(v−1\)和\(v\)两种取值。
假如\(e=v−1\)，那么该连通块有\(v\)种方案：考虑枚举每个点不放的情况，其他的点都可以唯一确定。
假如\(e=v\)且环长\(\gt 1\)，那么该连通块有\(2\)种方案：考虑环上的一条边，这条边的放法确定后其他的都可以唯一确定。