The 2016 ACM-ICPC Asia Dalian Regional Contest

一共a了6题

A：找二分图，判断有没有冲突或者孤立的店

题解：直接dfs即可

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

int color[N],n;

vector<int>v[N];

bool dfs(int u,int c)

{

    color[u]=c;

    for(int i=;i<v[u].size();i++)

    {

        int x=v[u][i];

        if(color[x]==c||(color[x]==&&!dfs(x,-c)))

            return ;

    }

    return ;

}

void solve()

{

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

    {

        if(color[i]==&&!dfs(i,))

        {

            cout<<"NO"<<endl;

            return ;

        }

        else if(color[i]==&&!dfs(i,))

        {

            cout<<"NO"<<endl;

            return ;

        }

    }

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

    {

        if(color[i]==&&!dfs(i,))

        {

            cout<<"NO"<<endl;

            return ;

        }

    }

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

        if(color[i]==-)

        {

            cout<<"NO"<<endl;

            return ;

        }

    cout<<"YES"<<endl;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int m,x,y;

    while(cin>>n>>m>>x>>y)

    {

        for(int i=;i<=n;i++)v[i].clear();

        memset(color,-,sizeof color);

        while(m--)

        {

            int a,b;

            cin>>a>>b;

            color[a]=color[b]=;

            v[a].push_back(b);

            v[b].push_back(a);

        }

        for(int i=;i<=x;i++)

        {

            int a;

            cin>>a;

            color[a]=;

        }

        for(int i=;i<=y;i++)

        {

            int a;

            cin>>a;

            color[a]=;

        }

        solve();

    }

    return ;

}

/*********************

5 4 1 2

1 3

1 4

3 5

4 5

2

1 3

*********************/

D：给你a，b，看能不能找到x，y使x+y==a，最小公约数（x，y）==b

题解：y=a-x，然后gcd（x，y）==gcd（a，b），看二元一次方程有没有解

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f;

map<ll,ll>m;

int main()

{

    for(ll i=;i<=;i++)m[i*i]=i;

    ll a,b;

    while(~scanf("%lld%lld",&a,&b))

    {

        ll y=-a,z=__gcd(a,b)*b;

        if(y*y<*z)puts("No Solution");

        else

        {

            if(!m[y*y-*z]&&y*y-*z!=)puts("No Solution");

            else

            {

                ll p1=-y+m[y*y-*z],p2=-y-m[y*y-*z];

                if(p1%==&&p1/>&&p2%==&&p2/>)printf("%lld %lld\n",min(p1/,p2/),max(p1/,p2/));

                else puts("No Solution");

            }

        }

    }

    return ;

}

F：给一个数a，找一堆不相同的数相加为a，使他们相乘最大

题解：直觉。。。2+3+。。+一直加到和大于a为止，然后把最后一位变成2+3+4+5+6+10这种形式，然后把10平摊到前面的数2+4+5+6+7+8，然后前缀和二分，答案用前缀积+逆元求

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=;

ll f[N],ans[N];

ll quick(ll a,ll b)

{

    ll ans=;

    while(b)

    {

        if(b&)ans=(ans*a)%mod;

        a=(a*a)%mod;

        b/=;

    }

    return ans;

}

int main()

{

    ans[]=;

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

    {

        f[i]=i*(i+)/-;

        ans[i]=ans[i-]*i%mod;

    }

    int t;

    scanf("%d",&t);

    while(t--)

    {

        ll x;

        scanf("%lld",&x);

        if(x<=)printf("%lld\n",x);

        else

        {

            ll p=lower_bound(f,f+,x)-f;

            if(f[p]==x)printf("%lld\n",ans[p]);

            else

            {

                if(p-x+f[p-]!=)printf("%lld\n",ans[p]*quick(p-x+f[p-],mod-)%mod);

                else printf("%lld\n",ans[p+]*quick(p,mod-)%mod*quick(,mod-)%mod);

            }

        }

    }

    return ;

}

H：一个袋子里有n个红球，1个黑球，二个人轮流拿(拿到不放回)，拿到黑球算赢，问先拿的人能不能赢

题解：找规律，emmm当n为奇数，可以看出概率为1/2，n为偶数时，把取的整个过程看成全排列那么就是(n+1)!，分成黑球在奇数位和在偶数位，在奇数位就是先手取的情况，

那么概率就是n+2/（2*（n+1）），保证大于0.5

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=;

int main()

{

    int k;

    while(~scanf("%d",&k))

    {

        if(k&)puts("");

        else puts("");

    }

    return ;

}

I水题

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=;

int main()

{

    int n,d;

    while(~scanf("%d%d",&n,&d))

    {

        double ans=;

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

        {

            double ang;

            scanf("%lf",&ang);

            ans+=sin(ang/*pi)/*d*d;

        }

        printf("%.3f\n",ans);

    }

    return ;

}

J主要是题意难懂= =，给一堆数，把他化成32位的二进制，然后每8个算一个数（字符），求a的个数，模拟即可

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=;

int main()

{

    int n,d;

    while(~scanf("%d",&n))

    {

        string a="";

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

        {

            ll x;

            scanf("%lld",&x);

            string p="";

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

            {

                if(x&)p+='';

                else p+='';

                x/=;

            }

            reverse(p.begin(),p.end());

            a+=p;

        }

        ll ans=;

        for(int i=;i<a.size();i+=)

        {

            ll p=;

            for(int j=;j>=;j--)p+=(<<(-j))*(int)(a[j+i]-'');

            if((char)p=='a')ans++;

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

The 2016 ACM-ICPC Asia Dalian Regional Contest

最新文章

热门文章