首页 > ACM题库 > HDU-杭电 > hdu 1999 不可摸数-最小生成树-[解题报告]C++
2013
12-26

hdu 1999 不可摸数-最小生成树-[解题报告]C++

不可摸数

问题描述 :

s(n)是正整数n的真因子之和,即小于n且整除n的因子和.例如s(12)=1+2+3+4+6=16.如果任何
数m,s(m)都不等于n,则称n为不可摸数.

输入:

包含多组数据,首先输入T,表示有T组数据.每组数据1行给出n(2<=n<=1000)是整数。

输出:

包含多组数据,首先输入T,表示有T组数据.每组数据1行给出n(2<=n<=1000)是整数。

样例输入:

3
2
5
8

样例输出:

yes
yes
no

/*
分析:
    n只有1000,暴力打表就行了。
    这里有半个结论,为什么说是半个呢,因为只说了符合结论中的两种情况的话,n是
可触摸数,但没有说反之则n不可触摸(不过可以ac= =I,数据水吧),反eg:t=7-1=6;t
不是素数、t也不可以被拆成两个不同的素数,由这个得出7是不可触摸数,但是S(8)==7,
所以。。。
    下面代码能ac,不过是错误的,懒得再写了,参考参考看看怎么错的吧= =I。
    下面是那个结论:
    “
      摘:
        设输入n,因为1是所有数的约数,首先t=n-1;
    如果此时 t 为素数,则n一定能被找到,eg:t*t,由于t是素数,t*t 的约数有且只有1和t,所以成立。
    否则,如果 t 能表示为两个互不相等的素数的和,则n一定找到。
    eg:i 为素数且t-i 也为素数,则 i*(n-i) 的约数一定只有 1,i ,t-i; 所以成立。
    但是,if(i==(t-i)),则不一定,因为相同素数只取一次。
    证毕。
    仅供参考,如有不妥之处,请指教!
    摘自:http://acm.hdu.edu.cn/forum/read.php?tid=8210
    ”

                                                     2013-05-09(改)
*/

#include"stdio.h"
#include"string.h"
int main()
{
	int flag[1001];              //1代表可触摸
	int num[1001];
	int prime[222],k;
	int i,l,temp;
	int T;
	int n;


	memset(num,0,sizeof(num));
	memset(flag,0,sizeof(flag));
	num[0]=num[1]=1;
	k=0;
	for(i=2;i<=1000;i++)
	{
		if(num[i]==0)
		{
			for(temp=2*i;temp<=1000;temp+=i)	num[temp]=1;
			flag[i+1]=1;            //1000肯定不是素数,所以不必加上“if(i+1)<=1000”了。
			prime[k]=i;
			k++;
		}
	}


	for(i=0;i<k;i++)
	for(l=i+1;l<k;l++)
	{
		if(prime[i]+prime[l]+1<=1000)	flag[prime[i]+prime[l]+1]=1;
		else	break;
	}


	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		if(flag[n]==0)	printf("yes\n");
		else			printf("no\n");
	}
	return 0;
}

解题转自:http://blog.csdn.net/ice_crazy/article/details/7536612


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  4. #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;
    }