A. Local Extrema
枚举每个位置
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; sci(n);
vi A(n); for(int &x : A) sci(x);
int ret = 0;
for(int i = 1; i < n - 1; i++){
if(A[i]>A[i-1] and A[i]>A[i+1]) ret++;
if(A[i]<A[i-1] and A[i]<A[i+1]) ret++;
}
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
B. Buggy Robot
左右抵消，上下抵消，分别取(min)即可
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;
string s;
cin >> n >> s;
vi A(4,0);
for(int i = 0; i < n; i++){
if(s[i]=='L') A[0]++;
if(s[i]=='R') A[1]++;
if(s[i]=='D') A[3]++;
if(s[i]=='U') A[2]++;
}
cout << min(A[0],A[1]) * 2 + 2 * min(A[2],A[3]) << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
C. K-Dominant Character
二分答案，然后判断就好了
双指针判断一下每个长度为(mid)的串中出现的字符
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];
int cnt[26];
bool app[26];
void solve(){
scanf("%s",s+1);
int n = strlen(s+1);
auto check = [&](int m){
memset(cnt,0,sizeof(cnt));
for(int i = 0; i < 26; i++) app[i] = true;
for(int i = 1; i < m; i++) cnt[s[i]-'a']++;
for(int i = m; i <= n; i++){
cnt[s[i]-'a']++;
for(int j = 0; j < 26; j++) if(!cnt[j]) app[j] = false;
cnt[s[i-m+1]-'a']--;
}
for(int i = 0; i < 26; i++) if(app[i]) return true;
return false;
};
int l = 1, r = n;
while(l<=r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
cout << l << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
D. Almost Identity Permutations
枚举一下错排的数量就好了，数据明显可以出大点
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;
LL C(LL n, LL k){
LL ret = 1;
for(int i = n; i >= max(0ll,n - k + 1); i--) ret *= i;
for(int i = 1; i <= k; i++) ret /= i;
return ret;
}
int f[5] = {1,0,1,2,9};
void solve(){
int n, k;
sci(n); sci(k);
LL ret = 0;
for(int i = 0; i <= k; i++) ret += C(n,i) * f[i];
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
E. Maximum Subsequence
把所有数分成两部分，然后每个部分(2^x)找出所有可以得到的数
然后枚举一部分，在另一部分里(lower\_bound)找使得答案最大的
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, m;
void solve(){
sci(n); sci(m);
vi A(n);
for(int &x : A) sci(x);
if(n==1){
cout << A[0]%m << endl;
return;
}
int x = n / 2, y = n - n / 2;
vi va(x), vb(y);
for(int i = 0; i < x; i++) va[i] = A[i];
for(int i = x; i < n; i++) vb[i-x] = A[i];
set<int,greater<int> > s1,s2;
for(int msk = 0; msk < (1 << x); msk++){
int tot = 0;
for(int bit = 0; bit < x; bit++) if(msk>>bit&1) tot = (tot + va[bit]) % m;
s1.insert(tot);
}
for(int msk = 0; msk < (1 << y); msk++){
int tot = 0;
for(int bit = 0; bit < y; bit++) if(msk>>bit&1) tot = (tot + vb[bit]) % m;
s2.insert(tot);
}
int ret = 0;
for(int x : s1) cmax(ret,x);
for(int x : s2) cmax(ret,x);
for(int x : s1){
int d = m - 1 - x;
auto p = s2.lower_bound(d);
if(p==s2.end()) continue;
cmax(ret,x+*p);
}
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
F. Connecting Vertices
令(dp[i][j])表示(i,j)已经有连边的情况下，(i+1)到(j-1)区间的点和(i)或(j)相连的方案数
枚举(i)连的位置(x)，这时候剩下的(x)到(j)区间的点还是有可能连到(i)
所以我们假设我们(i)连的(x)是下标最大的，之后的(x)到(j)之间不存在和(i)连的了
这时候转移还会出现重复，枚举了和(i)连的还有和(j)连的会出现重复统计
这里考虑把状态变为(dp[i][j][flag])其中(flag)表示是否还能和(i)连边
那么枚举和(j)连的(x)的时候，(i)到(x)区间内的点就不能再和(i)连了，因为这个在枚举(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 = 507;
const int MOD = 1e9+7;
int n, A[MAXN][MAXN], f[MAXN][MAXN][2];
int dp(int l, int r, int flag){
if(f[l][r][flag]!=-1) return f[l][r][flag];
if(l+1==r) return f[l][r][flag] = 1;
f[l][r][flag] = 0;
if(flag==1) for(int i = l + 1; i < r; i++) if(A[l][i]) f[l][r][flag] = (f[l][r][flag] + 1ll * dp(l,i,1) * dp(i,r,1)) % MOD;
for(int i = l + 1; i < r; i++) if(A[r][i]) f[l][r][flag] = (f[l][r][flag] + 1ll * dp(l,i,0) * dp(i,r,1)) % MOD;
return f[l][r][flag];
}
void solve(){
sci(n);
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) sci(A[i][j]);
for(int i = 1; i <= n; i++) A[i][0] = A[0][i] = A[n][i];
memset(f,255,sizeof(f));
cout << dp(0,n,0) << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
G. Xor-MST
相同的值的肯定可以先合并，所以先去重
然后把每个点都放到字典树里去，字典树应该是恰好有(n-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;
int n;
int tot, ch[MAXN<<5][2], l[MAXN<<5], r[MAXN<<5], root;
vi A;
LL ret;
void ins(int &rt,int x, int dep, int pos){
if(!rt) rt = ++tot;
if(l[rt]==-1) l[rt] = r[rt] = pos;
else cmin(l[rt],pos), cmax(r[rt],pos);
if(dep==-1) return;
ins(ch[rt][x>>dep&1],x,dep-1,pos);
}
int query(int rt, int x, int dep){
if(dep==-1) return 0;
if(ch[rt][x>>dep&1]) return query(ch[rt][x>>dep&1],x,dep-1);
else return query(ch[rt][(x>>dep&1)^1],x,dep-1) + (1 << dep);
}
void dfs(int rt, int dep){
if(dep==-1) return;
if(ch[rt][0]) dfs(ch[rt][0],dep-1);
if(ch[rt][1]) dfs(ch[rt][1],dep-1);
if(ch[rt][0]==0 or ch[rt][1]==0) return;
int lenl = r[ch[rt][0]] - l[ch[rt][0]];
int lenr = r[ch[rt][1]] - l[ch[rt][1]];
int minn = INT_MAX;
if(lenl<lenr){
for(int i = l[ch[rt][0]]; i <= r[ch[rt][0]]; i++){
int x = query(ch[rt][1],A[i],dep-1);
cmin(minn,x);
}
}else{
for(int i = l[ch[rt][1]]; i <= r[ch[rt][1]]; i++){
int x = query(ch[rt][0],A[i],dep-1);
cmin(minn,x);
}
}
ret += minn + (1 << dep);
}
void solve(){
sci(n);
A.resize(n);
for(int &x : A) sci(x);
sort(all(A));
A.erase(unique(all(A)),A.end());
memset(l,255,sizeof(l)); memset(r,255,sizeof(r));
for(int i = 0; i < A.size(); i++) ins(root,A[i],30,i);
dfs(root,30);
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}