族蚂建站,济南做网站多钱,长沙企业网站开发微联讯点,1688网站简介前言#xff1a; 前天晚上写的一场牛客上比赛#xff0c;虽然只写出了三道#xff0c;但比起之前的成绩感觉自己明显有了一点进步了#xff0c;继续努力吧#xff0c;
正文#xff1a; 链接#xff1a;牛客小白月赛97_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞…前言 前天晚上写的一场牛客上比赛虽然只写出了三道但比起之前的成绩感觉自己明显有了一点进步了继续努力吧
正文 链接牛客小白月赛97_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
A 三角形 #includebits/stdc.h
using namespace std;
int a[100005];
int main(){int n;cinn;for(int i1;in;i){cina[i];}sort(a1,an1);int flag0;for(int i1;in-2;i){if(a[i]a[i1]a[i1]a[i2])flag1;}if(flag)coutYESendl;else coutNOendl;return 0;
}
签到题我是排序后看看有没有三个连续相等的数字。更好的做法应该是用桶排看看有没有出现次数超过三的数字其实都差不多。
B 好数组 #include bits/stdc.h
using namespace std;int main()
{int n,x,f1,a0;cinn;for(int i0;in;i){cinx;if(x0) f0;}if(f0) coutNOendl;else coutYESendl;return 0;
}
又一道签到题只要包含0就不是好数组。
C 前缀平方和序列 #includebits/stdc.h
using namespace std;
int n,x;
const long long mod1e97;
typedef long long ll;
ll quick(ll a,ll b){ll res1;while(b){if(b%2)resres*a%mod;aa*a%mod;b/2;}return res;
}
ll f[10005];
void init(){f[0]1;for(int i1;i10005;i){f[i]f[i-1]*i%mod;}
}
ll inv(ll x){return quick(x,mod-2)%mod;
}
int main(){init();cinnx;ll cnt(ll)sqrt(x);if(cntn){cout0endl;return 0;}//coutf[cnt] inv(f[n]) inv(f[cnt-n])endl;ll ans(f[cnt]*((inv(f[n])%mod*inv(f[cnt-n]%mod))%mod))%mod;coutansendl;return 0;
}
预处理阶乘和逆元费马小定理然后求组合数注意要开long long,并且在计算过程中一定要时时取模否则会暴。
D 走一个大整数迷宫 #includebits/stdc.h
using namespace std;
typedef long long ll;
int a[15][15],b[15][15];
bool book[15][15][10005];
ll n,m,p;
ll quick(ll a,ll b,ll mod){ll res1;while(b){if(b%2)resres*a%mod;aa*a%mod;b/2;}return res;
}
int ne[4][2]{{0,-1},{0,1},{1,0},{-1,0}};
typedef struct stu{int x;int y;int z;int c;
}node;
int ans1e97;
queuenode q;
void bfs(int x,int y,int z,int c){node k{x,y,z,c};q.push(k);while(!q.empty()){kq.front();q.pop();if(book[k.x][k.y][k.c%(p-1)])continue;book[k.x][k.y][k.c%(p-1)]true; if(k.xnk.ymk.c%(p-1)0){ansmin(k.z,ans);break;}for(int i0;i4;i){int nxk.xne[i][0];int nyk.yne[i][1];if(nx1nxnny1nym){//coutnx ny k.z1 k.ca[nx][ny]endl;int cc(k.ca[nx][ny])%(p-1);node l{nx,ny,k.z1,cc};q.push(l);}}}
}
int main(){cinnmp;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}for(int i1;in;i){for(int j1;jm;j){cinb[i][j];}}bfs(1,1,0,a[1][1]);if(ans1e97)cout-1;else coutans;return 0;
}
首先咱们先看c的表式方式 首先我们要知道我们最后要求的数是对p-1取模的数我们完全可以在输入的时候就将图上的数直接取模。然后我们再对Cij进行简化很容易发现对p-1取模一直都为1。
由于
可以将展开为
然后用bfs跑分层图第一、二维为x,y第三维为走到这个点时的计数器上的数对p-1取模的结果这样能避免多走但计数器取模后一样的情况。具体写法见上。如果能搜到答案就输出不然就输出-1.
E 前缀和前缀最大值 #includebits/stdc.h
using namespace std;
int a[100005];
int pre[100005],sum[100005][101];
int main(){int n;cinn;for(int i1;in;i){cina[i];if(a[i]0)pre[i]pre[i-1]-a[i];else pre[i]pre[i-1];for(int j1;j100;j){sum[i][j]sum[i-1][j](a[i]j);}}int q;cinq;for(int i1;iq;i){int l,r,tmp0;cinlr;int tpre[r]-pre[l-1];int res0;int cnt0;for(int j1;j100;j){int ksum[r][j]-sum[l-1][j];if(k!0){if(k*jrest){cnt(t-res)/j;break;}else cntk;resk*j;//cout t cnt resendl;}}coutcnt1endl;}return 0;
}
这题是我看了他发的答案才写出来的咱们首先得要知道他的A类价值数是连续的可能又相等的值但一定是一个区间内的所有数考虑 A 类价值最小的方案是从小到大排序序列 a。然后进行n 次将序列 a 的最后一个数字移动到最前面。会发现这样操作序列 a 的 A 类价值是单调不减的并且每次只移动一个数增量只可能是0 或者 1。所以可以得出一个结论A 类价值是连续的。所以我们最后只需要求他的最大A的值r和最小A值l答案就为r-l1。上界即为正数个数下界就是从小到大排的第一个正数前缀到尾的距离。
F parent 树上启发式合并待补 看着好高级。
后记 我还是太菜了。
