A. Chores
把最大的换掉
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e5+7;
void solve(){
int n, m, k;
sci(n); sci(m); sci(k);
vi A(n); for(int &x : A) sci(x);
cmin(m,n);
for(int i = n - 1, j = 0; j < m; j++, i--) cmin(A[i],k);
cout << accumulate(all(A),0) << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
B. Balanced Substring
令(s)为前缀和
就是要找(s_r-s_{l-1}=frac {r-l+1}{2})
那就是(2s_r-r = 2s_{l-1}-(l-1))
维护每个值最早出现的位置
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e5+7;
char s[MAXN];
void solve(){
int n; cin >> n;
cin >> s + 1;
map<int,int> msk;
int pre = 0;
msk[0] = 0;
int ret = 0;
for(int i = 1; i <= n; i++){
pre += s[i] - '0';
if(msk.count(2*pre-i)) cmax(ret,i-msk[2*pre-i]);
else msk[2*pre-i] = i;
}
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
C. Strange Game On Matrix
每一列单独考虑，枚举(q)的起点
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e5+7;
int A[111][111];
void solve(){
int n, m, k;
sci(n); sci(m); sci(k);
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sci(A[i][j]);
int ret = 0, exc = 0;
for(int i = 1; i <= m; i++){
vi pos;
for(int j = 1; j <= n; j++) if(A[j][i]==1) pos << j;
if(pos.empty()) continue;
int tmpret = 0, tmpexc = 0;
for(int j = 0; j < (int)pos.size(); j++){
int sum = 0;
for(int kk = j; kk < pos.size(); kk++){
if(pos[kk] - pos[j] >= k) break;
sum++;
}
if(sum > tmpret) tmpret = sum, tmpexc = j;
}
ret += tmpret; exc += tmpexc;
}
cout << ret << ' ' << exc << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
D. Merge Sort
递归下去，如果还需要调用的话，就把当前数字区间左右互换然后分别调用，否则直接不换分别调用
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e5+7;
int n, k, A[MAXN];
void merge(int L, int R, int numl, int numr, int &T){
if(L+1==R){
A[L] = numl;
return;
}
int mid = (L + R) >> 1;
if(T>0) T-=2, merge(L,mid,numr-mid+L,numr,T), merge(mid,R,numl,numr-mid+L,T);
else merge(L,mid,numl,numl+mid-L,T), merge(mid,R,numl+mid-L,numr,T);
}
void solve(){
sci(n); sci(k); k--;
merge(0,n,1,n+1,k);
if(k!=0) cout << -1 << endl;
else for(int i = 0; i < n; i++) cout << A[i] << ' ';
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
E. Awards For Contestants
先所有数从大到小排序
枚举前两个的位置然后可以确定下一个位置的可行范围，然后(ST)表找最大的位置即可
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 3333;
int n, d1, d2, d3, x, y, z, ret[MAXN];
pii A[MAXN];
pii st[MAXN][20];
void solve(){
sci(n); for(int i = 1; i <= n; i++) sci(A[i].first), A[i].second = i;
sort(A+1,A+1+n,greater<pii>());
for(int i = 1; i <= n; i++) st[i][0] = make_pair(A[i].first-A[i+1].first,i);
for(int j = 1; (1 << j) <= n; j++) for(int i = 1; i + (1 << j) - 1 <= n; i++){
if(st[i][j-1].first > st[i+(1<<(j-1))][j-1].first) st[i][j] = st[i][j-1];
else st[i][j] = st[i+(1<<(j-1))][j-1];
}
auto query = [&](int l, int r){
int d = (int)log2(r - l + 1);
if(st[l][d].first>st[r-(1<<d)+1][d].first) return st[l][d];
else return st[r-(1<<d)+1][d];
};
d1 = d2 = d3 = -1;
for(int i = 1; i <= n - 2; i++) for(int j = i + 1; j <= n - 1; j++){
int a = i, b = j - i;
if(min(a,b) * 2 < max(a,b)) continue;
int l = 1, r = n - j;
cmax(l,(max(a,b)+1)/2);
cmin(r,min(a,b)*2);
if(l>r) continue;
l += j; r += j;
auto p = query(l,r);
int t1 = A[i].first - A[i+1].first, t2 = A[j].first - A[j+1].first, t3 = p.first;
if(t1>d1 or (t1==d1 and t2>d2) or (t1==d1 and t2==d2 and t3>d3)){
d1 = t1; d2 = t2; d3 = t3;
x = i; y = j; z = p.second;
}
}
for(int i = 1; i <= x; i++) ret[A[i].second] = 1;
for(int i = x + 1; i <= y; i++) ret[A[i].second] = 2;
for(int i = y + 1; i <= z; i++) ret[A[i].second] = 3;
for(int i = z + 1; i <= n; i++) ret[A[i].second] = -1;
for(int i = 1; i <= n; i++) cout << ret[i] << ' ';
cout << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
F. Forbidden Indices
后缀自动机，插入一个字符的时候如果这个位置末尾被禁止的话，当前点的(right)集合大小设为(0)，否则设为(1)，然后就是计算每个状态节点的(len[i]cdot right[i])最大值了
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 1e6+7;
char s[MAXN], t[MAXN];
struct SAM{
int len[MAXN],link[MAXN],ch[MAXN][26],cnt[MAXN],tot,last;
int buc[MAXN], sa[MAXN];
SAM(){ link[0] = -1; }
void extend(int c, int ct){
int np = ++tot, p = last;
len[np] = len[last] + 1; cnt[np] = ct;
while(p!=-1 and !ch[p][c]){
ch[p][c] = np;
p = link[p];
}
if(p==-1) link[np] = 0;
else{
int q = ch[p][c];
if(len[p]+1==len[q]) link[np] = q;
else{
int clone = ++tot;
len[clone] = len[p] + 1;
link[clone] = link[q];
memcpy(ch[clone],ch[q],sizeof(ch[q]));
link[np] = link[q] = clone;
while(p!=-1 and ch[p][c]==q){
ch[p][c] = clone;
p = link[p];
}
}
}
last = np;
}
void rua(){
for(int i = 1; i <= tot; i++) buc[i] = 0;
for(int i = 1; i <= tot; i++) buc[len[i]]++;
for(int i = 1; i <= tot; i++) buc[i] += buc[i-1];
for(int i = tot; i >= 1; i--) sa[buc[len[i]]--] = i;
LL ret = 0;
for(int i = tot; i >= 1; i--){
int u = sa[i];
cnt[link[u]] += cnt[u];
}
for(int i = 1; i <= tot; i++) cmax(ret, 1ll * cnt[i] * len[i]);
cout << ret << endl;
}
}sam;
void solve(){
int len;
cin >> len >> s >> t;
for(int i = 0; i < len; i++) sam.extend(s[i]-'a',(t[i]-'0')^1);
sam.rua();
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}