「CF715X」Codeforces Round #372 (Div. 1)

2016年9月19日4,4770

A. Plus and Square Root

推公式可得，可构造每次按完的数为 i * (i+1)

#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
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;
}
int n;
ll x=2;
int main()
{
    n=read();
    for(ll i=1;i<=n;i++)
    {
        ll ans=(i+1)*(i+1)*i-x/i;
//        cout<<ans<<' '<<(ll)sqrt(x+ans*i)<<endl;
        x=i*(i+1);
        cout<<ans<<endl;
    }
    return 0;
}

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

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;

}

int n;

ll x=2;

int main()

{

n=read();

for(ll i=1;i<=n;i++)

{

ll ans=(i+1)*(i+1)*i-x/i;

// cout<<ans<<' '<<(ll)sqrt(x+ans*i)<<endl;

x=i*(i+1);

cout<<ans<<endl;

}

return 0;

}

B. Complete The Graph

给一张无向图，要求赋值一些边的边权，使得最终S到T的最短路为L

用f(i,j)表示从S到点i，经过j条无边权的边的最短路

选择一个最小的j，使得f(T,j) + j <= L

更改这条路径上的边权，使得最短路为L，将其它无边权的边赋值为L

可以证明不会产生其它的最短路

似乎还可以采取一些暴力调整的做法，写起来会短一些

#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 9000000000000000000LL
#define ll long long
#define pa pair<ll,int>
using namespace std;
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;
}
int n,m,L,s,t;
int a[1005][1005],p[1005][1005];
ll dis[1005][1005];
int u[10005],v[10005],w[10005];
bool vis[1000005];
priority_queue<pa,vector<pa>,greater<pa> >q;
void pre()
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<n;j++)
            dis[i][j]=inf;
    q.push(make_pair(0,(s-1)*n+1));
    dis[s][0]=0;
    while(!q.empty())
    {
        int now=q.top().second;q.pop();
        int x=(now-1)/n+1,y=(now-1)%n;
        if(vis[now])continue;vis[now]=1;
        for(int i=1;i<=n;i++)
            if(i!=x)
            {
                int ny=y+(a[x][i]==0),id=(i-1)*n+ny+1;
                if(a[x][i]!=-1&&dis[x][y]+a[x][i]<dis[i][ny]&&!vis[id])
                {
                    dis[i][ny]=dis[x][y]+a[x][i];
                    q.push(make_pair(dis[i][ny],id));
                    p[i][ny]=x;
                }
            }
    }
}
int flag=0;
void dfs(int x,int y,int D)
{
    int fa=p[x][y];
    if(x==s)return;
    if(a[fa][x]==0)
    {
        y--;
        if(flag==0)
        {
            flag=1;
            a[fa][x]=a[x][fa]=D;
        }
        else a[fa][x]=a[x][fa]=1;
    }
    dfs(fa,y,D);
}
bool solve()
{    
    if(dis[t][0]<L)return 0;
    if(dis[t][0]==L)return 1;
    for(int i=1;i<n;i++)
        if(dis[t][i]+i<=L)
        {
            dfs(t,i,L-dis[t][i]-i+1);
            return 1;
        }
    return 0;
}
int main()
{
    memset(a,-1,sizeof(a));
    n=read();m=read();L=read();s=read();t=read();
    s++;t++;
    for(int i=1;i<=m;i++)
    {
        u[i]=read();v[i]=read();w[i]=read();
        u[i]++;v[i]++;
        a[u[i]][v[i]]=a[v[i]][u[i]]=w[i];
    }
    pre();
    if(!solve())
    {
        puts("NO");
        return 0;
    }
    else puts("YES");
    for(int i=1;i<=m;i++)
    {
        w[i]=a[u[i]][v[i]];
        if(!a[u[i]][v[i]])w[i]=L;
        u[i]--;v[i]--;
        cout<<u[i]<<' '<<v[i]<<' '<<w[i]<<endl;
    }
    return 0;
}

100

101

102

103

104

105

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 9000000000000000000LL

#define ll long long

#define pa pair<ll,int>

using namespace std;

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;

}

int n,m,L,s,t;

int a[1005][1005],p[1005][1005];

ll dis[1005][1005];

int u[10005],v[10005],w[10005];

bool vis[1000005];

priority_queue<pa,vector<pa>,greater<pa> >q;

void pre()

{

for(int i=1;i<=n;i++)

for(int j=0;j<n;j++)

dis[i][j]=inf;

q.push(make_pair(0,(s-1)*n+1));

dis[s][0]=0;

while(!q.empty())

{

int now=q.top().second;q.pop();

int x=(now-1)/n+1,y=(now-1)%n;

if(vis[now])continue;vis[now]=1;

for(int i=1;i<=n;i++)

if(i!=x)

{

int ny=y+(a[x][i]==0),id=(i-1)*n+ny+1;

if(a[x][i]!=-1&&dis[x][y]+a[x][i]<dis[i][ny]&&!vis[id])

{

dis[i][ny]=dis[x][y]+a[x][i];

q.push(make_pair(dis[i][ny],id));

p[i][ny]=x;

}

int flag=0;

void dfs(int x,int y,int D)

{

int fa=p[x][y];

if(x==s)return;

if(a[fa][x]==0)

{

y--;

if(flag==0)

{

flag=1;

a[fa][x]=a[x][fa]=D;

}

else a[fa][x]=a[x][fa]=1;

}

dfs(fa,y,D);

}

bool solve()

{

if(dis[t][0]<L)return 0;

if(dis[t][0]==L)return 1;

for(int i=1;i<n;i++)

if(dis[t][i]+i<=L)

{

dfs(t,i,L-dis[t][i]-i+1);

return 1;

}

return 0;

}

int main()

{

memset(a,-1,sizeof(a));

n=read();m=read();L=read();s=read();t=read();

s++;t++;

for(int i=1;i<=m;i++)

{

u[i]=read();v[i]=read();w[i]=read();

u[i]++;v[i]++;

a[u[i]][v[i]]=a[v[i]][u[i]]=w[i];

}

pre();

if(!solve())

{

puts("NO");

return 0;

}

else puts("YES");

for(int i=1;i<=m;i++)

{

w[i]=a[u[i]][v[i]];

if(!a[u[i]][v[i]])w[i]=L;

u[i]--;v[i]--;

cout<<u[i]<<' '<<v[i]<<' '<<w[i]<<endl;

}

return 0;

}

« 2016 ACM / ICPC Asia Regional Dalian Online 2016 ACM / ICPC Asia Regional Qingdao Online »

hzwer.com _ Home | http://hzwer.com

「CF715X」Codeforces Round #372 (Div. 1)

A. Plus and Square Root

B. Complete The Graph

分类目录

热门文章

Myfriends

近期评论