首页 > 搜索 > DFS搜索 > hdu 2632 Samuel’s NOKIA N73-DFS-[解题报告]C++
2014
02-12

hdu 2632 Samuel’s NOKIA N73-DFS-[解题报告]C++

Samuel’s NOKIA N73

问题描述 :

Samuel got an NOKIA N73 from his two aunts in the summer of 2007,he is so delighted that he often shows his cellphone off in public. But now he has a problem of his N73,because the appearance of his mobile phone is getting much uglier. As is known to all N73 users,N73′s paint peels off easily. Due to Samuel’s poor protection nearly all the paint on N73 has peeled off. So he made up his mind to do something with his cellphone. Now the cellphone seller gave him two pieces of advise:
1.Sell N73 to buy a new one due to the fact that he has not got enough money.
2.Change the appearance of his N73,but if he changed the value of his cellphone will reduce.
He has to make a decision. However,the right choice that will be made is based on the price he can get if he sells and the changing fee in case he changed N73′s appearance.
Suppose the cellphone he bought at the price of x RMB,and the sell price is fixed at a RMB,if Samuel changes the appearance once the price of cellphone will be reduced by b(0<b<1).So the value of the cellphone after the change is x(1-b)^1.That is too say,if Samuel change for a second time the value is x(1-b)^2. Every time you should compare the left value with the sell price,if the former is higher than the later,Samuel will keep it for another month or he will sell it immediately. And the seller says he will change for Samuel for free.
The question is:
How many times will Samuel change the appearance of his N73 before he decide to sell it at a second hand price?

输入:

The input consists 2 parts:
the test case’s number t. For each case,the input will contains the original price of N73 x, the money a he will get if he sells,and the reducing rate b. Notice all the numbers here are integers except b.

输出:

The input consists 2 parts:
the test case’s number t. For each case,the input will contains the original price of N73 x, the money a he will get if he sells,and the reducing rate b. Notice all the numbers here are integers except b.

样例输入:

1
3000 2000 0.1

样例输出:

Samuel will change the appearance for 3 time(s),before he decide to sell it.

题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=2632

题意:

设a代表空,a’代表非空。

b代表空,b’代表非空。

那么:

有n个条件要求a和b不可同时为空,则:a->b’,b->a’

有p个条件要求a和b至少有一个为空,则:a’->b,b’->a

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

#define Maxn (1005 * 2)
#define Maxm (2005 * 4)
struct Edge
{
	int a,b;
}edge[Maxm];

int first[Maxn],next[Maxm];
int total;

//scc相关
int sccno[Maxn];
bool instack[Maxn];
int dfn[Maxn];
int low[Maxn];
int dfs_clock;
int scc_cnt;
stack <int> st;

//2sat相关

void addEdge(int a,int b)
{
	edge[total].a = a,edge[total].b = b;
	next[total] = first[a];
	first[a] = total++;
}

void init()
{
	total = 0;
	memset(first,-1,sizeof(first));
}
void tarjan(int u)
{
  	dfn[u] = low[u] = ++dfs_clock;
  	st.push(u);
  	instack[u] = true;
  	for(int i=first[u];i!=-1;i=next[i])
  	{
    	int v = edge[i].b;
    	if(!dfn[v])
    	{
      		tarjan(v);
      		low[u] = min(low[u],low[v]);
    	}
    	else if(instack[v])
    	{
      		low[u] = min(low[u],dfn[v]);
    	}
  	}
  	if(dfn[u] == low[u])
  	{
    	scc_cnt++;
    	while(1)
    	{
      		int v = st.top();
      		st.pop();
      		instack[v] = false;
      		sccno[v] = scc_cnt;
      		if(u == v) break;
    	}
  	}
}
void find_scc(int start,int n)
{
	scc_cnt = dfs_clock = 0;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
  	memset(instack,false,sizeof(instack));
  	while(!st.empty())
  	{
    	st.pop();
  	}
  	for(int i=start;i<=n;i++)
  	{
    	if(!dfn[i]) tarjan(i);
  	}
}

bool twoSet(int start,int n,int add)
{
	find_scc(start,n);
	for(int i=start;i<=n;i++)
	{
		int temp;
		if(i>add) temp = i-add;
		else temp = i+add;
		if(sccno[i] == sccno[temp]) return false;
	}
	
	return true;
}
int main()
{
	#ifndef ONLINE_JUDGE
		freopen("in.txt","r",stdin);
	#endif
	int n,m,p;
	int a,b;
	while(scanf(" %d %d %d",&m,&n,&p)!=EOF)
	{
		init();
		//不可同时为空
		for(int i=0;i<n;i++)
		{
			scanf(" %d %d",&a,&b);
			addEdge(a,b+m);
			addEdge(b,a+m);
		}
		//至少有一个为空
		for(int i=0;i<p;i++)
		{
			scanf(" %d %d",&a,&b);
			addEdge(b+m,a);
			addEdge(a+m,b);
		}
		if(!twoSet(1,2*m,m))
		{
			puts("No");
			continue;
		}
		puts("Yes");
	}
	return 0;
}

解题转自:http://blog.csdn.net/niuox/article/details/10161637


,
  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }