10.3 模拟赛
远古时期就做过的模拟赛 依然无法AK 第一题数组还爆了
T1 万圣节的入场券
题目大意：
有n+1个数 其中有n个真的数 为一个合数x*互不相同的质数
另一个假的数 /x 后不为质数
给n+1个数 求其中那个假的数
思路：
可以两两求gcd 其中出现最多的那个gcd为x
若一个数不能整除x或除x后大于素数上限或除x后不为质数
线性筛预处理即可
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 #include<map> 10 #define inf 1001000 11 #define ll long long 12 #define MAXN 100100 13 #define lmt 1500000 14 using namespace std; 15 inline ll read() 16 { 17 ll x=0,f=1;char ch=getchar(); 18 while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();} 19 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 int n,ntp[lmt+100],p[lmt+100],tot,cnt[lmt]; 23 ll g[MAXN]; 24 void mem() 25 { 26 ntp[0]=ntp[1]=1; 27 for(int i=2;i<=lmt;i++) 28 { 29 if(!ntp[i]) p[++tot]=i; 30 for(int j=1;j<=lmt&&i*p[j]<=lmt;j++) 31 { 32 ntp[i*p[j]]=1; 33 if(i%p[j]==0) break; 34 } 35 } 36 } 37 ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);} 38 int main() 39 { 40 n=read()+1;ll x;mem(); 41 for(int i=1;i<=n;i++) g[i]=read(); 42 for(int i=1;i<=n;i++) x=gcd(g[i],g[i%n+1]),cnt[x]++,g[0]= cnt[x]>cnt[g[0]]?x:g[0]; 43 for(int i=1;i<=n;i++) 44 { 45 if(g[i]%g[0]) {printf("%lld",g[i]);return 0;} 46 if(g[i]/g[0]>lmt||ntp[g[i]/g[0]]) {printf("%lld",g[i]);return 0;} 47 } 48 }
T2 万圣节的积木
题目大意：
n个积木 从上至下数第 i 块积木覆盖了横坐标对应 Li 至 Ri 的范围，长度为 Ri−Li 单位长度
一个积木塔是否稳定的判定条件是：若一个积木塔有 m 层，当且仅当对于任意 i∈[1,m) ，从上至下数，前i 块积木的重心落在第i+1 块积木的覆盖范围内，则稳定，否则不稳定。前i 块积木的重心为前i 块积木的几何中心，以质量为权重的带权平均位置
要把塔搭好，避免中间过程出现不稳定结构（即最终积木塔分解成的一段一段的小积木塔都稳定，且在一个一个摞小积木塔时的所有中间形态也都稳定）提前规划好该如何把最终结构拆成小积木塔结构 保证拆解后层数最多的小积木塔层数最小
求拆解后层数最多的小积木塔层数最小是多少即可
思路：
从下向上dp i表示到第i层的答案
转移的时候枚举 j 判断整个是稳定的并且这一段的重心在下一层内
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 #include<map> 10 #define inf 2139062143 11 #define ll long long 12 #define MAXN 1010 13 using namespace std; 14 inline int read() 15 { 16 int x=0,f=1;char ch=getchar(); 17 while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();} 18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 19 return x*f; 20 } 21 int n,l[MAXN],r[MAXN],ok[MAXN][MAXN],dp[MAXN]; 22 double ctr[MAXN][MAXN],tmp,kg; 23 int main() 24 { 25 memset(dp,127,sizeof(dp)); 26 n=read(); 27 for(int i=n;i>=1;i--) l[i]=read(),r[i]=read(); 28 for(int i=n;i>=1;tmp=kg=0,i--) 29 for(int j=i;j>=1;j--) 30 { 31 tmp+=(r[j]*r[j]-l[j]*l[j])/2.0,kg+=r[j]-l[j],ctr[i][j]=tmp/kg; 32 if(i==j) ok[i][j]=1; 33 else if(ok[i][j+1]&&ctr[i][j+1]>=l[j]&&ctr[i][j+1]<=r[j]) ok[i][j]=1; 34 } 35 for(int i=1;i<=n;i++) 36 for(int j=1;j<=i;j++) 37 if(j==1) dp[i]= ok[i][1]?i:inf; 38 else if(ok[i][1]&&ctr[i][j]>=l[j-1]&&ctr[i][j]<=r[j-1]) dp[i]=min(dp[i],max(dp[j-1],i-j+1)); 39 printf("%d",dp[n]); 40 }
T3 万圣节的快递
题目大意：
思路：
80pt
发现两部分是互不影响的
可以两边分别n！枚举顺序 O n求答案
（na+nb=n的部分分写挂了 所以得了70pt
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 #include<map> 10 #define inf 2139062143 11 #define ll long long 12 #define MAXN 100100 13 using namespace std; 14 inline int read() 15 { 16 int x=0,f=1;char ch=getchar(); 17 while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();} 18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 19 return x*f; 20 } 21 int n,na,nb,hsh[MAXN]; 22 ll ans; 23 void calc(int x) 24 { 25 ans=0; 26 for(int i=1;i<=n;i++) 27 ans+=abs(x-hsh[i]),x=hsh[i]; 28 } 29 struct p30 30 { 31 int a,g[MAXN],tot,pos; 32 void work() 33 { 34 for(int i=1;i<=na;i++) 35 { 36 pos=tot=read(); 37 for(int i=1;i<=tot;i++) g[i]=read(),hsh[g[i]]=i; 38 } 39 for(int i=1;i<=nb;i++) 40 { 41 int x=read(); 42 for(int i=n;i>tot;i--) g[i]=read(),hsh[g[i]]=i; 43 } 44 calc(pos); 45 printf("%lld",ans); 46 } 47 }P30; 48 struct p40 49 { 50 int a[12][MAXN],b[12][MAXN],ca[12],cb[12],pa[12],pb[12]; 51 int t[MAXN],tot,sz,g[MAXN];ll res; 52 void work() 53 { 54 for(int i=1;i<=na;i++) 55 { 56 ca[i]=read(),pa[i]=i,sz+=ca[i]; 57 for(int j=1;j<=ca[i];j++) a[i][j]=read(); 58 } 59 for(int i=1;i<=nb;i++) 60 { 61 cb[i]=read(),pb[i]=i; 62 for(int j=1;j<=cb[i];j++) b[i][j]=read(); 63 } 64 tot=n+1,res=21474836470000000LL; 65 for(int i=1;i<=nb;i++) 66 for(int j=1;j<=cb[pb[i]];j++) t[--tot]=b[i][j],hsh[b[i][j]]=tot; 67 do 68 { 69 tot=0; 70 for(int i=1;i<=na;i++) 71 for(int j=1;j<=ca[pa[i]];j++) t[++tot]=a[pa[i]][j]; 72 for(int i=1;i<=n;i++) hsh[t[i]]=i; 73 calc(tot); 74 if(ans<res) 75 { 76 res=ans; 77 for(int i=1;i<=tot;i++) g[i]=t[i]; 78 } 79 }while(next_permutation(pa+1,pa+na+1)); 80 for(int i=1;i<=tot;i++) hsh[g[i]]=i; 81 for(int i=1;i<=tot;i++) t[i]=g[i]; 82 do 83 { 84 tot=n+1; 85 for(int i=1;i<=nb;i++) 86 for(int j=1;j<=cb[pb[i]];j++) t[--tot]=b[pb[i]][j]; 87 for(int i=1;i<=n;i++) hsh[t[i]]=i; 88 calc(tot-1); 89 if(ans<res) 90 { 91 res=ans; 92 for(int i=tot;i<=n;i++) g[i]=t[i]; 93 } 94 }while(next_permutation(pb+1,pb+nb+1)); 95 printf("%lld",res); 96 } 97 }P40; 98 int main() 99 { 100 n=read(),na=read(),nb=read(); 101 if(na<=1&&nb<=1) {P30.work();return 0;} 102 if(na<=10&&nb<=10) {P40.work();return 0;} 103 P40.work(); 104 }
100pt
用状压dp优化n！的枚举