Codeforces Round #383 Div 1题解-白红宇的个人博客

Codeforces Round #383 Div 1题解

发布日期：2021-08-14 08:22:16 浏览次数：6 分类：技术文章

本文共 2694 字，大约阅读时间需要 8 分钟。

第一次打Div 1，感觉还是挺难的。。把基础题打完就日常划水了。。。。

题目大意：有n个人，每个人有一个后继，求在进行多少次传递后第i 个人跟第j个人对话的同时，第j个人也能跟第i个人对话（允许自己与自己对话）。$1\leq n \leq 100$ 这

题意花了我好多时间啊。。说白了就是要找环咯，把每条环求出来然后看环长度是不是偶数，是的话就除2，然后就个最大公约数就行了。

Code：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define maxn 110 7 typedef long long ll; 8 ll gcd(ll x,ll y){ 9     if (y==0) return x;10     return gcd(y,x%y);11 }12 int a[maxn],b[maxn],n;13 int main(){14     scanf("%d",&n);15     for (int i=1;i<=n;i++) scanf("%d",a+i);16     ll ans=1;17     for (int i=1;i<=n;i++) {18         memset(b,0,sizeof(b));19         int l=1;20         int t=i;21         while (!b[t]) {22             b[t]=l;23             l++;24             t=a[t];25         }26         if (b[t]!=1) {27             printf("-1\n");28             return 0;29         }30         l--;31         if (l%2==0) l/=2;32         ans=ans*1ll*((l)/gcd(ans,l));33     }34     cout<
          
           <

View Code

题目大意：给定n群女生，每群女生要么只能邀请一个女生要么就要全部邀请，求在满足重量限制的情况下的最大收益。

分组背包模型，可以直接$O((m+n)w)$解决，令$f[i][j]$为前i组重量为j的最大收益，则每个$f[i]$内就是最好的。

Code：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 #define maxn 1010 9 vector
            
              e[maxn];10 int w[maxn],b[maxn];11 bool bo[maxn];12 int f[maxn][maxn];13 int num[maxn][maxn];14 inline void addedge(int x,int y){15 e[x].push_back(y);e[y].push_back(x);16 }17 int n,m,W,N;18 void bfs(int u){19 static queue
             
               q;20 q.push(u);21 bo[u]=1;22 N++;23 while (!q.empty()){24 u=q.front();q.pop();25 num[N][0]++;26 num[N][num[N][0]]=u;27 for (int i=0;i
              
               =w[num[i][j]];k--) 51 f[i][k]=max(f[i-1][k-w[num[i][j]]]+b[num[i][j]],f[i][k]);52 sumb[i]+=b[num[i][j]];53 sumw[i]+=w[num[i][j]];54 }55 for (int j=W;j>=sumw[i];j--) 56 f[i][j]=max(f[i-1][j-sumw[i]]+sumb[i],f[i][j]);57 }58 printf("%d\n",f[N][W]);59 return 0;60 }

View Code

题目大意：有n对情侣坐在一张圆桌上吃饭，有两种食品，要求每个人和男女朋友不吃同一种东西，同时要求没有连续3个人吃同一种东西。

这题太坑了。。要把条件收束一点才能做。。。把没有连续的3个人吃同一种东西变成1跟2吃不同，3跟4吃不同...，然后就变成一个二分图模型就可以2-set解决了。。。（为什么是个二分图可以自己想一想）

Code：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define pb push_back 8 #define maxn 201000 9 vector
           
             e[maxn];10 int n,x,y;11 int col[maxn],b[maxn];12 int dfs(int x,int y){ 13 col[x]=y;14 b[x]=1;15 for (int i=0;i

View Code

转载于:https://www.cnblogs.com/New-Godess/p/6222807.html

转载地址：https://blog.csdn.net/weixin_30715523/article/details/96276682 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：面向对象第三单元

下一篇：BZOJ 1009 ：[HNOI2008]GT考试（KPM算法+dp+矩阵快速幂）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章