Atcoder Beginner Contest 165题解

$A:$A:
题解： 给定 $l,r,k$l,r,k，问在 $[l,r]$[l,r]内 $k$k的倍数的个数。即 $b/k-(a-1)/k$b/k−(a−1)/k
代码：

#include<bits/stdc++.h>
using namespace std;

void solve() {
	int k;
	int a, b;
	cin >> k >> a >> b;	
	printf("%s\n", b / k - (a - 1) / k > 0 ? "OK" : "NG");
}

int main()
{
	int T = 1;
	//scanf("%d", &T);
	
	while(T--) {
		solve();
	}
}

$B:$B:
题意： 初始拥有 $100$100元，每年的利息是 $1\%$1%，利息的小数部分直接舍去，问要多少年才能得到 $x$x元。
题解： 直接循环就可以了 。
关于复杂度：由于 $1.01^{365}=37.8$1.01365=37.8，那么 $(1.01{)}^{7300}=(1.01^{365}{)}^{20}=(37.8{)}^{20}>10^{18}$(1.01)7300=(1.01365)20=(37.8)20>1018，故数量级才 $10^3$103。还有就是样例中直接给出了 $10^{18}$1018的答案，暗示直接循环。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
void solve() {
	ll x;
	scanf("%lld", &x);
	
	ll now = 100, g = 0;
	while(now < x) {
		now = now + now / 100;
		g++;
	}
	
	printf("%lld\n", g);
}
int main()
{
	int T = 1;
// scanf("%d", &T);
	
	while(T--) {
		solve();
	}
}

$C:$C:
题意： 让你构造出一个序列 $A$A，使得和最大。和的定义：所有满足 $A_{b_i}-A_{a_i}=c_i$Abi​​−Aai​​=ci​时的 $d_i$di​大小。
题解： 直接搜索即可。
关于复杂度：直接 $dfs$dfs记录下下列情况的最多循环数会发现只有 $3e5$3e5。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 20, Q = 60;

ll res = 0;

struct Node {
	int a, b, c, d;
}p[Q];
int n, m, q;

int A[N];

void dfs(int u, int num) {
	if(u == n + 1) {
		ll sum = 0;
		for(int i = 1; i <= q; i++) 
			if(A[p[i].b] - A[p[i].a] == p[i].c) sum += p[i].d;
			
		res = max(res, sum);
		return ;
	}
	
	A[u] = num;
	for(int i = num; i <= m; i++) dfs(u + 1, i);
}

void solve() {
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= q; i++) 
		scanf("%d%d%d%d", &p[i].a, &p[i].b, &p[i].c, &p[i].d);
	
	for(int i = 1; i <= m; i++) dfs(1, i);
	
	printf("%lld\n", res);
}

int main()
{
	int T = 1;
	//scanf("%d", &T);
	
	while(T--) {
		solve();
	}
}

$D:$D:
题意： 求 $\left(Ax\right)/B-A\times \left(x/B\right)$(Ax)/B−A×(x/B)的最大值， $x\le n$x≤n
题解： 结论题：答案即 $A\times min(n,b-1)/b$A×min(n,b−1)/b
证明： $\left(Ax\right)/B=A\left(x/B\right)+\left(A\right(x\%B\left)\right)/B$(Ax)/B=A(x/B)+(A(x%B))/B，第一部分是 $x$x中直接包含 $B$B的数量，第二部分是所有余数与 $A$A的乘积构成的 $B$B的数量。则当 $x$x取 $b-1$b−1时得到最大。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
void solve() {
	ll a, b, n;
	scanf("%lld%lld%lld", &a, &b, &n);
	
	ll fir = a * min(n, (b - 1)) / b;
	printf("%lld\n", fir);
}

int main()
{
	int T = 1;
	//scanf("%d", &T);
	
	while(T--) {
		solve();
	}
}

$E:$E:
题意： $n$n名玩家， $m$m个竞技场，共进行 $n$n个回合，每个玩家与其余 $n-1$n−1玩家只会竞技一次。
每轮结束后，所有玩家的编号加 $1$1，编号为 $n+1$n+1的玩家编号置为 $1$1。给出合法的构造方案。
题解： 由于每个玩家都只能与同一个玩家竞技一次，故需要构造出一个每次竞技后不会再竞技的方案。注意 $n\ge 2\times m+1$n≥2×m+1，那么我们构造 $n/2$n/2对数，使得所有数各不相同且绝对值差 $[1,n/2]$[1,n/2]。
代码：

#include<bits/stdc++.h>
using namespace std;

int n, m;

void solve() {
	scanf("%d%d", &n, &m);
	if(n & 1); else n--;
	int l = 1, r = (n + 1) / 2 + 1;
	int t = n / 2;
	for(int i = 1; i <= m; i++) {
		if(i & 1) {
			printf("%d %d\n", l, l + t);
			t--;
			l++;
		}
		else {
			printf("%d %d\n", r, r + t);
			t--;
			r++;
		}
	}
}

int main()
{
	int T = 1;
	//scanf("%d", &T);
	
	while(T--) {
		solve();
	}
}

$F:$F:
题意： 给定一棵树和树上每个点的权，问点 $1$1到 $[1,n]$[1,n]这 $n$n个点的路径上以点权构造的 $LIS$LIS程度。
题解： 树上直接写即可，注意用时间复杂度为 $O\left(nlogn\right)$O(nlogn)的 $LIS$LIS解法，以及回溯时要清 $LIS$LIS数组。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = N << 1;

int h[N], e[M], ne[M], idx;
int q[N], n;
int temp[N], g;
int res[N];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int b_s(int l, int r, int x) {
	while(l < r) {
		int mid = l + r >> 1;
		if(q[temp[mid]] >= x) r = mid;
		else l = mid + 1;
	}
	return l;
}

void dfs(int u, int fa) {
	for(int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if(v == fa) continue;
		
		int flag = 0, prep = 0, prev = 0;
		if(q[temp[g]] < q[v]) {
			flag = 1;
			temp[++g] = v;
		}
		else if(q[v] <= q[temp[g]]) {
			int t = b_s(1, g, q[v]);
			flag = 2, prep = t, prev = temp[t];
			temp[t] = v; 
		}
		res[v] = g;
		dfs(v, u);
		if(flag == 1) temp[g--] = 0;
		else if(flag == 2) {
			temp[prep] = prev;
		}
	}
}

void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &q[i]);
	
	for(int i = 1; i < n; i++) {
		int a, b; scanf("%d%d", &a, &b);
		add(a, b), add(b, a); 
	}
	
	res[1] = 1;
	temp[++g] = 1;
	dfs(1, 0);
	for(int i = 1; i <= n; i++) printf("%d\n", res[i]);
}

int main()
{
	int T = 1;
	//scanf("%d", &T);
	
	while(T--) {
		memset(h, -1, sizeof h); idx = 0;
		solve();
	}
}