图论+思维(2019牛客国庆集训派对day2)

摘要:
~! a: b;102}103104 voidswapp(int&a,int&b)105{106a^=b^=a^=b;107}108109 int

题意:https://ac.nowcoder.com/acm/contest/1107/J

n个点的完全图编号0-n-1,第i个点的权值为2^i,原先是先手选取一些边,然后后手选取一些点,满足先手选取的所有边对应的两点至少要有一个,并且总的权值和最少,现在给你后手选取的点得权值和,求先手选取边的方案数(就是先手选取完一些边,要求后手选一些点使所有边都被覆盖到并且权值和最小,现在告诉你后手的权值和问你先手的取法方案数

思路:

因为权值是二进制的形式给的,所以对应1的位置即对应的这个点也选了,对于选取的点来说,一定要和比他权值更大的点并且是没有被选择的点相连接,这样这个点才必须选择,和比他权值小的点可连可不连。https://blog.csdn.net/mmk27_word/article/details/90670209

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\Users\13606\Desktop\草稿.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 23 //******************
 24 int abss(int a);
 25 int lowbit(int n);
 26 int Del_bit_1(int n);
 27 int maxx(int a,int b);
 28 int minn(int a,int b);
 29 double fabss(double a);
 30 void swapp(int &a,int &b);
 31 clock_t __STRAT,__END;
 32 double __TOTALTIME;
 33 void _MS(){__STRAT=clock();}
 34 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
 35 //***********************
 36 #define rint register int
 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)
 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)
 39 #define mem(a,b) memset(a,b,sizeof(a))
 40 #define pr printf
 41 #define sc scanf
 42 #define ls rt<<1
 43 #define rs rt<<1|1
 44 typedef long long ll;
 45 const double E=2.718281828;
 46 const double PI=acos(-1.0);
 47 //const ll INF=(1LL<<60);
 48 const int inf=(1<<30);
 49 const double ESP=1e-9;
 50 const int mod=(int)1e9+7;
 51 const int N=(int)1e6+10;
 52 
 53 char temp[N],k[N];
 54 ll dp[N],er[N];
 55 
 56 ll get(int pos,int n)
 57 {
 58     ll ans=1;
 59     ans=ans*((er[dp[pos]]-1+mod)%mod)%mod*er[n-pos]%mod;
 60     return ans;
 61 }
 62 
 63 int main()
 64 {
 65     int n;
 66     er[0]=1;
 67     er[1]=2;
 68     for(int i=2;i<=N-3;++i)
 69         er[i]=er[i-1]*2,er[i]%=mod;
 70     while(~sc("%d%s",&n,temp+1))
 71     {
 72         int l=strlen(temp+1);
 73         int cnt=n-l;
 74         for(int i=1;i<=cnt;++i)
 75             k[i]='0';
 76         for(int i=1;i<=l;++i)
 77             k[i+cnt]=temp[i];
 78         l=cnt+l;
 79         for(int i=1;i<=l;++i)
 80         {
 81             dp[i]=dp[i-1];
 82             if(k[i]=='0')
 83                 dp[i]++;
 84         }
 85         ll ans=1;
 86         for(int i=1;i<=l;++i)
 87         {
 88             if(k[i]=='0')continue;
 89             ans*=get(i,l);
 90             ans%=mod;
 91         }
 92         pr("%lld
",ans);
 93     }
 94     return 0;
 95 }
 96 
 97 /**************************************************************************************/
 98 
 99 int maxx(int a,int b)
100 {
101     return a>b?a:b;
102 }
103 
104 void swapp(int &a,int &b)
105 {
106     a^=b^=a^=b;
107 }
108 
109 int lowbit(int n)
110 {
111     return n&(-n);
112 }
113 
114 int Del_bit_1(int n)
115 {
116     return n&(n-1);
117 }
118 
119 int abss(int a)
120 {
121     return a>0?a:-a;
122 }
123 
124 double fabss(double a)
125 {
126     return a>0?a:-a;
127 }
128 
129 int minn(int a,int b)
130 {
131     return a<b?a:b;
132 }

免责声明:文章转载自《图论+思维(2019牛客国庆集训派对day2)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Resistors in Parallel(找规律+大数)SOS--DP(基础版本)未压缩空间下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

图论总结

①DJ #include<iostream>#include<cstring>#include<cstdio>#include<queue> using namespacestd; #define e exit(0) #define re register #define inf 2147483647 co...

一次小总结:图论+数论+学长们

  用cnblogs就是好,用word编辑好了可以直接粘过去。   六 图论D1.串联位运算、bitset、搜索(迭代加深、估价)、树上数据结构、生成树、图的遍历(欧拉回路、拓扑排序、连通分量、2-SAT不懂不懂)+TEST 日 休息 一 图论D2.最短路、差分约束、网络流 二 图论D3.网络流加深+TEST 三 自习数学+数论讲解 四 数论讲解 五 即将进...

图论浅析--最小生成树之Kruskal

Kruskal 算法思想 将带权图G的所有边按权值从小到大排序; 图G’初始为空; 从小到大取边; 若加入边(x,y),G’中有环,则放弃此边,继续取边; 将边(x,y)加入图G’中,直至加入n-1条边。 过程演示 Code struct Edge { int u,v,w; }e[NUM]; int n; int f[NUM];...

HDU 3072 图论scc

1 #include<bits/stdc++.h> 2 #define INF 0x7fffffff 3 using namespacestd; 4 const int MAXN = 50010;//点数 5 const int MAXM = 100100;//边数 6 structEdge { 7 intto,next,val...

HDU 1827 Summer Holiday 图论scc

先scc缩点,变成DAG,显然ans=入度为0的scc个数,每个scc的答案就是scc内点权最小的值。 1 #include<bits/stdc++.h> 2 #define INF 0x7fffffff 3 using namespacestd; 4 const int MAXN = 2010;//点数 5 const int MAXM =...

csp赛前刷题篇 图论篇 [USACO09FEB]Revamping Trails G

洛谷p2939 本题为标准的分层图板子题,借由此题再次理解一噶分层图。 分层图 啥是分层图哩 就是你建的这个图,他有好几层,神不神奇,腻不腻害!? 分层图是干啥的呢 就是用于处理对边存在额外操作。腻害吧!! 至于具体哩,图请自行搜索dalao博客 各层图之间各自按照原图联通关系连边。 注意只能出上一层到下一层,就像你修了一条道,不可能再修回去。 细节问题 有...