[2019 Multi-University Training Contest 1]

比赛网址

训练详情

时间:2020-5-17 13:00~18:00
rank:
完成情况：

题解

C Are They All Integers?

solved by hxm

题意

大水题

题解

略

E The League of Sequence Designers

solved by wxg&hxm

题意

给定一个数字序列，求最大的连续和乘以长度。

现在给出一个错误的做法，错误做法仅计算最大连续和来更新答案

求构造出一个长度大于$l$小于$2000$的序列，使得错误答案和正确答案相差正好为$k$

题解

分析发现，只要在最大连续和的串前加上一个负数，那么这个做法就会出错，现在要构造出两种答案相差$k$

由于最大长度为$1999$，不妨就构造长度为$1999$的序列，第一位为$-1$，剩下为非负数，和为$a$，则有

$(a - 1) \times 1999 - a \times 1998 = k$

即$a = k + 1999$，算出$a$后，分配给剩下每一位即可

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int K,L;
int ans[maxn];
void work(){
	int sum = 1999 + K;
	printf("1999\n");
	printf("-1");
	for (int i = 1; i <= 1997; i++) printf(" %d",sum / 1998);
	printf(" %d\n",sum - sum / 1998 * 1997);
}
int main(){
	int T = read();
	while (T--){
		K = read(); L = read();
		if (L >= 2000) puts("-1");
		else work();
	}
	return 0;
}

H Mining a

solved by fyh&hxm

题意

$\frac{1}{n} = \frac{1}{a Xor b} + \frac{1}{b}$

给定$n$，$b$是任意的，求最大的$a$使等式成立

题解

化简得$b = n + \frac{n^2}{a Xor b - n}$

枚举分母即可

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
LL n,a,b,N,ans;
int main(){
	int T =read();
	while (T--){
		ans = 0;
		n = read(); N = n * n;
		LL t;
		for (int i = 1; i < n; i++){
			if (N % i == 0){
				//1
				t = i;
				b = N / t + n;
				a = (t + n) ^ b;
				ans = max(ans,a);
				//2
				t = N / i;
				b = N / t + n;
				a = (t + n) ^ b;
				ans = max(ans,a);
			}
		}
		printf("%I64d\n",ans);
	}
	return 0;
}

J Automatic Control Machine

solved by hxm

题意

给定若干个集合，使用最少的集合并成全集

题解

bitset状压dp一下就好了

代码

CVBB ACM Team

目录

[2019 Multi-University Training Contest 1]

训练详情

题解

C Are They All Integers?

题意

题解

E The League of Sequence Designers

题意

题解

H Mining a

题意

题解

J Automatic Control Machine

题意

题解

训练实况

训练总结

改进

CVBB ACM Team

用户工具

站点工具

目录

[2019 Multi-University Training Contest 1]

训练详情

题解

C Are They All Integers?

题意

题解

E The League of Sequence Designers

题意

题解

H Mining a

题意

题解

J Automatic Control Machine

题意

题解

训练实况

训练总结

改进

页面工具