20231018刷题记录

题记录"/>

20231018刷题记录

• P1878 舞蹈课

  堆。

  对于“舞蹈技术差”这一变量，可以想到用优先队列维护实现 O ( log ⁡ n ) O(\log n) O(logn) 级别的复杂度。

  对于整个舞蹈队伍的删除操作，可以用双向链表维护，比较经典的应用是开车旅行。这个东西首先比 STL 方便，具体实现画图理解即可。

  注意对于一对异性，只要有一个已经出队就直接 pop。

  #include <bits/stdc++.h>
  using namespace std;const int maxn=2e5+5;
  int ans[maxn][2];
  struct node1
  {int l,r,v;bool gen;
  }a[maxn];
  struct node2
  {int id1,id2,dif;bool friend operator < (node2 a,node2 b){int ll=a.dif,rr=b.dif;if(ll!=rr) return ll>rr;return a.id1>b.id1;}
  };
  priority_queue<node2> q;
  bool vis[maxn];int main()
  {int n;cin>>n;for(int i=1;i<=n;i++) {char c;cin>>c,a[i].l=i-1,a[i].r=i+1;if(c=='B') a[i].gen=0;else a[i].gen=1;}for(int i=1;i<=n;i++) cin>>a[i].v;for(int i=1;i<n;i++) if(a[i].gen^a[i+1].gen) q.push((node2){i,i+1,abs(a[i].v-a[i+1].v)});int k=0;while(!q.empty()){node2 t=q.top();if(vis[t.id1]||vis[t.id2]){q.pop();continue;}ans[++k][0]=t.id1,ans[k][1]=t.id2,q.pop(),vis[t.id1]=vis[t.id2]=1;a[a[t.id1].l].r=a[t.id2].r,a[a[t.id2].r].l=a[t.id1].l;if(a[t.id1].l>=1&&a[t.id2].r<=n&&a[a[t.id1].l].gen^a[a[t.id2].r].gen) q.push((node2){a[t.id1].l,a[t.id2].r,abs(a[a[t.id2].r].v-a[a[t.id1].l].v)});}cout<<k<<endl;for(int i=1;i<=k;i++) cout<<ans[i][0]<<' '<<ans[i][1]<<endl;return 0;
  }
  

• P2853 Cow Picnic S

  搜索。

  以每个奶牛为起点 DFS，统计每个点的访问次数即可。

  #include <bits/stdc++.h>
  using namespace std;const int maxn=1005,maxm=1e4+5;
  int head[maxn],cnt,tot[maxn],a[maxn];
  struct edge{int to,nxt;}e[maxm];
  bool vis[maxn];void add(int x,int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}void dfs(int x)
  {vis[x]=1,tot[x]++;for(int i=head[x];i;i=e[i].nxt) if(!vis[e[i].to]) dfs(e[i].to);
  }int main()
  {int K,N,M;cin>>K>>N>>M;for(int i=1;i<=K;i++) cin>>a[i];for(int i=1,u,v;i<=M;i++) cin>>u>>v,add(u,v);for(int i=1;i<=K;i++) memset(vis,0,sizeof vis),dfs(a[i]);int ans=0;for(int i=1;i<=N;i++) if(tot[i]>=K) ans++;cout<<ans;return 0;
  }
  

• P4667 Switch the Lamp On

  最短路。

  与原来相同的边边权为 0 0 0，不同的边权为 1 1 1。

  #include <bits/stdc++.h>
  using namespace std;
  #define int long longconst int maxn=1e6+5;
  int head[maxn],nxt[maxn],to[maxn],cnt,w[maxn],diss[maxn];
  char s[505][505];
  bool vis[maxn];void add(int x,int y,int z)
  {to[++cnt]=y;w[cnt]=z;nxt[cnt]=head[x];head[x]=cnt;
  }struct node
  {int id,dis;bool friend operator < (node a,node b){return a.dis>b.dis;}
  };
  priority_queue<node> q;void dij()
  {memset(diss,0x3f,sizeof(diss));diss[1]=0;q.push(node{1,0});while(!q.empty()){node qwq=q.top();q.pop();int x=qwq.id;if(vis[x]) continue;vis[x]=1;for(int i=head[x];i;i=nxt[i])if(diss[to[i]]>diss[x]+w[i])diss[to[i]]=diss[x]+w[i],q.push(node{to[i],diss[to[i]]});}
  }signed main()
  {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int N,M;cin>>N>>M;for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) cin>>s[i][j];if((N+M)%2) cout<<"NO SOLUTION"<<endl;else{int qwq=N*(M+1)+M+1;for(int i=1;i<=qwq;i++)head[i]=0,nxt[i]=0,to[i]=0,w[i]=0,vis[i]=0,cnt=0;for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){int l1=(M+1)*(i-1)+j,l2=l1+M+1,r1=l1+1,r2=r1+M+1;if(s[i][j]=='\\') add(l1,r2,0),add(r2,l1,0),add(l2,r1,1),add(r1,l2,1);else add(l1,r2,1),add(r2,l1,1),add(l2,r1,0),add(r1,l2,0);}	dij();cout<<diss[qwq]<<endl;}return 0;
  }
  

• P1962 斐波那契数列

  矩阵加速。

  有递推式;
  { f n = f n − 1 × 1 + f n − 2 × 1 f n − 1 = f n − 1 × 1 + f n − 2 × 0 \begin{cases} f_{n}=f_{n-1}\times 1+f_{n-2}\times 1\\ f_{n-1}=f_{n-1}\times 1+f_{n-2}\times 0 \end{cases} {fn​=fn−1​×1+fn−2​×1fn−1​=fn−1​×1+fn−2​×0​
  于是有
  [ f n f n − 1 ] = [ 1 1 1 0 ] n − 2 × [ f 2 f 1 ] \begin{bmatrix}f_n&f_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-2}\times\begin{bmatrix}f_2&f_1\end{bmatrix} [fn​​fn−1​​]=[11​10​]n−2×[f2​​f1​​]
  结构体中重载矩阵乘法的 * 运算符即可。

  注意特判 f 1 = 1 , f 2 = 1 f_1=1,f_2=1 f1​=1,f2​=1。

  #include <bits/stdc++.h>
  using namespace std;const int mod=1e9+7;struct mat
  {int a[3][3];mat(){memset(a,0,sizeof a);}mat operator * (const mat &b) const{mat res;for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++)res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%mod;return res;}
  }ans,ba;void init()
  {ba.a[1][1]=ba.a[1][2]=ba.a[2][1]=1;ans.a[1][1]=ans.a[1][2]=1;
  }void quickpow(int b)
  {while(b){if(b&1) ans=ans*ba;b>>=1,ba=ba*ba;}
  }int main()
  {int n;cin>>n;if(n<=2) cout<<1,exit(0);init();quickpow(n-2);cout<<(ans.a[1][1]%mod);return 0;
  }