2019 HZNU Winter Training Day 15 Comprehensive Training

A - True Liars

题意：

那么如果一个人说另一个人是好人，那么如果这个人是好人，说明对方确实是好人，如果这个是坏人，说明这句话是假的，对方也是坏人。

如果一个人说另一个人是坏人，那么如果这个人是好人，说明对方是坏人，如果这个是坏人，说明对方是好人。

也就是如果条件是yes说明这两个是相同集合的，否则是两个不同的集合。

思路：

用r[i]表示i结点与根结点的关系，0为相同集合，1为不同集合。这是一个经典的并查集问题。

这样处理之后，还需要判断是否唯一

我们通过并查集，可以将所有人分为若干个集合，其中对于每一个集合，又分为两个集合（好人和坏人，但是不知道哪些是好人，哪些是坏人，我们只有相对关系）

接下来就是从所有大集合中的两个小集合取一个，组成好人集合，判断是否唯一。

背包问题，dp[i][j]表示前i个大集合，好人为j个的方案有多少种，或者dp[i][j]表示当前好人i个，坏人j个的情况有多少种

如果dp[cnt][p1]！=1说明方案不唯一，或者无解。

输出方案就是加个pre数组，从后往前递推呢。

代码：

/*
POJ 1417
*/
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <string>
using namespace std;

const int MAXN=610;
int F[MAXN];
int val[MAXN];
int find(int x)
{
    if(F[x]==-1)return x;
    int tmp=find(F[x]);
    val[x]+=val[F[x]];
    val[x]%=2;
    return F[x]=tmp;
}
int a[MAXN][2];//a[i][0],a[i][1]表示每个大集合分成两部分的个数
vector<int>b[MAXN][2];
bool used[MAXN];
int dp[MAXN][MAXN/2];
int pre[MAXN][MAXN/2];
int main()
{
    int n,p1,p2;
    while(scanf("%d%d%d",&n,&p1,&p2)==3)
    {
        if(n==0 && p1==0 && p2==0)break;
        memset(F,-1,sizeof(F));
        memset(val,0,sizeof(val));
        int u,v;
        char str[10];
        while(n--)
        {
            scanf("%d%d%s",&u,&v,&str);
            int tmp;
            if(str[0]=='y')//相同
              tmp=0;
            else tmp=1;//相反
            int t1=find(u),t2=find(v);
            if(t1!=t2)
            {
                F[t1]=t2;
                val[t1]=(val[v]-val[u]+tmp+2)%2;
            }
        }
        for(int i=0;i<MAXN;i++)
        {
            b[i][0].clear();
            b[i][1].clear();
            a[i][0]=0;
            a[i][1]=0;
        }
        memset(used,false,sizeof(used));
        int cnt=1;
        for(int i=1;i<=p1+p2;i++)
          if(!used[i])
          {
              int tmp=find(i);
              for(int j=i;j<=p1+p2;j++)
              {
                  if(find(j)==tmp)
                  {
                      used[j]=true;
                      b[cnt][val[j]].push_back(j);
                      a[cnt][val[j]]++;
                  }
              }
              cnt++;
          }
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<cnt;i++)
        {
            for(int j=p1;j>=0;j--)
            {
                if(j-a[i][0]>=0 && dp[i-1][j-a[i][0]])
                {
                    dp[i][j]+=dp[i-1][j-a[i][0]];
                    pre[i][j]=j-a[i][0];
                }

                if(j-a[i][1]>=0 && dp[i-1][j-a[i][1]])
                {
                    dp[i][j]+=dp[i-1][j-a[i][1]];
                    pre[i][j]=j-a[i][1];
                }

            }
        }
        if(dp[cnt-1][p1]!=1)
        {
            printf("no\n");
        }
        else
        {
            vector<int>ans;
            ans.clear();
            int t=p1;
            //printf("%d\n",cnt);

            for(int i=cnt-1;i>=1;i--)
            {
                int tmp=t-pre[i][t];
                //printf("%d\n",i);
                //printf("%d  %d\n",t,tmp);
                if(tmp==a[i][0])
                {
                    for(int j=0;j<a[i][0];j++)
                      ans.push_back(b[i][0][j]);
                }
                else
                {
                    for(int j=0;j<a[i][1];j++)
                      ans.push_back(b[i][1][j]);
                }
                t=pre[i][t];
            }

            sort(ans.begin(),ans.end());
            for(int i=0;i<ans.size();i++)
              printf("%d\n",ans[i]);
            printf("end\n");
        }

    }
    return 0;
}

View Code

B - The Shortest Path in Nya Graph

题意：有n个点 , m条无向边 ,每条边都是有权值, 并且每个点属于一个楼层 ,楼层上的点到可以到相邻楼层的任意一点 ,但是要花费 c 。没有点的相邻楼层不能互达。求 1 到 n的最小花费。

思路：图建好了就是裸的最短路了。但是建图有点麻烦，参考了别人的代码之后才明白为什么要这样建图。
把楼层看成一个点，第i层可以看成第n+i个点。楼层与该楼层上的点建边，边权为0，单向；楼层与
相邻楼层建边，边权为C，双向；相邻楼层上的点与该楼层建边，边权为C，单向。

代码：

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#define N 200100
#define ll long long
 
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,c;
int lay[N];
bool hava[N];
 
bool vis[N];
int cnt[N];
int dist[N];
struct Edge {
    int v;
    int cost;
    Edge(int _v=0,int _c=0):v(_v),cost(_c) {}
    bool operator <(const Edge &r)const {
        return cost>r.cost;
    }
};
vector<Edge>E[N];
void addedge(int u,int v,int w) {
    Edge it;
    it.v=v;
    it.cost=w;
    E[u].push_back(it);
}
 
void Dijk(int n,int start) { //点的编号从1开始
    memset(vis,false,sizeof(vis));
    for(int i=1; i<=n*2; i++)dist[i]=inf;
    priority_queue<Edge>que;
    while(!que.empty())que.pop();
    dist[start]=0;
    que.push(Edge(start,0));
    Edge tmp;
    while(!que.empty()) {
        tmp=que.top();
        que.pop();
        int u=tmp.v;
        if(vis[u])continue;
        vis[u]=true;
        for(int i=0; i<E[u].size(); i++) {
            int v=E[tmp.v][i].v;
            int cost=E[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost) {
                dist[v]=dist[u]+cost;
                que.push(Edge(v,dist[v]));
            }
 
        }
    }
}
 
int main() {
   // freopen("test.in","r",stdin);
    int t;
    cin>>t;
    int ca=1;
    while(t--) {
        for(int i=0; i<=n*2+1; i++)E[i].clear();
        scanf("%d%d%d",&n,&m,&c);
        memset(hava,0,sizeof hava);
        for(int i=1; i<=n; i++) {
            scanf("%d",&lay[i]);
            hava[lay[i]]=true;
        }
        int u,v,cost;
        for(int i=1; i<=m; i++) {
            scanf("%d%d%d",&u,&v,&cost);
            addedge(u,v,cost);
            addedge(v,u,cost);
        }
        if(n<=1) {
            printf("Case #%d: 0\n",ca++);
            continue;
        }
 
        for(int i=1; i<n; i++) {
            if(hava[i]&&hava[i+1]) {
                addedge(n+i,n+i+1,c);
                addedge(n+1+i,n+i,c);
            }
        }
        for(int i=1; i<=n; i++) {
            addedge(lay[i]+n,i,0);
            if(lay[i]>1)addedge(i,lay[i]-1+n,c);
            if(lay[i]<n)addedge(i,lay[i]+1+n,c);
        }
        Dijk(n,1);
        printf("Case #%d: %d\n",ca++,dist[n]>=inf?-1:dist[n]);
    }
    return 0;
}

View Code

C - The Super Powers

题意：给你一个关于超级幂数的定义，只要一个数是至少两个数的幂，即为超级幂数。例如64=8*8=4*4*4。输出1~2^64-1内所有的超级幂数。

思路：一开始的思想暴力，但是肯定很慢。有两个比较重要的思路：① 找num^x<2^64-1的时候，尝试两边取对数，然后确定x<ln(2^64-1)/ln(num)，x在4~ln(2^64-1)/ln(num)里取。② 只有合数的时候才能产生超级幂数，然后判断是否为素数即可。

　　还有很重要的一点，pow会出错。谨慎使用，wa了很多次，用快速幂才ac。

　　扔进set里遍历输出即可。

代码：

 1 /*
 2  I have a dream!A AC deram!!
 3  orz orz orz orz orz orz orz orz orz orz orz
 4  orz orz orz orz orz orz orz orz orz orz orz
 5  orz orz orz orz orz orz orz orz orz orz orz
 6 
 7  */
 8 
 9 #include<iostream>
10 #include<cstdio>
11 #include<cstdlib>
12 #include<cstring>
13 #include<cmath>
14 #include<string>
15 #include<algorithm>
16 #include<vector>
17 #include<queue>
18 #include<set>
19 #include<stack>
20 using namespace std;
21 typedef long long ll;
22 typedef unsigned long long ull;
23 const int maxn = 1e4 + 5;
24 const int N = 2100;
25 #define pa pair<int,int>
26 inline int read()
27 {
28     int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar())if (ch == '-')f = -1;
29     for (; isdigit(ch); ch = getchar())x = x * 10 + ch - '0'; return x * f;
30 }
31 
32 bool isPrime(int n)
33 {
34     if (n <= 3)
35         return n > 1;
36     else if (n % 2 == 0 || n % 3 == 0)
37         return false;
38     else
39     {
40         for (int i = 5; i * i <= n; i += 6)
41             if (n % i == 0 || n % (i + 2) == 0)
42                 return false;
43     }
44     return true;
45 }
46 
47 ull qsm(int a, int b)
48 {
49     ull ans = 1, base = a;
50     while (b != 0) {
51         if (b & 1 != 0) {
52             ans *= base;
53         }
54         base *= base;
55         b >>= 1;
56     }
57     return ans;
58 }
59 
60 
61 int main()
62 {
63     set<ull>ans;
64     ans.insert(1);
65     ull maxx = 18446744073709551615;
66     for (int num = 2; num < 1e5; num++)
67     {
68         if (pow(num, 4) > maxx) break;
69         double m = log(maxx) / log(num);
70         for (int i = 4; i < m; i++)
71         {
72             if (isPrime(i)) continue;
73             ull p = qsm(num, i);
74             ans.insert(p);
75         }
76     }
77 
78     set<ull>::iterator it;
79     //int cnt = 0;
80     for (it = ans.begin(); it != ans.end(); it++)
81     {
82         //cnt++;
83         //if (cnt == 10) break;
84         printf("%llu\n", *it);
85     }
86     return 0;
87 }

View Code

D - Music Festival

题意：给你n组区间，每个居间都带有权值，让你选取一些区间使得区间不想交并且权值最大（要每组都至少有一个区间被选到）。

思路：n最多十组，我们就可以用二进制来记录当前唱歌的状态，然后离散化区间点（这样我们就可以用连续的点去表示这些区间），这样就有dp【i】【j】，i表示当前的区间点，j表示当前的状态，dp【i1】【j1】=dp【i】【j】+num【k】。每次寻找当前点往右能更新的最近的一个区间（一切切的一切都是膜拜大佬的博客来的，离散化真是个好东西）
---------------------
作者：liexss
来源：CSDN
原文：https://blog.csdn.net/liexss/article/details/83511980

代码：

 1 #include<stdio.h>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<map>
 6 #include<iostream>
 7 using namespace std;
 8 struct inst {
 9     int x, y;
10     int sud;
11     int id;
12 };
13 inst ax[1100];
14 int dp[2100][1100];
15 int bn[2100];
16 int maxn[1100];
17 int tot, cnt;
18 map<int, int>q;
19 int cmp(inst a, inst b) {
20     if (a.x!=b.x)return a.x < b.x;
21     else return a.y < b.y;
22 }
23 int binary_s(int x) {
24     int l = 0;
25     int r = tot-1;
26     int ans = tot-1;
27     while (l <= r) {
28         int mid = (l + r) / 2;
29         if (ax[mid].x >= x) {
30             ans = mid;
31             r = mid - 1;
32         }
33         else l = mid + 1;
34     }
35     if (x > ax[ans].x) ans++;
36     return ans;
37 }
38 int main(void) {
39     int n;
40     scanf("%d", &n);
41     tot = 0;
42     cnt = 0;
43     q.clear();
44     memset(maxn, 0x8f, sizeof(maxn));
45     memset(dp, 0x8f, sizeof(dp));
46     for (int i = 1; i <= n; i++) {
47         int m;
48         scanf("%d", &m);
49         for (int z = 0; z < m; z++) {
50             scanf("%d %d %d", &ax[tot].x, &ax[tot].y,&ax[tot].sud);
51             ax[tot].id = i-1;
52             bn[cnt++] = ax[tot].x;
53             bn[cnt++] = ax[tot].y;
54             tot++;
55         }
56     }
57     sort(bn, bn + cnt);
58     cnt = unique(bn,bn + cnt) - bn;
59     sort(ax, ax + tot, cmp);
60     for (int i = 0; i < cnt; i++) {
61         q[bn[i]] = i;
62     }
63     for (int i = 0; i < tot; i++) {
64         ax[i].x = q[ax[i].x];
65         ax[i].y = q[ax[i].y];
66     }
67     dp[0][0] = maxn[0] = 0;
68     for (int i = 0; i < cnt; i++) {
69         for (int j = 0; j < (1 << n); j++) {
70             dp[i][j] = maxn[j] = max(dp[i][j], maxn[j]);
71             if (dp[i][j] < 0) continue;
72             int pos=binary_s(i);
73             int pre = -1;
74             for (int z = pos; z < tot; z++) {
75                 if (pre == -1 || pre == ax[z].x) pre = ax[z].x;
76                 else break;
77                 int x1 = ax[z].y;
78                 int jj = j | (1 << ax[z].id);
79                 int sum = dp[i][j] + ax[z].sud;
80                 dp[x1][jj] = max(dp[x1][jj], sum);
81             }
82         }
83     }
84     if (maxn[(1 << n) - 1] >= 0) printf("%d\n", maxn[(1 << n) - 1]);
85     else printf("-1\n");
86     return 0;
87 }

View Code

E - Nature Reserve

题意：在二维坐标上，有动物的栖息地和一条河流，河流在y=0上，即为X轴。现在要建一个圆形的动物保护区，让动物都在里面，同时这个圆要求和X轴相切。因为只能相切，如果出现动物在X轴两侧的情况输出-1，即不能满足情况。

思路：我们二分半径，然后由于固定了与X轴相切，我们对于每一个点，就可以算出这个点在圆上的时候的圆心的极限距离。然后我们就可以求得每一个点的圆心的区间范围。然后所有点的区间范围都相交，那么证明这个半径可行，否则不可行。

代码：如果你的电脑和我的一样辣鸡，代码基本相同样例跑不出来，可能是精度的问题，建议您不要取很大的数字，取小点吧。

 1 /*
 2  I have a dream!A AC deram!!
 3  orz orz orz orz orz orz orz orz orz orz orz
 4  orz orz orz orz orz orz orz orz orz orz orz
 5  orz orz orz orz orz orz orz orz orz orz orz
 6 
 7  */
 8 
 9 #include<iostream>
10 #include<cstdio>
11 #include<cstdlib>
12 #include<cstring>
13 #include<cmath>
14 #include<string>
15 #include<algorithm>
16 #include<vector>
17 #include<queue>
18 #include<set>
19 #include<stack>
20 using namespace std;
21 typedef long long ll;
22 typedef unsigned long long ull;
23 const int maxn = 1e5 + 10;
24 #define pa pair<int,int>
25 
26 inline int read()
27 {
28     int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar())if (ch == '-')f = -1;
29     for (; isdigit(ch); ch = getchar())x = x * 10 + ch - '0'; return x * f;
30 }
31 
32 double x[maxn], y[maxn];
33 int N;
34 
35 bool check(long double R)
36 {
37     long double l = -100000000000000000.0, r = 100000000000000000.0, t;
38     for (int i = 1; i <= N; i++)
39     {
40         if (2 * R < y[i])
41             return 0;
42         t = sqrt(R*R - (R - y[i])*(R - y[i]));
43         if (l < x[i]-t) l = x[i] - t;
44         if (r > t+x[i]) r = t + x[i];
45     }
46     return l < r;
47 }
48 
49 int main()
50 {
51     scanf("%d", &N);
52     for (int i = 1; i <= N; i++)
53         scanf("%lf %lf", &x[i], &y[i]);
54     for (int i = 1; i <= N; i++)
55     {
56         if (y[i] * y[N] < 0)
57         {
58             printf("-1\n");
59             return 0;
60         }
61         y[i] = y[i] > 0 ? y[i] : -y[i];
62     }
63 
64     long double l = 0, r = 100000000000000000.0, mid;
65     for(int i = 1;i <= 100;i++)
66     {
67         mid = (l + r) / 2.0;
68         if (check(mid))
69             r = mid;
70         else
71             l = mid;
72     }
73     printf("%.10Lf\n", mid);
74     
75     return 0;
76 }

View Code

F - Graph And Its Complement

题意：给出n，a，b，问，是否有这样的一个图，有n个节点，分成a块，现将两两节点之间有边的把边删除，两两节点之间无边的建边，使得形成的图分成b块。如果有，输出YES，并且输出这个图的邻接矩阵，否则输出NO。这题难就难在是否能推出结论以及答案的输出。

思路：

任何一个图，不管分成多少块，经过上述操作后，必然变成一个联通图。

证：有n个节点，分成m块，任取一块，经过上述操作后，所取的这一块内的任意节点必定与其他块的所有节点相连！

这个结论换句话说就是，a和b里面，至少有一个数是1！知道这个结论就简单了，首先排除所有不含1的情况，然后，b==1的情况，我们将图分成a块，直接另前a-1块都只有一个节点，最后1块包含剩下的节点就行了。当然，对于a==1，只要将要输出反过来一下就可以了（注意，这里要讨论一下a和b都为1的情况，当n==2和n==3时，是不行的直接排除，其他情况都是可行的，特殊处理一下a和b都等于1的输出）
---------------------
作者：JIA-YAO
来源：CSDN
原文：https://blog.csdn.net/qq_41874469/article/details/80658410

代码：

#include "iostream"
#include "algorithm"
using namespace std;
int n,a,b;
char ch1='0',ch2='1';
int main() {
    cin>>n>>a>>b;
    if (a!=1&&b!=1||a==1&&b==1&&n<=3&&n>=2||a>n||b>n) {cout<<"NO"<<endl; return 0;}
    cout<<"YES"<<endl;
    if (a==1) swap(a,b), swap(ch1,ch2);
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            cout<<(i==j?'0':(i+1==j&&j>=a||j+1==i&&i>=a?ch1:ch2));
        }
        cout<<endl;
    }
}

View Code