当前位置: 首页 > news >正文

2025国庆Day5

模拟赛

T1

枚举b3

n^2 处理出a_b1^a_b2=x的所有情况(满足b2<i)

然后枚举b4,计算答案

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;	
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
int a[5005];
int mm[2000005];
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);int n=read();for(int i=1;i<=n;i++){a[i]=read();} int ans=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int zh=a[i]^a[j];ans+=mm[zh];}for(int j=1;j<i;j++){int zh=a[i]^a[j];mm[zh]++;}}cout<<ans<<'\n';return 0;
}

T2

首先若一个数两列全相同,一定为0

然后将其删去

注意若一个数高位全不同,这个数一定是p-1

进而发现所有数不同的高位数量都不同

根据这个算答案即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;	
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
int a[2005][4005],vis[2005];
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);int p=read();for(int i=0;i<p;i++){int sum=0;for(int j=0;j<p;j++) vis[j]=0;for(int j=0;j<2*p;j++){a[i][j]=read();if(j%2==0){if(!vis[a[i][j]]) sum++;vis[a[i][j]]=1;}}
//		cout<<sum<<'\n';if(sum==1){sum=0;for(int j=0;j<p;j++) vis[j]=0;for(int j=0;j<2*p;j++){if(j%2==1){if(!vis[a[i][j]]) sum++;vis[a[i][j]]=1;}}if(sum==1) cout<<0<<' ';else cout<<1<<' ';}else cout<<sum<<' ';}cout<<'\n';return 0;
}

T3

分治

对每个点求出到mid,mid+1的最短路

对每一行,求出当这一行最优时对哪些点产生贡献

这是一个二维数点,树状数组解决

递归时注意到最短路不一定在区间内部

所以需要处理区间内每个点到区间端点的最短路

容易发现改变的部分就是刚刚求出的到mid,mid+1最短路

注意求最短路可以dp(拐点较少,<=4),不要dij,多一个log

T4

先考虑k=1时dp

dpi,j,0/1,0/1,表示1~i插入完成最终序列有j个连续段,是否已经占据最终序列的开头,是否已经占据最终序列的结尾

image

数学

数论

素数

逆元

Wilson 定理

image

证明考虑乘法逆元

欧几里得算法

(exgcd)

image

中国剩余定理

扩展:对每个方程的模数质因数分解,对每个质数分别考虑check

转化成普通剩余定理

exgcd即可

积性函数

容易发现积性函数f(1)=1

完全积性函数,省去互素条件

埃氏筛

线性筛

思路可拓展求积性函数前缀和

整数分块

离散对数

莫比乌斯反演+欧拉反演

组合数学

插板法

例题

image

考虑乘积的组合意义

插板后对每个段加一个小球

再次进行插板

共插2p+1个板

容斥原理

min-max反演

二项式反演

斯特林数

image

错排

1.递推

2.容斥

卡特兰数

转化在数轴上

格路计数

两条线?

不合法容斥系数=0

prufer序列

一棵n个点有标号的无根树有n^(n-2)个

生成prufer序列:

image

还原树:

image

线性代数

矩阵加/乘

矩阵乘组合意义:i->j的方案数

向量

矩阵快速幂

高斯消元

主元和自由元

线性空间

线性相关

称一组线性空间的秩,为其最大的内部线性无关子空间

可以使用高斯消元求解

对于一组解,我们称之为线性基

正交线性基

对于每一个主元,保证只有一个数是包含它的

行列式

image

发现相邻行之间加减不影响最终结果

高斯消元变成阶梯矩阵

易求答案

http://www.hskmm.com/?act=detail&tid=25638

相关文章:

  • 字节跳动开源图标库:2000+图标一键换肤的魔法 - 教程
  • 换根DP学习笔记
  • 自动化数据操作平台获3000万美元融资
  • 模块
  • 实用指南:【相机基础知识与物体检测】更新中
  • AtCoder Beginner Contest 422 游记(VP)
  • 详细介绍:无人机光纤FC接口模块技术分析
  • 2025 --【J+S 二十连测】-- 第十三套 总结
  • 文件提供的基本操作
  • 深入解析:MySQL(50)如何使用UNSIGNED属性?
  • 迈向人机价值共生文明:AI元人文范式下的演化架构与协同治理
  • 10.6
  • 文件存储空间管理
  • 详细介绍:关于ios点击分享自动复制到粘贴板的问题
  • 新一代数据平台替代传统大数据技术栈
  • 攻击者如何绕过macOS内置安全防护机制
  • 在A列连续且相等行的最后插入空行,并求和
  • 10.6集训改错
  • @Prometheus 监控-MySQL (Mysqld Exporter) - 教程
  • AI元人文:走向人机价值共生的文明新范式
  • 实用指南:【机器学习基础】机器学习入门核心算法:层次聚类算法(AGNES算法和 DIANA算法)
  • CSP-J 第二轮集训 :总结 + 专题细分精讲_from_黄老师
  • ROIR 2024
  • 软件工程第一次随笔 - Nicholas
  • 深入解析:【数据库】关系数据库标准语言-SQL(金仓)下
  • Codeforces Round 1056 (Div. 2) (4/6)
  • 20251006
  • UV使用
  • 动手实验——mybatis generator
  • 学生管理系统面向对象分析报告