神tm结论大赛日神仙。

A

求中位数。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[1005];

int main(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    return printf("%d\n",a[n+1>>1]),0;
}

B

验证一张图是不是合法的扫雷游戏图。

#include<cstdio>
#include<cctype>
using namespace std;
const int maxn=100,maxm=100;
const int fl[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

int n,m;char pic[maxn+5][maxm+5];

int main(){
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%s",pic[i]+1);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (isdigit(pic[i][j])||pic[i][j]=='.'){
                int num=pic[i][j]=='.'?0:pic[i][j]-'0';
                int x,y,tot=0;
                for (int f=0;f<8;f++){
                    x=i+fl[f][0];y=j+fl[f][1];
                    if (x<0||x>n||y<0||y>m) continue;
                    if (pic[x][y]=='*') tot++;
                }
                if (tot!=num) return puts("NO"),0;
            }
    return puts("YES"),0;
}

C

给出 $p,q,b$ ，求 $p\over q$ 在 $b$ 进制下是否除尽。

结论：如果 $q$ 中只含有 $b$ 的素因子，那么可以除尽。所以不停令 $q={q\over gcd(q,b)}$ ，最后验证 $b\ mod\ q=0$ ，如果成立那么可以除尽。然而这么写你会成功TLE，估计数据故意设计过……

实际上因为你已经令 $q={q\over gcd(q,b)}$ ，所以下一次令 $q={q\over gcd(q,lastgcd)}$ 就行了（ $gcd(q,b)$ 只会越来越小，所以并不需要每次和 $b$ 取 $gcd$ ），这样就可以跑得飞快。

#include<cstdio>
using namespace std;
typedef long long LL;

int te,GCD[8005][8005];LL p,q,b;

LL gcd(LL a,LL b){
    if (!b) return a;if (a<=8000&&b<=8000&&GCD[a][b]) return GCD[a][b];
    if (a<=8000&&b<=8000) return GCD[a][b]=gcd(b,a%b); else return gcd(b,a%b);
}
int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%lld%lld%lld",&p,&q,&b);
        if (!(p%q)) {puts("Finite");continue;}
        LL t=gcd(p,q);q/=t;
        while ((t=gcd(q,b))>1) q/=t,b=t;
        if (!(b%q)) puts("Finite"); else puts("Infinite");
    }
    return 0;
}

D

$$ f(b) = \begin{cases} b[1] & \quad \text{if } m = 1 \\ f(b[1] \oplus b[2],b[2] \oplus b[3],\dots,b[m-1] \oplus b[m]) & \quad \text{otherwise,} \end{cases} $$

有 $q$ 个询问，求 $max\{f(b[i,j])|L\le i\le j\le R\}$ 。

画个图就会发现显然有结论 $f(b[i,j])=f(b[i+1,j])\ xor\ f(b[i,j-1])$ 。

然后再开个数据存一下所有答案，询问直接输出。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5000;

int n,te,f[maxn+5][maxn+5],MAX[maxn+5][maxn+5];

int main(){
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&f[i][i]);
    for (int L=2;L<=n;L++)
        for (int i=1,j=L;j<=n;i++,j++)
            f[i][j]=f[i][j-1]^f[i+1][j];
    for (int i=1;i<=n;i++)
        for (int j=(MAX[i][i]=f[i][i],i+1);j<=n;j++)
            MAX[i][j]=max(MAX[i][j-1],f[i][j]);
    for (int L=2;L<=n;L++)
        for (int i=1,j=L;j<=n;i++,j++)
            MAX[i][j]=max(MAX[i][j],max(MAX[i][j-1],MAX[i+1][j]));
    for (scanf("%d",&te);te;te--){
        int L,R;scanf("%d%d",&L,&R);
        printf("%d\n",MAX[L][R]);
    }
    return 0;
}