付忠庆的练习小笔记-Contest1009

Problem E: 最小公倍数和最大公约数问题

http://acm.qust.edu.cn/problem.php?cid=1009&pid=4

数论问题嘛，首先去除两个特殊情况

1两数互质输出0

2两数相等输出1

接下来讨论一般情况

实际上就是把t=y0/x0分解成两个因子,这两个因子互质的组合数,（可以实现保证一个数大于另一个数这样减少一半的搜索,结果*2即可（想想为什么））

 1 #include <iostream>
 2 #include <cmath>
 3 typedef long long LL;
 4 using namespace std;
 5 int lcd(LL a,LL b)  //英语不好...应该GCD更适合
 6 {
 7     if (b%a==0) return a;
 8     return lcd(b%a,a);
 9 }
10 int main()
11 {
12         LL x,y,t;
13         while (cin>>x>>y)
14         {
15             int ans=0;
16             if (lcd(x,y)==1) {cout<<0<<endl; continue;}//特殊情况
17             if (x==y) {cout<<1<<endl; continue;}//特殊情况
18             t=y/x;
19             for (int i=1;i<=sqrt(t);i++)//求根折半
20                 {
21                     if(t%i==0){
22                         if (lcd(i,t/i)==1) ans++; //互质《=》gcd==1
23                     }
24                 }
25             cout<<ans*2<<endl;
26         }
27         return 0;
28 }

Problem F: 选数

http://acm.qust.edu.cn/problem.php?cid=1009&pid=5

朴素求法枚举每种情况判断是不是质数

//是不是素数可以用筛法。我也不会写。。从网上copy的....所以在真正比赛的时候别忘了多带模板呦~~~

//枚举用的dfs ,有兴趣的可以深入研究呦~~~

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstring>
 4 using namespace std;
 5 int prime_len;
 6 int primes[500010];
 7 bool gash[500010];
 8 int gmap[21];
 9 bool vis[21];
10 int ans,n,k,tot;
11 void initPrimes(int n) {
12     memset(gash , 0 , sizeof(gash));
13     prime_len = 0;
14     for (int i=2 ; i<=n ; i++) {
15         if (!gash[i]) {
16             primes[prime_len++] = i;
17         }
18         for (int j=0 ; j<prime_len && ((i * primes[j]) <= n) ; j++) {
19             gash[i * primes[j]] = true;
20             if (i % primes[j] == 0) break;
21         }
22     }
23 }
24 bool isprime(int x)
25 {
26     if (x<=10000) return !gash[x];//前10000打表 超出单个判断,这个10000界限不固定,我主观上觉得10000之前查询比较频繁。可能是数据太弱要不然这道题很有可能TLE。。
27     for(int i=2;i<=sqrt(x);++i)
28         if (x%i==0) return false;
29     return true;
30 }
31 void dfs(int v,int s)
32 {
33     if(k==s) {
34         if (isprime(tot)) ans++;
35         return;
36     }
37     for(int i=v+1;i<=n;i++)
38     {
39         if (!vis[i]){
40             vis[i]=true; tot+=gmap[i]; dfs(i,s+1); vis[i]=false; tot-=gmap[i];
41         }
42     }
43 }
44 int main()
45 {
46     initPrimes(10000);
47     while(cin>>n>>k)
48     {
49         ans=0;
50         for(int i=1;i<=n;i++)
51             cin>>gmap[i];
52         for(int i=1;i<=n;i++)
53         {
54             memset(vis,false,sizeof(vis));
55             tot=0;
56             vis[i]=true;
57             tot+=gmap[i];
58             dfs(i,1);
59         }
60         cout<<ans<<endl;
61     }
62     return 0;
63 }

Problem G: ISBN号码

http://acm.qust.edu.cn/problem.php?cid=1009&pid=6

整体逻辑简单但就是那个'X‘很恶心，因为'X'不在'9'的后面啊~~（而是’:‘）所以我们可以一开始发现最后一个是'X'那就换成':'，到算法的最后如果有必要输出字符串再转换回来

.....其他的都看代码吧...

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 string str;
 5 int tab[]={0,2,3,4,6,7,8,9,10};
 6 const int key = 12;
 7 int main()
 8 {
 9     while(cin>>str)
10     {
11         if(str[key]=='X') str[key]=':'; //刚开始转换
12         int temp=0;
13         for(int i=0;i<9;i++) temp+=(str[tab[i]]-'0')*(i+1);
14         if (temp%11==str[key]-'0') {cout<<"Right"<<endl;continue;}
15         str[key]=temp%11+'0';
16         if(str[key]==':') str[key]='X'; //最后变回来
17         cout<<str<<endl;
18     }
19     return 0;
20 }

Problem H: 立体图

http://acm.qust.edu.cn/problem.php?cid=1009&pid=7

从左向右从后向前依次建立，就ok了！想多了脑子就混乱了的说！自己可以copy下来编译一下试试哟~~

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <string>
 5 #define FORL(a,b,i) for(int i=a;i<b;++i)
 6 #define DFORL(a,b,i) for(int i=a-1;i>=b;--i)
 7 using namespace std;
 8 string map[500];
 9 int base[51][51],m,n;
10 void cons(int &a,int &b)
11 {
12     int x=a,y=b;
13     a=2*a;
14     b=4*y+a;
15     return;
16 }
17 void build(int x,int y,int h)
18 {
19     x += 3*h;
20     map[x].replace(y,5,"+---+");
21     map[x+1].replace(y,6,"|   |/");
22     map[x+2].replace(y,7,"|   | +");
23     map[x+3].replace(y,7,"+---+ |");
24     map[x+4].replace(y+1,6,"/   /|");
25     map[x+5].replace(y+2,5,"+---+");
26 }
27 void work(int x,int y,int n)
28 {
29     cons(x,y);
30     FORL(0,n,h)
31     build(x,y,h);
32 }
33 int main()
34 {
35     //x,y postion is 4*x+2*y,2*y
36     int m,n;
37     while(cin>>m>>n)
38     {
39         int high=0,width=0;
40         DFORL(m,0,i)
41             FORL(0,n,j)
42             {
43                 int x=i+1,y=j;
44                 cons(x,y);
45                 cin>>base[i][j];
46                 high=max(high,x+base[i][j]*3+2);
47             }
48         high--;
49         width=m*2+n*4;
50         // init
51         FORL(0,high+1,i)
52         map[i]=string(width+1,'.');
53         DFORL(m,0,i)
54             FORL(0,n,j)
55             work(i,j,base[i][j]);
56         //out
57         DFORL(high,0,i)
58         cout<<map[i]<<endl;
59     }
60 
61     return 0;
62 }