基础算法题——P2926 [USACO08DEC]Patting Heads S（思维转变、剪枝）

柔情只为你懂 2022-11-22 00:10 146阅读 0赞

#### [Patting Heads S][] ####

今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。  
贝茜让 N(1 ≤ N ≤ 10 5) 头奶牛坐成一个圈。除了 1 号与 N 号奶牛外，i 号奶牛与 i-1 号和 i+1 号奶牛相邻。N 号奶牛与 1 号奶牛相邻。农夫约翰用很多纸条装满了一个桶，每一张包含了一个不一定是独一无二的 1 到 106 的数字。

接着每一头奶牛 i 从柄中取出一张纸条 Ai。每头奶牛轮流走上一圈，同时拍打所有手上数字能整除在自己纸条上的数字的牛的头，然后做回到原来的位置。牛们希望你帮助他们确定，每一头奶牛需要拍打的牛。

输入输出样例  
输入 \#1  
5  
2  
1  
2  
3  
4  
输出 \#1  
2  
0  
2  
1  
3  
说明/提示  
有五只牛编号分别为2,1,2,3,4。  
第一只牛被第二只、第三只牛拍，一共拍了 2 下。

--------------------

下面我写了三种方案，本质相同，只是查询、存储上不同。

#### 暴力法 ------ O(n2) ####

#### 解题思路 ####

管他三七二十一，直接把每头牛的编号从1倍开始都加上 1 ，最终输出答案减去自己就行！

#include<bits/stdc++.h>
    using namespace std;
    int A[100010], ans[1000010];
    
    int main(){ 
    // freopen("data.txt", "r", stdin);
    	int n;
    	scanf("%d", &n);
    	for(int i=0; i<n; i++){ 
    		scanf("%d", &A[i]);
    		for(int j=1; j*A[i]<=1000000; j++){ 
    			ans[j*A[i]]++;
    		}
    	}
    	
    	for(int i=0; i<n; i++){ 
    			printf("%d", ans[A[i]]-1);
    		if(i!=n-1) printf("\n");
    	}
    	
    	return 0;
    }

结果：T了3个点……

--------------------

#### 优化一：先统计，再暴力 ####

#### 解题思路 ####

我们需要先将每个编号对应牛的数量都统计下来，在（1 ~ 1000000）内把编号所对应的倍数都加上编号的数量。

for(int i=1; i<=1000000; i++)
    for(int j=1; j<=i&&j*i<=1000000; j++){ 
    	ans[i*j] += cnt[i];
    	if(i!=j) ans[i*j] += cnt[j];
    }

ps:注意去重  
整合代码

#include<bits/stdc++.h>
    using namespace std;
    int A[100010];
    int ans[1000010],cnt[1000010];
    int main(){ 
    	int n;
    	memset(ans, 0, sizeof(ans));
    	memset(cnt, 0, sizeof(cnt));
    // freopen("data.txt", "r", stdin);
    	scanf("%d", &n);
    	for(int i=0; i<n; i++){ 
    		scanf("%d", &A[i]);
    		cnt[A[i]]++;
    	}
    	
    	for(int i=1; i<=1000000; i++)
    	for(int j=1; j<=i&&j*i<=1000000; j++){ 
    		ans[i*j] += cnt[i];
    		if(i!=j) ans[i*j] += cnt[j];
    	}
    	
    	for(int i=0; i<n; i++){ 
    		printf("%d", ans[A[i]]-1);
    		if(i!=n-1) printf("\n");
    	}
    	
    	return 0;
    }

结果： AC

--------------------

#### 优化二：加快查找 ####

#### 解题思路 ####

与优化一原理几乎相同，不过这里采用了空间换时间的策略，减少了在查找环节中外层循环不必要的遍历。

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    int A[100010], B[100010];
    int cnt[1000010], ans[1000010];
    
    int main(){ 
    	int n;
    // freopen("data.txt", "r", stdin);
    	scanf("%d", &n);
    	for(int i=0; i<n; i++){ 
    		scanf("%d", &A[i]);
    		B[i] = A[i]; 
    		cnt[A[i]]++;
    	}
    	
    	sort(B, B+n);
    	int c = unique(B, B+n)-B;
    	for(int i=0; i<c; i++){ 
    		for(ll j=1; B[i]*j<=B[c-1]; j++){ 
    			ans[B[i]*j] += cnt[B[i]];
    		}
    	}
    	for(int i=0; i<n; i++)
    		printf("%d\n", ans[A[i]]-1);
    	
    	return 0;
    }

[Patting Heads S]: https://www.luogu.com.cn/problem/P2926