2025 乔斯集训
chenyiran2012 · · 个人记录
2025 乔斯集训
注：具体内容可见课件/deepseek/OI Wiki
DAY 1
上午：
1. 广搜拓展 bfs spfa floyd
普通最短路 + 带权最短路
普通最短路：队列 queue 队尾插入删除
带权最短路： 01广搜 时间复杂度和普通广搜一样
2. 01广搜 时间复杂度和普通广搜一样
双端队列 deque 支持从队首队尾插入删除元素
链式前向星
点个数 n<=10^5 边条数 m<=10^6 一张有向图 边权0或1 求点1到其他点的最短路
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
const int maxn=100100;
const int maxm=1001000;
struct node{
int next,to,len;
}edge[maxm];
int h[maxn],tot;
int n,m;
deque<int> T;
int dis[maxn],vis[maxn];
void add(int x,int y,int z){
tot++;
edge[tot].to=y;
edge[tot].len=z;
edge[tot].next=h[x];
h[x]=tot;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i=1;i<=m;i++){
int x,y,z;
cin >> x >> y >> z;
add(x,y,z);
}
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
T.push_back(1);
while (!T.empty()){
int u=T.front();
T.pop_front();
if (vis[u]){
continue;
}
vis[u]=1;
for (int i=h[u];i;i=edge[i].next){
int to=edge[i].to;
dis[to]=min(dis[to],dis[u]+edge[i].len);
if (edge[i].len==0){
T.push_front(to);
}
else{
T.push_back(to);
}
}
}
cout << dis[某一个点];
return 0;
}Bishop 2 bfs练习
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
char a[1510][1510];
int kf[5][2]={{},{1,1},{1,-1},{-1,1},{-1,-1}};
deque<array<int,4>> q;
int dis[1510][1510][5];
int INF=1e9;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int qx,qy;
cin >> qx >> qy;
int zx,zy;
cin >> zx >> zy;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cin >> a[i][j];
}
}
fill(dis[0][0],dis[n+1][0],INF);
// for (int i=0;i<=n+1;i++){
// for (int j=0;j<=4;j++){
// dis[i][0][j]=INF;
// }
// }
q.push_back({qx,qy,0,0});//坐标 方向 步数
while (!q.empty()){
auto p=q.front();
q.pop_front();
if (a[p[0]][p[1]]=='.' && dis[p[0]][p[1]][p[2]]==INF){
dis[p[0]][p[1]][p[2]]=p[3];
q.push_front({p[0]+kf[p[2]][0],p[1]+kf[p[2]][1],p[2],p[3]});
for (int i=1;i<=4;i++){
q.push_back({p[0],p[1],i,p[3]+1});
}
}
}
int sum=min({dis[zx][zy][1],dis[zx][zy][2],dis[zx][zy][3],dis[zx][zy][4]});
if (sum==INF){
cout << -1;
}
else{
cout << sum;
}
return 0;
}
5
1 3
3 5
....#
...#.
.....
.#...
#....
3例题 P5 Chamber of Secrets
错误原因：忘记给距离数组初始化（0x3f）,输出n,m写错，4个方向0-3写成0-4
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
char a[1010][1010];
int n,m;
// 右下左上
// 0 1 2 3
struct node{
int next,tox,toy,tod,len;// 行 列 方向
}edge[1010*1010*20];
int h[1010][1010][4],tot;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void add(int x,int y,int d,int dx,int dy,int dd,int bq){
// tot++;
// edge[tot].tox=x;
// edge[tot].toy=y;
// edge[tot].tod=d;
// edge[tot].len=bq;
// edge[tot].next=h[x][y][d];
// h[x][y][d]=tot;
tot++;
edge[tot].tox=dx;
edge[tot].toy=dy;
edge[tot].tod=dd;
edge[tot].len=bq;
edge[tot].next=h[x][y][d];
h[x][y][d]=tot;
}
int dis[1010][1010][4],vis[1010][1010][4];
deque<pair<pair<int,int>,int>> q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cin >> a[i][j];
if (a[i][j]=='#'){//有镜子
for (int k=0;k<=3;k++){
for (int o=0;o<=3;o++){
if (k!=o){
add(i,j,k,i,j,o,1);
}
}
}
}
//四个方向移动
for (int k=0;k<=3;k++){
if (i+dx[k]>=1 && i+dx[k]<=n && j+dy[k]>=1 && j+dy[k]<=m){
add(i,j,k,i+dx[k],j+dy[k],k,0);
}
}
}
}
bool fg=0;
for (int i=1;i<=m;i++){
if (a[n][i]=='#'){
fg=1;
}
}
if (fg==0){
cout << -1;
return 0;
}
q.push_back({{1,1},0});
memset(dis,0x3f3f3f,sizeof(dis));
dis[1][1][0]=0;
while (!q.empty()){
pair<pair<int,int>,int> p=q.front();
//cout << p.first.first << " " << p.first.second << " " << p.second << endl;
q.pop_front();
if (vis[p.first.first][p.first.second][p.second]){
continue;
}
vis[p.first.first][p.first.second][p.second]=1;
for (int i=h[p.first.first][p.first.second][p.second];i;i=edge[i].next){
int x=edge[i].tox,y=edge[i].toy,d=edge[i].tod;
dis[x][y][d]=min(dis[x][y][d],dis[p.first.first][p.first.second][p.second]+edge[i].len);
if (edge[i].len==0){
q.push_front({{x,y},d});
}
else{
q.push_back({{x,y},d});
}
}
}
if (dis[n][m][0]==0){
cout << -1;
}
else{
cout << dis[n][m][0];
}
return 0;
}3. 折半搜索 dfs
分别暴力搜索前半边和后半边
结果存储
前半边枚举，后半边二分/lower_bound
例题 P6 世界冰球锦标赛
错误原因：方法种数计算错误
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int n;
long long m;
long long a[50];
long long l[10000010],r[10000010],cnt=0,mnk=0;
void dfs1(int x,long long sum){
if (x==n/2+1){
cnt++;
l[cnt]=sum;
return;
}
dfs1(x+1,sum+a[x]);
dfs1(x+1,sum);
}
long long num=0;
void dfs2(int x,long long sum){
if (sum>m){
return;
}
if (x==n+1){
num+=upper_bound(l+1,l+cnt+1,m-sum)-l-1;
return;
}
dfs2(x+1,sum);
dfs2(x+1,sum+a[x]);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> a[i];
}
dfs1(1,0);
// cout << cnt << " " << mnk << endl;
sort(l+1,l+cnt+1);
dfs2(n/2+1,0);
cout << num;
return 0;
}下午
1.树上差分(边差分+点差分)
LCA（最近公共祖先）:分两部分计算
1：到达同一水平位置
2：到达最近公共祖先的儿子
倍增
预处理 f[i][j]往根方向走2^j 到达的点
f[i][j]=f[f[i][j-1]][j-1];
点的距离：（lca）模板
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
const int maxn=100100;
struct node{
int next,to;
}edge[maxn*2];
int f[maxn][22];// 2^20>100000
int h[maxn],tot,dep[maxn];
int n;
void add(int x,int y){
tot++;
edge[tot].to=y;
edge[tot].next=h[x];
h[x]=tot;
}
void dfs(int x,int fa){
for (int i=h[x];i;i=edge[i].next){
int to=edge[i].to;
if (to==fa){
continue;
}
dep[to]=dep[x]+1;
f[to][0]=x;
dfs(to,x);
}
}
int q;
int lca(int x,int y){
if (dep[y]>dep[x]){
swap(x,y);
}
int tmp=dep[x]-dep[y];
int tim=0;
while (tmp){
if (tmp&1){
x=f[x][tim];
}
tim++;
tmp>>=1;
}
// for (int i=20;i>=0;i--){
// if (dep[x]-(1<<i)>=dep[y]){
// x=f[x][i];
// }
// }
if (x==y){
return x;
}
for (int i=20;i>=0;i--){
if (f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=1;i<=n-1;i++){
int x,y;
cin >> x >> y;
add(x,y);
add(y,x);
}
dfs(1,0);
for (int j=1;(1<<j)<=n;j++){
for (int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
// cout << f[i][j] << " ";
}
}
cin >> q;
for (int i=1;i<=q;i++){
int x,y;
cin >> x >> y;
int lc=lca(x,y);
cout << dep[x]-dep[lc]+dep[y]-dep[lc] << endl;
}
return 0;
}Fools and Roads lca+边差分模板
边差分模板：
int sum[100100],ans;
void fs(int x,int fa){
for (int i=h[x];i;i=edge[i].next){
int to=edge[i].to;
if (to==fa){
continue;
}
fs(to,x);
sum[x]+=sum[to];
}
}
sum[x]++;
sum[y]++;
sum[lc]-=2;
fs(1,0);
for (int i=2;i<=n;i++){
cout << sum[i] << " ";
}
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
const int maxn=100100;
struct node{
int next,to;
}edge[maxn*2];
int f[maxn][22];// 2^20>100000
int h[maxn],tot,dep[maxn];
int n;
void add(int x,int y){
tot++;
edge[tot].to=y;
edge[tot].next=h[x];
h[x]=tot;
}
void dfs(int x,int fa){
for (int i=h[x];i;i=edge[i].next){
int to=edge[i].to;
if (to==fa){
continue;
}
dep[to]=dep[x]+1;
f[to][0]=x;
dfs(to,x);
}
}
int q;
int lca(int x,int y){
if (dep[y]>dep[x]){
swap(x,y);
}
int tmp=dep[x]-dep[y];
int tim=0;
while (tmp){
if (tmp&1){
x=f[x][tim];
}
tim++;
tmp>>=1;
}
// for (int i=20;i>=0;i--){
// if (dep[x]-(1<<i)>=dep[y]){
// x=f[x][i];
// }
// }
if (x==y){
return x;
}
for (int i=20;i>=0;i--){
if (f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int sum[100100],ans;
void fs(int x,int fa){
for (int i=h[x];i;i=edge[i].next){
int to=edge[i].to;
if (to==fa){
continue;
}
fs(to,x);
sum[x]+=sum[to];
}
}
int main(){
//边差分
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=1;i<=n-1;i++){
int x,y;
cin >> x >> y;
add(x,y);
add(y,x);
}
dfs(1,0);
for (int j=1;(1<<j)<=n;j++){
for (int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
// cout << f[i][j] << " ";
}
}
cin >> q;
for (int i=1;i<=q;i++){
ans=0;
int x,y;
cin >> x >> y;
int lc=lca(x,y);
sum[x]++;
sum[y]++;
sum[lc]-=2;
//cout << dep[x]-dep[lc]+dep[y]-dep[lc] << endl;
}
fs(1,0);
for (int i=2;i<=n;i++){
cout << sum[i] << " ";
}
return 0;
}点差分模板:
int sum[300100];
void fs(int x,int fa){
for (int i=h[x];i;i=edge[i].next){
int to=edge[i].to;
if (to==fa){
continue;
}
fs(to,x);
sum[x]+=sum[to];
}
}
sum[x]++;
sum[y]++;
sum[lc]--;
if (lc!=1){
sum[f[lc][0]]--;
}
fs(1,0);
for (int i=2;i<=n;i++){
sum[a[i]]--;
}
for (int i=1;i<=n;i++){
cout << sum[i] << endl;
}松鼠的新家 lca+点差分模板
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
const int maxn=300100;
struct node{
int next,to;
}edge[maxn*2];
int f[maxn][22];// 2^20>100000
int h[maxn],tot,dep[maxn];
int n;
int a[300100];
void add(int x,int y){
tot++;
edge[tot].to=y;
edge[tot].next=h[x];
h[x]=tot;
}
void dfs(int x,int fa){
for (int i=h[x];i;i=edge[i].next){
int to=edge[i].to;
if (to==fa){
continue;
}
dep[to]=dep[x]+1;
f[to][0]=x;
dfs(to,x);
}
}
int q;
int lca(int x,int y){
if (dep[y]>dep[x]){
swap(x,y);
}
int tmp=dep[x]-dep[y];
int tim=0;
while (tmp){
if (tmp&1){
x=f[x][tim];
}
tim++;
tmp>>=1;
}
// for (int i=20;i>=0;i--){
// if (dep[x]-(1<<i)>=dep[y]){
// x=f[x][i];
// }
// }
if (x==y){
return x;
}
for (int i=20;i>=0;i--){
if (f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int sum[300100];
void fs(int x,int fa){
for (int i=h[x];i;i=edge[i].next){
int to=edge[i].to;
if (to==fa){
continue;
}
fs(to,x);
sum[x]+=sum[to];
}
}
int main(){
//点差分
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i];
}
for (int i=1;i<=n-1;i++){
int x,y;
cin >> x >> y;
add(x,y);
add(y,x);
}
dfs(1,0);
for (int j=1;(1<<j)<=n;j++){
for (int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
// cout << f[i][j] << " ";
}
}
for (int i=1;i<n;i++){
int x=a[i],y=a[i+1];
int lc=lca(x,y);
sum[x]++;
sum[y]++;
sum[lc]--;
// sum[f[lc][0]]--;
if (lc!=1){
sum[f[lc][0]]--;
}
//cout << dep[x]-dep[lc]+dep[y]-dep[lc] << endl;
}
fs(1,0);
for (int i=2;i<=n;i++){
sum[a[i]]--;
}
for (int i=1;i<=n;i++){
cout << sum[i] << endl;
}
return 0;
}晚上
A 小杨的养??(熊)计划
B 强哥的传送带
DAY 2
上午
讲解昨晚比赛题目
小杨的养??(熊)计划 //前缀和+分别统计
#include<bits/stdc++.h>
using namespace std;
const double PI=acos(-1.0);
long long a[20010],b[20010];
map<long long,long long> mp;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n,x,y,z;
cin >> n >> x >> y >> z;
for (long long i=1;i<=n;i++){
cin >> a[i] >> b[i];
mp[a[i]]+=y-x;
mp[b[i]+1]+=z-y;
}
long long maxx=x*n,sum=x*n;
for (auto it:mp){
sum+=it.second;
maxx=max(maxx,sum);
}
cout << maxx;
//前缀和+分别统计
return 0;
}强哥的传送带 （尚未AC）
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
const int maxn=100100;
const int maxm=170;
int n,m;
// f[x][p] 在x号站点出发，第一个能访问到的包含p这个质因子的编号
// list[p] :拥有p这个质因子的元素的线性表
int prime[100100];
int cnt;
int a[100100];
int l[1010][1010];
int f[10010][1010];
int main(){
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> a[i];
int x=a[i];
//特殊的，如果a[i]等于0，默认他拥有所有的质数做质因子
for (int j=2;j*j<=x;j++){
if (x%j==0){
l[j][++l[j][0]]=i;
while (x%j==0){
x/=j;
}
}
}
if (x>1){
l[x][++l[x][0]]=i;
}
}
bool fg=0;
for (int i=2;i<=1000;i++){
for (int j=2;j<i;j++){
if (i%j==0){
fg=1;
break;
}
}
if (fg==1){
cnt++;
prime[cnt]=i;
}
}
memset(f,0x3f,sizeof(f));
for (int i=n-1;i>=1;i--){
int x=a[i];
//特殊的，如果a[i]等于0，默认他拥有所有的质数做质因子
for (int j=2;j*j<=x;j++){
if (x%j==0){
while (x%j==0){
x/=j;
}
//找到下一个拥有质因子j的数,并且进行转移
int nxt=upper_bound(l[j]+1,l[j]+l[j][0]+1,i)-l[j];
if (nxt<=l[j][0]){
f[i][j]=nxt; //连边p:枚举2~1000质数
for (int p=1;p<=cnt;p++){//找路径
if (j!=prime[p]){
f[i][prime[p]]=min(f[i][prime[p]],f[nxt][prime[p]]);
}
}
}
}
}
if (x>1){
l[x][++l[x][0]]=i;
}
}
for (int i=1;i<=m;i++){
int x,y;
cin >> x >> y;
//对a[y]分解质因数
int tmp=a[y];
bool flag=0;
for (int j=2;j*j<=tmp;j++){
if (tmp%j==0){
while (tmp%j==0){
tmp/=j;
}//发现a[y]
if (f[x][j]<=y){
flag=1;
}
}
if (tmp>1){
if (f[x][j]<=y){
flag=1;
}
}
}
if (flag==1){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}
return 0;
}
/*
1-5
1-3
2-3
3-4
3-5
2-4
4-5下午
动态规划：
1.背包 资源分配->获取价值 模板见洛谷个人笔记（记得复习）
2.状压DP
背包：
武器购买
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int p[110],c[110];
int dp[110][500010];
int main(){
int t;
cin >> t;
while (t--){
int n,P,Q;
cin >> n >> P >> Q;
int sum=0;
for (int i=1;i<=n;i++){
cin >> p[i] >> c[i];
sum+=p[i];
}
memset(dp,0,sizeof(dp));
for (int i=1;i<=n;i++){
for (int j=1;j<=Q;j++){
dp[i][j]=dp[i-1][j];
if (c[i]<=j){
dp[i][j]=max(dp[i][j],dp[i-1][j-c[i]]+p[i]);
}
}
}
bool fg=0;
for (int i=1;i<=Q;i++){
if (dp[n][i]>=P){
cout << i << endl;
fg=1;
break;
}
}
if (fg==0){
cout << -1 << endl;
}
// for (int i=1;i<=sum;i++){
// cout << dp[i] << " ";
// }
// cout << endl;
}
return 0;
}道路优化
#include<bits/stdc++.h>
using namespace std;
long long n,l,k;
struct node{
long long wz,xs;
}a[600];
long long dp[510][510];//表示到达第i个限速点时，已经删除了j个限速点时的最短时间
long long pl;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> l >> k;
for (int i=1;i<=n;i++){
cin >> a[i].wz;
}
for (int i=1;i<=n;i++){
cin >> a[i].xs;
}
a[n+1].wz=l;
a[n+1].xs=0;
memset(dp,0x3f,sizeof(dp));
dp[1][0]=0;
n++;
for (int i=1;i<=n;i++){
for (int j=0;j<=k;j++){
for (int m=1;m<i;m++){
pl=j-(i-m-1);
if (pl>=0 && pl<=k && dp[m][pl]!=0x3f){
dp[i][j]=min(dp[i][j],dp[m][pl]+a[m].xs*(a[i].wz-a[m].wz));
}
}
}
}
long long minn=INT_MAX;
for (int i=0;i<=k;i++){
// cout << dp[n][i] << " ";
minn=min(minn,dp[n][i]);
}
cout << minn;
return 0;
}状压dp
GEPPETTO
1.暴搜
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int a[50],b[50];
int s[50][50];
int f[50];
int sum;
int n,m;
void dfs(int x,int cnt){
if (x==n+1){
sum++;
return;
}
bool fg=0;
for (int i=1;i<=cnt;i++){
if (s[f[i]][x]==1 || s[x][f[i]]==1){
fg=1;
break;
}
}
if (fg==0){
cnt++;
f[cnt]=x;
dfs(x+1,cnt);
cnt--;
}
dfs(x+1,cnt);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i=1;i<=m;i++){
cin >> a[i] >> b[i];
s[a[i]][b[i]]=1;
s[b[i]][a[i]]=1;
}
dfs(1,0);
cout << sum;
return 0;
}2.二进制压缩（状压dp）
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int x[55],y[55];
int n,m;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i=1;i<=m;i++){
cin >> x[i] >> y[i];
}
int ans=(1<<n);
for (int i=0;i<(1<<n);i++){
for (int j=1;j<=m;j++){
//检查方案i里面是否包含x[j]和y[j]两种原材料
//检查的是 i在2^(x[j]-1)和2^(y[j]-1)这两位的取值
if ((i&(1<<(x[j]-1))) && (i&(1<<(y[j]-1)))){
ans--;
break;
}
}
}
cout << ans;
return 0;
}互不侵犯
#include<bits/stdc++.h>
using namespace std;
long long dp[11][110][110],ans;
long long num[110],s[110],n,l,ol;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// f[i][j][p]第i行国王放置方案为j且总国王个数为p时的时候合法方案个数
cin >> n >> l;
ol=0;
ans=0;
memset(dp,0,sizeof(dp));
for (int i=0;i<(1<<n);i++){
if (i&(i<<1)){//相邻
continue;
}
long long op=0;
for (int j=0;j<n;j++){
if (i&(1<<j)){
op++;
}
}
s[++ol]=i;
num[ol]=op;
//记录合法状态
}//预处理合法状态
dp[0][1][0]=1;//初始化
for (int i=1;i<=n;i++){//遍历
for (int j=1;j<=ol;j++){//当前合法状态
for (int k=0;k<=l;k++){//棋子数量
if (k>=num[j]){
for (int t=1;t<=ol;t++){//上一行合法状态
if (!(s[t]&s[j]) && !(s[t]&(s[j]<<1)) && !(s[t]&(s[j]>>1))){
dp[i][j][k]+=dp[i-1][t][k-num[j]];//状态转移
}
}
}
}
}
}
for (int i=1;i<=ol;i++){
ans+=dp[n][i][l];//方案统计
}
cout << ans;
return 0;
} 金明的预算方案
#include<bits/stdc++.h>
using namespace std;
long long v[100],w[100],q[100];
struct node{
long long vv,ww;
}fa[100][3];
long long zv[100],zw[100];
long long cnt=0;
long long dp[33010];
long long pj[110];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long m,n;
cin >> m >> n;
for (int i=1;i<=n;i++){
cin >> v[i] >> w[i] >> q[i];
if (q[i]==0){
cnt++;
pj[i]=cnt;
zv[cnt]=v[i];
zw[cnt]=w[i];
}
}
for (int i=1;i<=n;i++){
if (fa[pj[q[i]]][1].vv!=0 || fa[pj[q[i]]][1].ww!=0){
fa[pj[q[i]]][2].vv=v[i];
fa[pj[q[i]]][2].ww=w[i];
}
else{
fa[pj[q[i]]][1].vv=v[i];
fa[pj[q[i]]][1].ww=w[i];
}
}
memset(dp,0,sizeof(dp));
for (int i=1;i<=cnt;i++){
for (int j=m;j>=zv[i];j--){
dp[j]=max(dp[j],dp[j-zv[i]]+zw[i]*zv[i]);//不选附件，只决定选不选附件
if (j-zv[i]-fa[i][1].vv>=0){
dp[j]=max(dp[j],dp[j-zv[i]-fa[i][1].vv]+zw[i]*zv[i]+fa[i][1].vv*fa[i][1].ww);//附1
}
if (j-zv[i]-fa[i][2].vv>=0){
dp[j]=max(dp[j],dp[j-zv[i]-fa[i][2].vv]+zw[i]*zv[i]+fa[i][2].vv*fa[i][2].ww);//附2
}
if (j-zv[i]-fa[i][1].vv-fa[i][2].vv>=0){
dp[j]=max(dp[j],dp[j-zv[i]-fa[i][1].vv-fa[i][2].vv]+zw[i]*zv[i]+fa[i][1].vv*fa[i][1].ww+fa[i][2].vv*fa[i][2].ww);//附1附2
}
}
}
cout << dp[m];
return 0;
}晚上
模拟赛2
1.小杨的字符串难题
2.拆墙大作战
3.强哥的积木
DAY 3
上午
讲解模拟赛题目
小杨的字符串难题
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long a[20];
long long b[5000010];
long long cnt;
long long c[1250];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
//二进制表示
//前缀数字
long long sum=0;
cnt++;
b[cnt]=sum;
for (int i=0;i<s.size();i++){
a[s[i]-'0']++;
if (a[s[i]-'0']%2==1){
sum+=pow(2,s[i]-'0');
}
else{
sum-=pow(2,s[i]-'0');
}
cnt++;
b[cnt]=sum;
}
for (int i=1;i<=cnt;i++){
// cout << b[i] << " ";
c[b[i]]++;
}
// cout << endl;
long long ans=0;
for (int i=0;i<=1200;i++){
//cout << c[i] << " ";
if (c[i]>1){
ans=ans+(c[i]-1)*c[i]/2;
}
}
cout << ans;
return 0;
}
/*
1 2 3 4
1234
20230322
0:0
1:4
2:5
3:1
4:9
5:8
6:0
7:4
8:0拆墙大作战
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
struct node{
long long l,r;
}a[200010];
bool cmp(node s1,node s2){
return s1.r<s2.r;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n,d;
cin >> n >> d;//贪心
for (int i=1;i<=n;i++){
cin >> a[i].l >> a[i].r;
}
sort(a+1,a+n+1,cmp);
long long ol=0;
long long i=1;
while (i<=n){
long long gj=a[i].r;
// long long x=max(a[i].l,gj-d+1); //起点
ol++;
while (i<=n && a[i].l<=gj+d-1){//同时攻击到的
i++;
}
}
cout << ol;
return 0;
}
/*a:10
123456789a
**
****
*****
**
***
***
**
**
**
强哥的积木 80分 (尚未AC)
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long a[40];
string s;
string y,t;
long long n,m;
void dfs(int k,string g){
if (g<y){
y=g;
}
if (k==0){
return;
}
t=g;
for (int i=1;i<s.size();i++){
t=g;
swap(t[i],t[i-1]);
dfs(k-1,t);
}
}
vector<long long> b[30];
long long fg[500010];
deque<char> q;
deque<char> p;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> s; //暴搜
y=s;
if (m==0){
cout << s;
return 0;
}
else if (m==1000000000000000000){
for (int i=0;i<s.size();i++){
a[s[i]-'a']++;
}
for (int i=0;i<=26;i++){
if (a[i]!=0){
for (int j=1;j<=a[i];j++){
cout << char(i+'a');
}
}
}
return 0;
}
else if (n<=5 && m<=10){
dfs(m,s);
cout << y;
return 0;
}
// for (int i=0;i<s.size();i++){
// a[s[i]-'a']++;
// b[s[i]-'a'].push_back(i);
// }
// int kt=0;
// for (int i=0;i<=25;i++){
// if (char('a'+i)>s[kt]){
// kt++;
// continue;
// }
// if (char('a'+i)==s[kt]){
// kt++;
// }
// for (auto it:b[i]){
// if (it-kt>m){
// for (int j=it;j>=it-m+1;j--){
// swap(s[j],s[j-1]);
// }
// break;
// }
// for (int j=it;j>=kt+1;j--){
// swap(s[j],s[j-1]);
// }
// m-=(it-kt);
// kt++;
// }
// if (m==0){
// break;
// }
// }
// cout << s;
for (int i=0;i<s.size();i++){
q.push_back(s[i]);
}
while (m>0 && !q.empty()){
// int o=0;
// int minn=INT_MAX;
// char yh='z';
// while (!q.empty()){
// o++;
// if (q.front()<yh){
// yh=q.front();
// minn=o;
// }
// p.push_back(q.front());
// q.pop_front();
// }
// while (!p.empty()){
// q.push_back(p.front());
// p.pop_front();
// }
// m-=o;
// cout << yh;
// q.erase(q.begin()+o);
// p.clear();
auto it=min_element(q.begin(),q.begin()+min(m+1,(long long)(q.size())));
int jl=it-q.begin();
cout << *it;
m-=jl;
q.erase(it);
}
while (!q.empty()){
cout << q.front();
q.pop_front();
}
return 0;
}
/*
dcba
adcba
adcab
adacb
aadcb
下午
依赖背包
Great Cow Gathering
树形dp 树的重心+最短路
错误原因：2个dfs递归时名字写错
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
struct node{
long long next,to,len;
}edge[200010];
long long h[200010];
long long tot;
void add(long long x,long long y,long long z){
tot++;
edge[tot].to=y;
edge[tot].len=z;
edge[tot].next=h[x];
h[x]=tot;
}
long long sz[200010];
long long mx[200010];
long long c[200010];
long long sum;
void dfs(long long u,long long fa){
sz[u]=c[u];
for (int i=h[u];i;i=edge[i].next){
long long to=edge[i].to;
if (to==fa){
continue;
}
dfs(to,u);
sz[u]+=sz[to];
mx[u]=max(mx[u],sz[to]);
}
mx[u]=max(mx[u],sum-sz[u]);
}
void df(long long u,long long fa){
for (int i=h[u];i;i=edge[i].next){
long long to=edge[i].to;
if (to==fa){
continue;
}
sz[to]=sz[u]+edge[i].len;
df(to,u);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
for (int i=1;i<=n;i++){
cin >> c[i];
sum+=c[i];
}
for (int i=1;i<=n-1;i++){
long long u,v,l;
cin >> u >> v >> l;
add(u,v,l);
add(v,u,l);
}
long long cl=1;
dfs(1,1);
for (int i=1;i<=n;i++){
if (mx[i]<mx[cl]){
cl=i;
}
}
sz[cl]=0;
df(cl,cl);
long long ans=0;
for (int i=1;i<=n;i++){
ans+=sz[i]*c[i];
}
cout << ans;
return 0;
}选课
第一种
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int n,m;
int s[310];
int f[310][310];//第二维：刚好m节课（注意边界：能选m节课>=m 否则不合法赋极小值见46行）
struct node{
int next,to;
}edge[310];
int h[310],tot;
void add(int x,int y){
tot++;
edge[tot].to=y;
edge[tot].next=h[x];
h[x]=tot;
}
void dfs(int u){
f[u][1]=s[u];
for (int i=2;i<=m;i++){
f[u][i]=-(1<<30);//赋初值
}
for (int i=h[u];i;i=edge[i].next){
int to=edge[i].to;
dfs(to);//先算清楚再转移
for (int j=m;j>=2;j--){
for (int k=1;k<j;k++){//留一门课给根
f[u][j]=max(f[u][j],f[u][j-k]+f[to][k]);
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
/*森林/树
f[i][j]以i为根的子树内分配k门课，问最大学分
枚举1个儿子，将j-1门课其中k门给这棵子树
f[i][j]=max(f[i][j-k],f[v][k]);(j-k>=1)(枚举儿子v) 留一节课给父节点（根）
f[i][1]=s[i]
f[i][0]=0
状态个数O(nm*m)
森林->树（超级根，以原来树根为儿子）
超级先修课->超级根，0分，m+1门课
cin >> n >> m;
m++;
for (int i=1;i<=n;i++){
int k;
cin >> k >> s[i];
add(k,i);
}
dfs(0);
cout << f[0][m];
return 0;
}第二种
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int n,m;
int s[310];
int f[310][310];//第二维：刚好m节课（注意边界：能选m节课>=m 否则不合法赋极小值见46行）
struct node{
int next,to;
}edge[310];
int h[310],tot;
int siz[310],lis[310],cnt;
void add(int x,int y){
tot++;
edge[tot].to=y;
edge[tot].next=h[x];
h[x]=tot;
}
void dfs(int u){
siz[u]=1;
lis[++cnt]=u;
for (int i=h[u];i;i=edge[i].next){
int to=edge[i].to;
dfs(to);
siz[u]+=siz[to];
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
/*
1.
森林/树
f[i][j]以i为根的子树内分配k门课，问最大学分
枚举1个儿子，将j-1门课其中k门给这棵子树
f[i][j]=max(f[i][j-k],f[v][k]);(j-k>=1)(枚举儿子v) 留一节课给父节点（根）
f[i][1]=s[i]
f[i][0]=0
状态个数O(nm*m)
森林->树（超级根，以原来树根为儿子）
超级先修课->超级根，0分，m+1门课
2.
f[i][j]：考虑将最多j门课分配给DFS序在第i~n之间的课程中，获取的最大学分
f[i][j]=max(s[list[i]]+f[i+1][j-1],f[i+s[list[i]]][j]);
(i:n~1);
ans=f[1][m]
cin >> n >> m;
m++;
for (int i=1;i<=n;i++){
int k;
cin >> k >> s[i];
add(k,i);
}
dfs(0);
n++;
for (int i=n;i>=1;i--){
for (int j=1;j<=m;j++){
f[i][j]=max(s[lis[i]]+f[i+1][j-1],f[i+siz[lis[i]]][j]);
}
}
cout << f[1][m];
return 0;
}01广搜
Wizard in Maze
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
char a[1010][1010];
int js[1010][1010];
int h,w;
int sc,sr;
int ec,er;
deque<pair<int,int>> q;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ax[]={0,0,0,0,1,1,1,1,1,2,2,2,2,2,-1,-1,-1,-1,-1,-2,-2,-2,-2,-2};
int ay[]={-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> h >> w;
cin >> sc >> sr;
cin >> ec >> er;
for (int i=1;i<=h;i++){
for (int j=1;j<=w;j++){
cin >> a[i][j];
}
}
memset(js,0x3f,sizeof(js));
js[sc][sr]=0;
q.push_back({sc,sr});
while (!q.empty()){
pair<int,int> p=q.front();
q.pop_front();
if (p.first==ec && p.second==er){
cout << js[ec][er];
return 0;
}
for (int i=0;i<4;i++){
int xx=dx[i]+p.first,yy=dy[i]+p.second;
if (xx<1 || xx>h || yy<1 || yy>w || a[xx][yy]=='#'){
continue;
}
if (js[xx][yy]>js[p.first][p.second]){
js[xx][yy]=js[p.first][p.second];
q.push_front({xx,yy});
}
}
for (int i=0;i<24;i++){
int xx=p.first+ax[i],yy=p.second+ay[i];
if (xx<1 || xx>h || yy<1 || yy>w || a[xx][yy]=='#'){
continue;
}
if (js[xx][yy]>js[p.first][p.second]+1){
js[xx][yy]=js[p.first][p.second]+1;
q.push_back({xx,yy});
}
}
}
cout << -1;
return 0;
}石子合并 线性
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int a[310];
long long s[310];
long long dp[310][310];
long long ddp[310][310];
int main(){
int n;
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i];
}
for (int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
memset(dp,0x3f,sizeof(dp));
memset(ddp,-0x3f,sizeof(ddp));
for (int len=1;len<=n;len++){
for (int l=1;l+len-1<=n;l++){
int r=l+len-1;
if (len==1){
dp[l][r]=0;
ddp[l][r]=0;
}
else{
for (int k=l;k<r;k++){
dp[l][r]=min(dp[l][k]+dp[k+1][r]+s[r]-s[l-1],dp[l][r]);
ddp[l][r]=max(ddp[l][k]+ddp[k+1][r]+s[r]-s[l-1],ddp[l][r]);
}
}
}
}
cout << dp[1][n] << endl;
cout << ddp[1][n];
return 0;
}248
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long a[300];
long long dp[300][300];
int main(){
int n;
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i];
}
memset(dp,-0x3f,sizeof(dp));
for (int len=1;len<=n;len++){
for (int l=1;l+len-1<=n;l++){
int r=l+len-1;
if (len==1){
dp[l][r]=a[l];
}
else{
for (int k=l;k<r;k++){
if (dp[l][k]==dp[k+1][r]){
dp[l][r]=max(dp[l][r],dp[l][k]+1);
}
}
}
}
}
long long maxx=INT_MIN;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
maxx=max(maxx,dp[i][j]);
}
}
cout << maxx;
return 0;
}晚上
模拟赛3
小杨的空调温度调整
小杨爱整数
冰冻阵法
DAY 4
上午
讲解比赛题目
小杨的空调温度调整
差分
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long p[100010];
long long t[100010];
long long c[100010];
long long b[100010];
long long v[100010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
for (int i=1;i<=n;i++){
cin >> p[i];
}
for (int i=1;i<=n;i++){
cin >> t[i];
}
long long sum=0;
for (int i=1;i<=n+1;i++){
b[i]=p[i]-p[i-1];
c[i]=t[i]-t[i-1];
v[i]=b[i]-c[i];
if (v[i]>0){
sum+=v[i];
}
}
cout << sum;
return 0;
} 小杨爱整数
dp
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long a[110];
long long n;
long long f[110][110];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i];
}
//f[p][g]选择p个数时和对i取模=g的方案
//a[j]%i-> f[p][g]+=f[p-1][(g-a[j])%i];
//ans=f[i][0];
long long ans=0;
for (int i=1;i<=n;i++){
memset(f,0,sizeof(f));
f[0][0]=1;
for (int j=1;j<=n;j++){
for (int p=i;p>=1;p--){
for (int g=0;g<i;g++){
int lo=(g+a[j])%i;
f[p][lo]+=f[p-1][g];
f[p][lo]%=998244353;
}
}
}
ans+=f[i][0];
ans%=998244353;
}
cout << ans;
return 0;
}冰冻阵法(尚未AC)
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long c[1010],dis[1010],u[1010],w[1010],v[1010];
vector<pair<int,int>> p[1010];
int kl[1010];
int n;
bool lk;
long long minn;
void dfs(int x,long long sum){
if (x==n+1){
for (int i=1;i<=n;i++){
lk=0;
if (kl[i]==0){
for (auto j:p[i]){
if (kl[j.first]==1 && j.second<=dis[j.first]){
lk=1;
break;
}
}
// if (lk==0){
// if (kl[3]==1 && kl[4]==0 && kl[1]==0 && kl[5]==0 && kl[2]==0){
// cout << i << "**";
// }
// return;
// }
}
}
// if (kl[3]==1 && kl[4]==0 && kl[1]==0 && kl[5]==0){
// cout << sum << "**";
// }
minn=min(minn,sum);
return;
}
kl[x]=1;
dfs(x+1,sum+c[x]);
kl[x]=0;
dfs(x+1,sum);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// f[u][j] :根为u的子树全满足，且使用子树外冰柜为j的情况
//j>0 真用 1.以v[i]为根的子树自我消化 2.以v[i]为根的子树也用了j
//j=0,不用 1.以v[i]为根的子树自我消化 2.以v[i]为根的子树用u
//ans=f[i][0];
int t;
cin >> t;
while (t--){
cin >> n;
memset(kl,0,sizeof(kl));
memset(p,0,sizeof(p));
for (int i=1;i<=n;i++){
cin >> c[i];
}
for (int i=1;i<=n;i++){
cin >> dis[i];
}
for (int i=1;i<=n-1;i++){
cin >> u[i] >> v[i] >> w[i];
p[u[i]].push_back({v[i],w[i]});
p[v[i]].push_back({u[i],w[i]});
}
minn=0x3f3f3f3f;
dfs(1,0);
cout << minn << endl;
}
return 0;
}DAY 5
上午
图论和树论
换根dp
n个点，选择x集合 求和dis(i,x)(1<=i<=n) min
换根 1.假设一个点为根（1） 算出x=1的情况
- 更换树根
树的重心
删除该点后形成的森林中树的最大大小的最小值
树的重心有1个或2个
2个：
2个重心相连 ，且将两个重心分开后树对称
树的重心如果不唯一，则至多有两个，且这两个重心相邻。
以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
树的重心
树的重心 模板题 （1~2个重心）
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int n;
vector<int> f[500010];
int maxx;
int sz[500010];
int ol[2];
void dfs(int u,int fa){
sz[u]=1;
int mx=0;
for (auto v:f[u]){
if (v==fa){
continue;
}
dfs(v,u);
sz[u]+=sz[v];
mx=max(mx,sz[v]);
}
mx=max(mx,n-sz[u]);
if (mx<maxx){
maxx=mx;
ol[0]=u;
ol[1]=-1;
}
else if (mx==maxx){
ol[1]=u;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=1;i<=n-1;i++){
int u,v;
cin >> u >> v;
f[u].push_back(v);
f[v].push_back(u);
}
maxx=n;
dfs(1,0);
if (ol[1]==-1){
cout << ol[0];
}
else{
cout << min(ol[0],ol[1]) << " " << max(ol[0],ol[1]);
}
return 0;
} 会议
树的重心模板+计算树上点到重心的最小距离（重心可能有1~2个）
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
long long n;
vector<long long> f[500010];
long long maxx;
long long sz[500010];
long long ol[2];
long long kl,u,v;
void dfs(long long u,long long fa){
sz[u]=1;
long long mx=0;
for (auto v:f[u]){
if (v==fa){
continue;
}
dfs(v,u);
sz[u]+=sz[v];
mx=max(mx,sz[v]);
}
mx=max(mx,n-sz[u]);
if (mx<maxx){
maxx=mx;
ol[0]=u;
ol[1]=-1;
}
else if (mx==maxx){
ol[1]=u;
}
}
queue<long long> q;
long long fg[50010];
long long ans;
void bfs(){
q.push(kl);
q.push(-1);
fg[kl]=1;
long long dep=0;
while (!q.empty()){
int p=q.front();
q.pop();
if (p==-1){
dep++;
if (q.empty()){
break;
}
q.push(-1);
}
else{
for (auto it:f[p]){
if (fg[it]==0){
fg[it]=1;
q.push(it);
}
}
ans+=dep;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=1;i<=n-1;i++){
cin >> u >> v;
f[u].push_back(v);
f[v].push_back(u);
}
maxx=n;
dfs(1,0);
if (ol[1]==-1){
kl=ol[0];
}
else{
kl=min(ol[0],ol[1]);
}
bfs();
cout << kl << " "<< ans;
return 0;
}
/*
2 -1
-1 1 3 dep=1;
1 3 -1 dep=1;
3 -1 dep=1 ans=1
-1 4 dep=1 ans=2;
4 -1 dep=2 ans=2;
-1 dep=2 ans=4
机房
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
const int maxn=100100;
struct node{
long long next,to;
}edge[maxn*2];
long long f[maxn][22];// 2^20>100000
long long h[maxn],tot,dep[maxn];
long long n;
long long d[100010];
long long yh[100010];
void add(long long x,long long y){
tot++;
edge[tot].to=y;
edge[tot].next=h[x];
h[x]=tot;
}
void dfs(long long x,long long fa){
for (int i=h[x];i;i=edge[i].next){
long long to=edge[i].to;
if (to==fa){
continue;
}
dep[to]=dep[x]+1;
yh[to]=d[to]+yh[x];
f[to][0]=x;
dfs(to,x);
}
}
long long lca(long long x,long long y){
if (dep[y]>dep[x]){
swap(x,y);
}
// long long tmp=dep[x]-dep[y];
// long long tim=0;
// while (tmp){
// if (tmp&1){
// x=f[x][tim];
// }
// tim++;
// tmp>>=1;
// }
// for (int i=20;i>=0;i--){
// if (dep[x]-(1<<i)>=dep[y]){
// x=f[x][i];
// }
// }
for(int i=18;i>=0;i--){
if(dep[y]<=dep[f[x][i]]){
x=f[x][i];
}
}
if (x==y){
return x;
}
for (int i=18;i>=0;i--){
if (f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
if (f[x][0]==0){
return 1;
}
return f[x][0];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n,m;
cin >> n >> m;
for (int i=1;i<=n-1;i++){
long long x,y;
cin >> x >> y;
add(x,y);
add(y,x);
d[x]++;
d[y]++;
}
yh[1]=d[1];
dfs(1,0);
for (int j=1;j<=18;j++){
for (int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
// cout << f[i][j] << " ";
}
}
for (int i=1;i<=m;i++){
long long u,v;
cin >> u >> v;
// if (u==v){
// cout << d[u] << endl;
// }
// else{
long long cl=lca(u,v);
cout << yh[u]+yh[v]-2*yh[cl]+d[cl] << endl;
// }
}
return 0;
}Anton and Tree
建原树
缩点建新树
求新树直径
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int c[200010];
struct node{
int next,to;
}edge1[400010],edge2[400010];
int h1[200010],tot1;
int h2[200010],tot2;
int n;
int num[200010];
int cnt;//块的个数
void add1(int x,int y){
tot1++;
edge1[tot1].to=y;
edge1[tot1].next=h1[x];
h1[x]=tot1;
}
void add2(int x,int y){
tot2++;
edge2[tot2].to=y;
edge2[tot2].next=h2[x];
h2[x]=tot2;
}
void dfs1(int x,int fa){
num[x]=cnt;
for (int i=h1[x];i;i=edge1[i].next){
int to=edge1[i].to;
if (to!=fa && c[x]==c[to]){
dfs1(to,x);
}
}
}
int d[200010];
int ol;
void dfs2(int u,int fa){
for (int i=h2[u];i;i=edge2[i].next){
int to=edge2[i].to;
if (to==fa){
continue;
}
d[to]=d[u]+1;
if (d[to]>d[ol]){
ol=to;
}
dfs2(to,u);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//建原树
//缩点建新树
//求新树直径
cin >> n;
// cout << "%%";
for (int i=1;i<=n;i++){
cin >> c[i];
}
// cout << "++";
for (int i=1;i<=n-1;i++){
int u,v;
cin >> u >> v;
add1(u,v);
add1(v,u);
}
// cout << "{{}}";
for (int i=1;i<=n;i++){
if (num[i]==0){
cnt++;
dfs1(i,0);
// cout << "||";
}
}
// cout << "^^";
//看边是否应该出现在新树中
for (int i=1;i<=n;i++){
for (int j=h1[i];j;j=edge1[j].next){
int to=edge1[j].to;
if (num[i]==num[to]){
continue;
}
//i->to
add2(num[i],num[to]);
// add2(num[to],num[i]);
}
}
// cout << "**";
dfs2(1,0);//第一次dfs在新的树上找直径
// cout << "&&";
d[ol]=0;
dfs2(ol,0);//第二次dfs在新的树上找直径
//把距离变成操作次数
cout << int(ceil(d[ol]*1.0/2));
return 0;
}Kay and Snowflake (尚未AC)
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//1.根本身为重心O(N) 去根后子树大小<=1/2(size)树的大小;
//2.根本身不为重心O(N) 暴力找重心（范围内）
return 0;
}晚上
模拟赛四 OI赛制
小杨的房屋分配
小杨的符文师职业之旅
波动序列
回文博弈
DAY 6
上午
讲解比赛题目
小杨的房屋分配
错误原因：for循环边界错误（逗号用法不明确导致边界错误，本来能对）
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long a[200010],b[200010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n,m,k;
cin >> n >> m >> k;
for (int i=1;i<=n;i++){
cin >> b[i];
}
for (int j=1;j<=m;j++){
cin >> a[j];
}
sort(b+1,b+n+1);
sort(a+1,a+m+1);
long long sum=0;
//for (int i=1,j=1;i<=n,j<=m;){ 逗号分隔两个语句在中间（判断边界）只有最后一个生效
//https://chat.deepseek.com/a/chat/s/92f32a73-c097-4bb0-8b9d-d998a2d7238a
//判断边界同时成立用&& 或者用while()
//逗号用于for循环1，3部分（定义赋值和自增自减）
for (int i=1,j=1;;){
if (i>n || j>m){
break;
}
if (b[i]>=a[j]-k && b[i]<=a[j]+k){
sum++;
i++;
j++;
}
else if (b[i]<a[j]-k){
i++;
}
else if (b[i]>a[j]+k){
j++;
}
}
cout << sum;
return 0;
}
/*小杨的符文师职业之旅
错误原因：数组开小了（2582行，2592行，2599（原来<=pl）pl>1010越界）应该不用pl数组开1010
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long l[2010],d[2010];
long long dp[2010][2010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
//long long pl=0;
for (int i=1;i<=n;i++){
cin >> l[i];
// pl+=l[i];
}
for (int i=1;i<=n;i++){
cin >> d[i];
}
dp[0][0]=0;
for (int i=1;i<=n;i++){
for (int j=0;j<=n;j++){
dp[i][j]=dp[i-1][j];
if (j>=l[i]){
dp[i][j]=max(dp[i][j],dp[i-1][j-l[i]]+d[i]);
}
}
}
long long maxx=0;
for (int i=0;i<=n;i++){
maxx=max(maxx,dp[n][i]);
}
cout << maxx;
return 0;
}
/*
2 2 1 1 1
7 8 3 3 3
1234512345
8+3+7
以大换小 （比较）
排序
凑和为n，的最大值
第i个和为j的最大伤害
波动序列 (尚未AC)
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long a[1000010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i];
}
// long long maxx=0;
long long hj=0;
for (int i=1;i<=n;i++){
// maxx=max(maxx,a[i]-a[i-1]);
hj=hj+a[i]-a[i-1];
}
//2^31(32正负) 4*10^9（正负） 32/33 21 4748 3647
//没有单调性 不能二分
// long long l=minn,r=maxx,mid=(l+r)/2;
// while (l<=r){
// mid=(l+r)/2;
//
// }
hj/=n;
long long sum=1,mxx=0,ls=0,ol=0;
if (hj<0){
hj=0;
}
for (int i=0;i<=hj;i++){
sum=1;
ls=a[1];
for (int j=2;j<=n;j++){
if (a[j]>a[j-1]){
if (ls+i==a[j]){
sum++;
}
ls+=i;
}
else if (a[j]==a[j-1]){
if (ls==a[j]){
while (a[j]==a[j-1]){
sum++;
j++;
}
j--;
}
}
else{
if (ls-i==a[j]){
sum++;
}
ls-=i;
}
}
// cout << sum << " " << i << endl;
if (sum>mxx){
mxx=sum;
ol=i;
}
}
cout << mxx << endl;
cout << ol;
return 0;
}
/*
1 2 2 2 2 2 4
1 2 2 2 2 2 回文博弈(尚未AC)
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
const int maxn=1000100;
int len[maxn];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
/*
直接是回文 徐输
串长奇数
1.1：串不存在长度>1的回文子串 徐赢
1.2：存在长度>1的回文子串 徐赢
串长偶数
1.1 石老师赢
字符串回文
int n;
cin >> n;
string s;
cin >> s;
int q;
cin >> q;
bool fg=0;
len[0]=1;
int pos=0;
//奇数
for (int i=1;i<s.size();i++){
//s[i]已经不在之前的基准串里
if (i>pos+len[pos]/2){
pos=i;
len[i]=1;
while (i>=len[i]/2+1 && s[i-len[i]/2-1]==s[i+len[i]/2+1]){
len[i]++;
}
continue;
}
//基准串的中心点是pos 现在要求得是以s[i]为中心的最长回文串
//求出第二个基准串的中心点
int j=pos*2-i;
if (pos-len[pos]/2<j-len[j]/2){//第二个基准串可以完整对称过来
len[i]=len[j];
}
else if (pos-len[pos]/2>j-len[j]/2){//只能将第二个基准串处于第一个基准串里面的，且回文的部分进行对称
len[i]=2*(j-(pos-len[pos]/2))+1;
}
else{
len[i]=len[j];
while (i>=len[i]/2+1 && s[i-len[i]/2-1]==s[i+len[i]/2+1]){
len[i]++;
}
}
//维护第一个基准串
if (i+len[i]/2>pos+len[pos]/2){
pos=i;
}
}
while (q--){
int l,r;
cin >> l >> r;
l--;
r--;
// fg=0;
// for (int i=0;i<=(l+r)/2-l;i++){
// if (s[i+l]!=s[r-i]){
// fg=1;
// break;
// }
// }
if (fg==0){
cout << "Mr.Shi" << endl;
}
else{
if ((r-l+1)%2==1){
cout << "Mr.Xu" << endl;
}
else{
cout << "Mr.Shi" << endl;
}
}
}
return 0;
}
/*
asdfdsa
对称截 徐输
一左一右不对称 ？
全在左/右 奇偶性（这里只半边没有回文）奇 徐输 偶 石输
1~3
暴搜
枚举截取
记录最大值（最佳情况）选定一个人记录
边界 回文 输赢
走最佳路线 选定的人走赢得，另一个走他赢得（选定的输的）
最后看输赢 下午
1.KMP
2.manacher
KMP模板
https://paste.ubuntu.com/p/94cw4g5fsS/
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
const int maxn=1000100;
string sh,ch;
int fail[maxn]; //fail[i]表示ch串中右端点下标为i的前缀的border的右端点下标
// 特殊的 如果border为空 那么-1
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> sh >> ch;
fail[0]=-1;
for (int i=1;i<ch.size();i++){
//现在在求解右端点下标为i的前缀的border
//从右端点下标为i-1的前缀的border开始枚举
//试图加入ch[i] 形成一个新的border
int j=fail[i-1];
while (j!=-1){
if (ch[j+1]==ch[i]){
break;
}
j=fail[j];
}
if (ch[j+1]==ch[i]){
fail[i]=j+1;
}
else{
fail[i]=-1;
}
}
int j=-1;
for (int i=0;i<sh.size();i++){
while (j!=-1){
if (ch[j+1]==sh[i]){
break;
}
j=fail[j];
}
if (ch[j+1]==sh[i]){
j++;
}
else{
j=-1;
}
}
if (j==ch.size()-1){
//找到了，可以说明ch是sh的子串
//可以说明ch的最后一个字符是和sh[i]匹配的
}
return 0;
}
模板KMP
【模板】KMP
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int t[1000010];
int main(){
string s,p;
cin >> s >> p;
int sl=s.size();
int pl=p.size();
for (int i=1,j=0;i<pl;i++){
while (j && p[i]!=p[j]){
j=t[j-1];
}
if (p[i]==p[j]){
j++;
}
t[i]=j;
}
for (int i=0,j=0;i<sl;i++){
while (j && s[i]!=p[j]){
j=t[j-1];
}
if (s[i]==p[j]){
j++;
}
if (j==pl){
cout << i-pl+1+1 << endl;
j=t[j-1];
}
}
for (int i=0;i<p.size();i++){
cout << t[i] << " ";
}
return 0;
}模板马拉车
【模板】manacher
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int l[23000010];
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
string s,t="*";
cin >> s;
for (int i=0;i<s.size();i++){
t+=s[i];
t+='*';
}
l[0]=0;
int tmp=0,mx=0,ans=0;
for (int i=1;i<t.size();i++){
if (i<=tmp+mx){
int j=tmp*2-i;
if (tmp-mx<j-l[j]){
l[i]=l[j];
}
else if (tmp-mx>j-l[j]){
l[i]=j-(tmp-mx);
}
else{
l[i]=l[j];
}
}
while (i>l[i] && t[i-(l[i]+1)]==t[i+(l[i]+1)]){
l[i]++;
}
ans=max(ans,l[i]);
if (tmp+mx<=i+l[i]){
tmp=i;
mx=l[i];
// cout << i << " " << l[i] << endl;
}
}
cout << ans;
return 0;
}
/*
*a*a*a*无线传输
Radio Transmission 无线传输
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull p[1000010];
ull b[1000010];
ull wd(int l,int r){
return b[r]-b[l-1]*p[r-l+1];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
string s;
cin >> s;
ull k=131;
p[0]=1;
for (int i=1;i<=n;i++){
p[i]=p[i-1]*k;
}
b[0]=0;
for (int i=1;i<=n;i++){
b[i]=b[i-1]*k+s[i-1];
}
bool fg=0;
// cout << wd(1,3) << endl;
for (int i=1;i<=n;i++){
ull t=b[i];
// cout << t << " ";
fg=0;
for (int j=i;j<s.size();j+=i){
if (j+i<=s.size()){
ull l=wd(j+1,j+i);
if (l!=t){
fg=1;
// cout << s.substr(j,i) << " ";
// cout << i << " " << j << " " << l << "* " << endl;
break;
}
}
else{
ull m=b[s.size()%i];
ull o=wd(j+1,s.size());
if (m!=o){
fg=1;
// cout << i << " " << m << " " << o << "/ " << endl;
break;
}
}
}
if (fg==0){
cout << i;
return 0;
}
}
return 0;
}Barn Echoes G
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s1,s2;
cin >> s1 >> s2;
string s="";
int o=0;
for (int i=0;i<s1.size();i++){
s+=s1[i];
if (s2.find(s)<s2.size()){
o=s.size();
}
}
string ss="";
int p=0;
for (int i=0;i<s2.size();i++){
ss+=s2[i];
if (s1.find(ss)<s1.size()){
p=ss.size();
}
}
cout << max(o,p);
return 0;
}晚上
模拟赛5
A 数位之和
B gogogo 出发喽
C 抓娃娃机
D 动态队列
DAY 7
上午
数位之和
错误原因：判断条件错误，3633行，原来40分的判断适用于n为负整数（题面不明确）
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
int x,y;
cin >> x >> y;
int ol=x-y;
if (x+1==y){
cout << "Yes" << endl;
}
else if (x-y<=0){
cout << "No" << endl;
}
else if ((ol+1)%9==0){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}
return 0;
}gogogo 出发喽
错误原因：状态转移方程错误（人数判断应取最小值3691行）
边界条件错误：总人数>车载最大人数 impossible未判断
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long t[110],z[110];
long long dp[110][110];// i c j r
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n,k,d,T,sum=0;
cin >> n >> k >> d >> T;
for (int i=1;i<=k;i++){
cin >> t[i] >> z[i];
sum+=z[i];
}
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[0][0]=0;
for (int i=1;i<=k;i++){
for (int j=0;j<=n;j++){
if (dp[i-1][j]!=0x3f3f3f3f){
dp[i][j]=min(dp[i][j],dp[i-1][j]);
long long yh=min(z[i],n-j);
for (int k=1;k<=yh;k++){
long long fg=j+k;
long long cv=dp[i-1][j]+d+k*t[i];
dp[i][fg]=min(dp[i][fg],cv);
}
}
}
}
// for (int i=1;i<=k;i++){
// for (int j=0;j<=n;j++){
// cout << dp[i][j] << " ";
// }
// cout << endl;
// }
if (dp[k][n]==0x3f3f3f3f || sum<n){
cout << "impossible";
}
else{
cout << dp[k][n];
}
return 0;
}下午
数论一
快速幂
欧拉函数
积性函数
Sigma Function
Sigma Function
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for (int i=1;i<=t;i++){
long long n;
cin >> n;
cout << "Case " << i << ": " << n-int(sqrt(n))-int(sqrt(n/2)) << endl;
}
return 0;
}
/*
4 9 16 25 36 49 64 81
Raising Modulo Numbers
快速幂
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long a[45010],b[45010];
long long ksm(long long n,long long m,long long mod){
long long ans=1,bs=n;
while (m!=0){
if (m&1){
ans=(bs*ans)%mod;
}
bs=bs*bs%mod;
m>>=1;
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long m,n;
cin >> m >> n;
long long sum=0;
for (int i=1;i<=n;i++){
cin >> a[i] >> b[i];
long long k=ksm(a[i],b[i],m);
sum=(sum%m+k)%m;
}
cout << sum;
return 0;
} The Euler function
欧拉筛筛欧拉函数
#include<bits/stdc++.h>
using namespace std;
const int maxn=30000010;
int isprime[maxn],eular[maxn];
vector<int> prime;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long a,b;
cin >> a >> b;
for (int y=2;y<=b;y++){//y
if (isprime[y]==0){
prime.push_back(y);
eular[y]=y-1;
}
for (auto x:prime){
if (x*y>b){
break;
}
isprime[x*y]=1;
if (y%x==0){
eular[x*y]=x*eular[y];
break;
}
eular[x*y]=eular[x]*eular[y];
}
}
long long sum=0;
for (int i=a;i<=b;i++){
sum+=eular[i];
}
cout << sum;
return 0;
}DAY 8
上午
数论二
1.费马小定理
若a,p互质，且p是质数，则a的p-1次方mod(%)p=1;
S={1,2,3,······p-1}；
T={a,2a,3a······(p-1)a}
将T内每个元素对p取模后构造集合次T 有次T=S
1.T集合内不存在p的倍数
2.T集合内不存在两个元素在模p意义下同余
将S.T集合元素分别相乘
可证费马小定理
2.欧拉定理 （费马小定理特殊形式）
若a,p为两个互质整数，则a的o（p）次方 mod p=1;
o(p)为p的欧拉函数值
令集合S，集合内的任意元素x满足：
-
1 ≤ x<p。
-
gcd(p,x)=1。
乘法逆元
求解 a/b mod p的值 当a,b,特别大时怎末办
考虑将除法运算消除掉。对于 a/b mod p，在取模之前若乘上b的一个倍数，就可以把除法消除。
而为保证取模结果不变，根据乘法的同余定理，乘上的这个数对p取模的结果必须为1。
令满足条件的数为b*k。此时可称k是b关于模p意义下的逆元，当然反过来b也是k关于模p意义下的逆元。
例如，3是2关于模5意义下的逆元。
在求解 a/b mod p 的场景下，我们需要求解b关于模p意义下的乘法 逆元。
其实就是在已知b,p的情况下求解下面这个同余方程： bk ≡ 1 mod p k 的一个正整数解。
这个方程当且仅当gcd(b,p)=1 有解。且有解的时候一定有无数个。 对于乘法逆元的场景，只需要随便得到一个正整数解就行
3 的幂的和（乘法逆元+快速幂）
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long gh(long long n,long long a){
long long ans=1,bs=a;
while (n!=0){
if (n&1){
ans=(bs*ans)%1000000007;
}
bs=bs*bs%1000000007;
n>>=1;
}
return ans%1000000007;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
n++;
long long pl=gh(n,3);
pl-=1;
pl%=1000000007;
//pl/=2;
long long ol=gh(1000000005,2);
ol%=1000000007;
cout << pl*ol%1000000007;
return 0;
}Sumdiv
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long mod=9901;
long long gh(long long a,long long n){
long long ans=1,bs=a;
while (n!=0){
if (n&1){
ans=(bs*ans)%mod;
}
bs=bs*bs%mod;
n>>=1;
}
return ans%mod;
}
long long tg(long long p,long long k){
if (k==0){
return 1;
}
else if (k%2==0){
return ((1+gh(p,k>>1))*tg(p,(k>>1)-1)+gh(p,k))%mod;
}
else{
return ((1+gh(p,(k+1)>>1))*tg(p,(k-1)>>1))%mod;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a,b;
cin >> a >> b;
long long ans=1;
for (int i=2;i<=a;i++){
long long sum=0;
while (a%i==0){
sum++;
a/=i;
}
if (sum!=0){
ans=ans*tg(i,sum*b)%mod;
}
}
cout << ans;
return 0;
}
/*下午
二项式定理
数学练习:费马小定理 乘法逆元 特殊处理
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long mod=998244353;
long long n;
long long f[100010];
long long x,y;
long long sd(long long a,long long s,long long p){
long long ans=1;
while(s!=0){
if (s&1){
ans=ans*a%p;
}
a=a*a%p;
s>>=1;
}
return ans%p;
}
long long C(long long m,long long n){
long long x=sd(f[m]*f[n-m]%mod,mod-2,mod)%mod;
return f[n]*x%mod;
}
int main(){
cin >> n;
long long ans=0;
f[0]=1;
for (int i=1;i<=n;i++){
f[i]=f[i-1]*i%mod;
}
long long mid=n/2;
bool fg=0;
if (n%2==0){
fg=1;
}
for (int i=1;i<=n-1;i++){
if (fg==1 && i==mid){
continue;
}
ans=ans+C(i-1,n-2);
ans%=mod;
}
cout << ans;
return 0;
}计算系数:二项式定理
ADCBA
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int a,b,k,n,m;
long long ans=1;
long long kuai(int x,int y){
if (y==0){
return 1;
}
long long k=kuai(x,y>>1);
k=k*k%mod;
if (y&1){
k=k*x%mod;
}
return k;
}
int main(){
cin >> a >> b >> k >> n >> m;
ans=kuai(a,n)*kuai(b,m)%mod;
for (int i=1;i<=n+m;i++){
ans=ans*i%mod;
}
for (int i=1;i<=n;i++){
ans=ans*kuai(i,mod-2)%mod;
}
for (int i=1;i<=m;i++) {
ans=ans*kuai(i,mod-2)%mod;
}
cout << ans;
return 0;
}排队（超级加强版）
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long pl[200010];
long long fg[200010];
long long mod=1e9+7;
long long gh(long long a,long long n){
long long ans=1,bs=a;
while (n!=0){
if (n&1){
ans=(bs*ans)%mod;
}
bs=bs*bs%mod;
n>>=1;
}
return ans%mod;
}
long long C(int n,int m){
return pl[m]*pl[n-m]%mod*fg[n]%mod;
}
int n,m;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
fg[0]=1;
for (int i=1;i<200010;i++){
fg[i]=fg[i-1]*i%mod;
}
pl[200009]=gh(fg[200009],mod-2);
for (int i=200009;i>=1;i--){
pl[i-1]=pl[i]*i%mod;
}
while(cin >> n >> m){
cout << fg[n]*fg[m]*2%mod*(C(n+3,m)*C(n+1,2)%mod+C(n+1,1)*C(n+2,m-1)%mod)%mod << '\n';
}
return 0;
}字符串
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long pl[2000010];
long long fg[2000010];
long long mod=20100403;
long long gh(long long a,long long n){
long long ans=1,bs=a;
while (n!=0){
if (n&1){
ans=(bs*ans)%mod;
}
bs=bs*bs%mod;
n>>=1;
}
return ans%mod;
}
long long C(int n,int m){
return pl[m]*pl[n-m]%mod*fg[n]%mod;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
fg[0]=1;
for (int i=1;i<2000010;i++){
fg[i]=fg[i-1]*i%mod;
}
pl[2000009]=gh(fg[2000009],mod-2);
for (int i=2000009;i>=1;i--){
pl[i-1]=pl[i]*i%mod;
}
cout<<((C(n+m,m)-C(n+m,m-1))%mod+mod)%mod;
return 0;
}非回文串
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long pl[6201000];
long long fg[6201000];
long long mod=1000000007;
long long gh(long long a,long long n){
long long ans=1,bs=a;
while (n!=0){
if (n&1){
ans=(bs*ans)%mod;
}
bs=bs*bs%mod;
n>>=1;
}
return ans%mod;
}
long long a[30];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
long long jm=n/2;
string s;
cin >> s;
for (int i=0;i<s.size();i++){
a[s[i]-'a']++;
}
fg[0]=1;
for (int i=1;i<=n+100;i++){
fg[i]=fg[i-1]*i%mod;
}
pl[n+100]=gh(fg[n+100],mod-2);
for (int i=n+99;i>=0;i--){
pl[i]=pl[i+1]*(i+1)%mod;
}
long long ans=1;
for (int i=0;i<26;i++){
ans=ans*(fg[jm]*pl[a[i]/2]%mod*pl[jm-a[i]/2]%mod)%mod*(fg[a[i]]*pl[a[i]/2]%mod*pl[a[i]/2]%mod)%mod*fg[a[i]/2]%mod*fg[a[i]/2]%mod;
jm-=a[i]/2;
}
cout << ((fg[n]-ans)%mod+mod)%mod;
return 0;
}晚上
ACM欢乐赛
一切实力都来源于我们的肚量
密码：youduliang
DAY 9
讲解ACM欢乐赛
ABCDEFGHI均已AC
A
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll ref = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
ref = (ref << 1) + (ref << 3) + (ch ^ 48), ch = getchar();
return ref * f;
}
int main()
{
cout << "He1lo,World";
return 0;
}B
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll ref = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
ref = (ref << 1) + (ref << 3) + (ch ^ 48), ch = getchar();
return ref * f;
}
int main()
{
int n;
cin >> n;
int maxx=0;
for (int i=1;i<=n;i++){
int x;
cin >> x;
maxx=max(maxx,x);
}
cout << maxx;
return 0;
}C
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll ref = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
ref = (ref << 1) + (ref << 3) + (ch ^ 48), ch = getchar();
return ref * f;
}
int main()
{
ll a=read(),b=read();
cout<<a+b;
return 0;
}D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll ref = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
ref = (ref << 1) + (ref << 3) + (ch ^ 48), ch = getchar();
return ref * f;
}
int main()
{
int t = read();
while (t--)
{
int k = read(), cnt = 0;
char ans[20] = {};
for (int i = 9; i; i--)
if (k >= i)
ans[cnt++] = i ^ 48, k -= i;
reverse(ans, ans + cnt);
puts(ans);
}
return 0;
}E
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll ref = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
ref = (ref << 1) + (ref << 3) + (ch ^ 48), ch = getchar();
return ref * f;
}
int a[200010];
int b[200010];
int fg[200010];
int main()
{
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = a[i];
}
int op = x;
int sum = 0;
while (b[op] != 0 && fg[op] == 0)
{
fg[op] = 1;
sum++;
op = b[op];
}
cout << sum;
return 0;
}F
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
inline ll read()
{
ll ref = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
ref = (ref << 1) + (ref << 3) + (ch ^ 48), ch = getchar();
return ref * f;
}
long long a[200010];
signed main()
{
long long n = read(), k = read();
for (int i = 1; i <= n; i++)
{
a[i] = read();
}
if (n == 1)
return printf("%lld", a[1] + k), 0;
sort(a + 1, a + n + 1);
long long dis = (n+1)/2, len = 1;
while (dis + len - 1 < n)
{
int tmp=k;
k -= max((ll)0,min(k, (a[dis + len] - a[dis]) * len));
a[dis] += min(max((ll)0,tmp / len), max((ll)0,a[dis + len] - a[dis]));
len++;
// cout << a[dis] << ' ' << k << ' ' << len << '\n';
if (!k)
return printf("%lld", a[dis]), 0;
}
cout << max((ll)0,a[dis] + k / len);
return 0;
}G
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e+5 + 5;
int prime[maxn], cnt;
bool is_prime[maxn];
int num, ans = INT_MAX, duliang;
int a[10], b[10];
inline ll read()
{
ll ref = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
ref = (ref << 1) + (ref << 3) + (ch ^ 48), ch = getchar();
return ref * f;
}
inline int len(int al, int bl)
{
return min(abs(al - bl), min(al, bl) + 10 - max(al, bl));
}
int length(int number) // 计算num和number之间的距离
{
int answer = 0;
int temp = num;
for (int i = 0; i < 5; i++)
{
answer += len(temp % 10, number % 10);
temp /= 10, number /= 10;
}
return answer;
}
int main()
{
num = read();
for (int i = 2; i < maxn; i++)
{
if (!is_prime[i])
{
if (length(i) <= ans)
ans = length(i), duliang = i;
prime[cnt++] = i;
}
for (int j = 0; i * prime[j] < maxn; j++)
{
is_prime[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
printf("%05d", duliang);
return 0;
}H
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll ref = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
ref = (ref << 1) + (ref << 3) + (ch ^ 48), ch = getchar();
return ref * f;
}
int dp[1010];
int a[10];
int main()
{
int n;
cin >> n;
a[1] = 10;
a[2] = 20;
a[3] = 50;
a[4] = 100;
dp[0] = 1;
for (int i = 1; i <= 4; i++)
{
for (int j = a[i]; j <= n; j++)
{
dp[j] += dp[j - a[i]];
}
}
cout << dp[n];
return 0;
}I
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e+5+5;
inline ll read(){
ll ref=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch == '-') f = -1;ch = getchar();}
while (isdigit(ch)) ref = (ref << 1) + (ref << 3) + (ch ^ 48), ch = getchar();
return ref*f;
}
ll a[maxn],sum[maxn],pre[maxn];
int main(){
ll n=read(),k=read(),temp=0;
for(int i=0;i<n;i++) sum[a[i]=read()]++;sort(a,a+n);
for(int i=0;i+1<n;i++) temp+=a[n-1]-a[i];
if(k>temp) return printf("%lld",a[n-1]+(k-temp)/n),0;
for(int i=1;i<maxn;i++) pre[i]=pre[i-1]+sum[i]*i,sum[i]+=sum[i-1];
// puts("----");
for(int i=maxn-1;i;i--){
int j=i;
for(temp=0;j<maxn;j+=i){
temp+=(sum[j]-sum[j-i])*j-(pre[j]-pre[j-i]);
}temp+=(sum[maxn-1]-sum[j-i])*j-(pre[maxn-1]-pre[j-i]);
if(temp<=k) return printf("%lld",i),0;
}
return 0;
} 下午
堆，线段树
堆：完全二叉树
父亲<=儿子 小根堆
儿子<=父亲 大根堆
增 删 查
查：堆顶(根) / 元素个数
线段树 n0=n2+1;
总结点数：2n-1
线段树模板
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
const int maxn=100100;
int sum[maxn*4];
int a[maxn];
int n,m;
void pushup(int v){
sum[v]=sum[v<<1]+sum[v<<1|1];
}
void build(int v,int l,int r){
if (l==r){
sum[v]=a[l];
return;
}
int mid=(l+r)>>1;
build(v<<1,l,mid);
build(v<<1|1,mid+1,r);
pushup(v);
}
void modify(int v,int l,int r,int x,int y){
if (l==r){
sum[v]=y;
return;
}
int mid=(l+r)>>1;
if (x<=mid){
modify(v<<1,l,mid,x,y);
}
else{
modify(v<<1|1,mid+1,r,x,y);
}
pushup(v);
}
int ask(int v,int l,int r,int L,int R){
if (r<L || R<l){//[l,r],[L,R]不相交
return 0;
}
if (L<=l && r<=R){
return sum[v];
}
int mid=(l+r)>>1;
return ask(v<<1,l,mid,L,R)+ask(v>>1|1,mid+1,r,L,R);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> a[i];
}
build(1,1,n);
for (int i=1;i<=m;i++){
int op;
cin >> op;
if (op==1){
int x,y;
cin >> x >> y;
a[x]=y;
modify(1,1,n,x,y);
}
else{
int l,r;
cin >> l >> r;
cout << ask(1,1,n,l,r) << endl;
}
}
return 0;
}合并果子
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i=1;i<=n;i++){
int x;
cin >> x;
q.push(x);
}
long long sum=0;
while (q.size()>1){
long long s=q.top();
q.pop();
s=s+q.top();
q.pop();
sum=sum+s;
q.push(s);
}
cout << sum;
return 0;
}My Cow Ate My Homework S
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int a[100010];
int minn[100010];
double pj[100010];
int h[100010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i];
}
minn[n+1]=INT_MAX;
h[n+1]=0;
for (int i=n;i>=1;i--){
h[i]=h[i+1]+a[i];
minn[i]=min(minn[i+1],a[i]);
if (n-i!=0){
pj[i]=(h[i]-minn[i])/(n-i);
}
}
// for (int i=1;i<=n;i++){
// cout << h[i] << " ";
// }
// cout << endl;
// for (int i=1;i<=n;i++){
// cout << minn[i] << " ";
// }
// cout << endl;
// for (int i=1;i<=n;i++){
// cout << pj[i] << " ";
// }
// cout << endl;
int maxx=0,ol=0;
for (int i=1;i<=n;i++){
if (pj[i]>maxx){
maxx=pj[i];
// ol=i;
}
}
for (int i=1;i<=n;i++){
if (maxx==pj[i]){
cout << i-1 << endl;
}
}
// cout << ol-1;
return 0;
}Counting Haybale P
#include<bits/stdc++.h>
using namespace std;
long long a[200010];
long long t[800010];
long long tag[800010];
long long mi[800010];
void build(long long l,long long r,long long cnt){
if (l==r){
t[cnt]=a[l];
mi[cnt]=a[l];
return;
}
long long mid=(l+r)/2;
build(l,mid,cnt*2);
build(mid+1,r,cnt*2+1);
t[cnt]=t[cnt*2]+t[cnt*2+1];
mi[cnt]=min(mi[cnt*2],mi[cnt*2+1]);
}
void lz(long long cnt,long long l,long long r){
if (tag[cnt]!=0){
long long mid=(l+r)/2;
tag[cnt*2]+=tag[cnt];
tag[cnt*2+1]+=tag[cnt];
t[cnt*2]+=tag[cnt]*(mid-l+1);
t[cnt*2+1]+=tag[cnt]*(r-mid);
mi[cnt*2]+=tag[cnt];
mi[cnt*2+1]+=tag[cnt];
tag[cnt]=0;
}
}
void up(long long l,long long r,long long L,long long R,long long cnt,long long k){
long long mid=(l+r)/2;
if (L<=l && r<=R){
tag[cnt]+=k;
t[cnt]+=(r-l+1)*k;
mi[cnt]+=k;
return;
}
lz(cnt,l,r);
if (mid>=L){
up(l,mid,L,R,cnt*2,k);
}
if (mid<R){
up(mid+1,r,L,R,cnt*2+1,k);
}
t[cnt]=t[cnt*2]+t[cnt*2+1];
mi[cnt]=min(mi[cnt*2],mi[cnt*2+1]);
}
long long q(long long l,long long r,long long L,long long R,long long cnt){
long long mid=(l+r)/2,sum=0;
if (L<=l && r<=R){
return t[cnt];
}
lz(cnt,l,r);
if (mid>=L){
sum+=q(l,mid,L,R,cnt*2);
}
if (mid<R){
sum+=q(mid+1,r,L,R,cnt*2+1);
}
return sum;
}
long long q2(long long l,long long r,long long L,long long R,long long cnt){
long long mid=(l+r)/2,sum=LLONG_MAX;
if (L<=l && r<=R){
return mi[cnt];
}
lz(cnt,l,r);
if (mid>=L){
sum=min(sum,q2(l,mid,L,R,cnt*2));
}
if (mid<R){
sum=min(sum,q2(mid+1,r,L,R,cnt*2+1));
}
return sum;
}
int main(){
// freopen("101.in","r",stdin);
//freopen("101.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n,m;
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> a[i];
}
for (int i=0;i<=400005;i++){
mi[i]=LLONG_MAX;
}
//memset(mi,0x3f3f3f3f,sizeof(mi));
build(1,n,1);
while (m--){
char op;
cin >> op;
if (op=='P'){
long long x,y,k;
cin >> x >> y >> k;
// for (int i=1;i<=)
up(1,n,x,y,1,k);
}
else if (op=='M'){
long long x,y;
cin >> x >> y;
cout << q2(1,n,x,y,1) << endl;
}
else if (op=='S'){
long long x,y;
cin >> x >> y;
cout << q(1,n,x,y,1) << endl;
}
}
// for (int i=1;i<=15;i++){
// cout << t[i] << " ";
// }
// cout << endl;
// for (int i=1;i<=15;i++){
// cout << tag[i] << " ";
// }
return 0;
}
/*
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
7 5
3 4 1 7 2 5 8
1 1 5 2
1 1 4 3
2 1 4
2 3 4
2 1 2最小函数值
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
long long a[10010][5];
long long ok[1000010];
long long yh;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> a[i][1] >> a[i][2] >> a[i][3];
}
for (int x=1;x<=m;x++){
for (int i=1;i<=n;i++){
if (yh>1000000){
break;
}
ok[++yh]=a[i][1]*x*x+a[i][2]*x+a[i][3];
}
}
sort(ok+1,ok+yh+1);
for (int i=1;i<=m;i++){
cout << ok[i] << " ";
}
return 0;
}晚上
模拟赛6
武术修行之路
魔法大陆的传送网络
斐波那契序列
羊腿切割
DAY 10
上午
讲解模拟赛题目
武术修行之路:记忆化搜索/广搜
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
vector<long long> f[300010];
long long t[300010];
long long dp[300010];
long long n;
long long dfs(long long x){
long long sum=t[x];
for (auto it:f[x]){
if (dp[it]==-1){
sum+=dfs(it);
}
}
dp[x]=sum;
return sum;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
memset(dp,-1,sizeof(dp));
for (int i=1;i<=n;i++){
cin >> t[i];
long long k;
cin >> k;
for (int j=1;j<=k;j++){
long long x;
cin >> x;
f[i].push_back(x);
}
}
cout << dfs(n);
return 0;
}魔法大陆的传送网络:最大公因数+set去重
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
struct node{
long long x,y;
}a[510];
//bool cmp(node s1,node s2){
// if (s1.x!=s2.x){
// return s1.x<s2.x;
// }
// return s1.y<s2.y;
//}
long long gcd(long long a,long long b){
a=abs(a);
b=abs(b);
if (b==0){
return a;
}
return gcd(b,a%b);
}
set<pair<long long,long long>> s;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i].x >> a[i].y;
}
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if (i!=j){
long long dx=a[i].x-a[j].x;
long long dy=a[i].y-a[j].y;
long long g=gcd(dx,dy);
if (g!=0){
dx/=g;
dy/=g;
if (dx!=0){
if (dx<0){
dx=-dx;
dy=-dy;
}
}
else{
if (dy<0){
dy=-dy;
}
}
}
s.insert({dx,dy});
}
}
}
cout << s.size()*2;
return 0;
}下午：
单调队列+字典树
单调队列模板
#include<bits/stdc++.h>
using namespace std;
deque<int> dq;
int a[2000010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> a[i];
}
cout<< 0 << endl;
for (int i=1;i<n;i++){
while (!dq.empty() && a[i]<a[dq.back()]){
dq.pop_back();
}
if (!dq.empty() && i-dq.front()>=m){
dq.pop_front();
}
dq.push_back(i);
cout << a[dq.front()] << '\n';
}
return 0;
}区间内的最小值
#include<bits/stdc++.h>
using namespace std;
deque<int> dq;
int a[2000010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> a[i];
}
cout<< 0 << endl;
for (int i=1;i<n;i++){
while (!dq.empty() && a[i]<a[dq.back()]){
dq.pop_back();
}
if (!dq.empty() && i-dq.front()>=m){
dq.pop_front();
}
dq.push_back(i);
cout << a[dq.front()] << '\n';
}
return 0;
}[HNOI2003] 操作系统
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int n,sum,ik;
struct node{
int id,t,s,x;
friend bool operator < (const node&x,const node&y){
if (x.x!=y.x){
return x.x<y.x;
}
return x.t>y.t;
}
}a[10000010];
priority_queue<node> q;
int il(int x,int y){
return x<y?x:y;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
while (cin >> a[n+1].id >> a[n+1].t >> a[n+1].s >> a[n+1].x){
n++;
}
a[n+1].t=0x3f3f3f3f;
for (int i=1;i<=n;i++){
q.push(a[i]);
ik=a[i].t;
while (!q.empty() && ik<a[i+1].t && sum<n){
node tmp=q.top();
q.pop();
int w=il(tmp.s,a[i+1].t-ik);
tmp.s-=w;
ik+=w;
if (!tmp.s){
cout << tmp.id << " " << ik << endl;
sum++;
}
else{
q.push(tmp);
}
}
}
return 0;
}Secret Message G
#include<bits/stdc++.h>
using namespace std;
struct node{
long long ol[2];
long long fg;
long long end;
}s[5000010];
long long tot=1,cs=1;
long long n,m,t,num;
void build(const vector<int>& ol){
cs=1;
for (int it:ol){
if (s[cs].ol[it]==0){
s[cs].ol[it]=++tot;
}
cs=s[cs].ol[it];
s[cs].fg++;
}
s[cs].end++;
}
long long q(const vector<int>& ol){
cs=1;
num=0;
for (int i=0;i<ol.size();i++){
int ed=ol[i];
if (s[cs].ol[ed]==0){
return num;
}
cs=s[cs].ol[ed];
if (s[cs].end>0){
num+=s[cs].end;
}
}
num+=s[cs].fg-s[cs].end;
return num;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> m >> n;
for (int i=1;i<=m;i++){
long long x,y;
cin >> x;
vector<int> ol;
while (x--){
cin >> y;
ol.push_back(y);
}
build(ol);
}
for (int i=1;i<=n;i++){
long long x,y;
cin >> x;
vector<int> ol;
while (x--){
cin >> y;
ol.push_back(y);
}
cout << q(ol) << endl;
}
return 0;
}Karuta
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
string s[500010];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i=0;i<n;i++){
cin >> s[i];
}
vector<pair<string,int>> ol;
for (int i=0;i<n;i++){
ol.push_back({s[i],i});
}
vector<int> lcp(n-1);
sort(ol.begin(),ol.end());
for (int i=0;i<n-1;i++){
const string &a=ol[i].first;
const string &b=ol[i+1].first;
int len=min(a.size(),b.size());
int j=0;
while (j<len && a[j]==b[j]){
j++;
}
lcp[i]=j;
}
vector<int> yu(n);
for (int i=0;i<n;i++){
int maxx=0;
if (i>0){
maxx=max(maxx,lcp[i-1]);
}
if (i<n-1){
maxx=max(maxx,lcp[i]);
}
yu[ol[i].second]=maxx;
}
for (int i=0;i<n;i++){
cout << yu[i] << endl;
}
return 0;
}晚上
Ha了咯World
餐馆
定向机器人
DAY 11
上午
讲解模拟赛题目
Ha了咯 World
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
int n,k,p;
cin >> n >> k >> p;
if (k==0){
cout << 0 << endl;
}
else if (n*p<abs(k)){
cout << -1 << endl;
}
else{
k=abs(k);
if (k%p==0){
cout << k/p << endl;
}
else{
cout << k/p+1 << endl;
}
}
}
return 0;
}餐馆
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
struct node{
long long x,y;
}a[200010];
bool cmp(int a,int b){
return a>b;
}
long long s[200010];
long long pl[200010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
int n;
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i].x;
}
for (int i=1;i<=n;i++){
cin >> a[i].y;
}
for (int i=1;i<=n;i++){
s[i]=a[i].y-a[i].x;
}
sort(s+1,s+n+1,cmp);
int qd=1,jz=n;
int sum=0;
while (qd<jz){
if (s[qd]+s[jz]<0){
jz--;
}
else{
qd++;
jz--;
sum++;
}
}
cout << sum << endl;
}
return 0;
}
/*
8 3 9 2 4 5
5 3 1 4 5 10
3 0 8 -2 -1 -5下午
初赛讲解
面向对象
#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
int sum=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-'){
f=-1;
}
ch=getchar();
}
while (ch>='0' && ch<='9'){
sum=sum*10+ch-48;
ch=getchar();
}
return sum*f;
}
void print(int x){
if (x<0){
putchar('-');
x=-x;
}
if (x>9){
print(x/10);
}
putchar(x%10+48);
return;
}
class ABC{
public://类似于struct里面的成员权限
ABC(int A=0,int B=0) :a(A),b(B){
cout << "ffrhttd\n";
// a=A;
// b=B;
}
// ~ABC(){//删除操作
// cout << "ewef";
// }
int a;
int getA(){
return a;
}
int getB(){
return b;
}
virtual int getnum(){//虚函数
return a*b;
}
private://里面的成员只能在类ABC内被访问
int b;
protected://里面的成员只会在类ABC和ABC的子类内被访问
};
class ABCD : public ABC{//ABC的子类
public:
ABCD (int A=0,int B=0,int C=0) : ABC(A,B),c(c){
cout << "ddcdfsg\n";
}
int getnum(){//多态
return a*c;
}
int getBB(){
return b;
}
private:
int c;
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ABCD p3(1,2,3);
cout << p3.getnum();
ABC p1(1,2);
cout << p1.getnum();
return 0;
}2025 6月gesp6级
哈夫曼编码
格雷码
2024 12月gesp6级
晚上
2025 6月 gesp7级
DAY 12
上午
2024 12月gesp7级
做CSP2023提高组第一轮洛谷有题
下午
2024 csp-s 完善程序
2023 csp-s 完善程序
拓扑排序
晚上
讲解CSP2023提高组第一轮洛谷有题
c++代码编译运行 Linux常见操作
Linux命令行
文件/目录
目录
1.切换 cd 根目录
cd.. 上一层
cd 目录名 1.绝对路径 2.访问下一层
2.建立/删除/查看
mkdir/rm/ls文件
新建 touch
打开方式 比如（code/vim） +文件名
rm:删除基本操作1
基本操作2
diff命令差异输出详情
时间复杂度主定理
DAY 13
上午
讲解CSP-S 2022初赛真题
常见排序时间复杂度总结
基数排序1
基数排序2
圆排列
欧拉回路1
欧拉回路2
阿克曼函数
下午
讲解CSP-S 2022初赛真题 完善程序
讲解CSP-S 2021完善程序
笛卡尔树1
笛卡尔树2
笛卡尔树3
讲解CSP-S 2020完善程序
lowbit(x): 二进制下表示最低位的1
晚上
初赛模拟赛1 69分 估分34
DAY 14
上午
讲解初赛模拟赛1
初赛模拟赛1
位运算1
位运算2
Linux命令行 基本操作1
Linux命令行 基本操作2
迪杰斯特拉算法
哈夫曼编码1
哈夫曼编码2
概率1
概率2
快速排序1
快速排序2
assert函数
assign用法
下午
概率与期望
初赛模拟赛2 73 估分18
晚上
讲解初赛模拟赛2
初赛模拟赛2
位运算溢出
概率1
概率2
概率3
容器适配器
迭代器
抽象类
最小生成树1
最小生成树2
字符串 strlen 1
字符串 strlen 2
DAY 15
上午
讲解初赛模拟赛2
下午
讲解线段树区间修改
之前的内容： 线段树
懒标记
下午
模拟赛3 82.5
晚上
讲解模拟赛3
Linux命令行 基本操作1
Linux命令行 基本操作2
视频文件格式
2-SAT算法1
2-SAT算法2
DAY 16
上午
讲解模拟赛3
unique函数