哈理工训练赛20190310(组队赛1)

发表于 | 分类于 | 评论数： | 阅读次数：
哈理工训练赛20190310(组队赛1)

A Coffee Break(二分&&筛法)

直接用素数筛法的感觉去筛选即可，就是要注意筛选的过程中如果没有恰好找到的话，那么需要二分搜索下一个位置，否则超时，然后还需要注意如果找了临近的下一个位置那么now一定要变成那个值！！！我比赛的时候因为这个wa了

代码

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
#include <bits/stdc++.h>
using namespace std;
set<long long>st;
map<long long,long long> ans,num;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m,k,cnt=1;
  cin>>n>>m>>k;
  for(int i=1;i<=n;i++)
  cin>>num[i],st.insert(num[i]);
  while(st.size())
  {
    ans[*st.begin()]=cnt;
    int now=*st.begin();
    st.erase(st.begin());
    while(1)
    {
      now+=k+1;
      auto it=st.lower_bound(now);
      if(it==st.end())
      break;
      else
      {
        ans[*it]=cnt;
        now=*it;
        st.erase(it);
      }
    }
    cnt++;
  }
  cout<<cnt-1<<"\n";
  for(int i=1;i<=n;i++)
  cout<<ans[num[i]]<<" ";
}

B Glider (二分)

这个题实际上需要先把空气流层和无重力环境的层两种情况进行都先分出来然后我们会发现只需要将无重力层开始后续加上一个原先的高度即可，也不需要考虑很复杂了。最后就是二分答案，枚举各个起点然后二分无重力层最多的情况，最后答案加上初始高度即可,比赛的时候想复杂了。。。

代码

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
#include <bits/stdc++.h>
using namespace std;
struct node
{
  int l,r;
}num[200005];
int b[200005],c[200005],ans;
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].l>>num[i].r;
  for(int i=1;i<=n;i++)
  {
    b[i]=num[i].r-num[i].l;
    c[i]=num[i].l-num[i-1].r;
    b[i]+=b[i-1];
    c[i]+=c[i-1];
  }
  for(int i=1;i<=n;i++)
  {
    int pos=lower_bound(c+1,c+1+n,c[i]+m)-c;
    ans=max(ans,b[pos-1]-b[i-1]);
  }
  cout<<ans+m;
}

C Bacteria(优先队列||堆)

优先队列大水题当时就是因为没敢用优先队列做，因为想到要pop两个出来感觉有点奇怪，实际上思路还是一样的。这个题大家都做出来了也不多说了

代码

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
#include <bits/stdc++.h>
using namespace std;
priority_queue<long long,vector<long long>,greater<long long> >q;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,t,ans=0;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>t;
    q.push(t);
  }
  while(q.size()!=1)
  {
    long long p1=q.top();q.pop();
    long long p2=q.top();q.pop();
    if(p1==p2)
    q.push(p1+p2);
    else if((p2/p1)%2)
    return cout<<-1,0;
    else
    q.push(p1*2),q.push(p2),ans++;
  }
  cout<<ans;
}

D Masquerade strikes back(暴力)

直接暴力出奇迹，至于如何输出看代码即可，比赛的时候没有想到真要暴力啊都

代码

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 <bits/stdc++.h>
using namespace std;
vector<int> ans1(200005),ans2(200005);
struct node
{
  int sum,id;
}num[200005];
bool cmp(node a,node b)
{
  return a.sum<b.sum;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  for(int i=0;i<n;i++)
  cin>>num[i].sum,num[i].id=i;
  sort(num,num+n,cmp);
  for(int i=0;i<n;i++)
  {
    int l=i,r=0;
    for(int j=i+1;j<n;j++)
    if(num[j].sum==num[i].sum)
    r++;
    else
    break;
    r+=l;
    for(int j=1;j*j<=num[i].sum;j++)
    {
      if(num[i].sum%j==0)
      {
        ans1[num[l].id]=j;
        ans2[num[l].id]=num[i].sum/j;
        l++;
        if(l>r)
        break;
        if(num[i].sum!=j*j)
        {
          ans1[num[l].id]=num[i].sum/j;
          ans2[num[l].id]=j;
          l++;
        }
        if(l>r)
        break;
      }
    }
    if(l<=r)
    return cout<<"NO",0;
    i=r;
  }
  cout<<"YES\n";
  for(int i=0;i<n;i++)
  cout<<ans1[i]<<" "<<ans2[i]<<"\n";
}

E Painting the Fence(set)

这个题真心的不好想也不好做，主要是一个离散化的过程，我们不可能用O(N*N)的时间复杂度做，如何把他们离散化呢？这里开出了set数组然后把这个数出现的位置先塞到set数组里面然后每一次染色都需要把两个位置之间的所有位置删除并且原来的数的位置也会删除。好需要加一个优化要不TLE TEST55就是如果当前删除的这个位置的数已经是被询问要染色过的话，那么他会只剩下一个终点这个时候就不要再循环暴力了，直接输出终点然后结束循环即可

代码

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
#include <bits/stdc++.h>
using namespace std;
set<int> st[300005];
int num[300005],vis[300005],maxn,minn=int(1e9);
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n;
  for(int i=1;i<=n;i++)
  cin>>num[i],st[num[i]].insert(i),maxn=max(maxn,num[i]),minn=min(minn,num[i]);
  cin>>m;
  while(m--)
  {
    int x;
    cin>>x;
    if(vis[x]||st[x].size()<2)
    {
      vis[x]=1;
      continue;
    }
    int l=*(st[x].begin());
    int r=*(st[x].rbegin());
    for(int i=l+1;i<=r-1;i++)
    {
      st[num[i]].erase(i);
      if(vis[num[i]]&&st[num[i]].size()>=1)
      {
        i=*(st[num[i]].begin());
        st[num[i]].erase(i);
      }
    }
    vis[x]=1;
  }
  for(int i=minn;i<=maxn;i++)
  if(vis[i]&&st[i].size()>=2)
  {
    int l=*(st[i].begin());
    int r=*(st[i].rbegin());
    for(int j=l;j<=r;j++)
    num[j]=i;
  }
  for(int i=1;i<=n;i++)
  cout<<num[i]<<" ";
}

F Tickets(筛法)

直接预处理一次然后输出答案即可

代码

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
#include <bits/stdc++.h>
using namespace std;
int bk[66],ans[1000005];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for(int i=0;i<=999999;i++)
  {
    int ttt=0;
    if(i<1000)
    {
      int te=i;
      int sum=0;
      while(te)
      {
        sum+=te%10;
        te/=10;
      }
      bk[sum]++;
      for(int j=0;j<sum;j++)
      ttt+=bk[j];
      ans[i]=ttt;
    }
    else
    {
      int te=i,cnt=0;
      int sum1=0,sum2=0;
      while(te)
      {
        cnt++;
        if(cnt<=3)
        sum1+=te%10;
        else
        sum2+=te%10;
        te/=10;
      }
      bk[abs(sum1-sum2)]++;
      for(int j=0;j<abs(sum1-sum2);j++)
      ttt+=bk[j];
      ans[i]=ttt;
    }
    //cout<<ans[i]<<"\n";
  }
  int t;
  cin>>t;
  while(t--)
  {
    string a;
    cin>>a;
    stringstream tt;
    tt<<a;
    int te;
    tt>>te;
    cout<<ans[te]<<"\n";
  }
}

G Tree Reconstruction(贪心&&思维)

这个东西也是不好做，这里有一种简单的构造方法。首先判断如果最后一个节点不是最大值n的话那么肯定是不行的(这个地方确实是有点果断但是还是对的。。。)也就是说右边的节点必须得是n输入的时候否则就NO即可，然后我们升序排序把第一个最小的当成这个树的根，然后判断下一个小的数当前有两步
1.如果当前的数不等于上一个数，那么把这个数也放进答案同时set维护的值去掉这个数
2.否则的话看一看set顶端的最小的数是不是比当前的数小，如果是set顶端进入答案否则输出NO

代码

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 num[6666],ans[6666];
set<int> st;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,x;
  cin>>n;
  for(int i=1;i<=n-1;i++)
  {
    cin>>num[i]>>x;
    st.insert(i);
    if(x!=n)
    return cout<<"NO",0;
  }
  st.insert(n);
  sort(num+1,num+n);
  ans[0]=num[1];
  st.erase(num[1]);
  for(int i=2;i<=n;i++)
  {
    if(num[i]!=num[i-1])
    {
      ans[i-1]=num[i];
      st.erase(num[i]);
    }
    else
    {
      if(*st.begin()<num[i])
      {
        ans[i-1]=*st.begin();
        st.erase(st.begin());
      }
      else
      return cout<<"NO",0;
    }
  }
  ans[n-1]=n;
  cout<<"YES\n";
  for(int i=0;i<n-1;i++)
  cout<<ans[i]<<" "<<ans[i+1]<<"\n";
}

H Theater Square(数学)

好像都会做直接放码了

代码(昊哥版本)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int arr[200010];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m,x1,y1,x2,y2;
  cin>>n>>m>>x1>>y1>>x2>>y2;
  int tn = x2-x1+1;
  n-=tn;
  int m1 = y1-1;
  int m2 = m-y2;
  int ans = ((m1%2)+(m2%2))*tn + (m%2)*n;
  if(ans%2 == 1) ans+=1;
  ans/=2;
  cout<<ans;
}

I Heist(语法基础)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,maxn=-1,minn=int(1e9)+100;
  cin>>n;
  for(int i=0;i<n;i++)
  {
    int t;
    cin>>t;
    maxn=max(maxn,t);
    minn=min(minn,t);
  }
  cout<<maxn-minn+1-n;
}

J Buying a TV Set(数学)

代码(凯哥版本)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    long long int a, b, x, y, t;
    cin >> a >> b >> x >> y;
    t = __gcd(x, y);
    x = x / t;
    y = y / t;
    long long int ans;
    a = a / x;
    b = b / y;
    ans = min(a, b);
    cout << ans << endl;
    return 0;
}

K Medians and Partition(数学&&规律)

反正直接放lsr大佬的代码就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m,ans=0;
  cin>>n>>m;
  while(n--)
  {
    int t;
    cin>>t;
    if(t>=m)
    ans++;
    else
    ans--;
  }
  if(ans<0)
  ans=0;
  cout<<ans;
}
就算是一分钱，也是对作者极大的支持
------ 本文结束 ------

版权声明

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%