官方题解
Educational Codeforces Round 123 Editorial - Codeforces

菜鸟的赛后补题
C 感觉像贪心？
D 也算贪心吧？ 可惜我的想法假了

题意

给我们一个f(k) 意思是， 在ar 序列中，选择 k 个不同的点 ，增加x
注意，一定要选择k个，并且每一个点只能加一次，不能说一个点直接加上 k*x
完成增加后， 求 最大连续字列和

题目要求， 对于k=0~n , 求出对应的n+1 个最大子列和

思路

结果一定是在最大子列和的基础上，最多增加 k 个 x

求出最大子列和，以及对应的长度
然后结果就是， sum + min(l,k) * x
比如说，一开始k 比较小，就最多,在最大和的基础上增加kx
如果到了后面，k 比较大， 大于最大和的长度，那么就在最大和的基础上 加上 lx

#include<bits/stdc++.h>
#define endl "\n"
#define B 0x3f3f3f3f
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long int ll;
typedef pair<int,int> PII;

const int N=1e4+10;

ll ar[N],s[N],sum[N];//三个数组，读入数据，最大子列和，前缀和
//解释一下 s[i] = a , 意味着，长度为i 的最大连续子列和为 a 

ll n,t,x;

void solve()
{
//读入数据
    scanf("%lld%lld",&n,&x);
    For(i,1,n)
    {
        scanf("%lld",ar+i);
        s[i]=-B; //因为要保存最大子列和，那么初始化为 负无穷
        sum[i]=sum[i-1]+ar[i];//前缀和
    }
    s[0]=0;//最小的值可以取0

    ll ans=-B;

    // 下面是求 长度为 1~n 的最大子列和

    for (int len=1;len<=n;len++)//当长度为 len 
    {
        ans=-B;
        for (int i=1;i+len-1<=n;i++)// 利用前缀和
        {
            int j=i+len-1;
            // 从 i~j 的和是 sum[j]-sum[i-1]  
            // 要记得减 1
            ans=max(ans,sum[j]-sum[i-1]);
        }
        s[len]=max(s[len],ans);//保存长度len 的最大子列和
    }

    //这里是不需要前缀和的做法，不愧是官方题解
    /*For(i,1,n)
    {
        ll b=0;
        For(j,i,n)
        {
            b+=ar[j];
            s[j-i+1]=max(s[j-i+1],b);//直接不断计算  j-i+1 的长度的最大子列和
        }
    }*/

    For(k,0,n)// 注意k的范围 0~n
    {
        ll b=0;
        For(i,1,n)
        {
            b=max(b,s[i]+min(i,k)*x);
            // i 是最大子列和的长度， k 是增加点数的个数 
            // 两者取最小值
        }
        printf("%lld ",b);
    }
    printf("\n");
}

int main()
{
    scanf("%lld",&t);
    while(t--)solve();
    return 0;
}

D
题意
涂颜色问题
一个ｎ＊ｍ　的地图上
一开始，每个格子都是白色
后来进行　ｑ　次粉刷
每次粉刷的颜色一定不是白色，并且颜色种类有　ｋ　种

每一次粉刷时，　给我们ｘ，ｙ
表示第ｘ行　全部，第ｙ列　全部进行粉刷，并且会将之前的颜色覆盖（重点）

问　完成所有粉刷后，地图上的颜色一共有多少种可能

很明显，２ｅ５的数据范围，直接模拟是不可能的，因为这样需要遍历地图　ｑ＊（ｎ＋ｍ）次

思路
先对颜色进行分析，由于一开始全部是白色
每一个格子，如果被粉刷了，就有　ｋ　种可能
如果没有被粉刷，那么就一定是白色，只有一种可能，对最后的答案，可能出现的颜色情况没有影响

因此，我们关注　那ｑ次粉刷即可

然后，由于粉刷是会进行覆盖的，前面先刷的颜色，直接被覆盖，那我们就从　后面　开始粉刷
那样的话，如果这个点已经被粉刷，就不能改变，没有被粉刷，才可以进行粉刷
这样　不会出现那种，对着一个点死命粉刷的情况（但是好像问题不大？）

因此，我们使用　集合ｓｅｔ进行处理

进行逆序地查看粉刷的信息

一次直接粉刷一行，一列
那么用两个集合，分别记录行列的粉刷情况
ｓｅｔ＜ｌｌ＞　ｌ．ｒ

对于（可能）要进行粉刷的ｘ，ｙ
先看，ｘ是否已经在集合ｌ中，意味着，已经被粉刷啦，不要再管他
因为正序的时候进行覆盖，那么逆序的时候，相当于先粉刷的就不能被修改

同时，也要看ｙ　是否在集合　ｒ　中，如果ｙ已经在里面了，那么这一列已经有了颜色，是不能被更改的

我们已经考虑了涂颜色的情况
接下来，考虑计算种类的情况

什么时候一次粉刷算是有效的呢？
当且仅当，这次粉刷的ｘ，ｙ　至少一个进行了粉刷
说人话，ｘ，ｙ里面，至少有一个，原来是不在集合ｌ，ｒ里面的
那样的话，就可以将ｘ，ｙ加入集合中，
而我们逆序地进行粉刷，ｘ，ｙ是不会被修改的
因此，就可以使得总数　*　ｋ

当ｌ的数量为　ｎ，　或者　ｒ的数量为ｍ时
要直接退出
因为这时候，地图的颜色已经被确定了
（这里就是我的做法错误的地方）

比如说一个地图

A 表示没有颜色，也就是白色
1 A A
1
2
3
观察发现，此时已经将1，2，3都已经覆盖，也就是覆盖了整张地图
不论后面怎么进行修改，都不会改变最多的情况了
比如说，给 (1,2)涂颜色B，变成下面的样子，但是，总体的颜色还是只有三个地方，2，3，B
与之前的 1，2，3 (A是白色，没有影响)没有差别

B B B
B
2
3

因此，到此break退出循环，输出答案即可

#include<bits/stdc++.h>
#define endl "\n"
#define B 0x3f3f3f3f
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long int ll;
typedef pair<int,int> PII;

const int N=2e5+10;
ll p=998244353;

ll n,m,t,q,k,a,b;
ll ans;
int x[N],y[N];

void solve()
{
    set<ll> l,r;
    cin>>n>>m>>k>>q;
    bool f;
    ans=1;

    For(i,1,q)
    {
        cin>>a>>b;
        x[i]=a;y[i]=b;
    }
    //注意for 循环是逆序的
    for (int i=q;i>=1;i--)
    {
        f=false;
        if (!l.count(x[i])) //如果x可以进行涂色
        {
            f=true;

            l.insert(x[i]);
        }
        if (!r.count(y[i]) )//如果y可以进行涂色
        {
            f=true;

            r.insert(y[i]);
        }
        if (f)//如果f=true
        // 说明进行了成功的涂色，使得颜色的总数可以增加
        {
            ans*=k;ans%=p;
        }
        if (l.size()==n || r.size()==m)//退出循环
        {
            break;
        }
    }


    //cout<<ar.size()<<endl;

    cout<<ans<<endl;
    return ;
}


int main()
{
    cin>>t;
    while(t--)solve();
    return 0;
}