B.XOR = Average
算法本质
思维
题目大意
给定一个n，请给出n个范围为(1~1e9)的数字（可重复），使其异或和==平均值。
思路推演
n为奇数时，任意个相同数即可。n为偶数时，事情有了变化，暂时没有明确规律。
那先手动计算一些情况。
当n==2时，可以找出1 3、2 6等等方法。
考虑当n==4时，发现十分不好找，但是当利用n==2的情况，可以很快找出1 3 2 2。
随即找到n为偶数的规律：1 3 2 2 2 ...
C.Almost All Multiples
算法本质
思维
题目大意
对于一个长度为n的排列p[]，已知整数x，如果满意以下条件则是美丽的：
p[1]=xp[n]=1- 对于
i<n：p[i] % i == 0
在所有美丽的排列中选择字典序最小的输出。
思路推演
首先尝试构造一下p[]，从大到小构造。
很容易发现，只有n是还没用的，只有n的因数可以填n。
如果x不是n的因数，则没有美丽排列。
如果是n%x==0，就通过a[x]=n一定可以获得一个美丽排序，就考虑如何才能构造字典序最小的美丽排序。
首先小于x部分不动，动了会增大字典序，同时我们希望把a[x]=n往后移动一下，即找后面下标是n因数的位置。
即可发现规律。（规律相对简单，这里略过）
注意考虑x=1 和 x=n的情况，可能需要特判，根据代码的鲁棒性。
D.Range = √Sum
算法本质
思维
题目大意
给定一个n，请给出n个范围为(1~1e9)的数字（不可重复），使其max_val - min_val == √Sum。
思路推演
因为Sum需要开方，所以先设定Sum的值，当设置为n n+1 n+2的时候，调整空间过小导致了一些问题。
所以这里直接设2n，即Sum = 4n^2
构造就是一个尝试的过程
则平均数就是4n，范围为3n ~ 5n。
然后依次填入即可。
E.Tick, Tock
算法本质
思维、加权并查集
题目大意
给你一个n*m的矩形，每个格子有一个0 ~ h-1的数字，若为-1表示不确定。
如果一个矩形可以通过任意次以下操作使所有数字为0，则称其为美丽的：
- 选择任意一行或一列数字+1，然后对
h取模
输出可能存在的美丽狙矩阵个数。（取模1e9+7）
思路推演
首先来看看美丽矩阵具有的特征。
通过手动模拟可以发现，美丽矩阵的每一行中，其列下标之间的数字差是一样的：mp[x1][y1]-mp[x1][y2] == mp[x2][y1]-mp[x2][y2]（对h取模）。
以列为单位看也是一样的，值得注意的是：如果能保证每个行中，其对应位置的数字差一致，则不需要考虑列情况。
这时我们把每一列看作一个节点。
每行的某2个不为-1的数字，都代表了一种关系——表示这两列的节点之间的差值。
我们历便所有行，拿到所有关系，如果关系之间有冲突，说明是不可行的，输出0结束。
看似每行最多有m^2条关系，实际因为加法的结合律，可以最多使用m-1条关系来表示m个节点的关系。
建图+dfs可以维护这些关系，且可以判断冲突。
但是带权并查集十分适合当前情况，更加推荐。
随后思考：当关系不冲突时，有多少种情况。
当m个节点组合成一个连通块时，说明只有当前情况。
当他们组成x个连通块时，还可以用x-1条新关系填充，即qpow(k, x-1)。
假设已经补充了新关系，现在m个节点组成了一个连通块。
当某一行值全为-1时，即使知道他们的关系（差值），因为没有初始值，所以仍有k种可能。
所以ans = qpow(k, 全为-1值的行数 + 连通块数 - 1, mod)
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline int mu(int x)
{
return (x%k+k)%k;
}
// 先使用init_set()初始化
int fu[maxn], val[maxn]; // 加权并查集板子
void init_set()
{
for (int i=1; i<=m; i++) fu[i] = i; // i 就在它本身的集合里
for (int i=1; i<=m; i++) val[i] = 0;
return;
}
int find_set(int x)
{
if (x != fu[x]) // x 不是自身的父亲，即 x 不是该集合的代表
{
int fx=fu[x];
fu[x] = find_set(fu[x]); // 路径优化代码
val[x] += val[fx];
val[x] = mu(val[x]);
}
return fu[x];
}
void union_set(int x, int y, int v) // x家族 --> y家族（x为儿子，y为父亲）
{
int fx = find_set(x);
int fy = find_set(y);
if (fx==fy) return;
fu[fx] = fy; // 把 x 的祖先变成 y 的祖先的儿子
val[fx] = -val[x] + v + val[y];
}
bool vis[maxn]; //计算连通块数
inline void solve()
{
//init
cin>>n>>m>>k;
init_set();
//cal
int ans=0;
flag=1;
for (int x=1; x<=n; x++)
{
int y0=-1, v0=0; //y0表示这一行第一个不为-1的位置，val是其值
for (int y=1; y<=m; y++)
{
int v;
cin>>v;
if (v==-1) continue;
if (y0==-1)
{
y0=y;
v0=v;
}
else //同一行多个值，需要建立关系
{
int f1=find_set(y0), f2=find_set(y);
if (f1==f2 && mu(val[y0]-val[y])!=mu(v0-v)) //说明关系起冲突了，直接爆炸
flag=0;
else if (f1!=f2) //说明关系还没建立，建立关系
union_set(y0, y, mu(v0-v));
}
}
if (y0==-1) //说明这行全是-1
ans++;
}
rep(i,1,m) vis[i]=0;
for (int i=1; i<=m; i++) //连通块数
{
int fi=find_set(i);
ans += vis[fi]==0;
vis[fi]=1;
}
ans--;
//out
ans = qpow(k, ans, mod);
if (!flag) ans=0;
cout<<ans<<endl;
return;
}
评论 (0)