Codeforces Round #580 (Div. 2)-蒲公英云

A题—-水题：

int a[105],b[105];
int main()
{
    int n1,n2;
    cin>>n1;
    for(int i=0;i<n1;i++)
    cin>>a[i];
    sort(a,a+n1);
    cin>>n2;
    for(int i=0;i<n2;i++)
    cin>>b[i];
        sort(b,b+n2);
    cout<<a[n1-1]<<" "<<b[n2-1]<<endl;
 }

B题—-模拟题

题意：给定n个数字（数字范围为−10^9≤ai≤10^9），每个数字可以进行原基础上的加一或减一操作，问多少次操作之后这些数字的乘积为1？

思路：

要数字乘积为1 那么这些数字必须为-1与1

所以我们需要做的是让这些数字都靠近1与-1，另外处理数字0—-使他看情况变为1或-1

-3 -5 -5 -1 0 0 0 1 2

注明：这里需要处理一些细节

int main()
{
    int n,t;
    cin>>n;
    int a=0,b=0,c=0;
    long long ans=0;
    for(int i=0;i<n;i++)
    {
        cin>>t;
        if(t==0)
        c++;
        else if(t>0)
        {
            a++;
            ans+=(t-1);
        }
        else
        {
            b++;
            ans+=(-1-t);
        }
     }
        if(c==0)
        {
            if(a==0&&b)
            {
                if(b%2==1)
                ans+=2;
            }
            if(a&&b)
            {
                if(b%2==1)
                ans+=2;
            }
        }
        else
        {
            ans+=c;
        }
        cout<<ans<<endl;
 }

C题：规律模拟题

题意:给定数字n,让你求一个环，环上有2n个数字（1,2…2n），环上形成连续的n个数字其和与其他的环上形成连续的n个数字的和相差不大于1，问是否存在这样的环，存在输出该环

思路：我们可以得出a[i]-a[i+n]=1(或者-1) 即a[i]与a[i+n]相差1

我们只需求出n对这样的数每对数两数之间相差1 其实就是1,2 ；3,4；5,6；然后我们注意到每次都是先相差正1，然后下一组相差负1

int a[200005];
int main()
{
    int n;
    cin>>n;
    n=2*n; 
    int sum=n*(n+1)/2;
    int x=(sum+1)/2;
    a[1]=1,a[n]=n;
    if((n/2)%2==0)
    cout<<"NO"<<endl;
    else{
    int t=1;
    for(int i=1;i<=n/2;i++)
    {
        t=2*i;
        if(i%2)
        {
            a[i]=t-1,a[n/2+i]=t;
        }
        else
        {
            a[i]=t,a[n/2+i]=t-1;
        }        
    }
    cout<<"YES"<<endl;
    for(int i=1;i<=n;i++)
    {
        if(i!=n)
        cout<<a[i]<<" ";
        else
        cout<<a[i]<<endl;
    }
    }
 }

d题

思路：题目可以转化为求图中的最小环，从一个点去找路径，然后结束条件就是路径点又回到了起点，这就是环。然后记录最小的环的边数目。

枚举每个点的最小环

给你n个点,每个点都有权值,两个点当且仅当(ai&aj)!=0时才会有边.
让你求最小的循环长度 (循环中的点要大于等于3)

点的权值的上限是1e18,比2^60小.
易得结论:n>120时必定存在一个循环长度为3的环
假设前60个点每个点都不会与其他点连边,这是最坏的情况,也就是每个点都是2的k次方这样子
那么后面不论加什么点都会与前面60个点的其中至少一个点连有边,再考虑最坏的情况,加入120
个点后恰好每两个点有边,此时再加入任意一个点,即存在一个环.
注意点的权值可以为0,把权值为0的点剔除就好.
对于n<=120 跑个floyd最小环

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define maxn 100010
 5 const int inf = 0x3f3f3f3f; 
 6 ll a[maxn];
 7 int path[500][500];
 8 ll cost;
 9 int vis[500],m;
10 
11 void dfs(int u,int cnt,int x)//当前点  边数   遍历点的起点 
12 {
13     vis[u]=1;
14     if(cnt>cost) //剪枝 
15     return;
16     if(cnt>=3&&path[u][x])
17     {
18         cost=cnt;
19         return;
20      } 
21     
22     for(int v=1;v<=m;v++)
23     {
24         if(vis[v]==0&&path[u][v]&&v!=x)
25         {
26         //    vis[i]=1;
27             dfs(v,cnt+1,x);
28             vis[v]=0;
29         }
30     }
31     
32 }
33 
34 int main()
35 {
36     int n;
37     scanf("%d",&n);
38     ll a[maxn],kk;
39     m=0;
40     for(int i=1;i<=n;i++)
41     {
42         scanf("%lld",&kk);
43         if(kk!=0)
44         {
45             m++;
46             a[m]=kk;
47         }
48         
49     }
50     
51     if(n>=200)
52     printf("3\n");
53     else
54     {
55     //    memset(path,-1,memset(path));
56         for(int i=1;i<=m;i++)
57         for(int j=1;j<=m;j++)
58         {
59             if(a[i]&a[j])
60             path[i][j]=1;
61         }
62         ll ans=1ll*inf; 
63         for(int i=1;i<=m;i++)//遍历每个点的最小环的长度 
64         {
65             memset(vis,0,sizeof(vis));
66             cost=1ll*inf;
67             dfs(i,1,i);
68             ans=min(ans,cost);
69         }
70         
71         cout << (ans == inf ? -1 : ans) << endl;
72     }
73  }

借鉴的原文链接：https://blog.csdn.net/qq\_41608020/article/details/99716916

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m, mp[500][500];
LL a[N], b[N], ans = 1LL * inf, now;//1LL 是为了在计算时，把int类型的变量转化为long long，然后再赋值给long long类型的变量。 
bool vis[500];
void dfs(int u, int w, int rt) { //w表示该路径的边的数目  u表示路径现在走到的点   rt表示枚举的这个环的起点也即终点 
    vis[u] = 1;
    if(w > now) return;   //所走的步数大于之前存的最短路径 
    if(w >= 3 && mp[u][rt]) {  //说明走的路径形成环
        now = w;
        return;
    }
    for(int v = 1; v <= m; v++) {  //可走的路径 
        if(mp[u][v] && vis[v] == 0 && v != rt){
            dfs(v, w + 1, rt);
            vis[v] = 0;
        }
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        if(a[i]) b[++m] = a[i];//b数组存非0的所以数字 
    }
    if(m >= 200) puts("3");  //这个是大佬们发现的规律吧   
    else {
        for(int i = 1; i <= m; i++) 
        for(int j = 1; j <= m; j++) 
        if(b[i] & b[j]) mp[i][j] = 1; //说明节点i,j被连接 
        for(int i = 1; i <= m; i++) { //枚举环的起点 
            memset(vis, 0, sizeof vis);
            now = inf;
            dfs(i, 1, i); //路径当前所走到的点     路径点的个数    路径起点 
            ans = min(ans, now);//获得最短的周期 
        }
        cout << (ans == inf ? -1 : ans) << endl;
    }
}