A. Madoka and Strange Thoughts
算法本质
思维
思路推演
这个题值得注意的一个点就是，在考虑2个数的gcd()、lcm()类似的函数时，可以把这两个数设为ak和bk，保证gcd(a, b)==1。
如果使用这个思路，则这个题能够秒解出来。
按照题目的要求则把式子化简为：a*b<=3，那就只有数种情况。
比如当n=10时，我们把k分为三段。
第一段是k为1~3。a b则有5种情况：1 1、1 2、2 1、1 3、3 1。
第二段是k为4~5。a b若取3则会超出n，所以只有3种情况：1 1、1 2、2 1。
第三段是k为6~10。a b若取2、3则会超出n，所以只有1种情况：1 1。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
ans = 5*(n/3) + 3*(n/2-n/3) + 1*(n-n/2);B. Madoka and Underground Competitions
算法本质
思维、模拟
思路推演
最基础的性质就是，同一行、列X之间的距离为k。
所以最能第一时间想到的方法是，通过(r, c)把周围必须填的点填上，同时记录哪些行和列已经被填写。
然后找到没有填写的行和列，一行+一列为一组，这组把中间交叉的点填上，然后把周围的点天上，记录填写上的行和列。
数学上可以证明，不会有重合的部分。
但是这样做显得有点过头。
题目只会给出一个固定的点，实际完全没有必要采用这样的饱和式攻击。
看样例1的第三个情况，就很容发现一种填法，那就是斜着填写。这种填写方法只是正确答案中的一种，但是足够覆盖题目的要求了。（如果题目会给出多个点，这个方法就不能行了）
以斜着填写思路为主，稍加思索可知：
对于(r, c)，我们先把这一列所有应该填写的点找出来（包括(r,c)），放入集合s，然后集合s里的点，都固定向斜着填写（4个斜着的方向都行），直到再次回来这一列停止。
思路回顾
简单的一个通过性质写模拟的题目，这种就要留心观察，是否能有一个更加简洁的式子。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int mp[maxn][maxn];
int k, sx, sy;
void dfs(int x, int y)
{
if (x>n) x-=n;
if (x<1) x+=n;
if (y>n) y-=n;
if (y<1) y+=n;
if (y==sy) return;
mp[x][y]=1;
dfs(x+1, y+1);
}
inline void solve()
{
// init
cin>>n>>k>>sx>>sy;
mem(mp, 0);
//cal
vector <int> row;
for (int xx=(sx-1)%k+1; xx<=n; xx+=k)
{
row.push_back(xx); //记录这一列都应该填写的点的行坐标
mp[xx][sy]=1;
}
for (int x:row)
dfs(x+1, sy+1);
//out
rep(i,1,n)
{
rep(j,1,n)
{
if (mp[i][j]==1) cout<<"X";
else cout<<".";
}
cout<<endl;
}
return;
}C. Madoka and Formal Statement
算法本质
思维
思路推演
典型的找题目规律（本质）的题目。
- 性质1：存在
b[i]<a[i]则无解。
性质1是题目中已经给出，更重要的是另一个初始条件：
若a[i]<=a[i+1]，则可以a[i]++。
可知：在a[i]<=a[i+1]的情况下，最多可以使得a[i]=a[i+1]+1。
同时会发现，这个条件，是相邻2个数的关系。
于是我们先缩小范围，研究不同情况下a[i] a[i+1] b[i] b[i+1]能否有解。
根据条件，我们简单得分为4种情况：
a[i] <= a[i+1]+1 && b[i] <= b[i+1]+1a[i] <= a[i+1]+1 && b[i] > b[i+1]+1a[i] > a[i+1]+1 && b[i] <= b[i+1]+1a[i] > a[i+1]+1 && b[i] > b[i+1]+1
经过简单思考，发现如果存在b[i]-b[i+1]>=2，则必须保证a[i]==b[i]，否则无解。（性质2）
2个元素的关系推理出来了，接着看扩大范围。发现性质相互补充，无缝连接。
思路回顾
这类题，已经把”找规律“写在脸上了，过程就是通过初始的条件，推出一些规律。
但是具体要怎么推，就需要逻辑和思维。
代码思路
先检查是否存在b[i]<a[i]的情况（性质1）。
若存在，无解。
再看，如果出现了这样的情况b[i]-b[i+1]>=2，是否能保证a[i]==b[i]。（性质2）
若不能做到，无解。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn], b[maxn];
inline void solve()
{
// init
cin>>n;
rep(i,1,n) cin>>a[i];
rep(i,1,n) cin>>b[i];
//cal
flag=1;
rep(i,1,n)
if (a[i]>b[i]) flag=0; //性质1
if (!flag)
{
cout<<"NO"<<endl;
return;
}
//cal 2
b[n+1] = b[1];
for (int i=1; i<=n; i++) //性质2
{
if (b[i]-b[i+1] >= 2) //有沟壑
{
if (b[i] != a[i])
flag=0;
}
}
//out
if (flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return;
}D. Madoka and The Corruption Scheme
算法本质
思维、思维（二进制）、一点博弈论
思路推演
此题最大的提示地方在于：有pow(2,n)个选手，n最大范围1e5。
这个数据范围，稍微脑子一转就明白，必须得向二进制方向思考，这是大前提。
随后我们简化初始条件，Madoka可以随意变化选手初始位置和每场比赛的胜负边，这里其中有2个“随意”，但实际要做到任意更变，只需要1个“随意”就好了。
于是我们改成：每场比赛初始设置永远是左边获胜，Madoka可以随意变化选手初始位置。
同时对赞助商的行为简化：希望使得最后胜者编号最大。
此时，单纯根据文本推到比较困难，于是举一个例子。n=3，k=0~7。
可以很明显的想到，如果要推选任意一个选手为胜者，其付出的代价等价于n。
所以n=3 k>=3时，赞助商就可以推编号最大的选手获胜，作特殊处理。
接下来思考n=3, k=0~2。
以下图为例，红色代表胜利。
- 当
k=0时，只能采纳pos=1的点。
此时Madoka肯定在pos=1的地方放上编号为1的选手。 - 当
k=1时，通过改变胜负边，能采纳pos=1、2、3、5的点。
Madoka肯定会在这4个点，放上编号为1~4的选手，最后赞助商肯定会选择编号为4的选手。 - 当
k=2时，能采纳pos=1~7的点。
Madoka同上操作，赞助商会选择编号为15的选手。
接下来就是更简单的事了，根据目前发现的东西，找出规律。
（思考类似这样的问题：问什么pos=1点在k=0的时候都能被采纳，而pos=3的店只能在k>=1被采纳？）
很明显，一个点的位置是否能被采纳跟原本设定的胜利路径有关系。
我们用0表示红色代表胜利的线，1表示黑色代表失败的线，从上往下表示。
其二进制表示中，有多少个1则代表其胜利所需要的代价。
我们要找的就是：长度为n的二进制数，条件：拥有数字1数目小于等于k，符合条件的二进制数有多少个。
代码思路
组合数相加。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
//组合数板子略
int C(int a,int b); //C(下，上)
inline void solve()
{
// init
init_c();
cin>>n>>m; //m代替题目中的k
//cal
if (m>=n)
ans = qpow(2, n, mod);
else
{
ans=0;
rep(i, 0, m)
{
ans += C(n, i);
ans %= mod;
}
}
//out
cout<<ans<<endl;
return;
}
评论 (0)