C. 智乃的Notepad(Easy version)

题目简介：

给定一组英文单词的集合，求至少进行多少次操作，可以使所有单词至少出现过一次。输出一个字母或删除一个字母均视为一次操作

思路：

拥有公共前缀较长的两个字母应当相邻输出，即将字母按字典序排列，按序操作，由于题目允许操作结束后保留一个单词，所以应当最后输入最长的单词

代码如下

#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,m,l,r,max_len,ans;
string s[N];
int check(string s1,string s2)
{
    int i;
    for(i=0;i<s1.size();i++)
        if(s1[i]!=s2[i]) return i;
    return i;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        max_len=max(max_len,(int)s[i].size());
    }
    s[0]="";s[n+1]="";
    cin>>l>>r;
    sort(s+1,s+n+1);
    for(int i=0;i<=n;i++)
    {
        int t=check(s[i],s[i+1]);
        ans+=((int)s[i].size()-t);
        ans+=((int)s[i+1].size()-t);
    }
    cout<<ans-max_len;
    return 0;
}

E. 智乃的小球

题目简介：

个小球可以看成质量相同的质点在数轴上运动，速度为 或者 ，符号代表方向，当两球相向而行发生碰撞时发生完全弹性碰撞，即速度交换，求是否存在第 次碰撞。若存在，第一行输出 第二行输出碰撞的时间；若不存在，仅输出一行

思路：

两质点发生完全弹性碰撞，可看成两小球相互穿过对方，因此本题可简化为求所有小球第 次相遇的时间，可用二分法，通过二分时间，判断当前时间是否存在 次碰撞

代码如下

#include<bits/stdc++.h>
#define INF 1000000001
#define LL long long
using namespace std;
vector<LL> u,v;
int n,ans;
LL k;
LL check(LL t)		//返回时间t时，碰撞的次数
{
    LL result=0;
    int p1=0,p2=0;
    for(auto &i:u)
    {
        while(p2<v.size()&&v[p2]<i)++p2;
        while(p1<v.size()&&v[p1]<=i+t)++p1;
        result+=p1-p2;
    }
    return result;
}
int main()
{
    scanf("%d%lld",&n,&k);
    for(int i=0;i<n;i++)
    {
        LL x,y;
        scanf("%lld%lld",&x,&y);
        if(y==1) u.push_back(x);
        else v.push_back(x);
    }
    sort(u.begin(),u.end());
    sort(v.begin(),v.end());
    int l=0,r=INF;
    while(l<=r)
    {
        int mid=(l+r)/2;
        LL nowk=check(mid);
        if(nowk>=k)
            r=mid-1;
        else
        {
            ans=mid;
            l=mid+1;
        }
    }
    if(ans==INF)
        printf("No\n");
    else
        printf("Yes\n%.6lf",(double)(++ans)/2);
    return 0;
}

完结撒花