2020牛客暑期多校训练营(第八场)题解I、K、G

发布于 2020-08-03  0 次阅读


I. Interesting Computer Game

思路:

将每次输入的a和b当做点,将其连成一条边,很明显的对于形成的连通块来说,如果无环就只能取到当前连通块的顶点减一的点,如果连通块内存在至少一个环,即可将该连通块取完,所以我们只需要判断连通块有无环
同时我们注意到数据的范围为1<=ai<=109 1<=bi<=109
所以要采取离散化的方法将数据处理一下,然后对于连通块采取并查集的方式进行维护

AC Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5 +9;
// #define TDS_ACM_LOCAL
int n, vis[N<<1], ls[N<<1], fa[N<<1];
int x, y, len, cnt, ans, idx;
pair<int,int>p[N];

int find(int x){                //查找并查集的祖先
    if(x==fa[x])    return x;
    return fa[x]=find(fa[x]);
}

void solve(){
    cin>>n;
    len=0;
    for(int i=1; i<=n; i++){
        cin>>p[i].first>>p[i].second;
        ls[++len]=p[i].first, ls[++len]=p[i].second;    //ls离散化数组
    }
    sort(ls+1, ls+1+len);                               //排序
    cnt=unique(ls+1, ls+1+len)-ls-1;                    //去重并且求得不同元素的个数
    for(int i=1; i<=cnt; i++) fa[i]=i, vis[i]=0;
    for(int i=1; i<=n; i++){                            
        p[i].first=lower_bound(ls+1, ls+1+cnt, p[i].first)-ls;      //更新原数组的元素
        p[i].second=lower_bound(ls+1, ls+1+cnt, p[i].second)-ls;
        x=find(p[i].first), y=find(p[i].second);                    //找到相应的祖先
        if(x!=y){
            fa[y]=x;
            if(vis[x] || vis[y])    vis[x]=1, vis[y]=0;             //当有环的连通块遇到其他的连通块时,将祖先标记为1
        }
        else    vis[x]=1;                                           //相同祖先结点即为在一个连通块,即为行成环
    }
    ans=cnt;    //ans先取最大(即为a和b中不同元素的个数)
    for(int i=1; i<=cnt; i++) if(fa[i]==i && !vis[i]) ans--;        //如果为祖先但是为0(即为无环),ans--
    cout<<"Case #"<<++idx<<": "<<ans<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

K. Kabaleo Lite(贪心)

题目大意:

有n道菜,没道菜对应利润为a,数量为b,每次上菜必须从第一道菜开始(所以最大客人就是该值)
在最大顾客的情况下可以赚的最多的钱为?

思路:

用前缀和维护上菜可以赚的利润
对于每道菜记录1 − i 的菜中数量最少的
可以用结构体存后排序,也可以直接用优先队列
按照利润非递增排序,对于每道菜,若其位置在上一道菜右边则不行(因为上道菜已经将可以上的上完了,也就是无法连续到此时的位置),若其菜的数量少于上一道菜则不行(因为上一道菜已经上了cnt次了,此时的菜如果在左边则上完了,在右边直接达不到)
最后注意一下,对于最终的答案可能爆long long
n ( 1 ≤ n ≤ 105 ) , ai​( − 109 ≤ a i ≤ 10 9 ) ,bi ( 1 ≤ b i ≤ 105 )
所以采取__int128的方式存ans

对于__int128的输入输出(当然这里只用得着输出),cin和cout不行,所以单独写一下

inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}

AC Code:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
#define pll pair<ll,pair<ll,ll> >
#define INF 0x3f3f3f3f
const int N=1e5+9;

inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}

ll n, a, b, c, mb, cnt, pos, sum[N], idx, rs;
__int128 ans;
priority_queue<pll> q;

void solve(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a;
        sum[i]=sum[i-1]+a;
    }
    mb=INF;
    for(int i=1; i<=n; i++){
        cin>>b;
        if(i==1)    rs=b;
        mb=min(b,mb);
        q.push({sum[i],{mb, i}});
    }
    ans=0;
    cnt=0, pos=n+1;
    while(!q.empty()){
        a=q.top().first, b=q.top().second.first, c=q.top().second.second;
        q.pop();
        if(c>=pos || b<=cnt) continue;
        ans+=(__int128)a*(b-cnt);
        cnt=b;
        pos=c;
    }
    printf("Case #%d: %d ", ++idx, rs);
    print(ans);
    cout<<endl;
    return ;
}

int main(){
	// ios::sync_with_stdio(0);
	// cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

G. Game SET

思路:

直接暴力跑O(n^3)也能过,听说官方题解说的是在213
必定有解,所以直接暴力跑吧

AC Code:

#include<cstdio>
#include<iostream>
using namespace std;
// #define TDS_ACM_LOCAL
const int N=300;
int n, idx, flag, cnt;
string a, b, c;
struct node{
    string c[6];
}p[N];
string s[N];

void solve(){   
    cin>>n;
    for(int i=1; i<=n; i++){        //将每个行的字符串拆分并且存入结构体中
        cin>>s[i];
        idx=0;
        p[i].c[1]=p[i].c[2]=p[i].c[3]=p[i].c[4]="";
        for(int j=0; j<s[i].length(); j++){
            if(s[i][j]=='[')    {idx++; continue;}
            else if(s[i][j]==']')   continue;
            p[i].c[idx]+=s[i][j];
        }
    }
    for(int i=1; i<=n-2; i++)      //直接三个for暴力
        for(int j=i+1; j<=n-1; j++)
            for(int k=j+1; k<=n; k++){
                flag=1;
                for(int v=1; v<=4; v++){        //对三行中的括号中的四个字符挨次判断
                    a=p[i].c[v], b=p[j].c[v], c=p[k].c[v];
                    if(a=="*" || b=="*" || c=="*")  continue;       //出现*,可任意选(另外两个一样就三个一样,不一样就三个不一样)
                    else if(a==b && b==c) continue;                 //全一样
                    else if(a!=b && b!=c && a!=c)    continue;      //全不一样
                    else    {flag=0; break;}                        
                }
                if(flag)    {cout<<"Case #"<<++cnt<<": "<<i<<" "<<j<<" "<<k<<endl; return ;}
            }
    cout<<"Case #"<<++cnt<<": -1"<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

平平无奇的在校大学生