20220928
t1 牛牛的方程式
思路
由裴蜀定理:若\(a,b\)为整数，且\(gcd(a,b)=d\)，那么一定存在整数\(x,y\)使得\(ax+by=d\)成立。这样，这道题就迎刃而解了。代码也非常简单，就不放上来了。唯一需要注意的就是运算过程中0可能会作为除数。
t2 牛牛的猜球游戏
思路1 线段树
可以发现对于一个操作区间\([l,r]\)，依次进行单个操作与先进行区间\([l,k]\)，再进行区间\([k,r]\)的操作是一样的。所以我们可以考虑用线段树维护这个操作，在进行区间合并时，我们只需将左区间\([l,k]\)的合并结果按照右区间的合并结果进行交换即可。为什么这样是正确的呢？其实也很简单，因为一个区间\([l,r]\)的合并结果与将该区间的操作顺次进行是等效的，所以区间\([l,k],[k,r]\)都与其所含操作是等效的，将区间\([l,k]\)按区间\([k,r]\)交换与按区间\([k,r]\)包含的操作逐次进行也是等效的。
代码如下=) 可能代码有亿点丑陋:(
点击查看代码
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=100005;
int n,m;
struct move{
int a,b;
}act[N];
struct po{
int pos[10];
void init(){
fo(i,0,9)pos[i]=i;
}
bool check(){
fo(i,0,9)if(pos[i]!=i)return 0;
return 1;
}
void outt(){
fo(i,0,9){
if(i==9)out(pos[i]),putchar('\n');
else out(pos[i]),putchar(' ');
}
}
};
struct node{
int l,r,lch,rch;
po p;
}rt[N<<1];
int tot;
inline void merge(int x,int l,int r){
fo(i,0,9)
rt[x].p.pos[i]=rt[l].p.pos[rt[r].p.pos[i]];
}
inline po amerge(po a,po b){
po ans;
fo(i,0,9)
ans.pos[i]=a.pos[b.pos[i]];
return ans;
}
inline int build(int l,int r){
++tot;
int x=tot;
rt[x].l=l;
rt[x].r=r;
if(l==r){
rt[x].p.init();
rt[x].p.pos[act[l].a]=act[l].b;
rt[x].p.pos[act[l].b]=act[l].a;
return x;
}
int mid=(l+r)>>1;
rt[x].lch=build(l,mid);
rt[x].rch=build(mid+1,r);
merge(x,rt[x].lch,rt[x].rch);
return x;
}
inline po query(int x,int l,int r){
if(l<=rt[x].l&&rt[x].r<=r)return rt[x].p;
int mid=(rt[x].l+rt[x].r)>>1;
po tmp;
tmp.init();
if(l<=mid)tmp=query(rt[x].lch,l,r);
if(r>mid)tmp=amerge(tmp,query(rt[x].rch,l,r));
return tmp;
}
po ans;
int l,r;
int main(){
in(n),in(m);
fo(i,1,n)in(act[i].a),in(act[i].b);
build(1,n);
fo(i,1,m){
in(l),in(r);
ans=query(1,l,r);
ans.outt();
}
return 0;
}
思路2 广义前缀和
我们考虑如何用类似于前缀和的形式\(sum[r]-sum[l-1]\)求出操作区间\([l,r]\)的答案。我们可以用类似于前缀和的形式一个数组（结构体，或vector）存下每次操作后的状态。然后再考虑如何在相减时抵消之前操作的影响。由于每次游戏开始时序号排列一定是\(1—n\),所以可将进行了\(l-1\)次操作后的对应xulie进行标号，相当于一步完成从\(1\)到\(l-1\)的所有操作。然后再通过类似的操作，用\(r\)的状态还原出答案。
点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=200005;
int n,m;
int sum[N][10];
int ans[10];
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=9;++i)sum[0][i]=i;
for(int i=1;i<=n;++i){
memcpy(sum[i],sum[i-1],sizeof(sum[i-1]));
int x,y;
scanf("%d%d",&x,&y);
swap(sum[i][x],sum[i][y]);
}
while(m--){
int l,r;
scanf("%d%d",&l,&r);
int tmp[20];
for(int i=0;i<=9;++i)tmp[sum[l-1][i]]=i;
for(int i=0;i<=9;++i)ans[i]=tmp[sum[r][i]];
for(int i=0;i<=9;++i)printf("%d%c",ans[i],i==9?' ':'\n');
}
return 0;
}