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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[Topcoder]SRM695 Div1  

2016-07-19 21:42:10|  分类: 比赛 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
因为几天后要去义务讲课,所以今天稍微复习了一下……
数论大概能达到noip提高水平了(?
然后收到codeforces的mail,发现今天晚上9点多有场比赛
四处逛了一下发现7点有场tc
于是果断选择占时间比较短的tc

[Topcoder]SRM695 Div1 - 时光机 - 时光机TimeMachine
room里还是挺壮烈的
一题滚了……(应该说幸好还有一题
希望早日回黄

第一题题意:
定义constant string

A string is called constant if all of its characters are the same.

For example, "a" and "bbbbb" are constant strings, but "aba" is not a constant string.

定义substring

A substring of a string is any non-empty contiguous subsequence of its characters.

For example, both "abc" and "bcd" are substrings of "abcde", but "ace" is not a substring of "abcde".

位置不同的两个相同substring算是两个

给你长度为n的一个数组x(x[i]>=0)
构造一个只由a、b组成的字符串要求满足长度为i的substring有x[i]个
有多解输出字典序最小的

第二题:
给你一张图,和一些无向边
点数<1000 边数<1000
无自环无重边
每个点连的边数>=3
每个点有一个值v[i],给你一个整数K(1<=K<=7),表示最多可以修复K条边
如果一个点i有且仅有一条边被修复,ans+=v[i]
求最大的ans



下面是题解



首先我们把一个字符串转化一下
把aaabbaab这样的看成|xxx|xx|xx|x|
对于最大的一个x[i]非0的i,x[i]的值显然就是长度为i的constant string的个数
例如x[3]=2一定会有且仅有两个|xxx|
然后我们就把x[3]占用掉的x[1] x[2]减掉
也就是
x[1] -= 6 x[2] -= 4
再重复上面的过程
判掉不合法的情况
最后得到一个新的X数组,X[i]表示长度为i的|x...x|有X[i]个
然后构造的时候显然是一个a一个b
为了字典序最小,我们就一个尽可能长的a串接一个尽可能短的b

#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100;
int n,m;
short lef[N];
class BearPasswordLexic
{
public:
 string findPassword(vector <int>x){
  n = x.size();
  int i,j;
  for(i=1;i<=n;i++)lef[i] = x[i-1];
  //if(x[0]!=n)return "";
  int tot=0;
  for(i=n;i>=1;i--)
  if(lef[i]){
   if(lef[i] < 0)
    return "";
   tot += lef[i]*i;
   for(j=i-1;j;j--){
    lef[j] -= lef[i]*(i-j+1);
   }
  }
  if (tot != n)return "";
  //for(i=1;i<=n;i++)printf("%d ",lef[i]);printf("\n");
  //make
  string re="";
  i = n;j = 1;
  while(tot){
   while(!lef[i])i--;
   lef[i]--;
   tot-=i;
   for(int k = 1;k<=i;k++)re += "a";
   if(!tot)break;
   while(!lef[j])j++;
   lef[j]--;
   tot-=j;
   for(int k = 1;k<=j;k++)re += "b";
  }
  return re;
 }
}fuck;

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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