C
//观察数据得知是一维,发现性质非零和点的区间都可以。怎么dp,找每一次零和点,零和点间就是本次获得的
//并且前n次零和由dp【q】来,逆序方便处理
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
ll x;
cin >> n >> x;
vector<ll> a(n + 1), prefix(n + 1, 0);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
prefix[i] = prefix[i - 1] + a[i];
}
vector<ll> dp(n + 2, (ll)0);
ll result = 0;
for (int i = n - 1; i >= 0; --i) {
int left = i + 1, right = n + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (prefix[mid] - prefix[i] > x) {
right = mid;
} else {
left = mid + 1;
}
}
dp[i] = dp[left] + (left - i - 1);
result += dp[i];
}
cout << result << '\n';
}
return 0;
}
C
//数据2e5状态这么多,一看就是线性
//分析去掉一个人后对前面人的影响,似乎没有,对后面人的影响,发现被迫选择的人可能会有影响
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
int nm = n + m + 1;
vector<long long> a0(nm, 0), a1(nm, 0);
for(int i = 0; i < nm; i++) cin >> a0[i];
for(int i = 0; i < nm; i++) cin >> a1[i];
vector<int> op(nm, 0);
int bad = -1, badType = -1;
int cur[2] = {0, 0};
long long total_sum = 0;
for(int i = 0; i < n + m; i++) {
int curType = 0;
if(a0[i] < a1[i]){
curType = 1;
}
if(cur[curType] == ((curType == 0) ? n : m)){
curType = 1 - curType;
if(bad == -1){
bad = i;
badType = 1 - curType;
}
}
op[i] = curType;
if(curType == 0){
total_sum += a0[i];
cur[0]++;
}
else{
total_sum += a1[i];
cur[1]++;
}
}
for(int i = 0; i < n + m; i++) {
long long temp = total_sum - (op[i] == 0 ? a0[i] : a1[i]);
if(bad != -1 && i < bad && op[i] == badType){
if(badType == 0){
temp += a0[bad] - a1[bad] + a1[nm-1];
}
else{
temp += a1[bad] - a0[bad] + a0[nm-1];
}
}
else{
if(op[i] == 0){
temp += a0[nm-1];
}
else{
temp += a1[nm-1];
}
}
cout << temp << " ";
}
cout << total_sum << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
B
//切道水题放松
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int n;
cin >> n;
vector<ll> a(n+1), b(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
ll sum = 1;
for (int i = 0; i < n; i++) {
cin >> b[i];
sum += abs(a[i] - b[i]);
}
cin >> b[n];
// cout<<sum<<"\n";
ll t=1e9;
for (int i = 0; i < n; i++){
ll mmax=max(a[i],b[i]);
ll mmin=min(a[i],b[i]);
if(b[n]<=mmax&&b[n]>=mmin){
t=0;
break;
}else if(b[n]<mmin){
t=min(t,mmin-b[n]);
}else{
t=min(t,b[n]-mmax);
}
}
cout<<sum+t<<"\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
A
//暴力枚举不行!
//任敌杀戮不行。
//那就构造极限反例,k个字母全部要出现,取刚集满k的的字母放进ans,
//最后取一个缺的,不满足n个要随便输出点(忘记这个东西,一直卡住)
//思维路程
//我是尝试构造一个反例,比如对于k=3;就说abc,当n等于三的时候,
//最短的m应该是abcabcabc这样子才有全部子序列,但是对于题目给定的序列,
//我们就是要检查比如aabcabcbba,我们先检查字符串到哪里会集齐k然后模拟删去前缀
//同时把最后出现的字母放进答案,abcbba剩下,继续bba发现此时不符合,停止截断,
//然后我们发现只有第一个和第二个两个满足三个出现,
//但是n'等于3,错误,输出ans和缺的,如果仍不满足n就不断输出任意字母
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k, m;
string s;
cin >> n >> k >> m;
cin >> s;
int l = 0;
int cnt_segments = 0;
map<char, int> freq;
vector<char> ans;
while (l < m) {
freq.clear();
int r = l;
while (r < m) {
freq[s[r]]++;
r++;
if (freq.size() == k){ans.push_back(s[r-1]);break;}
}
if (freq.size() < k) break;
cnt_segments++;
l = r;
}
if (cnt_segments >= n) {
cout << "YES\n";
} else {
cout << "NO\n";
for(auto c:ans){
cout<<c;
}
freq.clear();
for(int i=l;i<m;i++){
freq[s[i]]++;
}
for(int i=0;i<k;i++){
if(!freq['a'+i]){
cout<<char('a'+i);
break;
}
}
while(ans.size()+1<n){
cout<<'a';
n--;
}
cout << "\n";
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}