JS's Blog

ZOJ - 3950 How Many Nines （模拟

Posted on 2019-04-24 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
https://cn.vjudge.net/problem/ZOJ-3950

题目大意：
题目给出两个日期a与b，统计从日期a到b之间的所有日期里共有多有个’9’

分析：
分成四部分写，年份不同，月份不同，日期不同和完全相同，前缀和处理各种数据，最后重点处理下年份不同的情况即可

代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <time.h>
using namespace std;


int y1,m1,d1,y2,m2,d2;

int year = 65;
int day[2][20] = {{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};
int mart[2][30][50];
int lp[12000];
int np[12000];
int mnine[2][30][50];
int nine[12000];

inline int count9(int n)
{
    int cnt = 0;
    while (n)
    {
        if (n%10==9)
            cnt++;
        n/=10;
    }
    return  cnt;
}

bool leap(int n)
{
    return (!(n%4)&&(n%100))||!(n%400);
}

void init()
{
    for (int i = 1 ; i <= 10000 ; i ++)
        nine[i] = count9(i);
    int cnt = 0;
    int sum = 0;
    for (int i = 1 ; i <= 12 ; i ++)
    {
        for (int j = 1 ; j <= day[0][i] ; j ++)
        {
            mart[0][i][j] = cnt++;
            mnine[0][i][j] = sum;
            sum += nine[i]+nine[j];
        }
    }
    cnt = 0,sum = 0;
    for (int i = 1 ; i <= 12 ; i ++)
    {
        for (int j = 1 ; j <= day[1][i] ; j ++)
        {
            mart[1][i][j] = cnt++;
            mnine[1][i][j] = sum;
            sum += nine[i]+nine[j];
        }
    }
    cnt  = 0;
    lp[2000] = 0;
    np[2000] = 0;
    for (int i = 2001 ; i <= 9999 ; i ++)
    {
        bool flag = leap(i-1);
        lp[i] = flag+lp[i-1];
        np[i] = np[i-1] + nine[i-1]*(365+flag);
    }

    return;
}

int main()
{
    init();
	int T;
	//cout<<mart[1][12][31]<<endl;
	scanf("%d",&T);
	clock_t st,ed;
	while (T--){
            int ans = 0;
            scanf("%d%d%d",&y1,&m1,&d1);
           scanf("%d%d%d",&y2,&m2,&d2);
//            for (int i = y1+1 ; i < y2 ;  i++)
//                ans += year + leap(i) + nine[i]*(365+leap(i));
            bool flag = leap(y1);
            int cnt = 0 ;
            if (y1==y2)
            {
                if (m1==m2)
                {
                    if (d1==d2)
                        ans += nine[y1]+nine[m1]+nine[d1];
                    else
                    {
                        ans += mnine[flag][m2][d2] - mnine[flag][m1][d1]+nine[m2]+nine[d2];
                        cnt = mart[flag][m2][d2] - mart[flag][m1][d1]+1;
                        ans += nine[y1]*cnt;
                    }
                }
                else
                {
                    ans += mnine[flag][m2][d2] - mnine[flag][m1][d1]+nine[m2]+nine[d2];
                    cnt = mart[flag][m2][d2] - mart[flag][m1][d1]+1;
                    ans += nine[y1]*cnt;
                }
            }
            else
            {
                ans += np[y2] -np[y1+1];
                ans += (y2-y1-1)*65 + lp[y2]-lp[y1+1];
                ans += mnine[flag][12][31]-mnine[flag][m1][d1];
                cnt = 365 + flag -  mart[flag][m1][d1];
                ans += nine[y1]*cnt;
                cnt = 0;
                flag = leap(y2);
                ans += mnine[flag][m2][d2]+nine[m2]+nine[d2];
                cnt = mart[flag][m2][d2]+1;
                ans += nine[y2]*cnt;
            }
            printf("%d\n",ans);
	}
	return 0;
}

Codeforces 832D-Misha, Grisha and Underground(LCA)

Posted on 2018-12-21 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
http://codeforces.com/contest/832/problem/D

题目大意：
给定一棵树，每次给出一组查询a,b,c，求其中两点到另一点的最大重合路径长度

分析：

事实上，在一棵树上，由于不存在环，对任意的三点都存在上图的关系（存在一些情况，三点中某点与X重合），即三点之间互相到达的路径必定均经过某点X，那么要求的便是 $max(AX,BX,CX)$ ，由于在树上，根据LCA可以求得AB,BC,AC，列出方程

\begin{array}\left AX +CX = AC\\ AX +BX = AB\\ BX +CX = BC\\ \end{array}

一一解得AX,BX,CX即可，取最大值即是结果

代码：



//给一棵树，求两个节点的LCA
#include<iostream>
#include<map>
#include<cstring>

#define pii pair<int, int>

using namespace std;

const int N = 120005;

int fa[N];
map<pii, int> Q;
map<pii, int> Ans;
bool vis[N];
int root;
int n,q;

struct Edge{
    int u, v, nxt, ans;
}e[N * 2], ans[N*6];
int cnt, cntq;
int h[N], hq[N];

void init(){
    memset(h, -1, sizeof(h));
    memset(hq, -1, sizeof(hq));
    cnt = cntq = 0;
}

void add(int u, int v){
    e[cnt].v = v;
    e[cnt].nxt = h[u];
    h[u] = cnt++;
}

void addq(int u, int v){
    ans[cntq].ans = 0;
    ans[cntq].v = v;
    ans[cntq].nxt = hq[u];
    hq[u] = cntq++;
}

int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void tarjan(int u,int pre){
    int v;
    fa[u] = u;
    for(int k = h[u]; ~k; k = e[k].nxt){//后序遍历
        v = e[k].v;
        if (v==pre)
            continue;
        tarjan(v,u);
        fa[v] = u;//并入并查集
    }
    vis[u] = true;//后序遍历
    for(int k = hq[u]; ~k; k = ans[k].nxt){//查找LCA
        v = ans[k].v;
        if(vis[v]){
            Ans[make_pair(u,v)] = Ans[make_pair(v,u)] = find(v);//此处为u，v的LCA
        }
    }
}

int t;
const int maxn = 120000;
int deep[maxn];
int a[maxn],b[maxn],c[maxn];

void dfs(int u,int pos,int pre)
{
    deep[u] = pos;
    for (int i = h[u] ; i != -1 ; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v==pre)
            continue;
        dfs(v,pos+1,u);
    }
}



int main()
{
    memset(h,-1,sizeof(h));
    memset(hq,-1,sizeof(hq));

    scanf("%d%d",&n,&q);
    for (int i = 2 ; i <= n ; i ++)
    {
        scanf("%d",&t);
        add(i,t);
        add(t,i);
    }
    dfs(1,0,1);
    memset(vis, false, sizeof(vis));
    for (int i =1 ; i <= q ; i ++)
    {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        addq(a[i],b[i]);
        addq(b[i],a[i]);
        addq(b[i],c[i]);
        addq(c[i],b[i]);
        addq(a[i],c[i]);
        addq(c[i],a[i]);
    }
    tarjan(1,1);
    for (int i = 1; i <= q ; i ++)
    {
        int lab = deep[a[i]]+deep[b[i]]-2*deep[Ans[pii(a[i],b[i])]];
        int lac = deep[a[i]]+deep[c[i]]-2*deep[Ans[pii(a[i],c[i])]];
        int lbc = deep[b[i]]+deep[c[i]]-2*deep[Ans[pii(b[i],c[i])]];
        int p = (lab+lac+lbc)/2;
        int x = p - lab;
        int y = p - lac;
        int z = p - lbc;
        //printf("lab %d lac %d lbc %d\n",lab,lac,lbc);
        //printf("%d %d %d\n",x,y,z);
        printf("%d\n",max(x,max(y,z))+1);

        //printf("ab %d ac %d bc %d \n",Ans[pii(a[i],b[i])],Ans[pii(a[i],c[i])],Ans[pii(c[i],b[i])]);
    }


    return 0;
}

Hdu 3709 - Balanced Number

Posted on 2018-10-31 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3709

题目大意：
如果一个数，指定某一个数位为轴，左右两边数位和轴的距离定义为数位上数字与数位离轴所在数位的距离的乘积，如果轴左右两边数位的距离平衡，则是一个Balanced Number,求给定的 $[l,r]$ 区间内有多少个这样的数

分析：
显然是数位DP，由于每一位都可以是数轴，所以枚举轴的位置，然后记录一个距离和，大于轴位置的数位为正值，小于轴为负值，最后检查是否和为0即可，由于需要DP数组记忆化，所以和不能是负值，所以对和加上一个初值，使区间 $[-s,s]$ 的数映射到 $[-s+d,s+d]$ ，需要 $d>s$ ，由于左边最大的总距离和也就是 $(10+9+\dots+2+1)*9 <500$ ，所以随意开一个大于500的初值作为0即可

另外做的时候一直和样例不一样，怎么也调不出来，后来想到是前导零的问题，但是加上一个bool lead参数反而容易出更多问题，没想到什么好的办法解决，后来看了题解发现，0的问题主要在于在所有的数轴位置下，0都是算作符合条件的数，所以数字长度为 $len$ ，则0被多计算了 $len-1$ ，最后答案减去即可

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

ll l,r;
ll dp[20][20][4000];
int a[30],pos;


ll dfs(int pos,int pivot,int pre,bool limit)
{
    if (pos==-1)
    {
        if (pre!=2000)    return 0;
        else    return 1;
    }
    if (!limit&&dp[pos][pivot][pre]!=-1)    return dp[pos][pivot][pre];
    int up = limit?a[pos]:9;
    ll ans = 0;
    for (int i = 0 ; i <= up ; i ++)
    {
        ans += dfs(pos-1,pivot,pre+(pos-pivot)*i,limit&&i==a[pos]);
    }
    if (!limit) dp[pos][pivot][pre] = ans;
    return ans;
}

ll solve(ll x)
{
    pos = 0;
    while (x)
    {
        a[pos++] = x%10;
        x /= 10;
    }
    ll ans = 0;
    for (int i = 0 ; i < pos ; i ++)
    {
        ans += dfs(pos-1,i,2000,true);
        //printf("now ans = %lld \n",ans);
    }
    return ans-pos+1;
}

int main(){

    int T;
    scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    while (T--)
    {
        scanf("%I64d%I64d",&l,&r);
        printf("%I64d\n",solve(r)-solve(l-1));
    }
	return 0;
}

HDU 5572-An Easy Physics Problem （计算几何）

Posted on 2018-10-25 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5572

题目大意：
有一个无体积的球，近似为质点，一开始给出球的初始位置和运动方向（为从原点到给出点的向量方向），同时平面中有一个圆柱体，给出圆心位置和半径，若球撞击圆柱体，则产生以撞击点切线为反射面的无损反弹，求问球是否会经过给定的P点

分析：
大体上可以分成两类情况，球会撞击圆柱或者不会撞击圆柱
球什么情况下会撞击圆柱呢

球的运动轨迹与圆柱体有交点
交点为两个，一个为与圆相切，不发生撞击
圆柱体在球的初始位置的前进方向上，而不是后方

如果球未撞击圆柱，只有一种可能，点处于球的运动轨迹前方，即一条射线上，而球撞击圆柱则有两种可能

球在初始位置和撞击点（与初始位置较近的一个交点）经过P点
球在反弹后，在撞击点的前方射线经过P点

理清楚这几种可能后，直接上计算几何板子，调一下方法即可

代码：

#include<bits/stdc++.h>

using namespace std;

const double PI = acos(-1);

bool ok;
double ox, oy, r;
double px, py;
double vx, vy;
double tx, ty;
double xta1, xta2, xta3, xta4;

const double eps = 1e-7;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;

int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    else return 1;
}

inline double sqr(double x)
{
    return x*x;
}

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    void input(){
        scanf("%lf%lf",&x,&y);
    }
    void output(){
        printf("%2.f,%.2f\n",x,y);
    }
    bool operator == (Point b)const{
        return sgn(x-b.x)==0&& sgn(y-b.y)==0;
    }
    bool operator < (Point b)const{
        return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
    }
    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;
    }
    //点积
    double operator * (const Point &b)const{
        return x*b.x + y*b.y;
    }
    double len()
    {
        return hypot(x,y);
    }
    double len2()
    {
        return x*x+y*y;
    }

    double distance(Point p)
    {
        return hypot(x-p.x,y-p.y);
    }

    Point operator + (const Point & b) const
    {
        return Point(x+b.x,y+b.y);
    }

    Point operator *(const double& k)const{
        return Point(x*k,y*k);
    }

    Point operator / (const double &k) const{
        return Point(x/k,y/k);
    }
    double rad(Point a,Point b)
    {
        Point p = *this;
        return fabs(atan2 (fabs((a-p)^(b-p)),(a-p)*(b-p)));
    }

    Point trunc(double r)
    {
        double l = len();
        if (!sgn(l)) return *this;
        r /=l ;
        return Point (x*r,y*r);
    }

    Point rotleft(){
        return Point(-y,x);
    }

    Point rotright(){
        return Point(y,-x);
    }

    Point rotate(Point p,double angle)
    {
        Point v = (*this) - p;
        double c = cos(angle) , s = sin(angle);
        return Point(p.x+v.x*c - v.y*s,p.y+v.x*s + v.y*c);
    }

};

struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e)
    {
        s = _s;
        e = _e;
    }
    bool operator == (Line v)
    {
        return (s==v.s)&&(e==v.e);
    }
    Line (Point p,double angle)
    {
        s = p;
        if (sgn(angle - pi/2) == 0)
        {
            e = (s + Point(0,1));
        }
        else
            e = (s +Point(1,tan(angle)));
    }

    Line (double a,double b,double c)
    {
        if (sgn(a)==0)
        {
            s = Point(0,-c/b);
            e = Point(1,-c/b);
        }
        else if (sgn(b)==0)
        {
            s = Point(-c/a,0);
            e = Point(-c/a,1);
        }
        else
        {
            s = Point(0,-c/b);
            s = Point(1,(-c-a)/b);
        }
    }
    void input()
    {
        s.input();
        e.input();
    }

    void adjust()
    {
        if (e<s) swap(s,e);
    }

    double length()
    {
        return s.distance(e);
    }

    double angle(){
        double k = atan2(e.y-s.y,e.x-s.x);
        if (sgn(k)<0) k+= pi;
        if (sgn(k-pi)==0) k -= pi;
        return k;
    }

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

    bool pointonseg(Point p)
    {
        return sgn((p-s)^(e-s)) ==0 &&sgn((p-s)*(p-e))<=0;
    }

    bool parallel(Line v)
    {
        return sgn((e-s)^(v.e-v.s)) ==0;
    }

    int segcrossseg(Line v)
    {
        int d1 = sgn((e-s)^(v.s-s));
        int d2 = sgn((e-s)^(v.e-s));
        int d3 = sgn((v.e-v.s)^(s-v.s));
        int d4 = sgn((v.e-v.s)^(e-v.s));
        if ((d1^d2) ==-2 && (d3^d4)==-2 ) return 2;
        return (d1==0&& sgn((v.s-s)*(v.s-e))<=0)||
        (d2 ==0 && sgn((v.e-s)*(v.e-e))<=0)||
        (d3 ==0 && sgn((s-v.s)*(s-v.e))<=0)||
        (d4 ==0 && sgn((e-v.s)*(e-v.e))<=0);
    }

    Point crosspoint(Line v)
    {
        double a1 = (v.e-v.s)^(s-v.s);
        double a2 = (v.e-v.s)^(e-v.s);
        return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }

    double dispointtoline(Point p)
    {
        return fabs((p-s)^(e-s))/length();
    }

    double dispointtoseg(Point p)
    {
        if (sgn((p-s)*(e-s))<0|| sgn((p-e)*(s-e))<0)
            return min(p.distance(s),p.distance(e));
        return dispointtoline(p);
    }

    Point symmetrypoint(Point p)
    {
    	Point q = lineprog(p);
    	return Point(2*q.x-p.x,2*q.y-p.y);
    }

    Point lineprog(Point p)
    {
        return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()));
    }

};


struct circle{
    Point p;
    double r;
    circle() {}
    circle(Point _p , double _r)
    {
        p = _p;
        r = _r;
    }

    circle(Point a, Point b, Point c)
    {
        Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
        Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
        p = u.crosspoint(v);
        r = p.distance(a);
    }


    void input()
    {
        p.input();
        scanf("%lf",&r);
    }

    void output()
    {
        printf("%.2f,%.2f,%.2f\n",p.x,p.y,r);
    }

    bool operator == (circle v)
    {
        return (p==v.p)&&sgn(r-v.r)==0;
    }
    bool operator < (circle v)const
    {
        return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));
    }

    double area()
    {
        return pi*r*r;
    }

    double circumference()
    {
        return 2*pi*r;
    }

    int relation(Point b)
    {
        double dst = b.distance(p);
        if (sgn(dst-r)<0) return 2;
        else if (sgn(dst-r)==0) return 1;
        return 0;
    }

    int relationseg(Line v)
    {
        double dst = v.dispointtoseg(p);
        if (sgn(dst-r) < 0) return 2;
        else if (sgn(dst -r) ==0) return 1;
        return 0;
    }

    int relationline (Line v)
    {
        double dst = v.dispointtoline(p);
        if (sgn(dst-r)<0) return 2;
        else if (sgn(dst-r)==0) return 1;
        return 0;
    }

    int relationcircle(circle v)
    {
        double d = p.distance(v.p);
        if (sgn(d-r-v.r)>0) return 5;
        if (sgn(d-r-v.r)==0) return 4;
        double l = fabs(r-v.r);
        if (sgn(d-r-v.r)<0 && sgn(d-l)>0) return 3;
        if (sgn(d-l) ==0 ) return 2;
        if (sgn(d-l)< 0) return 1;
    }

    int pointcrosscircle(circle v,Point& p1,Point& p2)
    {
        int rel = relationcircle(v);
        if (rel==1 || rel==5) return 0;
        double d = p.distance(v.p);
        double l = (d*d+r*r-v.r*v.r)/(2*d);
        double h = sqrt(r*r-l*l);
        Point tmp = p+ (v.p-p).trunc(l);
        p1 = tmp + ((v.p-p).rotleft().trunc(h));
        p2 = tmp + ((v.p-p).rotright().trunc(h));
        if (rel==2 || rel ==4)
            return 1;
        return 2;
    }

    int pointcorssline(Line v, Point &p1 , Point &p2)
    {
        if (!(*this).relationline(v))   return 0;
        Point a = v.lineprog(p);
        double d = v.dispointtoline(p);
        d = sqrt(r*r-d*d);
        if (sgn(d)==0)
        {
            p1 = a;
            p2 = a;
            return 1;
        }
        p1 = a + (v.e-v.s).trunc(d);
        p2 = a - (v.e-v.s).trunc(d);
        return 2;

    }


};

int main(){
	int T;
	scanf("%d", &T);
	for(int t = 1; t <= T; t++){
        circle cir;
        cir.input();
        Point points,pointv,pointt;
        points.input();
        pointv.input();
        vx = pointv.x;
        vy = pointv.y;
		pointt.input();

		Point pointe(points.x+vx,points.y+vy);

		ok = false;

		Line linep(points,pointe);  //构造直线


		bool flag = false;
        Point p,q;
        int res = cir.pointcorssline(linep,p,q);
        if (sgn(px-tx)==0&&sgn(py-ty)==0)
            flag = true;
        else if (res==2 && sgn(p.x - px) == sgn(vx) && sgn(p.y - py) == sgn(vy))   // 直线与圆相交
        {

            double dis1 = p.distance(points);
            double dis2 = q.distance(points);
            if(dis1 > dis2) swap(p,q);
            Line tpl(points,p);
            if (tpl.pointonseg(pointt))
            {
                flag = true;
            }
            else
            {
                Point symp = Line(cir.p,p).symmetrypoint(points);
                Line reflect(symp,p);
                double nvx = symp.x - p.x , nvy = symp.y - p.y;
                int nrels = reflect.relation(pointt);
                if (nrels==3&&sgn(pointt.x-p.x)==sgn(nvx)&&sgn(pointt.y-p.y)==sgn(nvy))
                {
                    flag = true;
                }
                else
                    flag = false;
            }

        }
        else   //相切 相离 或者未在前进方向上相交
        {
            int rels = linep.relation(pointt);
            if (rels==3&&sgn(pointt.x-points.x)==sgn(vx)&&sgn(pointt.y-points.y)==sgn(vy))// 点在直线上
            {
                flag = true;
            }
            else
                flag = false;

        }
		printf("Case #%d: ", t);
		if(flag) puts("Yes");
		else puts("No");
	}
}

HDU 5573-Binary Tree (构造)

Posted on 2018-10-10 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5573

题目大意：
有一棵二叉树，根结点值为1，左子结点为 $2*i$ ,右子结点为 $2*i+1$ ，给出n和k，求在二叉树上从根向下共走k步，每步可以为当前结点权值取正号或者负号，求一种使最终取值和为n的可行方案

分析：
通过打表每一个数的构成方式可以发现，每一个数都可以由序列 $1,2,4,8....(2^{k-1},2^{k-1}+1)$ 通过取正负，或者最后一项取奇偶来得到，不妨大胆假设从根开始每次取左子结点，可以取到所有$1,3,5,7,\dots 2^k-1 $ 等所有 $2^k-1$ 内的奇数，那么在此基础上，最后一层不取 $2^{k-1}$ ，转而取右子结点 $2^{k-1}+1$ ，即可构造出 $2^k$ 以内的所有偶数，而题意写明, $N\leq 2^K$ ，所以任意的N均可以由此方式构造得到

那么实际上这个过程就类似整数的二进制表示，1表示加，0表示减，如果该位为0，那么意味着在 $2^k−1$ 的基础上减去了二倍改为代表的数，所以我们求出n与 $2^k−1$ 的差，将差的一半的二进制中为1的位置为0即可
注意偶数的时候，差为奇数，那么我们将差多加个一，让最后一步走右边的结点，即加一即可

另外贪心也是可以的，由于当前层结点的值大于上层所有父结点的权值和，所以如果当前总权值<N，必须加上当前层结点，否则减去，依次递推即可得到一种方案，若最后得到的当前权值总和不为N，说明最后要取 $2^{k-1}+1$ ，将最后一项改变即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>


using namespace std;

long long bm[100];
long long n,temp,now;
int k;
void init()
{
    bm[0] = 1;
    for (int i = 1 ; i <= 61 ; i ++)
        bm[i] = bm[i-1]*2;
}
long long path[100];
char f[100];


int main()
{
    init();
    int T,t=1;
    scanf("%d",&T);
    while (T--)
    {
        temp = 0;
        scanf("%lld%d",&n,&k);
        now = bm[k-1];
        printf("Case #%d:\n",t++);
        for (int i = 1 ; i <= k ; i ++)
        {
            path[i] = now;
            if (temp<n)
                temp += now,f[i] = '+';
            else
                temp -= now,f[i] = '-';
            now /= 2;
        }
        if (temp==n)
        {
            for (int i = k ; i >= 1 ; --i)
                printf("%lld %c\n",path[i],f[i]);
            continue;
        }
        path[1] = bm[k-1]+1;
        for (int i = k ; i >= 1 ; --i)
            printf("%lld %c\n",path[i],f[i]);
        continue;

    }
  return 0;

}

Hdu 1024 Max Sum Plus Plus(基础DP)

Posted on 2018-10-03 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1024

题目大意：
给定n个数，找出m段连续序列和的最大值，序列之间不可相交

分析：
一开始并没有什么思路，后来看了一下kuangbin的题解，发现转移式其实就是

dp[i][j] = \max(dp[i][j-1],\max(dp[i-1][k] , i-1\leq{k}\leq{j-1}))+a[j]

dp[i][j] 表示取a[j]，并且分为i段的最大序列和，显然它等于之前同样分成i段的dp[i][j-1]末尾再添一个数，或者之前的数分成i-1段，a[j]单独成一段，两者取最大值

但是实际上这样时间复杂度是够的，空间复杂度是不够的，先不说dp数组第二维就是百万级，还是long long 的数据，第一维还未知，这题实际上给的内存要求非常严格，第一次交开了5个1e6的long long 数组，马上就MLE了，于是需要优化。

观察可以发现，转移式里其实只用到了 $dp[i][j-1]$ 和 $\max(dp[i-1][i-1]~dp[i-1][j-1])$ ，所以其实只需要开两个数组即可，一个保存当前dp数组，另一个数组maxx保存之前一层dp的前缀最大值信息 $maxx[k] = \max(dp[i-1][i-1]~dp[i-1][k])$

注意初始化和求最大值时maxx[i-1]先设负无穷即可
代码：

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long ll;
const int maxn = 1020000;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n,m;
ll dp[maxn],maxx[maxn];
int arr[maxn];

int main()
{
    int t = 1 ;
    while (~scanf("%d%d",&m,&n))
    {
        memset(dp,0,sizeof(dp));
        memset(maxx,0,sizeof(maxx));
        for (int i = 1 ; i <= n ; i ++)
        {
            scanf("%d",&arr[i]);
        }
        for (int i = 1 ; i <= m ; i ++)
        {
            maxx[i-1] = -INF;
            for (int j = i ; j <= n ; j ++)
                dp[j] = max(dp[j-1],maxx[j-1])+arr[j];
                maxx[i-1] = -INF;
            for (int j = i ; j <= n ; j ++)
                maxx[j] = max(dp[j],maxx[j-1]);
        }
        ll ans = -INF;
        for (int i = m ; i <= n ; i ++)
        {
            ans = max(ans,dp[i]);
        }
        printf("%lld\n",ans);
    }

    return 0;
}

Hdu 4063-Aircraft(计算几何+最短路）

Posted on 2018-09-24 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4063

题目大意：
有n个圆，给出圆心和半径，第一个和最后一个圆的圆心分别为起点和终点，求起点是否可达终点，且路径上所有点必须在给出的圆内或圆上

分析：
画图可以发现，从起点出发的最短路径，必定经过圆心，或者两圆的交点，所以找出所有的两圆并去重，然后任意两点之间检查是否可达。

可达性的检查为，作出两点间的线段，同时检查该线段所在直线与所有圆的交点，保存在线段上的交点，最后对所有交点排序，若相邻两交点间的线段被某个圆包括则合法，否则非法，该两点不可达，不可建边。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wZyRpKCI-1622049927811)(http://hi.csdn.net/attachment/201110/7/6627258_1317988620BYI7.jpg)]
两点之间的边的权值即是两点距离，然后对于建出的图直接跑dij或spfa即可，由于一开始排序去重了，点的顺序被打乱，所以需要一次遍历找回起点和终点，即与第一个和最后一个圆的圆心相同的点。

代码：
注：直接套了kuangbin的计算几何板子，很长

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;

int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    else return 1;
}

inline double sqr(double x)
{
    return x*x;
}

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    void input(){
        scanf("%lf%lf",&x,&y);
    }
    void output(){
        printf("%2.f,%.2f\n",x,y);
    }
    bool operator == (Point b)const{
        return sgn(x-b.x)==0&& sgn(y-b.y)==0;
    }
    bool operator < (Point b)const{
        return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
    }
    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;
    }
    //点积
    double operator * (const Point &b)const{
        return x*b.x + y*b.y;
    }
    double len()
    {
        return hypot(x,y);
    }
    double len2()
    {
        return x*x+y*y;
    }

    double distance(Point p)
    {
        return hypot(x-p.x,y-p.y);
    }

    Point operator + (const Point & b) const
    {
        return Point(x+b.x,y+b.y);
    }

    Point operator *(const double& k)const{
        return Point(x*k,y*k);
    }

    Point operator / (const double &k) const{
        return Point(x/k,y/k);
    }
    double rad(Point a,Point b)
    {
        Point p = *this;
        return fabs(atan2 (fabs((a-p)^(b-p)),(a-p)*(b-p)));
    }

    Point trunc(double r)
    {
        double l = len();
        if (!sgn(l)) return *this;
        r /=l ;
        return Point (x*r,y*r);
    }

    Point rotleft(){
        return Point(-y,x);
    }

    Point rotright(){
        return Point(y,-x);
    }

    Point rotate(Point p,double angle)
    {
        Point v = (*this) - p;
        double c = cos(angle) , s = sin(angle);
        return Point(p.x+v.x*c - v.y*s,p.y+v.x*s + v.y*c);
    }

};

struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e)
    {
        s = _s;
        e = _e;
    }
    bool operator == (Line v)
    {
        return (s==v.s)&&(e==v.e);
    }
    Line (Point p,double angle)
    {
        s = p;
        if (sgn(angle - pi/2) == 0)
        {
            e = (s + Point(0,1));
        }
        else
            e = (s +Point(1,tan(angle)));
    }

    Line (double a,double b,double c)
    {
        if (sgn(a)==0)
        {
            s = Point(0,-c/b);
            e = Point(1,-c/b);
        }
        else if (sgn(b)==0)
        {
            s = Point(-c/a,0);
            e = Point(-c/a,1);
        }
        else
        {
            s = Point(0,-c/b);
            s = Point(1,(-c-a)/b);
        }
    }
    void input()
    {
        s.input();
        e.input();
    }

    void adjust()
    {
        if (e<s) swap(s,e);
    }

    double length()
    {
        return s.distance(e);
    }

    double angle(){
        double k = atan2(e.y-s.y,e.x-s.x);
        if (sgn(k)<0) k+= pi;
        if (sgn(k-pi)==0) k -= pi;
        return k;
    }

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

    bool pointonseg(Point p)
    {
        return sgn((p-s)^(e-s)) ==0 &&sgn((p-s)*(p-e))<=0;
    }

    bool parallel(Line v)
    {
        return sgn((e-s)^(v.e-v.s)) ==0;
    }

    int segcrossseg(Line v)
    {
        int d1 = sgn((e-s)^(v.s-s));
        int d2 = sgn((e-s)^(v.e-s));
        int d3 = sgn((v.e-v.s)^(s-v.s));
        int d4 = sgn((v.e-v.s)^(e-v.s));
        if ((d1^d2) ==-2 && (d3^d4)==-2 ) return 2;
        return (d1==0&& sgn((v.s-s)*(v.s-e))<=0)||
        (d2 ==0 && sgn((v.e-s)*(v.e-e))<=0)||
        (d3 ==0 && sgn((s-v.s)*(s-v.e))<=0)||
        (d4 ==0 && sgn((e-v.s)*(e-v.e))<=0);
    }

    Point crosspoint(Line v)
    {
        double a1 = (v.e-v.s)^(s-v.s);
        double a2 = (v.e-v.s)^(e-v.s);
        return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }

    double dispointtoline(Point p)
    {
        return fabs((p-s)^(e-s))/length();
    }

    double dispointtoseg(Point p)
    {
        if (sgn((p-s)*(e-s))<0|| sgn((p-e)*(s-e))<0)
            return min(p.distance(s),p.distance(e));
        return dispointtoline(p);
    }

    Point lineprog(Point p)
    {
        return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()));
    }

};


struct circle{
    Point p;
    double r;
    circle() {}
    circle(Point _p , double _r)
    {
        p = _p;
        r = _r;
    }

    circle(Point a, Point b, Point c)
    {
        Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
        Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
        p = u.crosspoint(v);
        r = p.distance(a);
    }


    void input()
    {
        p.input();
        scanf("%lf",&r);
    }

    void output()
    {
        printf("%.2f,%.2f,%.2f\n",p.x,p.y,r);
    }

    bool operator == (circle v)
    {
        return (p==v.p)&&sgn(r-v.r)==0;
    }
    bool operator < (circle v)const
    {
        return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));
    }

    double area()
    {
        return pi*r*r;
    }

    double circumference()
    {
        return 2*pi*r;
    }

    int relation(Point b)
    {
        double dst = b.distance(p);
        if (sgn(dst-r)<0) return 2;
        else if (sgn(dst-r)==0) return 1;
        return 0;
    }

    int relationseg(Line v)
    {
        double dst = v.dispointtoseg(p);
        if (sgn(dst-r) < 0) return 2;
        else if (sgn(dst -r) ==0) return 1;
        return 0;
    }

    int relationline (Line v)
    {
        double dst = v.dispointtoline(p);
        if (sgn(dst-r)<0) return 2;
        else if (sgn(dst-r)==0) return 1;
        return 0;
    }

    int relationcircle(circle v)
    {
        double d = p.distance(v.p);
        if (sgn(d-r-v.r)>0) return 5;
        if (sgn(d-r-v.r)==0) return 4;
        double l = fabs(r-v.r);
        if (sgn(d-r-v.r)<0 && sgn(d-l)>0) return 3;
        if (sgn(d-l) ==0 ) return 2;
        if (sgn(d-l)< 0) return 1;
    }

    int pointcrosscircle(circle v,Point& p1,Point& p2)
    {
        int rel = relationcircle(v);
        if (rel==1 || rel==5) return 0;
        double d = p.distance(v.p);
        double l = (d*d+r*r-v.r*v.r)/(2*d);
        double h = sqrt(r*r-l*l);
        Point tmp = p+ (v.p-p).trunc(l);
        p1 = tmp + ((v.p-p).rotleft().trunc(h));
        p2 = tmp + ((v.p-p).rotright().trunc(h));
        if (rel==2 || rel ==4)
            return 1;
        return 2;
    }

    int pointcorssline(Line v, Point &p1 , Point &p2)
    {
        if (!(*this).relationline(v))   return 0;
        Point a = v.lineprog(p);
        double d = v.dispointtoline(p);
        d = sqrt(r*r-d*d);
        if (sgn(d)==0)
        {
            p1 = a;
            p2 = a;
            return 1;
        }
        p1 = a + (v.e-v.s).trunc(d);
        p2 = a - (v.e-v.s).trunc(d);
        return 2;

    }


}c[50];

const int MAXN = 1000;
const int MAXM = 500000;

Point arr[5000];
int n,pc;
struct Edge{
    int from, to, next;
    double val;
    int id;
}edge[MAXM];

struct Node{
    int x;
    double  d;
    Node(){}
    Node( int a, double b ): x( a ), d( b ){}
    bool operator < ( Node a ) const{
        return d > a.d;
    }
};

int head[MAXN],cnt;
double dis[MAXN];

void init(){
    cnt = 0;
    for (int i = 0 ; i < MAXN ; i ++)
        dis[i] = inf;
    memset( head, -1, sizeof( head ) );
}

void add( int from, int to, double val ){
    edge[cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].val = val;
    edge[cnt].next = head[from];
    head[from] = cnt++;
}

void dij( int s ){
    dis[s] = 0;

    priority_queue<Node> Q;
    Q.push( Node( s, dis[s] ) );

    while( !Q.empty() ){
        Node temp = Q.top(); Q.pop();
        int x = temp.x;
        if( temp.d > dis[x] ) continue;
        for( int k = head[x]; ~k; k = edge[k].next ){
            int y = edge[k].to;
            if( dis[y] > dis[x] + edge[k].val ){
                dis[y] = dis[x] + edge[k].val;
                Q.push( Node( y, dis[y] ) );
            }
        }
    }
}



bool check(Point a,Point b)
{
    if (b<a)
        swap(a,b);
    Point cs[500],p,q;
    int pt = 0;
    Line u = Line(a,b);
    for (int i = 1 ; i <= n ; i ++)
    {

        int res = c[i].pointcorssline(u,p,q);
        if (res==1&&u.pointonseg(p))
            cs[++pt] = p;
        else if (res==2)
        {
            if (u.pointonseg(p))
                cs[++pt] = p;
            if (u.pointonseg(q))
                cs[++pt] = q;
        }
    }
    sort(cs+1,cs+pt+1);
    pt = unique(cs+1,cs+pt+1) -cs - 1;
    for (int i = 2 ; i <= pt ; i ++)
    {
//        if ((cs[i]<a)||(b<cs[i]))
//            continue;
        int flag = 0;
        Point mid = Point((cs[i-1].x+cs[i].x)/2,(cs[i-1].y+cs[i].y)/2);
        for (int j = 1 ; j <= n ; j ++)
        {
            if (sgn(mid.distance(c[j].p)-c[j].r)<=0)
            {
//                cs[i-1].output();
//                cs[i].output();
//                c[j].output();
                flag = 1;
                break;
            }
        }
        if (!flag)
            return false;
    }
    return true;
}




int main()
{
    int T,t=1;
    Point p,q;
    scanf("%d",&T);
    while (T--)
    {
        init();
        scanf("%d",&n);
        for (int i = 1;  i <= n ; i ++)
        {
            c[i].input();
            arr[i] = c[i].p;
        }
        pc = n;
        for (int i = 1 ; i <= n ; i ++)
        {
            for (int j = i + 1 ; j <= n ; j ++)
            {
                int res = c[i].pointcrosscircle(c[j],p,q);
                if (res==1)
                    arr[++pc] = p;
                else if (res==2)
                {
                    arr[++pc] = p;
                    arr[++pc] = q;
                }
            }
        }
        sort(arr+1,arr+pc+1);
       // printf("pre pc = %d\n",pc);
        pc = unique(arr+1,arr+pc+1)- arr - 1;
       // printf("after pc = %d\n",pc);
        int st,ed;
        for (int i = 1 ; i <= pc ; i ++)
        {
            if (arr[i]==c[1].p) st = i;
            if (arr[i]==c[n].p) ed = i;
        }
       // printf("st= %d\ted= %d\n",st,ed);
        for (int i = 1 ; i <= pc ; i ++)
        {
            for (int j = i + 1; j <= pc ; j ++)
            {
                if (check(arr[i],arr[j]))
                {
                    //printf("-------------\n");
                    //arr[i].output();
                    //arr[j].output();
                    //printf("dis = %f\n",arr[i].distance(arr[j]));
                    //printf("-------------\n");

                    add(i,j,arr[i].distance(arr[j]));
                    add(j,i,arr[i].distance(arr[j]));

                }
            }
        }
        printf("Case %d: ",t++);
        dij(st);
        if (sgn(dis[ed]-inf)==0)
            printf("No such path.\n");
        else
            printf("%.4f\n",dis[ed]);




    }
    return 0;

}

Hdu 2859 - Phalanx (基础dp)

Posted on 2018-08-12 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2859

题目大意：
给定一个字符方阵，求最大的一个子方阵的大小，使得其以副对角线为轴完全对称

分析：
直接从上至下 $O(n^2)$ 遍历，对 $dp[i][j]$ ，查看位置 $(i,j)$ 上方和右方的总匹配数 $cnt$ （不包括自身），若大于 $dp[i-1][j-1]$ ，则 $dp[i][j]$ 更新为 $dp[i-1][j-1]+1$ ，否则 $dp[i][j] = cnt+1$

实际上一开始想到的就是这种做法，但是估算复杂度是 $O(n^3)$ ， $1\leq n \leq 1000$ ，大约1e9的复杂度，所以一开始估计过不了，就没继续想，后来看题解才发现这题是5s的题，1e9绰绰有余，实在应该再仔细点的

代码：

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long ll;

const int maxn = 1200;

int n;
char mat[maxn][maxn];
int dp[maxn][maxn];

int main()
{
    while (~scanf("%d",&n)&&n)
    {
        memset(dp,0,sizeof(dp));
        for (int i = 1 ; i <= n ; i ++)
        {
            scanf("%s",mat[i]+1);
        }
        int maxx = 1;
        for (int i = 1 ; i <=n ; ++i)
        {
            for (int j = 1 ; j <= n ; j ++)
            {
                if (i==1||j==n)
                {
                    dp[i][j] = 1;
                    continue;
                }
                int cnt = 0;
                for (int k = 1 ; k +j<=n && i - k>=1 ; k ++)
                {
                    if (mat[i-k][j]==mat[i][j+k])
                        cnt++;
                    else
                        break;
                }
                if (cnt>=dp[i-1][j+1])
                    dp[i][j] = dp[i-1][j+1]+1;
                else
                    dp[i][j] = cnt+1;
                maxx = max(dp[i][j],maxx);
            }
        }
        printf("%d\n",maxx);
    }

    return 0;
}

Hdu 6113 - 度度熊的01世界(搜索)

Posted on 2018-07-14 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6113

题目大意：
给定一个01矩阵，给出数字0和1的定义，判断给出的图形是0还是1或是-1

分析：
根据题意，如果不止一个1的连通块，肯定不是数字0或1，一定是-1，可以先判掉，然后考虑怎么判断1的连通块中间包围的0的连通块个数，这时候边界上的0可能会对我们的结果造成干扰，所以先遍历整个边界，然后再对剩下的0进行搜索，对连通块计数，0个就是1，1个就是0，多于1个就是-1，如果1形成一个U型与边界相交，按照题目的定义，不算包围，会在遍历边界的时候把中间的0遍历掉，在寻找0的连通块的时候，就只会遍历到0个包围的连通块了

代码：

//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

int n,m;
char mat[200][200];
int vis[200][200];

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};


bool check(int i,int j)
{
    if (i>=1&&i<=n&&j>=1&&j<=m) return true;
    else return false;
}

void dfs(int x,int y,char ch)
{
    vis[x][y] = 1;
    for (int i = 0 ; i< 4 ; i ++)
    {
        if (check(x+dx[i],y+dy[i])&&!vis[x+dx[i]][y+dy[i]]&&mat[x+dx[i]][y+dy[i]]==ch)
            dfs(x+dx[i],y+dy[i],ch);
    }
    return;

}



int main(){
    int T;

    while (~scanf("%d%d",&n,&m))
    {
        memset(vis,0,sizeof(vis));
        for (int i = 1 ; i <= n ; i ++)
            scanf("%s",mat[i]+1);
        for (int i = 1 ; i <= n ; i ++)
        {
            if (!vis[i][1]&&mat[i][1]=='0')
                dfs(i,1,'0');
            if (!vis[i][m]&&mat[i][m]=='0')
                dfs(i,m,'0');
        }
        for (int i = 1 ; i <= m ; i ++)
        {
            if (!vis[1][i]&&mat[1][i]=='0')
                dfs(1,i,'0');
            if (!vis[n][i]&&mat[n][i]=='0')
                dfs(n,i,'0');
        }
        int cnt = 0;
        for (int i = 1 ; i <= n ; i ++)
        {
            for (int j = 1 ; j <= m ; j ++)
            {
                if (mat[i][j] =='1'&&!vis[i][j])
                {
                    cnt++;
                    dfs(i,j,'1');
                }
            }
        }
        if (cnt!=1)
        {
            printf("-1\n");
            continue;
        }
        cnt = 0;
        for (int i = 1 ; i <= n ; i ++)
        {
            for (int j = 1 ; j <= m ; j ++)
            {
                if (!vis[i][j]&&mat[i][j]=='0')
                {
                    cnt ++;
                    dfs(i,j,'0');
                }
            }
        }
        if (cnt==0)
            printf("1\n");
        else if (cnt==1)
            printf("0\n");
        else
            printf("-1\n"); 

    }
    return 0;
}

CodeForces - 610A-G - Pasha and Stick-思维

Posted on 2018-07-13 Edited on 2023-05-08 In 算法 , 刷题

题目链接：
http://codeforces.com/problemset/problem/610/A

题目大意：
给定一个长度L，将其分为4段，要求能组成一个矩形，不能组成正方形，有多少种方案

分析：
首先奇数肯定不能切隔组成矩形，需要特判，偶数中，若同时为4的倍数，说明矩形的长与宽之和为偶数，可能出现长与宽相等，所以总情况数减少一种

代码：

#include  <cstdio>

int main(){
    int n;
    scanf("%d",&n);
    printf("%d\n",n%2?0:((n%4?0:-1)+n/4));
    return 0;
}