杭电ACM集训队-2020状态监测练习赛(2)

写篇博客纪念一下自闭的一场。(我好弱啊,呜呜呜)

下面题解的思路参考了大佬的博客,贴一下原博客链接,欢迎来%%%

%%%%

数对统计

题目大意:

给定一个序列,求多少对(i,j)满足 $a_i - a_j > a_i + a_j$ (i,j不能相等)

解题思路:

一开始化简后以为看错题了,发现其实就字面意思。化简后得到aj<0,那么对数就是负数的个数*(n-1)

AC代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define ll long long
#define debug(x) cout<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e6+10;
int main()
{
   int n;
   ll ans=0;
   cin>>n;
   for(int i=0;i<n;i++) 
   {
       ll x;
       cin>>x;
       if(x<0) ans++;
   }
   cout<<ans*(n-1)<<endl;
   //system("pause");
   return 0;
}

混合饮料

题目大意:

小明喝一杯刚开始由茶和牛奶等比混合的饮料。给定一个“HM”串,H代表喝掉半杯饮料,再倒入半杯茶。M代表喝掉半杯饮料,再倒入半杯牛奶。每次都混合均匀。按HM串喝,问最后喝掉的牛奶多还是茶多。

解题思路:

按题意模拟即可。double精度够用。(至少在这题的数据是这样的。)

AC代码:

 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
#include<bits/stdc++.h>
#define ll long long
#define debug(x) cout<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e6+10;
int main()
{
   int t;
   cin>>t;
   while(t--)
   {
       int n;
       cin>>n;
       string s;
       cin>>s;
       double nx=0.5,ny=0.5,x=0,y=0;
       for(int i=0;i<n;i++)
       {
           if(s[i]=='H') 
           {
               x+=nx/2;
               y+=ny/2;
               nx/=2,ny/=2;
               nx+=0.5;
           }
           if(s[i]=='M') 
           {
               x+=nx/2;
               y+=ny/2;
               nx/=2,ny/=2;
               ny+=0.5;
           }
       }
       if(x>y) cout<<"H"<<endl;
       else if(x==y) cout<<"HM"<<endl;
       else cout<<"M"<<endl;
   }
   //system("pause");
   return 0;
}

黑暗长廊

题目大意:

小明在一条只有第一盏灯亮的长廊上,当他走到某个位置时,可以打开或关闭这个位置上的灯,每盏灯有可以照亮的范围,小明只能在灯光下行动。求当小明走到第n盏灯,且除了第n盏灯亮,其他灯全灭 所需要的最短路径。如果不能到达,输出 “-1”

解题思路:

不难发现,不管我们选择哪几个灯路过最终到达n灯处,所行的距离始终是3*(xn-x1),也就是来回三趟。

所以我们只要判断能否从起点到达终点,并能否从终点返回起点,如果有一侧不行,就输出-1

判断能否到达,从起点开始,到一个点,每次更新所能到达的最大范围。如果中途出现无法到达下一个点的情况,就表示不行。

AC代码:

 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
#include<bits/stdc++.h>
#define ll long long
#define debug(x) cout<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e6+10;
ll x[maxn],r[maxn];
template<class T>inline void read(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
int main()
{
   int t;
   cin>>t;
   while(t--)
   {    
       int n;
        cin>>n;
        for(int i=1;i<=n;i++) read(x[i]),read(r[i]);
        ll flag=1,mx=x[1]+r[1];
        ll ans=3*(x[n]-x[1]);
        for(int i=1;i<=n-1;i++)
        {
            if(x[i+1]<=mx)
            mx=max(mx,x[i+1]+r[i+1]);
            else 
            {
                flag=0;
                break;
            }
        }
        mx=x[n]-r[n];
        for(int i=n;i>=2;i--)
        {
            if(x[i-1]>=mx)
            mx=min(mx,x[i-1]-r[i-1]);
            else 
            {
                flag=0;
                break;
            }
        }
        if(flag) cout<<ans<<endl;
        else puts("-1");
   }
   //system("pause");
   return 0;
}

咖啡馆

题目大意:

小明要建咖啡馆。已知小明的村庄有n位住户及他们的住址。咖啡馆最多能容纳k位顾客。

问当k分别取1,2,3.......k时,小明建的咖啡馆到这k位住户最短的哈密顿距离之和。

解题思路:

首先回想一个经典问题。

已知n个点,在平面上任意取一点使其到这n个点的哈密顿距离之和最短。

我们首先考虑这n个点在同一条直线上的情况,那么显然当n为奇数的时候,我们肯定取中位点(最中间的那个点)来保证距离之和最短。当n为偶数的情况时,我们取的就是最中间的两个点之间(包括这两个点)的任意一点。

那么从一维拓展到二维,我们只要从所有的x中取一个中位数,所有的y中取一个中位数。这个(X中,Y中)就是答案。值得注意的是,(X中,Y中)这个坐标不一定在这几个n点上,但是我们将所有的x和所有的y两两搭配一定能得到这个点。这也是解这道题的关键。

对于k位顾客,我们不管从这n个住户中挑哪k位,得到的答案点一定是在n个x和y的两两搭配中。

所以我们可以枚举x和y的两两搭配,然后求出n个点到这个点的距离并排序,选取最前面的k位作为顾客就好了。

AC代码:

 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
#include<bits/stdc++.h>
#define ll long long
#define debug(x) cout<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e2+10;
#define int long long
int x[maxn],y[maxn],a[maxn],ans[maxn],sum[maxn];
signed main()
{
   int n,k;
   cin>>n>>k;
   for(int i=1;i<=n;i++)
    cin>>x[i]>>y[i];
    for(int i=0;i<=k;i++) ans[i]=999999999999;//(要足够大,不然过不了)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x0=x[i],y0=y[j];//枚举x和y的两两搭配,答案点必在其中
            set0(a),set0(sum);
            for(int ii=1;ii<=n;ii++) a[ii]=abs(x0-x[ii])+abs(y0-y[ii]);//到n个点的距离
            sort(a+1,a+n+1);
            for(int ii=1;ii<=k;ii++) sum[ii]=sum[ii-1]+a[ii];//前缀和处理
            for(int kk=1;kk<=k;kk++) ans[kk]=min(ans[kk],sum[kk]);
        }
        for(int i=1;i<=k;i++)
        cout<<ans[i]<<endl;
   //system("pause");
   return 0;
}

偶数序列

题目大意:

给定一个整数序列$a_1,a_2,a_3...a_n$和参数k

定义一个序列是k偶数序列,当且仅当对于每个$i(1≤i≤n−k+1)$, $a_i +a_{i+1}...+a_{i+k-1}$都是偶数。

请计算最少修改其中多少个数字可以使得这个序列变成k偶数序列。

解题思路:

要是所有k序列都是偶数,必然会满足$a_1$和$a_{1+k}$, $a_2$和$a_{2+k}$......的奇偶性相同,因为第1个k序列和第2个k序列相差的只有$a_1$和$a_{1+k}$

所以,我们不妨把所有a按模k同余分成k组,比如n=8,k=3时,{$a_1$,$a_4$,$a_7$}为一组,{$a_2$,$a_5$,$a_8$}为一组,

{$a_3$,$a_6$}为一组。这样由上面的结论得同一组的奇偶性一定都一样。

所以,我们只要求得每组数全变成奇数或偶数的最小代价,然后对奇数组的个数计个数cnt,如果cnt位偶数的话,那么就已经满足所有k序列都为偶数了。如果cnt为奇数的话,我们要再让一组奇偶反转,找反转最小代价的一组,加到ans里即可。

AC代码:

 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
#include<bits/stdc++.h>
#define ll long long
#define debug(x) cout<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e6+10;
int a[maxn];
struct node
{
    int x,y;//x 奇数 y偶数
}t[maxn];

int main()
{
   int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        a[i]=a[i]%2;
        if(a[i]==1)t[i%k].x++;
        else t[i%k].y++;
    }
    ll ans=0,cnt=0;
    int mx,minn=inf;
   for(int i=0;i<k;i++)
   {
       if(t[i].x>t[i].y) ans+=t[i].y,cnt++;
       else ans+=t[i].x;
        if(abs(t[i].x-t[i].y)<minn) 
        mx=i,minn=abs(t[i].x-t[i].y);//反转代价最小的
   }
   if(cnt%2==1) 
   {
       ans=ans+abs(t[mx].x-t[mx].y);
   }       
  
  cout<<ans<<endl;
   return 0;
}