2023河南萌新联赛第（八）场：南阳理工学院题解
萨米肉鸽
https://ac.nowcoder.com/acm/contest/64221/L
A,B,C,D,E,F,G,K,L题解
A题解 | #唯物丁真遇上唯心王源：到了群星就要拿出真本事
贪心，先建立所有bi=1的联通块
1、连通块内的节点是可以互通的不需要传送门，总物质和节点的总和；
2、连通块之间需要传送门联通，贪心选择总物质最大的m个连通块。
O(NlgN)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;
void my_ans(){
long long i,j,ij,n,m,k,w,q,l,r,x,y,ans =0,t;
cin>>n>>m>>k>>w;
long long a[n+1],b[n+1];
int c[n+1];
memset(c,0,sizeof(c));
for(i=1;i<=n;++i) cin>>a[i];
for(i=1;i<=n;++i) cin>>b[i];
vector<int> vc[n+1];
vector<long long> v1;
vector<int> v2;
for(i=0;i<m;++i){
cin>>x>>y; vc[x].push_back(y); vc[y].push_back(x);
}
for(i=1;i<=n;++i) if (b[i] ==1 && c[i] ==0){
v2.clear();v2.push_back(i); c[i] = 1;t=a[i]; j=0;
while(j<v2.size()){
x=v2[j];++j;
for(ij=0;ij<vc[x].size();++ij) if (b[vc[x][ij]] ==1 && c[vc[x][ij]] ==0){
y = vc[x][ij];
t+=a[y];c[y] = 1; v2.push_back(y);
}
}
v1.push_back(t);
}
sort(v1.begin(), v1.end());
i=v1.size()-1;
while(i>=0 && k>0){
ans+=v1[i];--i;--k;
}
cout<<ans<<endl;
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
long long t=1,i,j,l,r;
//scanf("%d",&t);
//cin>>t;
while(t>0){
--t;my_ans();
}
return 0;
}
// 64 位输出请用 printf("%lld")
B题解 | #小分分
线段覆盖前缀和，分两种情况处理：第一种是一个点被每组线段覆盖一次，第二种是一个点被每组线段覆盖两次。假设一个点，第一种覆盖的次数是k1，第二种覆盖的次数是k2，k1+k2=n则为好点，覆盖的方案数会2^k2。时间复杂度是O(max(n,max(y)))。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;
string s;
void my_ans(){
long long i,j,ij,n,m,k,w,q,l,r,l1,r1,x,y,ans =0,t,mod = 1000000007;
cin>>n;
int a[n+1][4];
int b[500005],c[500005];
long long d[n+1];
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(i=0;i<n;++i) {
cin>>l>>r>>l1>>r1;
x = max(l, l1);y = min(r,r1);
if (y>=x){
b[x]+=1;--b[y+1];
l=min(l,l1);r=max(r,r1);
if (l<x){
c[l]+=1;--c[x];
}
if (r>y){
c[y+1]+=1;--c[r+1];
}
}else{
c[l]+=1;--c[r+1];c[l1]+=1;--c[r1+1];
}
}
d[0] = 1;
for(i=1;i<=n;++i) d[i]= (d[i-1] * 2) % mod;
x=0;y=0;
for(i=1;i<=500000;++i){
x+=c[i];y+=b[i];
if (x+y ==n){
ans = (ans + d[y]) % mod;
}
}
cout<<ans<<endl;
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
long long t=1;
//scanf("%d",&t);
//cin>>t;
while(t>0){
--t;my_ans();
}
return 0;
}
// 64 位输出请用 printf("%lld")
C题解 | #头好痛感觉要长脑子了O.o
题目有明显按时答案不超过9e7，而ai是素数，n<=664579，先对ai进行去重排序(使用set)，复杂度是O(NlgN)，然后暴力枚举每一个num，复杂不超过9e7，注意超乘法判断会超过long long。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
int b[664579];
int n;
long long ans =0,r=0,mod = 90000000;
using namespace std;
inline long long read()
{
long long date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void check(int i,long long t){
long long k = r/t;
for(int j=i;j<n;++j){
if (b[j]>k) break;
++ans;
check(j,t*b[j]);
}
return;
}
void my_ans(){
long long i,t;
n=read();
set<int> st;
for(i=0;i<n;++i) {
t=read();
st.insert(t);
}
r = read();
n=0;auto it = st.begin();
while(it != st.end()){
t = *it;++it;
if (t<=r){
b[n] = t;++n;
}
}
check(0,1);
printf("%lld\n",ans);
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t=1;
while(t>0){
--t;my_ans();
}
return 0;
}
// 64 位输出请用 printf("%lld")
D题解 | #鼠鼠的机器人
模拟，假设走一次S指令之后的位置为(x1,y1)，第一次走S指令时每个指令的位置为pos[i][0],pos[i][1]。能走到目标（x,y)的条件是 pos[i][0]+k * x1 = x, pos[i][1]+k * y1 = y, 0<=k<=n。 扫描两次S指令便可判断结果了，O(N)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;
long long a[2002][2];
void my_ans(){
long long i,j,ij,n,m,k,w,q,l,r,x,y,ans =0,t;
cin>>x>>y;
cin>>n;
string s;
cin>>s;
if (x==0 && y==0){
cout<<"Yes"<<endl;return;
}
l=0;r=0;
for(i=0;i<s.size();++i){
if (s[i] == 'U') ++r;
else if (s[i] =='D') --r;
else if (s[i] =='L')--l;
else ++l;
if (l==x && r == y){
cout<<"Yes"<<endl;return;
}else{
a[i][0] = l; a[i][1] = r;
}
}
for(i=0;i<s.size();++i){
if (l==0){
if (x-a[i][0]==0){
if(r==0){
if (y- a[i][1] ==0) {
cout<<"Yes"<<endl;return;
}
}else if ((y- a[i][1]) %r ==0 && ((y- a[i][1]) /r <=n) && ((y- a[i][1]) /r >=0)){
cout<<"Yes"<<endl;return;
}
}
}else if (r==0){
if (y- a[i][1]==0){
if ((x - a[i][0]) % l ==0 && ((x- a[i][0]) /l <=n) && ((x- a[i][0]) /l >=0)){
cout<<"Yes"<<endl;return;
}
}
}else if ((x - a[i][0]) % l ==0 && (y- a[i][1]) %r ==0){
if (((x - a[i][0]) / l == (y- a[i][1]) /r) && ((y- a[i][1]) /r <=n) && ((y- a[i][1]) /r >=0)){
cout<<"Yes"<<endl;return;
}
}
}
cout<<"No"<<endl;
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
long long t=1,i,j,l,r;
//scanf("%d",&t);
cin>>t;
while(t>0){
--t;my_ans();
}
return 0;
}
// 64 位输出请用 printf("%lld")
E题解 | #bilabila
数学，其中五角星的外切圆半径=边长/tan(36°)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;
string s;
double PI = 3.141592653;
double my_cos(double x){
return cos(x*PI / 180.0);
}
double my_sin(double x){
return sin(x*PI / 180.0);
}
double my_tan(double x){
return tan(x*PI / 180.0);
}
void my_ans(){
long long i,j,ij,n,mod = 1000000007;
double R,x,y;
cin>>n;
R = n/my_tan(36);
double r = R* my_sin(18);
double ans[5][2];
if(n==0){
for(i=0;i<5;++i) ans[i][0] =0.00,ans[i][1] =0.00;
}else{
ans[0][0] = R * my_cos(18); ans[0][1] = 0.00;
ans[1][0] = R * my_cos(54); ans[1][1] = -R * my_sin(54)-r;
ans[2][0] = -R * my_cos(54); ans[2][1] = -R * my_sin(54)-r;
ans[3][0] = -R * my_cos(18); ans[3][1] =0.00;
ans[4][0] = 0; ans[4][1] = R-r;
}
char ch = 'A';
for(i=0;i<5;++i){
printf("%c: %0.2lf %0.2lf\n", ch+i, ans[i][0], ans[i][1]);
}
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
long long t=1;
//scanf("%d",&t);
//cin>>t;
while(t>0){
--t;my_ans();
}
return 0;
}
// 64 位输出请用 printf("%lld")
F题解 | #小前前
二进制位数前缀和，求[al,ar]之间每一位二进制是否出现过，然后再|x。时间复杂度O(N * 60)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;
void my_ans(){
long long i,j,n,q,l,r,x;
cin>>n>>q;
int a[n+1][70];
memset(a,0,sizeof(a));
for(i=1;i<=n;++i){
for(j=0;j<70;++j) a[i][j] = a[i-1][j];
cin>>x;j=0;
while(x>0){
if (x%2==1) ++a[i][j];
x=x/2;++j;
}
}
while(q>0){
cin>>l>>r>>x;--q;
for(i=0;i<70;++i) if (a[r][i]>a[l-1][i]){
j=1;
x = x | (j<<i);
}
cout<<x<<endl;
}
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
long long t=1,i,j,l,r;
//scanf("%d",&t);
//cin>>t;
while(t>0){
--t;my_ans();
}
return 0;
}
// 64 位输出请用 printf("%lld")
G题解 | #摸鱼大师
暴力枚举，预处理记录S串中连续相邻位置相同字符的头尾位置（两个方向），然后暴力枚举S串的每个位置为摸鱼起点，复杂度是O(13 * N)。补充一下，26个字母在a+b串中仅出现一次。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;
void my_ans(){
int i,j,ij,n,m,k,w,q,l,r,x,y,x1,y1,ans =0,t;
string s1,s2,s3;
cin>>s1;cin>>s2;cin>>s3;
n=s3.size();
int a[n],b[n];
a[0] = 0;
for(i=1;i<n;++i){
a[i] = i;
if (s3[i] == s3[i-1]) a[i] = a[i-1];
}
b[n-1] = n-1;
for(i=n-2;i>=0;--i){
b[i] = i;
if (s3[i] == s3[i+1]) b[i] = b[i+1];
}
for(i=1;i<n-2;++i){
for(j=0;j<13;++j) if (s1[j] == s3[i] && s2[j] == s3[i+1]) break;
if (j!=13){
x=i;y=i+1;l=j;
while(x>0 && y<n-1){
t=min(x-a[x], b[y]-y);
x=x-t;y=y+t;
if (x<=0 || y >= n-1) break;
while(l<13 && (s1[l] != s3[x-1] || s2[l] != s3[y+1])) ++l;
if (l==13) break;
--x;++y;
}
ans = max(ans, y-x+1);
}
}
if(ans <4) ans =0;
cout<<ans<<endl;
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
long long t=1,i,j,l,r;
//scanf("%d",&t);
//cin>>t;
while(t>0){
--t;my_ans();
}
return 0;
}
// 64 位输出请用 printf("%lld")
K题解 | #小千很好奇
数据范围很小，直接打表预处理了，时间复杂度O(1e6)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;
string s;
int n;
int a[1000001], b[1000001];
void init(){
string s1;
int i,j,t=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(i=2;i<1000001;++i) {
b[i] = b[i-1];
if (a[i] ==0){
j=i*2; ++b[i];
while(j<1000001){
a[j] = 1;j+=i;
}
}
}
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
long long t=1,l,r;
//scanf("%d",&t);
init();
cin>>t;
while(t>0){
--t;cin>>l>>r;
cout<<b[r] - b[l-1]<<endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")
L题解 | #萨米肉鸽
bfs就可以了，假设num[i]为节点i到根节点的路径数量（num[1] = 1), fa[i]为节点i的父节点，a1,a2,a3...ak是特殊边的连通块，则有
num[a1] = num[a2]...= num[ak], 且 num[a1] = num[fa[a1]]+num[fa[a2]]...+num[fa[ak]]
O(N)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;
void my_ans(){
long long i,j,ij,n,m,k,w,q,l,r,x,y,ans =0,t, mod = 1000000007;
cin>>n>>m;
int a[n+1], fa[n+1], child[n+1];
long long num[n+1];
vector<int> vc[n+1];
vector<int> v1;
for(i=0;i<n-1;++i){
cin>>x>>y;vc[x].push_back(y);vc[y].push_back(x);
}
memset(a,0,sizeof(a));
memset(child,0,sizeof(child));
v1.push_back(1);i=0;a[1] =1;
while(i<v1.size()){
x = v1[i];++i;
for(j=0;j<vc[x].size();++j) if (a[vc[x][j]] ==0){
a[vc[x][j]] =1;v1.push_back(vc[x][j]);
fa[vc[x][j]] = x;
++child[x];
}
}
for(i=0;i<=n;++i) vc[i].clear();
for(i=0;i<m;++i) {
cin>>x>>y;vc[x].push_back(y);vc[y].push_back(x);
}
memset(a,0,sizeof(a));a[1] = 1; num[1] =1;
vector<int> v2;
for(i=1;i<n;++i) if (a[v1[i]] ==0){
a[v1[i]] =1; v2.clear(); v2.push_back(v1[i]);j=0; t = num[fa[v1[i]]];
while(j<v2.size()){
x = v2[j];++j;
for(ij=0;ij<vc[x].size();++ij) if (a[vc[x][ij]] ==0){
a[vc[x][ij]] = 1; v2.push_back(vc[x][ij]);
t=(t+num[fa[vc[x][ij]]]) % mod;
}
}
for(j=0;j<v2.size();++j) num[v2[j]] = t;
}
for(i=1;i<=n;++i) if (child[i] ==0) ans = (ans + num[i]) % mod;
cout<<ans<<endl;
return;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
long long t=1,i,j,l,r;
//scanf("%d",&t);
//cin>>t;
while(t>0){
--t;my_ans();
}
return 0;
}
// 64 位输出请用 printf("%lld")
腾讯泡池子983人在聊
投递美团等公司7个岗位
查看15道真题和解析