首页 > 其他分享 >【补题记录】ICPC2023 Jinan

【补题记录】ICPC2023 Jinan

时间：2024-01-21 20:33:25浏览次数：22  
标签：ICPC2023 cnt ch return int Jinan read 补题 col

【补题记录】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...

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);
}

标签：ICPC2023,cnt,ch,return,int,Jinan,read,补题,col
From： https://www.cnblogs.com/KiharaTouma/p/17978297/ICPC2023-Jinan

相关文章

  • Codeforces Round 920 (Div. 3)补题D~F
    CodeforcesRound920(Div.3)D.思路取a最大和c最小的或c最小和a最大的匹配ac代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;consti64inf=8e18;typedefpair<int,int>pii;constintmod=1e9+7;constintN=2e6+10;voidso......
  • 1.8日考试补题
    没有打，但感觉\(A,B,C\)都很简单。可能是黑色题面自动降智？\(A\)没想到这道题还有两个人没做出来做法用一个小根堆维护静态前缀第\(k\)大的值就行了。具体地如果当前堆中元素小于\(k\)个，那么就直接放入。如果当前堆中元素大于\(k\)个，那么就判断一下如果堆顶元素是否......
  • CF455A补题
    思路取与不取的问题，用dp就行ac代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;consti64inf=8e18;typedefpair<int,int>pii;constintN=1e5+10;i64dp[N];voidsolve(){intn;cin>>n;map<int,in......
  • CF1374D（补题）
    思路用map记录有多少个相同的(a[i]%k)的值，然后利用等差数列求和公式求最大值就行。比如a=[6,7,5,9,50,31]，且k=3。a[i]%k-->a=[0,1,2,0,2,1]。x要分别为25才能使得a[2]和a[6]满足题目要求ac代码#include<bits/stdc++.h>usingnamespacestd;using......
  • atcoder补题计划
    DPABC275EABC274DABC274EABC271EABC270DABC266D状态机模型ABC265Emap存状态+步骤型遍历（注意DP顺序）+复杂度证明ABC262D关于数字的DP，将一类数字分成一个状态加粗样式ABC261D没啥好说的看题目写DPABC253E关于数字的DPABC251E状态机DPABC197E在一维轴上行走的DP......
  • 补题--I题
    I.Letters算法:前缀和+二分(lower_bound)不开ll见祖宗#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;llt,n,m;constintN=2e5+10;#defineeps(a,b)for(inti=a;i<=b;i++)llb[N],s[N];intmain(){ios::sync_with_stdio(false);cin.tie()......
  • 补题日志
    补题日志**Codeforcesrating：1770**goal：1900ATcoderrating：1254goal：1600CodeforcesRound915(Div.2)D不难发现，设当前排列为\(q_1,q_2\dotsq_n\)，把\(q_1\)移到末尾，造成的影响有：对于前缀中\(\text{mex}_i<q_1\)的\(i\)，移动后不改变它的值。对于前......
  • ICPC2023 杭州站游记
    Day-2周五早八的飞机，周四晚上就润去机场旁边的酒店了。队长说昨晚没睡好，不到九点就先睡了，但是十二点左右就睡醒了。睡醒之后又点了外卖吃，这下完全不困了，玩手机玩到三点顶不住就睡了。和队长聊天，目标都是守银。Day-1本来定的5:45的闹钟，5:43刚好醒来，简单收拾一下就出发了，......
  • ICPC2023重庆市赛游记
    人生总是由遗憾构成的Day-1比赛前2天，由于dlh和fq需要考四级，所以我提前到重庆来"旅游"。来的路上vp了一场codeforsediv.2，1.5h写了3题，手感不是很好（也有可能题太阴间）来到重庆，天下着小雨，但是我还是开始我的CityWalk--ChongQing，我循着5年前的足迹走在解放碑......
  • Acwing秋季每日一题补题---搜索字符串
    搜索字符串题目链接思路：字符串哈希+滑动窗口当然因为符合题意的子串会重复，所以我们要考虑去重的问题代码：#include<bits/stdc++.h>usingnamespacestd;#defineintunsignedlonglongconstintN=2e5+10;constintP=131;chara[N],b[N];//字符串intcnt[26];//统......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99