T1 小朋友的数字
题面
分析
动态规划
求最长子段和，容易想到对于每一个数 \(i\) ,最大子段不是 \(i-1\) (之前的子段)，就是以 \(i\) 为终点的一段前缀差，题面分数的解释很日龙
点击查看代码
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#define int __int128
#define N 1000010
using namespace std;
int n,p,a[N],dp[N],sum[N],so[N],mn,c[N],pre,Ans;
template<typename T>void read(T &x)
{
x=0;char c=getchar();T neg=0;
while(!isdigit(c))neg|=!(c^'-'),c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(neg)x=(~x)+1;
}
template<typename T>void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar((x-x/10*10)^48);
return ;
}
signed main()
{
// freopen("number.in","r",stdin);
// freopen("number.out","w",stdout);
read(n); read(p);
for(int i=1;i<=n;i++)
{
read(a[i]);
sum[i]=sum[i-1]+a[i];
}
memset(dp, -0x7f, sizeof dp);
// printf("%lld\n",dp[0]);
Ans=dp[0];
for(int i=1;i<=n;i++)
{
dp[i]=max(dp[i-1],sum[i]-mn);//
mn=min(sum[i],mn);//同时维护一个之前最小的前缀，保证之后的 dp 存在最大值
}
// for(int i=1;i<=n;i++) cout<<dp[i]<<" ";
// cout<<endl;
so[1]=dp[1];
Ans=max(Ans,so[1]);
so[1]+=so[1];
int maxx=dp[1]*2;
for(int i=2;i<=n;++i)
{
so[i]=maxx; maxx=max(maxx,maxx+dp[i]);// 每个小朋友的分数就是之前最大分数 下一次再加上 dp 真的日龙
Ans=max(Ans,so[i]);
}
/* for(int i=1;i<=n;i++) cout<<so[i]<<" ";
cout<<endl;*/
// Ans=(Ans%p);
// if(Ans<0) putchar('-'),wr(abs(Ans%p));
wr(Ans%p);
return 0;
}
T2 涂满它！
题面
分析
每次改变左上角的颜色，并且进行联通，问最少几次全部联通
容易想到搜索，但怎么搜才能最少联通
可以通过外层枚举实际的步数
在 DFS 内部从每一步开始从头枚举每一种颜色，暴力枚举
但这会超时
这就需要大名鼎鼎的 \(IDA*\) 估计一个继续下去的值
如果搜索过程已经超过了我们实际的值，就可以 \(return\) 了
具体实现看码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int vis[10][10],G[10][10];
int v[10],n,lim;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y,int col)
{
vis[x][y]=1;// 标记为联通
for(int i=0;i<4;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||yy<1||xx>n||yy>n||vis[xx][yy]==1) continue;
vis[xx][yy]=2;// 可以被改变
if(G[xx][yy]==col) dfs(xx,yy,col); //继续联通
}
}
int fill(int col)//拓展
{
// 因为联通块内颜色可以任意改变，只需要改变 可改变颜色 （ vis=2 ）
int num=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(vis[i][j]==2&&G[i][j]==col)
{
dfs(i,j,col); ++num;// 当前点可以改变 且 颜色与改变量相同
}
}
}
return num;
}
int IDA(int col,int wow)
{
int f=0;
for(int i=0;i<=5;i++) v[i]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(vis[i][j]!=1) v[G[i][j]]=1;
}
}
for(int i=0;i<=5;i++) f+=v[i];//最小估计答案
if(!f) return 1;
int tmp[10][10];
if(wow+f>lim) return 0;//当前答案加估计最小答案 已经大于 实际答案 IDA估价
memcpy(tmp,vis,sizeof (vis));
for(int c=0;c<=5;c++)
{
if(c==col) continue;
if(fill(c)&&IDA(c,wow+1)) return 1;// 将联通块变为 c 颜色 再次估价
memcpy(vis,tmp,sizeof (vis));// 还原 现场
}
return 0;
}
signed main()
{
while(1)
{
scanf("%lld",&n);
if(!n) return 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%lld",&G[i][j]),vis[i][j]=0;// 每次预处理
}
}
dfs(1,1,G[1][1]);// 处理起始的联通块 与 可改变的颜色
for(lim=0;;++lim)
{
if(IDA(G[1][1],0))
{
printf("%lld\n",lim);
break;
}
}
}
return 0;
}
/*
3
0 1 2
1 1 2
2 2 1
2
1 0
0 0
*/
T3 亹亹运算
分析
| 和 & 操作结合相当于移动二进制下 1 的位置
又因为 \(a^2+b^2<=(a+b)^2\) 每个数都可以由2进制表示 所以将 1 尽可能的移到一个数，使其尽可能大。
点击查看代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
#define N 1000010
using namespace std;
template<typename T>void read(T &x)
{
x=0;char c=getchar();T neg=0;
while(!isdigit(c))neg|=!(c^'-'),c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(neg)x=(~x)+1;
}
template<typename T>void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar((x-x/10*10)^48);
return ;
}
int n,a,cnt[N],ans,Ans,f;
void add(int x)
{
int t=0;
while(x)
{
if(x&1) cnt[t]++;
t++;
x>>=1;
}
}
signed main()
{
// srand(time(0));
freopen("wei.in","r",stdin);
freopen("wei.out","w",stdout);
read(n);
for(int i=1;i<=n;i++) read(a),add(a);
while(1)
{
int f=false,tmp=0;
for(int i=0;i<=30;i++)
{
if(cnt[i])
{
tmp+=(1<<i),cnt[i]--;
f=1;
}
}
Ans+=tmp*tmp;
if(!f) break;
}
; wr(Ans),putchar('\n');
return 0;
}
T4 开车旅行
题面
分析
倍增，模拟
先想 \(70pts\) 暴力 ，每一个城市之间预处理最近与次近距离
用 \(dis\) 表示人在 \(i\) 位置时下一步走的距离
用 \(to\) 表示在 \(i\) 位置下一步走到哪
对于问题1
枚举 \(n\)，分别走 \(x\) 比较 \(A\) 与 \(B\) 比值
有个小技巧，用 \(xor\) 操作判断是\(A\) 还是 \(B\) 走
注意精度丢失
对于问题2
老老实实去枚举就行了
为什么考虑倍增，因为对于每一个点来说，下一步走到的点都是确定的
可以倍增优化
倍增优化就无法 \(n^2\) 预处理
1.将每个点以海拔排序，\(O(n)\) 处理每个点的 最小 与 次小，细节慢慢调
2.预处理倍增，由于 \(A\) 和 \(B\) 轮流开车，将 \(A\) 和 \(B\) 一起跳
用 \(fa\) 记录在i点跳 \((1<<j)\) 个点后位置
用 \(dis\) 记录对应人总共跳的距离
3.倍增查询，由于最后可能存在 \(A\) 还可以走一段，注意特判下一步
点击查看代码
#includebool cmp(node a,node b){return a.h<b.h;};
int pd(int i,int l,int r)
{
if(!l) return re[r].id;
if(!r) return re[l].id;
if(re[i].h-re[l].h<=re[r].h-re[i].h) return re[l].id;
return re[r].id;
}
bool L(int i,int l,int r)
{
if(!l) return 0;
if(!r) return 1;
if(re[i].h-re[l].h<=re[r].h-re[i].h) return 1;
return 0;
}
void BZ()
{
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)
{
fa[i][j]=fa[fa[i][j-1]][j-1];
disA[i][j]=disA[i][j-1]+disA[fa[i][j-1]][j-1];
disB[i][j]=disB[i][j-1]+disB[fa[i][j-1]][j-1];
}
}
//int A,B,turn;
void find(int st,int X)
{
A=B=0;
for(int j=20;j>=0;j--)
{
if(A+B+disA[st][j]+disB[st][j]>X||!fa[st][j]) continue;
A+=disA[st][j]; B+=disB[st][j];
st=fa[st][j];
}
// cout<<"A--"<<A<<" "<<"B--"<<B<<endl;
if(to2[st]&&A+B+disA[st][0]<=X) A+=disA[st][0];
// cout<<"A--"<<A<<" "<<"B--"<<B<<endl;
return ;
}
double minv=2147483647;
signed main()
{
// memset(disA,127,sizeof disA);
// memset(disB,127,sizeof disB);
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&re[i].h),re[i].id=i;
sort(re+1,re+n+1,cmp);
for(int i=1;i<=n;i++)// build pos
{
pos[re[i].id]=i;
re[i].l=i-1;
re[i].r=i+1;
}
re[n].r=0;
// cout<<"build ";
for(int i=1;i<=n;i++) // id
{
int loc=pos[i];// location
int l=re[loc].l,r=re[loc].r;// pos_ l r
if(L(loc,l,r)) to1[i]=re[l].id, to2[i]=pd(loc,re[l].l,r);
else to1[i]=re[r].id , to2[i]=pd(loc,l,re[r].r);
if(l) re[l].r=r;//
if(r) re[r].l=l;//
}
// cout<<"^";
for(int i=1;i<=n;i++) //id
{
fa[i][0]=to1[to2[i]]; // i---fa_2^0;
disA[i][0]=abs(re[pos[i]].h-re[pos[to2[i]]].h);
disB[i][0]=abs(re[pos[fa[i][0]]].h-re[pos[to2[i]]].h);//
// cout<<i<<" "<<disB[i][0]<<"--"<<disA[i][0]<<" "<<to1[i]<<"--"<<to2[i]<<endl;
}
BZ();
scanf("%lld",&X);
for(int i=1;i<=n;i++)
{
find(i,X);
if(B&&1.0*A/B<minv)
{
ans=i; minv=1.0*A/B;
}
}
printf("%lld\n",ans);
scanf("%lld",&m);
for(int i=1;i<=m;i++)
{
int u,x;
scanf("%lld%lld",&u,&x);
find(u,x);
printf("%lld %lld\n",A,B);
}
return 0;
}
/*
4
2 3 1 4
3
4
1 3
2 3
3 3
4 3
1
1 1
2 0
0 0
0 0
10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7
2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0
*/
#include<bits/stdc++.h>
#define int long long
#define N 200010
using namespace std;
int disa[N],disb[N],toa[N],tob[N],h[N];
int n,X,m;
void init()
{
int dis;
//dis1---nex min to---nex min_pos
// memset(disa,127,sizeof disa);
// memset(disb,127,sizeof disb);
// memset(toa,0,sizeof toa);
// memset(tob,0,sizeof tob);
for(int i=1;i<n;i++)
{
disb[i]=abs(h[i]-h[i+1]);
for(int j=i+1;j<=n;j++)
{
dis=abs(h[j]-h[i]);
if(dis<disb[i]||(dis==disb[i]&&h[j]<h[tob[i]]))
{
disa[i]=disb[i];
toa[i]=tob[i];
disb[i]=dis;
tob[i]=j;
}
else
{
if(!disa[i]||dis<disa[i]||dis==disa[i]&&h[j]<h[toa[i]])
{
disa[i]=dis;
toa[i]=j;
}
}
}
}
}
int ans=0,minv=-1;
signed main()
{
// freopen("P1081_2.in","r",stdin);
// freopen("aaa","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
init();
scanf("%lld",&X);
// cout<<"&";
int turn=0;
// ask 1
for(int i=1;i<=n;i++)
{
// cout<<"^";
int pos=i,A=0,B=0,turn=0;
while(1)
{
// cout<<"*";
if(turn)
{
if(A+B+disb[pos]>X||!tob[pos]) break;
B+=disb[pos];
pos=tob[pos];
}
else
{
if(A+B+disa[pos]>X||!toa[pos]) break;
A+=disa[pos];
pos=toa[pos];
}
turn^=1;
}
// cout<<i<<"---"<<(1.0*A/B)<<" "<<A<<"-"<<B<<" ";
if(!ans||(1.0*A/B-minv<-0.000000001)||(fabs(1.0*A/B-minv)<=0.000000001&&h[ans]<h[i]))
{
ans=i; minv=1.0*A/B;
}
}
printf("%lld\n",ans);
//ask 2
scanf("%lld",&m);
for(int i=1;i<=m;i++)
{
int st,eng,turn=0;
scanf("%lld%lld",&st,&eng);
int A=0,B=0;
while(1)
{
if(turn)
{
if(A+B+disb[st]>eng||!tob[st])break;
B+=disb[st];
st=tob[st];
}
else
{
if(A+B+disa[st]>eng||!toa[st])break;
A+=disa[st];
st=toa[st];
}
turn^=1;
}
printf("%lld %lld\n",A,B);
}
return 0;
}
/*
4
2 3 1 4
3
4
1 3
2 3
3 3
4 3
1
1 1
2 0
0 0
0 0
10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7
2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0
*/