Educational Codeforces Round 109
A
题意
配药，每次操作加一单位水或者配料，求最少需要多少次操作，使得最后配料占比为k%。
思路
容易想到，最差一定可以用100次操作（加k次配料，100-k次水）来完成目标，如果k与100有公因数，则可以优化。因为k是整数，所以化为最简分数即可。
代码
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int k;
scanf("%d",&k);
if(gcd(100,k)==1)
printf("100
");
else
printf("%d
",100/gcd(100,k));
}
}
B
题意
给一个1-n的排列，每次操作可以任意选择一个非全体（非1-n全选）的区间，然后任意排序其中的元素。求最少多少次操作使得整体递增。
思路
如果已经有序，则需要0次。如果第一个为1或最后一个为n，则需要一次。如果第一个不为1且最后一个不为n，则需要3次。其他情况需要2次。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=55;
int a[MAX];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
bool already=1,start_or_end=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=2;i<=n;i++)
already&=(a[i]==a[i-1]+1);
start_or_end=(a[1]==1)||(a[n]==n);
if(already) printf("0
");
else if(start_or_end) printf("1
");
else if(a[1]==n&&a[n]==1)printf("3
");
else printf("2
");
}
}
C
题意
数轴上有若干机器人，初试位于某一点，向左或向右移动。所有机器人速度一致，均为1。如果任意两个机器人在某整数点相遇，则会碰撞爆炸。数轴0和m的位置有墙，机器人到达墙所在位置后立刻换方向。现给出n个机器人的初始位置和方向。求每个机器人是否会爆炸，若爆炸给出爆炸时间，若不爆炸输出-1。
思路
根据规则可以看到，初始位于偶数位置的机器人，任意偶数时刻一定在奇数位置，奇数时刻一定在偶数位置。初始位于奇数位置的机器人反之。根据规则，只有整数节点相遇才会爆炸。故奇偶不同的机器人永远不会相互碰撞爆炸。所以可以分为奇偶两个集合分别解决。
对于其中某一个集合。只有相向而行的机器人才可能碰撞爆炸。故问题类似括号匹配，从根据初始位置左往右遍历每个机器人，如果向右则入栈，向左则与栈顶匹配，计算碰撞时间。再处理一下转向问题。某个机器人转向就等价于从墙的另一边走过相等的距离穿过墙。这样用类似括号匹配的方法，再处理好细节，问题就解决了。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=3e5+5;
vector<int>a[2];//0 for odd, 1 for even
int res[MAX],start[MAX],dir[MAX];//0 for left, 1 for right
stack<int>stk;
bool cmp(int x,int y)
{
return start[x]<start[y];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
a[0].clear();
a[1].clear();
int n,m;
char s[5];
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
{
res[i]=-1;
scanf("%d",&start[i]);
if(start[i]&1)a[0].push_back(i);
else a[1].push_back(i);
}
for(int i=0; i<n; i++)
{
scanf("%s",s);
if(s[0]=='L')dir[i]=0;
else dir[i]=1;
}
for(int i=0; i<2; i++)
sort(a[i].begin(),a[i].end(),cmp);
for(int k=0; k<2; k++)
{
for(int i=0; i<a[k].size(); i++)
{
int cur=a[k][i];
if(dir[cur])
stk.push(cur);
else if(stk.empty())
{
start[cur]*=-1;
stk.push(cur);
}
else
{
int r=stk.top();
stk.pop();
res[cur]=res[r]=(start[cur]-start[r])>>1;
}
}
while(stk.size()>=2)
{
int cur=stk.top();
stk.pop();
start[cur]=2*m-start[cur];
int r=stk.top();
stk.pop();
res[cur]=res[r]=(start[cur]-start[r])>>1;
}
while(stk.size())stk.pop();
}
for(int i=0; i<n; i++)
printf("%d ",res[i]);
printf("
");
}
}
D
题意
有n把椅子，编号1-n，其中一部分，最多n/2（向下取整）把有人，其余空置。每次操作可以让一个人换到一个最开始空置的椅子上，代价为两个椅子之间的距离。求使得所有最开始有人的椅子都变空（所有人都换到一开始空的位置上）的最小代价。
思路
容易想到，有人的椅子和空椅子可以构成一张二分图，边权为两椅子的距离。但是数据范围太大，最大权匹配显然会超时。所以这条路行不通。然后想到dp。
可以从左往右，从选择的角度考虑。从左往右选出的第一个空置椅子，最优一定是匹配从左往右第一个人。
证明如下：
将有人椅子的位置表示为一个集合X，空置的椅子的位置表示为集合Y，令Xi表示从左到右第i个有人的位置，Yi同理。
则有
按顺序匹配的代价可表示为
交换顺序匹配的代价表示为
当有
时，(1)与(2)等价。
当有
时，则有(1)<(2)。其余情况同理。
故问题转化为经典dp问题，一段区间内选一部分使得答案最优。
dp[i][j]表示，1-i位置内，选出j个位置作为置换的位置所需的最小代价。则有转移方程
dp[i][j]=min(dp[i][j], dp[i-1][j], dp[i-1][j-1]+|i-pos[j]|)，其中pos[j]表示从左往右第j个有人的位置。
代码
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAX=5e3+5;
int dp[MAX][MAX],a[MAX];
vector<int> pos;
int main()
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
if(a[i]) pos.push_back(i);
}
memset(dp,INF,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=pos.size();j++)
{
dp[i][j]=min(dp[i][j],dp[i-1][j]);
if(!a[i]&&j)dp[i][j]=min(dp[i][j],dp[i-1][j-1]+abs(i-pos[j-1]));
}
}
printf("%d
",dp[n][pos.size()]);
}