A.构造
构造出一个不超过 \(40\times40\)的矩阵，每个位置填 \(r,y,x\) 三者之一，使得连续的三个格子按顺序构成字符串 \(ryx\) 恰好有 \(n\) 个。
这里连续的是指同一行、同一列或者同一 \(45°\) 斜线，方向任意。
唐唐的构造。
最优的情况一定是 \(ryxyryx\) 这种情况，算一下发现最多能有 \(19\times117=2223\) 个 \(ryx\) ，然后随便构造一下就好了。
感觉有必要放一下赛时的略显抽象的码。
点击查看代码
#include <bits/stdc++.h>
#define fr first
#define se second
#define U unsigned
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define __ __int128
#define ld long double
#define VE vector<LL>
#define db double
using namespace std;
inline int read()
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
return x*f;
}
int n,a[45][45];
void D(int x,bool fl)
{
if (!n) return ;
if (x == 40)
{
a[x][1] = 1,a[x][2] = 2,a[x][3] = 3;fl = 1;n--;
for (int y = 4;y < 40 && n;y += 2)
{
if (fl) a[x][y] = 2,a[x][y+1] = 1,n--;
else a[x][y] = 2,a[x][y+1] = 3,n--;
fl ^= 1;
}
return ;
}
int nw = 1;
for (int y = 1;y <= 40 && n;y++)
{
if (y > 1) nw = 3;
if (y == 2 || y == 40) nw = 2;
if (n < nw)
{
if (n == 1 || y == 40)
{
if (fl)
{
if (y < 40) a[x][y] = 2,a[x+1][y] = 3;
else a[x][y] = 3,a[x+1][y] = 1;
}
else
{
if (y < 40) a[x][y] = 2,a[x+1][y] = 1;
else a[x][y] = 3,a[x+1][y] = 3;
}
}
else
{
if (y == 39)
{
if (fl) a[x][y] = 2,a[x+1][y] = 3,a[x][y+1] = 3,a[x+1][y+1] = 1;
else a[x][y] = 2,a[x+1][y] = 1,a[x][y+1] = 1,a[x+1][y+1] = 3;
}
else
{
if (fl) a[x][y] = 3,a[x+1][y] = 1,a[x][y+1] = 2,a[x+1][y+1] = 3;
else a[x][y] = 1,a[x+1][y] = 3,a[x][y+1] = 2,a[x+1][y+1] = 1;
}
y++;
}
n = 0;
}
else
{
if (fl) a[x][y] = 2,a[x+1][y] = 1;
else a[x][y] = 2,a[x+1][y] = 3;
n -= nw;
}
if (!n)
{
while (++y <= 40)
{
if (fl) a[x][y] = 3,a[x+1][y] = 3;
else a[x][y] = 1,a[x+1][y] = 1;
}
}
}
D(x+2,!fl);
}
int main()
{
freopen("ryx.in","r",stdin);
freopen("ryx.out","w",stdout);
n = read();int tmp = n;
int nw = 1;
for (int i = 1;i <= 40 && n;i++)
{
if (i > 2) nw = 3;
if (n < nw)
{
if (n == 1) a[1][i] = 1,a[2][i] = 2,a[3][i] = 2;
else a[1][i] = 1,a[2][i] = 3,a[3][i] = 3;
n = 0;
}
else a[1][i] = 1,a[2][i] = 2,a[3][i] = 3,n -= nw;
}
D(4,1);
cout << 40 << " " << 40 << '\n';
for (int i = 1;i <= 40;i++)
{
for (int j = 1;j <= 40;j++)
{
if (!a[i][j]) a[i][j] = 2;
if (a[i][j] == 1) cout << 'r';
if (a[i][j] == 2) cout << 'y';
if (a[i][j] == 3) cout << 'x';
}
cout << '\n';
}
return 0;
}
B.游戏
有数组 \(a_1\cdots a_n\) ，\(A\) 先选择一个数 \(i\) 使 \(a_i=0\)，\(B\) 后选择一个数 \(j\)，答案即为 \(a_j\) ，\(A\) 想使答案最小，\(B\) 想使答案最大，求期望答案。（\(B\) 在选择时并不知道 \(A\) 选了哪个数）
赛时没读懂题，实际上只需考虑一方就可以了，即找出一个策略，使得无论 \(B\) 选择哪个数，最终期望答案都 \(\le m\) 。
所以我们可以二分答案，设 \(p_i\) 为 \(A\) 选择 \(i\) 的概率。
每次将 \(a_i>m\) 的 \(a_i\) 分配一个概率，即 \((1-p_i)a_i=m\) ，所以 \(p_i=1-\frac{m}{a_i}\) ，最后判断一下所有概率的和是否 \(\le0\) 。
C.数数
对于一个排列 \(\{p_n\}\)，定义 \(f(k,i)=\min\limits_{j=i}^{i+k-1}p_j\)，\(F(k)=\max\limits_{i=1}^{n-k+1}f(k,i)\)。
现在给出 \(F(1),F(2),\dots,F(n)\)，求有多少个满足的排列。
赛时觉得跟 arc183_c 很像，但是在这里不能使用区间 \(dp\) 。
事实上这又是一个未知复杂度的题，不过这回 \(OI\) 赛制赛时谁敢写这个。
容易发现 \(F(i)\) 是单调不增的，同时每个数都覆盖一段区间。
于是我们记 \(l_i\) 为 \(i\) 在 \(F\) 中第一次出现的位置，\(r_i\) 为 \(i\) 在 \(F\) 中最后一次出现的位置。
当我们从小往大填数的时候，维护所有极长空段的长度，有两种情况：
- 当前数 \(i\) 在 \(F\) 数列中出现过，若当前最长空段的长度 \(\neq r_i\)，那么状态不合法。否则我们枚举 \(i\) 填入的位置，同时更新状态和答案，将插入的空段分为两个空段。
- \(i\) 在 \(F\) 中没有出现过，此时直接枚举填入的位置就好，一个细节是若当前最长空段只有一个，那么当前数 \(i\) 不能填入极长空段。
点击查看代码
#include <bits/stdc++.h>
#define fr first
#define se second
#define U unsigned
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define __ __int128
#define ld long double
#define VE vector<LL>
#define db double
using namespace std;
inline int read()
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
return x*f;
}
const int P = 998244353;
int F[55],n,L[55],R[55];
map < vector<int>,int > f;
map < vector<int>,bool > vis;
inline int mod(int x)
{return x >= P ? x-P : x;}
int main()
{
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
int n = read();
for (int i = 1;i <= n;i++)
{
F[i] = read();
if (!L[F[i]]) L[F[i]] = i;
R[F[i]] = i;
}
queue < vector<int> > q;
vector < int > ve;ve.pb(n);
q.push(ve),f[ve] = 1;
while (q.size())
{
ve = q.front();q.pop();vis[ve] = 0;
int mx = ve.back(),id = ve.size(),s = 0;
for (int i : ve) s += (i == mx);
if (!L[id])
{
for (int i = 0;i < ve.size();i++)
{
if (ve[i] && (ve[i] < mx || s > 1))
{
for (int j = 1;j <= ve[i];j++)
{
vector < int > tmp;
for (int k = 0;k < ve.size();k++)
if (k != i) tmp.pb(ve[k]);
tmp.pb(j-1),tmp.pb(ve[i]-j);
sort(begin(tmp),end(tmp));
if (!vis[tmp]) vis[tmp] = 1,q.push(tmp);
f[tmp] = mod(f[tmp]+f[ve]);
}
}
}
}
else
{
if (mx != R[id]) continue;
for (int i = ve.size()-1;i >= 0;i--)
{
if (ve[i] != mx) break;
for (int j = 1;j <= ve[i];j++)
{
vector < int > tmp;
for (int k = 0;k < ve.size();k++)
if (k != i) tmp.pb(ve[k]);
tmp.pb(j-1),tmp.pb(ve[i]-j);
sort(begin(tmp),end(tmp));
if (tmp.back() == L[id]-1)
{
if (!vis[tmp]) vis[tmp] = 1,q.push(tmp);
f[tmp] = mod(f[tmp]+f[ve]);
}
}
}
}
}
ve.clear(),ve.resize(n+1);
cout << f[ve];
return 0;
}
D.滈葕
给定一个 \(0/1\) 边权有向图，给每个点赋予一个 \(ABCD\) 中的字母使得每条有向边 \((u,v,w)\) 都满足 \(w=1\Leftrightarrow(a_u,a_v)\in\{(A,D),(A,B),(B,D),(B,A),(C,D),(C,A),(C,B)\}\) 。
简称输入的 \(0\) 边（不克制）为白边，\(1\) 边（克制）为黑边
容易看到，\(A,B\) 对称且强连通，而 \(C\) 只会克制别人，\(D\) 只会被别人克制。
所以首先，一个点只有无黑边入且无白边出（或者只有白边指向 \(C\)）的可以是 \(C\)，只有无白边入且无黑边出的可以是 \(D\)。
我们可以贪心把所有无黑边入且无白边出的染成 \(C\)，把所有无白边入且无黑边出且还没染成 \(C\) 的染成 \(D\)。
这样染之后，剩下的点都既有黑入/白出之一又有白入/黑出之一。把那些只有白边指向 \(C\) 的设为 \(C\)。再剩下的只能是 \(A,B\) 之一。称这些剩下的点组成集合 \(X\)。
我们只需要考虑 \(X\) 内部连的边，因为其它边都已经被染成 \(C,D\) 的点满足了。
可以发现 \(X\) 内如果存在一条白边，则说明两端相同属性，如果存在一条黑边则说明两端不同属性。因
为 \(A,B\) 互克。那么直接把白边缩起来，并判定黑边在缩点之后的二分图染色即可。