AtCoder Beginner Contest 308

简单场。

A. New Scheme

题意

给出八个整数，求是否满足如下条件：

• 都在 $[100,675]$ 的范围内；
• 都是 $25$ 的倍数；
• 单调不下降。

代码

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")
int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int a[10];
int main(){
    for(int i=1;i<=8;i++)a[i]=read();
    for(int i=1;i<=8;i++){
        if(a[i]<100 || a[i]>675){
            NO;return 0;
        }
        if(a[i]%25!=0){
            NO;return 0;
        }
        if(i!=1 && a[i]<a[i-1]){
            NO;return 0;
        }
    }
    YES;
    return 0;
}

B. Default Price

题意

有 $n$ 个商品，用字符串表示。现在有 $m$ 个字符串，为对应商品的价格。对于在 $m$ 个字符串中没有出现的商品，价格为固定 $P_0$ 元。

解法

用 std::map 储存即可。

代码

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

map<string,int> mp;
vector<string> v;
vector<string> v2;

int main(){
    int n=read(),m=read();
    int ans = 0;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        v.push_back(s);
    }
    for(int i=0;i<m;i++){
        string s;
        cin>>s;
        v2.push_back(s);
    }
    int p0=read();
    for(int i=0;i<m;i++){
        mp[v2[i]]=read();
    }

    for(auto s:v){
        if(mp.count(s)){
            ans += mp[s];
        }else{
            ans += p0;
        }
    }

    printf("%d\n",ans);
    return 0;
}

C. Standings

题意

给定 $n$ 个整数对 $(A_i,B_i)$。以 $\dfrac{A_i}{A_i+B_i}$ 作为关键字排序，如果相同，先出现的应该排在前面。

$0\le A_i,B_i \le 10^9$。

解法

对于两个分数比大小，不用把它们变成浮点数比大小，会有误差。直接把除法转化为乘法作比较。

即

$$\dfrac a b < \dfrac c d \iff ad < bc$$

自定义排序 cmp 函数，然后用 std::sort 即可。注意开 long long。

代码

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

struct Node{
    ll p,q;
    int ind;
};

bool cmp(Node a,Node b){
    // p/q > b.p/b.q
    if(a.p*b.q>a.q*b.p){
        return 1;
    }
    if(a.p*b.q<a.q*b.p){
        return 0;
    }
    return a.ind<b.ind;
}

const int N = 2e5+5;

Node a[N];

int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i].p=read();
        a[i].q=a[i].p+read();
        a[i].ind=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        printf("%d ",a[i].ind);
    }
    return 0;
}

D. Snuke Maze

题意

给定一个 $H \times W$ 的字符矩阵。

求：是否存在一条从 $(1,1)$ 到 $(H,W)$ 的路径，使得路径上经过的元素拼接成的字符串是按照 snuke 的顺序出现的（即字符串第一个字符是 s，对于任意一个 s，其后一个字符是 n，以此类推）。

解法

注意到一个点经过两次是没有意义的。因为状态的转移只于当前格子的字符有关系。

直接进行 BFS 即可。复杂度 $O(HW)$。

代码

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

char a[505][505];
bool vis[505][505];

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};


bool valid(char a,char b){
    swap(a,b);
    if(a=='s'&&b=='e')return 1;
    if(a=='n'&&b=='s')return 1;
    if(a=='u'&&b=='n')return 1;
    if(a=='k'&&b=='u')return 1;
    if(a=='e'&&b=='k')return 1;
    return 0;
}

int main(){
    int h=read(),w=read();
    for(int i=1;i<=h;i++){
        scanf("%s",a[i]+1);
    }

    if(a[1][1]!='s'){
        puts("No");return 0;
    }

    queue<pii> q;
    q.push({1,1});

    while(q.size()){
        auto x = q.front();q.pop();
        int i=x.first,j=x.second;

        if(i==h && j==w){
            puts("Yes");
            return 0;
        }
        for(int k=0;k<4;k++){
            int ii = i+dx[k];
            int jj = j+dy[k];

            if(!vis[ii][jj] && valid(a[i][j],a[ii][jj])){
                vis[ii][jj]=1;
                q.push({ii,jj});
            }
        }

    }

    puts("No");
    return 0;
}

E. MEX

题意

给定长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n (a_i=0,1,2)$ 以及长度为 $n$ 的字符串 $S$ （$S$ 只包含 $\texttt{M,E,X}$）。

对于所有满足 $S_iS_jS_k=\texttt{MEX}$ 的三元组 $(i,j,k)$ ，输出 $\sum{\operatorname{mex}(a_i,a_j,a_k)}$。式中 $\operatorname{mex}(a_i,a_j,a_k)$ 指不等于 $a_i,a_j,a_k$ 的最小自然数。

解法

乍一看可能有点复杂。我们先考虑一个简单的问题。给定一个字符串，求出满足 $S_iS_jS_k=\texttt{MEX}$ 的三元组 $(i,j,k)$ 的三元组个数。这个问题可以用两次后缀和在 $O(n)$ 时间复杂度解决。
具体来说，对于每一个 $\texttt M$，它的方案数就是它后面所有的 $\texttt E$ 的方案数总和。对于每一个 $\texttt E$ 它的方案数就是它后面 $\texttt X$ 的个数。因此，我们只需要 $\texttt X$ 出现次数存一个后缀和，然后在处理一个 $\texttt E$ 的方案数的后缀和就可以得到这个问题的答案。

注意到序列的取值只有 $0,1,2$，我们考虑把问题转化为上面的问题。这个问题难统计的原因就是 $(a_i,a_j,a_k)$ 是不确定的。然而 $(a_i,a_j,a_k)$ 只有 $3^3=27$ 种可能性，我们可以直接枚举所有可能的 $(a_i,a_j,a_k)$ 的取值，对每个取值都创建一个新的字符串（是原串的一个子串），在子串中求出满足条件的三元组个数然后再乘上它们的 $\text{mex}$。

注意开 long long。
复杂度 $O(27n)$。

代码

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
int n;
int a[N];
char s[N];

int mex(int a,int b,int c){
    if(a!=0 && b!=0 && c!=0)return 0;
    if(a!=1 && b!=1 && c!=1)return 1;
    if(a!=2 && b!=2 && c!=2)return 2;
    return 3;
}


ll back3[N]; // 3 出现次数的后缀和
ll back2[N]; // 2 的选择 3 方案数的后缀和
ll calc(const vector<int>& v){
    memset(back3,0,sizeof(back3));
    memset(back2,0,sizeof(back2));

    int len = v.size();
    for(int i=len-1;i>=0;i--){
        back3[i]=back3[i+1];
        if(v[i]==3)back3[i]++;
    }

    for(int i=len-1;i>=0;i--){
        back2[i]=back2[i+1];
        if(v[i]==2)back2[i]+=back3[i];
    }

    ll res = 0;
    for(int i=0;i<len;i++){
        if(v[i]==1)res += back2[i];
    }
    return res;
}

int main(){
    n=read();
    for(int i=0;i<n;i++){
        a[i]=read();
    }
    scanf("%s",s);
    
    ll ans = 0;

    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    for(int k=0;k<3;k++){
        vector<int> v; // 新的序列
        for(int l=0;l<n;l++){
            if(s[l]=='M' && a[l]==i)v.push_back(1);
            if(s[l]=='E' && a[l]==j)v.push_back(2);
            if(s[l]=='X' && a[l]==k)v.push_back(3);
        }
        ans += calc(v)*mex(i,j,k);
    }

    printf("%lld\n",ans);
    return 0;
}

F. Vouchers

题意

有 $n$ 个商品。每个商品价值为 $P_i$。
有 $m$ 张优惠券，每张优惠券由一个二元组 $(L_i,D_i)$ 确定，代表只有价格大于等于 $L_i$ 的商品才能使用，可以折扣 $D_i$ 元。

每个商品最多使用一张优惠券，求最小花费。

解法

简单贪心。从商品价格从低到高来买，每个商品用当前可用的折扣最多的优惠券即可。

用一个优先队列维护当前可用的优惠券。

代码

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

struct Cou{
    int l,d;
    bool operator<(const Cou& x)const{
        return d<x.d;
    }
};

const int N = 2e5+5;
int a[N];
Cou c[N];

bool cmp(Cou a,Cou b){
    return a.l<b.l;
}

int main(){
    int n=read(),m=read();
    for(int i=0;i<n;i++)a[i]=read();
    for(int i=0;i<m;i++)c[i].l=read();
    for(int i=0;i<m;i++)c[i].d=read();

    sort(a,a+n);
    sort(c,c+m,cmp);

    ll ans = 0;
    priority_queue<Cou> pq;
    int now = 0;

    for(int i=0;i<n;i++){
        while(now<m && c[now].l<=a[i]){
            pq.push(c[now++]);
        }

        ans += a[i];
        if(pq.size()){
            ans-=pq.top().d;
            pq.pop();
        };
    }

    printf("%lld\n",ans);

    return 0;
}

G. Minimum Xor Pair Query

题意

维护一个数据结构。支持：

1. 插入一个数；
2. 删除一个数；
3. 查询所有数的两两异或最小值。

解法

典中典。但是我没做出来。

对于异或有如下性质：
$\forall x<y<z, \min(x\oplus y, y\oplus z)<x \oplus z$。

证明：设 $x$ 和 $z$ 的二进制表示高位的 $k+1$ 之后的位相同，第 $k$ 位上 $x$ 为 $0$，$z$ 为 $1$（因为 $x<z$）。因此有 $x \oplus z \ge 2^k$。
此时，若 $y$ 第 $k$ 位上为 $0$，则 $x\oplus y < 2^k$，反之 $y\oplus z < 2^k$，得证。

因此，答案一定是把这个序列排序后两两相邻异或值的最小一个。我们用一个 std::multiset 来维护所有数，再用一个 std::multiset 来维护这些数两两相邻的异或值即可。（详见代码）

代码

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

multiset<int> num;
multiset<int> ans; // 所有相邻异或值

int main(){
    int q=read();
    while(q--){
        int o=read();
        if(o==1){
            int x=read();
            auto it = num.insert(x);

            if(it != num.begin())ans.insert((*it)^(*prev(it)));
            if(next(it) != num.end())ans.insert((*it)^(*next(it)));

            if(it != num.begin() && next(it) != num.end()){
                ans.erase(ans.find((*prev(it))^(*next(it)))); // 删除原来的那对相邻元素
            }
        }
        else if(o==2){
            int x=read();
            auto it = num.find(x);

            // 删除原来的那个元素的相邻异或值
            if(it != num.begin())ans.erase(ans.find((*it)^(*prev(it))));
            if(next(it) != num.end())ans.erase(ans.find((*it)^(*next(it))));

            it = num.erase(it);
            if(it != num.begin() && it != num.end()){ // 新的出现的相邻异或值
                ans.insert((*it)^(*prev(it)));
            }
        }
        else{
            printf("%d\n",*ans.begin()); // 最小值
        }
    }
    return 0;
}