2021-02-20

2021 HZNU Winter Training Day 16 (2015 ICL, Finals, Div. 2)

字数统计: 3k字 | 阅读时长: 15分

soved	A	B	C	D	E	F	G	H	I	J	K
8 / 11	O	O	·	O	·	O	O	·	Ø	O	Ø

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

比赛链接

A - Nano alarm-clocks

solved by Sstee1XD & Tryna. 0:41(+1)

题意： 定义时分秒的进位分别为 $12，10^6，10^6$ 。现在给你n个时间，一次只能让其中一个时间往后走，问你让所有的时间相同所需要的时间和最短是多少。

题解： 把时间转换成秒，sort一下，找下线性规律，找到最小值。

AC代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 7;
const ll hh = 1e12;
const ll mm = 1e6;

int n;
ll a[N], h[N], m[N], s[N];
ll suf[N];

int main() {
	scanf("%d", &n);
	ll maxx = 12 * hh;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld %lld %lld", &h[i], &m[i], &s[i]);
		a[i] = h[i] * hh + m[i] * mm + s[i];
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; ++i) {
		suf[i] = maxx - a[i];
	}
	for (int i = n - 1; i >= 1; --i) {
		suf[i] += suf[i + 1];
	}
	
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans += a[n] - a[i];
	}
	
	ll tmp = 0;
	ll go = a[1] + 12 * hh;
	for (int i = 2; i <= n; ++i) {
		if (a[i] == a[1]) continue;
		tmp += go - a[i];
	}
	ans = min(ans, tmp);
	
	ll pn = 1, sn = n - 2;
	ll now = 0;
	for (int i = 2; i <= n - 1; ++i) {
		now += pn * (a[i] - a[i - 1]);
		pn++;
		ans = min(ans, now + suf[i + 1] + sn * a[i]);
		sn--;
	}
	
	ll H = ans / hh;
	ans -= hh * H;
	ll M = ans / mm;
	ans -= mm * M;
	ll S = ans;
	printf("%lld %lld %lld\n", H, M, S);
	return 0;
}

B - Lunch

solved by lllllan.(+)

题意： 连续排列的 $n$ 片叶子，每片叶子上有一只苍蝇。有一只青蛙在第 $s$ 片叶子上，按题目要求遍历所有叶子后最后到达第 $f$ 片叶子结束。

每片叶子只能到达一次，遍历过就不能再次经过。
只能向相邻一个单位或者两个单位的叶子跳动。

题目要求【跳动一个单位】的最小次数。

题解： 先看题目要求的几个点：

每片叶子必须到达且只到达一次。
每次移动只能到达相邻一个单位或两个单位的叶子。
从s出发去完所有其他叶子最后到达f。

看完条件以后，就应该发觉是一道找规律的题目了。但是我懒得一一陈述规律的发现过程了，只讲个大概和方格代码。

假设一共10片叶子，s = 3，f = 7，按照题目要求，势必先遍历s左边的叶子，然后再去其他地方。那又因为每个叶子只能去一次和移动规则的限制，向左边的移动只能是3 -> 1 -> 2 -> 4，其中有一步是跳动一个单位的。可以自己改变s的位置去发现，只要是先去完成一边，然后调回另一边的，都至少有一次【跳动一个单位】的移动。

并且该样式的移动方式则应为：

跳着遍历s左边的叶子
跳回s的右边去，遍历s-f中间的叶子
再跳过f去遍历f右边的叶子

三步中一三都必须完成一次【跳动一个单位】的移动，只有第二部需要去找规律，这个就不说了，自己去发现呗。

再讲两个特殊，不能完成题目要求的情况1 2 s f 5 6 7，起点终点相邻，并且两端都还有叶子，不解释了自己看。s = f可能是我没读清楚，题目没有说明s不能等于f，一旦相等，又因为 $n>1$ ，那么就一定不能完成要求。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;

int n, s, f;

void run () {
	scanf("%d%d%d", &n, &s, &f);
	
	if (s > f) swap(s, f);
	
	if (s == f || s + 1 == f && s != 1 && f != n) return (void)(printf("-1"));
	
	int ans = 0;
	
	if (s > 1) ans++;
	if (f < n) ans++;
	
	ans += (f - s - ans) / 3 + (f - s - ans) % 3;
	
	printf("%d\n", ans);
}

int main () {
	run();
	return 0;
}

D - Ceizenpok’s formula

Solved by Sstee1XD. 0:05(+)

题意： 求 $\tbinom{n}{m}$ $mod$ $k$ 。

题解： $n$ 很大并且 $k$ 不保证是素数，扩展卢卡斯裸题，板子来自这里

AC代码

#include<bits/stdc++.h>
#define rg register
using namespace std;
typedef long long ll;
ll n, m, p;
void exgcd(ll a,ll b ,ll &x,ll &y){
    if(!b){x=1,y=0;return;}
    exgcd(b,a%b,x,y);
    ll t=x;
    x=y,y=t-(a/b)*y;
}
ll inv(ll a,ll b){
    ll x,y;
    return exgcd(a,b,x,y),(x%b+b)%b;
}
inline ll ksm(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1)
            ans=a*ans%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
ll crt(ll x,ll p,ll mod){
    return inv(p/mod,mod)*(p/mod)*x;
}
ll fac(ll x,ll a,ll b){
    if(!x)
        return 1;
    ll ans=1;
    for(ll i=1;i<=b;i++)
    if(i%a)
            ans*=i,ans%=b;
    ans=ksm(ans,x/b,b);
    for(ll i=1;i<=x%b;i++)
        if(i%a)
            ans*=i,ans%=b;
    return ans*fac(x/a,a,b)%b;
}
ll C(ll n,ll m,ll a,ll b){
    ll N=fac(n,a,b),M=fac(m,a,b),Z=fac(n-m,a,b),sum=0;
    for(ll i=n;i;i=i/a)
        sum+=i/a;
    for(ll i=m;i;i=i/a)
        sum-=i/a;
    for(ll i=n-m;i;i=i/a)
        sum-=i/a;
    return N*ksm(a,sum,b)%b*inv(M,b)%b*inv(Z,b)%b;
}
void exlucas(ll n,ll m,ll p){
    ll t=p,ans=0;
    for(ll i=2;i*i<=p;i++){
        ll k=1;
        while(t%i==0)
            k*=i,t/=i;
        ans+=crt(C(n,m,i,k),p,k),ans%=p;
    }
    if(t>1)
        ans+=crt(C(n,m,t,t),p,t),ans%=p;
    // return ans;
    printf("%lld\n",ans%p);
}
int main(){
    scanf("%lld %lld %lld", &n, &m, &p);
    exlucas(n,m,p);
    return 0;
}

F - The Pool for Lucky Ones

Solved by all. 2:01(+7)

题意： 给你 $n$ 条泳道里面的人数，你可以选择一个人移动到相邻的泳道里，求所有人数最多的泳道里的人数和的最小值。

题解： 对于最大值的数量只有 $1$ 的情况，我们肯定只能移动人数最多的泳道里的人，判断一下能不能让最大值减小就行。
对于数量大于 $1$ 的，我们计算出每条泳道进行移动的所有情况下的最小值。预处理出所有值的数量即可进行计算。

AC代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 7;

int n;
ll a[N], num[N], maxx = -1, ans;

void work(ll p, int i) {
	if (p == maxx) return;
	if (a[i] == 0) return;
	if (num[maxx] == 1) {
		if (p != maxx - 1) ans = min(ans, (num[maxx - 1] + 1) * (maxx - 1));
	    
	}
	else if (p > maxx){
		ans = min(ans, p);
	} else if (a[i] == maxx){
		ans = min(ans, (num[maxx] - 1) * maxx);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		num[ a[i] ]++;
		maxx = max(a[i], maxx);
	}
	
	ans = maxx * num[maxx];
	
	for (int i = 1; i <= n; ++i) {
		if (num[maxx] == 1 && a[i] != maxx) continue;
		if (i != 1) work(a[i - 1] + 1, i);
		if (i != n) work(a[i + 1] + 1, i);
	}
	
	printf("%lld\n", ans);
	return 0;
}

G - TheDress

solved by Tryna. 0:29(+)

题意： 回答中有黑和蓝的是地球人，有金和白的是i1c5l星球人，若都没有则是其他星球人，问这三种人的占比。

题解： 因为 $n$ 很小，所以按照题意模拟即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 1e2 + 10;
int t, n;
string st;
void solve() {
	cin>>n;
	getchar();
	int nn = n;
	int sum1 = 0, sum2 = 0, sum3 = 0;
	while(n--) {
		getline(cin, st);
		int len = st.size();
		int f11 = 0, f12 = 0, f21 = 0, f22 = 0;
		for(int i = 0; i < len; i++) {
			if(st.substr(i, 4) == "blue") f11++;
			if(st.substr(i, 5) == "black") f12++;
			if(st.substr(i, 4) == "gold") f21++;
			if(st.substr(i, 5) == "white") f22++;
		}
		if(f11 && f12) sum1++;
		else if(f21 && f22) sum2++;
		else sum3++;
	}
	double ans1 = sum1 * 1.0 / nn * 100;
	double ans2 = sum2 * 1.0 / nn * 100;
	double ans3 = sum3 * 1.0 / nn * 100;
	printf("%.10f\n%.10f\n%.10f\n", ans1, ans2, ans3);
}
int main() {
	solve();
	return 0;
}

I - Scrooge .net

solved by Tryna

题意： 给出一条直线和 $k$ 个点，要求找一个点，满足这个点在直线上并且这个点到其他点的距离和最短。

题解： 不难想到用三分来做，这题精度要求挺高的，所以用了 $long$ $double$ ，而且要注意是直线不是线段。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-10
const int maxn = 1e4 + 10;
int t, k;
long double X1, Y1, angle, d;
struct Point{
    long double x, y;
	Point(){}
    Point(long double x, long 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);}
}P[maxn];
Point p1, p2;
long double Dist(Point A,Point B){
    return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
}
long double f(long double t) {
	X1 = t * cos(angle);
	Y1 = t * sin(angle);
	X1 = X1 + p1.x;
	Y1 = Y1 + p1.y;
	Point pp = Point(X1, Y1);
	long double sum = 0;
	for(int i = 1; i <= k; i++) {
		sum += Dist(pp, P[i]);
	}
	return sum;
}
long double three_search(long double l, long double r) {
	long double midl, midr;
	while(r - l > eps) {
		midl = l + (r - l) / 3.0;
		midr = r - (r - l) / 3.0;
		if(f(midl) > f(midr))
			l = midl;
		else r = midr;
	}
	return f(midr);
}
void solve() {
	scanf("%Lf %Lf %Lf %Lf", &p1.x, &p1.y, &p2.x, &p2.y);
	scanf("%d", &k);
	for(int i = 1; i <= k; i++)
		scanf("%Lf %Lf", &P[i].x, &P[i].y);
	angle = atan2(p2.y - p1.y, p2.x - p1.x);
	d = Dist(p1, p2);
	long double res = three_search(-100000.0, 100000.0);
	printf("%.10Lf\n%.10Lf %.10Lf\n", res, X1, Y1);
}
int main() {
	solve();
	return 0;
}

J - Superfactorial numeral system

solved by lllllan

题意： 题目就是找到一个数列a满足题目中的公式。

题解： 无他，但贪心尔

AC代码

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

ll p, q, bas = 1;

int main () {
	scanf("%lld%lld", &p, &q);
	while (p) {
		ll tem = p / q;
		printf("%lld ", tem);
		p = (p - tem * q) * (++bas);
	}
	return 0;
}

K - Microcircuits

Solved by Sstee1XD. (-)

题意： 给你一个由 $n$ 个元件构成的环状的电路板，问你要连 $k$ 条互不相交的线的情况有多少种。

题解： 使用组合数学去计算的话很难处理，所以这里采用 $dp$ 去处理。
$dp[i][j]$ 表示在 $n$ 个元件之间连 $j$ 条线的方案数。我们转移时可以分成两种情况，第一种不用第 $i$ 个元件，那么就是 $dp[i - 1][j]$ ；第二种用第 $i$ 个元件，因为线不能相交，我们画一下图发现可以分成左右两幅图，由此我们想到枚举第 $i$ 个元件连接到第 $v$ 个元件，其左边的 $v - 1$ 个元件连了 $w$ 条边，那么右边还需要 $i - 1 - v$ 个元件连 $j - 1 - w$ 条边。得到了转移方程：

dp[i][j] = dp[i-1][j] + \sum_{v = 1}^{i - 1}\sum_{w = 0}^{j - 1}dp[v - 1][w] * dp[i - 1 - v][j - 1 - w]

AC代码

#include<bits/stdc++.h>

using namespace std;

#define dbg(x...)             \
	do {                      \
		cout << #x << " -> ";\
		err(x);               \
	} while (0)

void err() {
	cout << endl;
}

template <class T, class... Ts>

void err(const T& arg, const Ts&... args) {
	cout << arg << ' '; err(args...);
}

typedef long long ll;

ll dp[51][51];
int n, k; 

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 0; i <= n; ++i) dp[i][0] = 1;
	for (int i = 2; i <= n; ++i) {
		for (int j = 1; j <= i / 2; ++j) {
			dp[i][j] = dp[i - 1][j];
			for (int v = 1; v < i; ++v) {
				for (int w = 0; w < j; ++w) {
					dp[i][j] += dp[v - 1][w] * dp[i - 1 - v][j - 1 - w];
				}
			}
		}
	}
	printf("%lld\n", dp[n][k]);
	return 0;
}