2021.12.13

2021.12.13 2021.12.13 思维构造+小算数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jTJrl643-1639543185683)(C:UsersADguyAppDataRoamingTyporatypora-user-images1639412660425.png)]

题意：

给出一串长度为 n n n 的序列，可以进行总次数不超过 3n 的 *** 作使得序列中的所有数都相等。

每次 *** 作选择三个数 i , j , x i,j,x i,j,x

使得 a i − = x × i , a j + = x × i a_i-=x times i,a_j+=x times i ai​−=x×i,aj​+=x×i

如果不行输出 − 1 -1 −1 ，否则输出 *** 作的数量和具体的方案（不要求最小化 *** 作数量）

心路历程：

阿巴阿巴，首先 *** 作看错了，以为是 a j + = x × j a_j+=x times j aj​+=x×j ，我是fw（）

然后发现每次 *** 作过后，序列的总和不变。也就是说，如果序列的总和一开始就不能整除 n n n 说明一定是非法情况。

然后就是漫长的挂机时间

后来看了题解明白了，因为 i = 1 i=1 i=1 的特殊性，可以很方便的分配数字，所以整个过程分两趟进行

1. 把所有数字都移到 下标为 1 1 1 里面去
2. 均匀分配这些数字，进行 n − 1 n-1 n−1 次 *** 作

假设要把 a i a_i ai​ 里面的数加到 a 1 a_1 a1​ 里面去。如果 i ∣ a i i mid a_i i∣ai​ ，那么就只需要一次 *** 作。否则的话，先利用 a 1 a_1 a1​ 分配给 a i a_i ai​ 一些数，使得 i ∣ a i i mid a_i i∣ai​ ，然后再进行一次 *** 作。

有思考过这样 a 1 a_1 a1​ 会不会产生不够用的情况，实际上是不会的。以 i = 2 i=2 i=2 为例，如果能整除直接加，因为题目规定 a 1 ≥ 1 a_1geq1 a1​≥1，此时 a i ≥ 2 a_igeq2 ai​≥2 ，对于 i = 3 i=3 i=3 的情况也能够应付 ；如果不能整除，那么 a 2 a_2 a2​ 需要加 1 1 1 ，也是够用的，然后就又是上面的情况。这样一直归纳下去可以发现 a 1 a_1 a1​ 的值是必然够用的。

这样最多 2 2 2 次 *** 作就能完成数字向 a 1 a_1 a1​ 的转移，再经过 1 1 1 次 *** 作就能把数字均匀的分配到当前位置上，满足了题意orz。

#include
using namespace std;
#define ll long long
#define MAXN 10005
#define MAXM 200005
typedef pair pii;
#define INF 0x3f3f3f3f
int n;
int a[MAXN];
int sum=0;
struct node
{
    int x,y,val;
};
vector  ans;
void work(int x,int y,int val)
{
    a[x]-=x*val;
    a[y]+=x*val;
    ans.push_back({x,y,val});
}

void solve()
{
    ans.clear();
    sum=0;
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(sum%n!=0)
    {
        cout<<-1<T;
    while(T--)
    {
        solve();
    }

    return 0;
}

---

貌似贪心是歪解

e a s y easy easy 版本是从一个长度为 n n n 的序列 a 1 , a 2 , a 3 , a 4 , . . . , a n a_1,a_2,a_3,a_4,...,a_n a1​,a2​,a3​,a4​,...,an​ 中任选 k k k 个数使得 a b 1 − a b 2 + a b 3 − . . . + ( − 1 ) k − 1 × a b k a_{b_1}-a_{b_2}+a_{b_3}-...+(-1)^{k-1}times a_{b_k} ab1​​−ab2​​+ab3​​−...+(−1)k−1×abk​​ 最大。

呃呃呃，这是 e a s y easy easy 版本，可以用贪心， h a r d hard hard 版本貌似要用 d p dp dp 了。

首先可以想象取的点必然是波峰或者波谷，且波峰是用来加的，波谷是用来减得。因为如果加的数不是波峰，如果后面把这段的波峰加上说明多扣了一段。比如一段上升序列 1 2 3 4 5。如果加了 1 而且也要加 5，说明中间多扣了 2 3 4，而2 3 4 的绝对值是比1大的，说明这样不可取。

波谷也是同理。

然后把这些波峰波谷都push到vector里面。push的时候如果波峰未出现过则波谷也不能push，push完过后若发现最后的元素为波谷则直接忽略它或者 pop_back。

然后就是记录答案了阿巴阿巴，加波峰减波谷加波峰减波谷。

因为在判断波峰波谷的时候a[n+1]忘记清零了，导致莫名其妙多调了半小时，我真是个菜狗

#include 
using namespace std;
#define ll long long
#define MAXN 300005
#define MAXM 200005
typedef pair pii;
#define INF 0x3f3f3f3f
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define per(i, x, y) for (int i = x; i >= y; i--)
ll read()
{
    ll x = 0, f = 1;
    char ch;
    do
    {
        ch = getchar();
        if (ch == '-')
            f = -1;
    } while (ch < '0' || ch > '9');
    do
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    } while (ch >= '0' && ch <= '9');
    return x * f;
}

ll n, q;
ll a[MAXN];

void solve()
{
    n = read(), q = read();
    rep(i, 1, n) a[i] = read();
    vector ans;
    a[n+1]=0;//万恶之源呜呜呜
    rep(i, 1, n)
    {
        if (a[i] > a[i - 1] && a[i] > a[i + 1])
            ans.emplace_back(a[i]);
        else if (a[i] < a[i - 1] && a[i] < a[i + 1] && ans.size() > 0)
            ans.emplace_back(a[i]);
    }
    ll res = 0;
    if (ans.size() % 2 == 1)
    {
        for (int i = 0; i < ans.size(); i++)
        {
            if (i & 1)
                res -= ans[i];
            else
                res += ans[i];
        }
    }

    else if (ans.size() % 2 == 0&&ans.size()>0)
    {
        for (int i = 0; i < ans.size() - 1; i++)
        {
            if (i & 1)
                res = ans[i];
            else
                res += ans[i];
        }
    }
    cout << res << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    T = read();
    while (T--)
    {
        solve();
    }

    return 0;
}

阿巴阿巴，我觉得这样挺好的，每天互相发些题目，一是可以交流思路，二是可以相互监督。

os::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
T = read();
while (T–)
{
solve();
}

return 0;

}

阿巴阿巴，我觉得这样挺好的，每天互相发些题目，一是可以交流思路，二是可以相互监督。

睡觉去了，QAQ。