链接：http://codeforces.com/contest/1062
A - Prank - [二分]
题意：
给出长度为 $n(1 \le n \le 100)$ 的数组 $a[1 \sim n]$，且满足 $1 \le a[1] < a[2] < \cdots < a[n] \le 1000$。现在JATC要擦掉其中一段连续的数字，但是要求能够通过剩余的其他数字，推断出擦掉的数字是什么。求JATC能擦掉的最长长度。
题解：
其实 $O(n)$ 就可以求出能擦掉的最长长度，但是因为 $n$ 比较小，懒得考虑太多，直接二分吧……
二分能擦掉的长度，对于固定的长度，$O(n)$ 枚举始末点判断能否擦除即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int n,a[maxn];
bool judge(int k)
{
for(int i=,j=i+k-;j<=n;i++,j++) {
if(a[j+]-a[i-]==k+) return ;
}
return ;
}
int main()
{
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
a[]=, a[n+]=;
int l=, r=n;
while(l<r)
{
int mid=(l+r+)/;
if(judge(mid)) l=mid;
else r=mid-;
}
cout<<l<<endl;
}
B - Math - [数学题]
题意：
给出一个正整数 $n(1 \le n \le 1e6)$，你现在可以对 $n$ 进行任意多次乘以正整数 $x$ 或者开方（当结果为整数时才允许开方）操作。
求结果最小为多少，达到这个结果最少进行多少次操作。
题解：
分解质因数 $n = {p_1}^{a_1}{p_2}^{a_2} \cdots {p_k}^{a_k}$，显然最后结果只能是 $p_1 p_2 \cdots p_k$，那么如何才能得到 $p_1 p_2 \cdots p_k$？
找到 $\max(a_i)$，求得比小于它的最小 $2^x$，这样一来先做一次乘法把 $n$ 乘到 ${p_1}^{2^x}{p_2}^{2^x} \cdots {p_k}^{2^x}$，然后做 $2^x$ 次开方操作即可得到 $p_1 p_2 \cdots p_k$。因此最少 $x+1$ 次操作。
（当然，还有一些数字本身就是最小结果，这些另作判断即可。）
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n;
pair<int,int> solve(int n)
{
if(n<=) return make_pair(n,);
int res=,mx=, mn=;
for(int i=;i*i<=n;i++)
{
if(n%i==)
{
res*=i;
int cnt=;
while(n%i==) n/=i, cnt++;
mx=max(cnt,mx);
mn=min(cnt,mn);
}
}
if(n>) res*=n, mx=max(,mx), mn=min(,mn);
int t=ceil(log2(mx))+1e-;
if(mn==mx && (<<t)==mx) return make_pair(res,t);
else return make_pair(res,t+);
}
int main()
{
while(cin>>n)
{
pair<int,int> ans=solve(n);
cout<<ans.first<<' '<<ans.second<<endl;
}
}
C - Banh-mi - [简单思维题][贪心+前缀和+快速幂]
题意：
有一个食物，将其分成 $n(1 \le n \le 1e5)$ 份，编号为 $1 \sim n$，第 $i$ 份食物的初始美味度为 $x_i(x_i \in {0,1})$，
现在有 $q(1 \le q \le 1e5)$ 次查询，每个查询 $[l,r]$ 代表现在只考虑该区间内的食物，每次我吃其中的某一份食物 $i$，我的喜悦程度就会加上 $x_i$，同时区间内所有其他剩余的食物的 $x_j$ 都会加上 $x_i$。
现在要求对每个查询，输出我最大能获得的喜悦程度。
题解：
首先肯定是贪心地吃食物，每次都吃 $x_i$ 最大的食物。
假设初始区间内有 $a$ 个 $1$，$b$ 个 $0$，那么先吃完所有初始美味度为 $1$ 的食物，得到喜悦程度为
$1 + 2 + 4 + \cdots + 2^{a-1} = 2^0 + 2^1 + 2^2 + \cdots + 2^{a-1} = 2^a - 1$
接下来，剩下的初始美味度为 $0$ 的食物，现在美味度都变成了 $2^a - 1$，吃完这些食物得到喜悦程度为
$(2^a - 1) \cdot 2^0 + (2^a - 1) \cdot 2^1 + \cdots + (2^a - 1) \cdot 2^{b-1} = (2^a - 1)(2^0 + 2^1 + \cdots + 2^{b-1}) = (2^a - 1)(2^b - 1)$
因此我只需要通过前缀和，就能 $O(1)$ 统计出任意区间内 $0$ 和 $1$ 的数目，然后只需要快速幂求出 $2^a - 1 + (2^a - 1)(2^b - 1) = (2^a - 1)2^b$ 即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+;
const int maxn=1e5+;
int n,q;
char s[maxn];
int c[][maxn];
ll fpow(ll a,ll n)
{
ll res=,base=a%mod;
while(n)
{
if(n&) res*=base, res%=mod;
base*=base, base%=mod;
n>>=;
}
return res%mod;
}
int main()
{
scanf("%d%d",&n,&q);
scanf("%s",s+);
c[][]=c[][]=;
for(int i=,x;i<=n;i++)
{
x=s[i]-'';
c[x][i]=c[x][i-]+;
c[x^][i]=c[x^][i-];
}
for(int i=,l,r;i<=q;i++)
{
scanf("%d%d",&l,&r);
ll a=c[][r]-c[][l-], b=c[][r]-c[][l-];
printf("%lld\n",(fpow(,a+b)-fpow(,b)+mod)%mod);
}
}