本文共 1128 字,大约阅读时间需要 3 分钟。
【题目链接】
【题目大意】
有一个递归代码:
go(int dep, int n, int m)
begin
output the value of dep.
if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)
end
关键是看第四行, 如果满足条件dep < m and x[a[dep]] + x[b[dep]] != c[dep] 那么就可以进入下一层递归, x数组只取{0, 1}, c数组取{ 0,1,2 }, 而a和b数组取0~m, m是最大能递归的层数,也是数组x的大小。 问最多能递归多少层?
【思路】
对于每个x【i】, 只能取0或者1, 在每一层中如果满足条件就可以进入下一层,这个题非常像 , 做法也是一样的。
二分最多能递归的层数,然后对这些层数进行2-sat的建图,判断即可。
【代码】
#include#include #include #include #include #include #define MP make_pair#define SQ(x) ((x)*(x))using namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 10010;const int VN = MAXN*2;const int EN = VN*4;int n, m, s;int a[MAXN], b[MAXN], c[MAXN];struct Graph{ int size, head[VN]; struct{int v, next; }E[EN]; void init(){size=0; memset(head, -1, sizeof(head)); }; void addEdge(int u, int v){ E[size].v = v; E[size].next = head[u]; head[u] = size++; }}g;class Two_Sat{public: bool check(const Graph& g, const int n){ scc(g, 2*n); for(int i=0; i > 1; buildGraph(mid); if(sat.check(g, m)){ l = mid+1; ans = mid; } else r = mid; } printf("%d\n", ans); } return 0;}
转载地址:http://vpzni.baihongyu.com/