C. Removing Smallest Multiples
算法本质
思维（贪心）
思路推演
对于每个缺失的值，我们肯定是希望它用尽可能小的因数来去掉。
但是举例12，12的因数2。
要想12用因数2来去掉，就需要保证2、4、6、8、10、12都是缺失的。
显然，如果我们先找值，再找值的因数，选取最小的，这样复杂度是一定过不了的。
所以得先找因数。
历遍每个因数，我们寻找其能达到的值，一旦这个某个值并非丢失，则继续。
这样复杂度大约是O(nlog~2~n)
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
char ch2[maxn];
inline void solve()
{
cin>>n;
scanf("%s", ch+1); //ch[]来表示值是否缺失
rep(i,1,n) ch2[i]=ch[i]; //ch2[]来表示值是否已经被填充，避免重复
ans=0;
for (int i=1; i<=n; i++)
{
for (int pos=i; pos<=n; pos+=i)
{
if (ch[pos]=='1') break; //遇到不缺失的值了
if (ch2[pos]=='0') //填充
{
ch2[pos]='1';
ans+=i;
}
}
}
cout<<ans<<endl;
return;
}D. Slime Escape
算法本质
思维
思路推演
这道题跟多校的一个题，思路和模型都很类似，算是那个题的简单版本。
题目稍加推理可知，走出去的方法可以归纳为：先走x方向，再走y方向，……，吸纳足够的能量，然后向另一方向冲出去。
关键就在于，每次走的时候，应该走到什么地方停下。
基础操作围绕核心的点——能量，只要能保证能量收益是正的即可。
所以我们假装向某个方向前进，设定走到停下来的条件：
- 收益是大于等于0（那就真的走过去）
- 整体能量为负（那就换个方向）
- 触边（说明成功走出去了）
同时，再加一个触发机制——要是连续左右没有更新则表明不能走通。
ac核心代码
PS：代码看起来多，主要是有大循环里有左右两个方向的代码，重复了许多。
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
//init
cin>>n>>k;
rep(i,1,n) cin>>arr[i];
//cal
int l=k-1, r=k+1; //l r表示边界，表示还没走到的地方
ans=arr[k];
flag=0;
while (1)
{
//cal1 计算向左走
int da=ans; //模拟整体能量值——要是能走，就赋值，不能就不动
int yuan_l = l; //记录原来的l位置
int cnt=0; //cnt表示连续不更新的次数，要是cnt==2说明走不通
while (1) //向左边挖洞
{
if (da>ans && arr[l]<0) break; //整体收益大于等于0
if (l==0) break; //触碰到边界
if (da+arr[l]<0) break; //保证整体能量大于等于0
da += arr[l];
l--;
}
if (l==0 || r==n+1) //先判断是否走出来
{
flag=1;
break;
}
if (da>=ans) //有收益，则走
ans=da;
else //负收益，不走
l=yuan_l;
if (yuan_l != l) cnt++; //说明没有更新
//cal 2 计算向右走
da=ans;
int yuan_r = r;
while (1) //向右边挖洞
{
if (da>ans && arr[r]<0) break; //整体收益大于等于0
if (r==n+1) break; //触碰到边界
if (da+arr[r]<0) break; //保证整体能量大于等于0
da += arr[r];
r++;
}
if (l==0 || r==n+1) //先判断是否走出来
{
flag=1;
break;
}
if (da>=ans)
ans=da;
else
r=yuan_r;
if (yuan_r != r) cnt++;
//计算是否走不通
if (cnt==0) //说明左右目前都走不通，那就算了呗
break;
}
//out
if (flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return;
}E. Rectangular Congruence
算法本质
思维、（一点）数学
思路推演
这种题目好像被称之为构造题，叫做数学题也可以吧。
不管叫做什么名称，存在这样明确的数学条件（素数、方阵、算式），就一定需要使用数学方法推导出结论，来帮助更好地用代码去解决。
a(x,x)+a(y,y) != a(x,y)+a(y,x)
-->
a(x,x)-a(y,x) != a(x,y)-a(y,y)第二个式子明显有强烈的视觉规律——这4个点，两列，每列的上点减下点的差，不允许相等。
（结合方阵中只有主对角线有确定值，可以推断出整个方阵的规律只有相对差值有关系）
这个时候，就很容易想到一个思路：各列相邻两点的差值分别固定0 1 2 ... n-1。
用具体的数据验证一下，果然是可行的。
再结合式子简单分析，发现也是可行的。
思路回顾
数学题实际推出式子后就十分简单了。
作为编程题，大多时候所谓的数学题也不会是枯燥单纯的证明，比如此题是与图形方阵结合，还有的题与位运算结合。
也许一些条件、式子看起来毫无章法，但是对其演化，尝尝能得到不错的结果。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
void mo(int &x) //方便取余
{
x %= n;
if (x < 0) x += n;
}
int mp[maxn][maxn];
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>mp[i][i];
//cal
for (int c=1; c<=n; c++) //c：列下标
{
int add=c-1; //每列的相邻相差值
for (int r=c-1; r>=1; r--) //向上填充
{
mp[r][c] = mp[r+1][c]-add;
mo(mp[r][c]);
}
for (int r=c+1; r<=n; r++) //向下填充
{
mp[r][c] = mp[r-1][c]+add;
mo(mp[r][c]);
}
}
//out
rep(i,1,n)
{
rep(j,1,n) cout<<mp[i][j]<<" ";
cout<<endl;
}
return;
}题目
算法本质
思路推演
代码思路
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)