CF1286
CF1286C1&C2
题意
这是一道交互题。
有一个长度为 \(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
题意
一条无限长的管道中有 \(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;
}