题解：P6979 [NEERC2015] Generators

Anins · 2024-09-14 09:23:33 · 题解

[NEERC2015] Generators

题意

有 n 个序列，对于每个序列给定 x,a,b,c，并按照 x=(ax+b) \bmod c 进行扩展，每个序列取一个数进行累加，输出对 k 取模不为 0 的最大累加和以及每个序列中取出的数的下标，无解输出 -1。

思路

1. 显然 ax+b 是单调不减的，那么对 c 取模就是周期函数，只需求出一个周期即可代表整个序列。

2. 对每个序列记录对 k 取模后值不同的最大值和次大值。

3. 将每个序列最大值累加，若对 k 取模不为 0，那么输出。

4. 否则考虑将一个最大值替换成次大值，要求前后差值最小。

   • 若能替换，则替换后对 k 取模一定不为 0，进行输出。
   • 若不能替换，则意味着无解，输出 -1。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, mod;
ll x, a, b, c, ans;
ll vis[10005]; //存储序列元素下标
struct node {
    ll index, value; //下标和值 
}q[10005][2]; //0为最大值，1为次大值 
void Make_serial() {
    memset(vis, 0, sizeof(vis));
    for(int i=1; !vis[x]; i++) {
        vis[x]=i;
        x=(a*x+b)%c;
    }
}
void Get_max(ll i) {
    q[i][0].index=q[i][1].index=q[i][0].value=q[i][1].value=-1;
    for(int j=c-1; j>=0; j--) {
        if(!vis[j]) continue;
        if(j>=q[i][0].value) { //可以更新最大值 
            if(j%mod!=q[i][0].value%mod) q[i][1]=q[i][0]; //尝试用之前最大值替换次大值 
            q[i][0].value=j, q[i][0].index=vis[j];
        } else if(j>q[i][1].value&&j%mod!=q[i][0].value%mod) { //可以更新次大值 
            q[i][1].value=j, q[i][1].index=vis[j];
        }
        if(q[i][0].value!=-1&&q[i][1].value!=-1) break; //最大值和次大值都有了，结束 
    }
}
void Get_ans() {
    for(int i=1; i<=n; i++) ans+=q[i][0].value; //求最大值累加和 
    if(ans%mod) { //取模不为0，输出 
        cout << ans << "\n";
        for(int i=1; i<=n; i++) cout << q[i][0].index-1 << " ";
    } else {
        ll idx=0; q[0][0].value=0x7f7f7f7f7f, q[0][1].value=0;
        for(int i=1; i<=n; i++) { //找到替换后差值最小的序列编号
            if(q[i][1].value==-1) continue;
            if(q[i][0].value-q[i][1].value<q[idx][0].value-q[idx][1].value) idx=i;
        }
        if(idx==0) { //不能替换
            cout << -1;
            return;
        }
        ans=ans-q[idx][0].value+q[idx][1].value; //更新替换后的答案 
        cout << ans << "\n";
        q[idx][0]=q[idx][1]; //更新替换后的编号 
        for(int i=1; i<=n; i++) cout << q[i][0].index-1 << " ";
    }
} 
int main(){
    cin >> n >> mod;
    for(int i=1; i<=n; i++) {
        cin >> x >> a >> b >> c;
        Make_serial();
        Get_max(i);
    }
    Get_ans();
    return 0;
}