第十七届浙大城市学院程序设计竞赛（同步赛）题解
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版本。