头像

acwing_gza

$1.刷完基础课√\\2.天梯前5页\\3.刷完提高课√\\4.刷完CSP-J辅导课√\\5.刷完算法竞赛进阶指南(77/329)(暂停)\\6.刷完usaco辅导课(33/98)(暂停)\\小六$




离线:1小时前


最近来访(2515)
用户头像
tfszMitrs
用户头像
lenglitest
用户头像
陌上花开Charlie
用户头像
Heaven_and_Hell
用户头像
AcWing2AK
用户头像
lsz_
用户头像
蓬蒿人
用户头像
acwing_3992
用户头像
凉晨_6
用户头像
晚安_43
用户头像
冰中月
用户头像
进击的橡皮熊
用户头像
万能青年旅店
用户头像
7.9省赛加油
用户头像
喝怡宝的农夫
用户头像
凌钧
用户头像
v_egetable
用户头像
Sky390
用户头像
Pzt
用户头像
2001f


acwing_gza
2小时前

更加人性化了一些,现在math和tu和geometric中的内容需要自己加上math:: tu:: geometric::,删除了dx,dy数组,以便于应对更加一般的情况

#include<bits/stdc++.h>
using namespace std;
#define R read()
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define inf 0x3f3f3f3f
#define mod1 1000000007
#define mod2 998244353
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define m1(a,b) memset(a,b,sizeof a)
#define m2(a,b) memcpy(a,b,sizeof b)
using ld = long double;
using str = string;
using pi = pair<int,int>;
using pd = pair<ld,ld>;
using vi = vector<int>;
using vb = vector<bool>;
using vd = vector<ld>; 
using vs = vector<str>;
using vpi = vector<pi>;
using vpd = vector<pd>;
const ld PI = acos((ld)-1);
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
namespace IO{
    inline int read()
    {
        int X=0; bool flag=1; char ch=getchar();
        while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
        while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
        if(flag) return X;
        return ~(X-1);
    }
    inline void write(int X)
    {
        if(X<0) {X=~(X-1); putchar('-');}
        if(X>9) write(X/10);
        putchar(X%10+'0');
    }
}
namespace math{
    int lowbit(int x)  
    {
        return x & -x;
    }
    int qmi(int a,int k,int p)
    {
        int res=1%p;
        while(k)
        {
            if(k&1) res=res*a%p;
            a=a*a%p;
            k>>=1;
        }
        return res;
    }
    bool is_prime(int x)  
    {
        if (x < 2) return false;
        for (int i = 2; i <= x / i; i ++ )
            if (x % i == 0)
                return false;
        return true;
    }
    int gcd(int a,int b)
    {
        return b?gcd(b,a%b):a;
    }
    int exgcd(int a,int b,int &x,int &y) 
    {
        if(!b)
        {
            x=1;y=0;
            return a;
        }
        int d=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return d;
    }
    vector<int> add(vector<int> &A, vector<int> &B)  // C = A + B, A >= 0, B >= 0
    {
        if (A.size() < B.size()) return add(B, A);
        vector<int> C;
        int t = 0;
        for (int i = 0; i < A.size(); i ++ )
        {
            t += A[i];
            if (i < B.size()) t += B[i];
            C.push_back(t % 10);
            t /= 10;
        }
        if (t) C.push_back(t);
        return C;
    }
    vector<int> sub(vector<int> &A, vector<int> &B)  // C = A - B, 满足A >= B, A >= 0, B >= 0
    {
        vector<int> C;
        for (int i = 0, t = 0; i < A.size(); i ++ )
        {
            t = A[i] - t;
            if (i < B.size()) t -= B[i];
            C.push_back((t + 10) % 10);
            if (t < 0) t = 1;
            else t = 0;
        }

        while (C.size() > 1 && C.back() == 0) C.pop_back();
        return C;
    }
    vector<int> mul(vector<int> &A,vector<int> &B)  // C = A * B, A >= 0, b >= 0
    {
        vector<int> C;

        int t = 0, v = 1;
        for (int i = 0; i < A.size() || t; i ++ )
        {
            v = i + 1;
            if (i < A.size()) {
                vector<int> ans;
                int b = A[i], t1 = 0;
                for (int j = 0; j < B.size() || t1; j ++ , v ++ )
                {
                    if (j < B.size()) t1 += b * B[j];
                    if (v >= C.size()) C.push_back(t1 % 10);
                    else {
                        C[v] += t1;
                        C[v] %= 10;
                    }
                    t1 /= 10;
                }
            }

        }

        while (C.size() > 1 && C.back() == 0) C.pop_back();

        return C;
    }
    vector<int> mul(vector<int> &A, int b)  // C = A * b, A >= 0, b >= 0
    {
        vector<int> C;

        int t = 0;
        for (int i = 0; i < A.size() || t; i ++ )
        {
            if (i < A.size()) t += A[i] * b;
            C.push_back(t % 10);
            t /= 10;
        }

        while (C.size() > 1 && C.back() == 0) C.pop_back();

        return C;
    }
    vector<int> div(vector<int> &A, int b, int &r)  // A / b = C ... r, A >= 0, b > 0
    {
        vector<int> C;
        r = 0;
        for (int i = A.size() - 1; i >= 0; i -- )
        {
            r = r * 10 + A[i];
            C.push_back(r / b);
            r %= b;
        }
        reverse(C.begin(), C.end());
        while (C.size() > 1 && C.back() == 0) C.pop_back();
        return C;
    }
    int phi(int x) 
    {
        int res = x;
        for (int i = 2; i <= x / i; i ++ )
            if (x % i == 0)
            {
                res = res / i * (i - 1);
                while (x % i == 0) x /= i;
            }
        if (x > 1) res = res / x * (x - 1);

        return res;
    }
}
namespace tu{
    int h[100010],w[100010],e[100010],ne[100010],idx;
    void add(int a,int b)
    {
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }
    void add(int a,int b,int c)
    {
        e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    }
}
int ff(int x)
{
    return (int)(pow(10,x))+10;
}
namespace geometric{
    const double eps = 1e-8;
    int sign(double x)  // 符号函数
    {
        if (fabs(x) < eps) return 0;  // x为0,则返回0
        if (x < 0) return -1;  // x为负数,则返回-1
        return 1;  // x为正数,则返回1
    }
    int dcmp(double x, double y)  // 比较两数大小
    {
        if (fabs(x - y) < eps) return 0;  // x == y, 返回0
        if (x < y) return -1;  // x < y, 返回-1
        return 1;  // x > y, 返回1
    }
    pd operator+ (pd a, pd b)  // 向量加法
    {
        return {a.x + b.x, a.y + b.y};
    }
    pd operator- (pd a, pd b)  //  向量减法
    {
        return {a.x - b.x, a.y - b.y};
    }
    pd operator* (pd a, double t)  // 向量数乘
    {
        return {a.x * t, a.y * t};
    }
    pd operator/ (pd a, double t)  // 向量除以常数
    {
        return {a.x / t, a.y / t};
    }
    double operator* (pd a, pd b)  // 外积、叉积
    {
        return a.x * b.y - a.y * b.x;
    }
    double operator& (pd a, pd b)  // 内积、点积
    {
        return a.x * b.x + a.y * b.y;
    }
    double area(pd a, pd b, pd c)  // 以a, b, c为顶点的有向三角形面积
    {
        return (b - a) * (c - a);
    }
    double get_len(pd a)  // 求向量长度
    {
        return sqrt(a & a);
    }
    double get_dist(pd a, pd b)  // 求两个点之间的距离
    {
        return get_len(b - a);
    }
    double project(pd a, pd b, pd c)  // 求向量ac在向量ab上的投影
    {
        return ((c - a) & (b - a)) / get_len(b - a);
    }
    pd rotate(pd a, double b)  // 向量a逆时针旋转角度b
    {
        return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
    }
    pd norm(pd a)  // 矩阵标准化(将长度变成1)
    {
        return a / get_len(a);
    }
    bool on_segment(pd p, pd a, pd b)  // 点p是否在线段ab上(包含端点a、b)
    {
        return !sign((p - a) * (p - b)) && sign((p - a) & (p - b)) <= 0;
    }
    pd get_line_intersection(pd p, pd v, pd q, pd w)  // 求两直线交点:p + vt, q + wt
    {
        auto u = p - q;
        auto t = w * u / (v * w);
        return p + v * t;
    }
}
using namespace IO;

signed main(){
    return 0;
}

281行。



新鲜事 原文

壮哉,我深搜中国,与天不老;我中国深搜,与国无疆


新鲜事 原文

今天毕业典礼,好紧张



选择最佳路线:
有一天,琪琪想乘坐公交车去拜访她的一位朋友。

由于琪琪非常容易晕车,所以她想尽快到达朋友家。

现在给定你一张城市交通路线图,上面包含城市的公交站台以及公交线路的具体分布。

已知城市中共包含 $n$ 个车站(编号$1$~$n$)以及 $m$ 条公交线路。

每条公交线路都是 单向的,从一个车站出发直接到达另一个车站,两个车站之间可能存在多条公交线路。

琪琪的朋友住在 $s$ 号车站附近。

琪琪可以在任何车站选择换乘其它公共汽车。

请找出琪琪到达她的朋友家(附近的公交车站)需要花费的最少时间。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含三个整数 $n,m,s$,分别表示车站数量,公交线路数量以及朋友家附近车站的编号。

接下来 $m$ 行,每行包含三个整数 $p,q,t$,表示存在一条线路从车站 $p$ 到达车站 $q$,用时为 $t$。

接下来一行,包含一个整数 $w$,表示琪琪家附近共有 $w$ 个车站,她可以在这 $w$ 个车站中选择一个车站作为始发站。

再一行,包含 $w$ 个整数,表示琪琪家附近的 $w$ 个车站的编号。

输出格式

每个测试数据输出一个整数作为结果,表示所需花费的最少时间。

如果无法达到朋友家的车站,则输出 -1。

每个结果占一行。

数据范围

$n \le 1000, m \le 20000$,
$1 \le s \le n$,
$0 < w < n$,
$0 < t \le 1000$

输入样例:

5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1

输出样例:

1
-1

这道题目有一个特点,就是有多个起点。
我们可以建立一个虚拟的原点,把原点向所有起点连一条边,价值为0,这样就不会影响答案。
所以,直接以虚拟原点为起点,做一遍spfa。
代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include<bits/stdc++.h>
using namespace std;
const int N = 1010,M=40010;
int n,m,T;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];
bool st[N];
void add(int a,int b,int c)//加边操作
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa() //求最短路
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    int hh = 0, tt = 1;
    q[0] = 0;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])   
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    if (dist[T] == 0x3f3f3f3f) return -1;
    return dist[T];
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&T)!=-1)//有多组测试数据
    {
        memset(h,-1,sizeof h);
        memset(st, 0, sizeof st);
        idx=0;
        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a, b, c);//原来就有的边
        }
        int s;
        scanf("%d",&s);
        while(s--)
        {
            int ver;
            scanf("%d",&ver);//输入多个原点
            add(0,ver,0);//建立价值为0的边
        }
        printf("%d\n",spfa());
    }
    return 0;
}



day1:
设$x+y=c$

$c^3=x^3+y^3+3x^2y+3xy^2 $

$=x^3+y^3+3xy(x+y)$

$=x^3+y^3+3bc$

$=c^3$

$=>x^3+y^3=c^3-3bc$

$a=c^3-3bc$

移项

$c^3-3bc-a=0$

令$c=u+v$其中u和v是任取的,把这个式子代入方程,我们得到

$(u+v)^3+3b(u+v)-a=0$
展开
$u^3+3u^2v+3uv^2+v^3+3bu+3bv-a=0$
提取公因式
$u^3+v^3+3uv(u+v)+3b(u+v)-a=0$
提取公因式
$u^3+v^3+(u+v)(3uv+3b)-a=0$
因为u和v是任取的,令$3uv+3b=0$
则有
$uv=-b$
$u^3+v^3=a$
令$M=u^3,N=v^3$则
$MN=-b^3$
$M+N=a$
推一下
$M=\frac{a+\sqrt{a^2+4v^3}}{2}$
$N=\frac{a-\sqrt{a^2+4v^3}}{2}$
所以
$u={(\frac{a+\sqrt{a^2+4v^3}}{2}})^{\frac{1}{3}}$
$v={(\frac{a-\sqrt{a^2+4v^3}}{2}})^{\frac{1}{3}}$
所以
$c=u+v={(\frac{a+\sqrt{a^2+4v^3}}{2})}^{\frac{1}{3}}+{(\frac{a-\sqrt{a^2+4v^3}}{2})}^{\frac{1}{3}}$

day2:
简单:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N],q[N];
int l,r,mid,len;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
    {
        l=0,r=len;
        while(l<r)
        {
            mid=l+r+1>>1;
            if(q[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len,r+1);
        q[r+1]=a[i];
    }
    cout<<len;
    return 0;
}


新鲜事 原文

屏幕在深夜微微发亮 思想在那虚树路径上彷徨 平面的向量交错生长 织成 忧伤的网 剪枝剪去我们的疯狂 SPFA告诉我前途在何方 01背包装下了忧伤 笑颜 洋溢脸庞 键盘微凉 鼠标微凉 指尖流淌 代码千行 凸包周长 直径多长 一进考场 全都忘光 你在OJ上提交了千百遍 却依然不能卡进那时限 双手敲尽代码也敲尽岁月 只有我一人 写的题解 凋零在OJ里面 tarjan陪伴强联通分量 生成树完成后思路才闪光 欧拉跑过的七桥古塘 让你 心驰神往 队列进出图上的方向 线段树区间修改求出总量 可持久留下的迹象 我们 俯身欣赏 数论算法 图论算法 高斯费马 树上开花 线性规划 动态规划 时间爆炸 如何优化 我在OI中辗转了千百天 却不让我看AK最后一眼 我用空间换回超限的时间 随重新编译 测完样例 才发现漏洞满篇 原来CE 是因选错语言 其实爆0 只因忘写文件 如果标算太难请坚定信念 不如回头再看一眼题面 以那暴力模拟向正解吊唁 蒟蒻的蜕变 神犇出现 终将与Au擦肩 屏幕在深夜微微发亮 我心在考场 人生就像动态规划,你的一个又一个阶段是由上天安排的。而你,决定的是在这一阶段可以由上一阶段的哪些状态转移而来。越勤奋,越幸运,并不代表这一次你决策的方向有多么优秀。却代表着现在的这一个状态能够续写多少可能的结果。人生就像复杂的无向图,我们虽然不能找到最短路,但是我们能不断搜索。TLE之前,没有一个节点叫失败。


分享 $$\Huge .$$

$$\color{white}{哈哈,太棒了,经过几天的训练,跳绳1分钟又可以跳大约210下了。}$$



分享 .

$$\color{white}{诶,大了,跳绳一分钟只能跳个180~190了}$$
$$\color{white}{手骨折了好了以后还是不行}$$



活动打卡代码 AcWing 4269. 校庆

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 4269. 校庆

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~