ABC149 Summary

ABC149 Summary(2019-12-29 19:00-20:40)

2019-12-30 xiaoh

A-Strings

题意

给定两个字符串s,t（1<=|s|,|t|<=100），将t和s按顺序接在一起输出（不输出空格）

题解

显然，接在一起都是唬人的QAQ直接输出就行啦！时间复杂度O（1）

Code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int ret=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return w*ret;
}
int main()
{
    string a,b;
    cin>>a>>b;
    cout<<b<<a<<endl; 
    return 0;
}

B-Greedy Takahashi

题意

有两个人Takahashi和Aoki，各有a,b(1<=a,b<=1e12)块饼干。进行以下n(1<=a,b<=1e12)轮操作：若Takahashi有至少一块饼干，则他吃掉一块饼干；否则若Aoki有至少一块饼干，则他吃掉一块饼干。求n轮操作后两人各自的饼干数

题解

直接暴力地数，按题意模拟即可。但是要注意long long。时间复杂度O(1)

Code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int ret=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return w*ret;
}
long long n,a,b;
int main()
{
    cin>>a>>b>>n;
    if(a>=n) cout<<a-n<<" "<<b<<endl;
    else cout<<0<<" "<<max((long long)0,b-n+a)<<endl;
    return 0;
}

C-Next Prime

题意

给定一个整数n（2<=n<=1e5），求不小于n的最小质数。

题解

我敢打赌有人写了埃氏筛很显然，根据素数密度，我们可知从n开始暴力一个一个O(√n)的检验就好啦！由于素数密度约为n/In(n)，所以复杂度约为O（n×√n/In(n)）,大概是3e6的级别，时间绰绰有余

Code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int ret=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return w*ret;
}
int n;
bool check(int x)
{
    for(int i=2;i*i<=x;i++)
    if(x%i==0) return 0;
    return 1;
}
int main()
{
    cin>>n;
    for(;;n++)
    if(check(n))
    {
        cout<<n<<endl;
        return 0;
    }
    return 0;
}

D-Prediction and restriction

题意

有n盘剪刀石头布（2<=n<=1e5），你现在知道了对手的出拳顺序，而且你知道你出石头时赢对方（即此时对手出了剪刀，下同）获得R分，出剪刀赢S分，出布赢P分(1<=r,s,p<=1e4)。但是有一个限制条件，就是对于所有的i∈[1,n-k]，你第i局出的手势不能和第i+k局的相同（1<=k<=n-1）。求你的最大得分。

题解

这道题很容易飞到DP里去。实际上呢，我们可以用一个简单的贪心来解决问题：对于一个步骤i，若第i-k步（前提是存在的话）对手出的是与本局出的完全相同，那么随便出一个（可以理解为根据后面的需求出，若目前无法出布，而第i+k步出石头能赢对方，那么本步就出剪刀，其余同理，证明很显然，就不费笔墨证了）。否则出能赢对手的手势就好啦。其实严格证明非常非常难，但是建议证明还是很简单的。若第t步、第t+k步、第t+2k步，……，第t+xk步对手出的完全相同，且第t步与第t-k步出的不同（前提是t-k存在），显然，获得的分只能全取奇数项或全取偶数项，那么对于所有的x属于偶数时，不管全取奇数或偶数，答案都相同。若x为奇数，则全取奇数项会比全取偶数项答案大。所以全取奇数项的解不会比全取偶数项更劣。按照顺序遍历，对于这种情况我们一定会都取奇数项，即贪心正确而若没有上述的情况，则贪心依旧成立。所以综上所述，贪心正确！时间复杂度O（n）

Code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int ret=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return w*ret;
}
int n,k;
int r,s,p;
char ch[100010];
int a[100010];
int f[100010];
int ans=0;
inline int cal(int i)
{
    if(a[i]==1) return r;
    else if(a[i]==2) return s;
    else return p;
}
int main()
{
    scanf("%d %d",&n,&k);
    scanf("%d%d%d",&r,&s,&p);
    scanf("%s",ch+1);
    for(int i=1;i<=n;i++)
    if(ch[i]=='r') a[i]=3;
    else if(ch[i]=='s') a[i]=1;
    else a[i]=2;
    for(int i=1;i<=n;i++)
    if(i-k<=0) f[i]=a[i],ans+=cal(i);
    else if(f[i-k]==a[i]) f[i]=0;
    else f[i]=a[i],ans+=cal(i);
    cout<<ans<<endl;
    return 0;
}

E-handshake

题意

给定一个有n个数的序列A（1<=n<=1e5,1<=ai<=1e5），选取两个坐标p和q，那么有序数对(p,q)共有n^2个。不妨令f(p,q)=a[p]+a[q]，那么f(p,q)共有n^2个。求其中最大的m个的和（1<=m<=n^2）

题解

本题与你谷的一道毒瘤P1631 序列合并神似。于是，我在这个错误的算法里整整徘徊了30+min才发现这玩意不能用……好啦，开始正题。首先，我们二分前m大的数中最小的那一个。那么显然对于一个二分值mid，若所有数中若>=mid的数>=m，则mid小了，l=mid，反之亦然。那么就要考虑如何快速地求出这个数量。我们考虑将整个序列排序。那么对于一个a[i]，必存在一个坐标j，使得>=a[j]的所有数加上a[i]都>=mid（因为排过序了嘛），所以考虑使用lower_bound进行计算，就可以二分出这个值，不妨设其为minn。那么有人可能基于要问了：我要这个值有个鬼的用处？实际上，在我们二分的时候，我们就已经想到利用minn求出综合的方法了。首先，记s为a的前缀和。对于每个a[i]，那么一定存在一个坐标j使得a[i]+j及其右边的每个数都大于等于minn，而左边的都小于minn。所以我们只要再跑一遍计算即可。但是这个算法有一个小小的问题，不妨考虑以下4个和：3,2,1,1，m=3。此时，我们的程序会返回3+2+1+1=7，而真实的答案=3+2+1=6。对于这种情况，我们只需要把>=minn的数再算一遍，然后由于多出来的数一定都是minn，再减去就好啦！

Code

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
    long long ret=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return w*ret;
}
inline long long read_l()
{
    long long ret=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return w*ret;
}
long long n;
long long m;
long long a[100010];
long long s[100010];
long long ans=0;
bool check(long long x)
{
    long long tot=0;
    for(long long i=1;i<=n;i++) tot+=lower_bound(a+1,a+n+1,x-a[i])-a-1;
    if(n*n-tot<m) return 1;
    else return 0;
}
int main()
{
    n=read(),m=read_l();
    for(long long i=1;i<=n;i++) a[i]=read_l();
    sort(a+1,a+n+1);
    for(long long i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    long long l=1,r=999999999;
    while(l+1<r)
    {
        long long mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    for(long long i=1;i<=n;i++) 
    {
        long long x=lower_bound(a+1,a+n+1,l-a[i])-a;
        ans+=s[n]-s[x-1];
        ans+=a[i]*(n-x+1);
    }
    long long tot=0;
    for(long long i=1;i<=n;i++) tot+=lower_bound(a+1,a+n+1,l-a[i])-a-1;
    if(n*n-tot>m) ans-=(n*n-tot-m)*l;
    cout<<ans<<endl;
    return 0;
}

F-Surrounded nodes

由于E题卡太久导致无暇写了……希望未来的我能把这里补上吧QAQ

ABC149 Summary

原文：https://www.cnblogs.com/xiaoh105/p/12121668.html