第一题 简单模拟
题目意思：给你起点终点坐标 每一步可以走周围8个方向一步 求最少步数
解题思路：由于可以走8个方向则哪一个方向最慢抵达就是答案
int ax,ay,sx,sy;
void solve()
{
cin>>ax>>ay>>sx>>sy;
cout<<max(abs(sx-ax),abs(sy-ay))<<endl;
return ;
}
第二题 简单模拟
题目意思：给你a，b 求a到b中每一个数对应时钟上的条数
解题思路：我们力求简洁的代码，先判断每一个数对应的条数用数组存下直接调用
int num[10]={6,2,5,5,4,5,6,3,7,6};// 手算一边就好
void solve(){
int n,m;
cin>>n>>m;
int ans=0;
for(int i=n;i<=m;i++){
int x=i;
while(x){
ans+=num[nn%10];
x/=10;
}
}
cout<<ans<<endl;
}
第三题 双指针
题目意思：给你一串数请你划分为最多区间，每一个区间都至少有一个一样的数，
每一个数都必须在区间中
解题思路：首先面对动态区间问题首先想到双指针，接着对于一个区间的数我们可以发现1e9，
那就要使用mp来用做桶存储，接着动态记录即可，可以明显发现当区间中从开始到出现两个
一样的数时此时区间最小，最后一定要注意要包含所有的数，所以只要有即使最后几个数不
是独立区间也加到区间里面
int t,n,m;
map<int,int> mp;
void solve()
{
vector<PII> ans;
cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
int res=0,last=1;
bool ok=false;
int num=0;
for(int i=1;i<=n;i++){
mp[a[i]]++;
if(mp[a[i]]==2) res++;
if(res){
ans.push_back({last,i});
mp.clear();// 下一个区间
last=i+1;
res=0;
}
}
if(ans.empty()){
cout<<-1<<endl;
return ;
}
ans[ans.size()-1].second=n;// 表示有满足要求的区间必须把后面的数都加入
cout<<ans.size()<<endl;
for(auto&[l,r]:ans) cout<<l<<' '<<r<<"\n";
return ;
}
第四题 数的交换？推式子
题目意思：给你两个数组,求通过交换0-2次以后使得数组的总和差值最小
解题思路：首先我们注意数据范围2000的第一想法当然是暴力+分类讨论，首先直接求和可以解决0次
直接暴力交换两个数时间复杂度是n * m,接着我们就要想如何交换2个数的可能性，首先我们可以发现这
两次交换不会出现同样的数，因为如果出现了同样的下标等价于交换一次，接着如果我们直接暴力的话
时间复杂度是4次级别的必然是不可以的，那么我们就要思考如何优化，我们对于交换的式子入手看是否
满足某些特性，交换两次 a求和变为 suma-a1-a2+b1+b2 b求和 sumb -b1-b2+a1+a2,我们要的是差值所以
answer=abs((suma-a1-a2+b1+b2)-(sumb -b1-b2+a1+a2)) 我们把一样的数放在一起整理一下可以得到
answer=abs((suma-2 (a1+a2))-(sumb-2 (b1+b2))) 那么我们是不是可以预处理出来对于每一个(suma-
2 (a1+a2))(sumb-2 (b1+b2))然后找到最小差值呢？ 显然是可以的，找到这样的数之后我们可以使用
二分或者双指针来找到
数差值最小的情况
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define enl "\n"
const int N = 1000010,mod=1e9+7;
int n,m;
int a[N],b[N];
struct code{
int x;
int l,r;
bool operator<(const code&t){
return x<t.x;
}
};
void solve(){
cin>>n;
int sa=0,sb=0;
for(int i=1;i<=n;i++) cin>>a[i],sa+=a[i];
cin>>m;
for(int i=1;i<=m;i++) cin>>b[i],sb+=b[i];
int ans0=abs(sa-sb);// 表示使用次数为0
int ans1=3e18;
int p1,p2;//表示交换一次
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int res=abs(sa+2*b[j]-sb-2*a[i]);
if(res<ans1){
ans1=res;
p1=i,p2=j;
}
}
vector<code> aa,bb;
code pp1,pp2;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
aa.push_back({sa-2*(a[i]+a[j]),i,j});
for(int i=1;i<=m;i++)
for(int j=i+1;j<=m;j++)
bb.push_back({sb-2*(b[i]+b[j]),i,j});
sort(aa.begin(),aa.end());
sort(bb.begin(),bb.end());
int ans2=3e18;
for(int i=0,j=0;i<aa.size();i++){// 使用双指针找到比a当前数要大于等于的b
while(j<bb.size() and bb[j].x<aa[i].x) j++;
if(j<bb.size() and ans2 > bb[j].x-aa[i].x){
ans2=bb[j].x-aa[i].x;
pp1=aa[i];
pp2=bb[j];
}
}
for(int i=0,j=0;i<bb.size();i++){// 同理如上
while(j<aa.size() and aa[j].x<bb[i].x) j++;
if(j<aa.size() and ans2 > aa[j].x-bb[i].x){
ans2=aa[j].x-bb[i].x;
pp1=aa[j];
pp2=bb[i];
}
}
if(ans0<=ans1 and ans0<=ans2){
cout<<ans0<<endl;
cout<<0<<endl;
return ;
}
if(ans1<=ans0 and ans1 <= ans2){
cout<<ans1<<endl;
cout<<1<<endl;
cout<<p1<<' '<<p2<<endl;
return ;
}
cout<<ans2<<endl;
cout<<2<<endl;
cout<<pp1.l<<' '<<pp2.l<<endl;
cout<<pp1.r<<' '<<pp2.r<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
solve();
}
第五题 构造dfs序列 典 二进制+线段树
题目意思：给你一棵树以及每一个点对应的颜色(1-60)，1为树根
有如下两个操作：
1.查询每一个点所在的子树的所有颜色数量
2.把一个点所在子树颜色全部修改为一个颜色
解题思路：首先这似乎是一个树上的区间修改和区间查询，我们好像不会什么树和线段树集合，不过
题目告诉了我们1为根节点那么我们可以在dfs中对每个节点打上标记来得到一个点所在子树的开头和结尾
void dfs(int u,int fa){// 建立dfs序列！！典
lef[u]=++idx;
cnt[idx]=u;
for(auto&v:g[u]){
if(v!=fa) dfs(v,u);
}
righ[u]=idx;
}
接着我们对一个点所在的子树进行操作就是对其left-right区间操作！
我们发现颜色数据范围是60 ！事出反常必有妖 每一个颜色可以使用二进制优化变成一个数来记录
接着可以使用异或运算来查询区间！！ 其他的就是普通线段树了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 500010;
struct code{
int l,r;
LL color;
LL lazy;
}tr[4*N];
int w[N];
vector<int> g[N];
int lef[N],righ[N],cnt[N];
int idx;
int n,m;
void dfs(int u,int fa){// 建立dfs序列！！典
lef[u]=++idx;
cnt[idx]=u;
for(auto&v:g[u]){
if(v!=fa) dfs(v,u);
}
righ[u]=idx;
}
void pushup(int u){
tr[u].color=tr[u<<1].color|tr[u<<1|1].color;
}
void pushdown(code&u,code&l,code&r){
if(u.lazy){
r.color=l.color=u.color;
r.lazy=l.lazy=u.lazy;
}
u.lazy=0;
}
void pushdown(int u){
pushdown(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,(1ll<<w[cnt[l]])};
return ;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int v){
if(tr[u].l>=l and tr[u].r<=r){
tr[u].color=(1ll<<v);
tr[u].lazy=(1ll<<v);
return ;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,v);
if(r>mid) modify(u<<1|1,l,r,v);
pushup(u);
}
LL query(int u,int l,int r){
if(tr[u].l>=l and tr[u].r<=r){
return tr[u].color;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
LL v=0;
if(l<=mid) v|=query(u<<1,l,r);
if(r>mid) v|=query(u<<1|1,l,r);
return v;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,-1);
build(1,1,idx);// 依据dfs 序列构造线段树 对dfs 序列进行操作
while(m--){
int op,u,v;
cin>>op;
if(op==1){
cin>>u>>v;
modify(1,lef[u],righ[u],v);
}
else{
cin>>u;
LL ans = query(1,lef[u],righ[u]);
cout<<__builtin_popcountll(ans)<<"\n";// 注意这个是求二进制中数的1数量ll表示是long long类型
}
}
return 0;
}
