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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

2013-2014 ACM-ICPC, NEERC, Moscow Subregional Contest  

2014-08-05 21:43:31|  分类: cf_gym |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://codeforces.com/gym/100257
比赛中出了H,I,B,赛后搞出了F和A。

H题:
题意:某人在坐标轴上从A坐出租车出发到D,只能左右走或者上下走,要求走的路径最短,另一个也想去D,给出坐标B,问能够不改变路线同时带上这个人。
题解:只要判断下B的坐标是否在A和D之间即可。

I题:
题意:有n个集合,告诉任意两个集合之间的交集元素,问是否存在这样的n个集合。
题解:先用set数组按给出的条件放入交集元素,最后再循环一遍看是否符合每个条件。
struct Node{
int x,y,k;
int f[12];
}node[20010];
set<int>s[210];
set<int>::iterator it,itt;
int t,n;

int solve()
{
for(int i=0;i<t;i++)
{
for(int j=0;j<node[i].k;j++)
{
s
[node[i].x].erase(node[i].f[j]);
s
[node[i].y].erase(node[i].f[j]);
}
for(it=s[node[i].x].begin();it!=s[node[i].x].end();it++)
{
int tt=*it;
itt
=s[node[i].y].find(tt);
if(itt != s[node[i].y].end())
return 0;
}
for(int j=0;j<node[i].k;j++)
{
s
[node[i].x].insert(node[i].f[j]);
s
[node[i].y].insert(node[i].f[j]);
}
}
return 1;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen
("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
while(sf(n)!=EOF)
{
fr
(n+1) s[i].clear();
t
=n*(n-1)/2;
for(int i=0;i<t;i++)
{
sf2
(node[i].x,node[i].y);
sf
(node[i].k);
for(int j=0;j<node[i].k;j++)
{
sf
(node[i].f[j]);
s
[node[i].x].insert(node[i].f[j]);
s
[node[i].y].insert(node[i].f[j]);
}
}
if(!solve()) pfs("No");
else
{
pfs
("Yes");
for(int i=1;i<=n;i++)
{
printf
("%d",s[i].size());
for(it=s[i].begin();it!=s[i].end();it++)
printf
(" %d",*it);
pfn
;
}
}
}
return 0;
}

B题:
题意:给出一个十六进制数,求下一个不合法数(数上每位数都各不相同)
题解:
先把给出的数加1,然后从第一位开始判断,如果到第i位发现之前出现过a[i],则第i位加1,如果有进位则忘前进位,然后从最前更新的位置开始,重新往后判断,而且后面的位置都得从0开始判断。
char ss[22];
int len,f[22];

int Num(char c)
{
if(c<='9' && c>='0')
return c-'0';
else
return 10+c-'A';
}

int Add(int pos)
{
char p;
if(ss[pos]>='0' && ss[pos]<='8')
p
=ss[pos]+1;
else if(ss[pos] == '9')
p
='A';
else if(ss[pos]<='E')
p
=ss[pos]+1;
else
p
='0';
f
[Num(ss[pos])]--;
f
[Num(p)]++;
ss
[pos]=p;
if(p == '0') return 1;
return 0;
}

int fun(int pos)
{
int i,tt;
for(i=pos;i>=0;i--)
{
tt
=Add(i);
if(tt == 0)
{
MEM
(f);
for(int j=0;j<=i;j++)
{
f
[Num(ss[j])]++;
if(f[Num(ss[j])] > 1)
return j;
}
return i+1;
}
}
if(tt == 1 && i == -1)
{
ss
[0]='1';
for(int j=0;j<len;j++)
ss
[j+1]='0';
len
++;
ss
[len]='\0';
}
MEM
(f);f[1]=1;
return 1;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen
("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
while(sfs(ss)!=EOF)
{
len
=LEN(ss);
fun
(len-1);
MEM
(f);f[Num(ss[0])]++;
for(int i=1;i<len;i++)
{
f
[Num(ss[i])]++;
if(f[Num(ss[i])] > 1)
{
for(int j=i+1;j<len;j++)
ss
[j]='0';
int tt=fun(i);
i
=tt-1;
}
}
pfs
(ss);
}
return 0;
}

F题:
题意:题目略长,大致是做地铁需要花28卢布,公交需要26卢布,现在有一种90分钟方案:90分钟内坐一次地铁,公交不限制次数,一共花44卢布。现在给出一个人一天的乘坐方式,问最小花多少卢布,如果能够自己确定90分钟方案的开始时间,又能最小花多少卢布。
题解:前一问,模拟即可,注意细节。后面一问,简单dp即可,具体见代码:
int n,f[1510];
int a[1510],b[1510],dp[1510];

void fun1()
{
int pay,cnt,pre,ans=0;
for(int i=0;i<n;i++)
{
pay
=b[i]==1?28:26;
pre
=a[i];
cnt
=b[i]==1?1:0;
i
++;
while(i<n && a[i]-pre <= 90)
{
if(b[i]==1)
cnt
++;
if(cnt > 1)
break;
pay
=44;
i
++;
}
i
--;
ans
+=pay;
}
printf
("%d ",ans);
}

void fun2()
{
//dp
fr
(n) dp[i]=INF;
for(int i=0;i<n;i++)
{
if(i == 0) dp[i]=b[i]==1?28:26;
else dp[i]=min(dp[i],dp[i-1]+(b[i]==1?28:26));
int nu=0,p=i+1,cnt=a[i];
if(b[i] == 1) nu++;
while(p<n && a[p]-cnt <= 90)
{
if(b[p] == 1) nu++;
if(nu > 1)
break;
p
++;
}
p
--;
if(i == 0) dp[p]=min(dp[p],44);
else dp[p]=min(dp[p],dp[i-1]+44);
}
pf
(dp[n-1]);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen
("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
char c[2];
int aa,bb;
while(sf(n)!=EOF)
{
MEM
(f);
fr
(n){
scanf
("%d:%d %s",&aa,&bb,c);
int t=aa*60+bb;
if(c[0] == 'U')f[t]=1;
else f[t]=2;
a
[i]=t;
b
[i]=c[0]=='U'?1:0;
}
fun1
();
fun2
();
}
return 0;
}

A题:
题意:有n个点,每个点有一个权值,表示可以连出去的边数,问最多能构成多少个三角形,三角形可以有交叉,但是不能有共用边。
题解:
仔细思考下可以发现,当最大值大于其余值的和的两倍的时候,结果为其余值的和(最大值提供两条边,其余值提供一条);否则结果为所有值除3(每个值提供一条边)。
  评论这张
 
阅读(90)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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