《第十五届中北大学算法与程序设计竞赛（公开赛）》

K：
思路：
最优的操作就是一直操作一个数。
证明：
设最后的结果为
(a[i]+xi)-(a[j]-yj).
= abs(a[i]-a[j])+xi+yj (x+y = m);因为i,j肯定不一样。
那么max(i,j)x+max(i,j)y >= xi+yj.
所以全部分给下标最大的那个更优.
所以只需要去枚举操作哪个数,然后操作这个数为最大时和最小时都和最大值最小值计算下即可。
Code:

LL a[N];
int main()
{
    int n,m;sdd(n,m);
    LL minn = INF,maxx = -INF;
    for(int i=1;i<=n;++i) 
    {
        sld(a[i]);
        maxx = max(maxx,a[i]);
        minn = min(minn,a[i]);
    }
    if(n == 1) printf("0\n");
    else
    {
        LL ans = -INF;
        for(int i=1;i<=n;++i)
        {
            LL ma1 = a[i]+m*i;
            LL tmp = ma1-minn;
            ans = max(ans,tmp);
            LL ma2 = a[i]-m*i;
            tmp = maxx-ma2;
            ans = max(ans,tmp);
        }
        plr(ans);
    }
    system("pause");
    return 0;
}

C：
思路：差分+贪心
以第一个数为基准,让所有数向它靠近.
假设差分数组为b.
那么我们要使数组后面的数都和a[1]一样。
那么就是让b数组都为0(除了b[1]).
那么如何让这个b都为0最优。
我们通过差分这个差分数组的思想。
对于一段区间[L,r]。中间的数都为0.
我们可以让这个区间内的数都+1,那么区间内的差分值都不会变化.
就是b[L]++,b[r+1]--.同理都-1,b[L]--,b[r+1]--.
那么我们可以进行min(abs(b[L]),abs(b[r]))次操作,让区间[L,r]的一个端点变成0.
然后我们继续去找区间。那么很显然这样的区间两个端点是符号相反的。
然后可以思考,当一段区间的一端归0后,另一端也相对的减去了min(abs(b[L]),abs(b[r])).
然后我们继续去找符号相反的。最后其实就是让所有的负值和正值中较少的全归0,然后剩下的都对自己进行+1,-1操作来归0.
那么我们只需要去统计差分数组的正数个数和负数个数即可(除b[1]外).
那么显然答案就是min(num1,num2)+abs(num1-num2)
不难发现这个值其实就是max(num1,num2)

更直观地感受
假设差分数组b为
1 2 -3 4 5 -6 1.
第一次[2,3]进行min(abs(2),abs(3)) = 2次-1操作变成
1 0 -1 4 5 -6 1.
第二次[3,4]进行min(abs(-1),abs(4)) = 1次+1操作变成
1 0 0 3 5 -6 1.
第三次[5,6]进行min(abs(5),abs(-6)) = 5次-1操作变成
1 0 0 3 0 -1 1.
第四次[6,7]进行min(abs(-1),abs(1)) = 1次+1操作变成
1 0 0 3 0 0 0.
第五次[4,4]进行3次-1变成
1 0 0 0 0 0 0.
over！(注意会爆int)
Code:

int a[N];
int main()
{
    int n;sd(n);
    LL ma1 = 0,ma2 = 0;
    for(int i=1;i<=n;++i) 
    {
        sd(a[i]);
        if(i == 1) continue;
        LL tmp = a[i]-a[i-1];
        if(tmp > 0) ma1 += tmp;
        else ma2 -= tmp;//减负数其实就是加 
    }
    LL ans = max(ma1,ma2);
    plr(ans);
    system("pause");
    return 0;
}

F：
思路：
将在线查询改为离线查询.
用set来维护离散化后的元素和元素的值+1.
一开始我们让所有元素都在set中
很显然这个>=的值可以二分找到。
如果第一个数为a[1],那么a[1]+1就是他的大于1.
第二个数为a[2].那么如果a[1]+1 != a[2].
那么这时候要的值就是a[2],如果a[1]+1 > a[2].
这时的值就是a[2]+1.
以此类推,当a[2]+1 = a[3]时就是a[3]+1.
所以将所有的值和他们的+1都放入集合。
这个大于等于的值具有传递性。所以可以二分找。
因为我们维护的集合是不在原来的集合内的,所以我们插入这个数就要从这个集合中删去。
删去这个数就要把它插入到集合中
Code:
struct Node{int id,x;}p[N];
int main()
{
    int n;sd(n);
    set<int> S;
    for(int i=1;i<=n;++i)
    {
        sdd(p[i].id,p[i].x);
        S.insert(p[i].x);
        S.insert(p[i].x+1);
    }
    for(int i=1;i<=n;++i)
    {
        if(p[i].id == 1) S.erase(p[i].x);
        if(p[i].id == 2) S.insert(p[i].x);
        if(p[i].id == 3)
        {
            auto v = S.lower_bound(p[i].x);
            pr(*v);
        }
    }
    //system("pause");
    return 0;
}
H:记忆化搜索
思路：
基于底层开始统计的记忆化搜索
Code:
LL dp[55][1005][10][10];//dp[n][sum][i][j]表示n位数时,和为sum且前两位为i,j时的个数
int n,sum,x;
LL dfs(int pos,int num,int pre1,int pre2)
{
    if(pos == n)
    {
        if(num == sum) return 1;
        return 0;
    }
    if(num > sum) return 0;//剪枝
    if(dp[pos][num][pre1][pre2] != -1) return dp[pos][num][pre1][pre2];
    LL ans = 0;
    for(int i=0;i<10;++i)
    {
        if((pos < 2) || (pre2*100+pre1*10+i)%x == 0) ans = (ans+dfs(pos+1,num+i,i,pre1))%Mod;
    }
    return dp[pos][num][pre1][pre2] = ans;
}
int main()
{
    metf(dp);
    sddd(n,sum,x);
    LL ans = dfs(0,0,0,0);
    plr(ans);
    //system("pause");
    return 0;
}

I：二分图最大权匹配
因为x+y = 奇
那么只有奇和偶的配的才能满足。
所以可以看成奇和偶的二分图。
然后就是二分图最大权匹配的模板了。
注意点：
1.保证去配对的一方都是最小的那组数。这样才能走出循环。
2.这里的单个情况不需要算入结果。
3.因为任意奇偶之间都能配对,所以少的那一方肯定全都配对完,所以总对数就是min(cnt1,cnt2).
Code:

《第十五届中北大学算法与程序设计竞赛（公开赛）》

全站热榜