注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

CF 135 DIV2  

2012-08-28 02:55:03|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
AK了,rank20 ,毕竟是一件很令人高兴的事情
题目很水很水,所以做起来也比较爽,只不过评测等了好久
继续贴代码吧
A题很水

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;

const int MAX=1000+10;
char s[MAX];
int num[MAX],n,k,ans[MAX];

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,j;
scanf("%d",&k);
scanf("%s",s+1);
n=strlen(s+1);
for(i=1;i<=n;++i)
num[s[i]-'a']++;
for(i=0;i<26;++i)
if(num[i]%k!=0)
{
printf("-1\n");
return 0;
}
for(i=0;i<26;++i)
{
for(j=1;j<=num[i]/k;++j)
ans[++ans[0]]=i+'a';
}
for(i=1;i<=k;++i)
for(j=1;j<=ans[0];++j)
printf("%c",ans[j]);
printf("\n");
}

B 其实是最难的题,我写的是二分+暴枚

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

typedef unsigned long long LL;
LL n,d,power[20];

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i;
power[0]=1;
for(i=1;i<=20;++i)
power[i]=power[i-1]*10;
cin>>n>>d;
LL ansm=0;
for(i=1;power[i]-1<=n;++i)
{
LL left=0,right=n/power[i],mid;
while(left<right)
{
mid=(left+right+1)/2;
if(mid*power[i]+power[i]-1<=n)
left=mid;
else right=mid-1;
}
LL delta=n-(left*power[i]+power[i]-1);
if(delta<=d && delta>=0)
ansm=left*power[i]+power[i]-1;
}
if(ansm)cout<<ansm<<endl;
else cout<<n<<endl;
}

C 水dp

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX=500000+10;
const int NUM=30;
const int INF=1000000000;

int n,k,f[MAX][NUM],come[MAX][NUM];
char str[MAX],ans[MAX];

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,j;
scanf("%d %d",&n,&k);
scanf("%s",str+1);
for(i=0;i<=n+1;++i)
for(j=0;j<=26;++j)
f[i][j]=INF;
f[0][0]=0;
str[n+1]='A'-1;
for(i=1;i<=n+1;++i)
{
int m1=0,m2=0;
for(j=1;j<=k;++j)
{
if(f[i-1][j]<f[i-1][m1])
{
m2=m1;
m1=j;
}
else if(f[i-1][j]==f[i-1][m1])
m2=j;
else if(m2==m1 || f[i-1][m2]>f[i-1][j])
m2=j;
}
int cost;
j=(i==n+1?0:1);
for(;j<=k;++j)
{
cost=(j==m1)?f[i-1][m2]:f[i-1][m1];
f[i][j]=cost+((str[i]-'A'+1)!=j);
come[i][j]=(j==m1)?m2:m1;
}
}
int now=0;
for(i=n;i>=1;--i)
{
now=come[i+1][now];
ans[i]=now+'A'-1;
}
printf("%d\n",f[n+1][0]);
for(i=1;i<=n;++i)
printf("%c",ans[i]);
printf("\n");
}

D 树p,两遍dfs完事

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX=1000000+10;

int n;
int begin[MAX],c[MAX],t[MAX],next[MAX],tot;
int f1[MAX],f2[MAX],hash[MAX],fa[MAX],come[MAX];

void addedge(int u,int v,int k)
{
t[++tot]=v;
next[tot]=begin[u];
begin[u]=tot;
c[tot]=k;
}

void dfs(int u)
{
hash[u]=1;
int i,v;
f1[u]=0;
for(i=begin[u];i;i=next[i])
{
v=t[i];
if(!hash[v])
{
fa[v]=u;
come[v]=i;
dfs(v);
f1[u]+=f1[v]+c[i];
}
}
}

void dfs2(int u)
{
int i,v;
f2[u]=0;
if(fa[u])
f2[u]=f2[fa[u]]+(c[come[u]]==0)+f1[fa[u]]-f1[u]-c[come[u]];
for(i=begin[u];i;i=next[i])
{
v=t[i];
if(fa[v]==u)
dfs2(v);
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,x,y;
scanf("%d",&n);
for(i=1;i<=n-1;++i)
{
scanf("%d %d",&x,&y);
addedge(x,y,0);
addedge(y,x,1);
}
dfs(1);
dfs2(1);
int m=n+1;
for(i=1;i<=n;++i)
{
if(f1[i]+f2[i]<m)
m=f1[i]+f2[i];
}
printf("%d\n",m);
for(i=1;i<=n;++i)
if(f1[i]+f2[i]==m)
printf("%d ",i);
printf("\n");
return 0;
}

E set暴力维护区间

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#define x first
#define y second
#define mp make_pair
using namespace std;

const int MAX=2000000+20;
typedef pair<int,pair<int,int> > line;

int n,place[MAX];
set<line> t;
set<int> p;

int calc(int u,int v)
{
int cost;
if(u==0)cost=(v-1)*4;
else if(v==n+1)cost=(n-u)*4;
else
{
cost=((u+v)/2-u)*4;
}
return cost;
}

void insert(int u,int v)
{
if(u+1>=v)return;
int cost=calc(u,v);
t.insert(mp(-cost,mp(u,v)));
}

void add(int id)
{
if(t.empty())
{
place[id]=1;
p.insert(1);
insert(1,n+1);
}
else
{
set<line>::iterator it=t.begin();
if(it->y.x==0)
{
place[id]=1;
insert(1,it->y.y);
}
else if(it->y.y==n+1)
{
place[id]=n;
insert(it->y.x,n);
}
else
{
place[id]=(it->y.x+it->y.y)/2;
insert(it->y.x,place[id]);
insert(place[id],it->y.y);
}
t.erase(it);
p.insert(place[id]);
}
printf("%d\n",place[id]);
}

void erase(int u,int v)
{
if(u+1>=v)return;
int cost=calc(u,v);
set<line>::iterator it=t.lower_bound(mp(-cost,mp(u,v)));
if(it!=t.end())t.erase(it);
}

void del(int id)
{
int pp=place[id];
place[id]=0;
int pre,suc;
set<int>::iterator it;
if((it=p.lower_bound(pp))!=p.begin())
{
--it;
pre=*it;
}
else pre=0;

if((it=p.upper_bound(pp))!=p.end())
{
suc=*it;
}
else suc=n+1;

erase(pre,pp);
erase(pp,suc);
insert(pre,suc);
p.erase(pp);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,k,id,m;
scanf("%d %d",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%d %d",&k,&id);
if(k==1)
{
add(id);
}
else
{
del(id);
}
}
}



  评论这张
 
阅读(240)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018