Chips on the Board
算法本质
思维
题目大意
给定2个长度n的数组a[] b[]，现在有一个空白的n*n的棋盘，玩家需要放置若干个棋子满足：
- 每个棋格的所处的行或列至少存在一个棋子
每个棋子放置有成本：
- 放置在
(i, j)位置，需要a[i]+b[j]元
输出玩家的最小化成本。
思路推演
一种朴素的想法就是：
- 以行为单位，每行必须存在一个棋子
- 以列为单位，每列必须存在一个棋子
证：
若存在某种方式，第i行不存在棋子、第j列不存在棋子
则(i,j)格子不合法所以，既然每行都需要一个棋子，则a[]数组的贡献就是其元素和，b[]的贡献可以调整最小元素*n。
Make it Alternating
算法本质
思维
题目大意
给定01串s，希望s变成交错的（不出现连续1或连续0），玩家可以操作：
- 删除某个字符
在最少删除次数下，玩家删除的方案数。（注意，删除不同下标的字符视作不同操作，不同删除顺序视作不同操作）
思路推演
最少删除次数很容易求得。
例如100011110删除的次数显然是2+3。
核心在于操作数的计算，例如3个0，实际上只能删除2个元素。
计算方式：3个0中，C(3, 1)计算留下来的0的情况，另外2个操作放入操作池，4个1也同理。
操作池有5个操作，全排列即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
string s;
cin>>s;
int ans=1, kind=0;
for (int l=0, r=0; l<s.length(); l=r)
{
while (r<s.length() && s[l]==s[r])
r++;
kind++;
ans = ans * (r-l) % mod;
}
for (int i=1; i<=s.length()-kind; i++)
ans = ans*i%mod;
cout<<s.length()-kind<<" "<<ans<<endl;
return;
}Sum of XOR Functions
算法本质
思维
题目大意
给定长度n数组a[]，定义：
- $f(l,r) = a[l] ⊕ a[l+1] ⊕ ... ⊕ a[r]$
输出$\sum_{l=1}^n\sum_{r=l}^nf(l,r) * (r-l+1)$
思路推演
首先想到的就是拆位，拆位后效果会好很多。
拆位后题目就变成一个很简单的了，至少思路上没有什么障碍了。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
vector<int> a(n+5);
for (int i=1; i<=n; i++)
cin>>a[i];
int ans=0;
for (int val=1; val<=1e9; val*=2)
{
// num[0]表示奇数目前能作为左端点的个数，w[0]表示能作所有奇数左端点到目前下标的和
int num[2]={0, 0}, w[2]={0,0};
int res=0, x=0; // x表示当前是奇数点还是偶数点(注意奇偶切换的状态)
for (int i=1; i<=n; i++)
{
num[x]++;
w[0] += num[0];
w[1] += num[1];
if (a[i] & val) // 奇偶切换
x ^= 1;
res += w[x^1]; // 当前点作为右端点，可以收获w[x^1]的倍率
num[x] %= mod;
w[0] %= mod;
w[1] %= mod;
res %= mod;
}
ans += res*val;
ans %= mod;
}
cout<<ans<<endl;
return;
}Interactive Game with Coloring
算法本质
思维
题目大意
给定n大小的树，其中1是根节点。
玩家需要对树的边染色，然后保证在以下游戏必胜：
- 初始时玩家会被传送至某个未知的非1节点
- 如果玩家目前处于非1节点，可以知道附近任意颜色的边的数目，（玩家看来）相同颜色的边没有区别，然后选择一条边走
- 玩家必须保证每次行动都能缩减与节点1的距离，否则计为失败，当抵达1时成功
在保证必胜的前提下，减少使用的颜色种类。
玩家需要输出染色方案，同时还需要完成游戏（交互题）。
思路推演
稍加模拟就发现了一个特别简单的思路：
- 设节点1深度为0，则对任意深度为x的通向父节点的边，模3同余的点染相同颜色。
这样的话，每个节点的边至多存在2种颜色——一共三种可能，然后根据情况选择，可以保证自己深度一直减小。
那接下来还需要考虑仅用1种颜色和2种颜色的情况了。
通过样例可以发现，如果节点最大深度为1，那就可以使用1种颜色即可，那增加深度是否还可以保证仅用一种颜色呢？
显然不行，深度>1时一定存在某点有多条边，同种颜色边无区别，玩家无法选择唯一正确的边行动。
那接下来就是2种颜色的情况了。当最大深度>2时，能否存在情况仅用2种颜色——显然是可行的。
思考，可行动的本质是什么，首先正确的边的颜色只能为1。
所以在2种颜色的情况下，边的颜色交替染色，还有一个问题是：某个节点的2种颜色的数目都是1——这需要事先规定。
我们称仅有2条边相连的非1节点为斑点，节点1以下的子树是一个整体，这个整体中的斑点如果深度的奇偶不一致，则不可行，反之可行。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int fu[maxn], c[maxn];
vector<int> g[maxn];
vector<int> ck(int u, int dep) // 检查斑点的奇偶个数
{
vector<int> res(2);
if (g[u].size()==1)
res[dep%2]++;
for (int v:g[u])
{
vector<int> t=ck(v, dep+1);
res[0] += t[0];
res[1] += t[1];
}
return res;
}
void tu(int u, int col, int top) // 染色函数
{
if (col>top) col-=top;
c[u] = col;
for (int v:g[u])
tu(v, col+1, top);
}
inline void solve()
{
cin>>n;
k = 1;
for (int v=2; v<=n; v++)
{
int u=in();
g[u].push_back(v);
fu[v] = u;
if (fu[v]!=1) k=2;
}
if (k==1) // 检查是否可以用1种颜色搞定
{
cout<<k<<endl;
for (int i=2; i<=n; i++)
cout<<1<<" \n"[i==n];
cout.flush();
while (1)
{
int op=in();
if (op==1) break;
int t=in();
cout<<1<<endl;
cout.flush();
}
return;
}
for (int u:g[1]) // 检查k=2的情况
{
vector<int> x=ck(u, 1);
if (x[0]>0 && x[1]>0)
k = 3;
}
if (k==2)
{
cout<<k<<endl;
for (int u:g[1]) // 默认如果1、2颜色都是数目1，选择颜色1
{
vector<int> x=ck(u, 1);
if (x[0]>0)
tu(u, 2, k);
else
tu(u, 1, k);
}
for (int i=2; i<=n; i++)
cout<<c[i]<<" \n"[i==n];
cout.flush();
while (1)
{
int op=in();
if (op==1) break;
vector<int> num(k+1);
cin>>num[1]>>num[2];
cout<<(num[1]==1 ? 1 : 2)<<endl; // 默认如果1、2颜色都是数目1，选择颜色1
cout.flush();
}
return;
}
// k=3的情况
cout<<k<<endl;
tu(1, 0, k);
for (int i=2; i<=n; i++)
cout<<c[i]<<" \n"[i==n];
cout.flush();
while (1)
{
int op=in();
if (op==1) break;
vector<int> num(k+1);
cin>>num[1]>>num[2]>>num[3];
int res;
if (num[1] + num[2] + num[3] == 1)
{
if (num[1]==1)
res=1;
else if (num[2]==1)
res=2;
else
res=3;
}
else if (num[1]==0)
res=2;
else if (num[2]==0)
res=3;
else
res=1;
cout<<res<<endl;
cout.flush();
}
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)