「CF623X」AIM Tech Round (Div. 1)

2016年3月6日4,2070

A. Graph and String

题意

n个点，每个点有a,b,c其中一种颜色，若两个点颜色的字母相邻则它们之间连边。

给出图的连边情况，求一种可行的染色方案。

题解

如果有一个点和其它点都有连边，将其标号b。

然后选择一个未被标号的点，标号为a，二分图染色。

最后验证一下即可。

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define mod 10000007
#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,m;
bool e[505][505];
int v[505];
void solve(int x,int y)
{
    for(int i=1;i<=n;i++)
        if(i!=x&&i!=y)
        {
            if(e[i][x])v[i]=1;
            if(e[i][y])v[i]=3;
            if(e[i][x]&&e[i][y])v[i]=2;
        }            
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        e[u][v]=e[v][u]=1;
    }
    bool flag=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(!e[i][j])
            {
                v[i]=1;v[j]=3;
                solve(i,j);
                flag=1;
                break;
            }
    if(!flag)for(int i=1;i<=n;i++)v[i]=1;
    for(int i=1;i<=n;i++)if(!v[i]){puts("No");return 0;}
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            if(abs(v[i]-v[j])<=1&&!e[i][j]){puts("No");return 0;}
            if(abs(v[i]-v[j])==2&&e[i][j]){puts("No");return 0;}
        }
    puts("Yes");
    for(int i=1;i<=n;i++)
        printf("%c",'a'+v[i]-1);
    printf("\n");
    return 0;

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define mod 10000007

#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,m;

bool e[505][505];

int v[505];

void solve(int x,int y)

{

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

if(i!=x&&i!=y)

{

if(e[i][x])v[i]=1;

if(e[i][y])v[i]=3;

if(e[i][x]&&e[i][y])v[i]=2;

}

int main()

{

n=read();m=read();

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

{

int u=read(),v=read();

e[u][v]=e[v][u]=1;

}

bool flag=0;

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

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

if(!e[i][j])

{

v[i]=1;v[j]=3;

solve(i,j);

flag=1;

break;

}

if(!flag)for(int i=1;i<=n;i++)v[i]=1;

for(int i=1;i<=n;i++)if(!v[i]){puts("No");return 0;}

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

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

{

if(abs(v[i]-v[j])<=1&&!e[i][j]){puts("No");return 0;}

if(abs(v[i]-v[j])==2&&e[i][j]){puts("No");return 0;}

}

puts("Yes");

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

printf("%c",'a'+v[i]-1);

printf("\n");

return 0;

B. Array GCD

题意

给定长为n的数列和两个操作，每个操作用一次

1.移除数列的一个子串，代价是长度*a

2.对于一些数字+1或者-1，每个数字代价为b

求使得数列的gcd大于1的最小代价

题解

由于不能删掉所有的数，那么至少会剩下第一个或最后一个

这两个可能会被修改，枚举2 * 3 = 6种情况，分解质因数后扫一遍数列，取最优值

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define mod 10000007
#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;
}
ll mn;
int n;
ll a,b;
int v[1000005];
ll c[1000005],f[1000005];
void cal(int x)
{
    ll l=1,r=n,g=0;
    for(int i=1;i<=n;i++)
    {
        if(v[i]%x==1||v[i]%x==x-1)c[i]=b;
        else if(v[i]%x==0)c[i]=0;
        else c[i]=mn;
    }
    for(int i=1;i<=n;i++)
        f[i]=min(f[i-1]+c[i],mn);
    for(int i=1;i<=n;i++)
        f[i]=min(f[i-1],f[i]-a*i);
    for(int i=n;i;i--)
    {
        mn=min(mn,f[i]+g+a*i);
        g=min(g+c[i],mn);
    }
}
void solve(int t)
{
    for(int i=2;i<=100000;i++)
        if(t%i==0)
        {
            cal(i);
            while(t%i==0)t/=i;
        }
    if(t!=1)cal(t);
}
int main()
{
    n=read();a=read();b=read();
    mn=(n-1)*a;
    for(int i=1;i<=n;i++)
        v[i]=read();
    for(int i=-1;i<=1;i++)
        solve(i+v[1]),solve(i+v[n]);
    cout<<mn<<endl;
    return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define mod 10000007

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

}

ll mn;

int n;

ll a,b;

int v[1000005];

ll c[1000005],f[1000005];

void cal(int x)

{

ll l=1,r=n,g=0;

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

{

if(v[i]%x==1||v[i]%x==x-1)c[i]=b;

else if(v[i]%x==0)c[i]=0;

else c[i]=mn;

}

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

f[i]=min(f[i-1]+c[i],mn);

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

f[i]=min(f[i-1],f[i]-a*i);

for(int i=n;i;i--)

{

mn=min(mn,f[i]+g+a*i);

g=min(g+c[i],mn);

}

void solve(int t)

{

for(int i=2;i<=100000;i++)

if(t%i==0)

{

cal(i);

while(t%i==0)t/=i;

}

if(t!=1)cal(t);

}

int main()

{

n=read();a=read();b=read();

mn=(n-1)*a;

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

v[i]=read();

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

solve(i+v[1]),solve(i+v[n]);

cout<<mn<<endl;

return 0;

}

« 「CF618X」Wunder Fund Round 2016 (Div. 1 + Div. 2 combined) 「CF639X」VK Cup 2016 – Round 1 »

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

「CF623X」AIM Tech Round (Div. 1)

分类目录

热门文章

Myfriends

近期评论