【解题报告】CF EDU #ROUND 109A~D
比赛链接
比赛评价：
19分钟速杀了AB两题，算是新突破？然后就罚坐卡题，C看了一遍是一道模拟转战D，写了半天贪心结果WA7暴毙 。
排名1800+压线进2000
A. -
题意
每次可以加一次水或者魔法，问最少多少次水和魔法的比例达到要求的百分比
思路
100/gcd(n,100)即可
代码
// Problem: A. Potion-making// Contest: Codeforces - Educational Codeforces Round 109 (Rated for Div. 2)// URL: https://codeforces.com/contest/1525/problem/A// Memory Limit: 256 MB// Time Limit: 1000 ms// FishingRod#includeusing namespace std;#define endl "\n"typedef long long LL;typedef pair PII;#define MULINPUT/*DATA & KEY*/int T;void solve(int C){//NEW DATA CLEAN//NOTE!!!int n;cin>>n;int g=__gcd(n,100);cout<<100/g<
B.Sort
题意
给你一个全排列，你可以选择l，r区间并其中的数重新排列，但是不能一次性全选，问最多弄几次使得数组升序
思路
0 次 ， 已 经 升 序 0次，已经升序 0次，已经升序
1 次 ， a [ 1 ] = = 1 ∣ ∣ a [ n ] = = n 1次，a[1]==1||a[n]==n 1次，a[1]==1∣∣a[n]==n
3 次 ， a [ n ] = = 1 & & a [ 1 ] = = n 3次，a[n]==1 \&\& a[1]==n 3次，a[n]==1&&a[1]==n
2 次 ， 其 他 情 况 2次，其他情况 2次，其他情况
代码
【C待补【解题报告】CF EDU #ROUND 109A~D】// Problem: B. Permutation Sort// Contest: Codeforces - Educational Codeforces Round 109 (Rated for Div. 2)// URL: https://codeforces.com/contest/1525/problem/B// Memory Limit: 256 MB// Time Limit: 2000 ms// FishingRod#includeusing namespace std;#define endl "\n"typedef long long LL;typedef pair PII;#define MULINPUT/*DATA & KEY*/int T;const int N=55;int a[N];void solve(int C){//NEW DATA CLEAN//NOTE!!!int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];bool flag=1;for(int i=1;i=a[i+1]){flag=0;break;}if(flag)cout<<0<
C. Robot
题意
数据结构+模拟+思维，实现不能，思维不能（待补）
思路
首先考虑没有反射的情况，可以发现奇数坐标的和偶数坐标的是永远不可能相撞的，所以我们可以尝试奇数坐标的和偶数坐标的分开考虑 。
如果机器人走的方向相对，且同奇偶，那么他们会相撞，消耗的时间为两点距离的一半 。可以发现这和栈很类似，最右边或者的机器人和新遍历到的机器人如果方向相反那就会互相抵消 。
如果一个机器人向左检查一下栈是否为空，否则的抵消；向右走直接加入栈
如果有反射墙
以堆栈为空向左走为例，我们可以反射它走到墙的距离，我们可以说，他是从-x开始向右走的，因为本来它的右边没有机器，所以换个说法没啥影响 。
但是堆栈中最后的机器人（同一方向的）也是不一样的 。碰到右边墙反射，他们会依次配对碰撞，第一个和第二个，第三个和第四个 。同样的，我们可以m+(m-x)来做坐标反射
代码
就算看了题解也写不出代码的屑是我了，先码了
在这里插入代码片
D.
题意
给n个椅子，有的位置上坐了人，有的没有，每个人移动到另一个位置上需要花费 a b s ( i ? j ) abs(i-j) abs(i?j) 。问：最少花费多少，让每个人不在原来位置上 。
思路
原本想贪心，动态维护查询距离最近的点，然后发现WA7 。
赛后大佬发了几道相似题，貌似要用前缀和优化的DP 。
不过写贪心的过程中有几点还是需要记录的 。
set不怎么支持下标操作，所以如果要用下标相关的信息最好不要用set 。
实际上是老鼠进洞模型的DP，可以参考一下这几个博客（主要第一个的）