A 贪心

给定四种状态，状态0没有钓鱼也不能做鱼饵；状态1可以做鱼饵，但是没有鱼；状态三有鱼但不能做鱼饵；状态四有鱼也可以做鱼饵。没有鱼的状态下，如果有鱼饵，可以钓鱼。

做法是简单贪心。有鱼的时候直接钓鱼，没鱼但能做鱼饵就做鱼饵，没鱼且不能做鱼饵就看看有没有鱼饵可以用来钓鱼。从左到右扫一遍，如果最后发现鱼饵有剩下，那就答案加上鱼饵数/2，表示原本做鱼饵的状态，一半用来做鱼饵，一般用这些做出来的鱼饵钓鱼

B 简单思维题

刚看完题目的时候以为是线段树or Splay区间搬移，但想到签到题不太可能需要用到复杂的数据结构。后来wxdl说有很简单的思路，于是我就去看其他题了。赛后发现，实际上只需要移动指针即可维护答案。

C 简单计算几何

给出右手的形状，并说明左手和右手是对称的。现在给出一组20个点的坐标，问这些坐标表示的是左手还是右手。

题目中一个很重要的条件是，测试数据中的手和题面中的手相比，只会平移和旋转，而不会放大缩小。同时又观察到，图中由一条长为6的边、一条长为1的边和一条长为3的边组成的手指只有拇指。所以可以搞一个宽度为4的窗口，找到这样的四个点：两组相邻点的距离分别是6和3。这样就能找到拇指的位置。找到之后，用叉乘判断下在拇指左侧的点多还是右侧的点多即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <cmath>
#include <unordered_map>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=1e5+5;
const double eps=1e-3;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int sgn(double x)
{
    double Eps=1e-8;
    if(fabs(x)<Eps){
        return 0;
    }
    if(x<0) return -1;
    else return 1;
}
struct point{
    double x;
    double y;
    point(){}
    point(double _x,double _y){
        x=_x;y=_y;
    }
    point operator-(const point& b)const{
        return point(x-b.x,y-b.y);
    }
    double operator^(const point& b)const{
        return x*b.y-y*b.x;
    }
};
struct line{
    point s,e;
    line(){}
    line(point _s,point _e){
        s=_s;e=_e;
    }
    int relation(point p){
        int c=sgn((p-s)^(e-s));
        if(c<0) return 1;
        else if(c>0) return 2;
        else return 3;
    }
};
point ps[22];
double sqr(double x)
{
    return x*x;
}
double dist(const point& pa,const point& pb)
{
    return sqrt(sqr(pa.x-pb.x)+sqr(pa.y-pb.y));
}
bool check(const point& pa,const point& pb,const point& pc,const point& pd)
{
    double dis1=dist(pa,pb);
    double dis2=dist(pc,pd);
    //printf("dis1 = %lf, dis2 = %lf, %lf, %lf\n",dis1,dis2,fabs(dis1-3.0),fabs(dis2-6.0));
    if((fabs(dis1-6.00)<eps&&fabs(dis2-3.00)<eps)||(fabs(dis1-3.00)<eps&&fabs(dis2-6.00)<eps)) return 1;
    return 0;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        double X,Y;
        for(int i=0;i<20;i++){
            scanf("%lf %lf",&X,&Y);
            ps[i].x=X;ps[i].y=Y;
        }
        int pos;
        int idx1,idx2,idx3,idx4;
        for(int i=0;i<20;i++){
            idx1=i;idx2=(i+1)%20;
            idx3=(i+2)%20;idx4=(i+3)%20;
            if(check(ps[idx1],ps[idx2],ps[idx3],ps[idx4])){
                pos=i;
                break;
            }
        }  
        //printf("pos = %d\n",pos);
        line L(ps[pos],ps[(pos+1)%20]);
        int lef=0;
        int rig=0;
        for(int i=(pos+2)%20;i!=pos;i=(i+1)%20){
            int rela=L.relation(ps[i]);
            if(rela==1) lef++;
            else if(rela==2) rig++;
        }
        if(lef<rig) puts("right");
        else puts("left");
    }
    return 0;
}

F 数论、拓展欧几里得

题意是说，给出两个整数\(a,b\)，\(c,d,e,f\)都是未知数，求方程\(\frac{c}{d}-\frac{e}{f}=\frac{a}{b}\)的任意一个解。同时，需要满足以下两个条件：

  • \(d<b\ and\ f<d\)
  • \(1\leq c,e\leq 4\times 10^{12}\)

思路是这样的，分三种情况讨论：

  • \(\gcd(a,b)>1\)

    设\(g=\gcd(a,b)\)，则有\(\frac{(a+1)/g}{b/g}-\frac{a/g}{b/g}=\frac{a}{b}\)。因为\(g>1\)，所以\(b/g<b\)，所以直接令\(c=(a+1)/g,d=b/g,e=a/g,f=b/g\)即可。

  • \(\gcd(a,b)=1\)，且\(b\)的质因数至少有两个

    设此时的\(b=p_1^{x_1}p_2^{x_2}p_3^{x_3}\dots p_n^{x_n}\)，令\(d=p_1^{x_1},f=\frac{b}{d}\)，则有\(df=b\)。问题转化为求解不定方程\(cf-de=a\)。用exgcd求解即可。

  • \(\gcd(a,b)=1\)，且\(b=p^x\)（\(p\)是素数）。也就是说\(b\)是1或者一个指数的幂次

    此时无解，原因是，如果\(b\)是1，那么\(d,f\)就只能取0，这显然是不可能的。如果\(b=p^x\)，则可以设\(d=p^u,f=p^{x-u}\)。exgcd有解的充要条件是\(\gcd(d,f)\mid a\)，所以有\(\gcd(d,f)=p^{\min\{u,x-u\}}\)。但因为\(\gcd(a,b)=1\)，所以\(a\)的质因子中没有\(p\)，也就是说\(\gcd(d,f)\nmid a\)，exgcd不可能有解。

拓展欧几里得解不定方程\(ax+by=c\)，最后的解一定要乘以\(\frac{c}{\gcd(a,b)}\)！因为求解这个方程的时候，实际上是在求解\(ax'+by'=\gcd(a,b)\)，因此要左右两边都同乘上\(\frac{c}{\gcd(a,b)}\)这个因子，才是最终的解！数论忘得一干二净orz

L 签到题

温暖的签到题，代码就不放了