2020 icpc 上海站+模拟+dp

A、B题就忽略了。重点记录下C题，这代替的重点在于代码的实现。 思路很简单：在保证字典序最小的情况下，使得字母不存在环。 队友提醒可以用并查集去写，确实，并查集可用于判环。另一种思路看的知乎大佬写的，实现的很巧妙，都尝试了一下。

C. Phase Shift

用两个map记录对应关系。 m1记录字符串中s的字符可转化为字符串t中某字符。 m2记录字符串中t的字符可由原字符串s中某个字符得到。 具体解释见代码：

#include 
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int inf=1e18;
const int N=7e5+5;
const int mod=1e9+7;
bool cmp(int a,int b){return a>b;}
//priority_queueq;
int n;
string s;
mapm1,m2;
int fd(int x)
{
    while(m2[x]!=-1) x=m2[x]; //t中对应的s字符，从x出发不构成环
    return x;
}
void solve()
{
    cin>>n>>s;
    s=" "+s;
    string ss="";
    for(int i=0;i>s;
    s=" "+s;
    string ss="";
    for(int i=0;is     aft:s->t
    for(int i=1;ip1>>v1>>p2>>v2;
    ans=0;
    if(p1>p2)
    {
        swap(p1,p2);swap(v1,v2);
    }
    //一个人走完全程
    ans=min({(p1+n)/v1,(n-p1+n)/v1,(p2+n)/v2,(n-p2+n)/v2});
    //相对走
    ans=min(ans,max((n-p1)/v1,p2/v2));
    //走到l~r间的某个点返回
    double l=p1,r=p2;
    for(int i=1;i