【补题记录】ICPC2023 Jinan
【补题记录】ICPC2023 Jinan
Contest Link: https://qoj.ac/contest/1472.
Problems: https://sua.ac/wiki/2023-icpc-jinan/contest-zh.pdf.
Solution: https://qoj.ac/download.php?type=attachments&id=1472&r=1.
A. Many Many Heads
const int N = 1e5 + 10;
int T;
string s;
void solve(){
read(T);
while(T--){
read(s);
int n = s.size();
#define cg(x) (x=='['||x==']'?1:0)
bool flg = 1;
for(int i = 0; i + 2 < n; ++ i){
if(cg(s[i]) == cg(s[i+1]) && cg(s[i+1]) == cg(s[i+2])){
flg = 0;
break;
}
}
int cnt = 0;
for(int i = 0; i + 1 < n; ++ i){
if(cg(s[i]) == cg(s[i+1])){
++ cnt;
}
}
if(cnt > 2){
flg = 0;
}
println_cstr((flg ? "Yes" : "No"));
}
}
B. Graph Partitioning 2
C. Turn on the Light 2
D. Largest Digit
int clc(int x){
int mx = -1;
while(x){
mx = max(mx, x%10);
x /= 10;
}
return mx;
}
void solve(){
int T, a, b, x, y;
read(T);
while(T--){
read(a, b, x, y);
if(b - a >= 10 || y - x >= 10){
println(9);
} else {
int mx = -1;
for(int i = a; i <= b; ++ i){
for(int j = x; j <= y; ++ j){
mx = max(mx, clc(i+j));
}
}
println(mx);
}
}
}
E. I Just Want... One More...
const int N = 1e5 + 10;
int T, n, m, tot = 1, hd[N*2], now[N*2], dep[N*2];
struct edge{
int eg, nx, ln;
} eg[N*7];
void add(int x, int y, int z){
eg[++tot] = { y, hd[x], z };
hd[x] = tot;
}
bool bfs(int s, int t){
for(int i = 0; i <= n + n + 1; ++ i){
dep[i] = 0;
now[i] = hd[i];
}
dep[s] = 1;
queue<int> q;
q.push(s);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = hd[x]; i; i = eg[i].nx){
int y = eg[i].eg, z = eg[i].ln;
if(!dep[y] && z){
dep[y] = dep[x] + 1;
q.push(y);
if(y == t){
return 1;
}
}
}
}
return 0;
}
int dfs(int x, int t, int fl){
if(x == t){
return fl;
}
int rs = fl;
for(int i = now[x]; i && rs; i = eg[i].nx){
int y = eg[i].eg, z = eg[i].ln;
now[x] = i;
if(dep[y] == dep[x] + 1 && z){
int k = dfs(y, t, min(z, rs));
if(!k){
dep[y] = 0;
}
eg[i].ln -= k;
eg[i^1].ln += k;
rs -= k;
}
}
return fl - rs;
}
int dinic(int s, int t){
int mf = 0, tmp = 0;
while(bfs(s, t)){
while(tmp = dfs(s, t, 1000)){
mf += tmp;
}
}
return mf;
}
vector<int> g[N*2], gg[N*2];
int kx[N*2], ky[N*2];
int mch[N*2], vis[N*2], viss[N*2];
void dfs(int x){
if(vis[x]){
return;
}
vis[x] = 1;
if(x <= n){
kx[x] = 1;
}
for(int i : gg[x]){
dfs(i);
}
}
void dfss(int x){
if(viss[x]){
return;
}
viss[x] = 1;
if(x > n){
ky[x] = 1;
}
for(int i : g[x]){
dfss(i);
}
}
void solve(){
read(T);
while(T--){
read(n, m);
map<pair<int, int>, int> mp;
int st = 0, ed = n + n + 1;
for(int i = 1; i <= n; ++ i){
add(st, i, 1);
add(i, st, 0);
add(i+n, ed, 1);
add(ed, i+n, 0);
}
for(int i = 1; i <= m; ++ i){
int x, y;
read(x, y);
if(mp[make_pair(x, y)]){
continue;
}
mp[make_pair(x, y)] = 1;
add(x, y+n, 1);
add(y+n, x, 0);
}
dinic(st, ed);
for(int x = 1; x <= n; ++ x){
for(int j = hd[x]; j; j = eg[j].nx){
int y = eg[j].eg;
if(y > n && !eg[j].ln){
mch[x] = y;
mch[y] = x;
g[x].push_back(y);
gg[y].push_back(x);
} else if(y > n){
g[y].push_back(x);
gg[x].push_back(y);
}
}
}
for(int i = 1; i <= n; ++ i){
if(!mch[i]){
dfs(i);
}
if(!mch[i+n]){
dfss(i+n);
}
}
int xc = 0, yc = 0;
for(int i = 1; i <= n; ++ i){
if(kx[i]){
++ xc;
}
if(ky[i+n]){
++ yc;
}
}
println((ll)xc * yc);
for(int i = 1; i <= tot; ++ i){
eg[i].eg = eg[i].ln = eg[i].nx = 0;
}
for(int i = 0; i <= n+n+1; ++ i){
kx[i] = ky[i] = 0;
vector<int> ().swap(g[i]);
vector<int> ().swap(gg[i]);
vis[i] = viss[i] = 0;
hd[i] = mch[i] = 0;
}
tot = 1;
}
}
F. Say Hello to the Future
G. Gifts from Knowledge
const int N = 3e6 + 10;
int T, n, m, pool[N*2], col[N];
string s;
bool flg = false;
vector<pair<int, int> > g[N];
const ll P = 1e9 + 7;
ll pw2[N];
void dfs(int x, int cl){
col[x] = cl;
for(auto i : g[x]){
int y = i.first, z = i.second;
if(col[y] != -1 && (col[y] ^ z ^ col[x])){
flg = true;
}
if(col[y] == -1){
dfs(y, cl ^ z);
}
}
}
void solve(){
memset(col, -1, sizeof(col));
pw2[0] = 1;
for(int i = 1; i < N; ++ i){
pw2[i] = pw2[i-1] * 2 % P;
}
read(T);
while(T--){
read(n, m);
int (&a)[n+5][m+5] = decltype(a)(pool);
for(int i = 1; i <= n; ++ i){
read(s);
for(int j = 1; j <= m; ++ j){
a[i][j] = s[j-1] - '0';
}
}
flg = false;
for(int i = 1, j = m; i <= j; ++ i, -- j){
int cnt = 0, x = 0, y = 0;
for(int k = 1; k <= n; ++ k){
cnt += a[k][i] + a[k][j];
if(a[k][i] == 1 && a[k][j] != 1){
if(x){
if(y == i){
g[k].emplace_back(x, 1);
g[x].emplace_back(k, 1);
} else {
g[k].emplace_back(x, 0);
g[x].emplace_back(k, 0);
}
} else {
x = k, y = i;
}
} else if(a[k][j] == 1 && a[k][i] != 1){
if(x){
if(y == j){
g[k].emplace_back(x, 1);
g[x].emplace_back(k, 1);
} else {
g[k].emplace_back(x, 0);
g[x].emplace_back(k, 0);
}
} else {
x = k, y = j;
}
}
}
if(cnt > 2){
flg = true;
break;
}
}
if(flg){
println(0);
} else {
int cc = 0;
for(int i = 1; i <= n; ++ i){
if(col[i] == -1){
dfs(i, 0);
++ cc;
}
}
if(flg){
println(0);
} else {
println(pw2[cc]);
}
}
for(int i = 1; i <= n; ++ i){
col[i] = -1;
vector<pair<int, int> > ().swap(g[i]);
}
}
}
H. Basic Substring Structure
I. Strange Sorting
const int N = 110;
int T, n, a[N], b[N];
void solve(){
read(T);
while(T--){
read(n);
for(int i = 1; i <= n; ++ i){
read(a[i]);
}
memcpy(b, a, sizeof(a));
int ans = 0;
for(int i = 1; i <= n; ++ i){
if(a[i] != i){
for(int j = n; j > i; -- j){
if(a[i] > a[j]){
++ ans;
sort(a + i, a + j + 1);
break;
}
}
}
}
println(ans);
memcpy(a, b, sizeof(b));
for(int i = 1; i <= n; ++ i){
if(a[i] != i){
for(int j = n; j > i; -- j){
if(a[i] > a[j]){
println(i, j);
sort(a + i, a + j + 1);
break;
}
}
}
}
}
}
J. Computational Intelligence
K. Rainbow Subarray
const int N = 1e6 + 10;
int T, n, a[N];
ll k, bit[N], bb[N], b[N];
void add(int x, ll v){
while(x <= n){
bit[x] += v;
x += x & -x;
}
}
void addd(int x, ll v){
while(x <= n){
bb[x] += v;
x += x & -x;
}
}
ll ask(int x){
ll res = 0;
while(x){
res += bit[x];
x -= x & -x;
}
return res;
}
ll askk(int x){
ll res = 0;
while(x){
res += bb[x];
x -= x & -x;
}
return res;
}
int ch[N][2], val[N], pri[N], siz[N], tot;
int root, x, y, z;
void update(int x){
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
int newnode(int v){
siz[++tot] = 1;
val[tot] = v;
pri[tot] = rand();
return tot;
}
int merge(int x, int y){
if(!x || !y){
return x + y;
}
if(pri[x] < pri[y]){
ch[x][1] = merge(ch[x][1], y);
update(x);
return x;
} else {
ch[y][0] = merge(x, ch[y][0]);
update(y);
return y;
}
}
void split(int p, int k, int &x, int &y){
if(!p){
x = y = 0;
return;
}
if(val[p] <= k){
x = p;
split(ch[p][1], k, ch[p][1], y);
} else {
y = p;
split(ch[p][0], k, x, ch[p][0]);
}
update(p);
}
int kth(int p, int k){
while(true){
if(k <= siz[ch[p][0]]){
p = ch[p][0];
} else if(k == siz[ch[p][0]] + 1){
return p;
} else {
k -= siz[ch[p][0]] + 1;
p = ch[p][1];
}
}
}
void ins(int k){
split(root, k, x, y);
root = merge(merge(x, newnode(k)), y);
}
void del(int k){
split(root, k, x, z);
split(x, k-1, x, y);
y = merge(ch[y][0], ch[y][1]);
root = merge(merge(x, y), z);
}
int getval(int k){
return val[kth(root, k)];
}
void solve(){
read(T);
while(T--){
read(n, k);
for(int i = 1; i <= n; ++ i){
read(a[i]);
a[i] -= i;
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int m = unique(b + 1, b + n + 1) - b - 1;
for(int i = 1; i <= n; ++ i){
a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
}
int ans = 1;
add(a[1], b[a[1]]);
addd(a[1], 1);
ins(a[1]);
for(int l = 1, r = 1; l <= n; ++ l){
r = max(r, l-1);
while(r < n){
add(a[r+1], b[a[r+1]]);
addd(a[r+1], 1);
ins(a[r+1]);
int rr = ((r+1) - l + 1) / 2 + 1;
int mid = getval(rr);
ll val = b[mid] * askk(mid-1) - ask(mid-1);
val += ask(m) - ask(mid) - b[mid] * (askk(m) - askk(mid));
if(abs(val) <= k){
ans = max(ans, (r+1) - l + 1);
++ r;
} else {
add(a[r+1], -b[a[r+1]]);
addd(a[r+1], -1);
del(a[r+1]);
break;
}
}
add(a[l], -b[a[l]]);
addd(a[l], -1);
del(a[l]);
}
println(ans);
for(int i = 1; i <= n; ++ i){
bit[i] = bb[i] = b[i] = 0;
}
for(int i = 1; i <= tot; ++ i){
ch[i][0] = ch[i][1] = siz[i] = val[i] = pri[i] = 0;
}
tot = root = 0;
}
}
L. Ticket to Ride
M. Almost Convex
const int N = 4e3 + 10;
const double eps = 1e-8;
int n, x[N], y[N], is[N], id[N];
int is0(double x){return (fabs(x)<eps?0:(x<0)?-1:1);}
double at[N];
struct Point{
double x,y;
int id;
Point(){}
Point(double x,double y):x(x),y(y){}
Point operator+(Point b){return Point(x+b.x,y+b.y);}
Point operator-(Point b){return Point(x-b.x,y-b.y);}
bool operator==(Point b){return is0(x-b.x)==0&&is0(y-b.y)==0;}
bool operator<(Point b){return is0(x-b.x)<0||(is0(x-b.x)==0&&is0(y-b.y)<0);}
}p[N],ch[N];
typedef Point Vector;
typedef Point point;
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double Dist(Point a,Point b){return hypot(a.x-b.x,a.y-b.y);}
int Andrew(int n){
int v=0,k;
sort(p,p+n);
n=unique(p,p+n)-p;
for(int i=0; i<n; ++i){
while(v>1 && is0(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<1) --v;
ch[v++]=p[i];
}
for(int i=n-2,k=v; i>=0; --i){
while(v>k && is0(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<1) --v;
ch[v++]=p[i];
}
return (n>1?v-1:v);
}
bool cmp1(point x, point y){
if(at[x.id] != at[y.id]){
return at[x.id] < at[y.id];
}
return x.x < y.x;
}
int qdr(point x){
if(x.x > 0 && x.y >= 0) return 1;
if(x.x <= 0 && x.y > 0) return 2;
if(x.x < 0 && x.y <= 0) return 3;
if(x.x >= 0 && x.y < 0) return 4;
}
bool cmp(point x, point y){
if(qdr(x) == qdr(y)){
return cmp1(x, y);
} else {
return qdr(x) < qdr(y);
}
}
int v;
int calc(int k){
int cnt = 0, ans = 0;
for(int i = 0; i < n; ++ i){
if(i == k){
continue;
}
ch[++cnt].x = x[i] - x[k] + eps;
ch[cnt].y = y[i] - y[k] + eps;
ch[cnt].id = i;
at[i] = atan2(ch[cnt].y, ch[cnt].x);
}
sort(ch + 1, ch + cnt + 1, cmp);
ch[cnt+1] = ch[1];
for(int i = 1; i <= cnt; ++ i){
if(is[ch[i].id] && is[ch[i+1].id]){
if(abs(id[ch[i].id] - id[ch[i+1].id]) == 1){
++ ans;
} else if(id[ch[i].id] == v && id[ch[i+1].id] == 1){
++ ans;
} else if(id[ch[i].id] == 1 && id[ch[i+1].id] == v){
++ ans;
}
}
}
return ans;
}
void solve(){
read(n);
for(int i = 0; i < n; ++ i){
read(x[i], y[i]);
p[i].x = x[i];
p[i].y = y[i];
p[i].id = i;
}
v = Andrew(n);
for(int i = 0; i < v; ++ i){
is[ch[i].id] = 1;
id[ch[i].id] = i + 1;
}
int ans = 1;
for(int i = 0; i < n; ++ i){
if(!is[i]){
ans += calc(i);
}
}
println(ans);
}