专栏文章
2025 乔斯集训
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miojp15n
- 此快照首次捕获于
- 2025/12/02 20:19 3 个月前
- 此快照最后确认于
- 2025/12/02 20:19 3 个月前
2025 乔斯集训
注：具体内容可见课件/deepseek/OI Wiki
DAY 1
上午：
1. 广搜拓展 bfs spfa floyd
普通最短路 + 带权最短路
普通最短路 + 带权最短路
普通最短路：队列 queue 队尾插入删除
带权最短路： 01广搜 时间复杂度和普通广搜一样
2.
01广搜 时间复杂度和普通广搜一样
双端队列 deque 支持从队首队尾插入删除元素
链式前向星
点个数 n<=10^5 边条数 m<=10^6 一张有向图 边权0或1
求点1到其他点的最短路
C#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练习
C#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
C#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 世界冰球锦标赛
错误原因：方法种数计算错误
C#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）模板
C#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+边差分模板
边差分模板：
Cint 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;
}
点差分模板:
Cint 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+点差分模板
C#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
上午
讲解昨晚比赛题目
小杨的养??(熊)计划 //前缀和+分别统计
C#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）
C#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
背包：
武器购买
C#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;
}
道路优化
C#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.暴搜
C#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）
C#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;
}
互不侵犯
C#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;
}
金明的预算方案
C#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
上午
讲解模拟赛题目
小杨的字符串难题
C#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
拆墙大作战
C#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)
C#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递归时名字写错
C#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;
}
选课
第一种
C#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;
}
第二种
C#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
C#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;
}
石子合并 线性
C#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
C#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
上午
讲解比赛题目
小杨的空调温度调整
差分
C#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
C#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)
C#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个重心）
C#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个）
C#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
机房
C#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
建原树
缩点建新树
求新树直径
C#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)
C#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循环边界错误（逗号用法不明确导致边界错误，本来能对）
C#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
C#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)
C#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)
C#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模板
Chttps://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
C#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
C#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 无线传输
C#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;
}
#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为负整数（题面不明确）
C#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未判断
C#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
C#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
快速幂
C#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
欧拉筛筛欧拉函数
C#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 的幂的和（乘法逆元+快速幂）
C#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
C#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;
}
/*
下午
二项式定理
数学练习:费马小定理 乘法逆元 特殊处理
C#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
C#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;
}
排队（超级加强版）
C#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;
}
字符串
C#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;
}
非回文串
C#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
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()
{
cout << "He1lo,World";
return 0;
}
B
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()
{
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
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
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()
{
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
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 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
C#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
C#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
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 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
C#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
线段树模板
C#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;
}
合并果子
C#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
C#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
C#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
最小函数值
C#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
上午
讲解模拟赛题目
武术修行之路:记忆化搜索/广搜
C#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去重
C#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;
}
下午：
单调队列+字典树
单调队列模板
C#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;
}
区间内的最小值
C#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] 操作系统
C#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
C#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
C#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
C#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;
}
餐馆
C#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
下午
初赛讲解
C#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提高组第一轮洛谷有题
Linux命令行
文件/目录
目录
CPP 1.切换 cd 根目录
cd.. 上一层
cd 目录名 1.绝对路径 2.访问下一层
2.建立/删除/查看
mkdir/rm/ls
文件
CPP 新建 touch
打开方式 比如（code/vim） +文件名
rm:删除
DAY 13
上午
讲解CSP-S 2022初赛真题
下午
讲解CSP-S 2022初赛真题 完善程序
讲解CSP-S 2021完善程序
讲解CSP-S 2020完善程序
lowbit(x): 二进制下表示最低位的1
晚上
初赛模拟赛1 69分 估分34
DAY 14
上午
讲解初赛模拟赛1
下午
初赛模拟赛2 73 估分18
晚上
讲解初赛模拟赛2
DAY 15
上午
讲解初赛模拟赛2
下午
讲解线段树区间修改
之前的内容：
线段树
下午
模拟赛3 82.5
晚上
**讲解模拟赛3 **
DAY 16
上午
讲解模拟赛3
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...