首页 > 其他分享 >集训 4 & 模拟 5

集训 4 & 模拟 5

时间：2024-05-04 11:45:23浏览次数：12  
标签：const int void write Il 集训 模拟 out

集训 4 & 模拟 5

有点唐简单，所以一起写了（其实是因为之前懒得写）

集训 4：

T1 模拟，赛时不删调试保龄了。

T2 显然贪心

T3 发现显然要两两互质，有因为父比子小，所以方案数就是将 \(\varphi\) 乘起来（甚至都不需要线性筛）

T4 meet in middle 板子。

模拟 5

  1. T1 特殊字符串

    显然有 \(n^2\) 的 \(dp\)，发现字符集为 \(26\) 可以对结尾字符分别存储 \(\max\) 优化到 \(n*26\)

    CODE 
    #include<bits/stdc++.h>
#include<sys/mman.h>
#include<fcntl.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define Ct const
#define Il __always_inline
#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))
#define For_it(i,a,b) for(auto i=(a);i!=(b);++i)

namespace IO{
#ifdef ONLINE_JUDGE
	int Fin=open("shiki.in",0); FILE* Fout=fopen("shiki.out","w");
#elif defined(UN_FAST)
	FILE *Fin=freopen("in_out/in.in","r",stdin),*Fout=freopen("in_out/out.out","w",stdout);
#else
	int Fin=open("in_out/in.in",0); FILE* Fout=fopen("in_out/out.out","w");
#endif // file
#ifdef UN_FAST
	char cc;
	#define G (cc=getchar())
	#define C cc
#else
	const char *I=(char*)mmap(0,1<<28,1,2,Fin,0)-1; 
	#define G (*++I)
	#define C (*I)
#endif // fast (mmap)
#define P(x) putc_unlocked(x,Fout)
	template<class T> Il void read(T &x){x=0;bool f=0; while(f|=G==45,C<48); while(x=x*10+(C&15),G>47); f?x=-x:0;}
	template<class T> void write(T x){if(x<0)P('-'),x=-x; if(x/10)write(x/10); P('0'+x%10);}
	Il void read(char &c){while(G<33); c=C;} void read(char *s){int p=-1; while(G<33); while(s[++p]=C,G>32); s[++p]='\0';}
	Il void read(string &s){s.clear(); while(G<33); while(s.push_back(C),G>32);}
	template<class T=int> Il T read(){T a; read(a); return a;}
	template<class T,class... Argc> Il void read(T &x,Argc&... argc){read(x),read(argc...);}
	Il void write(const char &c){P(c);} Il void write(const char *s){for(const char *c=s;*c!='\0';++c) P(*c);}
	Il void write(const string &s){for(const char& c:s) P(c);}
	template<class T,class... Argc> Il void write(const T &x,const Argc&... argc){write(x),write(argc...);}
	template<class T> Il void Write(const T &x){write(x),P(' ');} Il void Write(const char &c){P(c); if(c>32)P(' ');}
	template<class T,class... Argc> Il void Write(const T &x,const Argc&... argc){Write(x),Write(argc...);}
#undef G
#undef C
#undef P
#define endl '\n'
}using IO::read; using IO::write; using IO::Write;

constexpr int N=1e5+3;
llt ma[30],n,m,wt[30][30],ans;
string s;

int main(){
	read(n,s,m);
	For(i,1,m,1){
		char a,b; int k; read(a,b,k);
		wt[a-'a'][b-'a']+=k;
	}
	memset(ma,-0x3f,sizeof(ma));
	ma[s[0]-'a']=0;
	For(i,2,n,1){
		int nw=s[i-1]-'a';
		For(j,0,25,1) ans=max(ans,ma[j]+wt[j][nw]);
		ma[nw]=max(ma[nw],ans);
	}
	write(ans);
}
// For(i,1,n,1) For(j,1,i-1,1) dp[i]=max(dp[i],dp[j]+wt[s[j-1]-'a'][s[i-1]-'a']);

  2. T2 宝可梦

    发现从一个点到自己的路径是一个环，并且每条询问路径都是环上一段，直接预处理环即可（不太好写，赛时想假了好几次）。

    CODE 
    #include<bits/stdc++.h>
#include<sys/mman.h>
#include<fcntl.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define Ct const
#define Il __always_inline
#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))
#define For_it(i,a,b) for(auto i=(a);i!=(b);++i)

namespace IO{
#ifdef ONLINE_JUDGE
	int Fin=open("pokemon.in",0); FILE* Fout=fopen("pokemon.out","w");
#elif defined(UN_FAST)
	FILE *Fin=freopen("in_out/in.in","r",stdin),*Fout=freopen("in_out/out.out","w",stdout);
#else
	int Fin=open("in_out/in.in",0); FILE* Fout=fopen("in_out/out.out","w");
#endif // file
#ifdef UN_FAST
	char cc;
	#define G (cc=getchar())
	#define C cc
#else
	const char *I=(char*)mmap(0,1<<28,1,2,Fin,0)-1; 
	#define G (*++I)
	#define C (*I)
#endif // fast (mmap)
#define P(x) putc_unlocked(x,Fout)
	template<class T> Il void read(T &x){x=0;bool f=0; while(f|=G==45,C<48); while(x=x*10+(C&15),G>47); f?x=-x:0;}
	template<class T> void write(T x){if(x<0)P('-'),x=-x; if(x/10)write(x/10); P('0'+x%10);}
	Il void read(char &c){while(G<33); c=C;} void read(char *s){int p=-1; while(G<33); while(s[++p]=C,G>32); s[++p]='\0';}
	Il void read(string &s){s.clear(); while(G<33); while(s.push_back(C),G>32);}
	template<class T=int> Il T read(){T a; read(a); return a;}
	template<class T,class... Argc> Il void read(T &x,Argc&... argc){read(x),read(argc...);}
	Il void write(const char &c){P(c);} Il void write(const char *s){for(const char *c=s;*c!='\0';++c) P(*c);}
	Il void write(const string &s){for(const char& c:s) P(c);}
	template<class T,class... Argc> Il void write(const T &x,const Argc&... argc){write(x),write(argc...);}
	template<class T> Il void Write(const T &x){write(x),P(' ');} Il void Write(const char &c){P(c); if(c>32)P(' ');}
	template<class T,class... Argc> Il void Write(const T &x,const Argc&... argc){Write(x),Write(argc...);}
#undef G
#undef C
#undef P
#define endl '\n'
}using IO::read; using IO::write; using IO::Write;

constexpr int N=1e5+3,NM=5e5+3,mx[]={0,0,-1,0,1},my[]={0,1,0,-1,0},tlt[]={0,2,3,4,1},trt[]={0,4,1,2,3};
vector<bool> c[N];
vector<int> pos[5][N];
int n,m,q,cnt;

void Dfs(Ct int &x,Ct int &y,Ct int &fw){
	if(pos[fw][x][y]) return ;
	pos[fw][x][y]=++cnt;
	int nf=trt[fw];
	For(i,1,4,1){
		int nx=x+mx[nf],ny=y+my[nf];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&c[nx][ny]) Dfs(nx,ny,nf);
		nf=tlt[nf];
	}
}
Il void Init(){
	int x,y;
	read(n,m);
	For(i,1,n,1){
		c[i].resize(m+3);
		For(k,1,4,1) pos[k][i].resize(m+3);
		For(j,1,m,1) if(read<char>()=='.') c[i][j]=1,x=i,y=j;
	}
	Dfs(x,y,2);
}

Il int Get(Ct int &xa,Ct int &ya,Ct int &fa,Ct int &xb,Ct int &yb,Ct int &fb){
	if(!pos[fa][xa][ya]||!pos[fb][xb][yb]) return 0x3f3f3f3f;
	if(pos[fa][xa][ya]<=pos[fb][xb][yb]) return pos[fb][xb][yb]-pos[fa][xa][ya];
	return cnt+pos[fb][xb][yb]-pos[fa][xa][ya]-1;
}

int main(){
	Init();
	read(q);
	For(i,1,q,1){
		int xa,ya,xb,yb,fa; char c; read(xa,ya,xb,yb,c);
		if(c=='R') fa=1; else if(c=='U') fa=2; else if(c=='L') fa=3; else fa=4;
		if(xa==xb&&ya==yb){write(0,'\n'); continue;}
		xa+=mx[fa],ya+=my[fa];
		int ans=0x3f3f3f3f; For(i,1,4,1) ans=min(ans,Get(xa,ya,fa,xb,yb,i)+1);
		write(ans,'\n');
	}
}

  3. T3 矩阵

    如果有相邻且相同的，就是 \(-1\)

    其他情况对公比分治，在公比 \(>200\) 时最多长度为 \(2\)，可以直接整。

    公比 \(\le 200\) \(n^2*\text{公比}\) 暴力 \(dp\) 即可。

    也可以直接最长路。

    ps:

    谁 tm 造的数据，每个 sub 里塞一个 ans=1 ，给我卡没了。

    CODE 
    #include<bits/stdc++.h>
#include<sys/mman.h>
#include<fcntl.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define Ct const
#define Il __always_inline
#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))
#define For_it(i,a,b) for(auto i=(a);i!=(b);++i)

namespace IO{
#ifdef ONLINE_JUDGE
	int Fin=open("matrix.in",0); FILE* Fout=fopen("matrix.out","w");
#elif defined(UN_FAST)
	FILE *Fin=freopen("in_out/in.in","r",stdin),*Fout=freopen("in_out/out.out","w",stdout);
#else
	int Fin=open("in_out/in.in",0); FILE* Fout=fopen("in_out/out.out","w");
#endif // file
#ifdef UN_FAST
	char cc;
	#define G (cc=getchar())
	#define C cc
#else
	const char *I=(char*)mmap(0,1<<28,1,2,Fin,0)-1; 
	#define G (*++I)
	#define C (*I)
#endif // fast (mmap)
#define P(x) putc_unlocked(x,Fout)
	template<class T> Il void read(T &x){x=0;bool f=0; while(f|=G==45,C<48); while(x=x*10+(C&15),G>47); f?x=-x:0;}
	template<class T> void write(T x){if(x<0)P('-'),x=-x; if(x/10)write(x/10); P('0'+x%10);}
	Il void read(char &c){while(G<33); c=C;} void read(char *s){int p=-1; while(G<33); while(s[++p]=C,G>32); s[++p]='\0';}
	Il void read(string &s){s.clear(); while(G<33); while(s.push_back(C),G>32);}
	template<class T=int> Il T read(){T a; read(a); return a;}
	template<class T,class... Argc> Il void read(T &x,Argc&... argc){read(x),read(argc...);}
	Il void write(const char &c){P(c);} Il void write(const char *s){for(const char *c=s;*c!='\0';++c) P(*c);}
	Il void write(const string &s){for(const char& c:s) P(c);}
	template<class T,class... Argc> Il void write(const T &x,const Argc&... argc){write(x),write(argc...);}
	template<class T> Il void Write(const T &x){write(x),P(' ');} Il void Write(const char &c){P(c); if(c>32)P(' ');}
	template<class T,class... Argc> Il void Write(const T &x,const Argc&... argc){Write(x),Write(argc...);}
#undef G
#undef C
#undef P
#define endl '\n'
}using IO::read; using IO::write; using IO::Write;

constexpr int N=4e4+3,mx[]={0,1,-1,0,0},my[]={0,0,0,1,-1};
vector<int> c[N],dp[N];
int n,m,ans=1;
int dfs(int x,int y,int k){
	if(dp[x][y]) return dp[x][y];
	else {
		For(i,1,4,1){
			int nx=x+mx[i],ny=y+my[i];
			if(nx>n||nx<1||ny>m||ny<1||c[nx][ny]!=c[x][y]*k) continue;
			dp[x][y]=max(dp[x][y],dfs(nx,ny,k));
		}
		dp[x][y]+=1;
		return dp[x][y];
	}
}

int main(){
	For(i,1,N-3,1) c[i].push_back(0);
	read(n,m);
	For(i,1,m,1){
		c[1].push_back(read());
		if(c[1][i]==c[1][i-1]){write(-1); return 0;}
		else if(i!=1&&(c[1][i]%c[1][i-1]==0||c[1][i-1]%c[1][i]==0)) ans=2;
	}
	For(i,2,n,1) For(j,1,m,1){
		c[i].push_back(read());
		if(c[i][j]==c[i][j-1]||c[i][j]==c[i-1][j]){write(-1); return 0;}
		else if(j!=1&&(c[i][j]%c[i][j-1]==0||c[i][j-1]%c[i][j]==0||c[i][j]%c[i-1][j]==0||c[i-1][j]%c[i][j]==0)) ans=2;
	}
	For(i,2,200,1){
		For(j,1,n,1) dp[j].clear(),dp[j].resize(m+1);
		For(a,1,n,1) For(b,1,m,1) ans=max(ans,dfs(a,b,i));
	}
	write(ans);
}

  4. T4 乘法

    这是真唐，整个拉插板子，我也不会，题解也不会

    标签：const,int,void,write,Il,集训,模拟,out
    From： https://www.cnblogs.com/xrlong/p/18172135

相关文章

  • [国家集训队] 矩阵乘法 题解
    发现实际上就是二维静态区间最大值，可以用整体二分维护。时间复杂度\(O((q+n^2)\log\max(a_{i,j})\logn^2)\)。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintW=310005;constintQ=6e4+5;intn,q,w,ans[Q];intc[505][505],m;voidadd(i......
  • 【网络自动化运维】使用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&#......
  • QBXT五一集训DAY1笔记
    \(Day1\)\(ASCII\)简单来说，\(ASCII\)其实就是字符与数字之间的映射比如说，\('a'\)的\(ASCII\)就是\(97\)模运算：%来复习一下小学数学：\(a/b=c……d\)这里的\(d\)就是\(a\)除以\(b\)的余数，在计算机中，用%来表示通过这个式子，我们进而得出\(a=b*c+d\)请一定要记住这......
  • 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