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);
}