哈理工训练赛20190304(简略题解)

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
简略版题解

A - Watto and Mechanism(trie&&dfs)

胡乱分析

先创建字典树，然后每个rt对应的字母一个一个dfs枚举，最终得到答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
string a;
int tot,trie[666666][6],bk[666666],len,f;
void insert(string a)
{
  int rt=0;
  for(int i=0;i<a.size();i++)
  {
    int id=a[i]-'a';
    if(!trie[rt][id])
    trie[rt][id]=++tot;
    rt=trie[rt][id];
  }
  bk[rt]=1;
}
int dfs(int pos,int rt)
{
  if(pos==len)
  {
    if(bk[rt]&&!f)
    return 1;
    else
    return 0;
  }
  int id=a[pos]-'a';
  for(int i=0;i<3;i++)
  {
    if(trie[rt][i])
    {
      if(i==id)
      {
        if(dfs(pos+1,trie[rt][i]))
        return 1;
      }
      else if(f)
      {
        f=0;
        if(dfs(pos+1,trie[rt][i]))
        return 1;
        f=1;
      }
    }
  }
  return 0;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  while(n--)
  {
    cin>>a;
    insert(a);
  }
  while(m--)
  {
    cin>>a;
    f=1;
    len=a.size();
    if(dfs(0,0))
    cout<<"YES\n";
    else
    cout<<"NO\n";
  }
}

B - Infinite Inversions

C - Pashmak and Parmida’s problem (逆序对)

胡乱分析

树状数组求逆序对，需要离散化一下这个式子然后倒着装，至于怎么装我也不知道题解怎么想出来的，不过确实挺巧妙的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
int n,c[1000005],pre[1000005],ed[1000005],num[1000005];
unordered_map<int,int> bk1,bk2;
int lowb(int x)
{
  return x&(-x);
}
void add(int x)
{
  for(int i=x;i<=n;i+=lowb(i))
  c[i]++;
}
int sum(int x)
{
  int ans=0;
  for(int i=x;i;i-=lowb(i))
  ans+=c[i];
  return ans;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long ans=0;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>num[i];
    bk1[num[i]]++;
    pre[i]=bk1[num[i]];
  }
  for(int i=n;i;i--)
  {
    bk2[num[i]]++;
    ed[i]=bk2[num[i]];
  }
  for(int i=n;i;i--)
  {
    ans+=sum(pre[i]-1);
    add(ed[i]);
  }
  cout<<ans;
}

D - Balanced Lineup (RMQ)

胡乱分析

ST表和线段树都可过，ST表快一点

代码(ST表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cmath>
using namespace std;
int ans1[666666][25],ans2[666666][25];
int sum1(int l,int r)
{
  int k=log2(r-l+1);
  return max(ans1[l][k],ans1[r-(1<<k)+1][k]);
}
int sum2(int l,int r)
{
  int k=log2(r-l+1);
  return min(ans2[l][k],ans2[r-(1<<k)+1][k]);
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  cin>>ans1[i][0],ans2[i][0]=ans1[i][0];
  for(int j=1;j<=21;j++)
  for(int i=1;i+(1<<j)-1<=n;i++)
  ans1[i][j]=max(ans1[i][j-1],ans1[i+(1<<j-1)][j-1]);
  for(int j=1;j<=21;j++)
  for(int i=1;i+(1<<j)-1<=n;i++)
  ans2[i][j]=min(ans2[i][j-1],ans2[i+(1<<j-1)][j-1]);
  while(m--)
  {
    int l,r;
    cin>>l>>r;
    cout<<sum1(l,r)-sum2(l,r)<<"\n";
  }
}

代码(线段树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;
struct node
{
  int l,r,maxn,minn;
}t[666666];
int num[666666];
void build(int p,int l,int r)
{
  t[p].l=l;t[p].r=r;
  if(l==r)
  {
    t[p].maxn=num[l];
    t[p].minn=num[l];
    return;
  }
  int mid=(t[p].l+t[p].r)>>1;
  build(2*p,l,mid);
  build(2*p+1,mid+1,r);
  t[p].maxn=max(t[2*p].maxn,t[2*p+1].maxn);
  t[p].minn=min(t[2*p].minn,t[2*p+1].minn);
}
int Max(int p,int x,int y)
{
  if(t[p].l>=x&&t[p].r<=y)
  return t[p].maxn;
  int mid=(t[p].l+t[p].r)>>1;
  int maxn=-1;
  if(x<=mid)
  maxn=max(maxn,Max(2*p,x,y));
  if(y>mid)
  maxn=max(maxn,Max(2*p+1,x,y));
  return maxn;
}
int Min(int p,int x,int y)
{
  if(t[p].l>=x&&t[p].r<=y)
  return t[p].minn;
  int mid=(t[p].l+t[p].r)>>1;
  int minn=int(1e9)+7;
  if(x<=mid)
  minn=min(minn,Min(2*p,x,y));
  if(y>mid)
  minn=min(minn,Min(2*p+1,x,y));
  return minn;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  cin>>num[i];
  build(1,1,n);
  while(m--)
  {
    int l,r;
    cin>>l>>r;
    cout<<Max(1,l,r)-Min(1,l,r)<<"\n";
  }
}

E - Snowflake Snow Snowflakes(哈希)

胡乱分析

这里用哈希，按照字符串模大质数加和的哈希，因为我们要把可能相同的放到一起去寻找，所以这样可以建立一个哈希表然后把可能相同的单独拿出来进行旋转比较的哈希，这里开了读入挂能够快一点读入，这题常数有点大

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
vector<int> hs[1000006];
int num[200005][10];
int mod=999983;
typedef long long ll;
inline ll read()
{
  ll x=0,f=1;
  char c=getchar();
  for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
  for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+c-'0';
  return f?x:-x;
}
int check(int a,int b)
{
  for(int i=0;i<6;i++)
  {
    if(num[a][0]==num[b][i]&&num[a][1]==num[b][(i+1)%6]&&num[a][2]==num[b][(i+2)%6]&&num[a][3]==num[b][(i+3)%6]&&num[a][4]==num[b][(i+4)%6]&&num[a][5]==num[b][(i+5)%6])
    return 1;
    if(num[a][0]==num[b][i]&&num[a][1]==num[b][(i+5)%6]&&num[a][2]==num[b][(i+4)%6]&&num[a][3]==num[b][(i+3)%6]&&num[a][4]==num[b][(i+2)%6]&&num[a][5]==num[b][(i+1)%6])
    return 1;
  }
  return 0;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  n=read();
  for(int i=1;i<=n;i++)
  {
    long long ans=0;
    for(int j=0;j<6;j++)
    {
      num[i][j]=read();
      ans=(ans%mod+num[i][j]%mod)%mod;
    }
    int len=hs[ans].size();
    if(len==0)
    hs[ans].push_back(i);
    else
    {
      for(int j=0;j<len;j++)
      {
        if(check(i,hs[ans][j]))
        return cout<<"Twin snowflakes found.",0;
      }
      hs[ans].push_back(i);
    }
  }
  cout<<"No two snowflakes are alike.";
}

F - 敌兵布阵 (树状数组)

胡乱分析

树状数组和线段树都可过，但是树状数组能够写少一点，对于这种单点修改的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
long long n,ans[50005];
int lowb(int x)
{
  return x&(-x);
}
void add(int num,int sum)
{
  for(int i=num;i<=n;i+=lowb(i))
  ans[i]+=sum;
}
int sum(int x)
{
  long long sum=0;
  for(int i=x;i;i-=lowb(i))
  sum+=ans[i];
  return sum;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t,cnt=0;
  cin>>t;
  while(t--)
  {
    cin>>n;
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;i++)
    {
      int te;
      cin>>te;
      add(i,te);
    }
    string a;
    cout<<"Case "<<++cnt<<":\n";
    while(cin>>a)
    {
      if(a[0]=='Q')
      {
        int l,r;
        cin>>l>>r;
        cout<<sum(r)-sum(l-1)<<"\n";
      }
      else if(a[0]=='A')
      {
        int num,sum;
        cin>>num>>sum;
        add(num,sum);
      }
      else if(a[0]=='S')
      {
        int num,sum;
        cin>>num>>sum;
        add(num,-sum);
      }
      else if(a[0]=='E')
      break;
    }
  }
}

G - Oulipo(KMP)

胡乱分析

裸题KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstring>
using namespace std;
int nex[1000100];
char a[1000100],b[1000100];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin>>t;
  while(t--)
  {
    int j=0,sum=0;
    cin>>a+1>>b+1;
    int lena=strlen(a+1);
    int lenb=strlen(b+1);
    memset(nex,0,sizeof(nex));
    for(int i=2;i<=lena;i++)
    {
      while(j&&a[i]!=a[j+1])
      j=nex[j];
      if(a[i]==a[j+1])
      j++;
      nex[i]=j;
    }
    j=0;
    for(int i=1;i<=lenb;i++)
    {
      while(j&&b[i]!=a[j+1])
      j=nex[j];
      if(b[i]==a[j+1])
      j++;
      if(j==lena)
      sum++,j=nex[j];
    }
    cout<<sum<<"\n";
  }
}

H - Power Strings(next数组应用)

胡乱分析

记住len|(len-next[len])时len/(len-next[len])能求最小长度循环串的循环长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstring>
using namespace std;
int nex[1000100];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string a;
  while(cin>>a)
  {
    a.insert(0,"#");
    if(a[1]=='.')
    break;
    int j=0;
    int len=a.size()-1;
    if(len==0)
    {
      cout<<0<<"\n";
      continue;
    }
    for(int i=2;i<=len;i++)
    {
      while(j&&a[i]!=a[j+1])
      j=nex[j];
      if(a[i]==a[j+1])
      j++;
      nex[i]=j;
    }
    if(len%(len-nex[len])==0)
    cout<<len/(len-nex[len])<<"\n";
    else
    cout<<1<<"\n";
  }
}

I - Period (next数组应用)

胡乱分析

同上一个题，不过就是最后求循环次数变成了边线性扫描边求

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstring>
using namespace std;
int nex[1000100];
char a[1000100],b[1000100];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t,cnt=0;
  while(cin>>t)
  {
    if(t==0)
    break;
    cin>>a+1;
    int len=strlen(a+1);
    memset(nex,0,sizeof(nex));
    int j=0;
    for(int i=2;i<=len;i++)
    {
      while(j&&a[i]!=a[j+1])
      j=nex[j];
      if(a[i]==a[j+1])
      j++;
      nex[i]=j;
    }
    cout<<"Test case #"<<++cnt<<"\n";
    for(int i=2;i<=len;i++)
    if(i%(i-nex[i])==0&&i/(i-nex[i])>1)
    cout<<i<<" "<<i/(i-nex[i])<<"\n";
    cout<<"\n";
  }
}

J - Hat’s Words (trie)

胡乱分析

这题网上说最多每个单词只有20个字符所以map可以水过，但是正解还是trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
string st[66666];
int bk[6666666],tot,trie[66666][66],p;
void insert(string a)
{
  int rt=0;
  for(int i=0;i<a.size();i++)
  {
    int id=a[i]-'a';
    if(!trie[rt][id])
    trie[rt][id]=++tot;
    rt=trie[rt][id];
  }
  bk[rt]=1;
}
int search(string a)
{
  int rt=0;
  for(int i=0;i<a.size();i++)
  {
    int id=a[i]-'a';
    if(!trie[rt][id])
    return 0;
    rt=trie[rt][id];
  }
  return bk[rt];
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string a;
  while(cin>>a)
  st[p++]=a,insert(a);
  for(int i=0;i<p;i++)
  for(int j=0;j<st[i].size();j++)
  {
    string a=st[i].substr(0,j);
    string b=st[i].substr(j,st[i].size()-1);
    if(search(a)&&search(b))
    {
      cout<<st[i]<<"\n";
      break;
    }
  }
}

K - Black Box (堆)

胡乱分析

创建一个大根堆和一个小根堆，大根堆维护前k-1个的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <queue>
using namespace std;
int num[666666];
priority_queue<int> big;
priority_queue<int,vector<int>,greater<int> >small;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  cin>>num[i];
  int now=1;
  while(m--)
  {
    int t;
    cin>>t;
    while(now<=t)
    {
      small.push(num[now]);
      if(!big.empty()&&small.top()<big.top())
      {
        int t1=big.top();
        int t2=small.top();
        big.pop();
        small.pop();
        big.push(t2);
        small.push(t1);
      }
      now++;
    }
    cout<<small.top()<<"\n";
    big.push(small.top());
    small.pop();
  }
}

L - 搬果子 (堆)

胡乱分析

放进去自己排序这样快，注意直接排序求解会可能合并的时候合出来一个大的还需要再排序，所以直接用堆即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  while(cin>>n)
  {
    priority_queue<int> q;
    while(n--)
    {
      int te;
      cin>>te;
      q.push(-te);
    }
    int sum=0;
    while(q.size()>1)
    {
      int p1=q.top();
      q.pop();
      int p2=q.top();
      q.pop();
      sum+=-(p1+p2);
      q.push(p1+p2);
      //cout<<sum<<"\n";
    }
    cout<<sum<<"\n";
  }
}
就算是一分钱，也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。
本文首发于baccano 博客（ http://baccano.fun ），版权所有，侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆？---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%