UESTC 2019 Summer Training #1 Div.2

比赛地址: https://vjudge.net/contest/309553

A – CodeForces 1080D 

题目大意:给你一个正方形,大的正方形可以切成四个小的正方形。然后从左下方到左上方到右上方需要有一条路径,这个路径上的所有方块要一样。

分析:路径上的,要么全切要么全不切。如果选择切中间的一定要先切。

代码:

#include <bits/stdc++.h>
using namespace std;
long long getlen(long long a,long long b)
{
    long long d=1;
    b--;
    long long len=1;
    while(d<a && b>=4*len-1)
    {
        b-=4*len-1;
        len*=2;d++;
    }
    return a-d;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        long long n,k;
        cin>>n>>k;
        if(n==2 && k==3)
        {
            cout<<"NO"<<endl;
            continue;
        }
        long long a=n,b=k;
        if(n<=60)
        {
            long long p=1;
            while(n--)
            {
                k-=p;
                p*=4;
            }
            if(k>0)
                cout<<"NO"<<endl;
            else
                cout<<"YES "<<getlen(a,b)<<endl;
        }
        else
            cout<<"YES "<<getlen(a,b)<<endl;
    }
    return 0;
}

C – Gym 101466E

题目大意:在A串中找最少出现n次的B串的最长子串的长度

分析:比赛时一开始想的是AC自动机,然后T掉了。仔细分析后,发现二分+KMP就可以过,但是万万没想到我的KMP板子有问题,调的心态爆炸。后来比赛后换了个板子就过了。

代码:

#include <bits/stdc++.h>
using namespace std;
void preKMP(string x,int m,int kmpNext[])
{
    int i,j;
    j=kmpNext[0]=-1;
    i=0;
    while(i<m)
    {
        while(j!=-1 && x[i]!=x[j]) j=kmpNext[j];
        if(x[++i]==x[++j])kmpNext[i]=kmpNext[j];
        else kmpNext[i]=j;
    }
}
int nexts[200010];
int KMP_Count(string x,string y)
{
    int i=0,j=0;
    int ans=0;
    int m=x.length(),n=y.length();
    preKMP(x,m,nexts);
    while(i<n)
    {
        while(j!=-1 && y[i]!=x[j]) j=nexts[j];
        i++;j++;
        if(j>=m)
        {
            ans++;
            j=nexts[j];
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    string str1,str2;
    int n;
    getline(cin,str1);
    getline(cin,str2);
    cin>>n;
    int l=0;int r=str2.length();
    while(l+1!=r)
    {
        int m=(l+r)/2;
        string str3=str2.substr(0,m);
        int q=KMP_Count(str3,str1);
        if(q>=n)
        {
            l=m;
        }
        else
        {
            r=m;
        }
    }
    string str3=str2.substr(0,r);
    int q=KMP_Count(str3,str1);
    if(q>=n)
    {
        if(str3=="")
        {
            cout<<"IMPOSSIBLE"<<endl;
            return 0;
        }
        cout<<str3<<endl;
        return 0;
    }
    str3=str2.substr(0,l);
    q=KMP_Count(str3,str1);
    if(q>=n)
    {
        if(str3=="")
        {
            cout<<"IMPOSSIBLE"<<endl;
            return 0;
        }
        cout<<str3<<endl;
        return 0;
    }
    cout<<"IMPOSSIBLE"<<endl;
    return 0;
}

D – CodeForces 1061D

题目大意:新开一个电视要花钱,每个电视每看一分钟也要花钱,求看完所有节目的最小花费

分析:节目可以抽象成线段,然后按照先左端点后右端点的排序。然后一个个的处理。显然对于某个节目,找离他最近的那个电视,然后判断是再开一个电视和拼接上去的花费哪个大。整个算法大概算个贪心吧。

代码:

#include <bits/stdc++.h>
using namespace std;
const long long MODNUM = 1000000007ll;
struct node
{
    long long s,e;
}nodes[100001];
bool cmp(const node &a,const node &b)
{
    if(a.s==b.s) return a.e<b.e;
    return a.s<b.s;
}
long long n,x,y;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>x>>y;
    for(long long i=0;i<n;++i)
    {
        cin>>nodes[i].s>>nodes[i].e;
    }
    sort(nodes,nodes+n,cmp);
    long long sum=0;
    multiset<long long> s;
    s.insert(nodes[0].e);
    sum = (x+y*(nodes[0].e-nodes[0].s)%MODNUM)%MODNUM;
    for(int i=1;i<n;++i)
    {
        auto q=s.lower_bound(nodes[i].s);
        --q;
        if( ( nodes[i].s - (*q) )*y <= x && nodes[i].s > (*q))
        {
            sum = (sum + (nodes[i].e - (*q))*y%MODNUM)%MODNUM;
            s.erase(q);
            s.insert(nodes[i].e);
        }
        else
        {
            sum = (sum + (nodes[i].e - nodes[i].s)*y%MODNUM + x)%MODNUM;
            s.insert(nodes[i].e);
        }
    }
    cout<<sum<<endl;
    return 0;
}

H – Gym 101466F

题目大意:绕来绕去,其实就是让你判三角形,签到题

代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    long long n,x,y,z;
    cin>>n;
    for(long long i=0;i<n;++i)
    {
        cin>>x>>y>>z;
        if(x>=y+z || y>=x+z || z>=x+y)
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

I – CodeForces 1074C

题目大意:让你计算那个函数的值。具体还是看题目吧

分析:大于等于4个点之后,这个值就不变了,所以只需要计算三个点和四个点。先说四个点,最左边最右边最上边最下边的四个点即可,我也不知道为什么。然后三个点的,选取那四个点中的两个,然后对剩下的点跑暴力即可。

代码:

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct p
{
    int x,y;
}ps[300010];
int dist(p a,p b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}
/////////////////////////
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    int pl,pr,pu,pd;
    int l=INF,r=-INF,u=-INF,d=INF;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>ps[i].x>>ps[i].y;
        if(ps[i].x<l)
        {
            l=ps[i].x;
            pl=i;
        }
        if(ps[i].x>r)
        {
            r=ps[i].x;
            pr=i;
        }
        if(ps[i].y>u)
        {
            u=ps[i].y;
            pu=i;
        }
        if(ps[i].y<d)
        {
            d=ps[i].y;
            pd=i;
        }
    }
    for(int k=3;k<=n;++k)
    {
        if(k==3)
        {
            int ans=0;
            for(int j=0;j<n;++j)
            {
                int tmp=dist(ps[j],ps[pl])+dist(ps[j],ps[pd])+dist(ps[pl],ps[pd]);
                ans=max(tmp,ans);
            }
            for(int j=0;j<n;++j)
            {
                int tmp=dist(ps[j],ps[pl])+dist(ps[j],ps[pu])+dist(ps[pl],ps[pu]);
                ans=max(tmp,ans);
            }
            for(int j=0;j<n;++j)
            {
                int tmp=dist(ps[j],ps[pr])+dist(ps[j],ps[pd])+dist(ps[pr],ps[pd]);
                ans=max(tmp,ans);
            }
            for(int j=0;j<n;++j)
            {
                int tmp=dist(ps[j],ps[pr])+dist(ps[j],ps[pu])+dist(ps[pr],ps[pu]);
                ans=max(tmp,ans);
            }
            cout<<ans<<" ";
        }
        else
        {
            cout<<2*(r-l+u-d)<<" ";
        }
    }
    return 0;
}

K – Gym 101505B

题目大意:签到题,对每个数统计一下每个数字出现与否,然后状压塞进set即可

代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    while(cin>>n)
    {
        string str;
        set<long long> s;
        for(int i=0;i<n;++i)
        {
            cin>>str;
            long long a[10]={0,0,0,0,0,0,0,0,0,0};
            for(int j=0;j<str.length();++j)
            {
                ++a[str[j]-'0'];
            }
            long long q=1;
            long long sum=0;
            for(int j=1;j<10;++j)
            {
                if(a[j])
                {
                    sum+=q;
                }
                q*=10;
            }
            s.insert(sum);
        }
        cout<<s.size()<<endl;
    }
    return 0;
}

L – Gym 101505K 

题目大意:让你敲一个摩尔斯电码的模拟……

代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    string str;
    string alp[26];
    alp[0]=".-";
    alp[1]="-...";
    alp[2]="-.-.";
    alp[3]="-..";
    alp[4]=".";
    alp[5]="..-.";
    alp[6]="--.";
    alp[7]="....";
    alp[8]="..";
    alp[9]=".---";
    alp[10]="-.-";
    alp[11]=".-..";
    alp[12]="--";
    alp[13]="-.";
    alp[14]="---";
    alp[15]=".--.";
    alp[16]="--.-";
    alp[17]=".-.";
    alp[18]="...";
    alp[19]="-";
    alp[20]="..-";
    alp[21]="...-";
    alp[22]=".--";
    alp[23]="-..-";
    alp[24]="-.--";
    alp[25]="--..";
    while(cin>>str)
    {
        int last=0;
        int q=str.find("/",last);
        string str1;
        while(q!=-1)
        {
            str1=str.substr(last,q-last);
            if(str1=="")
            {
                cout<<" ";
            }
            else
            {
                for(int i=0;i<26;++i)
                {
                    if(alp[i]==str1)
                    {
                        char c='A'+i;
                        cout<<c;
                        break;
                    }
                }
            }
            last=q+1;
            q=str.find("/",last);
        }
        str1=str.substr(last,str.length()-last);
        for(int i=0;i<26;++i)
        {
            if(alp[i]==str1)
            {
                char c='A'+i;
                cout<<c;
                break;
            }
        }
        cout<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注