第十七届浙大城市学院程序设计竞赛(同步赛)题解

第十七届浙大城市学院程序设计竞赛(同步赛)题解

萌新又来水题解了
原题链接
官方题解

A/B
略 签到题qwq

C Sumo and Virus
链接:https://ac.nowcoder.com/acm/contest/5954/C

题意:
一个病患每天可以传染x个未被感染的人;
潜伏期为7天,期间不发病也不传染别人;
第8天开始发病,并且可以传染;
第14天,被治愈(当天不会传染,且不再具有传染能力);
治愈之后具有抵抗力,不会被传染。
问:从Sumo感染病毒开始算第一天,第n天过后小镇上有几个传染者(指具有传染能力的人)?

tips:直接模拟就好~可以用数组存。比赛的时候直接用变量存了。注意小镇只有m个人,且患病后再不会患病,要从总人数中除去。此外,要用ll,会爆int!

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

ll t,x,n,m,qf1,qf2,qf3,qf4,qf5,qf6,qf7,fb1,fb2,fb3,fb4,fb5,fb6;

void solve(){
	qf1 = qf2 = qf3 = qf4 = qf5 = qf6 = qf7 = fb1 = fb2 = fb3 = fb4 = fb5 = fb6 = 0;
	if(n <= 7)	printf("0\n");
	else{
		qf7 = 1,m -= 1;
		for(int day = 8; day <= n; ++day){
			int rec = qf1, rec2 = fb1;
			if(qf7 || fb1 || fb2 || fb3 || fb4 || fb5){
				if(m >= (qf7 + fb1 + fb2 + fb3 + fb4 + fb5) * x)	qf1 = (qf7 + fb1 + fb2 + fb3 + fb4 + fb5) * x, m -= (qf7 + fb1 + fb2 + fb3 + fb4 + fb5) * x;
				else	qf1 = m, m = 0;
			}else	qf1 = 0;
			fb1 = qf7, qf7 = qf6, qf6 = qf5, qf5 = qf4, qf4 = qf3, qf3 = qf2, qf2 = rec;
			fb6 = fb5, fb5 = fb4, fb4 = fb3, fb3 = fb2, fb2 = rec2;
		}
		printf("%lld\n",fb1 + fb2 + fb3 + fb4 + fb5 + fb6);
	}
}

int main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld%lld",&x,&m,&n);
		solve();
	}
	return 0;
}

D. Sumo and Easy Sum
题意:
第十七届浙大城市学院程序设计竞赛(同步赛)题解
第十七届浙大城市学院程序设计竞赛(同步赛)题解
tips:注意分数的化简。

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

int t,k,a,b;

int gcd(int x, int y){
	if(x < y)	swap(x,y);
	int tmp;
	while(y){
		tmp = x % y;
		x = y;
		y = tmp;
	}
	return x;
}
void simplify(){
	if(a % b == 0)	printf("%d\n",a / b);
	else{
		printf("%d/%d\n",a / gcd(a,b), b / gcd(a,b));
	}
}

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&k);
		a = k;
		b = k * k - k - 1;
		simplify();
	}
	return 0;
}

G. Sumo and Robot Game
链接:https://ac.nowcoder.com/acm/contest/5954/F
题意:
Sumo has a total of n cars. Every day, he will choose any number of cars from the n cars (the number of cars cannot be 0) to form a team, and then choose one from this team to drive himself. How many options are there?

tips:(证明可以用二项式定理)
第十七届浙大城市学院程序设计竞赛(同步赛)题解

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 1e9 + 7;
int n,t;

ll ksm(ll x, ll n){
	ll res = 1;
	while(n){
		if(n & 1)	res = (res % mod) * (x % mod) % mod;
		n >>= 1;
		x = (x % mod) * (x % mod) % mod;
	}
	return res;
}

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		ll ans = (n % mod * ksm(2, n - 1)) % mod;
		printf("%lld\n",ans);
	}
	return 0;
}

H.Sumo and Electricity(Easy)
链接:https://ac.nowcoder.com/acm/contest/5954/H
题意:Sumo有n个核电站,每个核电站都有自己的耗电量w_i。
​这些核电站之间通过m条电缆相连,电缆的传输功耗为两个核电站耗电量之间的异或⊕(XOR)值。

但是核电站功率十分不稳定,因此Sumo并不知道部分核电站目前的功耗是怎样的,但是它可以选择调整这些核电站功耗的大小。

因为电缆的功耗远大于核电站的功耗,因此Sumo希望可以优先保证在所有电缆功耗总和尽可能低的条件下,尽量降低所有核电站的功耗总和,希望你能帮助Sumo为功耗未知的核电站设置功耗,从而满足以上的条件。

tips:只有一个wi是-1(hard版本有多个-1,不会做qwq)。取出所有-1核电站相连的核电站功耗值,对每一位处理,0多或者01数量相等,该位就是0,反之是1。(这样才能保证异或最小)。

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

int n,m,rec,a,b,maxlen;
ll sum,w,ans,sumdl,book[505],final;
vector <ll> box;

string convert(ll x){
	string str = "";
	do{
		str += x % 2 + '0';		
	}while(x /= 2);
	int len = str.length();
	maxlen = max(maxlen, len);
	return str;
}

ll con(string s){
	ll z = 0;
	int len = s.length();
	for(int i = len - 1; i >= 0; --i)
		z = z * 2 + s[i] - '0';
	return z;
}
void solve(){
	vector<string> v;
	string tmp = "";
	for(int i = 0; i < box.size(); ++i){
		v.push_back(convert(box[i]));
	}
	for(int i = 0; i < maxlen; ++i){
		int cnt0 = 0, cnt1 = 0;
		for(int j = 0; j < v.size(); ++j){
			if(v[j].length() <= i)	cnt0++;
			else	v[j][i] == '0' ? cnt0++ : cnt1++;
		}
		if(cnt0 >= cnt1)	tmp += "0";
		else	tmp += "1";
	}
	final = con(tmp);
	sum += final;
	for(int i = 0; i < box.size(); ++i){
		sumdl += final ^ box[i];
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; ++i){
		scanf("%lld",&w);
		(w != -1) ? sum += w, book[i] = w : rec = i;
	}
	for(int i = 1; i <= m; ++i){
		scanf("%d%d",&a,&b);
		if(a == rec)	box.push_back(book[b]);
		else if(b == rec)	box.push_back(book[a]);
		else	sumdl += book[b] ^ book[a];
	}
	solve();
	printf("%lld\n%lld",sumdl,sum);
	return 0;
}

J. Sumo and Balloon

tips:高数题。已知三个点求平面方程+点到平面的距离。

#include<bits/stdc++.h>
#define PI acos(-1)

using namespace std;

double A,B,C,D,l,x,y,z,x1,x2,x3,yy1,y2,y3,z1,z2,z3,dis;

int main(){
	scanf("%lf",&l);
	scanf("%lf%lf%lf",&x,&y,&z);
	scanf("%lf%lf%lf",&x1,&yy1,&z1);
	scanf("%lf%lf%lf",&x2,&y2,&z2);
	scanf("%lf%lf%lf",&x3,&y3,&z3);
	A = (y2 - yy1)*(z3 - z1) - (z2 -z1)*(y3 - yy1);
	B = (x3 - x1)*(z2 - z1) - (x2 - x1)*(z3 - z1);
	C = (x2 - x1)*(y3 - yy1) - (x3 - x1)*(y2 - yy1);
	D = -(A * x1 + B * yy1 + C * z1);
	dis = abs(A * x + B * y + C * z + D) / sqrt(A * A + B * B + C * C) / 2;
	printf("%lf",4.0 * PI * dis * dis * dis / (3.0 * l));
	return 0;
}

L. Sumo and Coins
题意:有n个硬币,开始时a个朝上,b个朝下。每次只能反转n-1个硬币,问可否最终全正/全反。

tips:转换思路,每次翻n-1个转化为每次翻1个,再全反过来是一样的
然后瞎猜几次,可以不完全归纳 出结论:
A.n偶数,答案为ALL;
B.不存在NONE;
C.n为奇数,a奇数则UP,b奇数则DOWN.
具体证明看官方题解8!

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

int t,a,b,n;

int main(){
	scanf("%d",&t);
	while(t--){
		bool upflag = false, downflag = false;
		scanf("%d%d%d",&n,&a,&b);
		if(n % 2){
			if(a % 2)	upflag = true;
			if(b % 2)	downflag = true;
		}else{
			upflag = true;
			downflag = true;
		}
		if(upflag && downflag)	printf("ALL\n");
		if(!upflag && downflag)	printf("DOWN\n");
		if(upflag && !downflag)	printf("UP\n");
		if(!upflag && !downflag)	printf("NONE\n");
	}
	return 0;
}

一共做了8个qwq 剩下4个题:dp、线段树、莫队、H题的hard版本。

上一篇:「自制地图实现carla交通流」sumo与carla百米同步实现交通流仿真


下一篇:sumo与python的接口——TraCI