首页 > 其他分享 >P4621 [COCI2012-2013#6] BAKTERIJE 题解

P4621 [COCI2012-2013#6] BAKTERIJE 题解

时间:2024-11-07 17:24:27浏览次数:1  
标签:P4621 10 md int 题解 COCI2012 times xx face

一道很好的数学题。

首先不难想到每个细菌的移动路线是有循环节的,循环节外的时间最多就是每个格子的四个方向都走一遍,也就是 \(4\times N \times M\)。

可以预处理每个细菌分别通过四个方向第一次到达终点的时间 \(b_{i,0/1/2/3}\) 和再次回到当前状态的循环节长度 \(md_{i,0/1/2/3}\)。

要特别注意的是不同方向到达终点是不同的状态。

首先 \(4\times N \times M\) 以内的答案直接暴力算出来(有可能有病毒没有进入循环节)。

然后计算大于 \(4\times N \times M\) 的答案,假设已知了每个病毒最终到达终点面对的方向 \(face_i\),其实限制就是一个同余方程,设答案为 \(x\),对于每个病毒有限制:

\[x\equiv b_{i,face_i}(\bmod md_{i,face_i}) \]

可以扩展中国剩余定理求解,每个病毒面对的方向可以搜索。

有一个细节,扩展中国剩余定理求解的答案必须大于等于所有的 \(b_{i,face_i}\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=60;
const int INF=1e18;
int as=INF;
int n,m,k,rx,ry;
int dx[10]={-1,0,1,0},dy[10]={0,1,0,-1};
int tun[10]={2,3,0,1};
int vis[N][N][4],b[N][4],md[N][4],rec[N][N];
int mp[N][N],x,y;
int ton[2*N*N*4];
int hp[4],cho[N],lim=0;

struct node{
    int x,y;
    char c;
}q[N];
bool out(int xx,int yy){
    if(xx>n || xx<1 || yy>m || yy<1) return true;
    return false;
} 

int go(int xx,int yy,int st){
    st+=mp[xx][yy];
    st%=4;
    if(!out(xx+dx[st],yy+dy[st])) return st;
    else return tun[st];
}

void work(int now,int nx,int ny,char ch){
    int st;
    if(ch=='U') st=0;
    else if(ch=='R') st=1;
    else if(ch=='D') st=2;
    else st=3;
    int tim=0;
    hp[0]=hp[1]=hp[2]=hp[3]=0;
    int xf=INF;
    while(tim<=n*m*4){
        ++tim;
        if(nx==rx && ny==ry){
            xf=min(xf,tim);
            if(b[now][st]==INF) b[now][st]=tim;
            else if(md[now][st]==INF) md[now][st]=tim-b[now][st];
            ton[tim]++;
            hp[st]=tim;
        }
        st=go(nx,ny,st);
        nx+=dx[st],ny+=dy[st];
    }
    lim=max(lim,xf);
}

void init(){
    cin>>n>>m>>k;
    cin>>rx>>ry;
    for(int i=0;i<N;i++){
        for(int j=0;j<4;j++) b[i][j]=md[i][j]=INF;
    }
    for(int i=1;i<=k;i++){
        cin>>q[i].x>>q[i].y>>q[i].c;
        string s;
        for(int j=1;j<=n;j++){
            cin>>s,s=" "+s;
            for(int k=1;k<=m;k++) mp[j][k]=(s[k]-'0');
        }
        work(i,q[i].x,q[i].y,q[i].c);
    }
}

int exgcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return a;
	}
	else{
		int as=exgcd(b,a%b);
		int xx=x,yy=y;
		x=yy,y=xx-(a/b)*yy;
		return as;
	}
}

int qmul(int af,int bf,int p){
	int aa=0,x=af;
	while(bf){
		if(bf&1){
			aa+=x;
			aa%=p;
		}
		x*=2;
		x%=p;
		bf/=2;
	}
	return aa;
}

int excrt(){
    int ans=b[1][cho[1]],lcm=md[1][cho[1]];
	for(int i=2;i<=k;i++){
        int aa=lcm,bb=md[i][cho[i]],cc=b[i][cho[i]]-ans;
		cc=(cc%md[i][cho[i]]+md[i][cho[i]])%md[i][cho[i]];
		int d=exgcd(aa,bb);
		if(cc%d){
		    return INF;
		}
		ans=ans+lcm*qmul(x,cc/d,md[i][cho[i]]);
		lcm/=d,lcm*=md[i][cho[i]];
		ans=(ans%lcm+lcm)%lcm;
	}
    int af=ans;
    if(lim>af){
        int xx=(lim-af)/lcm;
        af+=(xx*lcm);
        if(af<lim) af+=lcm; 
    }
    return af;
}

void dfs(int x){
    if(x==k+1){
        as=min(as,excrt());
        return;
    }
    for(int i=0;i<4;i++){
        if(b[x][i]==INF || md[x][i]==INF) continue;
        cho[x]=i;
        dfs(x+1);
    }
}

signed main(){
    init();
    for(int i=1;i<=n*m*4;i++){
        if(ton[i]==k){
            cout<<i;
            return 0;
        }
    }
    dfs(1);
    if(as==INF) cout<<-1;
    else cout<<as;
    return 0;
}

标签:P4621,10,md,int,题解,COCI2012,times,xx,face
From: https://www.cnblogs.com/wangwenhan/p/18533127

相关文章

  • 题解:[BZOJ2958] 序列染色
    ProblemLinkBZOJ2958序列染色题意给出一个长度为\(n\),由\(\ttB,W,X\)三种字符组成的字符串\(S\),你需要把每一个\(\ttX\)染成\(\ttB\)或\(\ttW\)中的一个。Solution字符串,染色,方案数,一眼\(dp\)。要求前半段是B,后半段是W。考虑容斥。\(f_{i,0/1},g_{i,......
  • IOR的脚本化、版本兼容性及常见问题解答
    脚本化IOR可以使用-f选项在命令行中使用输入脚本。在-f选项之前设置的命令行选项将被视为运行脚本的默认设置。例如:mpirun./ior-W-fscript将使用隐式-W运行脚本中的所有测试。脚本本身可以覆盖这些设置,并且可以设置为在一次执行下运行许多不同的IOR测试,重要的是要注意在-......
  • 【题解】CF1944
    CF1944A简要题意给定完全图删k条边使得从一号点开始的可达点最少Solution注意到最多需要删n-1条边就可以使得任意一个其他点都到达不了又注意到只要删的边少于n-1就可以从一号点走出去,主要走出去就可以走到任何点所以这题答案只有两种如果k≤n-1答案为n否则答案为1......
  • 题解:P11248 [GESP202409 七级] 矩阵移动
    题目传送门题目大意给出一个nnn行mmm列的只包含0、1、?的矩......
  • 【记录】Cordial Sync具身智能协作源码复现及问题解决
    论文简要总结智能体需要合作将家具移动到客厅的指定位置。这个任务与现有的任务不同,它要求智能体在每个时间步都必须进行协调。模型部分1.SYNC-policies(SynchronizeYourActionsCoherently)为了解决智能体在每个时间步都需要协调的问题,研究者提出了SYNC-policies。这......
  • AtCoder Beginner Contest 284题解
    AtCoderBeginnerContest284A没有什么难点,反着输出一遍就可以了。#include<bits/stdc++.h>usingnamespacestd;stringa[2000];intmain(){ intn; cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=n;i;i--)cout<<a[i]<<'\n';......
  • 题解:HDU5628 Clarke and math
    数学题可爱捏~HintAnalysis注意到形式很好看,猜测是某种神奇迭代。考虑特殊情况\(k=1\),于是有:\(g(i)=\sum_{i_1\midi}f(i_1)=(f*1)(i)\)$即\(g=f*1\)。于是猜测\(g=f*1^k\),这里的幂运算表示多次Dirichlet卷积。简单证明一下,采用数学归纳法:基本情况\(k=1\),已经证过,......
  • CF 1438 题解
    CF1438题解ASpecificTastesofAndre考虑一种非常简单的构造:\(a_i=1\).不难发现满足条件.BValeriiAgainstEveryone结论:符合条件当且仅当有两个一样的元素.证明:充分性显然,下证必要性.若不存在两个一样的元素,则由于无法进位,故没有办法得到两个区间和在相......
  • 【考试题解】NOIP2024加赛2
    目录A.新的阶乘(factorial)题目内容部分分?pts正解思路代码B.博弈树(tree)题目内容部分分80pts正解思路代码C.划分(divide)题目内容部分分10pts14pts正解思路代码D.灯笼(lantern)A.新的阶乘(factorial)题目内容定义运算\(f(x)=x^1\times(x-1)^2\times(x-2)^3\dots2^{x-1......
  • CF2001 题解
    A给定循环数组,每次操作时,设当前大小为m。选择$i\in[0,m)$,若满足$a_i\lea_{i+1\bmodm}$,则可删除$a_i,a_{i+1\bmodm}$中的任意一个。求最小的操作次数,使得数组中所有元素都相等。$n\le100$操作非常强,除了两个相邻位置相等的情况,可以删除任意元素。然而所有位置都......