濮阳网站建设 公司名字,wordpress文章模板编辑,贵港网站seo,工信部网站备案被注销A.牛牛的mex n,q≤105,0≤ain且ai互不相同n,q≤10 ^5,0≤a in 且 a_i互不相同n,q≤105,0≤ain且ai互不相同 后面两个条件非常重要#xff0c;通过后面两个条件将问题转化为一个区间内最小未出现的自然数就等于不在这个区间内最小出现的自然数对于区间[l,r][l,r]…A.牛牛的mex
n,q≤105,0≤ain且ai互不相同n,q≤10 ^5,0≤a in 且 a_i互不相同n,q≤105,0≤ain且ai互不相同 后面两个条件非常重要通过后面两个条件将问题转化为一个区间内最小未出现的自然数就等于不在这个区间内最小出现的自然数对于区间[l,r][l,r][l,r]只需要算出[1,l−1]和[r1,n][1,l-1]和[r1,n][1,l−1]和[r1,n]区间最小出现的自然数即可。直接预处理前缀后缀注意边界由于0≤ain0\leq a_in0≤ain只需让pre[0]suc[n1]n即可
//O(n)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
const int N100010;
int a[N],pre[N],suc[N];
int n,q;
int main()
{cinnq;pre[0]suc[n1]n;for(int i1;in;i) cina[i];for(int i1;in;i) pre[i]min(pre[i-1],a[i]);for(int in;i;i--) suc[i]min(suc[i1],a[i]);while(q--){int l,r;cinlr;coutmin(pre[l-1],suc[r1])\n;}return 0; }由于日常眼瞎非常容易看不见上述重要条件因此不如上优雅暴力——莫队
//O(nsqrt(n))
#includeiostream
#includecmath
#includealgorithm
using namespace std;
const int N100010;
int cnt[N],sz,pos[N];
struct node
{int l,r,id;bool operator(const node o) const {if(pos[l]pos[o.l]) return ro.r;else return pos[l]pos[o.l];}
}q[N];
int a[N],n,m;
int ans[N],res;
void add(int k)
{cnt[a[k]];while(cnt[res]) res;
}
void sub(int k)
{cnt[a[k]]--;if(!cnt[a[k]]a[k]res) resa[k];
}
int main()
{cinnm;szsqrt(n);for(int i1;in;i){cina[i];pos[i]i/sz;}for(int i1;im;i){cinq[i].lq[i].r;q[i].idi;}sort(q1,q1m);int l1,r0;for(int i1;im;i){while(lq[i].l) sub(l);while(lq[i].l) add(--l);while(rq[i].r) add(r);while(rq[i].r) sub(r--);ans[q[i].id]res;}for(int i1;im;i) coutans[i]\n;return 0;
}B.牛牛的算术
发现当 n≥199999n \geq 199999n≥199999 时答案必为000。 于是我们只需要预处理 n199999n 199999n199999的答案即可。 预处理前缀和和前缀积直接算答案。
#includestring
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N200010;
const ll mod199999;
ll s1[N],s2[N];
string p199999;
void init()
{for(int i1;imod;i)s1[i](s1[i-1]1ll*i*(i1)/2*i%mod)%mod;s2[0]1;for(int i1;imod;i)s2[i]s2[i-1]*i%mod*s1[i]%mod;
}
int main()
{int T1;init();cinT;while(T--){string a;cina;if(a.size()6||a.size()6ap){cout0\n;continue;}reverse(a.begin(),a.end());int base1,n0;for(auto t:a){nbase*int(t-0);base*10;}couts2[n]\n;}return 0; }C.牛牛的无向图
不难看出所求就是通过长度不大于L的边相互可达点的数量 对于大于L的边我们可以看作无这条边我们用并查集维护连通块点的数量。 把询问和边放在一起排序然后处理即可
#includecstdio
#includestring
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N100010,M500010;
struct node
{int op;int a,b,w;int id;bool operator(const node o)const {if(wo.w) return opo.op;return wo.w;}
}e[2*M];
int n,m;
int q[M],k;
ll ans[M],now;
unsigned int SA, SB, SC; int LIM;
unsigned int rng61(){SA ^ SA 16;SA ^ SA 5;SA ^ SA 1;unsigned int t SA;SA SB;SB SC;SC ^ t ^ SA;return SC;
}
void gen(){scanf(%d%d%d%u%u%u%d, n, m, k, SA, SB, SC, LIM);for(int i 1; i m; i){e[i].a rng61() % n 1;e[i].b rng61() % n 1;e[i].w rng61() % LIM;}for(int i 1; i k; i){q[i] rng61() % LIM;}
}
int p[N],sz[N];
int find(int x)
{return xp[x]?x:p[x]find(p[x]);
}
int main()
{gen();for(int i1;im;i) e[i].op1;for(int i1;in;i) p[i]i,sz[i]1;for(int i1;ik;i){e[im].op2;e[im].wq[i];e[im].idi;}sort(e1,e1mk);for(int i1;imk;i){if(e[i].op1){int pafind(e[i].a),pbfind(e[i].b);if(pa!pb){p[pa]pb;now1ll*sz[pa]*sz[pb];sz[pb]sz[pa];}}elseans[e[i].id]now;}ll res0;for(int i1;ik;i) res^ans[i];coutres\n;return 0;
}牛客网的题目感觉挺不错的但是评测机就很让人落泪啊 要加油哦~
