7.15模擬賽

T1.fuction

吐槽一波錯誤拼寫。

跟考場思路差不多，只不過細節挺多的呢。

判掉a=0,b=0,c=0的幾種組合，還有負數的情況要打標記特殊處理。

然后就是一個拓歐啦，先求出g=gcd(a,b)，順便求出ax+by=g的x和y，然后根據裴蜀定理（或者是直覺），我們知道ax+by可以以g為長度遍歷數軸，要是c%g!=0，那就無解了。

然后是可以整除的情況，就把x和y乘以d=c/g，這樣就求出了ax+by=c的一組x和y了，定x為較小的數，把x補到正，同時y跟著減，要是x剛好到正，y已經負了，那就是無解。

還有，此時如果a和b是一正一負的，是無窮多解的，因為可以正負系數同時不斷擴大。

然后剩下的情況，就是x和y都是正整數啦，此時為了滿足ax+by=c，考慮有多少種等價情況，也就是x加上一個sa*x，y就得減去一個sb*y，顯然sa=lcm(a,b)/a=b/g，同理sb=a/g

因為x是增大的，y是減小的，我們只需要判斷y能減多少個sb就可以啦。

?

#include<iostream>
#include<cstdio>
#define NON puts("0"),0
#define INF puts("ZenMeZheMeDuo"),0
using namespace std;const int MAX=65535;inline int rd(){int ret=0,f=1;char c;while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;while(isdigit(c))ret=ret*10+c-'0',c=getchar();return ret*f;
}typedef long long ll;ll exgcd(ll A,ll B,ll &x,ll &y){if(!B) return x=1,y=0,A;ll ret=exgcd(B,A%B,y,x);y-=A/B*x;return ret;
}ll T,a,b,c;int solve(){a=rd();b=rd();c=rd();bool fa=0,fb=0;if(a<=0&&b<=0) a=-a,b=-b,c=-c;if(!a)if(c%b==0&&c/b>0) return INF;else return NON;if(!b)if(c%a==0&&c/a>0)return INF;else return NON;if(a==0&&b==0)return c?NON:INF;if(a==1&&b==1)return c>MAX-1?INF:printf("%lld\n",c-1);if(a<0) fa=1,a=-a;if(b<0) fb=1,b=-b;if(a+b==c)return puts("1"),0;ll x,y;ll g=exgcd(a,b,x,y);if(c%g) return NON;ll d=c/g;x*=d;y*=d;if(fa) a=-a,x=-x;if(fb) b=-b,y=-y;ll sa=b/g,sb=a/g;if(a*b<0) return INF;ll t=x/sa-1;if(x%sa==0) t--;x-=t*sa;y+=t*sb;if(x>sa) x-=sa,y+=sb;if(y<=0) return NON;ll ans=y/sb+(y%sb!=0);if(ans>MAX) return INF;printf("%lld\n",ans);return 0;
}int main(){T=rd();while(T--) solve();return 0;
}

?

?

T2.coloration

樹形DP，提供了一種好的思路。

涉及考慮樹上點對的題，與其O(n^2)地考慮任意兩點的關系，不如考慮每條邊的貢獻。

本題中，對于一條邊e，它的邊權為w，其貢獻為 (左側黑點*右側黑點+左側白點*右側白點)*w

設f[i][j]為以i為根的子樹中選取j個黑點的最大貢獻，轉移時逐個合并子樹，用一個g數組先跑一次背包，再添加進f狀態。

復雜度O(n^2)，卡好邊界。

注意int到long long要乘一個1ll

#include<iostream>
#include<cstring>
#include<cstdio>using namespace std;const int MAXN=2048;inline int rd() {int ret=0,f=1;char c;while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;while(isdigit(c))ret=ret*10+c-'0',c=getchar();return ret*f;
}struct Edge {int next,to,w;
} e[MAXN<<1];
int ecnt,head[MAXN];
inline void add(int x,int y,int w) {e[++ecnt].to = y;e[ecnt].next = head[x];e[ecnt].w = w;head[x] = ecnt;
}int n,m;
long long f[MAXN][MAXN],g[MAXN];
int siz[MAXN];
int dfs(int x,int pre) {siz[x]=1;for(int i=head[x]; i; i=e[i].next) {int v=e[i].to;if(v==pre) continue;memset(g,0,sizeof(g));dfs(v,x);for(int j=min(m,siz[x]); j>=0; j--)for(int k=min(m-j,siz[v]); k>=0; k--)g[j+k]=max(g[j+k],f[x][j]+f[v][k]+((k*(m-k)+(siz[v]-k)*(n-m-siz[v]+k))*1ll*e[i].w));for(int j=0; j<=m; j++)f[x][j]=g[j];siz[x]+=siz[v];}
}int main() {n=rd();m=rd();int x,y,w;for(int i=1; i<=n-1; i++) {x=rd();y=rd();w=rd();add(x,y,w);add(y,x,w);}dfs(1,0);cout<<f[1][m];
}

?T3.ray

神題，正解居然是模擬。

考場寫了四類分類討論，預期得分60，實際扣了一些？可能是寫掛了一部分的原因。

考場想到了離散化存儲，二分查找，但是突然覺得這樣會多一個log，感覺最差情況的狀態數是n^2的，非常不可做，就用一個二維數組直接存了。

事實上，是可以離散化存的，這樣就有70分啦。（實際復雜度確實是O(nmlogn)）

#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>using namespace std;const int MAXN=100005;inline int rd(){int ret=0,f=1;char c;while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;while(isdigit(c))ret=ret*10+c-'0',c=getchar();return ret*f;
}vector<int> V[MAXN];bool vis[MAXN];
inline bool vaild(int x,int y){return !binary_search(V[x].begin(),V[x].end(),y);}
inline void add(int x,int y){vis[x]=1;V[x].push_back(y);} int n,m,lim,stx,sty,stdir;const int dx[5]={0,-1,-1,1,1};
const int dy[5]={0,1,-1,1,-1};int main(){n=rd();m=rd();lim=rd();int x,y;for(int i=1;i<=lim;i++){x=rd();y=rd();add(x,y);}for(int i=0;i<=n+1;i++){add(i,0);add(i,m+1);}for(int i=0;i<=m+1;i++){add(0,i);add(n+1,i);}stx=rd();sty=rd();string s;cin>>s;if(s=="NE") stdir=1;if(s=="NW") stdir=2;if(s=="SE") stdir=3;if(s=="SW") stdir=4;for(int i=1;i<=100000;i++) if(vis[i]) sort(V[i].begin(),V[i].end());//nlogn is better :)int cur,nx,ny,t1,t2;long long cnt=0;x=stx;y=sty;cur=stdir;bool db=0;while(cnt==0||x!=stx||y!=sty||cur!=stdir){nx=x+dx[cur];ny=y+dy[cur];cnt++;if(vaild(nx,ny)){x=nx;y=ny;continue;}switch(cur){case 1:{t1=vaild(nx,ny-1);t2=vaild(nx+1,ny);if(!(t1^t2)){db=1;cur=4;continue;}if(!t1){y++;cur=3;continue;}if(!t2){x--;cur=2;continue;}break;}case 2:{t1=vaild(nx+1,ny);t2=vaild(nx,ny+1);if(!(t1^t2)){db=1;cur=3;continue;}if(!t1){x--;cur=1;continue;}if(!t2){y--;cur=4;continue;}break;}case 3:{t1=vaild(nx,ny-1);t2=vaild(nx-1,ny);if(!(t1^t2)){db=1;cur=2;continue;}if(!t1){y++;cur=1;continue;}if(!t2){x++;cur=4;continue;}break;}case 4:{t1=vaild(nx-1,ny);t2=vaild(nx,ny+1);if(!(t1^t2)){db=1;cur=1;continue;}if(!t1){x++;cur=3;continue;}if(!t2){y--;cur=2;continue;}break;}}}if(db) cnt>>=1;cout<<cnt<<endl;return 0;
}

正解是這樣的，我們不去考慮每一步怎么走，而是考慮沿著這個方向可以到達哪里（哪個反射點）。

反射點的位置是可以計算的，可以證明，反射的次數是O(n+m+k)級別的，再加上關于k個限制的二分，總復雜度在O((n+m+k)logk)，可以接受！

對于先后經過的兩個反射點u,v，它們一定處于一個正方形對角線上，所以其距離就是切比雪夫距離。

所以，現在就要快速地找到某條對角線上下次出現的點了，怎么做呢？

對于左上到右下對角線上的點(x,y)，x-y是一個定值，與在第幾條有關。

同理，對于右上到左下的，x+y是一個定值，可以唯一代表第幾條對角線。

因此，我們重新將坐標分別寫為(x+y,x),(x-y,x)，這即保留了原始的坐標信息（可以O(1)算出），還可以通過把第一維作為第一關鍵字，使得排序后一條對角線在一個連續區間，第二維遞增。

這樣就可以迅速二分出下一個障礙物啦，很快地就可以算出了。

順便學到了切比雪夫距離（好像有人講過誒，忘記了..），可以方便地把坐標系旋轉45°并放縮sqrt(2)倍。

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;inline int rd() {int ret=0,f=1;char c;while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;while(isdigit(c))ret=ret*10+c-'0',c=getchar();return ret*f;
}// "CBSV" == "Chebyshev" :)
struct CBSV {int fi,se;CBSV(int X,int Y) {fi=X;se=Y;}bool operator<(const CBSV &rhs) const {return rhs.fi==fi?se<rhs.se:fi<rhs.fi;}
};int n,m,lim;
long long ans;
int sx,sy,sdx,sdy;
int cur,dir,dx,dy,db=0;vector<CBSV> V[2];
vector<CBSV>::iterator it;inline void add(int x,int y) {V[0].push_back(CBSV(x-y,x));V[1].push_back(CBSV(x+y,x));
}void work(int &x,int &y) {dir=(dx!=dy);CBSV now=dir?CBSV(x+y,x):CBSV(x-y,x);it=upper_bound(V[dir].begin(),V[dir].end(),now);while(it->fi!=now.fi) it--;if(dx<0) while(it->se>=x) it--;ans+=abs(x-it->se)-1;x=it->se;y=dir?it->fi-x:x-it->fi;int u=binary_search(V[0].begin(),V[0].end(),CBSV(x-y-dx,x-dx));int v=binary_search(V[0].begin(),V[0].end(),CBSV(x-y+dy,x));if(u==v )db=1,dx*=-1,dy*=-1;else if(u) x-=dx,dy*=-1;else if(v) y-=dy,dx*=-1;
}int main() {n=rd();m=rd();lim=rd();int x,y;for(int i=1; i<=lim; i++) {x=rd();y=rd();add(x,y);}for(int i=0; i<=n+1; i++) add(i,0),add(i,m+1);for(int i=0; i<=m+1; i++) add(0,i),add(n+1,i);sort(V[0].begin(),V[0].end());sort(V[1].begin(),V[1].end());char s[50];x=rd();y=rd();scanf("%s",s);dx=s[0]=='N'?-1:1;dy=s[1]=='W'?-1:1;work(x,y);ans=0;sx=x;sy=y;sdx=dx;sdy=dy;do work(x,y);while(!(x==sx&&y==sy&&dx==sdx&&dy==sdy));printf("%lld",db?(ans>>1):ans);
}

?