首页 > 其他分享 >初三奥赛模拟测试1

初三奥赛模拟测试1

时间：2024-05-04 12:12:33浏览次数：22  
标签：char int void write read 奥赛 inline 初三 模拟

初三奥赛模拟测试1

  1. T1 回文

    暴力 \(dp\) 是 \(n^4\) 的。

    类似传纸条吧无用状态去了就是 \(n^3\) 的

    CODE 
    #include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
const int N=502,MOD=993244853;
int n,m;
unsigned int dp[N][N][N<<1];
char ca[N][N];

namespace IO{
	template<class T> inline void write(T x){
		static T st[45];T top=0;if(x<0)x=-x,putchar('-');
		do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
	}
	template<class T = int> inline T read(T &x){
		char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
		while('0'<=s&&s<='9'){x=x*10+(s^48),s=getchar();} return (pd?(x=-x):x);
	}
}
namespace IO{
	inline char read(char &c){c=getchar();while(c<33||c>126) c=getchar();return c;}
	template<int MAXSIZE=INT_MAX> inline int read(char* c){
		char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
		while(s>=33&&s<=126&&pos<MAXSIZE) c[pos++]=s,s=getchar();c[pos]='\0';return pos;
	}
	template<int MAXSIZE=INT_MAX> inline int read(string &c){
		c.clear();char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
		while(s>=33&&s<=126&&pos<MAXSIZE) c.push_back(s),s=getchar(),pos++;return pos;
	}
	inline double read(double &x){scanf("%lf",&x);return x;}
	inline llf read(llf &x){scanf("%Lf",&x);return x;}
	template<class T,class... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
	template<class T = int> inline T read(){T a;return read(a);}
	inline void write(char c){putchar(c);}
	inline void write(char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
	inline void write(string &c){int len=c.size();For(i,0,len-1,1) putchar(c[i]);}
	inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
	template<int PRECISION=6> inline void write(double x){printf("%.*lf",PRECISION,x);}
	template<int PRECISION=6> inline void write(llf x){printf("%.*Lf",PRECISION,x);}
	template<class T> inline void Write(T x){write(x),putchar(' ');}
	inline void Write(char c){write(c);if(c!='\n') putchar(' ');}
	inline void Write(char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
	inline void Write(string &c){write(c);if(c[c.size()-1]!='\n') putchar(' ');}
	inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
	template<class T,class... Args> inline void write(T x,Args... args){write(x);write(args...);}
	template<class T,class... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
}
using namespace IO;
#define Check(y) (y>0&&y<=m)

int main(){
#ifndef ONLINE_JUDGE
	freopen("in_out/in.in","r",stdin);
	freopen("in_out/out.out","w",stdout);
#endif
	read(n,m);
	For(i,1,n,1) For(j,1,m,1) read(ca[i][j]);
	int len=((n+m)>>1)+1;
	dp[2][1][n]=(ca[1][1]==ca[n][m]);
	For(i,3,len,1) For(xa,1,n,1) For_(xb,n,1,1){
		int ya=i-xa,yb=m-(i-(n-xb+1))+1;
		if(!(Check(ya)&&Check(yb))) continue ;
		if(ca[xa][ya]==ca[xb][yb]) dp[i][xa][xb]+=(dp[i-1][xa][xb]+dp[i-1][xa-1][xb+1]+dp[i-1][xa-1][xb]+dp[i-1][xa][xb+1])%MOD;
	}
	int ans=0;
	if((n+m)&1)
		For(x,1,min(len-1,n),1) ans=(ans+dp[len][x][x]+dp[len][x][x+1])%MOD;
	else
		For(x,1,min(len-1,n),1) ans=(ans+dp[len][x][x])%MOD;
	write(ans);
}

  2. T2 快速排序

    把代码粘下来用有 24pts

    在无 nan 时写 sort 再得 12pts

    发现规律：

    没有 nan 就是升序排列

    如果第一个是 nan，nan 在最前面，接着排后面的数。

    否则就把小于等于第一个数的都提前（包括第一个数），升序排好后再排后面的。

    堆显然处理。

    CODE 
    #include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
const int N=5e5+4;
int val[N];
priority_queue<int,vector<int>,greater<int> > que;

namespace IO{
	template<class T> inline void write(T x){
		static T st[45];T top=0;if(x<0)x=-x,putchar('-');
		do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
	}
	template<class T> inline T read(T &x){
		char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
		while('0'<=s&&s<='9'){x=x*10+(s^48),s=getchar();} return (pd?(x=-x):x);
	}
}
namespace IO{
	inline char read(char &c){c=getchar();while(c<33||c>126) c=getchar();return c;}
	template<int MAXSIZE=INT_MAX> inline int read(char* c){
		char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
		while(s>=33&&s<=126&&pos<MAXSIZE) c[pos++]=s,s=getchar();c[pos]='\0';return pos;
	}
	template<int MAXSIZE=INT_MAX> inline int read(string &c){
		c.clear();char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
		while(s>=33&&s<=126&&pos<MAXSIZE) c.push_back(s),s=getchar(),pos++;return pos;
	}
	inline double read(double &x){scanf("%lf",&x);return x;}
	inline long double read(long double &x){scanf("%Lf",&x);return x;}
	template<class T,class... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
	template<class T=int> inline T read(){T a;return read(a);}
	inline void write(char c){putchar(c);}
	inline void write(char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
	inline void write(string &c){int len=c.size();For(i,0,len-1,1) putchar(c[i]);}
	inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
	template<int PRECISION=6> inline void write(double x){printf("%.*lf",PRECISION,x);}
	template<int PRECISION=6> inline void write(long double x){printf("%.*Lf",PRECISION,x);}
	template<class T> inline void Write(T x){write(x),putchar(' ');}
	inline void Write(char c){write(c);if(c!='\n') putchar(' ');}
	inline void Write(char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
	inline void Write(string &c){write(c);if(c[c.size()-1]!='\n') putchar(' ');}
	inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
	template<class T,class... Args> inline void write(T x,Args... args){write(x);write(args...);}
	template<class T,class... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
}
using namespace IO;

int main(){
#ifndef ONLINE_JUDGE
	freopen("in_out/in.in","r",stdin);
	freopen("in_out/out.out","w",stdout);
#endif
	int t; read(t);
	while(t--){
		int n; read(n);
		For(i,1,n,1){
			string a; read(a);
			if(a=="nan") val[i]=-1;
			else val[i]=atoi(a.c_str()),que.push(val[i]);
		}
		For(i,1,n,1){
			if(~val[i]){
				while(que.top()<val[i]) Write(que.top()),que.pop();
				if(!que.empty()&&val[i]==que.top()) Write(que.top()),que.pop();
			}else Write("nan");
		}
		while(!que.empty()) Write(que.top()),que.pop();
		puts("");
	}
}

  3. T3 混乱邪恶

    题目已经告诉了做法

    题目的限制已经保证了有解。

    考虑假贪心，将排序的序列随机交换（或循环位移）跑，最多不到 10 次就有正解。

    不会证，但也不太好卡。

    题解挺强的做法，我没看懂。

    CODE 
    #include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
const int N=2e6+4;
struct VAL{int val,id,ans;}c[N];
llt sum;

namespace IO{
	template<class T> inline void write(T x){
		static T st[45];T top=0;if(x<0)x=-x,putchar('-');
		do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
	}
	template<class T> inline T read(T &x){
		char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
		while('0'<=s&&s<='9'){x=x*10+(s^48),s=getchar();} return (pd?(x=-x):x);
	}
}
namespace IO{
	inline char read(char &c){c=getchar();while(c<33||c>126) c=getchar();return c;}
	template<int MAXSIZE=INT_MAX> inline int read(char* c){
		char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
		while(s>=33&&s<=126&&pos<MAXSIZE) c[pos++]=s,s=getchar();c[pos]='\0';return pos;
	}
	template<int MAXSIZE=INT_MAX> inline int read(string &c){
		c.clear();char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
		while(s>=33&&s<=126&&pos<MAXSIZE) c.push_back(s),s=getchar(),pos++;return pos;
	}
	inline double read(double &x){scanf("%lf",&x);return x;}
	inline long double read(long double &x){scanf("%Lf",&x);return x;}
	template<class T,class... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
	template<class T=int> inline T read(){T a;return read(a);}
	inline void write(char c){putchar(c);}
	inline void write(char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
	inline void write(string &c){int len=c.size();For(i,0,len-1,1) putchar(c[i]);}
	inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
	template<int PRECISION=6> inline void write(double x){printf("%.*lf",PRECISION,x);}
	template<int PRECISION=6> inline void write(long double x){printf("%.*Lf",PRECISION,x);}
	template<class T> inline void Write(T x){write(x),putchar(' ');}
	inline void Write(char c){write(c);if(c!='\n') putchar(' ');}
	inline void Write(char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
	inline void Write(string &c){write(c);if(c[c.size()-1]!='\n') putchar(' ');}
	inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
	template<class T,class... Args> inline void write(T x,Args... args){write(x);write(args...);}
	template<class T,class... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
}
using namespace IO;
mt19937 rnd(114514);
inline bool cmp_val(VAL a,VAL b){return a.val>b.val;}
inline bool cmp_id(VAL a,VAL b){return a.id<b.id;}
inline bool check(int l,int r){
	llt num=sum>>1;
	For(i,l,r,1){
		if(num-c[i].val>=0) num-=c[i].val,c[i].ans=1;
		else c[i].ans=-1;
	}
	return !num;
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("in_out/in.in","r",stdin);
	freopen("in_out/out.out","w",stdout);
#endif
	int n,m,cnt=0;read(n,m);
	For(i,1,n,1) read(c[i].val),c[i].id=i,sum+=c[i].val;
	puts("NP-Hard solved");
	int bg=1,ed=n;
	while(!check(bg,ed)) swap(c[rnd()%n+1],c[rnd()%n+1]),cnt++;
	cerr<<cnt<<endl;
	sort(c+bg,c+ed+1,cmp_id);
	For(i,bg,ed,1) Write(c[i].ans);
}

  4. T4 校门外歪脖树上的鸽子

    类似 zkw 线段树的更新，将左右儿子信息互换，用树剖维护。

    口胡的，没写。

标签：char,int,void,write,read,奥赛,inline,初三,模拟
From： https://www.cnblogs.com/xrlong/p/18172159

相关文章

  • CSS & JS Effect – 用 wheel 模拟 scroll
    前言在用JavaScript实现positionsticky 文章中，我提到了用wheel来模拟scroll效果。这篇来说说具体怎么实现，挺简单的哦。 Preparationtable.html<divclass="container"><table><thead><tr><th>FirstName</th>&l......
  • 集训 4 & 模拟 5
    集训4&模拟5有点唐简单，所以一起写了（其实是因为之前懒得写）集训4：T1模拟，赛时不删调试保龄了。T2显然贪心T3发现显然要两两互质，有因为父比子小，所以方案数就是将\(\varphi\)乘起来（甚至都不需要线性筛）T4meetinmiddle板子。模拟5T1特殊字符串显然有\(n^2\)......
  • 【网络自动化运维】使用pythonping检查设备的连通性并记录可达设备（eNSP模拟器）
    实验拓扑：PC的IP地址和五台交换机的地址在同一网段，具体IP如图所示。现在保证直连网络能够通信，并且故意将SW5的接口shutdown掉，保证无法联通，作为对照的测试设备。在PC上运行python代码，测试与五台交换机的连通性。由于本次测试使用的是pythonping模块，这并不是python自带的模块，需要......
  • mumu模拟器 MuMuManager.exe是MuMu模拟器12新加入的工具
    前言全局说明MuMuManager.exe是MuMu模拟器12新加入的工具官方说明：https://mumu.163.com/help/20230504/35047_1086360.html一、说明MuMu模拟器12的调用程序MuMuManager.exe在模拟器的安装目录下可以找到，如“X:\ProgramFiles\Netease\MuMuPlayer-12.0\shell>MuMuManager......
  • 纸牌游戏（超长大模拟）
    根据题意模拟即可，但这代码......CODE:#include<bits/stdc++.h>usingnamespacestd;inti[20]={0},t[20]={0},m[20]={0},ton[4][10]={0},z[10]={0},cmp[4][10]={0},zz[10][10]={0};intread(){ chara;intn;boolz=true; while(1) { a=getchar(); if(a>'9&#......
  • 2024/5/2 NOIP 模拟赛
    \(90+85+0+45=220\)本来应该\(100+100+15+45=260\)的，这样的成绩是我彩笔导致的。\(A\)题前缀异或桶，开考半个小时就将之秒掉了，但是没开\(\texttt{longlong}\)挂掉了\(10pts.\)非常生气。\(\texttt{B}\)思维题。给一个\(a_i(i=1,2,3,\cdots,n).\)进行无数次下面两种......
  • 数论模拟(1) 小朋友们，我们今天来找规律
    \(60\)分钟，干出来\(30\)至\(40\)分（满分\(50\)），最后一步没写出来还是有点rz.题目：求最小的整数\(n\)，使得对至少两个不同的奇素数\(p\)，有\[\sum_{k=1}^{n}(-1)^{v_p(k!)}<0.\]解：根据\(v_p\)函数的性质，可以对所有正整数进行规律性地分块，每块中的\(v_p\)值都是相同的：......
  • 模拟集成电路设计系列博客——6.2.5 毛刺
    6.2.5毛刺数字逻辑的毛刺是转换器进行高速工作时的一个主要问题，\({b_1,b_2,...,b_N}\)与开关信号直接关联。毛刺的来源是开关切换不同信号的延迟。例如，但数字码从\(0111...1\)切换到\(1000...0\)时，所有的\(N-1\)的LSB都关闭，而MSB打开，然而，有可能LSB开关的电流先于MSB开关的电流关......
  • 模拟集成电路设计系列博客——6.2.2 基于R-2R的转换器
    6.2.2基于R-2R的转换器为了避免二进制权重转换器中的巨大电阻比例，可以通过引入串联电阻来使得阵列中的信号缩放，如下图所示：注意此处的节点电压\(V_A\)等于参考电压\(V_{ref}\)的四分之一，作为\(3R\)的串联电阻引入的结果。同时注意一个额外的\(4R\)被添加在地处，从而使得从\(3R\)......
  • 模拟集成电路设计系列博客——6.2.3 电荷重分布开关电容转换器
    6.2.3电荷重分布开关电容转换器电荷重分布开关电容转换器的基本思想是将开关电容增益放大器的输入电容替换为一个可编程电容阵列（PCA，ProgrammableCapacitorArray），如下图所示：如我们之前在开关电容增益放大器时讨论的一样，上图中的电路对于放大器输入失调电压，\(1/f\)噪声和有限放......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99