Codeforces Round #250 (Div. 1)

这几次CF都挺惨。。

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

数组开小，WA一次

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 2010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int v[N];

 int a[N];

 int main()

 {

     int i,j,n,m;

     cin>>n>>m;

     for(i =  ; i <= n; i++)

     scanf("%d",&v[i]);

     for(i = ; i <= m ;i++)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         a[i] = min(v[x],v[y]);

     }

     int ans = ;

     for(i =  ;i <= m ;i++)

     {

         ans+=a[i];

     }

     cout<<ans<<endl;

     return ;

 }

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

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

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

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 100010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int fa[N],res[N],a[N];

 int find(int x)

 {

     if(fa[x]!=x)

     {

         fa[x] = find(fa[x]);

         return fa[x];

     }

     return x;

 }

 struct node

 {

     int u,v,w;

 }p[N];

 bool cmp(node a,node b)

 {

     return a.w>b.w;

 }

 int main()

 {

     int n,m,i;

     cin>>n>>m;

     for(i = ; i <=n; i++)

     {

         scanf("%d",&a[i]);

         fa[i] = i;

         res[i] = ;

     }

     for(i = ;i <=m ;i++)

     {

         scanf("%d%d",&p[i].u,&p[i].v);

         p[i].w = min(a[p[i].u],a[p[i].v]);

     }

     sort(p+,p+m+,cmp);

     double ans = ;

     for(i = ; i <= m ;i++)

     {

         int tx = find(p[i].u),ty = find(p[i].v);

         if(tx!=ty)

         {

             fa[tx] = ty;

             ans+=(double)p[i].w*res[tx]*res[ty];

             res[ty]+=res[tx];

            // res[tx] = 0;

         }

     }

     printf("%.6f\n",(ans*)/(n*1.0*(n-)));

     return ;

 }

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

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 100010

 #define LL __int64

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 LL s[N<<],lm[N<<];

 int a[N];

 void up(int w)

 {

     s[w] = s[w<<]+s[w<<|];

     lm[w] = max(lm[w<<],lm[w<<|]);

 }

 void build(int l,int r,int w)

 {

     if(l==r)

     {

         s[w] = a[l];

         lm[w] = a[l];

         return ;

     }

     int m = (l+r)>>;

     build(l,m,w<<);

     build(m+,r,w<<|);

     up(w);

 }

 LL query(int a,int b,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         return s[w];

     }

     int m = (l+r)>>;

     LL res=;

     if(a<=m) res+=query(a,b,l,m,w<<);

     if(b>m) res+=query(a,b,m+,r,w<<|);

     return res;

 }

 void update(int p,int d,int l,int r,int w)

 {

     if(l==r)

     {

         s[w] = lm[w] = d;

         return ;

     }

     int m = (l+r)>>;

     if(p<=m) update(p,d,l,m,w<<);

     else update(p,d,m+,r,w<<|);

     up(w);

 }

 void find(int a,int b,int mod,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         if(lm[w] < mod)

             return ;

         if(l==r)

         {

             int k = s[w]%mod;

             s[w] = lm[w] = k;

             return ;

         }

         int m = (l+r)>>;

         find(a,b,mod,l,m,w<<);

         find(a,b,mod,m+,r,w<<|);

         up(w);

         return ;

     }

     int m = (l+r)>>;

     if(a<=m) find(a,b,mod,l,m,w<<);

     if(b>m) find(a,b,mod,m+,r,w<<|);

     up(w);

 }

 int main()

 {

     int n,m,i;

     cin>>n>>m;

     for(i = ; i <=n; i++)

     scanf("%d",&a[i]);

     build(,n,);

     int l,r,x,k;

     while(m--)

     {

         scanf("%d",&k);

         if(k==)

         {

             scanf("%d%d",&l,&r);

             LL k = query(l,r,,n,);

             printf("%I64d\n",k);

         }

         else if(k==)

         {

             scanf("%d%d%d",&l,&r,&x);

             find(l,r,x,,n,);

         }

         else

         {

             scanf("%d%d",&k,&x);

             update(k,x,,n,);

         }

     }

     return ;

 }

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

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

巴特西

Codeforces Round #250 (Div. 1)

最新文章

热门文章