2016ACM/ICPC亚洲区大连站-重现赛（感谢大连海事大学）（7/10）

时间：2021-08-31 09:12:58

1001题意：n个人，给m对敌对关系，X个好人，Y个坏人。现在问你是否每个人都是要么是好人，要么是坏人。

先看看与X，Y个人有联通的人是否有矛盾，没有矛盾的话咋就继续遍历那些不确定的人关系，随便取一个数3，与其相连的就是4，间隔就要相同，dfs搜过去就可以判断了

#include<bits/stdc++.h>

using namespace std;

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

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 5e5+, maxn = 1e3+, mod = 1e9+, inf = 2e9;

int vis[N],t,head[N],n,m,x,y,z,cal[N],xx[N],yy[N];

int flag;

struct ss{

int to,next;}e[N * ];

void add(int u,int v) {e[t].next = head[u]; e[t].to = v; head[u] = t++;}

void dfs(int u,int fa) {

        cal[u] = ;

        for(int i = head[u]; i!=-; i = e[i].next) {

            int to = e[i].to;

            if(to == fa) continue;

            if(vis[u] == ) vis[u] = ;

            if(vis[to] == vis[u]) {

                flag = ;

                return ;

            }

            if(cal[to]) continue;

            if(vis[u] == ) vis[to] = ;

            else if(vis[u] == ) vis[to] = ;

            else if(vis[u] == ) vis[to] = ;

            else if(vis[u] == ) vis[to] = ;

            dfs(to,u);

        }

}

int main() {

        while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF) {

                t = ;

        memset(head,-,sizeof(head));

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

                int a,b;

                scanf("%d%d",&a,&b);

                add(a,b);

                add(b,a);

            }

            memset(cal,,sizeof(cal));

            memset(vis,,sizeof(vis));

            for(int i = ; i <= x; ++i) scanf("%d",&xx[i]),vis[xx[i]] = ;

            for(int i = ; i <= y; ++i) scanf("%d",&yy[i]),vis[yy[i]] = ;

            flag = ;

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

                if(!cal[i]) dfs(xx[i],-);

            }

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

                if(!cal[i]) dfs(yy[i],-);

            }

            if(flag) {

                puts("NO");

                continue;

            }

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

                if(!cal[i]) {

                    dfs(i,-);

                }

            }

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

                if(!vis[i]) flag = ;

            }

            if(flag) puts("NO");

            else puts("YES");

        }

        return ;

}

1001

1003题意：两堆石子，你可以任选一堆去掉任意个数，你也可从两堆中同时去掉任意个数，最后全部取完的人胜

石子的数量是10^100.高精度的威佐夫博弈，需要黄金比例精确到100位，队友javaA。

import java.util.*;

import java.math.*;

public class Main {

    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);

        BigInteger k=new BigInteger("6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374");

        BigInteger p=new BigInteger("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");

        while(cin.hasNext())

        {

            BigInteger nn=cin.nextBigInteger();

            BigInteger mm=cin.nextBigInteger();

            BigInteger n=nn.min(mm);

            BigInteger m=nn.max(mm);

            BigInteger j=n.multiply(k);

            j=j.divide(p);

            BigInteger l=j.multiply(k.add(new BigInteger("1")));

            l=l.divide(p);

            if(n.equals(l)==false)

                j=j.add(new BigInteger("1"));

            n=n.add(j);

            if(n.equals(m))

                System.out.println("0");

            else

                System.out.println("1");

        }

    }

}

1003

1004题意：给定a,b; 求出满足 LCM(X,Y) = b && X+Y = a的一组解，或者是无解

公式转化：b*gcd(X,Y) = X*Y,X+Y=a;

我们可以知道gcd(X,Y) 必然是a的因子！，那么我们为了枚举gcd(X,Y)就直接去枚举a的因子就是了

枚举以后就相当于求解一个二元一次方程的整数解了；

#include<bits/stdc++.h>

using namespace std;

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

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 5e5+, maxn = 1e3+, mod = 1e9+, inf = 2e9;

LL a,b,p[N],ans1,ans2;

int ok;

int check(LL a,LL B,LL gc) {

            if(a*a - *B < ) return ;

            LL tmp = (int)(sqrt(a*a - *B)+0.00001);

            if(tmp*tmp != a*a - *B) return ;

            LL fi = a+tmp;

            if(fi>=&&fi%==) fi/=;

            else fi = -;

            LL se = a-tmp;

            if(se>=&&se%==) se/=;

            else se = -;

            if(fi <=  && se <= ) return ;

            if(fi > ) {

                    LL x = a - fi;

                    if((__gcd(fi,x)==gc)&&x * fi == B) {

                        ans1 = fi,ans2 = x;

                        if(ans1>ans2)

                            swap(ans1,ans2);

                        ok = ;

                        return ;

                    }

                }

                 if(se > ) {

                    LL x = a - se;

                    if((__gcd(x,se)==gc)&&x * se == B) {

                        ans1 = se,ans2 = x;

                        if(ans1>ans2)

                            swap(ans1,ans2);

                        ok = ;

                        return ;

                    }

                }

                return ;

}

int main() {

        while(scanf("%I64d%I64d",&a,&b)!=EOF) {

            ok = ;

            for(int i = ; i * i <= a; ++i) {

                if(a % i == ) {

                    if(check(a,b*i,i)) break;

                    if(check(a,b*(a/i),a/i)) break;

                }

            }

            if(ok) printf("%I64d %I64d\n",ans1,ans2);

            else puts("No Solution");

        }

}

1004

1006题意：给你一个x，然后你要构造一个数组a，满足∑a = x， 任意的i,j( i != j) a[i] != a[j];问你 最大的 s = a1*a2*a3*......*an是多少；

要使得乘积最大，那么相乘的数越多显然S是越大的。。。。

假设x = 7, 那么我们构造出一个数组   2 3 2，到这里有重复的数了，我们就把最后面的2平分到前面  2,3 -> 3，4

假设x = 8，那么我们构造出一个数组   2 3 3，到这里有重复的数了，我们就把最后面的3平分到前面  2,3 -> 3，4 到这里，还有一个1，我们就分到最后一个数上去 -> 3 5

#include<bits/stdc++.h>

using namespace std;

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

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long ll;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 5e5+, maxn = 1e3+, mod = 1e9+, inf = 2e9;

ll sum[N];

ll pre[N];

ll quick_pow(ll x,ll y)

{

    ll ans=;

    while(y)

    {

        if(y&)ans*=x,ans%=mod;

        y>>=;

        x*=x;

        x%=mod;

    }

    return ans;

}

int main() {

        sum[]=;

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

                sum[i]=sum[i-]+i+;

        }

    int cnt=,T;

    pre[]=;

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

        {

            pre[i]=(pre[i-]*(i+))%mod;

        }

    scanf("%d",&T);

    while(T--)

    {

        ll x;

        scanf("%lld",&x);

        if(x == 1LL) {

            puts("");

            continue;

        }

        int pos=upper_bound(sum+,sum+cnt+,x)-sum-;

        ll m=x-sum[pos];

        if(m == pos+) {

            ll ans=pre[pos];

            ans=(ans*(pos+))%mod;

            ans=(ans*quick_pow(,mod-))%mod;

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

            continue;

        }

        ll ans = pre[pos - m];

        if(m!=) ans = ans * ((pre[pos+]*quick_pow((pre[pos-m+]),mod-))% mod )% mod;

        if(x==)

            printf("1\n");

        else

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

    }

    return ;

}

1006

1007题意：一个n点n边的树，每个树节点上有一种颜色苹果最多有k个不同的颜色，问你有多少条路径至少包含了所有颜色的苹果

树分治，这里要用到状态压缩的一点技巧

#include<bits/stdc++.h>

using namespace std;

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

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = +, maxn = 1e3+, mod = 1e9+, inf = 2e9;

LL ans = ;

int n,k,t,head[N],root,a[N],f[N],vis[N],siz[N],allnode;

LL cnt[N],num[N];

struct edge{

    int to,next;

}e[N * ];

void add(int u,int v) {e[t].next = head[u]; e[t].to = v;head[u] = t++;}

void getroot(int u,int fa) {

        f[u] = ;

        siz[u] = ;

        for(int i = head[u]; i != -; i = e[i].next) {

            int to = e[i].to;

            if(vis[to] || to == fa) continue;

            getroot(to,u);

            siz[u] += siz[to];

            f[u] = max(f[u],siz[to]);

        }

        f[u] = max(f[u],allnode - siz[u]);

        if(f[u] < f[root]) root = u;

}

void getdeep(int u,int fa,int now) {

    for(int i = head[u]; i != -; i = e[i].next) {

        int to = e[i].to;

        if(to == fa || vis[to]) continue;

        cnt[now|(<<a[to])]++;

        num[now|(<<a[to])]++;

        getdeep(to,u,now|(<<a[to]));

    }

}

LL cal(int u,int now) {

    for(int i = ; i < (<<k); ++i) cnt[i] = ,num[i] = ;

    num[now]++;

    cnt[now]++;

    getdeep(u,,now);

    for(int i = ; i < k; ++i) {

        for(int j = (<<k)-; j >= ; --j) {

            if(!((<<i)&j)) cnt[j] += cnt[j|(<<i)];

        }

    }

    LL ans1 = ;

    for(int i = ; i < (<<k); ++i) {

        ans1 += 1LL*num[i]*cnt[i^((<<k)-)];

    }

    return ans1;

}

void work(int u) {

        vis[u] = ;

        ans += cal(u,<<a[u]);

        for(int i = head[u]; i != -; i = e[i].next) {

            int to = e[i].to;

            if(vis[to]) continue;

            ans -= cal(to,(<<a[u])|(<<a[to]));

            allnode = siz[to];

            root = ;

            getroot(to,-);

            work(root);

        }

}

void init() {

        memset(head,-,sizeof(head));

        memset(vis,,sizeof(vis));

        t = ;

        ans = ;

}

int main() {

        while(scanf("%d%d",&n,&k)!=EOF) {

            for(int i = ; i <= n; ++i) scanf("%d",&a[i]),a[i]--;

            init();

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

                int u,v;

                scanf("%d%d",&u,&v);

                add(u,v);add(v,u);

            }

            f[] = inf;

            allnode = n;

            root = ;

            getroot(,-);

            work(root);

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

        }

        return ;

}

1007

1008题意：k个黑球，1个白球，每次每人只能取一球，先取到红球的人胜利，问先取的人是否为有利，或者是平等

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

#define eps 1e-14

const int N=2e5+,M=4e6+,inf=1e9+,mod=1e9+;

const ll INF=1e18+,MOD=1e9+;

int main()

{

    int x;

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

    {

        if(x&)

            printf("0\n");

        else

            printf("1\n");

    }

    return ;

}

1008

1009题意：N个角度，长度为D，求出这n个线段围成的面积

#include<bits/stdc++.h>

using namespace std;

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

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 4e5+, maxn = 1e3+, mod = 1e9+, inf = 2e9;

double d;

int n;

int main() {

        while(scanf("%d%lf",&n,&d)!=EOF) {

                double ans = 0.0;

                double x;

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

                    scanf("%lf",&x);

                    ans += d*d*sin(x/ * Pi)/;

                }

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

        }

    return ;

}

1009

　　

相关文章