首页 > 其他分享 >2024初三集训模拟测试2

2024初三集训模拟测试2

时间：2024-02-20 22:25:32浏览次数：24  
标签：ch 奇数 int long 2024 include now 初三 集训

T0 谜之阶乘

题意：给定一个数 \(x\)，\(x\) 为 \(\dfrac{a!}{b!}\)，求 \(a\) 和 \(b\)。（多测，\(1\le x\le 10^{18}\)）
阶乘增长很快，\(a\) 和 \(b\) 的范围很小，所以直接暴力枚举即可。

T1 小P的2048

点击查看题目

image

根据题意模拟即可，根据方向决定遍历顺序比较方便。
点击查看代码 
#include<bits/stdc++.h>
#define int long long
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=10;
int last[N][N],now[N][N],ans,sum,n,m;
bool vis[N][N];
inline void up(){
	for(int i=2;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(now[i][j]){
				int x=i,y=j;
				while(x>1){
					if(now[x-1][y]){
						if(now[x-1][y]==now[x][y]){
							if(!vis[x-1][y]){
								vis[x-1][y]=1;
								now[x-1][y]*=2;
								sum+=now[x-1][y];
								now[x][y]=0;
							}
						}
						break;
					}else{
						now[x-1][y]=now[x][y];
						now[x][y]=0;
						x--;
					}
				}
			}
		}
	}
}
inline void down(){
	for(int i=n-1;i;--i){
		for(int j=1;j<=n;++j){
			if(now[i][j]){
				int x=i,y=j;
				while(x<n){
					if(now[x+1][y]){
						if(now[x+1][y]==now[x][y]){
							if(!vis[x+1][y]){
								vis[x+1][y]=1;
								now[x+1][y]*=2;
								sum+=now[x+1][y];
								now[x][y]=0;
							}
						}
						break;
					}else{
						now[x+1][y]=now[x][y];
						now[x][y]=0;
						x++;
					}
				}
			}
		}
	}
}
inline void left(){
	for(int j=2;j<=n;++j){
		for(int i=1;i<=n;++i){
			if(now[i][j]){
				int x=i,y=j;
				while(y>1){
					if(now[x][y-1]){
						if(now[x][y-1]==now[x][y]){
							if(!vis[x][y-1]){
								vis[x][y-1]=1;
								now[x][y-1]*=2;
								sum+=now[x][y-1];
								now[x][y]=0;
							}
						}
						break;
					}else{
						now[x][y-1]=now[x][y];
						now[x][y]=0;
						y--;
					}
				}
			}
		}
	}
}
inline void right(){
	for(int j=n-1;j;--j){
		for(int i=1;i<=n;++i){
			if(now[i][j]){
				int x=i,y=j;
				while(y<n){
					if(now[x][y+1]){
						if(now[x][y+1]==now[x][y]){
							if(!vis[x][y+1]){
								vis[x][y+1]=1;
								now[x][y+1]*=2;
								sum+=now[x][y+1];
								now[x][y]=0;
							}
						}
						break;
					}else{
						now[x][y+1]=now[x][y];
						now[x][y]=0;
						y++;
					}
				}
			}
		}
	}
}
inline void add(int k,int v){
	int tot=0,zc=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(!now[i][j])tot++;
	tot=1+(k%tot);
	for(int i=1;i<=n;++i){
		bool pd=0;
		for(int j=1;j<=n;++j){
			if(!now[i][j])zc++;
			if(zc==tot){now[i][j]=v;pd=1;break;}
		}
		if(pd)break;
	}
}
inline void check(){
	ans++;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(last[i][j]!=now[i][j])return;
	ans--;
	std::cout<<ans<<'\n'<<sum<<'\n';exit(0);
}
signed main(){
	// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
	n=read(),m=read();
	int x1=read(),y1=read(),v1=read(),x2=read(),y2=read(),v2=read();
	last[x1][y1]=v1,last[x2][y2]=v2;now[x1][y1]=v1,now[x2][y2]=v2;
	for(int i=1;i<=m;++i){
		memset(vis,0,sizeof(vis));
		int d=read(),k=read(),v=read();
		if(d==0)up();
		if(d==1)down();
		if(d==2)left();
		if(d==3)right();
		check();
		add(k,v);
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				last[i][j]=now[i][j];
	}
	std::cout<<ans<<'\n'<<sum<<'\n';
}

T2 子集

点击查看题目

image

My Algorithm：
将 \(n\) 个数平均分为 \(k\) 组，每组有 \(len=\dfrac{n}{k}\) 个数，将 \(k\) 个数划分为一组。只需要在这 \(len\) 组数中每组选一个即可构造出一组答案。
关于 \(k\) 和 \(len\)，有如下情况：

  • \(k\) 为奇数，\(len\) 为奇数。
  • \(k\) 为奇数，\(len\) 为偶数。
  • \(k\) 为偶数，\(len\) 为偶数。

至于为什么没有 \(k\) 为偶数，\(len\) 为奇数。这种情况，证明如下：
当 \(k\) 为偶数，\(len\) 为奇数。时，显然有 \(sum=\dfrac{n\cdot (n+1)}{2}\) 为奇数，此时 \(k\nmid sum\)，无解。
偶数随便构造，下面介绍奇数的构造。
奇数的构造比较困难在于 \(len\) 为奇数，如果按照偶数的方式来构造的话，就会剩下一组，并且所有组都要用到剩下这一组中间的数，可以先构造出公差为 \(1\) 的一些数，然后直接再按照偶数构造的方式构造 \(n-2\) 列，这样他们的差也是 \(1\)，这么说不好理解，附图如下。
n=15 k=3
image
发现红色区域的构造和偶数如出一辙，但由于 \(len\) 为奇数，所以他们的差为 \(1\)，所以继续构造出 \(3\) 组数，每组有 \(2\) 个数，且他们的和差值为 \(1\)。
前面容易处理，考虑后面，经过观察奇数和奇数，偶数和偶数，发现他们之间都相差 \(2\)，所以构造出为在两段中的差值都为 \(1\)。
发现奇数对应前一段，偶数对应后一段，如 n=25 k=5 这样的情况。
image
相信你已经看出规律了。代码如下。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
signed main(){
	// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
	int T=read();
	while(T--){
		int n=read(),k=read();
		int len=n/k,s=n*(n+1)/2;
		if(s%k||(k==n&&n!=1)){std::cout<<"No\n";continue;}
		std::cout<<"Yes\n";
		if(k==1){
			for(int i=1;i<=n;++i)std::cout<<i<<' ';
			std::cout<<'\n';continue;
		}
		if(len&1){
			int qian=len/2;
			for(int i=1;i<=k;++i){
				int sum=0;
				for(int j=i;j<=qian*k;j+=k){
					std::cout<<j<<' ';sum+=j;
				}
				int w=len-2;
				for(int j=w*k-i+1;j>qian*k;j-=k){
					std::cout<<j<<' ';sum+=j;
				}
				sum=s/k-sum;
				if(i&1){
					int zc=n-(i+1)/2+1;
					std::cout<<sum-zc<<' '<<zc;
				}else{
					int zc=len/2*2*k-(i/2)+1;
					std::cout<<zc<<' '<<sum-zc;
				}
				std::cout<<'\n';
			}
		}else{
			for(int i=1;i<=k;++i){
				for(int j=i;j<=n/2;j+=k)std::cout<<j<<' ';
				for(int j=n-i+1;j>n/2;j-=k)std::cout<<j<<' ';
				std::cout<<'\n';
			}
		}
	}	
}

T3 混凝土粉末

点击查看题目

image

询问本质是：作若干次区间加，并询问 $x$ 位置上的值最早 $h_x\ge y$ 的时间。

无脑做法为：主席树加二分，空间会炸，常数会炸，和优秀暴力一个分。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=1e6+10;
int n,m,cnt,root[N],a[N],now;
struct Tree{int ls,rs,h,tag;}t[N<<4];
inline void modify(int last,int p,int x,int y,int d,int l,int r){
	t[p]=t[last];
	if(x<=l&&r<=y){t[p].tag=t[p].tag+d;return;}
	int mid=l+r>>1;
	if(x<=mid)modify(t[last].ls,t[p].ls=++cnt,x,y,d,l,mid);
	if(y>mid)modify(t[last].rs,t[p].rs=++cnt,x,y,d,mid+1,r);
}
inline int query(int p,int x,int l,int r){
	if(l==r){return t[p].h+t[p].tag;}
	int mid=l+r>>1;
	if(x<=mid)return query(t[p].ls,x,l,mid)+t[p].tag;
	else return query(t[p].rs,x,mid+1,r)+t[p].tag;
}
inline int work(int x,int y,int r){
	if(query(root[r],x,1,n)<y)return 0;
	int ans=0,l=1;
	while(l<=r){
		int mid=l+r>>1;
		if(query(root[mid],x,1,n)>=y)r=mid-1,ans=mid;
		else l=mid+1;
	}
	return ans;
}
signed main(){
	// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
	n=read(),m=read();
	for(int i=1;i<=m;++i){
		root[i]=root[i-1];
		int opt=read();
		if(opt==1){
			int l=read(),r=read(),h=read();
			modify(root[i-1],root[i]=++cnt,l,r,h,1,n);
		}else{
			int x=read(),y=read();
			std::cout<<work(x,y,i)<<'\n';
		}
	}
}

正解做法为：把操作离线下来，扫描 \(1\) 到 \(n\) 的位置，用下标为操作时间的树状数组维护每个位置的所有操作时间的信息。
具体如下：扫描到一个位置 \(i\)，如果他是左端点，在树状数组上区间加 \(d\)，是右端点就区间减 \(d\)，消除这次操作的影响。此时树状数组维护的就是位置 \(i\) 在所有时刻的信息。如果是询问的话就在树状数组上倍增，找到第一个 \(h_i\ge y\) 的时间。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=1e6+10;
int n,q;
std::vector<std::pair<int,int>> st[N],qu[N];
struct Tree{
	int c[N];
	inline void add(int x,int d){for(int i=x;i<=q;i+=i&-i)c[i]+=d;}
	inline int query(int x,int y){
		int l=0,t=0;
		for(int i=std::__lg(x);i>=0;--i)
			if((l|1<<i)<=x&&t+c[(l|1<<i)|l]<y)
				t+=c[l|1<<i],l+=1<<i;
		return l==x?0:l+1;
	}
}t;
int __[N];
bool vis[N];
signed main(){
	// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
	n=read(),q=read();
	for(int i=1;i<=q;++i){
		int opt=read();
		if(opt==1){
			int l=read(),r=read(),h=read();
			st[l].push_back({i,h});
			st[r+1].push_back({i,-h});
		}else{
			int x=read(),y=read();
			qu[x].push_back({i,y});
			vis[i]=true;
		}
	}
	for(int i=1;i<=n;++i){
		for(auto it:st[i])t.add(it.first,it.second);
		for(auto it:qu[i])__[it.first]=t.query(it.first,it.second);
	}
	for(int i=1;i<=q;++i)if(vis[i])std::cout<<__[i]<<'\n';
}

大多数人的做法为：正解，但是没有在树状数组上二分，而是二分套树状数组。

这是白简的代码 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define int long long

using namespace std;

const int N = 2005000;

int n,q;
int opt[N],res[N];

vector< pair<int,int> > g[N],h[N];

class BIT{
	private:
		int bit[N];
		
		int lowbit(int x) {
			return x & (-x);
		}
	public:
		void Add(int x,int y,int val) {
			for(int i = x;i <= y; i += lowbit(i))
				bit[i] += val;
		}
		
		int Query(int x) {
			int ans = 0;
			
			for(int i = x;i; i -= lowbit(i))
				ans += bit[i];
				
			return ans;
		}
}tree;

signed main() {
	cin >> n >> q;
	for(int i = 1,l,r,x,y;i <= q; i++) {
		cin >> opt[i];
		if(opt[i] == 1) {
			cin >> l >> r >> x;
			g[l].push_back(make_pair(i,x));
			g[r + 1].push_back(make_pair(i,-x));
		}
		else {
			cin >> x >> y;
			h[x].push_back(make_pair(i,y));
		}
	}
	
	for(int i = 1;i <= n; i++) {
		for(int j = 0;j < g[i].size(); j++)
			tree.Add(g[i][j].first,q,g[i][j].second);
		
		for(int j = 0;j < h[i].size(); j++) {
			int l = 1,r = h[i][j].first,mid;
			
			while(l < r) {
				mid = (l + r) >> 1;
				if(tree.Query(mid) >= h[i][j].second)
					res[h[i][j].first] = r = mid;
				else
					l = mid + 1;
			}
		}
	}
	
	for(int i = 1;i <= q; i++)
		if(opt[i] == 2) 
			cout << res[i] << endl;
	return 0;
}

不知道为啥这个双 log 有人写的跑的比正解快，技不如人，膜拜~~

这里有一个赛时nishishui123的高分暴力，和主席树同分 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+100;
int n,q,p,num;
ll x,y;
struct node{
    int l,r,id;
    ll h;
}name[N];
ll height;
int main()
{
    scanf("%d%d",&n,&q);
    for(int t=1;t<=q;t++){
        scanf("%d",&p);
        if(p==1){
            ++num;
            scanf("%d%d%lld",&name[num].l,&name[num].r,&name[num].h);
            name[num].id=t;
        }
        else{
            scanf("%lld%lld",&x,&y);
            height=0;
            bool flag=0;
            for(int i=1;i<=num;i++){
                if(name[i].l<=x&&x<=name[i].r){
                    height+=name[i].h;
                    if(height>=y){
                        flag=1;
                        printf("%d\n",name[i].id);
                        break;
                    }
                }
            }
            if(flag==0)puts("0");
        }
    }
}

T4 排水系统

点击查看题目

image

比较板的概率期望，该润了，明天补。

标签：ch,奇数,int,long,2024,include,now,初三,集训
From： https://www.cnblogs.com/Ishar-zdl/p/18024163

相关文章

  • 20240220
    每日whk是令人绷不住的。今日份背诵古诗：静女静女静女其姝，俟我于城隅。爱而不见，搔首踟蹰。静女其娈，贻我彤管。彤管有炜，说怿女美。自牧归荑，洵美且异。匪女之为美，美人之贻。涉江采芙蓉涉江采芙蓉涉江采芙蓉，兰泽多芳草。采之欲遗谁？所思在远道。还顾望旧乡，长路漫浩......
  • 2024.2.20
    今天把之前的fastbinattack第二个实例搞明白了，明天理一下记成笔记学了一些网络安全基础知识明天继续昨天遭到网络诈骗，把事情大概说了一下，结果是损失了一个价值挺高的账号和三千余元。现在说一下今天的后续，我通过平台在国外的官方平台客服，把我的账号找回了（损失的钱还没找回来），中......
  • 2024初三集训模拟测试2
    2024初三集训模拟测试2T1大模拟磨了1hour，T2想了45mins弃了（其实就差一点），T3暴力，T4暴力都没打。策略有问题。T1小P的2048本来是暑假集训原题。\(Shadow\)以41秒的成绩直接贺过，甚至估分于是miaomiao来找，喜提换题。所以\(Shadow\)薄纱了。\(\sqrt{}8\)......
  • 2024.2.20闲话——luogu5021随机选取边的正确性
    推歌：生きる(feat.可不)——水野あつ这首歌听完之后接着转去咖喱乌冬了，歌词甚至能接上，没绷住。刚刚写证明中间把wxy的杯子碰倒洒键盘上了，抢救键盘的过程中碰到缝就有水，有点涩。但是这个键盘里面怎么这么脏啊？下面来证luogu5021在菊花树中以任何顺序选取边并采取贪心策略的......
  • 【闲话】2024.2.20
    年前yspm让我写闲话，我说文笔不好且没啥可写的，今天确实有很多想写一下的，看int_R等人今天都写闲话了，比较蠢蠢欲动。昨天莫名放电影了，四机房自然是从自己找若干电影中公投一个下载，这次的选择范围是整个豆瓣TOP250！最终《看不见的客人》在《幸福终点站》《被解救的姜戈》《小丑......
  • 2024.2.20 横渡海峡 年轻的人
    数学很难。头一次感觉非常罚坐，但是细细思考还是很有收获的。ARC172F需要尝试对操作找出一个优秀的描述。手玩一下操作，偷一张题解的图：仅看这一段，可以发现我们的操作形如：插入一个字符，然后删除一个字符。做到这里已经是提高组题目了，令\(f_{i,j}\)表示\(S\)匹配到\(i\)，\(T......
  • 2024.2.20 近期练习
    P4766不难发现时间的先后顺序是不重要的。所以把时间转化到数轴上。数据范围提示区间dp，设\(f_{l,r}\)表示\([l,r]\)时间里面全部消除的代价。\(f_{l,r}=\max(f_{l,k}+f_{k,r}+d_{l,k,r})\)，其中\(d_{l,k,r}\)表示跨越\(k\)的，且在\([l,r]\)里最远的距离。然而\(d\)......
  • #15 2024.2.19
    604.xsy5339怎么有人(why)605.xsy5340NOIP(noip)得到的结论是，动态凸包水太深，别碰，你把握不住。叉随机化叉了一万年，然后发现std是假的。遇到这种题来个猫树分治得了。傻逼。大粪模拟赛/tuu。606.qoj8224CaughtintheMiddle607.qoj1071The2022ICPCAsiaHan......
  • UESTC 2024 寒假集训 - Day4
    Preface万恶的psk搬的全是Atcoder上的题目，然后理所当然的后面题目全是CountingProblem了作为计数苦手直接当场暴毙，3h写完前面的8个题然后直接跑路AtCoderarc148_amodM开场差点被签到腐乳了，没发现答案不是\(1\)就是\(2\)直接傻掉了由于\(M=2\)时答案至多为\(2\)，因此只需......
  • 2024年2月20号题解
    P5594【XR-4】模拟赛解题思路重点是怎么判断是不是同一套模拟题用一个数组来标记是不是同一套题代码实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<time.h>#include<stdbool.h>#defi......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99