头像

s.y.




离线:1小时前


最近来访(560)
用户头像
艾倫耶格爾
用户头像
AcWing2AK
用户头像
三三得玖
用户头像
ohhhdddentist
用户头像
754839
用户头像
Tongtiandai
用户头像
Resurgence1001
用户头像
OOOVOOO
用户头像
こんにちは
用户头像
zzf_yyy
用户头像
Henry1
用户头像
忘打周赛
用户头像
yxy.
用户头像
鲶鱼饭
用户头像
略略略_3
用户头像
同学请叫我笨笨
用户头像
lmzz
用户头像
种花家的Trae
用户头像
一万小时定律
用户头像
珂艾尔丶芙兰奈特


s.y.
1小时前

3 5
2 2
3 3
1 3
3 2
1 2

ans:1




s.y.
19天前

2022-07-28 22-33-13屏幕截图.png
图片包括数据和时间和我的呆码




s.y.
3个月前

这数据有点水




s.y.
4个月前

为什么还是MLE




s.y.
4个月前

最后一个良心数据



题目讨论 AcWing 352. 想法

s.y.
5个月前

我们认为一条边能“代替”另一条边,当且仅当此边换掉另一条边仍能连通;
令cnt[x]意为 x连向fa[x]的那条边,找另一条边可“代替”其的个数。
(这些可以用LCA+树上差分去维护)
最后再统计个数
如果一条边cnt值为0,则贡献为m
如果一条边cnt值为1,则贡献为1
Otherwise,贡献为0。




s.y.
5个月前

这题时限卡太紧了吧



题目讨论 AcWing 182. A*

s.y.
6个月前

此题如果没有内存限制 A_star也可以通过此题
如果n==6的话 A_star跑的还更快(快2倍)
但其他时候DFS+A_star跑的更快 (n==7时又比A*快了,戏剧)



题目讨论 AcWing 181. 思考

s.y.
6个月前

起因:我用DFS跑的很慢
(圆圈语句后面有参考代码)

首先讲如果这道题用BFS做的话:
首先要存当前状态;
然后还要bool数组去标记走过的状态
这两个东西用在这题常数很大,所以不用

用DFS做的话:
状态可以用一个全局变量代替,直接进行修改,回溯;
路径直接可以覆盖,标记,无需bool数组(②或像yxc那样)
这两点是DFS的优点

(另外BFS其实都可以用迭代加深去做)

我(之前)用DFS:
每层的状态都记录下来了;③
查找路径用了BFS回溯的方式(自然也要用bool数组)④
就差个queue代替递归存状态了
(写的很像BFS)

另外
转移状态时要利用特殊数组进行统一转移
而不是…⑥
一些没有必要的操作就不用弄⑦

所以要利用好各自优点做题(看状态的存储难易决定迭代加深还是BFS)

(最后我学IDA*觉得这个就像剪枝,BFS也可以用,而A*是有特殊性质的)

string AF,BE,CH,DG;①直接全局变量修改
string C;②直接存路径

void modify(char c)
{
  if(c=='A'||c=='F')
    {
      int len=7;
      if(c=='A')
        {
          char st=AF[0];
          AF.erase(AF.begin());①
          AF+=st;
        }
      else
        {
          char ed=AF[len-1];
          AF.pop_back();
          AF=ed+AF;
        }
      CH[2]=AF[2];DG[2]=AF[4];
      return;
    }
 .......
 }
bool dfs(int res,char last)
{
  if(!res)return true;
  for(int i=0;i<8;++i)
    {
      if(ones[last]=='A'+i)continue;
      modify('A'+i);①
      if(get_f()>res-1)
        {
          modify(ones['A'+i]);
          continue;
        }
      C+='A'+i;②
      if(dfs(res-1,'A'+i))return true;
      modify(ones['A'+i]);①
      C.pop_back();②
    }
  return false;
}
um<string,bool>b[30];④
um<string,char>C[30];④采用BFS回溯找路径(反例)
bool dfs(int res,string AF,string BE,string CH,string DG,char last)③全部状态都记录了(反例)
{
  if(!res)return true;
  for(int i=0;i<8;++i)
    {
      if(ones[last]=='A'+i)continue;
      modify(AF,BE,CH,DG,'A'+i);
      if(get_f(AF,BE,CH,DG)>res-1)
        {
          modify(AF,BE,CH,DG,ones['A'+i]);
          continue;
        }
      string s=AF;s+=BE,s+=CH,s+=DG;
      if(b[t][s])continue;
      C[t][s]='A'+i;b[t][s]=1;④
      if(dfs(res-1,AF,BE,CH,DG,'A'+i))return true;
      b[t][s]=0;④
      modify(AF,BE,CH,DG,ones['A'+i]);
    }
  return false;
}

inline string back(string s,char c)④
{
  string res;
  string AF,BE,CH,DG;
  for(int i=0;i<7;++i)AF+=s[i];for(int i=7;i<14;++i)BE+=s[i];
  for(int i=14;i<21;++i)CH+=s[i];for(int i=21;i<28;++i)DG+=s[i];
  modify(AF,BE,CH,DG,ones[c]);
  res+=AF,res+=BE,res+=CH,res+=DG;
  return res;
}
⑤统一转移
int op[8][7] = {
    {0, 2, 6, 11, 15, 20, 22},
    {1, 3, 8, 12, 17, 21, 23},
    {10, 9, 8, 7, 6, 5, 4},
    {19, 18, 17, 16, 15, 14, 13},
    {23, 21, 17, 12, 8, 3, 1},
    {22, 20, 15, 11, 6, 2, 0},
    {13, 14, 15, 16, 17, 18, 19},
    {4, 5, 6, 7, 8, 9, 10}
};

⑥反例
void modify(char c)
{
  if(c=='A'||c=='F')
    {
      int len=7;
      if(c=='A')
        {
          char st=AF[0];
          AF.erase(AF.begin());①
          AF+=st;
        }
      else
        {
          char ed=AF[len-1];
          AF.pop_back();
          AF=ed+AF;
        }
      CH[2]=AF[2];DG[2]=AF[4];
      return;
    }
 .......
 }

⑦反例
AF=get_AF(),BE=get_BE(),CH=get_CH(),DG=get_DG();
//我分开它们了



s.y.
6个月前
#include<iostream>
#include<queue>
#include<unordered_map>
#pragma GCC optimize("Ofast")
#define um unordered_map
using namespace std;
struct state
{
  string s;
};
um<string,bool>A[3],B[3];
string st,ed;
string opt="0123456789:;<=>?";
int behind[1000];
int n,step,t;
queue<state> qa,qb;
bool flag;
bool f(string s,int maxx,char c)
{
  int res=0,tot=s.size();
  if(c=='A')
    {
      for(int i=0;i<tot-1;++i)
        if(s[i+1]!=s[i]+1)++res;
      if(s[tot-1]!=ed[tot-1])++res;
    }
  else
    {
      for(int i=0;i<tot-1;++i)
        if(s[i+1]!=behind[(int)s[i]])++res;
      if(s[tot-1]!=st[tot-1])++res;
    }
  return (res+2)/3>maxx;
}
void work(queue<state>&q,um<string,bool>&X,um<string,bool>&Y,int maxx)
{
  char c;
  if(step&1)c='A';
  else c='B';
  int note=q.size();
  for(int i=1;i<=note;++i)
    {
      auto k=q.front();q.pop();
      int tot=k.s.size();
      for(int len=1;len<tot;++len)
        for(int l=1;l+len-1<tot;++l)
          {
            int r=l+len-1;
            for(int put=0;put<=l-1;++put)
              {
                string next=k.s;
                int x=put-1,y=l-1;
                while(y<r)next[++x]=k.s[++y];
                y=put-1;
                while(y<l-1)next[++x]=k.s[++y];
                if(f(next,maxx,c))continue;
                X[next]=1;
                if(Y[next])
                  {
                    flag=1;return;
                  }
                q.push({next});
              }
          }
    }
}
void bfs()
{
  if(f(st,4,'A'))
    {
      cout<<"5 or more"<<'\n';
      return;
    }
  for(int i=0;i<n;++i)behind[(int)st[i]]=st[i+1];
  A[t][st]=1,B[t][ed]=1;
  while(!qa.empty())qa.pop();
  while(!qb.empty())qb.pop();
  qa.push({st});qb.push({ed});
  for(int i=1;i<=2;++i)
    {
      ++step;
      work(qa,A[t],B[t],4-i);
      if(flag)break;

      ++step;
      work(qb,B[t],A[t],4-i);
      if(flag)break;
    }
  if(flag)cout<<step<<'\n';
  else cout<<"5 or more"<<'\n';
}
int main()
{
  cin>>t;
  while(t--)
    {
      st="",ed="";
      cin>>n;
      for(int i=1;i<=n;++i)
        {
          int x;cin>>x;
          char c=opt[x];
          ed+=opt[i];st+=c;
        }
      if(st==ed)cout<<"0"<<'\n';
      else step=0,flag=0,bfs();
    }
  return 0;
}