CF1286

Codeforces Round 612 (Div. 1)

CF1286C1&C2

link

题意

这是一道交互题。

有一个长度为 \(n\) 的由小写字母组成的字符串,你需要通过两种操作得到整个字符串:

  • ? l r ——列出 \(s[l\dots r]\) 的所有子串。子串返回的顺序会被随机打乱,并且在每一个子串中,字母的顺序也会被随机打乱。
  • ! s ——表示你已经得到了 \(s\)。这个操作只能进行一次,进行完后游戏立即结束。

你可以进行最多三次询问,同时所有询问中所有子串长度 \(\lceil0.777(n+1)^2\rceil\)

注:简单版本只要求询问中所有子串长度 \(\lceil(n+1)^2\rceil\)

注意测试点中的字符串是预先给定的,而不会根据你的询问而发生改变。

题解

先特判下 \(n=3\) 的情况,这个时候直接问每一位是什么即可。

以下的 \(n\ge 4\)

先来想简单版本怎么做。

发现一次询问如果区间长度是 \(len\),那么所有子串长度是 \(\frac{len\times(len + 1)}{2}\)

发现如果你直接问一次 \([1,n],[2,n]\),那么在 \([1,n]\) 中出现、在 \([2,n]\) 中没有出现的串的左端点一定是 \(1\)。然后每次在长度为 \(len+1\) 中出现,在 \(len\) 没有出现的字符就是第 \(len + 1\) 个字符。

询问总长度是 \(\frac{n(n+1)}{2}+\frac{n(n-1)}{2}=n^2\le (n+1)^2\),可以通过简单版本。

现在来到了困难版本

发现刚刚的方法行不通,问的子串长度太大了。

但是我问 \([1,\lceil\frac{n}{2}\rceil]\) 是可以的,用了 \(\frac{1}{4}n^2\) 个字符。

现在还剩下大约 \(\frac{1}{2}n^2\) 个字符可以使用。

先问一次 \([1,n]\),用完剩下的字符。

然后考虑怎么做。

设在最后一次询问中,在长度为 \(len\) 的所有子串中,字符 \(x\) 出现了 \(cnt_{len,x}\) 次。

然后考虑,对于 \(2\times len + 1\le n\)\(cnt_{len + 1,x}-cnt_{len,x}\) 表示什么。

考虑将长度 \(len+1\)\(len\) 的子串按照左端点匹配,那么还剩下一个 \([n-len+1,n]\) 的子串没有匹配。

依次让匹配的 \(len+1\) 子串“减去” \(len\) 子串,那么会得到子串 \([len+1,n]\)

再减去刚刚的 \([n-len+1,n]\) 子串,最终就变成了 \([len+1,n-len]\)

不难发现这个左右端点是对称的。

而左边的字符串我们已经知道具体是什么了。

然后每次只需要判断这个多出来的字符是什么即可。

做完了。

代码

#include<bits/stdc++.h>
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 100 + 10;
int n;
string ans;
namespace Subtask1{
multiset<string> st;
int cnt[maxn][27];
string solve(int n){
    if(n == 1){
        cout << "? " << 1 << " " << 1 << endl;
        string s;cin >> s;
        return s;
    }
    cout << "? " << 2 << " " << n << endl;
    for(int i = 1;i <= (n - 1) * n / 2;i++){
        string s;cin >> s; sort(s.begin(),s.end());
        st.insert(s);
    }
    cout << "? " << 1 << " " << n << endl;
    for(int i = 1;i <= n * (n + 1) / 2;i++){
        string s;cin >> s; sort(s.begin(),s.end());
        auto it = st.find(s);
        if(it == st.end()){
            for(int j = 0;j < s.length();j++)
                cnt[s.length()][s[j] - 'a']++;
        }
        else st.erase(it);
    }
    string res = "";
    for(int len = 1;len <= n;len++){
        char ch = '-';
        for(int i = 0;i < 26;i++)
            if(cnt[len][i] != cnt[len - 1][i]){
                ch = i + 'a';break;
            }
        res.push_back(ch);
    }
    return res;
}
};
int cnt[maxn][27];
int sum[27];
void main(){
    ios::sync_with_stdio(false);
    cin >> n;
    if(n <= 3){
        for(int i = 1;i <= n;i++){
            cout << "? " << i << " " << i << endl;
            char ch;cin >> ch;
            ans.push_back(ch);
        }
        cout << "! " << ans << endl;
        return;
    }
    ans = Subtask1::solve((n + 1) / 2);
    cout << "? " << 1 << " " << n << endl;
    for(int i = 1;i <= (n + 1) * n / 2;i++){
        string s;cin >> s;
        for(int j = 0;j < s.length();j++)
            cnt[s.length()][s[j] - 'a']++;
    }
    ans.resize(n);
    if(n & 1){sum[ans[n / 2] - 'a']++;}
    for(int i = n - (n + 1) / 2  - 1;i + 1;i--){
        // cerr << "i = " << i << "n - i = " << n - i << endl;
        sum[ans[i] - 'a']++;
        for(int j = 0;j < 26;j++)
            if(cnt[i + 1][j] - cnt[i][j] - sum[j] == 1){
                ans[n - i - 1] = j + 'a';break;
            }
        sum[ans[n - i - 1] - 'a']++;
    }
    cout << "! " << ans << endl;
    return;
}
};
bool edmemory;
signed main(){
    auto stclock = clock();
    Call_me_Eric::main();
    auto edclock = clock();
    cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
    cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
    return 0;
}

CF1286D

link

题意

一条无限长的管道中有 \(n\) 个粒子,第 \(i\) 个粒子的位置为 \(x_i\),保证对于 \(1\leq i <n\),有 \(x_i<x_{i+1}\)

一次实验开始时,第 \(i\) 个粒子会获得 \(v_i\) 的初速度,并有 \(\frac{p_i}{100}\) 的概率向右移动,\(1-\frac{p_i}{100}\) 的概率向左移动。

当任意两个粒子移动到相同位置的时候,我们称之为一次 碰撞。一次实验耗费的时间为所有 碰撞 发生时间的最小值。特别地,如果没有发生任何 碰撞,我们认为这次实验耗费的时间为 \(0\)

求一次实验期望耗费的时间,对 \(998244353\) 取模后输出。

题解

先来想一个问题:可能作为答案的碰撞到底有多少个?

不妨设四元组 \((i,j,0/1,0/1)\) 表示 \(i,j\) 相碰,方向分别是 \(0\iff \leftarrow,1\iff \rightarrow\)

不难发现,如果 \(j\neq i+1\),那么 \(i+1\) 一定会先和 \(i\) 或者 \(j\) 相碰。

所以 \(j=i+1\)

然后发现,相邻的两个粒子相碰,只有最多两种情况。

  • 相对:这个显然。
  • 同向:当且仅当速度大的(严格大于)追速度小的。

然后发现,碰撞情况数最多只有 \(2\times (n – 1)\) 种。

将每个碰撞需要用的时间从小到大排个序。

不难发现,第 \(i\) 个碰撞发生当且仅当前 \(i-1\) 个碰撞全都不发生。

那么这个碰撞对期望的贡献就是:前 \(i-1\) 个碰撞不发生且第 \(i\) 个碰撞发生的概率 \(\times\) 这个碰撞用时。

不难发现,可以利用差分,将 “前 \(i-1\) 个碰撞不发生且第 \(i\) 个碰撞发生的概率” 转化为 “前 \(i – 1\) 个碰撞不发生的概率 \(-\)\(i\) 个碰撞不发生的概率”。

然后设 \(f_{i,0/1}\) 表示第 \(i\) 个粒子向 左/右 移动,且保证前 \(i\) 个粒子都不相碰的概率。

\(b_{i,0/1,0/1}\) 表示是否允许第 \(i\) 个粒子向 左/右 移动且第 \(i + 1\) 个粒子向 左/右 移动。

\(p_i\) 表示第 \(i\) 个粒子向移动的概率(注意这里与题意定义不同

那么有递推式:

\[f_{i,0}=p_i\times (b_{i-1,0,0}\times f_{i-1,0} + b_{i-1,1,0}\times f_{i-1,1})\\ f_{i,1}=(1 – p_i)\times (b_{i-1,0,1}\times f_{i-1,0} + b_{i-1,1,1}\times f_{i-1,1}) \]

不难发现这个东西可以写成矩阵乘法:

\[\begin{bmatrix} f_{i,0}\\ f_{i,1} \end{bmatrix}= \begin{bmatrix} p_i&p_i\\ 1-p_i&1-p_i \end{bmatrix} \times \begin{bmatrix} f_{i-1,0}\\ f_{i-1,1} \end{bmatrix} \]

每次对于第 \(i\) 个碰撞 \((i,i+1,x,y)\),在计算“前 \(i\) 个碰撞不发生的概率”的时候,将 \(b_{i,x,y}\gets 0\),然后进行计算即可。

但是现在每次修改之后都需要从头算一遍,复杂度 \(O(n^2)\) 过不去。

然后发现这个东西直接放到线段树上维护即可。

然后就没了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 10, mod = 998244353;
int qpow(int x,int a){
    int res = 1;
    while(a){
        if(a & 1)res = res * x % mod;
        x = x * x % mod;a >>= 1;
    }
    return res;
}
int n;
int x[maxn], v[maxn], ps[maxn];
struct node{
    int pos;int dist, speed;
    int lvec, rvec;//0 <=> <-,1 <=> ->
    node(int pos = 0,int dist = 0,int speed = 0,int lvec = 0,int rvec = 0
        ):pos(pos),dist(dist),speed(speed),lvec(lvec),rvec(rvec){}
    friend bool operator < (node a,node b){
        return a.dist * b.speed < b.dist * a.speed;
    }
}d[maxn << 1];
struct Matrix{
    int a[2][2];
    Matrix(){a[0][0] = a[1][0] = a[0][1] = a[1][1] = 0;}
    Matrix(int a1,int a2,int a3,int a4){//[a1,a2]\n[a3,a4]
        a[0][0] = a1;a[0][1] = a2;
        a[1][0] = a3;a[1][1] = a4;
    }
    friend Matrix operator * (Matrix a,Matrix b){
        Matrix c = Matrix();
        for(int i = 0;i < 2;i++)for(int j = 0;j < 2;j++)
            for(int k = 0;k < 2;k++)c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;
        return c;
    }
};
struct Segment_Tree{
    struct node{
        Matrix sum;
        node(Matrix sum = Matrix()):sum(sum){}
    }d[maxn << 2];
    node mergenode(node l,node r){return node(l.sum * r.sum);}
    void build(int l,int r,int p){
        if(l == r){d[p] = node(Matrix(ps[l],ps[l],(1 - ps[l] + mod) % mod,(1 - ps[l] + mod) % mod));return;}
        int mid = l + r >> 1;
        build(l,mid,p << 1);build(mid + 1,r,p << 1 | 1);
        d[p] = mergenode(d[p << 1],d[p << 1 | 1]);
    }
    node query(int l,int r,int s,int t,int p){
        if(s <= l && r <= t){return d[p];}
        int mid = l + r >> 1;
        if(t <= mid)return query(l,mid,s,t,p << 1);
        if(mid < s)return query(mid + 1,r,s,t,p << 1 | 1);
        return mergenode(query(l,mid,s,t,p << 1),query(mid + 1,r,s,t,p << 1 | 1));
    }
    void update(int l,int r,int pos,int p,int x,int y){
        if(l == r && l == pos){d[p].sum.a[x][y] = 0;return;}
        int mid = l + r >> 1;
        if(pos <= mid)update(l,mid,pos,p << 1,x,y);
        else update(mid + 1,r,pos,p << 1 | 1,x,y);
        d[p] = mergenode(d[p << 1],d[p << 1 | 1]);
    }
}tree;
void main(){
    int inv100 = qpow(100,mod - 2);n = read();
    for(int i = 1;i <= n;i++){x[i] = read();v[i] = read();ps[i] = (1 - read() * inv100 % mod + mod) % mod;}
    if(n == 1){puts("0");return;}
    int cnt = 0;
    for(int i = 1;i < n;i++){
        d[++cnt] = node(i,x[i + 1] - x[i],v[i + 1] + v[i],1,0);
        if(v[i] > v[i + 1]){d[++cnt] = node(i,x[i + 1] - x[i],v[i] - v[i + 1],1,1);}
        if(v[i] < v[i + 1]){d[++cnt] = node(i,x[i + 1] - x[i],v[i + 1] - v[i],0,0);}
    }
    sort(d + 1,d + 1 + cnt);tree.build(1,n,1);
    int lst = 1, ans = 0;
    for(int i = 1;i <= cnt;i++){
        tree.update(1,n,d[i].pos,1,d[i].lvec,d[i].rvec);
        Matrix tmp = tree.query(1,n,1,n,1).sum * Matrix(1,0,0,0);
        int now = (tmp.a[0][0] + tmp.a[1][0]) % mod;
        ans = (ans + (d[i].dist) * qpow(d[i].speed,mod - 2) % mod * ((lst - now + mod) % mod) % mod) % mod;
        lst = now;
    }
    printf("%lld\n",ans);
    return;
}
};
bool edmemory;
signed main(){
    auto stclock = clock();
    Call_me_Eric::main();
    auto edclock = clock();
    cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
    cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
    return 0;
}
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。