2016ICPC 大连

╰半橙微兮° 2023-10-11 13:27 26阅读 0赞

A.1:41:18 solved by hl

大致就是一个图上染色判断是否有矛盾。

按照样例来看，似乎存在孤立点就要输出NO

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1010;
    const int maxm = 10010;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int N,M,X,Y;
    int fa[maxn],sz[maxn];
    int color[maxn];
    int head[maxn],tot;
    struct Edge{
        int to,next;
    }edge[maxm * 2];
    void init(){
        for(int i = 0 ; i <= N ; i ++) fa[i] = i,sz[i] = 1;
        for(int i = 0; i <= N ; i ++) head[i] = -1;
        tot = 0;
    }
    int find(int x){
        if(x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }
    void Union(int a,int b){
        a = find(a); b = find(b);
        if(a != b){
            sz[b] += sz[a];
            fa[a] = b;
        }
    }
    void add(int u,int v){
        edge[tot].to = v;
        edge[tot].next = head[u];
        head[u] = tot++;
    }
    bool flag;
    void dfs(int x){
        //cout << x << " " << color[x] << endl;
        for(int i = head[x]; ~i ;i = edge[i].next){
            int v = edge[i].to;
            if(!color[v]){
                color[v] = -color[x];
                dfs(v);
            }
            else if(color[v] == color[x]) flag = 0;
        }
    }
    int main(){
        while(~Sca2(N,M)){
            Sca2(X,Y); init();
            for(int i = 1; i <= N ; i ++) color[i] = 0;
            for(int i = 1; i <= M ; i ++){
                int u,v ; Sca2(u,v); add(u,v); add(v,u);
                Union(u,v);
            }
            flag = 1;
            for(int i = 1; i <= X ; i ++){
                int x = read();
                if(color[x] == -1) flag = 0;
                if(!color[x]){
                    color[x] = 1;
                    dfs(x);
                }
            }
            for(int i = 1; i <= Y; i ++){
                int x = read();
                if(color[x] == 1) flag = 0;
                if(!color[x]){
                    color[x] = -1;
                    dfs(x);
                }
            }
    
            for(int i = 1; i <= N ; i ++){
               // cout <<sz[find(i)] << endl;
                if(!color[i]){
                    if(sz[find(i)] == 1) flag = 0;
                   // if(flag) puts("YES");
                   // else puts("NO");
                    color[i] = 1;
                    dfs(i);
                }
            }
            if(flag) puts("YES");
            else puts("NO");
        }
        return 0;
    }

C.4:34:31(-4) solved by zcz

方法1.如果较大的数和较小的数比例是黄金比就是0

方法2.设b为较大的数，a为较小的数，l为b - a,满足 b > b \* l - a \* a >= 0就为0

要用JAVA上大数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

import java.math.*;
    import java.util.*;
    import java.io.*;
    
    public class Main{
        public static void main(String[] args){
            Scanner in = new Scanner(System.in);
            BigInteger a,b,x,y,m,n,l,cnt,fu,q,zero;
            while(in.hasNext()){
                x = in.nextBigInteger();
                y = in.nextBigInteger();
                a = x;  b = x;
                b = b.max(y);
                a = a.min(y);
                l = b.subtract(a);
                n = b.multiply(l);
                q = a.multiply(a);
                int t = b.compareTo(n.subtract(q));
                int tt = n.compareTo(q);
                if(t == -1  || tt == -1 || t == 0) System.out.println("1");
                else System.out.println("0");
            }
        }
    }

D. 1:14:59 solved by gbs

可以推公式，直接解方程解出来

x1= (X + sqrt(XX - 4ygcd(x,y) ) ) /2;  
y1 = X - x1;

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include<stack>
    #include<math.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<ctime>
    #include<complex>
    #include<stdio.h>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<deque>
    using namespace std;
    typedef long long LL;
    
    int gcd(int a,int b)
    {
        if (b == 0)
            return a;
        return gcd(b,a%b);
    }
    int judge1(int X,int Y)
    {
        int left1 = 1;
        int right1 = X/2;
        while(left1<=right1)
        {
            //cout<<left1
            int mid = (left1+right1)>>1;
            LL ans = 1LL*(X-mid)*mid;
            //cout<<ans<<' '<<Y<<' '<<mid<<endl;
            if (ans>Y)
                right1 = mid-1;
            else if (ans == Y)
            {
                if (gcd(mid,X-mid)!=1)
                    return -1;
                return mid;
            }
            else
                left1 = mid+1;
        }
        return -1;
    }
    int main()
    {
        int X,Y;
        int gcd1;
        while(scanf("%d%d",&X,&Y)!=EOF){
            gcd1 = gcd(X,Y);
            X/=gcd1;
            Y/=gcd1;
            //cout<<X<<' '<<Y<<endl;
            int ans1= judge1(X,Y);
            if (ans1 == -1)
                printf("No Solution\n");
            else
                printf("%d %d\n",ans1*gcd1,(X-ans1)*gcd1);
    
        }
        return 0;
    }
    
    
    /*
    111
    5111111 11111116 12133215 251111111
    111
    5 15 5 25
    5 14 5 25
    5 13 5 25
    5 12 5 25
    3
    14 14 5 5
    14 14 5 5
    */

F. 1:08:17(-1) solved by zcz and hl

WA:读错题

很显然，段数分的越多越好,同时要满足每段不同，所以从2开始分直到不能分

例如10分为 2 + 3 + 4,最后剩下的1平均从后往前分，变为 2 + 3 + 5

12分为 2 + 3 + 4 ,剩下的3分给他们变为 3 + 4 + 5

13分为 2 + 3 + 4,剩下的分为 3 + 4 + 5,又剩下1分到5上变为 3 + 4 + 6

这是一个等差数列，知道了分法就总结一下计算公式就可以了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

G.3:05:25(-2) solved by hl

WA:没整清楚就交 + 忘记特判

点分治 + 状压dp

点分治每次寻找子树的重心，对于不同的两棵树之间维护dp1\[i\]表示已经被记入的树在i满足存在状态i结点的数量

dp2表示正在处理的当前子树的状态数，dp3\[i\]表示当前处理的子树下状态确实为i的数量

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 5e4 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    LL N,M,K;
    int type[maxn];
    struct Edge{
        int to,next;
    }edge[maxn * 2];
    int head[maxn],tot;
    void init(){
        for(int i = 0 ; i <= N ; i ++) head[i] = -1;
        tot = 0;
    }
    void add(int u,int v){
        edge[tot].to = v;
        edge[tot].next = head[u];
        head[u] = tot++;
    }
    int root,max_part,SUM,ed;
    int size[maxn],vis[maxn];
    void dfs_root(int u,int la){
        size[u] = 1;
        int heavy = 0;
        for(int i = head[u];~i ; i = edge[i].next){
            int v = edge[i].to;
            if(v == la || vis[v]) continue;
            dfs_root(v,u);
            heavy = max(heavy,size[v]);
            size[u] += size[v];
        }
        if(max_part > max(heavy,SUM - heavy)){
            max_part = max(heavy,SUM - heavy);
            root = u;
        }
    }
    LL dp1[3000],dp2[3000],dp3[3000];
    void dfs_dis(int t,int la,int state){
        state |= (1 << type[t]);
        dp3[state]++;
        for(int sta = state;sta; sta = (sta - 1) & state) dp2[sta]++; dp2[0]++;
        for(int i = head[t]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(vis[v] || v == la) continue;
            dfs_dis(v,t,state);
        }
    }
    LL ans;
    void work(int t){
        int state = 1 << type[t];
        for(int i = 0 ; i <= ed; i ++) dp1[i] = dp2[i] = dp3[i] = 0;
        for(int sta = state;sta; sta = (sta - 1) & state) dp1[sta]++; dp1[0]++;
        LL sum = 0;
        for(int i = head[t]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(vis[v]) continue;
            dfs_dis(v,t,state);
            for(int sta = 0; sta <= ed; sta++){
                ans += dp1[sta] * dp3[ed - sta];
               // cout << "  " <<  sta  <<"  " << dp1[sta] << " " << dp3[ed - sta] << endl;
            }
            //ans -= sum;
           // sum += dp2[ed - state];
            for(int sta = 0; sta <= ed; sta++){
                dp1[sta] += dp2[sta];
                dp2[sta] = 0;
                dp3[sta] = 0;
            }
           // cout << t << " " << v << " " << ans << endl;
        }
    }
    void divide(int t){
        max_part = INF,root = t;
        dfs_root(t,-1);
        vis[root] = 1;
        work(root);
        for(int i = head[root]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(vis[v]) continue;
            SUM = size[v];
            divide(v);
        }
    }
    int main(){
        while(~scanf("%lld%d",&N,&K)){
            init(); ed = (1 << K) - 1; ans = 0;
            for(int i = 0 ; i <= N ; i ++) vis[i] = 0;
            for(int i = 1; i <= N ; i ++){
                Sca(type[i]);
                type[i]--;
            }
            for(int i = 1; i <= N - 1; i ++){
                int u,v; Sca2(u,v); add(u,v); add(v,u);
            }
            if(K == 1){
                Prl(N * N);
                continue;
            }
            SUM = N; divide(1);
            Prl(ans *2);
        }
        return 0;
    }
    
    /*
    3 2
    1 2 2
    1 2
    1 3
      0  0 1
      1  1 0
      2  0 0
      3  0 0
    1 3 0
      0  0 1
      1  2 0
      2  1 0
      3  1 0
    1 2 0
    0
    */

H.0:27:19 solved by gbs

判断一下奇偶

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

I.0:16:52 solved by hl

把凸包变成一圈三角形拼起来的，

三角形面积公式是 S = 0.5absin(θ)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

J. 0:10:46 solved by gbs

每次八位判断一下是不是97

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

K. 3:15:49(-1) solved by zcz

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    
    const int maxn=5e6+5;
    long long mod=100000073;
    long long a[maxn];
    long long b[maxn];
    long long sum[maxn];
    
    int main()
    {
        int c1=1,c2=1;
        while(c2<maxn)
        {
            a[c2]=c1;
            c1++;
            c2+=c1;
        }
        a[maxn-1]=c1;
        for(int i=maxn-2;i>=1;i--)
        {
            if(!a[i])   a[i]=a[i+1];
        }
        b[1]=1;
        b[2]=2;
        b[3]=1;
        sum[1]=1;
        sum[2]=3;
        sum[3]=4;
        c1=0;
        for(int i=4;i<maxn;i++)
        {
            if(c1==0)   c1=a[i];
            //cout<<c1<<endl;
            // for(int j=0,k=a[i]-1;j<c1;j++,k--)
            // {
            //     b[i]=(b[i]+b[i-k-1])%mod;
            //  }
            b[i]=(sum[i-a[i]+c1-1]-sum[i-a[i]-1]+mod)%mod;
            sum[i]=(sum[i-1]+b[i])%mod;
            c1--;
        }
        long long a1,a2;
        while(scanf("%lld %lld",&a1,&a2)!=EOF)
        {
            printf("%lld %lld\n",a[a2-a1+1],b[a2-a1+1]);
        }
    
    
    
        return 0;
    }

转载于:https://www.cnblogs.com/Hugh-Locke/p/11328979.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif