OJ
A K题的大模拟实在写不动了 摸掉了(其实是其他作业叠太多了)等有空了再说吧
写得太烂 大佬们请不要介意
给你一个象棋盘 棋子的个数可能跟普通的不同 问能否在2步内将对方的军
A掉的大佬tql
考场一看是到大模拟 果断跳
给你竖着的n个积木 当积木的长度能被高度加1整除可抽出
给定积木堆 问是否能被抽完
显然上面的积木不会对下面积木造成影响
对于某个高度的积木
在最优抽出的过程中 一定能保证 对于其高度及其以下的位置 在某个时刻能够达到
那么 对于该积木 如果能被 其高度及其以下的 任意一高度整除 那么该积木就可抽出
考虑从底层往上枚举 用cup记录该数能否被抽
设高度为x
如果x为质数 那么 将x*Z 都可以取到
如果非质数 那么一定被之前某个质数的更新所覆盖
最终的流程就是
线性筛预处理质数
从底层往上枚举
判断该高度积木能否抽出
更新cup标记能取到的值
输出结果
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } const int N=2e6+10; int n,mx; int a[N],pd[N]; int prime[N],top,vis[N]; void xxs(int mx)//线性筛 { vis[0]=vis[1]=1; //1为不是0为是 for(int i=2;i<=mx;i++) { if(!vis[i]) prime[++top]=i; for(int j=1;j<=top&&prime[j]*i<=mx;j++) { vis[prime[j]*i]=1; if(!(i%prime[j])) break; } } } int main() { n=read();xxs(N-10); for(int i=1;i<=n;i++) a[i]=read(),mx=max(mx,a[i]); for(int i=1;i<=n;i++) { int del=i+1; if(!vis[del]) for(int j=del;j<=N-10;j+=del) pd[j]=1; if(!pd[a[i]]){printf("NO");return 0;} } printf("YES"); return 0; }
给个层数最高0层最高25次
k +5次 d -10次 a -2次
给定kda个数
问有多少种排列方法使得最后层数为25次
刚开始被原题意误导说大于等于25次 以为层数能大于25 错了好几次 浪费了一段时间
直接考虑dp emmm不知道为什么我开始还怀疑了正确性 考虑正做还是反做 还是用广搜做
数据范围有限 可直接设dp[i][j][k][v] 前三位表示各用了多少次 一维表示当前的值
记得用max min 限制更新 时v更新时的上下界
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } const ll N=100; ll k,d,a,ans; ll dp[20][10][10][70]; int main() { k=read(),d=read(),a=read(); dp[0][0][0][0]=1; for(ll i=0;i<=k;i++) for(ll j=0;j<=d;j++) for(ll k=0;k<=a;k++) for(ll v=0;v<=25;v++) { dp[i+1][j][k][min(25*1ll,v+5*1ll)]+=dp[i][j][k][v]; dp[i][j+1][k][max(0*1ll,v-10*1ll)]+=dp[i][j][k][v]; dp[i][j][k+1][min(25*1ll,v+2*1ll)]+=dp[i][j][k][v]; } for(ll i=25;i<=25;i++) ans+=dp[k][d][a][i]; cout<<ans; return 0; }
给2个式子求另个式子
没什么好说的 真的强行数学题
(2)*2-(1)=(3)
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } #define db double const db pi=3.1415926; int main() { printf("%.3lf",pi*pi/12.0); return 0; }
给你个方阵的左上角位置和边长 给你个点
问以改点为圆心 最小半径多少能覆盖矩阵
好(毒)题(瘤)啊
不得不提 该题的坐标轴x向右 y轴向上 不是默认的坐标轴
考场考场反反复复看了题目好几遍 最开始还以为是贪心错了 看时间范围够把边长也都算了进去
时间消失法术 心态差点爆炸 我记住你了
显然 只要保证方阵四个顶点能被包括就可以了
不够就算边长也算也不会超时
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } #define db double ll xx,yy,d; ll x,y; db ans; inline db js(ll xx,ll yy,ll x,ll y) { return sqrt(1.0*abs(xx-x)*abs(xx-x)+1.0*abs(yy-y)*abs(yy-y)); } int main() { xx=read(),yy=read(),d=read(); x=read(),y=read(); //// cout<<js(xx,yy,x,y)<<endl; // for(ll i=0;i<=d;i++) ans=max(ans,js(xx+i,yy,x,y)); // for(ll i=0;i<=d;i++) ans=max(ans,js(xx,yy+i,x,y)); // for(ll i=0;i<=d;i++) ans=max(ans,js(xx+d,yy+i,x,y)); // for(ll i=0;i<=d;i++) ans=max(ans,js(xx+i,yy+d,x,y)); db tmp= max( max(js(xx+d,yy,x,y),js(xx,yy-d,x,y)) , max(js(xx,yy,x,y),js(xx+d,yy-d,x,y)) ); ans=max(ans,tmp); printf("%.3lf",ans); return 0; }
给你几个矩阵 观察规律
求第n个矩阵
考场看也是大模拟也跳了下
后来其他题目做差不多回来看只剩半小时 结束差几分钟才调出来
最后这题发现交了总时间还是比前面的人总时间成 排名没变化
观察得知 图形是三角形往左下和右下复制一遍重叠一部分
按意模拟 冷静
我的实现是按方阵copy记录 复制和被复制的两个矩阵的左上角位置 如果已经是 *就跳过防止覆盖
设三角形边长*数为len 去0列后 矩阵中点位置w
被复制 起始 stx sty
复制 起始 tmpx tmpy
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } const int N=1300; int n,w,md; int stx,sty,len; char a[N][N]; inline void cp(int x,int y,int len) { for(int i=0;i<len;i++) for(int j=0;j<2*len;j++) if(a[x+i][y+j]==' ') a[x+i][y+j]=a[stx+i][sty+j]; } int main() { n=read();w=(1<<n)+1; for(int i=1;i<=w;i++) for(int j=0;j<=2*w-1;j++) if(a[i][j]!='*') a[i][j]=' '; a[1][w]='*'; a[2][w-1];a[w][w-2]='*'; stx=1,sty=w-1;len=(1<<0)+1;//*长 for(int cs=1;cs<=n;cs++) { int tmpx=stx+len-1,tmpy=sty-len+1; cp(tmpx,tmpy,len); tmpx=stx+len-1,tmpy=w; cp(tmpx,tmpy,len); stx=1;sty=sty-len+1; len=((1<<cs)+1); } for(int i=1;i<=w;i++,puts("")) for(int j=0;j<=2*w-1;j++) cout<<a[i][j]; return 0; }
求n矩阵 对于其中某个位置 在每个矩阵中都是横纵的最小点 就标记
问有几个标记
看到第一反应二维线段树?
看见前缀和可以直接做
后来发现数据范围太小 就算直接写暴力枚举也能过
做的时候不知道为什么题目又没看清写了最大 改回最小又浪费了一段时间
写的时候 因为还是前缀和更好写就写了这个
上下前后左右都枚举下用遍前缀和 标记下是否为最小
统计答案
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } const int N=20,V=110; int n,x,y,mn,ans; int a[N][N][N],pd[N][N]; int main() { n=read();x=read(),y=read(); for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) pd[i][j]=1; for(int k=1;k<=n;k++) for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) a[k][i][j]=read(); for(int k=1;k<=n;k++) { for(int i=1;i<=x;i++) { mn=1e9+7; for(int j=1;j<=y;j++) { mn=min(mn,a[k][i][j]); if(a[k][i][j]>mn) pd[i][j]=0; } mn=1e9+7; for(int j=y;j>=1;j--) { mn=min(mn,a[k][i][j]); if(a[k][i][j]>mn) pd[i][j]=0; } } for(int j=1;j<=y;j++) { mn=1e9+7; for(int i=1;i<=x;i++) { mn=min(mn,a[k][i][j]); if(a[k][i][j]>mn) pd[i][j]=0; } mn=1e9+7; for(int i=x;i>=1;i--) { mn=min(mn,a[k][i][j]); if(a[k][i][j]>mn) pd[i][j]=0; } } } // for(int i=1;i<=x;i++,puts("")) // for(int j=1;j<=y;j++) // cout<<pd[i][j]<<" "; // for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) if(pd[i][j]) ans++; cout<<ans; return 0; }
一个红绿灯入口
给定一个状态 问是否矛盾
显然 对于每个入口来说是等价的
强制对其中单一入口考虑
分别考虑 当前路口直行有哪些矛盾 左行有哪些矛盾
左行有5种矛盾 直行有4种矛盾(考场 刚开始纠结左行和右口的左行是否有矛盾 后来交了下确实是有矛盾的)
再对于每个入口都这样做一遍判断有没有矛盾
这里对于每个入口做一遍的时候推荐用循环数组枚举每个入口
具体实现 请参考代码 0表示左行 1表示直行
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } char s[20]; inline int del(int x) { x=(x+24)%4; if(x==0) x+=4; return x; } inline int dw(int x,int y) { return (x-1)*2+y+1; } int main() { scanf("%s",s+1); for(int x=1;x<=4;x++) { if(s[dw(x,0)]=='G') { if(s[dw(del(x+1),0)]=='G'){cout<<"terrible";return 0;} if(s[dw(del(x+3),1)]=='G'){cout<<"terrible";return 0;} if(s[dw(del(x+3),0)]=='G'){cout<<"terrible";return 0;} if(s[dw(del(x+2),1)]=='G'){cout<<"terrible";return 0;} if(s[dw(del(x+2),0)]=='G'){cout<<"terrible";return 0;} } if(s[dw(x,1)]=='G') { if(s[dw(del(x+1),0)]=='G'){cout<<"terrible";return 0;} if(s[dw(del(x+1),0)]=='G'){cout<<"terrible";return 0;} if(s[dw(del(x+2),0)]=='G'){cout<<"terrible";return 0;} if(s[dw(del(x+3),1)]=='G'){cout<<"terrible";return 0;} } } cout<<"perfect"; return 0; }
给你120个菜 6个人
拿最多的人和最小的人都被淘汰
第一个人拿的量已给出
后每个人 先保证 不被淘汰 再保证淘汰的人最多 再保证自己拿的菜尽可能多
菜不必取完
因为第一个人的量a给出 第二个人就比较特殊 知道前面的人的值
考虑对a分类讨论
1 a>58 保证a肯定最大 得出a>58 第二个人尽量取 其他人全1
2 a==58 结果 a-1 2 1 1
3 (20<a&&a<58) 因为平分每个人20 该范围此时保证 a非最小 后面人尽量取a-1为非最大 保证最后个人取最小
4 a<=20
考场的时候这边不确定 考虑到答案可能有2种情况 因为菜不必取完 第二个人无论取多少 都不能保证不被淘汰
1 因为 第二人不能保证不被淘汰 所以保证可能性尽可能大 淘汰尽可能多 取a 后几个人也这么做 最后所有人都取a 所有人一起淘汰
按这样的推理 到最后个人 最后的人发现前面人取总肯定不会 和 前面三种的任意一种相同
那么 得知 a取值情况必为第四种 那么按推理 前面人都是a 最后个人按取的优先级必定把剩下的取完 淘汰的还是6个人
而第二的人想到前面的情况 也没法改变取值保证 淘汰人数6不变 取值变多
交上去发现 这种方法错了
2 因为 第二人不能保证不被淘汰 在第二人取尽可能多时保证淘汰人数5人 并且取值最大
交上去发现从从50到71分了 发现std是这种情况
考场上不知道为什么情况3的58打成28 又搞来搞查了半天 以为其他几个直接输出的结果有问题
最后每种情况都单独交了下 才查出来
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } const int N=120; int a; int b[N]; int main() { a=read(); if(a>58) cout<<N-a-4<<" "<<1<<" "<<1<<" "<<1<<" "<<1; //33 if(a==58) cout<<a-1<<" "<<2<<" "<<1<<" "<<1<<" "<<1; if(20<a&&a<58)//20-28 17 38 { int sum=a; for(int i=1;i<=5;i++) { b[i]=min(N-sum-(5-i),a-1); sum+=b[i]; } cout<<b[1]; for(int i=2;i<=5;i++) cout<<" "<<b[i]; } // if(a==20) cout<<20<<" "<<20<<" "<<20<<" "<<20<<" "<<20; // if(a<20) cout<<a<<" "<<a<<" "<<a<<" "<<a<<" "<<a; if(a<=20) cout<<N-a-4<<" "<<1<<" "<<1<<" "<<1<<" "<<1; //21 return 0; }
给个数列 每次按给定的位置取 最后输出取的次序 没取为0 被删掉为-1
如果对与一个还未取的位置如 果右边先被取了 左边再被取了 那么该位置被删掉
考虑按取的次序一个个处理
用个指针r 标记到当前情况最有边已经被取的位置
用树状数组处理被删的情况
对于当前取的位置w
1 r<=w 更新指针 更新答案
2 w<r
如果没被删 更新答案 用区间-1 更新w+1到r-1值
被删了跳过 或者更新答案
最后判断哪些位置没更新答案 并且值小于0 表示被删掉了 更新答案
考场 没找到自己树状数组模板 太久没写了 以防万一
随便找了板子 码风有点奇怪(考后改掉了)
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } const int N=1e4+10; int n,m,l,r,topa; int a[N],b[N],mp[N],tr[N],ans[N]; inline void add(int x,int v) { for(;x<=n;x+=x&(-x)) tr[x]+=v; } inline int ask(int x) { int ans=0; for(;x;x-=x&(-x)) ans+=tr[x]; return ans; } int main() { n=read();r=0;l=n+1; for(int i=1;i<=n;i++) a[i]=read(),mp[a[i]]=i; m=read(); for(int i=1;i<=m;i++) b[i]=read(); for(int i=1;i<=m;i++) { int w=mp[b[i]]; if(r<=w){r=w,ans[w]=++topa;continue;}//l=w-1; if(w<r) { if(ask(w)>=0) { ans[w]=++topa; add(w+1,-1);add(r,1); continue; } } } for(int i=1;i<=n;i++) if(!ans[i]) if(ask(i)<0) ans[i]=-1; for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }
给你个推箱子的地图 问最小步数 最小方案数 最小步数的最小字典序的方案
A掉的大佬tql
考场一看是到大模拟 果断跳
给你n个有编号的石子 每次只能取与编号与当前最大编号互质的石子 每次最多取n个
两个人取 问谁赢
emmmm 怎么说呢 原题的 只有唯一公约数 怎么看怎么奇怪
考场竟然一直没意识到就是 互质
知道意思后发现 最大的石子 除了n==1 其他情况是永远取不到的
那么能取的石子是固定
原题就转化为
1 给你一个数n 求小于等于n的与n互质的数x
2 给你个x个数的石子 每次限取m个 问谁赢
说来惭愧 考后写的时候 已经是完全忘记了欧拉函数的定义就是 问1 了 数论学得太不扎实了
线性筛oula函数就解决了问1
问2就是经典的取石子问题
1 x%(m+1)==0 那么无论先手取什么 后手总能 取到一个数 使此轮 两人加起来取到m+1 最后 后手胜
2 x%(m+1)!=0 那么先手可以肯定可以一定数 使得剩下来的数被(m+1)整除 转化为情况1 先手胜
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } ll n,m; const ll N=1e7+10; int vis[N],prime[N],top,oula[N]; void xxoula(ll mx) { vis[0]=vis[1]=1;//1为不是0为是 oula[0]=0;oula[1]=1; for(ll i=2;i<=mx;i++) { if(!vis[i]){prime[++top]=i;oula[i]=i-1;} for(ll j=1;j<=top&&prime[j]*i<=mx;j++) { vis[prime[j]*i]=1; if(!(i%prime[j])){oula[prime[j]*i]=oula[i]*prime[j];break;} oula[prime[j]*i]=oula[i]*(prime[j]-1); } } } int main() { xxoula(1e7); ll t=read(); while(t--) { n=read(),m=read(); if((oula[n])%(m+1)) printf("Alice\n"); else printf("Bob\n"); } return 0; }
给你两个串a,b 问b移位后和对a的最大贡献
ABCD组成一个环的顺序 后项对前一项 算1的贡献
感觉这场考试收获最大的就是这题了 重新理解了fft的优化
考虑对a预处理 直接把每个位置的值按ABCD循环加1变换
题目就转换成 b移位后和对a的最大贡献 位置上值相等算1贡献
接着就感觉特别熟悉
看到题目反应套用kmp的思想 处理信息
然后就发现这样的话信息极难维护
然后就想到了bitset
对ABCD各单独考虑贡献
该位置有 bitset中该值就为1
统计贡献就是a b的bitset 取&
太久没用 完全忘记了一次复杂度是n/32级别的 都是拿来卡常用的
考场以为复杂度是lgn级别 写完后喜获暴力的分数33分 复杂度 O(nn/32)
考场后看到了某个大佬发的链接 说用fft优化
大佬的代码太长了懒得仔细看了就自己写了
考虑原来复杂度的瓶颈是统计贡献n*n/32
对于 单一的一个值 假设m=6
统计贡献的情况是
相当上下两数列各位相乘
而对与多项式卷积来说
x+6+x+1维值的计算 相当于下图
那么将b数组前后翻转下就通过卷积就可以得到 该情况的贡献了
移动各个长度答案也就是卷积后的各个维度
用fft优化卷积 对于 单一的一个值 移动各个长度的的贡献就能求出来 复杂度nlgn
4个值总复杂度 O(4*nlgn)
注意每次fft的时候 初始化卷积的ab数组到记得初始到最小的2^x>n+m
另外题目中 m+移动的长度 是允许大于n的(允许两边都能空的赛马真的太奇怪了)
关于之前的暴力用的stl 如果stl用int实现的话 手写个ll的 除/64的常数
因为答案只要最优的一个移动位置就能计算了 缩小下移动枚举的量
用+rand()枚举移动位置 数据水点 机器快点 多交几遍运气好点说不定能过
bitset代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } const int N=1e5+10; int n,m,ans; char a[N],b[N]; bitset<N> bt1[6],bt2[6],bt3[6]; inline int del(int x) { x=x%4; if(x==0) x=4; return x; } int main() { n=read(),m=read(); scanf("%s",a+1);scanf("%s",b+1); for(int i=1;i<=n;i++) bt1[del(a[i]-'A'+2)][i]=1; for(int i=1;i<=m;i++) bt2[del(b[i]-'A'+1)][i]=1; for(int i=1;i<=n;i++) { int tmp=0; for(int k=1;k<=4;k++) { bt3[k]=bt1[k]&(bt2[k]<<i); tmp+=bt3[k].count(); } ans=max(ans,tmp); } cout<<ans; }
fft代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } const int N=3e5+10; int nn,mm,ans; char aa[N],bb[N]; int bt1[6][N],bt2[6][N],bt3[6][N]; inline int del(int x) { x=x%4; if(x==0) x=4; return x; } #define E complex<double> //N记得至少开两倍 const double pi=acos(-1); int n,m,l,r[N]; E a[N],b[N]; void fft(E *a,int f){ for(int i=0;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]);//交换位置 if为了避免重复交换变回原来的 for(int i=1;i<n;i<<=1){//当前合并两个长度为i的值的集合 E wn(cos(pi/i),f*sin(pi/i));//单位复根 将一个圆分成i部分 因为每次要合并i对下标为奇数和欧素的 for(int p=i<<1,j=0;j<n;j+=p){//当前要合并区间的第一个位置p E w(1,0); for(int k=0;k<i;k++,w*=wn){//要合并这个区间的第几个数 E x=a[j+k],y=w*a[j+k+i]; a[j+k]=x+y;a[j+k+i]=x-y; //算出带进去的两个值的结果 } } } } inline void cl() { n=nn,m=mm;l=0; for(int i=0;i<=N-10;i++) r[i]=0; for(int i=0;i<=N-10;i++) a[i]=b[i]=0; } int main() { nn=read(),mm=read(); scanf("%s",aa+1);scanf("%s",bb+1); for(int i=1;i<=nn;i++) bt1[del(aa[i]-'A'+2)][i]=1; for(int i=1;i<=mm;i++) bt2[del(bb[i]-'A'+1)][i]=1; for(int k=1;k<=4;k++)// { cl(); m+=n;for(n=1;n<=m;n<<=1)l++;//乘运算后的长度至少为n+m 运算要求为2的整次幂 for(int i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));//蝴蝶操作 for(int i=1;i<=nn;i++) a[i]=bt1[k][i]; for(int i=1;i<=mm;i++) b[i]=bt2[k][mm-i+1];; fft(a,1);fft(b,1);//转化为点值表达 for(int i=0;i<=n;i++)a[i]=a[i]*b[i];//O(n)运算 fft(a,-1);//转化为系数表达 for(int i=0;i<=m;i++) bt3[k][i]=(int)(a[i].real()/n+0.5);; } for(int i=0;i<=nn;i++) { int tmp=0; for(int k=1;k<=4;k++) tmp+=bt3[k][1+mm+i]; ans=max(ans,tmp); } cout<<ans; }