Codeforces Round #536

Dashboard - Codeforces Round #536 (Div. 2) - Codeforces

A. Lunar New Year and Cross Counting

题意：给一个n*n的网格，网格由'.'和'X'构成，问M(i,j)=M(i−1,j−1)=M(i−1,j+1)=M(i+1,j−1)=M(i+1,j+1)= 'X'.有多少对(i,j) ? (其实就是问网格上有多少个长3宽3的X图形)

知识点：暴力

思路：对于每一个（i，j）暴力判他的本身,左上,左下,右上,右下是不是都是'X'就可以了

代码

#include 
using namespace std;
typedef long long ll;
const ll N = 5e5+5;
const ll mod =998244353;
char mp[505][505];
void solve(){
    ll n;cin>>n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>mp[i][j];
        }
    }ll ans=0;
    for(int i=2;i_;
    while(_--){
        solve();
    }
    return 0;
}

B. Lunar New Year and Food Ordering

题意：有n种物品，每种物品有对应的价值和个数，现在有m个顾客，每个顾客有自己喜爱的物品种类和要点的个数，如果当前这个顾客喜爱的种类的个数不能满足要求，则再还有的物品中拿价值最小的物品来补充，如果仍然没有满足顾客需要的个数，顾客就会离开（不花费钱）。问m个顾客一共要花费多少钱。

知识点：模拟，优先队列

思路：维护一个数组表示每个种类的物品还剩下几个，然后因为有价值最小的补充，可以开一个优先队列来维护还剩下的种类物品的最小价值。

代码

#include 
using namespace std;
typedef long long ll;
const ll N = 1e5+5;
const ll mod =998244353;
struct dd{
    ll a,c,id;
    inline bool operator <(const dd &r)const{
        return c>r.c;//重载小于号使得小的先出队列
    }
}op[N];
ll n,m,t,d;
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>op[i].a,op[i].id=i;
    for(int i=1;i<=n;++i)cin>>op[i].c;
    priority_queue
q;
    for(int i=1;i<=n;++i)q.push(op[i]);//全部插入优先队列中
    for(int i=1;i<=m;++i){
        cin>>t>>d;ll res=0;
        if(op[t].a>=d){//如果当前种类物品比顾客需要的还多
            op[t].a-=d;
            res=d*op[t].c;
            d=0;//说明满足了顾客的需求
        }
        else {//如果当前种类物品比顾客需要的少
            res=op[t].c*op[t].a;
            d-=op[t].a;
            op[t].a=0;
            while(!q.empty()){
                auto g=q.top();q.pop();
                g.a=op[g.id].a;
                if(g.a>=d){
                    res+=d*g.c;
                    g.a-=d;
                    if(g.a)q.push({g.a,g.c,g.id});
                    op[g.id].a=g.a;//更新一下当前种类物品的个数
                    d=0;//说明满足了顾客的需求
                    break;
                }
                else {
                    res+=g.a*g.c;
                    d-=g.a;
                    op[g.id].a=0;//更新一下当前种类物品的个数
                }
            }
        }
        if(d)cout<<0<<'\n';//没有满足顾客需求
        else cout<>_;
    while(_--){
        solve();
    }
    return 0;
}

C. Lunar New Year and Number Division

题意：给你一个正整数n，n一定是一个偶数，现在有一个长度为n个数组，你需要把这个数组分成任意份，每份要保证元素个数大于等于2，设每份的元素总和为，问最小是多少？

知识点：数学，贪心，蒙（不是

思路：可以大概猜到一个分成n/2份，每份是最大和最小，次大和次小...........以此类推，所以只要排序一下，就能解决问题。

证明1：对于最后的答案一定会出现+w(w类似),因为，所以对于一定是大于0的，我们要尽可能减少这样的项出现，所以每一份一定是俩个数。

证明2：假设0

第一个很好证明

移项后变成 a(d-b)+c(b-d)<=0

也就是 (a-c)(d-b)<=0这是显然的

第二个的话

同样的 移项后变成 a(d-c)+b(c-d)<=0

也就是 (a-b)(d-c)<=0这也是显然的

所以我们猜的那个结论是正确的

代码

#include 
using namespace std;
typedef long long ll;
const ll N = 3e5+5;
const ll mod =998244353;
ll n,a[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    sort(a+1,a+n+1);
    ll ans=0;
    for(int i=1;i<=(n/2);++i){
        ans+=(a[i]+a[n-i+1])*(a[i]+a[n-i+1]);//注意理清楚下标
    }
    cout<>_;
    while(_--){
        solve();
    }
    return 0;
}

D. Lunar New Year and a Wander

题意：一个有n个点，m条边（双向）的图，可能有重边和自环，有一个人从点1开始走，这个人开始的时候手上有一个数字，每次走到一个没有走过的点就会把手上的数字+1，并且把这个点的赋值为手上的数字，问最小的d序列？

知识点：BFS

思路：要让序列最小，肯定想每次先走现在可以走的最小的序号，所以我们可以想到BFS来解决，开一个以序号从小到大排序的优先队列就可以了。

代码

#include 
using namespace std;
typedef long long ll;
const ll N = 1e5+5;
const ll mod =998244353;
ll n,m;
vectormp[N],ans;
bool vis[N];
void bfs(){
    priority_queue,greater >q;//从小到大排序的优先队列
    q.push(1);//1先进去
    vis[1]=true;
    while(!q.empty()){
        ll g=q.top();q.pop();
        ans.push_back(g);//记录答案
        for(auto v:mp[g]){
            if(vis[v])continue;
            vis[v]=true;
            q.push(v);//把现在能走的点都扔进队列里
        }
    }
}
void solve(){
    cin>>n>>m;
    for(ll i=1,u,v;i<=m;++i){
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    bfs();
    for(auto w:ans)cout<>_;
    while(_--){
        solve();
    }
    return 0;
}

E. Lunar New Year and Red Envelopes

题意：现在有k个红包，第i个红包只能在到的时间获取的钱，并且在获取后直到时间都不能拿别的红包，现在有一个十分贪婪的人，他会有n个时间去获取红包，只要当前时间能拿红包，他就会拿当前时间能拿红包的最大值，如果有最大值相同的拿d最大的，现在你可以干扰他m个时间，让他不拿，问他拿到的钱数的最小值？

知识点：DP，数据结构

思路：其实很容易想到dp[i][j],表示前i个时间干扰m次他能拿到钱数的最小值，转移的话,

如果第i个时间不能拿任何红包，那么dp[i][j]=max dp[i-1][j]

如果第i个时间能拿红包且我们去干扰，那么dp[i][j]=max dp[i-1][j-1]]

如果第i个时间能拿红包且我们不去干扰，那么dp[ d ][j]=max dp[i-1][j]]+w

所以现在只有一个问题就是如何知道当前时间所能选到的的最大值，并且要知道。

我们可以先按s,t 排序 ，再开一个以w和d排序的优先队列，每次把s<=i的点扔进队列里，把t

代码

#include 
using namespace std;
typedef long long ll;
const ll N = 1e5+5;
const ll mod =998244353;
ll n,m,k;
struct dd{
    ll s,t,d,w;
    inline bool operator <(const dd &r)const{
        if(s==r.s){
            return t>n>>m>>k;
    priority_queueq;
    for(int i=1;i<=k;++i){
        cin>>op[i].s>>op[i].t>>op[i].d>>op[i].w;
    }
    sort(op+1,op+k+1);
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j)dp[i][j]=1e18;//初始化，因为有取min
    }
    ll l=1;
    for(int i=1;i<=n;++i){
        while(l<=k&&op[l].s<=i){
            q.push({op[l].s,op[l].t,op[l].d,op[l].w});//如何当前点的s小于等于i那他一定包含了
            l++;
        }
        ll w=0,d=0;
        while(!q.empty()){
            auto g=q.top();
            if(g.s<=i&&i<=g.t){//如果符合，就是找到了
                w=g.w;d=g.d;
                break;
            }
            else q.pop();//不符合说明i>t了，pop出去
        }
        for(int j=0;j<=m;++j){
            if(w){//有红包
                if(j>=1)dp[i][j]=min(dp[i-1][j-1],dp[i][j]);//不干扰
                dp[d][j]=min(dp[d][j],dp[i-1][j]+w);//干扰
            }
            else {//没红包
                dp[i][j]=min(dp[i-1][j],dp[i][j]);
            }
        }
    }ll ans=1e18;
    for(int i=0;i<=m;++i){
        ans=min(ans,dp[n][i]);//找答案
    }
    cout<>_;
    while(_--){
        solve();
    }
    return 0;
}
/*
*/

F. Lunar New Year and a Recursive Sequence

题意：给你一个长度为k的序列b和p=998244353,定义

现在知道，并且知道

求 等于几？如果不存在输出 -1

知识点：原根，矩阵快速幂，BSGS

思路：先观察定义，发现是个次幂的形式，这样不好找联系，发现p是个大质数，那么我们就可以转化次幂成乘法通过原根。

我们定义原根G

这里我们用到原根的：G的0~p-2次幂可以唯一的表示1~p-1（其实不是很严谨，但这里可以这么说

也就是我们可以转化定义为

再化一下

也就是我们可以通过矩阵快速幂来转移了，构造矩阵

因为，所以, ()

所以,(表示矩阵快速幂运算完后的矩阵第i行第j列的元素)

再带回去，,也就是

这个怎么求的值呢，我们可以通过BSGS算出，就求出来了，

最后答案.

那G又是多少呢，如果学过一点点NTT，我们可以知道998244353的原根是3，不知道也可以通过求原根的方法算出来。

代码

#include 
using namespace std;
typedef long long ll;
const ll N = 1e5+5;
const ll mod =998244352;
const ll Mod = 998244353;
const int maxl=105;
struct Matrix {
    ll a[maxl][maxl];
    int n,m;
    inline Matrix(int n,int m) : n(n) , m(m) {
        for(int i=0;in,this->m),a=*this;
        ans.init();
        while(b){
            if(b&1)ans=ans*a;
            a=a*a;
            b>>=1;
        }
        return ans;
    }
};
ll ksm(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
ll BSGS(ll a,ll b,ll p){//求a^x=b %p的最小的x
    a%=p;b%=p;
    if(!a){
        if(!b)return 1;
        else return -1;
    }
    if(b==1)return 0;
    ll n=ceil(sqrt(p)),res=b;
    mapmp;
    for(ll i=0;i>k;
    for(int i=1;i<=k;++i)cin>>b[i];
    cin>>n>>m;
    Matrix now(k,k);
    for(int i=0;i_;
    while(_--){
        solve();
    }
    return 0;
}
/*
*/