[ Luogu Contest 10364 ] TG

\(\\\)

\(\#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<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

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<cmath>

#include<queue>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define N 50010

#define M 100010

#define R register

#define gc getchar

using 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<pair<int,int> >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\) \(PION\)贪吃蛇

模拟题，题面见链接。

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

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

首先模拟的时候蛇会死的情况：撞墙，撞到自己或其他蛇的身体。
然后蛇吃东西变长也很好操作：更改头指针，把地图食物变为蛇头。
恶心在移动一步到空地：蛇头好说，蛇尾巴呢？
- 直接找尾巴旁边唯一一个身体或头的符号？虽然开始的时候保证蛇之间不会混淆，但是走着走着就有可能蛇身子成一坨，废了。像下面这种情况下一步并不知道往哪里走。
- 那就记录每一个节点的前驱，每次移动或死亡都维护一下？废了，如果蛇只有一个头呢。
- 对每一条蛇用单独一个队列维护。倒序存储，即队头是蛇尾。每次移动的时候先将新的头加入，在将蛇尾重置尾空地。
有了上面的维护方法统计答案就很简单，队列大小即为对应蛇的长度，注意排序需要双关键字。

#include<cmath>

#include<queue>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 410

#define R register

#define gc getchar

using 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<point> 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.x:x.len>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;

}

巴特西

[ Luogu Contest 10364 ] TG

\(\#A\) 小凯的数字

\(\#B\) 密室

\(\#C\) \(PION\)贪吃蛇

最新文章

热门文章