HDU 5211 Mutiple 水题

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5211

题解:

1、筛法:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 const int maxn=10000+10;
 9 const int INF=0x3f3f3f3f;
10
11 int n;
12 int a[maxn],mmp[maxn];
13 vector<int> mat[maxn];
14
15 void init(){
16     for(int i=0;i<maxn;i++) mat[i].clear();
17     memset(mmp,-1,sizeof(mmp));
18 }
19
20 int main(){
21     while(scanf("%d",&n)==1&&n){
22         init();
23         int maxa=-1;
24         for(int i=1;i<=n;i++){
25             scanf("%d",a+i);
26             maxa=max(maxa,a[i]);
27             mmp[a[i]]=i;
28         }
29         int ans=0;
30         for(int i=1;i<=n;i++){
31             int minm=INF;
32             for(int j=2;j*a[i]<=maxa;j++){
33                 if(mmp[j*a[i]]!=-1&&mmp[j*a[i]]>i){
34                     minm=min(minm,mmp[j*a[i]]);
35                 }
36             }
37             if(minm==INF) minm=0;
38             ans+=minm;
39         }
40         printf("%d\n",ans);
41     }
42     return 0;
43 }

2、倒着扫回来,不断刷新约数的值

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 const int maxn=10000+10;
 9 const int INF=0x3f3f3f3f;
10
11 int n;
12 int a[maxn],mmp[maxn];
13
14 void init(){
15     memset(mmp,0,sizeof(mmp));
16 }
17
18 int main(){
19     while(scanf("%d",&n)==1&&n){
20         init();
21         for(int i=1;i<=n;i++) scanf("%d",a+i);
22         int ans=0;
23         for(int i=n;i>=1;i--){
24             ans+=mmp[a[i]];
25             for(int j=1;j*j<=a[i];j++){
26                 if(a[i]%j==0){
27                     mmp[j]=i;
28                     mmp[a[i]/j]=i;
29                 }
30             }
31         }
32         printf("%d\n",ans);
33     }
34     return 0;
35 }
时间: 04-13

HDU 5211 Mutiple 水题的相关文章

HDU 2092 整数解 --- 水题

x+y = n, x*y = m; y = n - x; x * ( n - x) = m nx - x^2 = m; x^2 - nx + m = 0; △ = sqrt(n^2 - 4m) 要有整数解即△需要为可开方数即可. /* HDU 2092 整数解 --- 水题 */ #include <cstdio> #include <cmath> int main() { double n, m; while (scanf("%lf%lf", &n,

hdu 5210 delete 水题

Delete Time Limit: 1 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=5210 Description wld有n个数(a1,a2,...,an),他希望进行k次删除一个数的操作,使得最后剩下的n−k个数中有最多的不同的数,保证1≤n≤100,0≤k<n,1≤ai≤n(对于任意1≤i≤n) Input 多组数据(最多100组)对于每组数据:第一行:一个数n表示数的个数接下来一行:

hdu 5211 Mutiple 数学

Mutiple Time Limit: 1 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=5211 Description wld有一个序列a[1..n], 对于每个1≤i<n, 他希望你求出一个最小的j(以后用记号F(i)表示),满足i<j≤n, 使aj为ai的倍数(即aj mod ai=0),若不存在这样的j,那么此时令F(i) = 0保证1≤n≤10000,1≤ai≤10000 对于任意

HDU 5703 Desert 水题 找规律

已知有n个单位的水,问有几种方式把这些水喝完,每天至少喝1个单位的水,而且每天喝的水的单位为整数.看上去挺复杂要跑循环,但其实上,列举几种情况之后就会发现是找规律的题了= =都是2的n-1次方,而且这题输出二进制数就行了......那就更简单了,直接输出1,然后后面跟n-1个0就行了╮(╯_╰)╭ 下面AC代码 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm>

hdu 4802 GPA 水题

GPA Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4802 Description In college, a student may take several courses. for each course i, he earns a certain credit (ci), and a mark ranging from A to F, which is c

hdu 1015 Safecracker 水题一枚

题目链接:HDU - 1015 === Op tech briefing, 2002/11/02 06:42 CST === "The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World

hdu 5495 LCS 水题

LCS Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=5495 Description 你有两个序列\{a_1,a_2,...,a_n\}{a?1??,a?2??,...,a?n??}和\{b_1,b_2,...,b_n\}{b?1??,b?2??,...,b?n??}. 他们都是11到nn的一个排列. 你需要找到另一个排列\{p_1,p_2,...,p_n\}{p?1?

hdu 5326 Work 水题

Work Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 225    Accepted Submission(s): 166 Problem Description It’s an interesting experience to move from ICPC to work, end my college life and star

hdu 4493 Tutor 水题

Tutor Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4493 Description Lilin was a student of Tonghua Normal University. She is studying at University of Chicago now. Besides studying, she worked as a tutor tea