C - 2D Plane 2N Points
把能连边的点找到然后跑二分图匹配即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define space putchar(' ')
#define enter putchar('
')
#define mp make_pair
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int g[105][105];
int a[105],b[105],c[105],d[105],N,matk[105];
bool vis[105];
bool match(int u) {
for(int i = 1 ; i <= 100 ; ++i) {
if(g[u][i] && !vis[i]) {
vis[i] = 1;
if(!matk[i] || match(matk[i])) {
matk[i] = u;
return true;
}
}
}
return false;
}
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) {read(a[i]);read(b[i]);}
for(int i = 1 ; i <= N ; ++i) {read(c[i]);read(d[i]);}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
if(a[i] < c[j] && b[i] < d[j]) g[i][j] = 1;
}
}
int ans = 0;
for(int i = 1 ; i <= N ; ++i) {
memset(vis,0,sizeof(vis));
if(match(i)) ++ans;
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
D - Two Sequences
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define space putchar(' ')
#define enter putchar('
')
#define mp make_pair
#define MAXN 200005
#define pb push_back
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N;
int a[MAXN],b[MAXN];
int val[2][MAXN],len[2];
bool check(int p) {
len[0] = len[1] = 0;
for(int i = 1 ; i <= N ; ++i) {
if(a[i] & (1 << p)) val[1][++len[1]] = a[i] & (1 << p) - 1;
else val[0][++len[0]] = a[i] & (1 << p) - 1;
}
sort(val[1] + 1,val[1] + len[1] + 1);
sort(val[0] + 1,val[0] + len[0] + 1);
int64 res = 0;
for(int i = 1 ; i <= N ; ++i) {
int t = (1 << p) - (b[i] & (1 << p) - 1);
int p0,p1;
p0 = lower_bound(val[0] + 1,val[0] + len[0] + 1,t) - val[0] - 1;
p1 = lower_bound(val[1] + 1,val[1] + len[1] + 1,t) - val[1] - 1;
if(b[i] & (1 << p)) {res += p0;res += len[1] - p1;}
else {res += p1;res += len[0] - p0;}
}
return res & 1;
}
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) {read(a[i]);}
for(int i = 1 ; i <= N ; ++i) {read(b[i]);}
int ans = 0;
for(int i = 28 ; i >= 0 ; --i) {
if(check(i)) ans |= (1 << i);
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
E - Both Sides Merger
显然是只能从(f[i] = max(f[i - 2k] + a[i]))转移过来
记录一下前一个从哪里转移过来，删一段区间的时候从中间开始删
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define enter putchar('
')
#define space putchar(' ')
#define MAXN 1005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N;
int64 a[MAXN],dp[MAXN];
int fr[MAXN];
int op[MAXN],tot;
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) read(a[i]);
int64 ans = a[1];
for(int i = 1 ; i <= N ; ++i) {
dp[i] = a[i];fr[i] = 0;
for(int j = 2 ; j <= i ; j += 2) {
if(dp[i - j] + a[i] > dp[i]) {
dp[i] = dp[i - j] + a[i];
fr[i] = i - j;
}
}
ans = max(ans,dp[i]);
}
out(ans);enter;
int a = N;
for(int i = N ; i >= 1 ; --i) {
if(dp[i] == ans) {
for(int j = N ; j > i ; --j) {op[++tot] = j;--a;}
int t = i,c = 0;
while(fr[t]) {
++c;
int mid = (fr[t] + 1 + a - c) >> 1;
for(int j = mid ; j > fr[t] ; --j) {op[++tot] = j;}
a -= (a - c - fr[t]);
t = fr[t];
}
for(int j = 1 ; j < t ; ++j) op[++tot] = 1;
break;
}
}
out(tot);enter;
for(int i = 1 ; i <= tot ; ++i) {
out(op[i]);enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
F - Two Faced Edges
mdzz，我不会卡常，走了
生气了