首页 > 代码库 > Codeforces Round #250 (Div. 1)

Codeforces Round #250 (Div. 1)

2024-07-06 21:33:55   231人阅读

这几次CF都挺惨。。

A

没条边权设为两端点的最小点权，最后加起来。

数组开小，WA一次

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 2010
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 int v[N];
18 int a[N];
19 int main()
20 {
21     int i,j,n,m;
22     cin>>n>>m;
23     for(i =  1; i <= n; i++)
24     scanf("%d",&v[i]);
25     for(i = 1; i <= m ;i++)
26     {
27         int x,y;
28         scanf("%d%d",&x,&y);
29         a[i] = min(v[x],v[y]);
30     }
31     int ans = 0;
32     for(i = 1 ;i <= m ;i++)
33     {
34         ans+=a[i];
35     }
36     cout<<ans<<endl;
37     return 0;
38 }
View Code

 

B

以点权排序，删除某个点之后，哪些比它点权大的不再连通就说明那些点对的p值肯定为他的点权，想到了这点，却忘了并差集可以使不连通块连通。

做法：给每个边一个边权，为两端点的最小点权，以边权从大到小排序，依次进行合并，若当前不连通这以这个边权*块1的数量*块2的数量

排序的时候 错把m写成n wa一次。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 100010
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 int fa[N],res[N],a[N];
18 int find(int x)
19 {
20     if(fa[x]!=x)
21     {
22         fa[x] = find(fa[x]);
23         return fa[x];
24     }
25     return x;
26 }
27 struct node
28 {
29     int u,v,w;
30 }p[N];
31 bool cmp(node a,node b)
32 {
33     return a.w>b.w;
34 }
35 int main()
36 {
37     int n,m,i;
38     cin>>n>>m;
39     for(i = 1; i <=n; i++)
40     {
41         scanf("%d",&a[i]);
42         fa[i] = i;
43         res[i] = 1;
44     }
45     for(i =1 ;i <=m ;i++)
46     {
47         scanf("%d%d",&p[i].u,&p[i].v);
48         p[i].w = min(a[p[i].u],a[p[i].v]);
49     }
50     sort(p+1,p+m+1,cmp);
51     double ans = 0;
52     for(i = 1; i <= m ;i++)
53     {
54         int tx = find(p[i].u),ty = find(p[i].v);
55         if(tx!=ty)
56         {
57             fa[tx] = ty;
58             ans+=(double)p[i].w*res[tx]*res[ty];
59             res[ty]+=res[tx];
60            // res[tx] = 0;
61         }
62     }
63     printf("%.6f\n",(ans*2)/(n*1.0*(n-1)));
64     return 0;
65 }
View Code

 

D

没有比这题更悲伤了，最后20分钟看，十几分钟敲完，最后十几秒交上，wa了，，发现少写了个lm。。。

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 using namespace std;
 11 #define N 100010
 12 #define LL __int64
 13 #define INF 0xfffffff
 14 const double eps = 1e-8;
 15 const double pi = acos(-1.0);
 16 const double inf = ~0u>>2;
 17 LL s[N<<2],lm[N<<2];
 18 int a[N];
 19 void up(int w)
 20 {
 21     s[w] = s[w<<1]+s[w<<1|1];
 22     lm[w] = max(lm[w<<1],lm[w<<1|1]);
 23 }
 24 void build(int l,int r,int w)
 25 {
 26     if(l==r)
 27     {
 28         s[w] = a[l];
 29         lm[w] = a[l];
 30         return ;
 31     }
 32     int m = (l+r)>>1;
 33     build(l,m,w<<1);
 34     build(m+1,r,w<<1|1);
 35     up(w);
 36 }
 37 LL query(int a,int b,int l,int r,int w)
 38 {
 39     if(a<=l&&b>=r)
 40     {
 41         return s[w];
 42     }
 43     int m = (l+r)>>1;
 44     LL res=0;
 45     if(a<=m) res+=query(a,b,l,m,w<<1);
 46     if(b>m) res+=query(a,b,m+1,r,w<<1|1);
 47     return res;
 48 }
 49 void update(int p,int d,int l,int r,int w)
 50 {
 51     if(l==r)
 52     {
 53         s[w] = lm[w] = d;
 54         return ;
 55     }
 56     int m = (l+r)>>1;
 57     if(p<=m) update(p,d,l,m,w<<1);
 58     else update(p,d,m+1,r,w<<1|1);
 59     up(w);
 60 }
 61 void find(int a,int b,int mod,int l,int r,int w)
 62 {
 63     if(a<=l&&b>=r)
 64     {
 65         if(lm[w] < mod) 
 66             return ;
 67         if(l==r)
 68         {
 69             int k = s[w]%mod;
 70             s[w] = lm[w] = k;
 71             return ;
 72         }
 73         int m = (l+r)>>1;
 74         find(a,b,mod,l,m,w<<1);
 75         find(a,b,mod,m+1,r,w<<1|1);
 76         up(w);
 77         return ;
 78     }
 79     int m = (l+r)>>1;
 80     if(a<=m) find(a,b,mod,l,m,w<<1);
 81     if(b>m) find(a,b,mod,m+1,r,w<<1|1);
 82     up(w);
 83 }
 84 int main()
 85 {
 86     int n,m,i;
 87     cin>>n>>m;
 88     for(i = 1; i <=n; i++)
 89     scanf("%d",&a[i]);
 90     build(1,n,1);
 91     int l,r,x,k;
 92     while(m--)
 93     {
 94         scanf("%d",&k);
 95         if(k==1)
 96         {
 97             scanf("%d%d",&l,&r);
 98             LL k = query(l,r,1,n,1);
 99             printf("%I64d\n",k);
100         }
101         else if(k==2)
102         {
103             scanf("%d%d%d",&l,&r,&x);
104             find(l,r,x,1,n,1);
105         }
106         else
107         {
108             scanf("%d%d",&k,&x);
109             update(k,x,1,n,1);
110         }
111     }
112     return 0;
113 }
View Code

 

小小总结下：貌似每题都有注意不到的地方，还各不相同，说明不是我记忆力的问题，是注意力的问题，有空多刷几场TC，我印象中TC没有不出问题的时候，所以我现在依旧安稳的呆在DIV2。

发现学的多就会想得多，B题一直想在强连通分量上，心里觉得图的东西不是特别会，隐隐约约的觉得应该做不出来了，可又发现过的人好多，应该是会的，比赛的时候想的太多了，思路没有前行在正确的方向，注意力不能完全集中在题上。


联系
我们