Solution to the problems of the 17th Zhejiang University City College Program Design Competition (synchronized competition)

The 17th Zhejiang University City College Program Design Competition （ Synchronized competition ） Answer key

Mengxin has come to the water again
Original link
Official explanation

A/B
A little Sign in problem qwq

C Sumo and Virus
link ：https://ac.nowcoder.com/acm/contest/5954/C

The question ：
A patient can be infected every day x An uninfected person ;
The incubation period is 7 God , During this period, it will neither get sick nor infect others ;
The first 8 The disease begins on day , And it can infect ;
The first 14 God , Be cured （ It will not be infected that day , And no longer have the ability to infect ）;
After healing, it has resistance , Will not be infected .
ask ： from Sumo The first day of infection , The first n Days later, there are several infected people in the town （ Refers to people with infectious ability ）？

tips: Direct simulation is good ~ You can save in an array . The variables are directly saved during the competition . Note that there are only m personal , And you won't get sick again , To remove from the total number . Besides , Use ll, Explosive 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
The question ：


tips: Pay attention to the reduction of scores .

#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
link ：https://ac.nowcoder.com/acm/contest/5954/F
The question ：
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:( It can be proved by binomial theorem ）

#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)
link ：https://ac.nowcoder.com/acm/contest/5954/H
The question ：Sumo Yes n A nuclear power plant , Each nuclear power plant has its own power consumption w_i.
​ These nuclear power stations pass through m Two cables are connected , The transmission power consumption of the cable is the XOR between the power consumption of two nuclear power plants ⊕（XOR） value .

But the power of nuclear power plants is very unstable , therefore Sumo I don't know what the current power consumption of some nuclear power plants is , But it can choose to adjust the power consumption of these nuclear power plants .

Because the power consumption of cables is much greater than that of nuclear power plants , therefore Sumo It is hoped that priority can be given to ensuring that the total power consumption of all cables is as low as possible , Try to reduce the total power consumption of all nuclear power plants , I hope you can help Sumo Set power consumption for nuclear power plants with unknown power consumption , So as to meet the above conditions .

tips： only one wi yes -1（hard There are multiple versions -1, Can not do qwq）. Remove all -1 The power consumption value of the nuclear power plant connected to the nuclear power plant , Deal with everyone ,0 More or 01 Equal quantity , This bit is 0, Conversely 1.（ In this way, the XOR can be minimized ）.

#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： Advanced mathematics problems . Find the plane equation with three known points + The distance from the point to the plane .

#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
The question ： Yes n A coin , At the beginning of the a One up ,b One down . You can only reverse at a time n-1 A coin , Ask whether it can finally be corrected / Total reflection .

tips： Change your mind , Every time I turn n-1 Turn into each turn 1 individual , The reverse is the same .
then Guess a few times , It can not be completely summarized Draw a conclusion ：
A.n even numbers , The answer for ALL;
B. non-existent NONE;
C.n It's odd ,a Odd rule UP,b Odd rule DOWN.
See the official explanation for the specific proof 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;
}

A total of did 8 individual qwq be left over 4 Questions ：dp、 Line segment tree 、 Mo team 、H The question is hard edition .