T1.turnover(营业额统计)

题意:自行百度,省选题
分析:这种只需要找前驱后继的数据结构题,实在犯不着手写Splay,SegmentTree之类的玩意,一个set搞定,开了O2跑得飞起,不开依旧稳稳的。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>

using namespace std;

set<int>st;
set<int>::iterator pre,suf;
int a,n;
long long ans,pls;
int main()
{
    freopen("turnover.out","w",stdout);
    freopen("turnover.in","r",stdin);
    scanf("%d%d",&n,&a);
    st.insert(a);
    ans=a;
    for(int w=2;w<=n;w++)
    {
        scanf("%d",&a);
        pre=suf=st.lower_bound(a);
        pre--;
        pls=99999999;
        if(suf==st.begin())pls=min(pls,(long long)(*suf-a));
        else if(suf==st.end())pls=min(pls,(long long)(a-*(pre)));
        else pls=min(pls,(long long)min(a-*pre,*suf-a));
        ans+=pls;
        st.insert(a);
    }
    cout<<ans<<endl;
    return 0;
}

T2.Promotion(商品推销)

题意:不停给你一些数,找到当前最大和最小的数,“答案”加上他们的差,然后删除他们。最后输出“答案“即可。
分析:这种只需要找最大最小的数据结构题,实在犯不着手写Splay,SegmentTree之类的玩意,一个map搞定,开了O2跑得飞起,不开好像很危险,但不会超时。

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

map<int,int>mp;
map<int,int>::iterator il,ir;
long long ans;

int main()
{
    freopen("pro.in","r",stdin);
    freopen("pro.out","w",stdout);
    int n,a,k;
    scanf("%d",&n);
    for(register int i=1;i<=n;++i)
    {
        scanf("%d",&k);
        for(register int j=1;j<=k;++j)
        {
            scanf("%d",&a);
            mp[a]++;
        }
        if(mp.empty())continue;
        il=mp.begin();
        ir=mp.end();
        ir--;
        ans+=ir->first-il->first;
        if(il->second>=2)il->second--;
        else mp.erase(il);
        if(mp.empty())continue;
        if(ir->second>=2)ir->second--;
        else mp.erase(ir);
    }
    cout<<ans<<endl;
    return 0;
}

T3.money(彩票问题)

题意:给定1-M的数字,求其中选出不同的N个使他们的倒数和为(X/Y)的方案有几种。(M<=50;N<=10;X,Y<=100)
分析:很显然的搜索,但是需要强效的剪枝:
首先,我们从倒数大的数往小的数搜索。
设:当前正在决策x是否选择,已经选择了k个数字,倒数和为s,sum[i]表示第i到m的倒数和。
1.$ X/Y-s>(sum[x]+sum[x+(n-k)])$时剪枝,意思是如果以后全选最大数都不能达到X/Y时剪枝
2.$ X/Y-s<(sum[m-(n-k)+1]) $时剪枝,意思是如果以后全选最小数都会比X/Y大时剪枝
有了这两个剪枝,再使用long double,并将eps设为1e-10~1e-12就可以AC了(1e-9会WA)。

#include <iostream>
#include <cstring>
#include <cstdio>

#define abs(x) (((x)<0)?(-(x)):(x))
#define MX 100
#define eps 0.0000000001

using namespace std;

typedef long double data;

data sum[MX],x,y;
int n,m,ans;

void init()
{
    sum[m+1]=0;
    for(int i=m;i>=1;i--)
        sum[i]=sum[i+1]+1.000000000/(data)i;
}

int stp[MX];

void sch(data rm,int pos,int num)
{
    if(rm<-eps)return;
    if((n-num+pos-1)>m)return;
    if(abs(rm-0)<eps&&num==n)
    {
        ans++;
        return;
    }
    if(num>=n)return;
    if(rm-sum[pos]+sum[pos+(n-num)]>eps)return;
    if(rm-sum[m-(n-num)+1]<-eps)return;
    sch(rm-1.0000000000/(data)pos,pos+1,num+1);
    sch(rm,pos+1,num);
}

int main()
{
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    cin>>n>>m>>x>>y;
    init();
    sch(x/y,1,0);
    cout<<ans<<endl;
    return 0;
}

T4.game(数字游戏)

题意:给你几个数字(2~20),两个人轮流选。每选择一个数x,会出现以下效果:x和之前任何一个被选的数y组成的ax+by不可被选(0<=x,y)
求当前局面先手选哪个才可以100%使对方最后无数可选。
分析:注意到状态数十分的少,(2^19),所以使用状态压缩Dp.
我们需要先预处理出每个状态中1的个数(lowbit),然后预处理每种状态去掉一个1后转移到哪种状态(去掉一个1后有些数不能选,故相当于去掉很多数)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 524290

#define WIN 1
#define LOSE 0
#define MSTATE ((1<<19)-1)

using namespace std;

int beg;
int st[MX];
int num1[MX];
int stage[MX];
char chose[MX][30];
int mask[11];
int nexts[MX];
int pre[MX][30];

int lowbit(int x){return x&-x;}
bool cmp(int a,int b){return num1[a]<num1[b];}

int refresh(int now)
{
    int nxt=now;
    for(int i=2;i<=10;i++)
        if((now&(1<<(i-2)))==0)now&=mask[i];
    for(int i=0;i<19;i++)
    {
        for(int j=0;j+i<19;j++)
        {
            if((!(now&(1<<i)))&&(!(now&(1<<j))))
                nxt=(nxt&(MSTATE^(1<<(i+j+2))));
        }
    }
    return nxt;
}

void init()
{
    int t;
    for(int i=2;i<=10;i++)
    {
        mask[i]=MSTATE;
        for(int j=1;j*i<=20;j++)
            mask[i]=mask[i]&(MSTATE^(1<<(j*i-2)));
    }
    for(int i=1;i<=MSTATE;i++)
    {
        t=i;
        while(t)t-=lowbit(t),num1[i]++;
    }
    for(int i=1;i<=MSTATE;i++)stage[i]=i;
    sort(stage+1,stage+MSTATE+1,cmp);
    for(int i=1;i<=MSTATE;i++)nexts[i]=refresh(i);

}

void work()
{
    int now,nxt;
    for(int i=1;i<=MSTATE;i++)
    {
        if(num1[stage[i]]==1){st[stage[i]]=WIN;continue;}
        for(int j=0;j<19;j++)
        {
            now=stage[i];
            if((now&(1<<j)))
            {
                nxt=now^(1<<j);
                nxt=nexts[nxt];
                if(st[nxt]==LOSE)
                {
                    st[now]=WIN;
                    pre[now][++pre[now][0]]=j+2;
                }
            }
        }
    }
}

int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    init();
    int a;
    while(cin>>a)beg|=(1<<(a-2));
    work();
    if(st[beg]==1)
    {
        for(int i=1;i<=pre[beg][0];i++)cout<<pre[beg][i]<<" ";cout<<endl;
    }
    else cout<<0<<endl;

    return 0;
}

T5.windoors(windoors安装密码)

题意:给定一些字符串,忽略掉其中长度不为25,出现了非字母的字符串。然后求其中出现最多的是哪一个。如果有多个一样多输出0。
分析:把字符串都hash一下就太棒了。

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 50002
#define MD 142857

using namespace std;

typedef unsigned long long ull;

int n;
int fst[MD],nxt[MX],cnt[MX],pos[MX],hnum;
ull val[MX];

inline ull rehash(char *str)
{
    ull has=0,hh=1313131313;
    for(int i=1;i<=25;i++)has=has*hh+(*str++)-'a';
    return has;
}

void insrt(char *str,int p)
{
    ull has=rehash(str);
    for(int i=fst[has%MD];i;i=nxt[i])
        if(val[i]==has)
        {
            cnt[i]++;
            return;
        }
    nxt[++hnum]=fst[has%MD];
    fst[has%MD]=hnum;
    cnt[hnum]=1;
    val[hnum]=has;
    pos[hnum]=p;
}

char in[10005][26];

int main()
{
    freopen("windoors.in","r",stdin);
    freopen("windoors.out","w",stdout);
    int f;
    scanf("%d",&n);
    for(int w=1;w<=n;w++)
    {
        cin>>in[w];
        if(strlen(in[w])!=25)continue;
        f=0;
        for(int i=0;i<25;i++)
        {
            if(in[w][i]>='a'&&in[w][i]<='z')continue;
            else if(in[w][i]>='A'&&in[w][i]<='Z')in[w][i]=in[w][i]-('A'-'a');
            else f=1;
        }
        if(f==1)continue;
        insrt(in[w],w);
    }

    int mx=-1,p=0;
    for(int i=1;i<=hnum;i++)
    {
        if(cnt[i]>mx)
        {
            mx=cnt[i];
            p=i;
        }
    }
    for(int i=1;i<=hnum;i++)
        if(cnt[i]==mx&&i!=p)
        {
            cout<<"no solution"<<endl;
            return 0;
        }
    if(mx==-1)
    {
        cout<<"no solution"<<endl;
        return 0;
    }
    cout<<in[pos[p]]<<endl;
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

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

你是机器人吗? =。= *