285484026

Codeforces Round#536(Div.2)
A. Lunar New Year and Cross Counting题意:计算给定的数据中满足以下图形的X.X...
扫描右侧二维码阅读全文
03
2019/02

Codeforces Round#536(Div.2)

A. Lunar New Year and Cross Counting
题意:
计算给定的数据中满足以下图形的

X.X
.X.
X.X

题解:模拟

#include <bits/stdc++.h>

using namespace std;

int n,sum;
char s[1000][1000];

inline bool check(int x,int y){
    if(s[x][y] == 'X' && s[x-1][y-1] == 'X' && s[x-1][y+1] == 'X' && s[x+1][y-1] == 'X' && s[x+1][y+1] == 'X') return true;
    else return false;
}

int main()
{
    scanf("%d",&n);
    
    for(int i = 1;i <= n;i++)
        scanf("%s",s[i]+1);
    
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            if(check(i,j))
                sum++;
        
    printf("%d\n",sum);
    
    return 0; 
} 

B. Lunar New Year and Food Ordering
题意:
一共有n盘菜,每盘菜的数量为$a_i$,价格为$c_i$,一共有M个客人每个客人会要编号为$t_i$的菜$d_i$盘,如果菜品的盘数不够,他就会在剩下的菜品中选择最便宜的买。如果最后他买到的菜品不够$d_i$盘,那么他就不会给钱。否则的话他会支付相应的金额。
题解:
用set记录菜品的分量和价格,然后排序,额外用个数组记录每样菜品的价格和数量。最后一个一个更新。计算答案。需要注意的是无论如何都要同时更新数组和set

#include <bits/stdc++.h>

const int MAXN = 200000;

using namespace std;

long long n,m;
long long sum,sum1;
long long a[MAXN],c[MAXN];

struct node{
    long long id,w,c;
    
    friend bool operator < (const node &A,const node &B){
        if(A.c == B.c) return A.id < B.id;
        else return A.c < B.c;
    }
};

set<node>S;
queue<node>Q;

inline void init()
{
    scanf("%lld %lld",&n,&m);
    
    for(int i = 1;i <= n;i++)
        scanf("%lld",&a[i]);
    
    for(int i = 1;i <= n;i++)
        scanf("%lld",&c[i]);
    
    for(int i = 1;i <= n;i++)
        S.insert((node){i,a[i],c[i]});

}

int main()
{
    init();
    
    long long t,d;
        
    for(int i = 1;i <= m;i++)
    {
        scanf("%lld %lld",&t,&d);
        sum = 0;
        if(a[t] >= d){
            sum += d*c[t];
            a[t] -= d;
            S.erase(S.find((node){t,0,c[t]}));
            S.insert((node){t,a[t],c[t]});
        }
        else {
            long long tmp = 0; 
            tmp += a[t] * c[t];
            d -= a[t];
            if(a[t]) S.erase(S.find((node){t,0,c[t]}));
            a[t] = 0;
            for(auto it = S.begin();it != S.end();it++){
                if(it->w > d){
                    tmp += d * it->c;
                    int id = it->id,w = it->w,c = it->c;
                    a[it->id] -= d;
                    S.erase(it);
                    S.insert((node){id,w-d,c});
                    it = S.find((node){id,w-d,c});
                    d = 0;
                    break;
                }else{
                    tmp += it->c * it->w;
                    a[it->id] = 0;
                    d -= it->w;
                    Q.push(*it);
                }
            }
            if(d == 0){
                sum += tmp;
            }
            while(!Q.empty()){
                auto it = Q.front();Q.pop();
                S.erase(it);
            }
        }
        printf("%lld\n",sum);
    }
    
    return 0;
}

C. Lunar New Year and Number Division
题意:
将n个数字两两分组,使得最后的分组和的平方最大。
题解:
显然排序以后$$\large \sum_{i=1}^{\frac{n}{2}}(a_i+a_{n-i+1})^{2}$$
这样组合会使得和最小

#include <bits/stdc++.h>

const int MAXN = 300005;

using namespace std;

int n;
long long sum,d[MAXN];

int main()
{    
    scanf("%d",&n);
    
    for(int i = 1;i <= n;i++)
        scanf("%lld",&d[i]);
    
    sort(d+1,d+n+1);
    
    for(int i = 1;i <= n / 2;i++){
        sum += (d[i]+d[n-i+1])*(d[i]+d[n-i+1]);
    }
    
    printf("%lld\n",sum);
    
    return 0;
} 

D. Lunar New Year and a Wander
题意:
有一张N个点M条边的图,如果新到达一个点就将这个点按照访问顺序记录下来,需要求出一个使得记录字典序最小的顺序输出。
题解:
先将点1加入优先队列,将1从优先队列弹出来,然后将1的所有子节点加入优先队列,再弹出一个编号最小的点,将当前点的所有没有访问过的子节点加入优先队列。重复以上过程。

#include <bits/stdc++.h>

const int MAXN = 1000000;

using namespace std;

int n,m;

vector<int>E[MAXN];

priority_queue<int>Q;

bool vis[MAXN],inq[MAXN];

int main()
{
    scanf("%d %d",&n,&m);
    
    int u,v;
    for(int i = 1;i <= m;i++){
        scanf("%d %d",&u,&v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    Q.push(-1);vis[1] = true;
    while(!Q.empty()){
        int x = Q.top();Q.pop();
        x = -x;
        printf("%d ",x);
        for(int i = 0;i < E[x].size();i++){
            int v = E[x][i];
            if(!vis[v]){
                vis[v] = true;
                Q.push(-v);
            }
        }
    }
    
    return 0;
}

E. Lunar New Year and Red Envelopes
题意:
有n天时间,k个红包每个红包打开的时间范围是$s_i$至$t_i$打开这个红包会获得$w_i$个硬币,下次需要到$d_i$天之后才能开红包,Bob在每一天会在所有的红包中选择$w_i$最大的,如果有多个$w_i$最大的红包,就会选择$d_i$最大的打开,如果有多个$d_i$最大的红包那么会随机选择一个打开。而爱丽丝会阻止鲍勃获得金钱于是爱丽丝会选择一些天(小于等于M)使得在选择的那天鲍勃不能打开任何的红包。
题解:
假设我们已经计算出来每天要打开的红包
设dpi代表前i天在被妨碍j次的情况下能获得最小值。状态转移方程为:

\begin{equation} \begin{aligned} dp[d_i+1][j]&=min(dp[d_i+1][j],dp[i][j]+w_i)\\ dp[i+1][j+1]&=min(dp[i+1][j+1],dp[i][j])\\ \end{aligned} \end{equation}

对于求出来每天要打开的红包是哪个我采用三种不用的方法
第一种set
PS:因为set会去重所以我们排序关键词如果只有$w_i$和$d_i$那么我们会有一些红包没了。。。于是我额外加入$i$这个变量来比较使得不会有重复的元素出现。就不用multset。

#include <bits/stdc++.h>

const int MAXN = 100005;

using namespace std;

int n,m,k;
long long dp[MAXN][205],ans;

struct node{
    int w,d,id;
    friend bool operator < (const node &A,const node &B){
        if(A.w == B.w && A.d == B.d) return A.id < B.id;
        if(A.w == B.w) return A.d > B.d;
        return A.w > B.w;
    }
};

pair<int,int>inf[MAXN];

vector<int>L[MAXN],R[MAXN]; 

set<node>S;

int main()
{
    scanf("%d %d %d",&n,&m,&k);
    int s,t,d,w;
    for(int i = 1;i <= k;i++){
        scanf("%d %d %d %d",&s,&t,&d,&w);
        L[s].push_back(i);R[t+1].push_back(i);
        inf[i].first = w;inf[i].second = d;
    } 
    
    memset(dp,63,sizeof(dp));
    for(int i = 0;i <= m;i++)
        dp[1][i] = 0;
    
    for(int i = 1;i <= n + 1;i++)
    {
        for(int j = 0;j < L[i].size();j++)
        {
            int v = L[i][j];
            S.insert((node){inf[v].first,inf[v].second,v});
        }
        for(int j = 0;j < R[i].size();j++){
            int v = R[i][j];
            S.erase(S.find((node){inf[v].first,inf[v].second,v}));
        }
        if(S.size()){
            auto tmp = S.begin();
            d = tmp->d;w = tmp->w;
            for(int j = 0;j < m;j++){
                dp[d+1][j] = min(dp[i][j]+w,dp[d+1][j]);
                dp[i+1][j+1] = min(dp[i][j],dp[i+1][j+1]);
            }
            dp[d+1][m] = min(dp[i][m]+w,dp[d+1][m]);            
        }
        else{
            for(int j = 0;j <= m;j++)
                dp[i+1][j] = min(dp[i+1][j],dp[i][j]);        
        }
    }
    
    ans = LONG_LONG_MAX;
    
    for(int i = 0;i <= m;i++)
        ans = min(ans,dp[n+1][i]);
        
    printf("%lld\n",ans);
    
    return 0;
} 

第二种:线段树
相当于对于区间$s_i$至$t_i$内的数如果小于$pair<w_i,d_i>$那么更新,否则不管。这显然就是一个线段树的基本操作。就是这种线段树有一个基本剪枝就是如果不能更新就返回。

#include <bits/stdc++.h>

const int MAXN = 400005;

#define lson o<<1,L,M
#define rson o<<1|1,M+1,R

using namespace std;

int n,m,k,ql,qr;
long long dp[100005][205],ans;

pair<int,int>P[MAXN],tmp,d[100005];

inline void update(int o,int L,int R){
    if(P[o] >= tmp) return;
    if(ql <= L && R <= qr){
        P[o] = max(P[o],tmp);
        return;
    }
    int M = L + R >> 1;
    if(ql <= M) update(lson);
    if(M < qr) update(rson);
}

inline void T_init(int o,int L,int R)
{
    if(L == R){
        d[L] = P[o];
        if(d[L].second == 0) d[L].second = L;
        return;
    }
    int M = L + R >> 1;
    P[o<<1] = max(P[o<<1],P[o]);P[o<<1|1] = max(P[o<<1|1],P[o]);
    
    T_init(lson);
    T_init(rson);
}

inline void init()
{
    scanf("%d %d %d",&n,&m,&k);
    
    for(int i = 1;i <= k;i++){
        scanf("%d %d %d %d",&ql,&qr,&tmp.second,&tmp.first);
        update(1,1,n);
    }
        
    T_init(1,1,n);
    
}

int main()
{
    init();
    memset(dp,63,sizeof(dp));
    
    for(int i = 0;i <= m;i++) dp[1][i] = 0;
    
    for(int i = 1;i <= n;i++){
        tmp = d[i];
        for(int j = 0;j <= m;j++){
            dp[tmp.second+1][j] = min(dp[tmp.second+1][j],dp[i][j]+tmp.first);
            if(j != m) dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]);
        }
    }
    
    ans = LONG_LONG_MAX;
    
    for(int i = 0;i <= m;i++)
        ans = min(ans,dp[n+1][i]);
    
    printf("%lld\n",ans);
    return 0;
} 

第三种:ST表
相当于对于区间$s_i$至$t_i$内的数如果小于$pair<w_i,d_i>$那么更新,否则不管。第二种方法用的线段树维护的。
但是!!!!著名的大圣年前曾说过

如果题目是静态的(对于任意询问都在每一个修改操作之后),那么大概率存在某种数据结构能替代线段树--大圣

显然本题就是一个静态的而且询问在每一个操作之后。所以在大圣不抛弃不放弃的教导之后,我明白了我们原来的普通的ST表的更新操作
$$Max[j][i] = max(Max[j][i-1],Max[j+(1<<i-1)][i-1])$$
但是对于本题而言反过来也是成立的。
$$Max[j][i-1] = max(Max[j][i-1],Max[j][i])\\Max[j+(1<<i-1)][i-1] = max(Max[j+(1<<i-1)][i-1],Max[j][i])$$
于是只用先把标记打上去最后一次性全部压至叶子节点

#include <bits/stdc++.h>

const int MAXN = 100005,MAXD = 20;

using namespace std;

int n,m,k,d[MAXD+5];
long long dp[MAXN][205],ans;

pair<int,int>P[MAXN][MAXD+5],tmp;

inline void init()
{
    scanf("%d %d %d",&n,&m,&k);
    
    d[0] = 1;
    for(int i = 1;i <= MAXD;i++) d[i] = d[i-1] << 1;
    int s,t;
    for(int i = 1;i <= k;i++)
    {
        scanf("%d %d %d %d",&s,&t,&tmp.second,&tmp.first);
        int pos = 0;
        while(d[pos+1] <= t - s + 1) pos++;
        P[s][pos] = max(P[s][pos],tmp);
        P[t-d[pos]+1][pos] = max(P[t-d[pos]+1][pos],tmp);
    }
    
    for(int i = MAXD;i >= 1;i--)
        for(int j = 1;j + d[i] <= n + 1;j++)
        {
            P[j][i-1] = max(P[j][i-1],P[j][i]);
            P[j+d[i-1]][i-1] = max(P[j+d[i-1]][i-1],P[j][i]);
        }
    
    for(int i = 1;i <= n;i++) 
        if(P[i][0].second == 0)
            P[i][0].second = i;

}

int main()
{
    init();
    memset(dp,63,sizeof(dp));
    for(int i = 0;i <= m;i++) dp[1][i] = 0;
    
    for(int i = 1;i <= n;i++)
    {
        tmp = P[i][0];
        for(int j = 0;j <= m;j++)
        {
            dp[tmp.second+1][j] = min(dp[i][j]+tmp.first,dp[tmp.second+1][j]);
            if(j != m) dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]);
        }
    }
    
    ans = LONG_LONG_MAX;
    for(int i = 0;i <= m;i++)
        ans = min(ans,dp[n+1][i]);
    printf("%lld\n",ans);
}
Last modification:February 15th, 2019 at 02:30 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment