Codeforces Round #306 (Div. 2) D-E

「爱情、让人受尽委屈。」 2022-08-08 15:50 40阅读 0赞

D构造
首先我们想到的是做一个对称的图形，如同哑铃一般，中间的就是桥，两侧的就是双连通块。
那么我们想到的是构造一个双连通块，使得这个双连通块有一个点的度数为k−1，其他点的度数为k。
接着想到了完全图，对于一个完全图来说，每个点的度数为n−1，但是这样做不能够保证有一个点的度数为k−1，于是想到再加上一个点用k+2个点去构造。
此时发现当k是偶数的时候是不能够构造出来的。
奇数的时候，构造方法很多，随便画一下就行了。
我的方法是：将它连成一个环，然后除去最大的那个值(当做桥的接口)，从(1)~((k+1)/2)向着对面((k+1)/2+1)~(k+1)连边。然后k+2再从(k+1)/2和(k+1)/2+1往两侧连缺少边。

  1. // whn6325689
  2. // Mr.Phoebe
  3. // http://blog.csdn.net/u013007900
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <cstring>
  8. #include <climits>
  9. #include <complex>
  10. #include <fstream>
  11. #include <cassert>
  12. #include <cstdio>
  13. #include <bitset>
  14. #include <vector>
  15. #include <deque>
  16. #include <queue>
  17. #include <stack>
  18. #include <ctime>
  19. #include <set>
  20. #include <map>
  21. #include <cmath>
  22. #include <functional>
  23. #include <numeric>
  24. #pragma comment(linker, "/STACK:1024000000,1024000000")
  27. using namespace std;
  29. #define eps 1e-9
  30. #define PI acos(-1.0)
  31. #define INF 0x3f3f3f3f
  32. #define LLINF 1LL<<62
  33. #define speed std::ios::sync_with_stdio(false);
  35. typedef long long ll;
  36. typedef unsigned long long ull;
  37. typedef long double ld;
  38. typedef pair<ll, ll> pll;
  39. typedef complex<ld> point;
  40. typedef pair<int, int> pii;
  41. typedef pair<pii, int> piii;
  42. typedef vector<int> vi;
  44. #define CLR(x,y) memset(x,y,sizeof(x))
  45. #define CPY(x,y) memcpy(x,y,sizeof(x))
  46. #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
  47. #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
  48. #define debug(a) cout << #a" = " << (a) << endl;
  49. #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
  51. #define mp(x,y) make_pair(x,y)
  52. #define pb(x) push_back(x)
  53. #define lowbit(x) (x&(-x))
  55. #define MID(x,y) (x+((y-x)>>1))
  56. #define getidx(l,r) (l+r|l!=r)
  57. #define ls getidx(l,mid)
  58. #define rs getidx(mid+1,r)
  59. #define lson l,mid
  60. #define rson mid+1,r
  62. template<class T>
  63. inline bool read(T &n)
  64. {
  65.     T x = 0, tmp = 1;
  66.     char c = getchar();
  67.     while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
  68.     if(c == EOF) return false;
  69.     if(c == '-') c = getchar(), tmp = -1;
  70.     while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
  71.     n = x*tmp;
  72.     return true;
  73. }
  74. template <class T>
  75. inline void write(T n)
  76. {
  77.     if(n < 0)
  78.     {
  79.         putchar('-');
  80.         n = -n;
  81.     }
  82.     int len = 0,data[20];
  83.     while(n)
  84.     {
  85.         data[len++] = n%10;
  86.         n /= 10;
  87.     }
  88.     if(!len) data[len++] = 0;
  89.     while(len--) putchar(data[len]+48);
  90. }
  91. //-----------------------------------
  93. int k;
  94. vector<int> g[222];
  95. int main()
  96. {
  97.     scanf("%d",&k);
  98.     if(k==1)
  99.     {
  100.         puts("YES");
  101.         printf("%d %d\n",2,1);
  102.         printf("%d %d\n",1,2);
  103.     }
  104.     else if(k&1)
  105.     {
  106.         puts("YES");
  107.         for(int i=1; i<=k+1; i++)
  108.             for(int j=i+1; j<=k+1; j++)
  109.                 g[i].push_back(j);
  110.         for(int i=1; i<=k/2; i++)
  111.             for(int j=0; j<g[i].size(); j++)
  112.                 if(g[i][j]==(k+1)-i+1)
  113.                 {
  114.                     g[i][j]=k+2;
  115.                     g[(k+1)-i+1].push_back(k+2);
  116.                 }
  117.         printf("%d %d\n",(k+2)*2,(k+2)*k);
  118.         for(int i=1; i<=k+1; i++)
  119.             for(int j=0; j<g[i].size(); j++)
  120.                 printf("%d %d\n",i,g[i][j]);
  121.         for(int i=1; i<=k+1; i++)
  122.             for(int j=0; j<g[i].size(); j++)
  123.                 printf("%d %d\n",k+2+i,k+2+g[i][j]);
  124.         printf("%d %d\n",k+2,(k+2)*2);
  125.     }
  126.     else puts("NO");
  127.     return 0;
  128. }

E也是构造，题目不太好做，但是如果看了数据的话，很快就可以出来。
从给的四个式子中可以发现如果结果要为0，最后一位必须是0，现在要做的就是再最后一个0之前构造1，我们可以发现如果最后一个0的前面一个是1，那么不管这个1之前是什么最后答案都是1，因为0 ->1=1，1 ->1=1，即与前面的值无关，所以我们转过来考虑不可能的情况，考虑最后一个0的前面是0，因为要构1，又0->0=0，1->0=0也就是说这个0前面不能是1，依次类推可以得到，如果倒数第二个0的前面都是1，那必然无解，否则就有解

  1. // whn6325689
  2. // Mr.Phoebe
  3. // http://blog.csdn.net/u013007900
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <cstring>
  8. #include <climits>
  9. #include <complex>
  10. #include <fstream>
  11. #include <cassert>
  12. #include <cstdio>
  13. #include <bitset>
  14. #include <vector>
  15. #include <deque>
  16. #include <queue>
  17. #include <stack>
  18. #include <ctime>
  19. #include <set>
  20. #include <map>
  21. #include <cmath>
  22. #include <functional>
  23. #include <numeric>
  24. #pragma comment(linker, "/STACK:1024000000,1024000000")
  27. using namespace std;
  29. #define eps 1e-9
  30. #define PI acos(-1.0)
  31. #define INF 0x3f3f3f3f
  32. #define LLINF 1LL<<62
  33. #define speed std::ios::sync_with_stdio(false);
  35. typedef long long ll;
  36. typedef unsigned long long ull;
  37. typedef long double ld;
  38. typedef pair<ll, ll> pll;
  39. typedef complex<ld> point;
  40. typedef pair<int, int> pii;
  41. typedef pair<pii, int> piii;
  42. typedef vector<int> vi;
  44. #define CLR(x,y) memset(x,y,sizeof(x))
  45. #define CPY(x,y) memcpy(x,y,sizeof(x))
  46. #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
  47. #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
  48. #define debug(a) cout << #a" = " << (a) << endl;
  49. #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
  51. #define mp(x,y) make_pair(x,y)
  52. #define pb(x) push_back(x)
  53. #define lowbit(x) (x&(-x))
  55. #define MID(x,y) (x+((y-x)>>1))
  56. #define getidx(l,r) (l+r|l!=r)
  57. #define ls getidx(l,mid)
  58. #define rs getidx(mid+1,r)
  59. #define lson l,mid
  60. #define rson mid+1,r
  62. template<class T>
  63. inline bool read(T &n)
  64. {
  65.     T x = 0, tmp = 1;
  66.     char c = getchar();
  67.     while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
  68.     if(c == EOF) return false;
  69.     if(c == '-') c = getchar(), tmp = -1;
  70.     while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
  71.     n = x*tmp;
  72.     return true;
  73. }
  74. template <class T>
  75. inline void write(T n)
  76. {
  77.     if(n < 0)
  78.     {
  79.         putchar('-');
  80.         n = -n;
  81.     }
  82.     int len = 0,data[20];
  83.     while(n)
  84.     {
  85.         data[len++] = n%10;
  86.         n /= 10;
  87.     }
  88.     if(!len) data[len++] = 0;
  89.     while(len--) putchar(data[len]+48);
  90. }
  91. //-----------------------------------
  93. const int MAXN=100010;
  94. int a[MAXN],n;
  96. int main()
  97. {
  98.     scanf("%d",&n);
  99.     for(int i=1; i<=n; i++)
  100.         scanf("%d",&a[i]);
  101.     if(a[n])
  102.     {
  103.         puts("NO");
  104.         return 0;
  105.     }
  106.     if(n==1)
  107.         printf("YES\n0\n");
  108.     else if(a[n-1])
  109.     {
  110.         puts("YES");
  111.         for(int i=1; i<=n; i++)
  112.             printf("%d%s",a[i],i==n?"\n":"->");
  113.     }
  114.     else if(n==2)
  115.         printf("NO\n");
  116.     else
  117.     {
  118.         int las=n-2;
  119.         while(las && a[las])    las--;
  120.         if(las==0)
  121.             puts("NO");
  122.         else
  123.         {
  124.             puts("YES");
  125.             for(int i=1; i<las; i++)
  126.                 printf("%d->",a[i]);
  127.             printf("(0->(");
  128.             for(int i=las+1; i<=n-2; i++)
  129.                 printf("1->");
  130.             printf("0))->0\n");
  131.         }
  132.     }
  133.     return 0;
  134. }

发表评论

表情：
评论列表 （有 0 条评论，40人围观）

还没有评论，来说两句吧...

相关阅读

    相关 codeforces-round375-div2

    题目链接：[codeforces round 375 div2][] A题： 读一遍题目就知道是超级水的题目，，就是给你三个坐标，求三个坐标汇集到一个点所走的路程

    亦凉亦凉/ 0 赞/ 290 阅读