D:
完全模拟一定超时，设2个数组来存加在前面的/加在后面的，如果出现reverse操作，交换这两个数组即可
#include<bits/stdc++.h>
using namespace std;
#define ms(x,y) memset(x, y, sizeof(x))
#define lowbit(x) ((x)&(-x))
#define sqr(x) ((x)*(x))
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
void run_case() {
string s;
int q;
cin >> s >> q;
vector<char> store[2];
int sta = 0;
while(q--) {
int type;
cin >> type;
if(type == 1) sta = !sta;
else {
static int pos;
static char ch;
cin >> pos >> ch;
pos--;
store[pos^sta].push_back(ch);
}
}
string ans;
for(auto i = store[0].rbegin(); i != store[0].rend(); i++) ans += *i;
ans += s;
for(auto ch: store[1]) ans += ch;
if(sta) reverse(ans.begin(), ans.end());
cout << ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cout.flags(ios::fixed);cout.precision(9);
//int t; cin >> t;
//while(t--)
run_case();
cout.flush();
return 0;
}
E:
(O(n^2))算法很容易想到怎么做，优化这种问题也是比较常见的形式，这里我们可以使用前缀和的形式。
设(num_i)为第(i)位到末尾的十进制数的大小，那么问题可转换为(frac{num_i-num_j}{10^{i-j+1}} (i < j))是否能被(p)整除，也就是(frac{num_i-num_j}{10^{i-j+1}}\%p=0 (i < j))
转换一下，得到同余式:(num_i equiv num_j (mod p))，那我们可以借用偏序的思想，从尾向头扫，统计每一个(num_i)出现的数量，若重复出现，则一定满足同余式，更新答案即可，注意要特判(p=2/5)的情况
#include<bits/stdc++.h>
using namespace std;
#define ms(x,y) memset(x, y, sizeof(x))
#define lowbit(x) ((x)&(-x))
#define sqr(x) ((x)*(x))
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
void run_case() {
int n, p;
string s;
cin >> n >> p >> s;
LL ans = 0;
if(p == 2) {
for(int i = 0; i < n; ++i) if((s[i]-'0') % 2 == 0) ans += i+1;
} else if(p == 5) {
for(int i = 0; i < n; ++i) if((s[i]-'0') % 5 == 0) ans += i+1;
} else {
map<int, int> mp;
mp[0]++;
int now = 0, idx = 1;
for(int i = n-1; i >= 0; --i) {
now = (now + (s[i]-'0')*idx) % p;
ans += mp[now]++;
idx = idx*10%p;
}
}
cout << ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cout.flags(ios::fixed);cout.precision(9);
//int t; cin >> t;
//while(t--)
run_case();
cout.flush();
return 0;
}
F:
本题要考虑到前者会对后者的影响，那我们也可以像E题一样，从后往前考虑，我们可以先进行排序使之有规律
假设现在有两个点(i,j(X_i<X_j)), (dp_x为移动第x个后剩下的不同集合的数量), 总集合为(s), 第(j)个移动后的集合为(s_1),若(X_i+D_i < X_j), 那么(i)移动后(j)不移动，则剩下的集合为(s-{i}, dp_i=dp_j+1)，若(X_i+D_i geq X_j), 则(j)也会跟着移动，剩下的集合就为(s_1-{1}), 假设(k)为满足(X_j+D_j < X_k), 则(dp_i=dp_k+1),若不激活第(i)个机器人,则(dp_i=dp_j)
将激活与不激活两种情况相加即可
#include<bits/stdc++.h>
using namespace std;
#define ms(x,y) memset(x, y, sizeof(x))
#define lowbit(x) ((x)&(-x))
#define sqr(x) ((x)*(x))
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const LL MOD = 998244353;
void run_case() {
int n; cin >> n;
vector<pll> a(n), sta;
vector<LL> dp(n+1);
for(auto &x: a) cin >> x.first >> x.second;
sort(a.begin(), a.end());
sta.emplace_back(n, 3e9);
dp[n] = 1;
for(int i = n-1; i >= 0; --i) {
while(sta.back().second < a[i].first + a[i].second) sta.pop_back();
dp[i] += dp[sta.back().first];
sta.emplace_back(i, a[i].first);
dp[i] = (dp[i] + dp[i+1]) % MOD;
}
cout << dp[0];
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cout.flags(ios::fixed);cout.precision(9);
//int t; cin >> t;
//while(t--)
run_case();
cout.flush();
return 0;
}