Codeforces Round #310 (Div. 2)简洁题解

A：原来是大水题，我还想去优化。。

结果是abs(num('0')-num('1'));

num表示一个符号的个数;

B：暴力模拟即可，每次判断是否能构造出答案。

C：俄罗斯套娃，套套套，捉鸡的E文。

抛开乱七八糟的题意；

思路就是除了1连续的不拆开，其他都拆，所以乱写就好了。

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 #include<string>

 using namespace std;

 #define N 222222

 typedef long long ll;

 int a[N];

 int main()

 {

     int n,k;

     cin>>n>>k;

     int ans=;

     for (int i=;i<=k;i++)

     {

         int m;

         cin>>m;

         for (int j=;j<=m;j++) cin>>a[j];

         ans+=m-;

         int pos=n+;

         for (int j=;j<=m;j++)

         if (a[j]==) pos=j;

             for (int j=pos+;j<=m;j++)

             if (a[j]-==j-pos)

             ans-=;

     }

     cout<<ans+n-;

     return ;

 }

D:我们先求出两座相邻的岛需要桥的范围是[x,y];即 node a.x,a.y;

思路关键词：贪心;

解析：先按y从小到大排序，相同，x大的在前。

即：

     int cmp(node a,node b)

     {

      if (a.y==b.y) return a.x>b.x;

      return a.y<b.y;

     }
然后对于每个桥我们都丢到set 中，可能有相同元素，加一维序号；

对于node 我们在set中 找大于node a.x 最前的 然后从set中删除。

为何这么做：
         因为排好序后，最前的优先级一定最高，想想。
         三种情况：
                   【       】 ...1
                 【         】 ...2
              【                  】...3
           满足1的一定满足2,满足2的不一定满足1,同理2满足，也满足3,满足3,不一定满足2

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 #include<string>

 using namespace std;

 #define N 222222

 typedef long long ll;

 #define mp make_pair

 struct node

 {

     ll x,y;

     int flag;

 }b[N];

 int n,m;

 ll l[N],r[N];

 set<pair<ll,int> >S;

 set<pair<ll,int> >::iterator it;

 struct node2

 {

     ll x;

     int idx;

 }a[N];

 int cmp(node a,node b)

 {

     if (a.y==b.y) return a.x>b.x;

     return a.y<b.y;

 }

 int ans[N];

 int main()

 {

     scanf("%d%d",&n,&m);

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

     scanf("%I64d%I64d",&l[i],&r[i]);

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

             scanf("%I64d",&a[i].x);

             S.insert(mp(a[i].x,i));

     }

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

     b[i].x=l[i+]-r[i],b[i].y=r[i+]-l[i],b[i].flag=i;

     sort(b+,b+n,cmp);

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

     {

         it=S.lower_bound(mp(b[i].x,));

         if (it==S.end()||(it->first>b[i].y))

         {

             cout<<"No";

             return ;

         }

         ans[b[i].flag]=it->second;

         S.erase(it);

     }

     cout<<"Yes"<<endl;

     for (int i=;i<n;i++) cout<<ans[i]<<" ";

     return ;

 }

E ：不会

巴特西

Codeforces Round #310 (Div. 2)简洁题解

最新文章

热门文章