排位一和二记录

博主： zzsqwq
发布时间：2020 年 08 月 17 日
2531次浏览
3 条评论
976字数
分类： ACM

Day 1

A. 兔子的区间密码

题意

给定一个区间$[L,R]$ ，求从这个区间任意取两个整数(可以相同)，两者异或后能得到的最大值是多少？

思路

首先我们想一下特例，当 $L==R$ 的时候，那么只能是L和他自己异或，就是0了。

然后可以分两部分来想，设区间端点 $L,R$ 的二进制最高位，从右往左开始数位置分别为 $p_1,p_2$

如果 $p_1 \neq p_2 $ ，那么必然是 $p_1 < p_2$ ，我们很容易发现这时候肯定可以取到 $2^{p_2-1}-1 和 2^{p_2-1}$ ，那么两者异或一下就是最大的，答案为 $2^{p_2}$
如果 $p_1 == p_2$ ，那么我们可以转化为更小规模的问题，就是区间为 $[L-2^{p_1-1},R-2^{p_1-1}]$ 。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

#define ll long long 

ll l,r;
int t;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ll l,r;
        scanf("%lld%lld",&l,&r);
        if(l == r)
        {
            printf("0\n");
        }
        else
        {
            int p1 = log2(l),p2 = log2(r);
            while(p1 == p2 && l != 0)
            {
                l^=(1LL<<p1);
                r^=(1LL<<p1);
                p1 = log2(l),p2=log2(r);
            }
            printf("%lld\n",((1LL<<(p2+1))-1));
        }
    }
    return 0;

}

B. 猴子排序的期望

题意

有 $N$ 张卡片，每个上面都写着一个大写字母，问随便扔一次这 $N$ 张的卡片就已经按字典序排好的概率，答案用分字为1的形如 $1/x$ 的形式表示。$( 1<N < 100)$

思路

这题很显然是道数学排列组合题，我们设每个字母重复出现的次数为 $p[i]$ ，好比字母为$A$的卡片出现了两次，那么就 $p['A']$ 为2。

那么答案就是如下

$$ ans = \frac{N!}{\Pi_{i='A'}^{i='Z'}(p[i]!)} $$

这题主要难点大概是在高精，因为可能会涉及到 $100!$ 这种丧心病狂的东西，所以就用笨比的方法写了一发python。~~其实是高级的算法不会用python写，C++乘法的高精忘掉了~~。

代码实现

n = int(input())
s = input()
s[0:n:1]
ans = 1
for i in range(1,n+1):
    ans = ans*i
for i in range(0,n):
    count = 0
    for j in range(i,n):
        if s[i] == s[j]:
          count = count + 1
    if count >= 0:
        ans = ans//count  #这里本来//写成了/,连WA3发
print("1/",end="")
print(int(ans))

Day 2

A. 愤怒的巨巨

题意

已知香蕉的次品率为 $p(0\le p\le 1)$ ，如果想要买到好香蕉则买香蕉个数的期望值是多少。如果买不到好香蕉，输出”Sorrry,JuJu!”(忽略双引号)。否则输出期望值的最简分数形式：c/d. $p$ 的最多位数为6。

思路

首先理解一下题意，好比次品率 $p$ 为0.5，则期望的个数为2个。如果次品率 $p$ 为 0.25，则可以说平均买四个有一个次品，那么最少需要的买的个数其实是 $3/4$ 。

再者特判一下 $p == 0$ 以及 $p==1$ 的情况，分别输出 1/1 和 Sorrry,JuJu! 。

然后其实可以看一下非次品率 $k = 1-p$ ，然后其实就是一个最大公约数问题了。只需要把 $k$ 转换成分数形式，然后用最大公约数约分一下，再取一个倒数即可。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
 
using namespace std;
 
char str[100];
int k = 0;
int mod = 1;
bool flag = false;
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int main()
{
    scanf("%s",str);
    int len = strlen(str);
    if(str[0] == '0')
    {
        for(int i=2;i<len;i++)
        {
            if(str[i] != '0') flag = true;
        }
        if(flag == false)
        {
            printf("1/1");
            return 0;
        }
    }
    if(str[0] == '1')
    {
        printf("Sorrry,JuJu!");
        return 0;
    }
    for(int i=2;i<len;i++)
    {
        k = k*10+str[i]-'0';
        mod *= 10;
    }
    int m = mod - k;
    int p = gcd(m,mod);
    printf("%d/%d",mod/p,m/p);
    return 0;
}

B. 兔子的逆序对

题意

给定一个区间 $[L,R]$ ，然后给出 $m$ 次翻转操作，通过给出子区间左右端点，反转该区间。每翻转一次，要求给出区间 $[L,R]$ 逆序对的奇偶性，如果是奇数，输出 dislike ，如果是偶数，输出 like 。

思路

首先用归并 / 树状数组的方法，求出来区间 $[L,R]$ 的逆序对 $ans$。

然后我们考虑每一次翻转带来的影响。我们考虑一个子区间 $[l,r]$ ，设该区间逆序对为 $x$ ，那么反转后该区间的逆序对为 $C_n^2 -x$ 。翻转区间 $[l,r]$ 导致答案 $ans = ans + C_n^2 -x - x = ans + C_n^2-2x$

因为只需要奇偶性，那么 $2x$ 需要考虑，那么就每次看看 $C_n^2$ 的奇偶性即可。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
 
using namespace std;
 
#define lowbit(x) (x)&(-x)
typedef struct Node
{
    int val; // value
    int pos; //postion
}node;
int cmp(node a,node b)
{
    return a.val<b.val;
}
const int maxn = 1e5+5;
const int maxm = 2e6+5;
node num[maxn];
int tree[maxm];
int n,m;
int l,r;
 
void add(int x)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        tree[i]++;
    }
}
int find(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        sum+=tree[i];
    }
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i].val);
        num[i].pos=i;
    }
    sort(num+1,num+n+1,cmp);
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        ans+=find(num[i].pos);
        add(num[i].pos);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        int k = ((r-l+1)*(r-l))>>1;
        if(k&1)
        {
            if(ans%2 == 0)
            {
                printf("dislike\n");
                ans++;
            }
            else
            {
                printf("like\n");
                ans++;
            }
        }
        else
        {
            if(ans%2 == 0)
            {
                printf("like\n");
            }
            else
            {
                printf("dislike\n");
            }
        }
    }
}

C. Butterfly

题意

这题描述起来有点难，还是直接点链接去看比较好。

大概就是给定一个由 X 和 O 构成的$n\times m$ 的矩阵，让你找出里面由 X 构成的蝴蝶的最大对角线长度。

思路

这题第一时间让我想到了我 2020/2/12 写的dp练习中的创意吃鱼法。

一开始想要考虑从中心开始考虑，但是需要维护的东西有点多，而且周围的判别不好判。因此可以考虑从右上/右下/左上/左下 这四个位置考虑，我这里是从左下考虑的。设我们要求的答案为 $ans$ 。

考虑维护三个数组，看 X 向上延伸，左上延伸，右上延伸的长度。所以我们依次遍历矩阵中的每一个元素，判定他是否可以作为蝴蝶的左下角，首先取一个向上延伸和右上延伸的最小值 $p$，然后从 $p$ 到 $ans$ 遍历，每次判定一下该答案是否合法，判定的话无非是从右下角判定一下就行，比较简单。如果答案合法，那么更新 $ans$。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
 
using namespace std;
 
const int maxn = 2005;
int lr[maxn][maxn],rr[maxn][maxn],str[maxn][maxn]; //分别为按左上、右上，向上延伸
char x;
int n,m;
int ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>x;
            if(x == 'X')
            {
                lr[i][j] = lr[i-1][j-1] + 1;
                rr[i][j] = rr[i-1][j+1] + 1;
                str[i][j] = str[i-1][j] + 1;
                ans = 1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int p = min(str[i][j],rr[i][j]);
            for(int k = p;k>ans;k--)
            {
                if(k&1)
                {
                    if(str[i][j+k-1]>=k && lr[i][j+k-1]>=k) ans = max(ans,k);
                }
            }
        }
    }
    printf("%d",ans);
}

最后修改：2021 年 02 月 20 日 12 : 16 AM

如果觉得我的文章对你有用，请随意赞赏

3 条评论

zyq
August 18th, 2020 at 12:07 am
你是柴米油盐
清晨白米稀饭
你懂得四季变换
懂得长久为伴
眼有五彩斑斓
让我留恋
让我葬身于你的
知寒问暖
我是春去秋来
只会饮酒寻欢
看过草长莺飞
只知情长纸短
每天悱恻难眠
想着鸿鹄之言
然后自命不凡
自以冯唐恨晚
如今良辰好景你却此去经年
没了痛苦深渊
我不再隔江唱晚
你却散落人间
寻不到灯火阑珊
我想清晨温酒
与你看日出夜暖
我原是道貌岸然
经你似水流年
你陪我日出日落
为我驱寒问暖
愿你百岁无忧
肆无忌惮
管他沧海桑田
你仍是四月人间
你陪我走过三年
看过腊月十三
看过惊蛰春雨
经过阴晴月满
我却踏雪寻梅
然后英雄气短
不见你凄楚可怜
辗转难眠
如今良辰好景你却此去经年
没了痛苦深渊
我不再隔江唱晚
你却散落人间
寻不到灯火阑珊
我想清晨温酒
与你看日出夜暖
我原是道貌岸然
经你似水流年
你陪我日出日落
为我驱寒问暖
愿你百岁无忧
肆无忌惮
管他沧海桑田
你仍是四月人间
而今良辰好景
却是撒满天边
我想你携酒踏月
共享伯牙绝弦
共赴高山流水
死后齐挂东南
亦是万物生长
长出昙花永现
我不再烈酒肝胆
不再斗米而嫌
褪去满身疲倦
平凡而勇敢
而你
白衣轻叹
小楼装轩
淡妆浓抹
在水一边
你仍是小桥河畔
我亦是此间少年
共看风花雪月
与你西窗共剪
笑看人世间
----《亦是此间少年》枯木逢春
回复
1. zzsqwq
  August 18th, 2020 at 12:11 am
  
  @zyq
  
  tql!!!
  
  回复
JJHQAQ
August 17th, 2020 at 10:19 pm

TQL!!!!!!

回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

耶耶耶
small_5发布的固件现在最新的都搜不到了=。=博主能提供最新的吗
菜鸟
您好！感谢您的教程，发现了一些错误：在最后命令行创建快捷方式中...
老赵
已经搞定了，谢谢大佬，最后换了树莓派os，按照你的方法安装成功...
老赵
大佬能不能帮我看一下这个是什么意思？安装不起来啊。root@u...
老赵
感谢

排位一和二记录

zzsqwq • 2020 年 08 月 17 日

Day 1

A. 兔子的区间密码

题意

给定一个区间$[L,R]$ ，求从这个区间任意取两个整数(可以相同)，两者异或后能得到的最大值是多少？

思路

首先我们想一下特例，当 $L==R$ 的时候，那么只能是L和他自己异或，就是0了。

然后可以分两部分来想，设区间端点 $L,R$ 的二进制最高位，从右往左开始数位置分别为 $p_1,p_2$

如果 $p_1 \neq p_2 $ ，那么必然是 $p_1 < p_2$ ，我们很容易发现这时候肯定可以取到 $2^{p_2-1}-1 和 2^{p_2-1}$ ，那么两者异或一下就是最大的，答案为 $2^{p_2}$
如果 $p_1 == p_2$ ，那么我们可以转化为更小规模的问题，就是区间为 $[L-2^{p_1-1},R-2^{p_1-1}]$ 。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

#define ll long long 

ll l,r;
int t;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ll l,r;
        scanf("%lld%lld",&l,&r);
        if(l == r)
        {
            printf("0\n");
        }
        else
        {
            int p1 = log2(l),p2 = log2(r);
            while(p1 == p2 && l != 0)
            {
                l^=(1LL<<p1);
                r^=(1LL<<p1);
                p1 = log2(l),p2=log2(r);
            }
            printf("%lld\n",((1LL<<(p2+1))-1));
        }
    }
    return 0;

}

B. 猴子排序的期望

题意

思路

这题很显然是道数学排列组合题，我们设每个字母重复出现的次数为 $p[i]$ ，好比字母为$A$的卡片出现了两次，那么就 $p['A']$ 为2。

那么答案就是如下

$$ ans = \frac{N!}{\Pi_{i='A'}^{i='Z'}(p[i]!)} $$

代码实现

n = int(input())
s = input()
s[0:n:1]
ans = 1
for i in range(1,n+1):
    ans = ans*i
for i in range(0,n):
    count = 0
    for j in range(i,n):
        if s[i] == s[j]:
          count = count + 1
    if count >= 0:
        ans = ans//count  #这里本来//写成了/,连WA3发
print("1/",end="")
print(int(ans))

Day 2

A. 愤怒的巨巨

题意

思路

再者特判一下 $p == 0$ 以及 $p==1$ 的情况，分别输出 1/1 和 Sorrry,JuJu! 。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
 
using namespace std;
 
char str[100];
int k = 0;
int mod = 1;
bool flag = false;
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int main()
{
    scanf("%s",str);
    int len = strlen(str);
    if(str[0] == '0')
    {
        for(int i=2;i<len;i++)
        {
            if(str[i] != '0') flag = true;
        }
        if(flag == false)
        {
            printf("1/1");
            return 0;
        }
    }
    if(str[0] == '1')
    {
        printf("Sorrry,JuJu!");
        return 0;
    }
    for(int i=2;i<len;i++)
    {
        k = k*10+str[i]-'0';
        mod *= 10;
    }
    int m = mod - k;
    int p = gcd(m,mod);
    printf("%d/%d",mod/p,m/p);
    return 0;
}

B. 兔子的逆序对

题意

思路

首先用归并 / 树状数组的方法，求出来区间 $[L,R]$ 的逆序对 $ans$。

因为只需要奇偶性，那么 $2x$ 需要考虑，那么就每次看看 $C_n^2$ 的奇偶性即可。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
 
using namespace std;
 
#define lowbit(x) (x)&(-x)
typedef struct Node
{
    int val; // value
    int pos; //postion
}node;
int cmp(node a,node b)
{
    return a.val<b.val;
}
const int maxn = 1e5+5;
const int maxm = 2e6+5;
node num[maxn];
int tree[maxm];
int n,m;
int l,r;
 
void add(int x)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        tree[i]++;
    }
}
int find(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        sum+=tree[i];
    }
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i].val);
        num[i].pos=i;
    }
    sort(num+1,num+n+1,cmp);
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        ans+=find(num[i].pos);
        add(num[i].pos);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        int k = ((r-l+1)*(r-l))>>1;
        if(k&1)
        {
            if(ans%2 == 0)
            {
                printf("dislike\n");
                ans++;
            }
            else
            {
                printf("like\n");
                ans++;
            }
        }
        else
        {
            if(ans%2 == 0)
            {
                printf("like\n");
            }
            else
            {
                printf("dislike\n");
            }
        }
    }
}

C. Butterfly

题意

这题描述起来有点难，还是直接点链接去看比较好。

大概就是给定一个由 X 和 O 构成的$n\times m$ 的矩阵，让你找出里面由 X 构成的蝴蝶的最大对角线长度。

思路

这题第一时间让我想到了我 2020/2/12 写的dp练习中的创意吃鱼法。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
 
using namespace std;
 
const int maxn = 2005;
int lr[maxn][maxn],rr[maxn][maxn],str[maxn][maxn]; //分别为按左上、右上，向上延伸
char x;
int n,m;
int ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>x;
            if(x == 'X')
            {
                lr[i][j] = lr[i-1][j-1] + 1;
                rr[i][j] = rr[i-1][j+1] + 1;
                str[i][j] = str[i-1][j] + 1;
                ans = 1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int p = min(str[i][j],rr[i][j]);
            for(int k = p;k>ans;k--)
            {
                if(k&1)
                {
                    if(str[i][j+k-1]>=k && lr[i][j+k-1]>=k) ans = max(ans,k);
                }
            }
        }
    }
    printf("%d",ans);
}

Day 1

A. 兔子的区间密码

题意

思路

代码实现

B. 猴子排序的期望

题意

思路

代码实现

Day 2

A. 愤怒的巨巨

题意

思路

代码实现

B. 兔子的逆序对

题意

思路

代码实现

C. Butterfly

题意

思路

代码实现

3 条评论

发表评论 取消回复

排位一和二记录

Day 1

A. 兔子的区间密码

题意

思路

代码实现

B. 猴子排序的期望

题意

思路

代码实现

Day 2

A. 愤怒的巨巨

题意

思路

代码实现

B. 兔子的逆序对

题意

思路

代码实现

C. Butterfly

题意

思路

代码实现

发表评论取消回复