Drink

注意到只能选一种,直接枚举就好了。

GPA

$n^3$ 暴力枚举。

Dec

简单 DP ,考虑 $f_{i,j}$ 由哪个状态转移来更优。

$f_{i,j}=\max\{f_{i-1,j},f_{i,j-1}\}+(i,j)$

Civilization

还是暴力,就是考虑在点 $(x,y)$ 建立城市,然后计算贡献,再统计步数即可。

const int N=505;
int d[20];
int cnt[5],n,a[N][N];
bool pd(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=n;}
int calc(int x,int y)
{
    int ans=0,w=a[x][y];
    memset(cnt,0,sizeof(cnt));
    for(int i=3;i>=-3;--i)
    {
        int w=3-abs(i);
        for(int j=-w;j<=w;++j)
        {
            if(pd(x+i,y+j))++cnt[a[x+i][y+j]];
        }
    }
    cnt[w]--;
    int t=1,s=0;
    while(t<9) 
    {
        s+=w; ans++;
        if(d[t]<=s) 
        {
            t++;
            for(int i=3;i;i--) 
                if(cnt[i]) 
                {
                    w+=i;
                    cnt[i]--;
                    break;
                }
        }
    }
    return ans;
}
int main()
{
    int t;scanf("%d",&t);
    for(int i=1;i<=9;i++)d[i]=8*i*i;
    while(t--)
    {
        int x,y;scanf("%d%d%d",&n,&x,&y);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        int ans=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int wd=abs(x-i)+abs(y-j);
                ans=min(ans,calc(i,j)+((wd-1)>>1)+1);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

Rotate

一道有问题的期望题。

不过讲讲做法吧,由于 $a_i$ 非严格递增,那么从外到内,一个黑段只会向内连一条边。

因此 $\mathbb{E}(\text{联通块数})=\text{点数}-\mathbb{E}(\text{边数})$ ,而边数我们只需要考虑 $i,i+1$ 层的情况即可。

分别钦定一段在 $i,i+1$ 层的黑段,仔细分析一下,对于 $i+1$ 层黑段而言,概率应为 $\frac{1}{a_i}+\frac{1}{a_{i+1}}$ 。

然后不钦定了,于是就有 $(\frac{1}{a_{i+1}}+\frac{1}{a_i})\frac{a_i}{2}\frac{a_{i+1}}{2}=\frac{a_{i}+a_{i+1}}{4}$ ,然后统计一下答案为 $\frac{a_n+a_1}{4}$


但是这样做显然有一个问题,对于同层点而已,第一个点的选择势必会影响后续的点的选择,举个最简单的例子,$a_i=2,a_{i+1}=1000$,按照上面的方法计算时,会出现有一个概率没有边,而实际上不可能出现没有边的情况,即概率为 $0$ 。相悖,所以是道错题。

Matrix

其实贡献只有四个情况,覆盖数为 $1,2,3,4$ 这四种情况下的最优解。

那么我们考虑当前最优解的覆盖数为 $i$ ,$|x|+|y|=dis$ ,一个点的贡献自然就是 $i*dis$

继续考虑有多少个这样的点,分情况讨论,且这里只讨论一个方向,$x,y\ge 0$:

当 $dis\le a_i$ ,则 $x\in[0,dis]$ ,右边界已然合法,然而左边界仍需要考虑 $x,y\le a_{i-1}$ 的情况,

即 $dis-a_{i-1}\le a_{i-1}$ ,不合法的方案为 $a_{i-1}-(dis-a_{i-1})+1$ 。注意特判 $(0,0)$ 的情况。

当 $dis>a_i$ ,则 $x\in[0,a_i]$ ,即方案数为 $a_i-(dis-a_i)+1$ ,再减去左边界不合法的情况即可出解。

Mosquito

一个最简单的暴力就是二分答案 $t$,然后对于每一个窗户可达点建一条流量为 $1$ 的边,看看是否能跑满。

但是这样显然是不行的。

但是我们从中可以找出一些结论,对于两个可达集合相同点 $i,j$,它们并没有本质不同,我们可以把它缩起来。

于是我们把本质相同的点的个数记录下来,预处理 $f_{t,statue}$ 表示 $t$ 时间下,集合为 $statue$ 的二进制的数量,这个可以差分预处理。

然后如果 $statue$ 二进制包含 $i$ 窗户,那么连一条无限流量边表示可行,其他与暴力相同。

const int N=1e3+2;
template<class o>void qr(o &x)
{
    x=0;int f=1;char c=gc;while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}x*=f;
}
template<class o>void qw(o x){if(x<0)x=-x,putchar('-');if(x/10)qw(x/10);putchar(x%10+48);}
struct edge{int y,c,next;}a[N*N];int len,last[N],cur[N];
void ins(int x,int y,int c)
{
    a[++len]=(edge){y,c,last[x]};last[x]=len;
    a[++len]=(edge){x,0,last[y]};last[y]=len;
}
int gap[N<<1],d[N<<1],q[N<<1],n,m,sum,st,ed,size,K;
int ISAP(int x,int f)
{
    if(x==ed)return f;
    int s=0,t;
    for(int y,&k=cur[x];k;k=a[k].next)
        if(d[y=a[k].y]+1==d[x])
        {
            s+=(t=ISAP(y,min(f,a[k].c)));
            a[k].c-=t;a[k^1].c+=t;
            f-=t;if(!f)return s;
        }
    if(!--gap[d[x]])d[s]=size+1;
    ++gap[++d[x]];cur[x]=last[x];
    return s;
}
struct node{int x,y,z;}A[7];int f[N<<3][64];
struct vec{int x,y;bool operator <(const vec &a)const{return x<a.x;}}b[7];
bool solve(int t)
{
    len=1;memset(last,0,sizeof(last));
    size=K+(1<<K)+1;st=K+(1<<K),ed=st+1;
    for(int i=1;i<=K;i++)ins(st,i,A[i].z);
    for(int i=1;i<(1<<K);i++)ins(i+K,ed,f[t][i]);
    for(int i=1;i<(1<<K);i++)
    {
        for(int j=0;j<K;j++)if(i>>j&1)
            ins(j+1,i+K,0x3f3f3f3f);
    }
    memset(gap,0,sizeof(gap));memset(d,0,sizeof(d));
    int l=1,r=0;++gap[d[q[++r]=ed]=1];
    for(int x=q[l];l<=r;x=q[++l])for(int k=last[x],y;k;k=a[k].next)if(!d[y=a[k].y])++gap[d[q[++r]=y]=d[x]+1];
    int ans=0;memcpy(cur,last,sizeof(cur));
    while(d[st]<=size)ans+=ISAP(st,0x3f3f3f3f);
    return ans==sum;
}
void init()
{
    memset(f,0,sizeof(f));
     for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
         {
             for(int k=1;k<=K;k++)
             {
                 int dis=abs(A[k].x-i)+abs(A[k].y-j);
                b[k]=(vec){dis,k-1};
             }sort(b+1,b+K+1);
             int u=0;
             for(int k=1;k<=K;k++)
             {
                 if(u)f[b[k].x][u]--;
                 u|=1<<b[k].y;
                 f[b[k].x][u]++;
             }
         }
    for(int i=1;i<=n+m;i++)
        for(int k=1;k<(1<<K);k++)
            f[i][k]+=f[i-1][k];
}
int main()
{
    int T;qr(T);
    while(T--)
    {    
        qr(n),qr(m),qr(K);sum=0;
        for(int i=1;i<=K;i++)qr(A[i].x),qr(A[i].y),qr(A[i].z),sum+=A[i].z;
        if(sum<n*m){puts("-1");continue;}
        sum=n*m;
        init();
        int l=0,r=n+m;
        while(l<r)
        {
            int mid=l+r>>1;
            if(solve(mid))r=mid;
            else l=mid+1;
        }
        printf("%d\n",l);
    }
    return 0;
}

Function

答案要求

$$\begin{aligned}\sum_{i=1}^n\sum_{j|i}j[(j,\frac{i}{j})=1]&=\sum_{j=1}^n\sum_{i=1}^{\lfloor\frac{n}{j}\rfloor}j[(i,j)=1]\\&=\sum_{j=1}^n\sum_{i=1}^{\lfloor\frac{n}{j}\rfloor}j\sum_{d=1}^n[d|i][d|j]\mu(d)\\&=\sum_{d=1}^n\mu(d)\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}jd\sum_{i=1}^{\lfloor\frac{n}{jd^2}\rfloor}1\end{aligned}$$

然后我们可以发现,当 $d>\sqrt{n}$ 或 $j>\lfloor\frac{n}{d^2}\rfloor$ ,值为 $0$ ,因此可以改写为:

$\begin{aligned}\sum_{i=1}^n\sum_{j|i}j[(j,\frac{i}{j})=1]&=\sum_{d=1}^{\sqrt{n}}\mu(d)\sum_{j=1}^{\lfloor\frac{n}{d^2}\rfloor}jd\sum_{i=1}^{\lfloor\frac{n}{jd^2}\rfloor}1\\&=\sum_{d=1}^{\sqrt{n}}d\mu(d)\sum_{j=1}^{\lfloor\frac{n}{d^2}\rfloor}j\lfloor\frac{n}{jd^2}\rfloor\end{aligned}$

代入 $G(i)=\sum\limits_{i=1}^ni\lfloor\frac{n}{i}\rfloor$ ,然后整除分块即可。