上午考了一套sb题，但是没有人AK。李巨290虐场。

下午又考了一套sb题，李巨AK虐场。%%%

T1 %

中国剩余定理好像做不了啊，我一直在想如何用CRT做，然后就GG了。

然而正解是bike当初说的“CRT根本没用啊你每次合并两个数就可以了”然而这玩意似乎就叫做EXCRT。

考虑合并

x=y mod P

x=bi mod ai

k1*P+y=k2*ai+bi

k1*P+k3*ai=bi-y

exgcd解同余方程，得到一个解，从而得到k1的最小整数解。

x=x+k1*P

P=lcm(P,ai)

洛谷这道题要写快速乘

 

这道t1相当于是k1是暴力从小到大枚举的，lcm(p1~pi)=p1*p2*……pi，与p(i+1)互质，k最多枚举到i。P和x都很大不需要记下来，只需要记录它们模每个a和每个b的结果即可。

1 //Achen 2 #include
      
        3 #define For(i,a,b) for(int i=(a);i<=(b);i++) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int up=2007,N=307; 7 typedef unsigned long long LL; 8 typedef double db; 9 using namespace std;10 int n,m;11 int a[N],b[N];12 13 template
       
         void read(T &x) {14     char ch=getchar(); x=0; T f=1;15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();16     if(ch=='-') f=-1,ch=getchar();17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;18 }19 20 int bo[up+7],p[up+7];21 void get_prime() {22     for(int i=2;i<=up;i++) {23         if(!bo[i]) p[++p[0]]=i;24         for(int j=1;j<=p[0]&&p[j]*i<=up;j++) {25             bo[i*p[j]]=1;26             if(i%p[j]==0) break;27         }28     }29 }30 31 struct ct {32     int ma[N],mb[N];33     friend ct operator +(const ct &A,const ct &B) {34         ct rs;35         For(i,1,n) rs.ma[i]=(A.ma[i]+B.ma[i])%p[i];36         For(i,1,m) rs.mb[i]=((LL)A.mb[i]+B.mb[i])%b[i];37         return rs;38     }39     friend ct operator *(const ct &A,const int &B) {40         ct rs;41         For(i,1,n) rs.ma[i]=A.ma[i]*B%p[i];42         For(i,1,m) rs.mb[i]=(LL)A.mb[i]*B%b[i];43         return rs;44     }45 }bs,rs;46 47 #define ANS48 int main() {49 #ifdef ANS50     freopen("mod.in","r",stdin);51     freopen("mod.out","w",stdout);52 #endif53     get_prime();54     read(n); read(m);55     For(i,1,n) read(a[i]);56     For(i,1,m) read(b[i]);57     For(i,1,n) bs.ma[i]=1,rs.ma[i]=0; // rs=0 bs=158     For(i,1,m) bs.mb[i]=1,rs.mb[i]=0;59     For(i,1,n) {60         while(rs.ma[i]!=a[i]) rs=rs+bs;61         bs=bs*p[i];62     }63     int tp=0;64     For(i,1,n) if(rs.ma[i]==0) tp++;65     For(i,1,m) {66         if(tp==n) cout<
        
         <
        
       
      

 

T2 净化

最短路裸题。。

把水厂的dis设为0跑最短路，对于单向边u->v，答案和dis[u]+val(u,v)取max,对于双向边u<->v,ans-dis[u]+ans-dis[v]>=val(u,v)。

1 //Achen 2 #include
      
        3 #define For(i,a,b) for(int i=(a);i<=(b);i++) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int N=600007,inf=1e9; 7 typedef long long LL; 8 typedef double db; 9 using namespace std;10 int n,m,is[N],ec[N][4];11 12 template
       
         void read(T &x) {13     char ch=getchar(); x=0; T f=1;14     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();15     if(ch=='-') f=-1,ch=getchar();16     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;17 }18 19 int ecnt,fir[N],nxt[N],to[N],val[N];20 void add(int u,int v,int w,int i) {21     nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w;22 }23 24 struct node {25     int x,dis;26     node(int x,int dis):x(x),dis(dis){}27     friend bool operator <(const node&A,const node&B) {28         return A.dis>B.dis;29     }30 };31 priority_queue
        
         que;32 33 int dis[N];34 int solve() {35     For(i,1,n) {36         if(is[i]==1) {37             dis[i]=0; 38             que.push(node(i,0));    39         }40         else dis[i]=inf;41     }42     while(!que.empty()) {43         node t=que.top();44         que.pop();45         if(t.dis!=dis[t.x]) continue;46         for(int i=fir[t.x];i;i=nxt[i]) {47             if(dis[to[i]]>t.dis+val[i]) {48                 dis[to[i]]=t.dis+val[i];49                 que.push(node(to[i],dis[to[i]]));50             }51         }52     }53     int rs=0;54     For(i,1,m) {55         int x=ec[i][0],y=ec[i][1];56         int t=ec[i][2],len=ec[i][3];57         if(t==1) rs=max(rs,dis[x]+len);58         else {59             int tp=(dis[x]+dis[y]+len)/2;60             if((dis[x]+dis[y]+len)%2) tp++;61             if(tp>rs) rs=tp;62         }63     }64     return rs;65 }66 67 #define ANS68 int main() {69 #ifdef ANS70     freopen("purify.in","r",stdin);71     freopen("purify.out","w",stdout);72 #endif73     read(n); read(m);74     For(i,1,n) read(is[i]);75     For(i,1,m) {76         int x,y,t,len;77         read(x); read(y); read(t); read(len);78         ec[i][0]=x; ec[i][1]=y;79         ec[i][2]=t; ec[i][3]=len;80         add(x,y,len,i);81         if(t==2) add(y,x,len,i);82     }83     printf("%d\n",solve());84     Formylove;85 }
        
       
      

 

T3 三点通信

lca裸题。。

树上的答案等于d[x]+d[y]+d[z]-d[lca(x,y)]-d[lca(x,z)]-d[lca(y,z)]

有环的话，记下多出的一条边，要么只在树上走，同上，要么考虑多出的一条边(u,v)要被经过，枚举x,y,z中某些点到u,某些点到v，再加上u,v的权值。

求树上k个点之间的路径长度的话，怕是要建哦，不知道有没有更简单的方法。

1 //Achen 2 #include
      
        3 #define For(i,a,b) for(int i=(a);i<=(b);i++) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int N=200017; 7 typedef long long LL; 8 typedef double db; 9 using namespace std;10 int n,m,q;11 LL HC,HD[N];12 13 template
       
         void read(T &x) {14     char ch=getchar(); x=0; T f=1;15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();16     if(ch=='-') f=-1,ch=getchar();17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;18 }19 20 int ecnt,fir[N],nxt[N],to[N];21 LL val[N];22 void add(int u,int v,LL w) {23     nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w;24     nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;25 }26 27 int vis[N],R[N],ok,ex,ey,f[N][20];28 LL dis[N],el;29 void dfs(int x,int fa) {30     vis[x]=1;31     f[x][0]=fa;32     R[x]=R[fa]+1;33     For(i,1,17) f[x][i]=f[f[x][i-1]][i-1];34     for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) {35         if(vis[to[i]]) {36             ok=1;37             ex=x; ey=to[i]; el=val[i];38         }39         else {40             dis[to[i]]=dis[x]+val[i];41             dfs(to[i],x);42         }43     }44 }45 46 int lca(int x,int y) {47     if(R[x]
        
         =R[y])49         x=f[x][i];50     if(x==y) return x;51     Rep(i,17,0) if(f[x][i]!=f[y][i])52         x=f[x][i],y=f[y][i];53     return f[x][0];54 }55 56 LL calc(int a,int b) { return dis[a]+dis[b]-2LL*dis[lca(a,b)]; }57 LL calc(int a,int b,int c) { return dis[a]+dis[b]+dis[c]-dis[lca(a,b)]-dis[lca(a,c)]-dis[lca(b,c)]; }58 59 LL solve(int a,int b,int c) {60     LL rs=calc(a,b,c);61     if(ok) {62         rs=min(rs,calc(a,ex)+calc(b,c,ey)+el);63         rs=min(rs,calc(b,ex)+calc(a,c,ey)+el);64         rs=min(rs,calc(c,ex)+calc(a,b,ey)+el);65         rs=min(rs,calc(a,ey)+calc(b,c,ex)+el);66         rs=min(rs,calc(b,ey)+calc(a,c,ex)+el);67         rs=min(rs,calc(c,ey)+calc(a,b,ex)+el);68     }69     return rs;70 }71 72 #define ANS73 int main() {74 #ifdef ANS75     freopen("three.in","r",stdin);76     freopen("three.out","w",stdout);77 #endif78     read(n); read(m); read(q);79     For(i,1,m) {80         int x,y; LL z;81         read(x); read(y); read(z);82         add(x,y,z);83     }84     dfs(1,0);85     For(cs,1,q) {86         int x,y,z;87         read(x); read(y); read(z);88         printf("%lld\n",solve(x,y,z));89     }90     Formylove;91 }