\(\\\)

\(\#A\)

---

给出两个整数\(L,R\)，从\(L\)到\(R\)按顺序写下来，求生成整数对\(9\)取模后的答案。

例如\(L=8,R=12\)，生成的数字是\(89101112\)，对\(9\)取模的答案是\(5\)。

• 多组询问，次数\(\le 10^5\)，\(L,R\le 10^{12},L\le R\)。

• 首先要知道一个性质：因为\(10^k-1\equiv 0\pmod{9}\)，所以\(10^k\equiv 1\pmod{9}\)，于是整个数对\(9\)取模，等于每一个数位上的数字乘以\(10\)对应的幂次之和对\(9\)取模，因为\(10\)的任意幂次对\(9\)取模都为\(1\)，所以答案就变成了各个数位上的数字和对\(9\)取模的答案。
• 直接等差数列就和，没必要计算\(2\)的逆元，因为相乘的两项里必有一个是偶数，先除掉就好。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;ll t,l,r;int main(){ scanf("%lld",&t); while(t--){ scanf("%lld %lld",&l,&r); if((l+r)%2==0) printf("%lld\n",(l+r)/2%9*(r-l+1)%9); else printf("%lld\n",(r+l)%9*(r-l+1)/2%9); } return 0;}
          
         
        
       
      
     
    

\(\\\)

\(\#B\)

---

一张\(N\)个点\(M\)条边的无向图，通过边有时间的消耗，有两个人开始都在\(1\)号点。有\(K\)个点只能让第一个人通过。

现给出两个特殊点\(A,B\)，求出这两点中每一个点都至少都被一个人访问的最早时间。

• \(N\le 5\times 10^4\)，\(A,B,K\le N\)，数据保证图和可行答案均合法。

• 显然答案只有可能产生于四种情况：

  • 第一个人去\(A\)，第二个人去\(B\)
  • 第一个人去\(B\)，第二个人去\(A\)
  • 第一个人先去\(A\)，再从\(A\)去\(B\)
  • 第一个人先去\(B\)，再从\(B\)去\(A\)

  显然不存在第二个人去两个点的最优解，因为第二个人能到达的所有地方第一个人都可以到。

• 预处理\(1,A,B\)三个点的最短路，\(1\)号点需要多处理一次不走那\(K\)个点的最短路，然后四个答案取\(min\)就好。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 50010#define M 100010#define R register#define gc getcharusing namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}bool s[N],vis[N];int n,m,k,tot,hd[N],dis[4][N];struct edge{int to,nxt,w;}e[M<<1];inline void add(int u,int v,int w){ e[++tot].to=v; e[tot].w=w; e[tot].nxt=hd[u]; hd[u]=tot;}priority_queue
            
             
               >q;inline void dij1(){ memset(vis,0,sizeof(vis)); q.push(make_pair(0,1)); dis[0][1]=0; while(!q.empty()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(R int i=hd[u],v;i;i=e[i].nxt) if(dis[0][v=e[i].to]>dis[0][u]+e[i].w){ dis[0][v]=dis[0][u]+e[i].w; q.push(make_pair(-dis[0][v],v)); } }}inline void dij2(){ memset(vis,0,sizeof(vis)); q.push(make_pair(0,1)); dis[1][1]=0; while(!q.empty()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(R int i=hd[u],v;i;i=e[i].nxt) if(!s[v=e[i].to]&&dis[1][v]>dis[1][u]+e[i].w){ dis[1][v]=dis[1][u]+e[i].w; q.push(make_pair(-dis[1][v],v)); } }}inline void dij3(int x){ memset(vis,0,sizeof(vis)); q.push(make_pair(0,x)); dis[2][x]=0; while(!q.empty()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(R int i=hd[u],v;i;i=e[i].nxt) if(dis[2][v=e[i].to]>dis[2][u]+e[i].w){ dis[2][v]=dis[2][u]+e[i].w; q.push(make_pair(-dis[2][v],v)); } }}inline void dij4(int x){ memset(vis,0,sizeof(vis)); q.push(make_pair(0,x)); dis[3][x]=0; while(!q.empty()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(R int i=hd[u],v;i;i=e[i].nxt) if(dis[3][v=e[i].to]>dis[3][u]+e[i].w){ dis[3][v]=dis[3][u]+e[i].w; q.push(make_pair(-dis[3][v],v)); } }}int main(){ n=rd(); m=rd(); k=rd(); for(R int i=1;i<=k;++i) s[rd()]=1; for(R int i=1,u,v,w;i<=m;++i){ u=rd(); v=rd(); w=rd(); add(u,v,w); add(v,u,w); } int t1=rd(),t2=rd(); memset(dis,0x3f,sizeof(dis)); dij1(); dij2(); dij3(t1); dij4(t2); int ans1=max(dis[0][t1],dis[1][t2]); int ans2=max(dis[0][t2],dis[1][t1]); int ans3=dis[0][t1]+dis[2][t2]; int ans4=dis[0][t2]+dis[3][t1]; printf("%d\n",min(min(ans1,ans2),min(ans3,ans4))); return 0;}
             
            
           
          
         
        
       
      
     
    

\(\\\)

\(\#C\)

---

模拟题，题面见链接。

• \(N,M\le 200\)，\(c\le 20,k\le 100\)，数据保证图中的蛇不会引起混淆

WA了不知道多少遍......

• 首先模拟的时候蛇会死的情况：撞墙，撞到自己或其他蛇的身体。

• 然后蛇吃东西变长也很好操作：更改头指针，把地图食物变为蛇头。

• 恶心在移动一步到空地：蛇头好说，蛇尾巴呢？

  • 直接找尾巴旁边唯一一个身体或头的符号？虽然开始的时候保证蛇之间不会混淆，但是走着走着就有可能蛇身子成一坨，废了。像下面这种情况下一步并不知道往哪里走。

    

  • 那就记录每一个节点的前驱，每次移动或死亡都维护一下？废了，如果蛇只有一个头呢。

  • 对每一条蛇用单独一个队列维护。倒序存储，即队头是蛇尾。每次移动的时候先将新的头加入，在将蛇尾重置尾空地。

• 有了上面的维护方法统计答案就很简单，队列大小即为对应蛇的长度，注意排序需要双关键字。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 410#define R register#define gc getcharusing namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}bool v[N],vis[N][N];int n,m,k,cnt;char c,mp[N][N],w[N*N][110];struct point{ int x,y; point(int _x=0,int _y=0){x=_x;y=_y;}};queue
            
              q[N*N];struct ans{int len,x;}a[N*N];inline bool cmp(ans x,ans y){ return (x.len==y.len)?x.x
             
              y.len;}inline void dead(int x){ v[x]=1; while(q[x].size()){ mp[q[x].front().x][q[x].front().y]='&'; q[x].pop(); }}inline void move(int x,char t){ int nx=q[x].back().x,ny=q[x].back().y; if(t=='W') --nx; if(t=='S') ++nx; if(t=='A') --ny; if(t=='D') ++ny; if(nx<1||nx>n||ny<1||ny>m) dead(x); else if(mp[nx][ny]=='#'||mp[nx][ny]=='@') dead(x); else if(mp[nx][ny]=='.'){ mp[nx][ny]='@'; mp[q[x].back().x][q[x].back().y]='#'; mp[q[x].front().x][q[x].front().y]='.'; q[x].push((point){nx,ny}); q[x].pop(); } else{mp[nx][ny]='@'; mp[q[x].back().x][q[x].back().y]='#';q[x].push((point){nx,ny});}}void dfs(int x,int y){ vis[x][y]=1; if(mp[x+1][y]=='#'&&!vis[x+1][y]) dfs(x+1,y); if(mp[x-1][y]=='#'&&!vis[x-1][y]) dfs(x-1,y); if(mp[x][y+1]=='#'&&!vis[x][y+1]) dfs(x,y+1); if(mp[x][y-1]=='#'&&!vis[x][y-1]) dfs(x,y-1); q[cnt].push((point){x,y});}int main(){ n=rd(); m=rd(); k=rd(); for(R int i=1;i<=n;++i){ c=gc(); while(c!='.'&&c!='#'&&c!='@'&&c!='&') c=gc(); mp[i][1]=c; scanf("%s",mp[i]+2); } for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) if(mp[i][j]=='@') ++cnt,dfs(i,j); for(R int i=1;i<=cnt;++i){ c=gc(); while(!isupper(c)) c=gc(); w[i][1]=c; for(R int j=2;j<=k;++j) w[i][j]=gc(); } for(R int i=1;i<=k;++i) for(R int j=1;j<=cnt;++j) if(!v[j]) move(j,w[j][i]); for(R int i=1;i<=cnt;++i) a[i].x=i,a[i].len=q[i].size(); int ss=0; for(R int i=1;i<=cnt;++i) a[i].x=i; for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) if(mp[i][j]=='&') ++ss; sort(a+1,a+1+cnt,cmp); for(R int i=1;i<=cnt;++i) printf("%d %d\n",a[i].len,a[i].x); printf("%d",ss); return 0;}