NOIp2018集训test-10-23

上午考了一套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的结果即可。

 //Achen

 #include<bits/stdc++.h>

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 #define Formylove return 0

 const int up=,N=;

 typedef unsigned long long LL;

 typedef double db;

 using namespace std;

 int n,m;

 int a[N],b[N];

 template<typename T> void read(T &x) {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 int bo[up+],p[up+];

 void get_prime() {

     for(int i=;i<=up;i++) {

         if(!bo[i]) p[++p[]]=i;

         for(int j=;j<=p[]&&p[j]*i<=up;j++) {

             bo[i*p[j]]=;

             if(i%p[j]==) break;

         }

     }

 }

 struct ct {

     int ma[N],mb[N];

     friend ct operator +(const ct &A,const ct &B) {

         ct rs;

         For(i,,n) rs.ma[i]=(A.ma[i]+B.ma[i])%p[i];

         For(i,,m) rs.mb[i]=((LL)A.mb[i]+B.mb[i])%b[i];

         return rs;

     }

     friend ct operator *(const ct &A,const int &B) {

         ct rs;

         For(i,,n) rs.ma[i]=A.ma[i]*B%p[i];

         For(i,,m) rs.mb[i]=(LL)A.mb[i]*B%b[i];

         return rs;

     }

 }bs,rs;

 #define ANS

 int main() {

 #ifdef ANS

     freopen("mod.in","r",stdin);

     freopen("mod.out","w",stdout);

 #endif

     get_prime();

     read(n); read(m);

     For(i,,n) read(a[i]);

     For(i,,m) read(b[i]);

     For(i,,n) bs.ma[i]=,rs.ma[i]=; // rs=0 bs=1

     For(i,,m) bs.mb[i]=,rs.mb[i]=;

     For(i,,n) {

         while(rs.ma[i]!=a[i]) rs=rs+bs;

         bs=bs*p[i];

     }

     int tp=;

     For(i,,n) if(rs.ma[i]==) tp++;

     For(i,,m) {

         if(tp==n) cout<<bs.mb[i]<<endl;

         else cout<<rs.mb[i]<<endl;

     }

     Formylove;

 }

T2 净化

最短路裸题。。

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

 //Achen

 #include<bits/stdc++.h>

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 #define Formylove return 0

 const int N=,inf=1e9;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,m,is[N],ec[N][];

 template<typename T> void read(T &x) {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 int ecnt,fir[N],nxt[N],to[N],val[N];

 void add(int u,int v,int w,int i) {

     nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w;

 }

 struct node {

     int x,dis;

     node(int x,int dis):x(x),dis(dis){}

     friend bool operator <(const node&A,const node&B) {

         return A.dis>B.dis;

     }

 };

 priority_queue<node>que;

 int dis[N];

 int solve() {

     For(i,,n) {

         if(is[i]==) {

             dis[i]=;

             que.push(node(i,));

         }

         else dis[i]=inf;

     }

     while(!que.empty()) {

         node t=que.top();

         que.pop();

         if(t.dis!=dis[t.x]) continue;

         for(int i=fir[t.x];i;i=nxt[i]) {

             if(dis[to[i]]>t.dis+val[i]) {

                 dis[to[i]]=t.dis+val[i];

                 que.push(node(to[i],dis[to[i]]));

             }

         }

     }

     int rs=;

     For(i,,m) {

         int x=ec[i][],y=ec[i][];

         int t=ec[i][],len=ec[i][];

         if(t==) rs=max(rs,dis[x]+len);

         else {

             int tp=(dis[x]+dis[y]+len)/;

             if((dis[x]+dis[y]+len)%) tp++;

             if(tp>rs) rs=tp;

         }

     }

     return rs;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("purify.in","r",stdin);

     freopen("purify.out","w",stdout);

 #endif

     read(n); read(m);

     For(i,,n) read(is[i]);

     For(i,,m) {

         int x,y,t,len;

         read(x); read(y); read(t); read(len);

         ec[i][]=x; ec[i][]=y;

         ec[i][]=t; ec[i][]=len;

         add(x,y,len,i);

         if(t==) add(y,x,len,i);

     }

     printf("%d\n",solve());

     Formylove;

 }

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个点之间的路径长度的话，怕是要建虚树哦，不知道有没有更简单的方法。

 //Achen

 #include<bits/stdc++.h>

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 #define Formylove return 0

 const int N=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,m,q;

 LL HC,HD[N];

 template<typename T> void read(T &x) {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 int ecnt,fir[N],nxt[N],to[N];

 LL val[N];

 void add(int u,int v,LL w) {

     nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w;

     nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;

 }

 int vis[N],R[N],ok,ex,ey,f[N][];

 LL dis[N],el;

 void dfs(int x,int fa) {

     vis[x]=;

     f[x][]=fa;

     R[x]=R[fa]+;

     For(i,,) f[x][i]=f[f[x][i-]][i-];

     for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) {

         if(vis[to[i]]) {

             ok=;

             ex=x; ey=to[i]; el=val[i];

         }

         else {

             dis[to[i]]=dis[x]+val[i];

             dfs(to[i],x);

         }

     }

 }

 int lca(int x,int y) {

     if(R[x]<R[y]) swap(x,y);

     Rep(i,,) if(R[f[x][i]]>=R[y])

         x=f[x][i];

     if(x==y) return x;

     Rep(i,,) if(f[x][i]!=f[y][i])

         x=f[x][i],y=f[y][i];

     return f[x][];

 }

 LL calc(int a,int b) { return dis[a]+dis[b]-2LL*dis[lca(a,b)]; }

 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)]; }

 LL solve(int a,int b,int c) {

     LL rs=calc(a,b,c);

     if(ok) {

         rs=min(rs,calc(a,ex)+calc(b,c,ey)+el);

         rs=min(rs,calc(b,ex)+calc(a,c,ey)+el);

         rs=min(rs,calc(c,ex)+calc(a,b,ey)+el);

         rs=min(rs,calc(a,ey)+calc(b,c,ex)+el);

         rs=min(rs,calc(b,ey)+calc(a,c,ex)+el);

         rs=min(rs,calc(c,ey)+calc(a,b,ex)+el);

     }

     return rs;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("three.in","r",stdin);

     freopen("three.out","w",stdout);

 #endif

     read(n); read(m); read(q);

     For(i,,m) {

         int x,y; LL z;

         read(x); read(y); read(z);

         add(x,y,z);

     }

     dfs(,);

     For(cs,,q) {

         int x,y,z;

         read(x); read(y); read(z);

         printf("%lld\n",solve(x,y,z));

     }

     Formylove;

 }

巴特西

NOIp2018集训test-10-23

最新文章

热门文章