首页 > 其他分享 >JAG Spring Contest 2012 G PLAY in BASIC 题解

JAG Spring Contest 2012 G PLAY in BASIC 题解

时间:2022-12-19 14:57:20浏览次数:87  
标签:tmp PLAY string Contest int 题解 rep pb size

提交链接

其实就是个大模拟。首先对输入的串进行处理,把所有的命令分开,并把连续的停顿合并。为了方便,定义一个时间单位为全音符的\(\frac 1{128}\),这样所有命令的持续时间都是整数个时间单位。然后就可以dp了,\(dp_{i,j,k}\)表示处理到第i个命令,当前八度为j,当前默认时长为k的最优解长度。音量不需要记录,因为音量操作占用的总长度是固定的,只有音符音量改变的时候才需要用一次。dp的时候需要记录路径,因为是要构造方案的。转移情况比较多,但是都不难想。如果下一个命令准备填L,则转移的时候需要进一步枚举设置成的新的默认长度(一共8种)。需要对任意长度的音符和停顿预处理出在j和k固定的情况下的最短表示。有一个问题是连续的停顿长度可能达到\(128n\)个时间单位,不可能预处理到那么长的。当连续的停顿很长的时候,一定存在一种最优解满足在这些停顿中靠前的某个位置把默认时长设置成了全音符,然后后面填上一堆R,这样是最省空间的。可以猜一个阈值,比如2000,在连续停顿很长的时候把前2000个和后2000个拿出来单独用dp预处理,中间的部分则全填成R。

时间复杂度\(O(8^3n)\),常数略大。

点击查看代码
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

using namespace std;

const int inf=1000000000;

struct node
{
  pii nn;
  int oo,ll,vv;
  node(pii _n=mpr(0,0),int _o=0,int _l=0,int _v=0){nn=_n;oo=_o;ll=_l;vv=_v;}
};
string s,pat="CDEFGAB",f[2010][10][10];
char c[100010];
vector <node> v,vv;
int dp[100010][10][10],imp[200];
pair <pii,int> lst[100010][10][10];
string lsts[100010][10][10];

int getNid(char c){rep(i,pat.size()) if(pat[i]==c) return i;return 114514;}

string getNote(pii note,int len,int curlen)
{
  string ret="";ret.pb(pat[note.fi]);
  if(note.se==0) ret.pb('-');else if(note.se==2) ret.pb('+');
  if(curlen==len) return ret;
  int good=0;rep(i,8) if((1<<i)<=len) good=i;
  good=(1<<good);
  if(curlen!=good) ret+=to_string(128/good);
  LL ori=good;
  while(good<len)
  {
    good+=ori/2;ori/=2;
    ret.pb('.');
  }
  return ret;
}

void upd(int i,int j,int k,int ii,int jj,int kk,string tmp)
{
  if(dp[i][j][k]>tmp.size()+dp[ii][jj][kk])
  {
    dp[i][j][k]=tmp.size()+dp[ii][jj][kk];
    lst[i][j][k]=mpr(mpr(ii,jj),kk);
    lsts[i][j][k]=tmp;
  }
}

void chmin(string &x,string y){if(x=="-"||x.size()>y.size()) x=y;}

int main()
{
  rep(i,8) imp[1<<i]=i;
  rep(i,2008) rep(j,10) rep(k,10) f[i][j][k]="-";
  rep(i,8) f[0][i][i]="";
  rep(i,2001) rep(j,8) rep(k,8) if(f[i][j][k]!="-")
  {
    rep(p,8)
    {
      int bas=(1<<p);
      string bk="";
      int ori=bas;
      rep(r,p+1)
      {
        if(i+bas<=2000) chmin(f[i+bas][j][p],f[i][j][k]+"L"+to_string(128/(1<<p))+"R"+bk);
        bas+=(ori>>1);ori/=2;bk.pb('.');
      }
    }
    rep(p,8)
    {
      int bas=(1<<p);
      string bk="";
      int ori=bas;
      rep(r,p+1)
      {
        if(i+bas<=2000) chmin(f[i+bas][j][k],f[i][j][k]+"R"+(p==k ? "":to_string(128/(1<<p)))+bk);
        bas+=(ori>>1);ori/=2;bk.pb('.');
      }
    }
  }
  int tn=0;
  while(scanf("%s",c))
  {
    ++tn;
    s=c;
    if(s=="*") break;
    int curo=4,curl=32,curv=100;
    v.clear();
    rep(i,s.size())
    {
      if(s[i]=='O')
      {
        curo=s[i+1]-'0';
        ++i;
      }
      else if(s[i]=='<') --curo;
      else if(s[i]=='>') ++curo;
      else if(s[i]=='L')
      {
        int val=0;
        while(i+1<s.size()&&isdigit(s[i+1])) val=val*10+s[++i]-'0';
        val=128/val;
        curl=val;
      }
      else if(s[i]=='V')
      {
        int val=0;
        while(i+1<s.size()&&isdigit(s[i+1])) val=val*10+s[++i]-'0';
        curv=val;
      }
      else if(s[i]!='R')
      {
        pii N=mpr(getNid(s[i]),1);
        if(i+1<s.size()&&s[i+1]=='-') N.se=0,++i;
        else if(i+1<s.size()&&s[i+1]=='+') N.se=2,++i;
        if(N==mpr(2,2)) N=mpr(3,1);else if(N==mpr(3,0)) N=mpr(2,1);
        int L=curl;
        if(i+1<s.size()&&isdigit(s[i+1]))
        {
          L=0;
          while(i+1<s.size()&&isdigit(s[i+1])) L=L*10+s[++i]-'0';
          L=128/L;
        }
        int ori=L;
        while(i+1<s.size()&&s[i+1]=='.') ++i,L+=ori/2,ori/=2;
        v.pb(node(N,curo,L,curv));
      }
      else
      {
        int L=curl;
        if(i+1<s.size()&&isdigit(s[i+1]))
        {
          L=0;
          while(i+1<s.size()&&isdigit(s[i+1])) L=L*10+s[++i]-'0';
          L=128/L;
        }
        int ori=L;
        while(i+1<s.size()&&s[i+1]=='.') ++i,L+=ori/2,ori/=2;
        v.pb(node(mpr(-1,0),0,L,(v.size()==0 ? 100:v.back().vv)));
      }
    }
    vv.clear();
    rep(i,v.size())
    {
      if(v[i].nn.fi>-1) vv.pb(v[i]);
      else
      {
        int p=i,tot=v[i].ll;
        while(p+1<v.size()&&v[p+1].nn.fi==-1) tot+=v[++p].ll;
        vv.pb(node(mpr(-1,0),0,tot,v[i].vv));
        i=p;
      }
    }
    v=vv;
    rep(i,v.size()+3) rep(j,10) rep(k,10) dp[i][j][k]=inf;
    dp[0][5][4]=0;
    rep(i,v.size()) rep(j,8) repn(k,8) if(dp[i][j][k]<inf)
    {
      if(v[i].nn.fi>-1)
      {
        int preV=(i==0 ? 100:v[i-1].vv);
        string addV="";
        if(preV!=v[i].vv) addV="V"+to_string(v[i].vv);
        vector <node> nns=vector <node>{v[i]};
        if(v[i].nn==mpr(0,0)&&v[i].oo>1) nns.pb(node(mpr(6,1),v[i].oo-1,v[i].ll,v[i].vv));
        else if(v[i].nn==mpr(6,2)&&v[i].oo<8) nns.pb(node(mpr(0,1),v[i].oo+1,v[i].ll,v[i].vv));
        else if(v[i].nn==mpr(0,1)&&v[i].oo>1) nns.pb(node(mpr(6,2),v[i].oo-1,v[i].ll,v[i].vv));
        else if(v[i].nn==mpr(6,1)&&v[i].oo<8) nns.pb(node(mpr(0,0),v[i].oo+1,v[i].ll,v[i].vv));
        rep(p,nns.size())
        {
          node nxt=nns[p];
          string add=addV;
          if(nxt.oo==k-1) add.pb('<');
          else if(nxt.oo==k+1) add.pb('>');
          else if(nxt.oo!=k) add+="O"+to_string(nxt.oo);
          string sv=add;
          {
            int hi=0;rep(r,8) if((nxt.ll&(1<<r))>0) hi=r;
            hi=(1<<hi);
            add+="L"+to_string(128/hi)+getNote(nxt.nn,nxt.ll,hi);
            upd(i+1,imp[hi],nxt.oo,i,j,k,add);
          }
          add=sv;
          {
            add+=getNote(nxt.nn,nxt.ll,1<<j);
            upd(i+1,j,nxt.oo,i,j,k,add);
          }
        }
      }
      else
      {
        int len=v[i].ll;
        string add="";while(len>2000) len-=128,add.pb('R');
        rep(ed,8)
        {
          string tmp=f[len][j][ed];
          if(tmp=="-") continue;
          if(!add.empty())
          {
            int pre=0;
            if(j==7);
            else rep(p,tmp.size()-1) if(tmp[p]=='L'&&tmp[p+1]=='1'&&(p+2>=tmp.size()|| !isdigit(tmp[p+2])))
            {
              pre=p+2;
              break;
            }
            string tmpp=tmp.substr(0,pre)+add+tmp.substr(pre);
            tmp=tmpp;
          }
          upd(i+1,ed,k,i,j,k,tmp);
        }
      }
    }
    int opt=inf,i,j,k;
    rep(ii,8) repn(jj,8) if(dp[v.size()][ii][jj]<opt) opt=dp[v.size()][ii][jj],i=v.size(),j=ii,k=jj;
    string ans="";
    while(i>0)
    {
      for(int ii=(int)(lsts[i][j][k].size())-1;ii>=0;--ii) ans.pb(lsts[i][j][k][ii]);
      pair <pii,int> tmp=lst[i][j][k];i=tmp.fi.fi;j=tmp.fi.se;k=tmp.se;
    }
    reverse(ans.begin(),ans.end());
    printf("%s\n",ans.c_str());
  }
	return 0;
}

标签:tmp,PLAY,string,Contest,int,题解,rep,pb,size
From: https://www.cnblogs.com/legendstane/p/play-in-basic-jag-spring-contest-2012-baekjoon-11702

相关文章

  • 洛谷 P6580 [Ynoi 2019] 美好的每一天~ 不连续的存在 题解
    既然是YNOI那肯定是要分块的。先考虑树是一条链的情况,可以直接回滚莫队,对n个节点组成的序列分块。在回滚莫队的过程中,当前维护的区间一共会扩展\(O(n\sqrtn)\)次,每次都是......
  • Android Studio使用Mob实现短信验证功能遇到的问题解决
    一、Mob短信验证​​全球领先的数据智能科技平台-MobTech袤博解决​​进行注册登入 登入成功后,点击开发者服务中的短信验证,进入开发者平台填好信息创建成功后显示下图,可以......
  • P7710 [Ynoi2077] stdmxeypz 题解
    对@LHFdalao的题解进行一些补充说明。因为他讲的实在是太难懂了。最后在@_•́へ•́╬_dalao的帮助下才勉强知道怎么做。不过他的代码非常简洁易懂,有需求的可以去看......
  • P6877 题解
    前言题目传送门!更好的阅读体验?贪心。内容抄自某校课件。思路部分分这个随便搞都可以,可以二分答案然后建边然后跑二分图最大匹配。正解考虑贪心。这里有一个重要的......
  • P3556 题解
    前言题目传送门!更好的阅读体验?最短路应用。内容抄自某校课件。思路首先想到题目与最短路有关。假如\(a\)到\(b\)的最短路径长度是\(x\),那么对于一个询问是否存......
  • AtCoder Beginner Contest 282
    《MakeBipartite2》思维,二分图  这个简单图可以有两种情况:1.全部点都通过边连起来,即连通分量只有一个,其自己2.还有有些点没有全部连起来,即有多个连通分......
  • Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
    A.AddPlusMinusSign如果有偶数个1,显然可以通过加减各一半的方式达到和为0;否则可以达到和为1。需要注意如果序列的第一个数是1,则它的前面只能填加号。时间复杂度\(O(n......
  • Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
    A.AddPlusMinusSign如果有偶数个1,显然可以通过加减各一半的方式达到和为0;否则可以达到和为1。需要注意如果序列的第一个数是1,则它的前面只能填加号。时间复杂度\(O(n......
  • Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
    A.AddPlusMinusSign如果有偶数个1,显然可以通过加减各一半的方式达到和为0;否则可以达到和为1。需要注意如果序列的第一个数是1,则它的前面只能填加号。时间复杂度\(O(n......
  • Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
    A.AddPlusMinusSign如果有偶数个1,显然可以通过加减各一半的方式达到和为0;否则可以达到和为1。需要注意如果序列的第一个数是1,则它的前面只能填加号。时间复杂度\(O(n......