头像

Tyouchie




离线:2019-11-15 05:36



Tyouchie
2019-11-01 07:36

在这里推销一下博客 总结了常见距离计算公式的计算方法
这个题目不过是 欧氏距离 也就是欧几里得距离
还有一些切比雪夫距离 或者 曼哈顿距离 或者二者 之间的转化
一些基本模型的转换 https://www.cnblogs.com/Tyouchie/p/11769313.html
如果 博客里有什么问题 欢迎指出

C++ 代码

#include<bits/stdc++.h>
typedef long long ll;
const ll N=1100;
ll T,n,h,r,x[N],y[N],z[N],father[N],d[N],u[N];
template<typename T>inline void read(T &x)
{
    x=0;T f=1,ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
}
inline long long dis(ll i,ll j) {
    return (ll)(x[i]-x[j])*(x[i]-x[j])+(ll)(y[i]-y[j])*(y[i]-y[j])+(ll)(z[i]-z[j])*(z[i]-z[j]); 
}
ll fa[N + 5];
ll find(ll x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void Union(ll x, ll y) {
    fa[find(x)]=find(y);
}

signed main() {
    read(T);
    while(T--) {
        read(n);read(h);read(r);
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        memset(z,0,sizeof(z));
        memset(u,0,sizeof(u));
        memset(d,0,sizeof(d));
        for(ll i=1;i<=n;++i) fa[i]=i; 
        for(ll i=1;i<=n;++i) read(x[i]), read(y[i]), read(z[i]);
        for(ll i=1;i<=n;++i)
            for(ll j=1;j<i;++j)
                if(dis(i,j)<=(ll)4*r*r)
                    Union(i,j);
        bool flag=0;
        for(ll i=1;i<=n;++i) {
            if(z[i]-r<=0) d[find(i)]=1;
            if(z[i]+r>=h) u[find(i)]=1;
        }
        for(int i=1;i<=n;++i)
        {
            if(d[i]&&u[i])flag=1;
            if(flag)break;
        }
        puts(flag ? "Yes" : "No");
    }
    return 0;
}



Tyouchie
2019-10-31 03:45

说白了 这个题目就是dp中悬线法的一个求解最大合法矩阵的一个问题
可以使用单调栈优化 不过 直接n^2 没有问题
https://www.cnblogs.com/Tyouchie/p/11382288.html
曾经总结过的小计 如果不熟悉 可以学习一下 不过如果会的
直接看code8

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1010][1010],l[1010][1010],r[1010][1010],up[1010][1010];
char s[1010][1010]; 
template<typename T>inline void read(T &x) {
    x=0;T f=1,ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
}
int main() {
    read(n); read(m);
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1);
        for(int j=1;j<=m;j++) {
            if(s[i][j]=='F') a[i][j]=0;
            else a[i][j]=1;
            l[i][j]=r[i][j]=j;
            up[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=2;j<=m;j++) {
            if(!a[i][j]&&!a[i][j-1]) {
                l[i][j]=l[i][j-1];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=m-1;j>=1;j--) {
            if(!a[i][j]&&!a[i][j+1]) {
                r[i][j]=r[i][j+1];
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(i>1&&!a[i][j]&&!a[i-1][j]) {
                l[i][j]=max(l[i][j],l[i-1][j]);
                r[i][j]=max(r[i][j],r[i-1][j]);
                up[i][j]=up[i-1][j]+1;
            }
            ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);
        }
    }
    cout<<ans*3<<endl;
    return 0;
}



Tyouchie
2019-09-27 00:01

关于后缀中缀前缀表达式计算
https://www.cnblogs.com/Tyouchie/p/11570638.html




Tyouchie
2019-08-31 22:45

期望题目
设f[x] 表示从x出发 所经过的 路径 期望长度
若从x出发有k条边 所以f[y]=1/k∑(f[x]+zi);
显然 f[n]=1;

C++ 代码

//f[x]表示从x节点走到终点期望路经长度 
//f[n]==0
//终点是一切概率的结束 也是一切期望的开始; 
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x) {
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
const int N=200100;
int n,m,x,y,v,tot,deg[N],out[N],lin[N];
double f[N];
struct gg {
    int y,next,v;
}a[N<<1];
inline void add(int x,int y,int v) {
    a[++tot].y=y;
    a[tot].next=lin[x];
    lin[x]=tot;
    a[tot].v=v;
}
queue<int>q; 
int main() {
    read(n); read(m);
    for(int i=1;i<=m;i++) {
        read(x); read(y); read(v);
        deg[x]++,out[x]++;
        add(y,x,v);
    } 
    q.push(n);
    while(q.size()) {
        int x=q.front();q.pop();
        for(int i=lin[x];i;i=a[i].next) {
            int y=a[i].y;
            f[y]+=(f[x]+a[i].v)/deg[y];
            out[y]--;
            if(!out[y]) q.push(y);
        }
    }
    printf("%.2lf\n",f[1]);
}



Tyouchie
2019-08-21 04:16

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int n,m,tot,lin[N],v[N],w[N],root,p;
int f[1010][1010];//表示将i为根的子树内选取了容量为j的物品所获得的最大价值; 
struct gg {
    int y,next;
}a[N];
inline void add(int x,int y) {
    a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot;
}
inline void dfs(int x) {
    for(int i=lin[x];i;i=a[i].next) {
        int y=a[i].y;
        dfs(y);
        for(int j=m-v[x];j>=v[y];j--) {
            for(int k=v[y];k<=j;k++) {
                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
            }
        }
    }
    for(int i=m;i>=v[x];i--) {
        f[x][i]=f[x][i-v[x]]+w[x];
    }
    for(int i=0;i<v[x];i++) {
        f[x][i]=0;
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%d%d%d",&v[i],&w[i],&p);//体积价值;
        if(p==-1) root=i;
        else add(p,i);
    }
    dfs(root);
    cout<<f[root][m];
    return 0; 
}



Tyouchie
2019-08-09 05:48

费用流练习的题目,跑了EK;

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=20010;
const int inf=1000000000;
int dis[N],lin[N],vis[N],incf[N],pre[N],s,t,ans,maxflow,tot=1,n,m,h[55][55];
template<typename T>inline void read(T &x) {
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
struct gg {
    int y,next,flow,c;
}a[N];
inline void add(int x,int y,int flow,int c) {
    a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot; a[tot].flow=flow; a[tot].c=c;
    a[++tot].y=x; a[tot].next=lin[y]; lin[y]=tot; a[tot].flow=0; a[tot].c=-c;
}
inline bool spfa() {
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=t;i++) dis[i]=-inf;
    queue<int> q; 
    q.push(s); vis[s]=1; dis[s]=0;
    incf[s]=1<<30;
    while(q.size()) {
        int x=q.front(); q.pop(); vis[x]=0;
        for(int i=lin[x];i;i=a[i].next) {
            int y=a[i].y;
            if(!a[i].flow) continue;
            if(dis[y]<dis[x]+a[i].c) {
                dis[y]=dis[x]+a[i].c;
                incf[y]=min(incf[x],a[i].flow);//incf[x]; 
                pre[y]=i;
                if(!vis[y]) {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
    if(dis[t]==-inf) return false;
    return true;
}
inline void update() {
    int x=t;
    while(x!=s) {
        int i=pre[x];
        a[i].flow-=incf[t];
        a[i^1].flow+=incf[t];
        x=a[i^1].y;
    }
    maxflow+=incf[t];
    ans+=dis[t]*incf[t];
}
inline int num(int x,int y) {
    return (x-1)*m+y;
}
int main() {
    read(n); read(m);
    tot=1;
    s=n*m<<1|1,t=s+1;
    add(s,1,2,0);//要求两条路径;
    add(2*n*m,t,2,0);//收流是也是两条;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            read(h[i][j]);
            add(num(i,j),num(i,j)+n*m,1,h[i][j]);
            if(j+1<=m) add(num(i,j)+n*m,num(i,j+1),inf,0);
            if(i+1<=n) add(num(i,j)+n*m,num(i+1,j),inf,0);
        }
    add(1,n*m+1,inf,0);
    add(num(n,m),num(n,m)+n*m,inf,0);
    while(spfa()) update();
    cout<<ans<<endl;
    return 0;
} 



Tyouchie
2019-08-02 07:39

四维飘过

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int f[55][55][55][55],n,m,a[55][55];
#define max(x,y) ((x)>(y)?(x):(y))
#define max4(x,y,w,z) max(max(x,y),max(w,z))
template<typename T>inline void read(T &x) {
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
int main() {
    read(n); read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            read(a[i][j]);
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++)
            for(int k=1;k<=n;k++)
                for(int l=1;l<=m;l++) {
                    f[i][j][k][l]=max4(f[i-1][j][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k][l-1],f[i][j-1][k-1][l])+a[k][l]+a[i][j];
                    if(i==k||j==l) f[i][j][k][l]-=a[i][j];
                }
    cout<<f[n][m][n][m]<<endl;
    return 0;
}

三维飘过

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 55
using namespace std;
int f[2*maxn][maxn][maxn];
int a[maxn][maxn];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int k=1;k<=n+m-1;k++)
        for(int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
            {
                if(k-i+1<1||k-j+1<1)    continue;
                f[k][i][j]=max(max(f[k-1][i][j],f[k-1][i-1][j-1]),max(f[k-1][i][j-1],f[k-1][i-1][j]))+a[i][k-i+1]+a[j][k-j+1];
                if(i==j)    f[k][i][j]-=a[i][k-i+1];
            }
    cout<<f[n+m-1][n][n]<<endl;
    return 0;
}



Tyouchie
2019-08-01 09:07

佩服nlogn的大根堆的做法;
但是这里只有n方的做法qwq;
正如lyd大佬的话,取自算法竞赛进阶指南;
B序列中所有数都在A中出现过;
证明:
对于n=1,显然成立。
设定理对N=k-1成立,
对于n=k-1时假设其满足由原数列的数构成最优解。那么,考虑对于n=k。
如果Bk-1<=Ak,那么令Bk=Ak即可;
否则Bk=Bk-1;命题仍成立,也可以结合中位数的知识;
我们设f[i][j]表示处理出来的序列长度为i,并且B的最后一位是j时的最小代价;
那么我们有转移方程:f[i][j]=min(f[i-1][k])+|Ai-j|(0=<k<=j);
书上说需要离散化,只需要知道j枚举的范围即可,所以我并没有写lower_bound;】
只是排了个序,去了个重;
然后我们将原序列翻转一下,在做一次dp,就得到了另一种情况,取min即可;

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,f[2010][2010];
int n,m,A[2010],a[2010];
template<typename T>inline void read(T &x) {
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
inline void dp() {
    for(int i=1;i<=n;i++) {
        ll minn=f[i-1][1];
        for(int j=1;j<=m;j++) {
            minn=min(minn,f[i-1][j]);
            f[i][j]=minn+abs(A[j]-a[i]);
        }
    }
}
int main() {
    read(n);
    for(int i=1;i<=n;i++) {
        read(a[i]);
        A[i]=a[i];
    }
    sort(A+1,A+n+1); m=unique(A+1,A+n+1)-A-1;
    dp();
    ans=f[n][1];
    for(int i=2;i<=m;i++) ans=min(ans,f[n][i]);
    reverse(a+1,a+n+1);
    dp();
    for(int i=1;i<=m;i++) ans=min(ans,f[n][i]);
    printf("%lld\n",ans);
}



Tyouchie
2019-07-31 00:27

博客题解:https://www.cnblogs.com/Tyouchie/p/10385615.html
题目描述
太鼓达人的鼓坏了,现在vani来修鼓。

鼓的主要元件是 M 个围成一圈的传感器。

每个传感器都有开和关两种工作状态,分别用 1 和 0 表示。

显然,从不同的位置出发沿顺时针方向连续检查 K 个传感器可以得到 M 个长度为 K 的 01 串。

Vani 知道这 M 个 01 串应该是互不相同的。

而且鼓的设计很精密,M 会取到可能的最大值。

现在 Vani 已经了解到了 K 的值,他希望你求出 M 的值,并给出字典序最小的传感器排布方案。

输入格式

一个整数K。

输出格式

一个整数和一个二进制串,由一个空格分隔,分别表示可能的最大的 M 以及字典序最小的排布方案。
字符 0 表示关,1 表示开,你输出的串的第一个字和最后一个字是相邻的。

数据范围
2≤K≤11
输入样例:
3
输出样例:
8 00010111

算法
题意:给出k,求一个最长的M位01串,使其从每一个位置向后走k个得到的M个k位01串互不相同(最后一个和第一个相邻,即是一个环)。输出字典序最小的答案。 2 ≤ k ≤ 11。
反正就是 结论+爆搜;
第二问我们将每个k二进制数看成一个点,在它后面加上0/1就能得 到两个新数,我们从这个数向两个新数连边,于是这就变成了求一个欧拉回路的问题。
显然此题是存在欧拉回路的第一问答案为2的k次方 ,第二问暴力求欧拉回路即可。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+50;
template<typename T>inline void read(T &x)
{
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch) && ch^'-') ch=getchar();
    if (ch=='-') f=-1, ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
int n,t,ans[maxn];
bool used[maxn];
inline bool eular(int x,int k)//x是当前子串的十进制表示,k是当前查询次
{
    if(used[x]) return 0;
    used[x]=1,ans[k]=x&1;//统计答案,&的规则是:有零则零,否则为一,返回末位数字
    if(k==t) return 1;//查询结束
    if(eular((x<<1)&(t-1),k+1)) return 1;
    if(eular((x<<1|1)&(t-1),k+1)) return 1;//将每个二进制数看成一个点,将他前面的数删去,并在它后面加上0/1就能得到两个新数
    used[x]=0;//回溯,以免影响之后的dfs
    return 0;
}
int main()
{
    read(n);
    t=1<<n;
    printf("%d ",t);
    eular(t-2,1);//从每位走n位子串,可得到的完整子串数量为2^n-2
    for(int i=1;i<=t;++i)
        printf("%d",ans[i]);
    return 0;
}



Tyouchie
2019-07-30 02:47

https://www.cnblogs.com/Tyouchie/p/10426016.html

题目描述

现代社会,路是必不可少的。

共有n个城镇,m条道路,任意两个城镇都有路相连,而且往往不止一条。

但有些路年久失修,走着很不爽。

按理说条条大路通罗马,大不了绕行其他路呗——可小撸却发现:从a城到b城不管怎么走,总有一些逃不掉的必经之路。

他想请你计算一下,a到b的所有路径中,有几条路是逃不掉的?

输入格式

第一行是n和m,用空格隔开。

接下来m行,每行两个整数x和y,用空格隔开,表示x城和y城之间有一条长为1的双向路。

第m+2行是q。

接下来q行,每行两个整数a和b,用空格隔开,表示一次询问。

输出格式
对于每次询问,输出一个正整数,表示a城到b城必须经过几条路。

每个输出占一行。

数据范围

n≤105,m≤2∗105,q≤105
对于全部的数据,1≤x,y,a,b≤n;对于任意的道路,两端的城市编号之差不超过104;
任意两个城镇都有路径相连;同一条道路不会出现两次;道路的起终点不会相同;查询的两个城市不会相同。

输入样例:
5 5
1 2
1 3
2 4
3 4
4 5
2
1 4
2 5
输出样例:
0
1
思路:
既然是求必须经过的边,那么边双包含的集合肯定不是必须经过的,就可以把所有边双缩点;

原图得到一颗树后,问题就变成了简单的求树上两点之间的距离。

这个题就是lca+边双的题啦:

注意:

边双连通分量缩点后,原图变成一颗真正的树,而树上各种操作可以和其他知识点结合起来。

这种敏感性要有,比如缩点之后就可以快速求必经边,必经点之类的。

鬼知道我因为a和e打错调了多长时间;

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
template<typename T>inline void read(T &x) {
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
struct gg {
    int y,next,v;
}a[N<<1],e[N<<1];
int tot=1,tc=1;
int n,m,q,x,y,num,dcc;
int d[N],f[N][25],dfn[N],low[N],lin[N],linc[N],bridge[N<<1],c[N];
inline void add(int x,int y) {
    a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot;
}
inline void tarjan(int x,int in_edge) {
    dfn[x]=low[x]=++num;
    for(int i=lin[x];i;i=a[i].next) {
        int y=a[i].y;
        if(!dfn[y]) {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]) {
                bridge[i]=bridge[i^1]=1;
            }
        }
        else if(i!=(in_edge^1))
            low[x]=min(low[x],dfn[y]);
    } 
}
inline void dfs(int x) {//求出每个边双; 
    c[x]=dcc;
    for(int i=lin[x];i;i=a[i].next) {
        int y=a[i].y;
        if(c[y]||bridge[i]) continue;
        dfs(y);
    }
}
inline void add_c(int x,int y) {
    e[++tc].y=y; e[tc].next=linc[x]; linc[x]=tc;
}
inline void bfs() {
    queue<int> q;
    q.push(1);d[1]=1;
    while(q.size()) {
        int x=q.front();q.pop();
        for(int i=linc[x];i;i=e[i].next) {
            int y=e[i].y;
            if(d[y]) continue;
            d[y]=d[x]+1;
            f[y][0]=x;
            for(int j=1;j<=23;j++)
                f[y][j]=f[f[y][j-1]][j-1];
            q.push(y);
        }
    }
}
inline int lca(int x,int y) {
    if(d[x]>d[y]) swap(x,y);
    for(int i=23;i>=0;i--)
        if(d[f[y][i]]>=d[x]) y=f[y][i];
    if(x==y) return x;
    for(int i=23;i>=0;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main() {
    read(n); read(m);
    for(int i=1;i<=m;i++) {
        read(x); read(y);
        add(x,y); add(y,x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i,-1);
    for(int i=1;i<=n;i++) {
        if(!c[i]) {
            ++dcc;
            dfs(i);
        }
    }
    for(int i=2;i<=tot;i++) {
        int x=a[i^1].y,y=a[i].y;
        if(c[x]==c[y]) continue;
        add_c(c[x],c[y]);
        add_c(c[y],c[x]);
    } 
    bfs();
    read(q);
    while(q--) {
        read(x); read(y);
        x=c[x]; y=c[y];
        printf("%d\n",d[x]+d[y]-2*d[lca(x,y)]);
    }
    return 0;
}