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)，然后预处理每种状态去掉一个１后转移到哪种状态 (去掉一个１后有些数不能选，故相当于去掉很多数)
#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;
}
0 条评论