第十七届浙大城市学院程序设计竞赛（同步赛）题解QIzikk的博客-csumoandvirus

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

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

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("0n"); 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("%lldn",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("%dn",a / b); else{ printf("%d/%dn",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("%lldn",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("%lldn%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("ALLn"); if(!upflag && downflag) printf("DOWNn"); if(upflag && !downflag) printf("UPn"); if(!upflag && !downflag) printf("NONEn"); } return 0; } 

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