天梯赛省赛选拔赛复盘

题目链接
ZZU 2022 3.26选拔赛
题目链接A.蜗牛与井---签到B.火力覆盖---小学数学C.ZZ的函数---线性求逆元公式+除法分块D.自然溢出---找规律E.小y的棋子---线段树
标准线段树写法bitset优化写法 F.小y的镜像串---manacherG.飞，比跑快吧---bfs+模拟H.旋转矩阵---思维+模拟I.抽卡游戏---数学推导J.可莉的宝藏---高斯消元取模K.回文时刻---模拟L.hs爱矩形---模拟
A.蜗牛与井—签到
#include
using namespace std;
#define int long long
signed main()
{
    int h,x,y;
    cin>>h>>x>>y;
    h-=x;
    int res=(h+x-y-1)/(x-y);
    cout< 
B.火力覆盖—小学数学 
#include
#include
using namespace std;
#define int long long
signed main()
{
    int n;cin>>n;
    vectorres;
    int r=n;
    while(r>=1)
    {
        int x=(double)r*5/6+0.999999;
        res.push_back(x);
        int l=(double)x*0.8+0.999999;
        r=l-1;
    }
    cout< 
C.ZZ的函数—线性求逆元公式+除法分块 
#include 
#include 
#include 
using namespace std;
#define int long long
const int mod = 1000000007;
int qmi(int a,int b){int res=1;a=a%mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;}
int block[150]={1,682498929,491101308,76479948,723816384,67347853,27368307,625544428,199888908,888050723,927880474,281863274,661224977,623534362,970055531,261384175,195888993,66404266,547665832,109838563,933245637,724691727,368925948,268838846,136026497,112390913,135498044,217544623,419363534,500780548,668123525,128487469,30977140,522049725,309058615,386027524,189239124,148528617,940567523,917084264,429277690,996164327,358655417,568392357,780072518,462639908,275105629,909210595,99199382,703397904,733333339,97830135,608823837,256141983,141827977,696628828,637939935,811575797,848924691,131772368,724464507,272814771,326159309,456152084,903466878,92255682,769795511,373745190,606241871,825871994,957939114,435887178,852304035,663307737,375297772,217598709,624148346,671734977,624500515,748510389,203191898,423951674,629786193,672850561,814362881,823845496,116667533,256473217,627655552,245795606,586445753,172114298,193781724,778983779,83868974,315103615,965785236,492741665,377329025,847549272,698611116};
int get_fac(int x)
{
	int res=block[x/10000000];
	for(int i=x/10000000*10000000+1;i<=x;i++)res=res*i%mod;
	return res;
}
signed main()
{
	int l,r;cin>>l>>r;
	cout< 
D.自然溢出—找规律 
#include
using namespace std;
#define int unsigned long long
signed main()
{
    int n;cin>>n;
    if(n>=66)cout<<0<<'n';
    else
    {
        int res=1;
        for(int i=1;i<=n;i++)res*=i;
        cout< 
E.小y的棋子—线段树 
标准线段树写法 
#include 
#include 
#include 
#include 
using namespace std;
#define int long long
int n,m,idx=0;
mapS;
int a[10010];
struct node
{
    int l,r;
    int color[200];
}tr[40010];
int res[10010];
int get_number(int x)
{
    if(S.count(x))return S[x];
    else return S[x]=++idx;
}
void pushup(int u)
{
    for(int i=1;i<200;i++)
    	tr[u].color[i]=tr[u<<1].color[i]+tr[u<<1|1].color[i];
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u]={l,r};
        tr[u].color[a[l]]++;
    }
    else
    {
        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 x,int old,int v)
{
    if(tr[u].l==x&&tr[u].r==x)
    {
        tr[u].color[old]=0;
        tr[u].color[v]=1;
    }
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid)modify(u<<1,x,old,v);
        else modify(u<<1|1,x,old,v);
        pushup(u);
    }
}

void query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        for(int i=1;i<200;i++)res[i]+=tr[u].color[i];
    }
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)query(u<<1,l,r);
        if(r>mid)query(u<<1|1,l,r);
    }
}


signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]=get_number(a[i]);
    build(1,1,n);
    while(m--)
    {
        int op;cin>>op;
        if(op==1)
        {
            memset(res,0,sizeof res);
            int l,r;cin>>l>>r;
            query(1,l,r);
            int sum=0;
            for(int i=0;i<200;i++)sum+=!!res[i];
            cout<>p;
            modify(1,p,a[p],a[p%n+1]);
            a[p]=a[p%n+1];
        }
    }
}
 
bitset优化写法 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define int long long
bitset<150>color[40010];
int n,m,idx=0;
mapS;
int a[10010];
int get_number(int x)
{
    if(S.count(x))return S[x];
    else return S[x]=++idx;
}
void pushup(int u)
{
    color[u]=color[u<<1|1]|color[u<<1];
}
void build(int u,int l,int r)
{
    if(l==r)color[u][a[l]]=1;
    else
    {
        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 x,int v)
{
    if(l==x&&r==x)color[u].reset(),color[u][v]=1;
    else
    {
        int mid=l+r>>1;
        if(x<=mid)modify(u<<1,l,mid,x,v);
        else modify(u<<1|1,mid+1,r,x,v);
        pushup(u);
    }
}

bitset<150> query(int u,int l,int r,int ql,int qr)
{
    bitset<150>res;
    if(l>=ql&&r<=qr)
    {
        res|=color[u];
        return res;
    }
    else
    {
        int mid=l+r>>1;
        if(ql<=mid)res|=query(u<<1,l,mid,ql,qr);
        if(qr>mid)res|=query(u<<1|1,mid+1,r,ql,qr);
        return res;
    }
}

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]=get_number(a[i]);
    build(1,1,n);
    while(m--)
    {
        int op;cin>>op;
        if(op==1)
        {
            int l,r;cin>>l>>r;
            cout<>p;
            modify(1,1,n,p,a[p%n+1]);
            a[p]=a[p%n+1];
        }
    }
}
 
F.小y的镜像串—manacher 
#include 
#include 
#include 
using namespace std;
#define int long long
const int N = 200010,mod = 998244353;
int n;
char a[N],b[N];
int p[N];
bool check(char op)
{
	if(op=='0'||op=='1'||op=='8'||op=='#')return true;
	return false;
}
void init()
{
    int k=0;
    b[k++]='$',b[k++]='#';
    for(int i=0;imr)
        {
            mr=i+p[i];
            mid=i;
        }
    }
}
signed main()
{
    cin>>n;
	scanf("%s",a);
    init();
    manacher();
    int res=0;
    for(int i=0;i 
G.飞，比跑快吧—bfs+模拟 
#include
#include
#include
#include
#include
using namespace std;
const int mod =1e9+7;
int n,m,vf,vd;
int sx,sy,sz;//初始坐标
struct Point{
    int x,y,z;
}point[2010];
struct Fly//风场坐标
{
    int x,y,l,h;
}fly[2010];
bool get_point(Point a,Point b)//判断a点是否能到达b点
{
    double d=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    d=sqrt(d)/vf*vd;
    return a.z-d>=b.z;
}
int main() {
    cin>>n>>m>>vf>>vd;
    cin>>sx>>sy>>sz;
    for(int i=1,x,y,z;i<=n;i++)
    {
        cin>>x>>y>>z;
        point[i]={x,y,z};
    }
    for(int i=1,x,y,l,h;i<=m;i++)
    {
        cin>>x>>y>>l>>h;
        fly[i]={x,y,l,h};
    }
    //判断能到达的风场
    queueq;
    bool fly_Wind[2010]={0};
    q.push({sx,sy,sz});
    while(q.size())
    {
        Point t=q.front();
        q.pop();
        for(int i=1;i<=m;i++)
        {
            if(fly_Wind[i])continue;
            Point b={fly[i].x,fly[i].y,fly[i].l};
            if(get_point(t,b))
            {
                q.push({fly[i].x,fly[i].y,fly[i].h});
                fly_Wind[i]=true;
            }
        }
    }
    //不经过风场能到达的点
    int fly_Point[2010]={0};
    Point st={sx,sy,sz};
    for(int i=1;i<=n;i++)
        if(get_point(st,point[i]))fly_Point[i]=true;
    //判断每个能到达的风场能到达的点
    for(int i=1;i<=m;i++)
    {
        if(!fly_Wind[i])continue;
        for(int j=1;j<=n;j++)
        {
            if(fly_Point[j])continue;
            if(get_point({fly[i].x,fly[i].y,fly[i].h},point[j]))fly_Point[j]=true;
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)if(fly_Point[i])res++;
    cout< 
H.旋转矩阵—思维+模拟 
#include
#include
#include
#include
#include
using namespace std;
#define int long long
int g[10][200];
tuplemaxv[10];
void solve()
{
    memset(maxv,0,sizeof maxv);
    int n,m;
    cin>>n>>m;
    vectorq;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
             cin>>g[i][j],q.push_back(g[i][j]);
    sort(q.begin(),q.end(),greater());
    if(n<=3||n==4&&q[3]==q[4])
    {
        int res=0;
        for(int i=0;imp;
    for(int i=0;iy;
    vectorx[110];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(mp[g[i][j]])
            {
                y[j]=1;
                x[j].push_back(i);
            }
        }
    }
    if(y.size()==2)
    {
        mapst;
        for(auto [a,b] : y)
        {
            int xx=x[a][1]-x[a][0];
            st[xx]=1;
        }
        if(st.count(1)&&st.count(2))res=res-q[3]+q[4];
    }
    cout<>T;
    while(T--)solve();
}
 
I.抽卡游戏—数学推导 
#include 
#include 
#include 
using namespace std;
#define int long long
const int mod = 998244353;
int qmi(int a,int b){int res=1;a=a%mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;}
int Mod(int x){return (x%mod+mod)%mod;}
signed main()
{
    int n,m;
    cin>>n>>m;
    int s=(n+1)*n/2;
    s=qmi(Mod(s),mod-2);
    for(int i=1,now=0,last=0;i<=n;i++)
    {
        last=now;
        now+=n-i+1;
        now=Mod(now);
        int res=qmi(Mod(now*s),m)-qmi(Mod(last*s),m);
        cout< 
J.可莉的宝藏—高斯消元取模 
#include
#include
#include
#include
using namespace std;
#define int long long
int b[510],c[510];
int a[510][510];
int n,mod;
int Mod(int x){return (x%mod+mod)%mod;}
int qmi(int a,int b){int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;}

void guass()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
            if(a[j][i])
            {
                swap(a[i],a[j]);
                break;
            }
        if(a[i][i]==0){cout<<"No Solutionn";return ;}
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            int t=Mod(a[j][i]*qmi(a[i][i],mod-2));
            for(int k=1;k<=n+1;k++)
                a[j][k]=Mod(a[j][k]-a[i][k]*t);
        }
    }
    for(int i=1;i<=n;i++)a[i][n+1]=Mod(a[i][n+1]*qmi(a[i][i],mod-2));
    for(int i=1;i<=n;i++)cout<>n>>mod;
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++)a[i][n+1]=abs(Mod(c[i]-b[i]));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    guass();
}
 
K.回文时刻—模拟 
#include
using namespace std;
#define int long long
int a,b,c;
signed main(){
	scanf("%d:%d:%d",&a,&b,&c);
	c++;
	if(c==60)c=0,b++;
	if(b==60)b=0,a++;
	if(a==24)a=0,b=0,c=0;
	while(1){
		int aa=(a%10)*10+a/10;
		if(aa==c&&b/10==b%10)break;
		c++;
		if(c==60)c=0,b++;
		if(b==60)b=0,a++;
		if(a==24)a=0,b=0,c=0;
	}
	printf("%02d:%02d:%02d",a,b,c);
}
 
L.hs爱矩形—模拟 
#include 
using namespace std;
int main() {
    int x,y,a=0,b=0;
    for(int i=1;i<=3;i++)
    {
        cin>>x>>y;
        a^=x,b^=y;
    }
    cout<
天梯赛省赛选拔赛复盘

C/C++/C#相关栏目本月热门文章
