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
      
       #include
       
        #define NON puts("0"),0#define INF puts("ZenMeZheMeDuo"),0using 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
      
       #include
       
        #include
        
         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<
        
       
      

 T3.ray

神题，正解居然是模拟。

考场写了四类分类讨论，预期得分60，实际扣了一些？可能是写挂了一部分的原因。

考场想到了离散化存储，二分查找，但是突然觉得这样会多一个log，感觉最差情况的状态数是n^2的，非常不可做，就用一个二维数组直接存了。

事实上，是可以离散化存的，这样就有70分啦。（实际复杂度确实是O(nmlogn)）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           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
           
             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<
            
             <
            
           
          
         
        
       
      

正解是这样的，我们不去考虑每一步怎么走，而是考虑沿着这个方向可以到达哪里（哪个反射点）。

反射点的位置是可以计算的，可以证明，反射的次数是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
      
       #include
       
        #include
        
         #include
         
          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
          
           
             V[2];vector
            
             ::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);}