Fill in the Matrix
算法本质
思维
题目大意
给定n*m的棋盘，每个格子需要放一个数字，满足：
- 每行数字是一个0开始的长度
m的排列
存在集合set，每列数字的MEX值放入set。
最大化set的MEX值。
输出这个值，且输出棋盘信息。
思路推演
从后往前推到，先考虑某列的MEX值为0，既然顺序不重要，所以我们可以假定：
- 第
i列（0下标）的MEX值为i
随后稍加模拟可以写出一种方式，以5*4为例子：
4 0 1 2 3
3 4 0 1 2
2 3 4 0 1
1 2 3 4 0
1 2 3 4 0稍加修改后观察可知，仅有前m-1行做出了贡献，若行数>=m-1，其贡献为m——第一行做出了2贡献，其他行做出1贡献。
同时样例告诉我们，当m=1时，第一行无法做出2贡献，特判一下即可
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>m;
if (m==1)
{
n++;
while (n--)
cout<<0<<endl;
return;
}
int ans = min(m, n+1);
cout<<ans<<endl;
for (int i=1; i<=n; i++)
{
int s = (i >=m ? 1 : m-i);
for (int j=0; j<m; j++)
cout<<(s+j)%m<<" \n"[j==m-1];
}
return;
}Candy Party (Easy Version)
算法本质
思维
题目大意
给定数组a[]，表示n个人初始手中的糖果，每个人需要执行一次操作：
- 给另外一人2^x^个糖果
这个过程能否同时满足下列条件：
- 每个人都收到糖果，且恰好来自于一个人
- 操作后每个人的糖果数目一致
思路推演
首先特判糖果能否均匀。
既然一个人又要给出，又要收到糖果，其得到的糖果可以用2^x - 2^y来表示。
通过二进制观察，可以保证差集合与{x, y}组成的集合一一对应。
所以此题十分简单，只需要事先构造一个映射：差 --> (x, y)，然后对于每个人初始糖果值与最后值做差。
假设平均值是10，初始值是6，可以看作市场上会增加一张4卡牌，减少一张8卡牌，最后检查所有卡牌数目是否为0即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
vector<int> v;
for (int i=1; i<=n; i++) v.push_back(in());
vector<int> er(40);
er[0] = 1;
for (int i=1; i<=30; i++)
er[i] = er[i-1]*2;
map<int, pair<int, int>> mp; // 插值 --> (x,y)
for (int i=0; i<=30; i++)
for (int j=0; j<=30; j++)
mp[er[j]-er[i]] = {i, j};
int sum=accumulate(v.begin(), v.end(), 0ll);
if (sum%n) // 考虑能否平均
{
cout<<"NO"<<endl;
return;
}
int avg=sum/n;
flag = 1;
map<int, int> cod; // cod[x]=y：表示市场上值x的卡牌有y张
for (int x:v)
{
int cha=x-avg;
if (cha==0) continue; // 差值为0可以视作自己打自己
if (mp.count(cha)==0)
{
flag = 0;
break;
}
auto [a, b] = mp[cha];
cod[a]++, cod[b]--; // 市场上a多一张、b少一张
}
for (auto [val, cnt] : cod)
if (cnt!=0)
flag=0;
cout<<(flag ? "YES" : "NO")<<endl;
return;
}Candy Party (Hard Version)
算法本质
思维
题目大意
给定数组a[]，表示n个人初始手中的糖果，每个人需要执行0次或1次操作：
- 给另外一人2^x^个糖果
这个过程能否同时满足下列条件：
每个人满足下列条件之一：
- 收到糖果，且恰好来自于一个人
- 没有收到糖果
- 操作后每个人的糖果数目一致
思路推演
与Easy版本不同的点在于，其可以只给糖果、只收糖果。
比如对于某人需要4个糖果才能达到平均值，在Easy版本中，一定是收到8个、给出4个，但是在Hard中还有另一种情况：只给出4个。
通过模拟可以发现：（差值为负数转换一下意思）
- 差值的不满足
2^x - 2^y
整体不可解 - 情况A：差值为0
仍然可以忽视 - 情况B：差值仅满足
2^x - 2^y
需要收到2^x，给出2^y 情况C：差值满足
2^x
有两种可能：- 收到
2^(x+1)，给出2^x - 收到
2^x
- 收到
我们仍然以市场角度去记录，AB情况方案是固定的，先处理。
现在对于C，力求通过转换方案使得市场整体为0——这是一种典型的思维题，通常用贪心或者dp搞定。
- 给出
2^x
市场上x卡牌数目+1 - 收到
2^x
市场上x卡牌数目-1
现在市场有一个初始情况，只需要从最低为开始，力求满足即可。（贪心思路）
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
vector<int> v;
for (int i=1; i<=n; i++) v.push_back(in());
vector<int> er(40);
er[0] = 1;
for (int i=1; i<=30; i++)
er[i] = er[i-1]*2;
map<int, pair<int, int>> mp; // 插值 --> (x,y)
set<int> st;
for (int i=0; i<=30; i++)
for (int j=0; j<=30; j++)
mp[er[i]-er[j]] = {i, j}; // +i,-j
for (int i=0; i<=30; i++)
st.insert(er[i]), st.insert(-er[i]); // st记录一下2的指数，用于判断
int sum=accumulate(v.begin(), v.end(), 0ll);
if (sum%n)
{
cout<<"NO"<<endl;
return;
}
int avg=sum/n;
flag = 1;
map<int, int> cod; // cod[x]表示市面上x值的剩余数目
map<int, int> mp2; // {巧合差值， 数目} 巧合差值是指恰好为2的指数的差值
for (int x:v)
{
int cha=x-avg;
if (cha==0) continue; // 差值为0忽略
if (st.count(cha)) // 相差恰好是2的指数情况，先保存，之后处理
{
mp2[cha]++;
continue;
}
if (mp.count(cha)==0) // 如果没有对应的操作，说明无解
{
flag = 0;
break;
}
auto [a, b] = mp[cha];
cod[a]++, cod[b]--; // 市场上的a卡-1，b卡+1
}
set<int> alive;
for (auto [val, cnt] : mp2) // 待会需要按巧合差值的绝对值升序遍历
alive.insert(abs(val));
for (int cha:alive) // 遍历巧合差值
{
int p;
for (int i=0, val=1; i<=30; i++, val*=2) // 检查巧合差值是多少
{
p = i;
if (val==cha)
break;
}
if (cod[p] > mp2[cha]+mp2[-cha]) // 正巧合差值 + 负巧合差值 能使其为0的极限
{
flag = 0;
break;
}
cod[p] += mp2[cha] - mp2[-cha];
if (cod[p]%2!=0) // 比较巧地规避了复杂的公式计算
{
flag=0;
break;
}
cod[p+1] += cod[p]/2;
cod[p] = 0;
}
cod[0] = 0;
for (auto [val, cnt] : cod)
if (cnt!=0)
flag=0;
cout<<(flag ? "YES" : "NO")<<endl;
return;
}Travel Plan
算法本质
组合数思维、一点组合数学
题目大意
给定top个点的无向图，满足下列条件的点对存在边：
i点和2i点i点和2i+1点
每个点的点值为[1~m]，定义一条路径的成本：
- 经过点值的最大值
输出遍历所有点值的情况，每种情况下的图计算所有路径的成本和的和。（包含单点自己到自己的情况）
t <= 200
top <= 1e18（单个样例）
m <= 1e5（所有样例之和）思路推演
一个朴素的思路是，找出所有价值为x的路径的数目，然后相加求和即可。
先将图画出来，是一个很标准的二叉树图（只是点特别多），两点的路径唯一。
可以发现每层的点至多存在3种不同的状态，对于某个点，我们可以枚举其左侧延申数目、右侧延申数目，复杂度是log级别平方，大概是60*60，加上枚举层的循环、整体的样例数：200 * 60^3 ≈ 5e7是可行的。
ac核心代码
下列代码的整体思路是，先计算完整三角形的二叉图，然后再计算不规则部分，但是实际这样比较麻烦，这个题解的思路是上方的方法：每层算3个状态：
头文件、宏定义、快读模板、常见变量、常见变量等略。
int q(int x) {return (x%mod + mod)%mod;}
inline void solve()
{
vector<int> er(70); // 未取模
er[0] = 1;
for (int i=1; i<=60; i++) er[i]=er[i-1]*2;
int top;
cin>>top>>m;
for (int i=0; i<=60; i++)
{
if (top >= er[i]-1)
n = i;
}
n--; // 0~n层构成了完美倒三角
// debug(n)
vector<int> cnt(130); // cnt[x]=y表示有x个点的链数目是y（总的图）
// 现在先计算最上方的n层，覆盖了2^n-1个数
for (int i=n; i>=0; i--)
{
vector<int> now(130); // 当前层的点，now[x]=y有x个点的链数是y
int ju = n-i; // 当前层与底层的距离
// l表示当前层的点，左侧向下层延申的距离，注意l=0或1时方案都是1
for (int l=0; l<=ju; l++)
{
for (int r=0; r<=ju; r++)
{
int wayl = (l>0 ? er[l-1]%mod : 1);
int wayr = (r>0 ? er[r-1]%mod : 1);
now[l+r+1] = q(now[l+r+1] + wayl*wayr%mod);
}
}
// 将其加入总图
for (int j=1; j<=120; j++)
cnt[j] = q(cnt[j] + now[j]*q(er[i])); // er[i]表示第i层的点数
}
// 接下里计算第n+1层
int num = top - (er[n+1]-1); // 第n+1层还有num个数
if (num > 0)
{
vector<int> now(130); // 当前层的点，now[x]=y有x个点的链数是y
// 首先考虑，链两侧都是n+1层的情况
now[1] = 1;
for (int len=1, ju=3; len<num; len*=2, ju+=2) // 现在是以len个点为一个整体，和旁边的整体互动
{
// ju表示两个组的点形成链的长度（点长度）
int zu=(num + len-1) / len; // 一共有zu个整体
int res=0;
if (zu%2==0) // 如果恰好能一一对应分配
{
int last = num - (zu-1)*len; // 最后一个组的长度
// res += (zu/2-1)*len*len; // 其中前zu-2个组都是一定是完整的
res += (zu/2-1)%mod*q(len)%mod*q(len)%mod;
res = q(res);
// res += len*last; // 最后一个组的长度
res += q(len)*q(last)%mod;
res = q(res);
}
else
// res += zu/2*len*len; // 正好抛弃最后一个组
res += q(zu/2)*q(len)%mod*q(len)%mod, res = q(res);
cnt[ju] = q(cnt[ju] + res);
}
// 然后考虑，链只有一侧是n+1层的情况
for (int i=n; i>=0; i--) // n+1层先走到i层，再往下走
{
int ju1 = n+1-i+1; // 先走的距离，包含第i层的点
for (int j=i; j<=n; j++)
{
int ju2=j-i;
int ways=1; // 从第i层走到第j层的方案数（不能走左边）
if (ju2>=1) ways=er[ju2-1]%mod;
now[ju1+ju2] = q(now[ju1+ju2] + ways);
}
}
for (int j=1; j<=120; j++)
cnt[j] = q(cnt[j] + q(now[j]*q(num)));
}
// 至此，我们已经拿到了图所有长度链的数目
int ans=0;
for (int len=1; len<=119; len++)
{
if (cnt[len]==0) continue;
for (int val=m; val>=1; val--)
{
// num：一条长度为len、价值为val的链本身的方案数
// cnt[len]：有cnt[len]条长度len、价值val的链本身的方案数
// num2：在这个图中，当放置了一条长度len、价值val的链后，其他top-len个点可以随机选择的方案数
int num = q(qpow(val, len, mod) - qpow(val-1, len, mod));
int num2 = qpow(m, top-len, mod);
ans = q(ans + val * cnt[len] % mod * num % mod * num2 % mod);
}
}
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)