竞赛地址

知乎版本

A. 几何糕手

求圆的面积

#define pi 3.14159265358979323846
void solve() {
	scanf("%d%d", &x, &y);
	x += y;
	printf("%.10f\n", pi * x * x);
}

B. 国际裁判带师

模拟

#define debugging 0
int cal(int x) {
	int res = 0;
	if (x < 10) {
		++res;
	}
	if (x % 10 == 0) {
		++res; 
	}
	return res;
}

void solve() {
	scanf("%s", s);
	n = strlen(s);
	int x = 0, y = 0;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		char &c = s[i];
		if (c == 'a') {
			++x;
		} else {
			++y;
		}
		if (debugging) {
			printf("cal(%d):%d\n", x, cal(x));
			printf("cal(%d):%d\n", y, cal(y));
		}
		ans += cal(x);
		ans += cal(y);
	}
	printf("%d\n", ans);
}

C. 第K小表示数

动态规划，双指针。维护当前最小的x,y下标。

void solve() {
	scanf("%lld%lld%lld", &k, &x, &y);
	if (x == y) {
		printf("%lld\n", k * x);
		return;
	}
	if (x > y) {
		swap(x, y);
	}
	vector<ll> ans;
	ans.push_back(0);
	ans.push_back(x);
	int l = 0, l2 = 0, r = 2;
	while (r <= k) {
		ll tmp = ans.back();
		while (l < r && ans[l] + x <= tmp) {
			++l;
		}
		while (l2 < r && ans[l2] + y <= tmp) {
			++l2;
		}
		if (ans[l] + x <= ans[l2] + y) {
			ans.push_back(ans[l] + x);
		} else {
			ans.push_back(ans[l2] + y);
		}
		++r;
	}
	printf("%lld\n", ans[k]);
}

D. 数树

算出最大的y使得2^y<=n，

对于大小为2^y的完全二叉树，它的二叉树个数为A

A = (2^(y) - 1) +  (2^(y-1) - 1) + ...  + (2^(1)-1) = 2 * (2^y - 1) - y.

对于多出的部分m

m = n - (2^(y) - 1)

对应的贡献实际就是（对应完全二叉树尺寸为1，2，...）

m, m/2, ..., 1

#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<deque> 
#include<queue>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define ll long long
#define inf 2000000009
#define pi 3.14159265358979323846
#define debugging 0
const int maxn = 200010;
const int mod = 1e9+7;

ll n, m;
ll k, x, y;

ll M(ll x, ll y) {
	return x * y % mod;
}
ll A(ll x, ll y) {
	return (x + y) % mod;
}
ll Sub(ll x, ll y) {
	return A(x, mod - (y % mod));
}

ll b2[62], b2mod[62];
void init() {
	b2[0] = 1;
	b2mod[0] = 1;
	for (int i = 1; i <= 61; ++i) {
		b2[i] = b2[i-1] * 2;
		b2mod[i] = M(b2mod[i-1], 2);
	}
}

void solve() {
	scanf("%lld", &n);
	y = 0;
	while (b2[y] <= n + 1) {
		++y;
	}
	--y;
	
	// 2^(y) - 1, 2^(y-1) - 1, ... 2^(1)-1
	// m = n - (2^(y) - 1)
	// m, m/2, ..., 1
	
	// A = 2 * (2^y - 1)
	// B = y;
	// C 
	ll ans = M(Sub(b2mod[y], 1), 2);
	ans = Sub(ans, y);
	
	m = n - (b2[y] - 1);
	while (m) {
		ans = A(ans, m);
		m /= 2;
	}

	printf("%lld\n", ans);
} 
int main() {
	init();
	int t = 1, cas = 1;
	scanf("%d", &t);
//	cin >> t;
	while (t--) {
//		debug();
//		if(debugging) printf("case :%d\n", cas++); // debug
		if (debugging) cout << "case: " << cas++ << endl;
		solve();
	}
}
/*
*/

E. 自动计算机

预处理，算出每轮能走到的相对位置。

模拟走n轮（因为第n+1轮开始，就肯定重复了），看是否能走到终点。

#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<deque> 
#include<queue>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define ll long long
#define inf 2000000009
#define pi 3.14159265358979323846
#define debugging 0
const int maxn = 200010;
const int mod = 1e9+7;

int n, m;
ll k, x, y;
ll b[maxn];
ll a[maxn];
ll pre[maxn];
ll num[maxn];


void solve() {
	scanf("%d%d%lld", &n, &m, &x);
	for (int i = 0; i < n; ++i) {
		num[i] = -1;
	}
	pre[0] = 0;
	for (int i = 1; i <= m; ++i) {
		scanf("%lld", &a[i]);
		pre[i] = pre[i-1] + a[i];
		pre[i] %= n;
		if (num[pre[i]] == -1) {
			num[pre[i]] = i;
		}
	}
	
	ll ans = -1;
	for (int i = 1; i <= n; ++i) {
		ll tmp = n - x;
		if (!x) {
			ans = (i - 1) * m;
			break;
		}
		if (num[tmp] != -1) {
			ans = 1LL * (i - 1) * m + num[tmp];
			break;
		}
		x = (x + pre[m]) % n;
	}
	printf("%lld\n", ans);
	
} 
void debug() {
	
}
int main() {
	int t = 1, cas = 1;
//	scanf("%d", &t);
//	cin >> t;
	while (t--) {
//		debug();
//		if(debugging) printf("case :%d\n", cas++); // debug
		if (debugging) cout << "case: " << cas++ << endl;
		solve();
	}
}
/*
参考：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63838516
*/