2024年寒假开学赛题解

题目	知识点	难度/10
组合数（易）	签到题	1
最高海拔	签到题/前缀和	2
连续自然数	数学/前缀和	3
这题主要考察了找规律	递推	4
这题主要考察了画画	贪心 思维	4
组合数（难）	数学 + 预处理	5
这题主要考察了图的遍历	DFS&BFS	6
昨夕是何天	模拟	6
修路	并查集	6
倍数	倍数的特点	6
算两次	质因数分解	7
或与异或	位运算 思维	8
这题主要考察了DP	DP	8

combinatorial number（easy）

本场第一签到，根据公式直接算就行了，注意开long long

#include<bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 100010, mod = 1e9 + 7;void solve()
{int a, b;cin >> a >> b;LL ans1 = 1, ans2 = 1;for (int i = 1, j = a; i <= b; i ++, j --){ans1 *= j;ans2 *= i;}cout << ans1/ ans2 << endl;
}int main()
{int q;cin >> q;while (q --) solve();return 0;
}

combinatorial number（normal）

由于$(a+b)\%mod=(a\%mod+b\%mod)\%mod$，根据递推公式$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$，可以求出所有的答案，每次询问时输出预处理出来的答案即可

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
void init()
{for (int i = 0; i < N; i ++ )for (int j = 0; j <= i; j ++ )if (!j) c[i][j] = 1;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}int main()
{init();int n;cin >> n;while (n --){int a, b;cin >> a >> b;cout << c[a][b] << endl;}return 0;
}

大家去学一下逆元，也可以用下面的方法做

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long 
const int MAX=1e5+10;
const ll mod=1e9+7;
int n, m;
int fact[MAX], infact[MAX];
int quick_power(int a,int b)
{int ans = 1;while(b){if(b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}
void init()
{fact[0] = infact[0] = 1;for(int i = 1 ; i < MAX ; i ++){fact[i] = fact[i-1] * i % mod;infact[i] = infact[i-1] * quick_power(i,mod-2) % mod;}
}
void solve()
{cin >> n >> m;cout << (fact[n]%mod*infact[m]%mod*infact[n-m]%mod)%mod << endl; 
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int _;cin >> _;//_ = 1;init();  while(_--) solve();return 0;
}

这题主要考察了画画

这种题可以多观察一下样例

可以贪心地先把一行填满，每填一个方块可贡献2条需要的对角线(不重复的)，剩下的只能填一个，贡献一条对角线了

void solve()
{int n,m;cin >> n >> m;n = n + max(0,n-2);if(m <= 2*n){if(m&1) cout << (m >> 1) + 1 << endl;else cout << (m >> 1) << endl;}else {cout << n + (m - 2 * n) << endl;}}

这题主要考察了DP

#include<bits/stdc++.h>
using namespace std;
int n, m;
const int N = 510;
double dp[N][N];
void solve()
{cin >> n >> m;//dp[i][j]表示前i个人用了j个仙贝的好感度，k为枚举第i个人获得的仙贝数for(int i = 1 ; i <= n ; i++)for(int j = 1 ; j <= m ; j++)for(int k = 1 ; k <= j ; k++)dp[i][j] = max(dp[i][j],dp[i-1][j-k] + k*1.0/(m*1.0-(j-k)*1.0));
}
int main()
{int _;_ = 1;while(_--) solve();printf("%.6f",dp[n][m]);
}

这题主要考察了图的遍历

跑一边dfs和bfs的板子就行了，但要注意题目要求，如果有很个节点可以遍历，先遍历序号小的。

所有用set存边或者用vector存，然后排序

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 +  100;
set<int> e[N];
int n, m;
int vis[N];
queue<int> q;
void dfs(int u)
{if(vis[u]) return;vis[u] = 1 ;cout << u << " ";for(auto v : e[u]) dfs(v);
}
void bfs()
{q.push(1);while(q.size()){int u = q.front(); q.pop();if(vis[u]) continue;vis[u] = 1;cout << u << " ";for(int v : e[u]) q.push(v);}
}
int main()
{cin >> n >> m;for(int i = 1 ; i <= m ; i ++) {int u, v;cin >> u >> v ;e[u].insert(v);}dfs(1);cout << endl;memset(vis , 0 , sizeof vis);bfs();return 0;
}

这题主要考察了找规律

题目肯定是骗人的，这哪儿来的规律，和爬楼梯类似，第i阶只能由第i-1和i-阶爬到，直接递推就好了，注意开long long

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
long long f[N];
int a[N];
void solve(){//这里放自己程序的主函数//自己程序的其他函数，直接写在其他地方就行了memset(f,0,sizeof f);int n;scanf("%d",&n);for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);f[0] = 0 , f[1] = a[0];for(int i = 2 ; i <= n ; i ++)f[i] = min(f[i-1] + (long long)a[i-1],f[i-2]+(long long)a[i-2]);printf("%lld",f[n]);
}int main(void)
{solve();return 0;
}

我就站在你眼前，你看我有几分像从前

这题是第三次考核题目，但出题的时候发现还是没有一个人补体，所有出出来让大家体会一下没补题的后悔

正解是质因数分解，但是我们给的程序直接取合适的模数也可以

#include <bits/stdc++.h>
#define ll long long
#define N 100005
int f[N],p[N],nu1[N],nu2[N];
int num1=0,num2=0;
int ma=0;
using namespace std;
int num=0;
void init_p()
{f[1]=1;num=0;for(int i=2;i<=N;i++){if(f[N]==0){p[++num]=i;}for(int j=1;j<=num;j++){if(i*p[j]<N) f[i*p[j]]=1;if(i%p[j]==0||i*p[j]>N) break;}}
}
int main()
{init_p();int m;scanf("%d",&m);for(int i=1;i<=m;i++){int op,x;scanf("%d%d",&op,&x);if(x<0){num1++;x=-1*x;}ma=max(ma,x);if(op==1){for(int i=1;p[i]<=x;i++){if(f[x]==0){nu1[x]++;break;}while(1){if(x%p[i]==0){nu1[p[i]]++;x/=p[i];}else break;}}}else {for(int i=1;p[i]<=x;i++){if(f[x]==0){nu1[x]--;break;}while(1){if(x%p[i]==0){nu1[p[i]]--;x/=p[i];}else break;}}}}scanf("%d",&m);for(int i=1;i<=m;i++){int op,x;scanf("%d%d",&op,&x);if(x<0){num2++;x=-1*x;}ma=max(ma,x);if(op==1){for(int i=1;p[i]<=x;i++){if(f[x]==0){nu2[x]++;break;}while(1){if(x%p[i]==0){nu2[p[i]]++;x/=p[i];}else break;}}}else {for(int i=1;p[i]<=x;i++){if(f[x]==0){nu2[x]--;break;}while(1){if(x%p[i]==0){nu2[p[i]]--;x/=p[i];}else break;}}}}if(num1%2!=num2%2){printf("NO");return 0;}for(int i=1;p[i]<=ma;i++){if(nu1[p[i]]!=nu2[p[i]]){printf("NO");return 0;}}printf("YES");return 0;
}

修路

考察并查集 如果两个村庄要修路，就合并，每次合并之前查询

#include <bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
int p[N],r[N];
int find(int x)
{if(x==p[x]) return p[x];else {p[x]=find(p[x]);return p[x];}
}
void join(int x,int y)
{int rx=find(x),ry=find(y);if(r[rx]<r[ry]) p[rx]=ry;else {p[ry]=rx;if(r[rx]==r[ry]) r[rx]++;}}
void init(int n)
{for(int i=1;i<=n;i++){p[i]=i;r[i]=1;}
}int n,m; 
void slove()
{scanf("%d%d",&n,&m);init(n);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);if(find(x)==find(y)){printf("No\n");}else {join(x,y);printf("Yes\n");}}
}
int main()
{ll t;t=1;while(t--){slove();}return 0;}

倍数

大家要去了解一下怎么判断这些数的倍数

#include <bits/stdc++.h>
#define ll long long
using namespace std;
string s;
int len;
int num[10];
ll get_sum()
{ll ret=0;for(int i=0;i<len;i++){ret+=(s[i]-'0');}return ret;
}
ll get_he(int x)
{ll ret=0;for(int i=x;i>=1;i--){ret=ret*10+(s[len-i]-'0');}return ret;
}
int main() 
{int q;scanf("%d",&q);while(q--){cin>>s;len=s.length();ll sum=get_sum();if((s[len-1]-'0')%2==0) {num[2]++;if(sum%3==0) num[6]++;}if(sum%3==0) num[3]++;if(len>=2){int x=get_he(2);if(x%4==0) num[4]++;}else {int x=get_he(1);if(x%4==0) num[4]++;} if(s[len-1]=='0'||s[len-1]=='5'){if(s!="0") num[5]++;}if(len>=3){int x=get_he(3);if(x%8==0) num[8]++; }else if(len==2){int x=get_he(2);if(x%8==0) num[8]++;}else {int x=get_he(1);if(x%8==0) num[8]++;}if(sum%9==0) num[9]++;}for(int i=2;i<=9;i++){if(i==7) continue;printf("%d ",num[i]);}
}

或与异或

#include <bitsdc++.h>
#define ll long long
using namespace std;
int q;
ll x,y,z;
ll a,b;
int get_ans()
{ll p=1;do{ll xx=x%2,yy=y%2,zz=z%2;x/=2;y/=2;z/=2;if(xx==0&&yy==1) return 0;if(zz==0){if(xx!=yy) return 0;else {if(xx==1){a+=p;b+=p;}}}else {if(xx==0||yy==1) return 0;else {a+=p;}}p*=2;}while(x||y||z);return 1;
}
int main()
{scanf("%d",&q);while(q--){scanf("%lld %lld %lld",&x,&y,&z);a=0,b=0;if(get_ans()){printf("%lld %lld\n",a,b);}else printf("-1 -1\n");}return 0;
}

#include <bitsdc++.h>
#define ll long long
using namespace std;
int q;
ll x,y,z;
ll a,b;
int get_ans()
{ll p=1;do{ll xx=x%2,yy=y%2,zz=z%2;x/=2;y/=2;z/=2;if(zz==0){if(xx!=yy) return 0;else {if(xx==1){a+=p;b+=p;}}}else {if(xx==0||yy==1) return 0;else {a+=p;}}p*=2;}while(x||y||z);return 1;
}
int main()
{scanf("%d",&q);while(q--){scanf("%lld %lld %lld",&x,&y,&z);if((x^y)==z&&(x|y)==x&&(x&y)==y) printf("%lld %lld\n",x,y);else printf("-1 -1\n");}return 0;
}

前夕是何天

按照题意，计算日期即可

这里有一份把日历存下来，每次询问直接访问的代码

#include <bits/stdc++.h>
using namespace std;
string data[400005];
map <string,int> mp;
int num=0;
string int_to_str(int x,int len)
{string ret="";for(int i=1;i<=len;i++){ret=(char)(x%10+'0')+ret;x/=10;}return ret;
}
void get_data()
{int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};for(int y=2000;y<=3000;y++){if((y%4==0&&y%100!=0)||(y%400==0)) day[2]=29;else day[2]=28;string year=int_to_str(y,4)+'-';for(int m=1;m<=12;m++){string month=int_to_str(m,2)+'-';for(int d=1;d<=day[m];d++){string time=year+month+int_to_str(d,2);data[++num]=time;mp[time]=num;}}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);get_data();int q;string t;int k;cin>>q;while(q--){cin>>t>>k;int id=mp[t];cout<<data[id-k]<<'\n';}return 0;
}

最高海拔

应该算是本场第二签，前缀和求出来然后找到最大值，输出这个点就好了

#include <stdio.h>
#define ll long long
int main()
{ll ma=0,ip=0,sum=0;int n;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);sum+=x;if(sum>ma){ma=sum;ip=i;}}printf("%d %d",ip,ma);return 0;
}