因题目录入时出现了失误，导致部分题目题面以及数据范围发生错误，赛时及时进行了修改，对此我们深感抱歉。
事先声明：由于此比赛面向普通学生，所以题目的难度较低，如果您非本校学生且对此比赛的难度表示不满，我在这里谨代表校方表示诚挚的歉意，同时，此比赛题目均为本校学生原创或改编，如有雷同，纯属巧合，此外，如果您认为题目中有任何不合理或者错误的地方，欢迎在评论区批评指正。
难度预估
Easy:H L
Easy-Mid:A G I J
Mid:C E K
Hard:B D F
A 纯粹的数学符号
，直接求和即可
时间复杂度
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int n,sum,x;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
sum+=x*(n-1);
}
cout<<sum;
return 0;
}
B 狼人杀
这题其实是22nd 浙江省赛L题的变形，加了一些条件把贪心思想限制了，题目思路其实不难，用基环树DP的思想即可过题。（没能让大佬们感到尽兴我们感到很抱歉，我们实力太弱了QAQ）
玩家指认玩家
是狼人，其关系可以表示为
->
则会产生如下几种情况：
1.狼->平民（符合条件）
2.平民->狼（符合条件）
3.平民->平民（符合条件）
4.狼->狼（不符合条件）
因此无论连双向边还是连单向边，我们只需要保证相邻的两个节点不全为狼即可符合题目条件
每一个玩家都有一个指认的对象，对于每一个联通块，必定会存在一个环，因此每个联通块就是一个基环树。
到这里就很清晰了，对于每个联通块，我们要进行基环树dp，使得幸福值最大即可。
至于怎么dp，可以拆分成两个部分：
1.树形dp预处理环上的点作为一棵树的根节点时，根结点当平民和当狼时此树的最大幸福值。
2.环形dp得到当前基环树的最大幸福值。
//树形dp，定义a[i][0/1]为i节点当平民/狼的最大幸福值
a[u][1]+=a[v][0];
a[u][0]+=max(a[v][1],a[v][0]);
//把环拆成链，再定义一维记录首位状态防止首尾冲突
//环形dp，定义f[i][0/1][0/1]为i节点当平民/狼时其环的起始节点当平民/狼的最大幸福值，tmp数组里是当前联通块环上的结点
f[i][0][1]=max(f[i-1][0][1],f[i-1][1][1])+a[tmp[i-1]][0];
f[i][1][1]=f[i-1][0][1]+a[tmp[i-1]][1];
f[i][0][0]=max(f[i-1][0][0],f[i-1][1][0])+a[tmp[i-1]][0];
f[i][1][0]=f[i-1][0][0]+a[tmp[i-1]][1];
除此之外，我们还需要考虑一些细节，比如多个联通块，自环……
时间复杂度
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
vector<int>g[N];
int n,ans,b[N],c[N];
int cycle[N],du[N],vis[N];
int a[N][2];
int f[N][2][2];
void top(){
queue<int>q;
for(int i=1;i<=n;i++){
if(du[i]==1){
q.push(i);
}
}
while(q.size()){
int u=q.front();
q.pop();
cycle[u]=0;
for(int v:g[u]){
du[v]--;
if(du[v]==1) q.push(v);
}
}
}
void dfs(int u,int fa){
a[u][0]=b[u];
a[u][1]=c[u];
for(int v:g[u]){
if(v==fa || cycle[v]) continue;
dfs(v,u);
a[u][1]+=a[v][0];
a[u][0]+=max(a[v][1],a[v][0]);
}
}
void cycle_dp(int u){
vector<int>tmp;
while(!vis[u]){
vis[u]=1;
tmp.push_back(u);
for(int v:g[u]){
if(!cycle[v] || vis[v]) continue;
u=v;
break;
}
}
int siz=tmp.size();
for(int i=0;i<=siz;i++){
f[i][0][0]=-2e18;
f[i][0][1]=-2e18;
f[i][1][0]=-2e18;
f[i][1][1]=-2e18;
}
f[1][1][1]=a[tmp[0]][1];
f[1][0][0]=a[tmp[0]][0];
for(int i=2;i<=siz;i++){
f[i][0][1]=max(f[i-1][0][1],f[i-1][1][1])+a[tmp[i-1]][0];
f[i][1][1]=f[i-1][0][1]+a[tmp[i-1]][1];
f[i][0][0]=max(f[i-1][0][0],f[i-1][1][0])+a[tmp[i-1]][0];
f[i][1][0]=f[i-1][0][0]+a[tmp[i-1]][1];
}
ans+=max({f[siz][0][1],f[siz][1][0],f[siz][0][0]});
}
signed main(){
cin>>n;
for(int i=1,fa;i<=n;i++){
cin >> fa;
g[fa].push_back(i);
g[i].push_back(fa);
du[i]++;
du[fa]++;
cycle[i]=1;
}
for(int i=1;i<=n;i++){cin >> b[i];}
for(int i=1;i<=n;i++){cin >> c[i];}
top();
for(int i=1;i<=n;i++){
if(cycle[i]){
dfs(i,-1);
}
}
ans=0;
for(int i=1;i<=n;i++){
if(cycle[i] && !vis[i]){
cycle_dp(i);
}
}
cout << ans;
return 0;
}
C 哪个七海？
利用欧拉函数预处理出每个难度对应的价格然后背包即可
关于欧拉函数可以像题解中使用试除法求得，同时，不难发现由于m只有不超过1e4，所以有效的难度范围大约为1e5，利用欧拉筛预处理也可通过本题，且更快
时间复杂度
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
int a[N],b[N],dp[N];
int phi(int x){
if(x>1e7)return 1e9;
int res=x;
for(int i=2;i*i<=x;i++){
if(x%i==0){
res=res/i*(i-1);
while(x%i==0)x/=i;
}
}
if(x>1)res=res/x*(x-1);
return res;
}
signed main()
{
int n,m,ans=0;cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=phi(a[i]);
}
for(int i=1;i<=n;i++) for(int j=m;j>=b[i];j--) dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
for(int i=m;i>=0;i--)ans=max(ans,dp[i]);
cout<<ans;
return 0;
}
D 三块石头
对于三元组(a,b,c) 要想让其变为 (d,e,f) 我们考虑让后者对前者做差即(d,e,f)-(a,b,c)=(x,y,z)
这样问题就转化为，能不能让(0,0,0) 变成 (x,y,z)
首先如果x,y,z任意一个为负数则无解
接着考虑操作2，可以得出这么一个结论: (x,y,z)必然可以从(x%3,y%3,z%3)演变而来
然后扩展一下不难得出，若x,y,z大于等于3 且能演变出 (x%3+3,y%3+3,z%3+3)，则 (x,y,z) 必然可以演变出来
由此x,y,z的所有情况不会超过6 * 6 * 6，那么我们可以用任意方法(包括不限于dfs,dp,直接数学推论)，预处理出所有情况，对于所有查询就可以直接得出结论了
时间复杂度，此为预处理复杂度，记忆化搜索复杂度与此差不多
#include<bits/stdc++.h>
using namespace std;
bool dp[7][7][7];
bool DFS(int x,int y,int z){
if(x<0 || y<0 || z<0) return false;
if(x>6) x = 3 + x%3;
if(y>6) y = 3 + y%3;
if(z>6) z = 3 + z%3;
if(dp[x][y][z]) return true;
return dp[x][y][z] = (DFS(x-3,y,z) || DFS(x,y-3,z) || DFS(x,y,z-3)
|| DFS(x-1,y-1,z) || DFS(x-1,y,z-1) || DFS(x,y-1,z-1));
}
bool check(int x,int y,int z){
if(x<0 || y<0 || z<0) return false;
if(x>6) x = 3 + x%3;
if(y>6) y = 3 + y%3;
if(z>6) z = 3 + z%3;
return dp[x][y][z];
}
int main(){
dp[0][0][0] = true;
int T,a,b,c,d,e,f;
for(int i=0;i<=6;i++){
for(int j=0;j<=6;j++){
for(int k=0;k<=6;k++){
dp[i][j][k] = DFS(i,j,k);
}
}
}
scanf("%d",&T);
while (T--){
scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f);
bool flag = check(d-a,e-b,f-c) || check(d-a,e-c,f-b) || check(d-b,e-a,f-c)
|| check(d-b,e-c,f-a) || check(d-c,e-a,f-b) || check(d-c,e-b,f-a);
puts(flag?"yes":"no");
}
return 0;
}
E 特殊安排
老师只有两个人，考虑从老师下手
我们先默认没有老师不允许相邻这个条件，此时只需要求出2位老师和m位女生所组成的方案数，而后将其视为一个整体，再加入n个男生算出方案数即可
但此时不满足老师不允许相邻这个条件，不难发现，在上述方案数中，非法的方案总是两个老师站在一起，故我们可以将其视为一个整体，算出一个老师和同学们所能组成的方案数，而后容斥即可
时间复杂度，此处忽视组合数预处理大小
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e7+10;
const int mod=1e9+7;
int inv[N],jc[N];
int ksm(int a,int b){int res=1;for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;return res;}
void init(){
jc[0]=1,jc[1]=1,inv[1]=1;
for(int i=2;i<=1e7;i++)jc[i]=jc[i-1]*i%mod;
inv[N-10]=ksm(jc[N-10],mod-2);
for(int i=N-10;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
int C(int n,int m){
if(n<m||m<0)return 0;
return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
init();ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);int t;cin>>t;
while(t--){
int n,m;cin>>n>>m;
if(n>m+3){
cout<<0<<endl;
continue;
}
int a=C(m+2,2)*2%mod*jc[m]%mod*C(m+3,n)%mod*jc[n]%mod,b=(m+1)*2%mod*jc[m]%mod*C(m+2,n)%mod*jc[n]%mod;
cout<<((a-b)%mod+mod)%mod<<endl;
}
return 0;
}
F 宝石箱
从第一个宝箱里找i个意味着从第二个宝箱里找k-i个，故求
通过范德蒙德卷积变换后得到(如无过多考虑可直接得出此式)
求组合数即可
考虑到较大的NM以及较小的P，选择使用卢卡斯定理求组合数
时间复杂度
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e7+10;
int n,m,k,p,inv[N],jc[N];
int ksm(int a,int b){int res=1;for(;b;b>>=1,a=a*a%p)if(b&1)res=res*a%p;return res;}
void init(){
jc[0]=1,jc[1]=1,inv[1]=1;
for(int i=2;i<p;i++)jc[i]=jc[i-1]*i%p;
inv[p-1]=ksm(jc[p-1],p-2);
for(int i=p-1;i>=1;i--)inv[i-1]=inv[i]*i%p;
}
int C(int a,int b){
if(a<b||b<0)return 0;
return jc[a]*inv[b]%p*inv[a-b]%p;
}
int lucas(int a,int b){
if(a<p&&b<p)return C(a, b);
return (int)C(a%p,b%p)*lucas(a/p,b/p)%p;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t;cin>>t;
while(t--){
cin>>n>>m>>k>>p;init();
if(k>n+m)cout<<0<<endl;
else if(k==0)cout<<1<<endl;
else cout<<lucas(n+m,k)%p<<endl;
}
return 0;
}
G 验证TFF
不难发现i*(i+1)/2很快便会超过1e9，预处理后暴力匹配即可
时间复杂度
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
map<int,int> mp1;
signed main(){
for(int i=0;i*(i+1)/2<=1e9;i++) mp1[i*(i+1)/2]=1;
int t;cin>>t;
for(int i=1;i*(i+1)/2<=t;i++){
if(mp1[t-i*(i+1)/2]){
cout<<"YES";
return 0;
}
}
cout<<"NO";
return 0;
}
H 我是签到
真签到题
#include <bits/stdc++.h>
using namespace std;
string s,t;
int main(){
cin>>s;t=s;
reverse(t.begin(),t.end());
cout<<t<<endl;
if(s==t) cout<<"Family Guy";
return 0;
}
I 赌神比点
对手B只考虑最大三张牌+最小三张牌的情况，记作maxB和minB
暴力枚举A选手的所有情况，大小得分分别记作maxA,minA
只要存在minA＞maxB或者 (minA==maxB && maxA大于minB ) 则必定获胜
时间复杂度，C不超过216
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define int long long
using namespace std;
int getCard(){
string s;cin>>s;
if(s=="A") return 1;
if(s=="J") return 11;
if(s=="Q") return 12;
if(s=="K") return 13;
if(s=="10") return 10;
return s[0] - '0';
}
signed main(){
int t;cin>>t;
while(t--){
int a[6],b[6],sum=0,flag=0;
for(int i=0;i<6;i++){a[i]=getCard();sum+=a[i];}
for(int i=0;i<6;i++){b[i]=getCard();}
sort(b,b+6);
int minB=b[0]+b[1]+b[2],maxB=b[3]+b[4]+b[5];
for(int i=0;i<=2;i++){
for(int j=i+1;j<=4;j++){
for(int k=j+1;k<=5;k++){
int maxA=a[i]+a[j]+a[k];
int minA=sum-maxA;
if(maxA<minA) swap(minA,maxA);
if(minA>maxB || (minA==maxB && maxA>minB) )flag=1;
}
}
}
cout<<(flag ? "yes" : "no")<<endl;
}
return 0;
}
J Simple
根据期望公式求解即可，公式为
时间复杂度
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int t;cin>>t;
while(t--){
double x,y,p,es=0.0;
cin>>x>>y>>p;
for(int m=0;m<=7;m++){
double c=1.0;
for(int k=1;k<=m;k++) c*=(7-(m-k))/(double)k;
double prob=c*pow(p,m)*pow(1-p,7-m);
es+=prob*(y/(m+1));
}
cout<<fixed<<setprecision(6)<<es<<endl;
}
return 0;
}
K 通讯节点破解计划
按时间窗口的结束时间排序，依次选择不重叠的最早结束的窗口，保证后续有更多选择空间。
步骤
- 将所有节点按结束时间
升序排序。
- 初始化当前结束时间
，计数器
。
- 遍历排序后的节点：若当前节点的开始时间
，选择该节点，更新
，
时间复杂度按
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,sum;
pair<int,int>a[N];
signed main(){
cin>>n;
for(int i=1,l,r;i<=n;i++)cin>>a[i].second>>a[i].first;
sort(a+1,a+1+n);
int last=-1e9,ans=0;
for(int i=1;i<=n;i++){
if(a[i].second>last){
last=a[i].first;
ans++;
}
}
cout<<ans;
return 0;
}
L 3的倍数
能被3整除意味着数位和能被3整除，求数位和判断即可
时间复杂度，n为字符串平均长度
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
signed main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--){
int ans=0;string s;
cin>>s;
for(char c:s) ans+=c-'0';
if(ans%3==0) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
京公网安备 11010502036488号