本人能力有限,有些题做不来,也在补,求大佬指点。也欢迎大家讨论。

A World Final? World Cup! (I)

简单题,根据题意模拟,记录现有情况和还剩多少场可以踢。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int a[2][2];
char ch[100];
int main() {
	int T = read();
	while(T--) {
		int f = 0;
		cin >> ch + 1;
		a[0][0]=a[1][0]=0;
		a[0][1]=a[1][1]=5;
		for(int i = 1;i <= 10;i++) {
			if(ch[i] == '1') {
				a[i & 1][0] += 1;
				a[i & 1][1] -= 1;
			}
			else {
				a[i & 1][1] -= 1;				
			}
			if(a[i & 1][0] > a[(i - 1) & 1][1] + a[(i - 1) & 1][0]) {
				f = 1;
				cout << i << endl;
				break;
			}
			if(a[(i - 1) & 1][0] > a[i & 1][1] + a[i & 1][0]) {
				f = 1;
				cout << i << endl;
				break;
			}
		}
		if(!f) {
			cout << "-1" << endl;
		}
	}
}

B World Final? World Cup! (II)

留坑

C 现在是,学术时间 (I)

简单题,根据有这句话至少H篇论文的引用量大于等于H"这一命题成立的最大的H所以其实一篇论文最大的贡献也就是1,考虑到论文数目和人数是一样的,每个人分配一篇论文就好了,记录0的个数。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int main() {
	int T = read();
	while(T--) {
		int n = read();
		int ans = 0;
		for(int i = 1;i <= n;i++) {
			ans += (read() != 0);
		}
		cout << ans << endl;
	}
}

D 现在是,学术时间 (II)

简单题,给出的初始矩形,大体把平面分为了四个部分每一个部分讨论一下取最大值就好了。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int x,y,a,b,tot;
int main() {
	int T = read();
	while(T--) {
		x = read();y = read();a = read();b = read();
		tot = x * y;
		if(a <= x && b <= y) {
			int res = max(max(a*b,(y-b)*a),max((y-b)*(x-a),(x-a)*b));
			cout << 1.0 * res / tot << endl;
		}
		if(a <= x && b > y) {
			double ans = 0;
			ans = max(ans,y * a * 1.0 / (x * y + (b - y) * a));
			ans = max(ans,y * (x - a) * 1.0 / (x * y + (b - y) * (x - a)));
			cout << ans << endl;
		}
		if(a > x && b <= y) {
			swap(x,y);swap(a,b);
			double ans = 0;
			ans = max(ans,y * a * 1.0 / (x * y + (b - y) * a));
			ans = max(ans,y * (x - a) * 1.0 / (x * y + (b - y) * (x - a)));	
			cout << ans << endl;		
		}
		if(a > x && b > y) {
			cout << 1.0 * (x * y) / (a * b) << endl;;			
		}
	}
}

E 鸡算几何

中档题,主要题意就是说,是否进行了翻转操作。对于这个我们最好的办法就是判断叉积的正负。但是要选取一个标准,我这里选取的是长边向短边做叉积,要注意等腰的图形翻转依旧不能判断,需要特判。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
struct Tri{
	int rnk[4];
	double id[4][3];
	double val[100];
	int top;
	double pd[100];
	bool cmp(int x,int y) {
		return pd[x] < pd[y];
	}
	double dist(double x,double y,double a,double b) {
		return sqrt((x-a)*(x-a)+(b-y)*(b-y));
	}
	double clac(int a,int b,int c) {
		double x = id[b][0] - id[a][0],y = id[b][1] - id[a][1];
		double X = id[c][0] - id[a][0],Y = id[c][1] - id[a][1];
		return x * Y - y * X;
	}
	void solve() {
		for(int i = 0;i < 3;i++) {
			int tot = 0;
			for(int j = 0;j < 3;j++) rnk[j] = j;
			for(int j = 0;j < 3;j++) {
				pd[tot++] = dist(id[i][0],id[i][1],id[j][0],id[j][1]);
			}
			for(int j = 0;j < 3;j++){
				for(int k = j + 1;k < 3;k++){
					if(pd[rnk[j]]>pd[rnk[k]]) swap(rnk[j],rnk[k]);
				}
			}
//			cout << "Woce nima " << endl;
//			for(int i = 0;i < 3;i++) cout << pd[rnk[i]] <<" ";
//			cout << " ce " << endl; 
			
			val[++top] = clac(i,rnk[1],rnk[2]);
		}
		sort(val + 1,val + 1 + top);
	}
	bool caoni() {
		if(fabs(dist(id[0][0],id[0][1],id[1][0],id[1][1])-dist(id[2][0],id[2][1],id[1][0],id[1][1])) < 1e-8) {
			return 1;
		}
		return 0;
	}
}a,b;
int main() {
	int T;cin >> T;
	while(T--) {
		for(int i = 0;i < 3;i++) {
			for(int j = 0;j < 2;j++) {
				cin >> a.id[i][j];
			}
		}
		for(int i = 0;i < 3;i++) {
			for(int j = 0;j < 2;j++) {
				cin >> b.id[i][j];
			}
		}
		a.solve();b.solve();
		if(a.caoni()) {
			printf("NO\n");
		}
		else {
			int f = 0;
			for(int i= 1;i <= a.top;i++) {
//				cout <<"woc:: "<< a.val[i] <<" " <<  b.val[i] << endl;
				if(fabs(a.val[i] - b.val[i]) > 1e-8) {
					f = 1;
				}
			}
			if(!f) {
				cout << "NO" << endl;
			}
			else cout << "YES" << endl;			
		}
		a.top = b.top = 0;
	}
}

F 鸡玩炸蛋人

中档题,如果没有下蛋的要求,那么就是输出每个连通块的大小的平方。有下单的要求的话,我们容易知道,如果两个需要下单的地方不在一个连通块,那么答案显然是0。那么现在就是考虑一个连通块内的下蛋地方有什么影响,因为可以选择下蛋和不下蛋,所以其实完全没有影响。我们可以把连通块抽离出一棵树,先去叶节点下蛋便是。所以答案是下蛋连通块大小的平方,用并查集维护。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 3e5 + 10;
int n,m;
int f[N],si[N],u,val[N];
int find(int x) {
	if(f[x] == x) return x;
	else return f[x] = find(f[x]);
}
int main() {
	n = read();m = read();
	for(int i = 1;i <= n;i++) f[i] = i,si[i] = 1;
	for(int i = 1;i <= m;i++) {
		int a = read(),b = read();
		a = find(a);
		b = find(b);
		if(a == b) continue;
		f[a] = b;si[b] += si[a];
	}
	for(int i = 1;i <= n;i++) {
		val[i] = read();
		if(val[i]) u = i;
	}
	ll ans = 0;
	if(!u) {
		for(int i = 1;i <= n;i++) {
			if(find(i) == i) {
//				cout << i << " " << find(i) << " " << si[i] << endl;
				ans += si[i] * 1ll * si[i];
			}
		}
		cout << ans << endl;		
	}
	else {
		for(int i = 1;i <= n;i++) {
			if(val[i] && find(i) != find(u)) {
				cout << "0" << endl;
				return 0;
			}
		}
		u = find(u);
		ll ans = si[u] * 1ll * si[u];
		cout << ans << endl;
	}
	return 0;
}

G 鸡格线

中档题,有根号的区间操作,很容易想到以前做的一道线段树的题目。性质利用的是根号操作收敛的非常快。但是这道题有系数10,我们通过打表可以知道所有的数字通过这个操作,只会收敛于0,99,100这三个数字,所以我们线段树维护一下区间这三个数字的个数就好。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int f(ll x) {
	return int(10 * sqrt(x) + 0.5);
}
const int N = 5e5 + 10;
ll m99[N],m100[N],m0[N],t[N],n,a[N];
void build(ll u,ll l,ll r) {
	if(l == r) {
		t[u] = a[l];
		if(t[u] == 0) m0[u] = 1;
		if(t[u] == 99) m99[u] = 1;
		if(t[u] == 100) m100[u] = 1;
		return ;
	}
	ll mid = l + r >> 1;
	build(u<<1|1,mid + 1,r);build(u<<1,l,mid);
	t[u]=t[u<<1]+t[u<<1|1];
	m0[u]=m0[u<<1]+m0[u<<1|1];
	m100[u]=m100[u<<1]+m100[u<<1|1];
	m99[u]=m99[u<<1]+m99[u<<1|1];
}
void ask(ll u,ll l,ll r,ll L,ll R,ll k) {
	if(L <= l && r <= R && (m0[u]+m99[u]+m100[u]==r-l+1)) return;
	if(r < L || R < l) return;
	if(l == r) {
		for(ll i = 1;i <= k;i++) {
			t[u] = f(t[u]);
			if(t[u] == 99 || t[u] == 100 || t[u] == 0) break;
		}
		if(t[u] == 0) m0[u] = 1;
		if(t[u] == 99) m99[u] = 1;
		if(t[u] == 100) m100[u] = 1;
		return ;
	}
	ll mid = l + r >> 1;
	ask(u<<1|1,mid + 1,r,L,R,k);ask(u<<1,l,mid,L,R,k);
	t[u]=t[u<<1]+t[u<<1|1];
	m0[u]=m0[u<<1]+m0[u<<1|1];
	m100[u]=m100[u<<1]+m100[u<<1|1];
	m99[u]=m99[u<<1]+m99[u<<1|1];
}
int main() {
	n = read();ll T = read();
	for(ll i = 1;i <= n;i++) a[i] = read();
	build(1,1,n);
	while(T--) {
		ll opt = read();
		if(opt == 1) {
			ll l = read(),r = read(),k = read();
			ask(1,1,n,l,r,k);
		}
		else {
			cout << t[1] << endl;
		}
	}
}

H 本题主要考察了DFS

简单题,考虑到拼图的特性,我们并不在意缺少的位置,我们只关心有几个凹陷和凸起。所以记录1,2的个数就好。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 40;
int n,vis[N * N],id[N][N],ans;
char ch[N * N][6];
int main() {
	int T = read();
	while(T--) {
		n = read();
		ans = 0;
		for(int i = 1;i <= n * n - 1;i++) {
			cin >> ch[i];
			for(int j = 0;j < 4;j++) {
				if(ch[i][j] == '1') ans += 1;
				if(ch[i][j] == '2') ans -= 1;
			}
		}
		
		cout << ans + 10 << endl;
	}
}

I 本题也主要考察了DFS

难题,我先留。

J 本题竟也主要考察了DFS

嘿,再留。

K 本题主要考察了dp

简单题,主要考虑1,0的关系,我们是尽量不想出现坏区间,所以我们发现100100100...这种构造可以在不出现坏区间的情况下尽可能的填入最多的1。而对于实在要出现坏区间的情况,我们就构造11111...11100这样的,用最多的1去构造坏区间。所以答案就是一部分111..11100100100...构成的,枚举一下断点就好。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 20004;
int n,m;
int main() {
	cin >> n >> m;
	int ans = 100000;
	if(n <= 2) {
		cout << 0 << endl;
		return 0;
	}
	if(n == m) {
		cout << n - 2 << endl;
		return 0;
	}
	if(n - 1 == m) {
		cout << n - 2 << endl;
		return 0;
	} 
	if((n - 1) / 3 + 1 >= m) ans = 0;
	for(int i = 4;i <= n;i++) {
		int res = 0,rm = m;
		rm -= (i - 2); 
		if((n - i - 1) / 3 + 1 >= rm) {
			ans = min(ans,i - 3);
		}
	}
//	ans = max(ans,0);
	cout << ans << endl;
}

L 本题主要考察了运气

简单题,数学题目。组和第几个人本质是一样的。除了最后只剩2组或者2人只需要问一次,其余的都是等概率事件,1/4,1/5。加起来就好了。最后的期望次数是 5.05。就是 i = 32 。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int main() {
	cout << "32" << endl;
}

M 本题主要考察了找规律

简单题,一个简单的 O(n3)O(n^3) 的动态规划,dp(i,j)dp(i,j) 表示考虑到第 ii 个人,现在还有 jj 个仙贝的最大收益。那么转移就是,dp(i,j)=max(dp(i1,jx)+xj)dp(i,j)=\max(dp(i-1,j-x)+\frac{x}{j})

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 1005;
double f[N][N];
int n,m;
int main() {
	cin >> n >> m;
	if(n >= m) n = m;
	for(int i = 1;i <= m;i++) f[1][i] = 1;
	for(int i = 2;i <= n;i++) {
		for(int j = 1;j <= m;j++) {
			for(int x = 0;x <= j;x++) {
				f[i][j] = max(f[i][j],f[i - 1][j - x] + 1.0 * x / j);
			}
 		}
	}
	printf("%.6f",f[n][m]);
	return 0;
}