2019-10-29

T1

T1可能（一定）在某些大佬的眼中就是一道送分题（然而我只有10分）

明眼人都看得出来这是一道拓展欧几里得的题目，我们知道系数\(a,b\)，要求解方程\(ax+by=c\) 并且使得\(|x|+|y|\)取得最小值

我们知道拓展欧几里得可以求解\(ax+by=gcd(a,b)\)，并且如果有某一正数c满足\(c\)%\(gcd(a,b)==0\)，令\(k=c/gcd(a,b)\) 那么显然\(akx+bky=c\) 令\(x=kx,y=ky\) 我们现在相当于求解\(|x|+|y|\)

对于一个方程 显然\(ax+by=gcd(a,b)\)与\(a(x-nb)+b(y+na)=x\)是等价的 因此我们可以将我们用拓展欧几里得求出来的特殊解通过这种变形，求得满足条件的解。而如果要满足条件的话，我们需要让\(x-nb\)接近于0 或者令\(y+na\)接近于0

假设\(a<b\) 显然如果x变化了 那么对于 y的变化是很小的 因此如果让a的未知数x接近于0，对于y的影响是比较小的，那么可以优化一下，将问题简化一下（即在开始的时候 \(if(a<b) swap(a,b)\))

然后就可以做了（其实不要上面的优化也可以）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long 
using namespace std;
const int maxn=200010;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();};
    return x*f;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(a%b==0){
        x=1;y=0;return b;
    }
    ll d=exgcd(b,a%b,x,y),t;
    t=y-a/b*x;
    y=x;
    x=t;
    return d;
}
ll n,num[maxn],a,b;
int main()
{
//  freopen("array.in","r",stdin);
//  freopen("arrayown.out","w",stdout);
    n=read();a=read();b=read();
    if(a<b) a^=b^=a^=b;
    ll d,x,y,ans=0;
    d=exgcd(a,b,x,y);
    a/=d;b/=d;
    //这里一定要除哦 不然要WA 
    for(ll i=1;i<=n;i++){
        num[i]=read();
        if(abs(num[i])%d)   
            return printf("-1"),0;
        ll X=x*(num[i]/d),Y=y*(num[i]/d);
        swap(X,Y);
        //x对应的系数大 y对应的系数小
        //因为要改变y 使得y 尽量为接近零的数 
        if(Y<0){//使得Y变正 
            X-=b*((-Y)/a+1);
            Y+=a*((-Y)/a+1);
        }
        X+=b*((Y)/a);
        Y-=a*((Y)/a);
        ans=ans+min(abs(X)+abs(Y),abs(X+b)+abs(Y-a));
    }
    printf("%lld",ans);
}

T2

咕咕咕

#include<bits/stdc++.h>
#define L long long
#define vi vector<int>
#define pb push_back
using namespace std;
int n,m,w[200010],p;
L f[800010],g[800010];
struct orz
{
    int a,b,p;
}x[100010];
inline bool cmp(orz a,orz b)
{
    return a.a+a.b<b.a+b.b;
}
inline void down(int i)
{
    f[i<<1]+=g[i];
    g[i<<1]+=g[i];
    f[i<<1|1]+=g[i];
    g[i<<1|1]+=g[i];
    g[i]=0;
}
inline L query(int i,int j,int k,int p)
{
    if(j==k)
      return f[i];
    down(i);
    if(p<=j+k>>1)
      return query(i<<1,j,j+k>>1,p);
    else
      return max(f[i<<1],query(i<<1|1,(j+k>>1)+1,k,p));
}
inline void maxx(int i,int j,int k,int p,L q)
{
    f[i]=max(f[i],q);
    if(j!=k)
      {
       down(i);
       if(p<=j+k>>1)
         maxx(i<<1,j,j+k>>1,p,q);
       else
         maxx(i<<1|1,(j+k>>1)+1,k,p,q);
      }
}
inline void add(int i,int j,int k,int l,int r,int p)
{
    if(l<=j && k<=r)
      {
       f[i]+=p;
       g[i]+=p;
      }
    else
      {
       down(i);
       if(l<=(j+k>>1))
         add(i<<1,j,j+k>>1,l,r,p);
       if(r>(j+k>>1))
         add(i<<1|1,(j+k>>1)+1,k,l,r,p);
       f[i]=max(f[i<<1],f[i<<1|1]);
      }
}
int main()
{
    freopen("pair.in","r",stdin);
    freopen("pair.out","w",stdout);
    int i,j;
    L k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
      {
       scanf("%d%d%d",&x[i].a,&x[i].b,&x[i].p);
       w[++m]=x[i].a;
       w[++m]=x[i].b;
      }
    sort(w+1,w+m+1);
    m=unique(w+1,w+m+1)-w;
    for(i=1;i<=n;i++)
      {
       x[i].a=lower_bound(w+1,w+m,x[i].a)-w;
       x[i].b=lower_bound(w+1,w+m,x[i].b)-w;
      }
    sort(x+1,x+n+1,cmp);
    for(p=1;p<m;p<<=1);
    for(i=1;i<=n;i++)
      {
       j=min(x[i].a,x[i].b);
       k=query(1,1,p,j)+x[i].p;
       maxx(1,1,p,x[i].a,k);
       if(x[i].b>x[i].a)
         add(1,1,p,x[i].a+1,x[i].b,x[i].p);
      }
    printf("%lld\n",f[1]);
    return 0;
}

T3

这道题的话呢 在大佬眼中这就是一道板子题 但是蒟蒻调了好久（原因竟是m条边只输入了n条）

emmm 首先对于两个特殊点之间距离的转移，要不就是他们直接连接，要不就是他们不直接连接，并且通过其他的点转移过来（注意，只有可能由其他不是特殊点的点转移过来，因为如果是从其他特殊点转移过来，显然会更劣 因为转移过来的特殊点显然更优）

因此可以启发我们用多源最短路，然后对于一条边的两个端点，如果是由不同的特殊点转移过来，那么就可以更新这两个特殊点的ans

至于证明。。

不难证明，对于源点i，由i拓展的点j以及与j相邻且不由i拓展的点k，
如果i的最优路径从j走到了k，那么走到拓展k的源点是最优的。因此这个做
法是正确的。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define LL long long 
#define int long long
using namespace std;
const LL maxn=400010;
LL read(){
    LL x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node
{
    int dis;
    int pos;
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
};
priority_queue<node> q;
LL n,m,p,spe[maxn],tot=1,from[maxn],dis[maxn],ans[maxn<<1];
LL fir[maxn<<1],nxt[maxn<<1],to[maxn<<1],val[maxn<<1],inque[maxn<<1];
void add(LL x,LL y,LL z){
    nxt[++tot]=fir[x];fir[x]=tot;to[tot]=y;val[tot]=z;
    nxt[++tot]=fir[y];fir[y]=tot;to[tot]=x;val[tot]=z;
}
void dij()
{
    int rp,des;
    for(int i=1;i<=p;i++)
        q.push(node{0,spe[i]});
    while(!q.empty())
    {
        node tmp=q.top();
        q.pop();
        int x=tmp.pos;int y=tmp.dis;
        if(inque[x])    continue;
        inque[x]=true;
        for(rp=fir[x];rp;rp=nxt[rp])
        {
            des=to[rp];
            if(dis[des]>y+val[rp]){
            dis[des]=y+val[rp];
            from[des]=from[x];
            if(inque[des]==false)
            {
                q.push( ( node ){dis[des], des} );
            }
            }
                
        }
    }
}
signed main(){
//  freopen("distance.in","r",stdin);
//  freopen("distanceown.out","w",stdout);
    n=read();m=read();p=read();
    for(LL i=1;i<=p;i++)
        spe[i]=read();
    for(LL i=1,x,y,z;i<=m;i++){
        x=read();y=read();z=read();
        add(x,y,z);
    }
    for(LL i=1;i<=n;i++)
        dis[i]=1e18,ans[i]=1e18;
    for(LL i=1;i<=p;i++)
        dis[spe[i]]=0,from[spe[i]]=spe[i];
    dij();
    for(LL x=1;x<=n;x++){
        for(LL i=fir[x];i;i=nxt[i]){
            LL y=to[i];
            if(from[x]!=from[y])
                ans[from[x]]=min(ans[from[x]],dis[x]+dis[y]+val[i]);
        }
    }
    for(LL i=1;i<=p;i++)
    {
        if(i!=p)
            printf("%lld ",ans[spe[i]]);
        else printf("%lld\n",ans[spe[i]]);
    }
    return 0;
}

大概这就是今天的题吧，说实话不难，但是因为做的同类型的题太少了 导致今天的整体情况差的鸭痞

2019-10-29

原文：https://www.cnblogs.com/mendessy/p/11761044.html