2020CCPC网络选拔赛
1002 Graph Theory Class
题意:
给定一个个结点的完全无向图,结点间的权值为,求最小生成树的值
题解:
分析可以发现一个合数的贡献就是它本身,而质数和的为两倍的质数,因此最终结果就是中所有合数的和加上两倍的所有质数的和。那么就是加上质数和,的和就是,而质数和可用min25筛求。
要注意用long long会爆精度。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000010; ll prime[maxn], id1[maxn], id2[maxn], f[maxn]; ll g[maxn], sum[maxn], a[maxn],T,n,p; ll findID(ll x){return x <= T ? id1[x] : id2[n / x];} ll calc(ll x){return x * (x + 1) / 2 - 1;} void print(__int128 x){ if(x<0)putchar('-'),x=-x; if(x>9)print(x/10); putchar(x%10+'0'); } inline void init() { ll cnt = 0,m = 0; T = sqrt(n + 0.5); for (ll i = 2; i <= T; i++) { if (!f[i]) { prime[++cnt] = i; sum[cnt] = sum[cnt - 1] + i; } for (ll j = 1; j <= cnt && i * prime[j] <= T; j++) { f[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } for (ll l = 1; l <= n; l = n / (n / l) + 1) { a[++m] = n / l; if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m; g[m] = calc(a[m]); } for (ll i = 1; i <= cnt; i++) for (ll j = 1; j <= m && (ll)prime[i] * prime[i] <= a[j]; j++) g[j] = g[j] - (ll)prime[i] * (g[findID(a[j] / prime[i])] - sum[i - 1]); } int main() { int TT; scanf("%d",&TT); while(TT--) { scanf("%lld%lld", &n,&p); n++; init(); print(((__int128)n*(n+1)/2-5+g[findID(n)])%p); puts(""); //printf("%lld\n",(calc(n)-4+g[findID(n)])%p); } return 0; }
1003 Express Mail Taking
题意:
有个快递柜,其中要去个快递柜中取快递,每次只能取一个快递,而且每次取快递前都要先去指定的第个快递柜解锁,从号点进入,并且要从号点离开,求取快递花费的最少距离
题解:
贪心,只要保证最后一次取的快递离号点最近即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6+5; int a[maxn]; int main() { int t; scanf("%d",&t); while(t--) { int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) scanf("%d",&a[i]); sort(a+1,a+m+1); ll ans = 0; if(a[m]<=k) { ans = 2*(k-1); for(int i=m;i>=2;i--) ans+=2*(k-a[i]); } else if(a[1]>=k) { ans = a[m]-1+(a[m]-k); for(int i=2;i<m;i++) ans += 2*(a[i]-k); ans += (a[1]-k)+(a[1]-1); } else { ans = a[m]-1+(a[m]-k); for(int i=2;i<m;i++) ans += 2*abs(a[i]-k); ans += k-1; } printf("%lld\n",ans); } return 0; }
1005 Lunch
题意:
给定个数字,每次操作可以选择一个数字,把它变成个(是的因子)。选择的数不能为.因此当只剩时则判为输
题解:
对于一个数来说,它由若干个质因子组成。对于一个奇数质因子,被拆成个,因为是奇数,相当于变成了个的情况。因此最多只能操作的奇数质因子次,会变成次,当遇到时,一个人操作后,另一个人跟着做同样操作则必输。因此每个数相当于一堆为(奇数质因子个数+ [为偶数])个数的石子,因此问题就转化为标准的nim博弈
#include <bits/stdc++.h> using namespace std; const int maxn = 100100; int isp[maxn], p[maxn]; void init() { for (int i = 2; i < maxn; i++) { if (isp[i] == 0) p[++p[0]] = i; for (int j = 1; j <= p[0] && i * p[j] < maxn; j++) { isp[i * p[j]] = 1; if (i % p[j] == 0) break; } } } int main(void) { init(); int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); int ans = 0; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); int num = 0; if (x % 2 == 0) { num++; while (x % 2 == 0) x /= 2; } for (int j = 2; p[j] * p[j] <= x; j++) if (x % p[j] == 0) { num++, x /= p[j]; while (x % p[j] == 0) num++, x /= p[j]; } if (x > 1) num++; ans ^= num; } puts(ans ? "W" : "L"); } return 0; }
1006 Robotic Class
题意:
定义个分段函数
其中,判断是否为连续函数
之间会形成,只有没有出边
题解:
之间形成,因此考虑到从后往前拓扑排序,每次都判断一下,即左右边界的极限
模拟即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, K[505]; int a[505][2020], b[505][2020], c[505][2020], d[505][2020]; ll gao(int t, ll x, int cc) { if (t == n) return x; int pos = lower_bound(a[t], a[t] + K[t], x) - a[t]; if (pos < K[t] && x == a[t][pos] && cc == 1) pos++; return gao(d[t][pos], c[t][pos] * (ll)x + b[t][pos], c[t][pos] * cc); } int main() { int T; scanf("%d", &T); for (int cas = 1; cas <= T; cas++) { printf("Case #%d: ", cas); scanf("%d", &n); for (int i = 1; i < n; i++) { scanf("%d", &K[i]); for (int j = 0; j <= K[i]; j++) { scanf("%d%d%d", &c[i][j], &b[i][j], &d[i][j]); if (j < K[i]) scanf("%d", &a[i][j]); } } int flag = 1; for (int i = n - 1; i >= 1; i--) { for (int j = 0; j < K[i]; j++) { ll left = gao(i, a[i][j], -1); ll right = gao(i, a[i][j], 1); ll mid = gao(i, a[i][j], 0); if (left != right || left != mid) { flag = 0; break; } } if (!flag) break; } puts(flag ? "YES" : "NO"); } return 0; }
1007 CCPC Training Class
题解:
看过了的人很多,观察样例猜一个出现最多次的字母次数就过了
#include <bits/stdc++.h> using namespace std; int a[26]; int main(){ int t;cin>>t; for(int cas=1;cas<=t;cas++){ string s; cin>>s; memset(a,0,sizeof a); for(int i=0;i<s.length();i++){ a[s[i]-'a']++; } sort(a,a+26); printf("Case #%d: %d\n",cas,a[25]); } return 0; }
1010 Reports
题意:
给定一个长度为的序列,询问序列是否不存在相邻且相等的元素
题解:
模拟即可
#include <bits/stdc++.h> using namespace std; int a[110]; int main(){ int t;cin>>t; while(t--){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } bool flag=true; for(int i=1;i<n;i++){ if(a[i]==a[i-1]){ flag=false; break; } } puts(flag?"YES":"NO"); } return 0; }
1011 3x3 Convolution
题意:
给定一个的矩阵和一个的矩阵,,,求
题解:
可以发现当除外有不为的数时,值一定会流失,最终只能变为全矩阵。因此只有当不为时才会为原矩阵。
具体证明:
#include <bits/stdc++.h> using namespace std; int a[55][55],k[4][4]; int main(){ int t;cin>>t; for(int cas=1;cas<=t;cas++){ int n; cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&a[i][j]); } } int sum=0; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ scanf("%d",&k[i][j]); sum+=k[i][j]; } } if(sum==k[0][0]){ for(int i=0;i<n;i++){ for(int j=0;j<n-1;j++){ printf("%d ",a[i][j]); } printf("%d\n",a[i][n-1]); } } else{ for(int i=0;i<n;i++){ for(int j=0;j<n-1;j++){ printf("0 "); } printf("0\n"); } } } return 0; }