做题记录 洛谷P2671求和

做题记录 洛谷P2671求和,第1张

做题记录 洛谷P2671求和

题目链接

思路1:

三层循环暴力枚举,复杂度 O ( n 3 ) O(n^3) O(n3),对应20分。
没用这种方法,代码就不水了。

思路2:

不难发现与中间点y没什么关系,只需保证x,y,z成等差数列即可。因此枚举x,z,若(x+z)/2到x和z的距离相等,则可以判断是否满足条件。
优化:容易发现公差必然为偶数,所以枚举x+2,x+4…z即可,复杂度仍为 O ( n 2 ) O(n^2) O(n2)但常数降低一半,能得40分。

for(int i=1; i 
思路3: 

color[]改为记录每种颜色出现的位置。
对每个x,二层循环枚举位置,当color[x][j]-colo[x][i]为偶数时就算数。
此种方法要开long long。
注意color[][]要开得足够大。经实验第二维开到50时能得60分。
不难发现color[][]中有效元素至多为n个。直接开大的二维数组会非常浪费,因此使用vector< vector< int > >,能得80分。

#include 
#include 
#include 
#define MOD 10007
const int M=(int)1e5+1,MAX_C=(int)1e5+1;
using namespace std;
typedef long long llong;
int num[M];
vector > color;
inline int res_x(int x) {
    int res=0,tot=color[x].size();
    for(int i=0; i 
思路4:正解 

将每个color[x]分为奇数、偶数两部分,不难发现两部分可以直接两两相加而无需判断。
假设color[x]的奇数部分共有k个元素,每个元素为 i m i_m im​,其对应的数据为 n i m n_{i_{m}} nim​​则其对答案的贡献为
∑ m = 1 k i m [ ( k − 1 ) n i m + ∑ j = m + 1 k n i j + ∑ j = 1 m − 1 n i j ] sum limits _{m=1}^{k}i_m[(k-1)n_{i_{m}}+sum limits_{j=m+1}^kn_{i_{j}}+sum limits_{j=1}^{m-1}n_{i_{j}}] m=1∑k​im​[(k−1)nim​​+j=m+1∑k​nij​​+j=1∑m−1​nij​​]
推导过程如下:

根据以上公式,可写出下面的代码:

#include 
#include 
#include 
#define MOD 10007
const int M=(int)1e5+1;
using namespace std;
typedef long long llong;
int num[M];

inline int sum(vector a) {
    int tot=a.size()-1,res=0;
    if(tot<=1)	return 0;
    for(int i=1; i<=tot; i++) {
        int index=a[i]-a[i-1];  //求当前下标
        int val=num[index];  //数值
        //对答案的贡献。注意
        llong now_res=(llong)val*(a[i-1]+(a[tot]-a[i])+index*(tot-1)); 
        res=(res+now_res)%MOD;
    }
    return res;
}

int main() {
    vector > odd,even;
    int n,m,res=0;
    scanf("%d%d",&n,&m);
    even.resize(m+1);
    odd.resize(m+1);
    for(int i=1; i<=m; i++) {
        even[i].push_back(0);
        odd[i].push_back(0);
    }
    for(int i=1; i<=n; i++)    scanf("%d",&num[i]);
	for(int i=1; i<=n; i++) {
        int x;
    	scanf("%d",&x);
    	if(i&1) {
            odd[x].push_back(i);
            int size=odd[x].size();
            odd[x][size-1]+=odd[x][size-2];
    	}
        else {
            even[x].push_back(i);
            int size=even[x].size();
            even[x][size-1]+=even[x][size-2];
        }
	}
	for(int i=1; i<=m; i++) {
        res=(res+sum(odd[i])+sum(even[i]))%MOD;
	}
	printf("%d",res);
    return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5594129.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-15
下一篇 2022-12-15

发表评论

登录后才能评论

评论列表(0条)

保存