企业门户网站怎么做,硬件开发面试题,网站域名不想实名认证,wordpress mysql 搭建正题
比赛链接:https://ac.nowcoder.com/acm/contest/1085#question 成绩 总结
除了那道积分数学其他还好
后面没有FFF题的题解 T1:小sun的假期T1:小sun的假期T1:小sun的假期
题目大意
长度为nnn的序列#xff0c;mmm个区间#xff0c;求最大的没有被任何区间覆盖的区间…正题
比赛链接:https://ac.nowcoder.com/acm/contest/1085#question 成绩 总结
除了那道积分数学其他还好
后面没有FFF题的题解 T1:小sun的假期T1:小sun的假期T1:小sun的假期
题目大意
长度为nnn的序列mmm个区间求最大的没有被任何区间覆盖的区间。
解题思路
我们将区间按照右端点从大到小枚举我们每次求从这个右端点往右可以扩展多少格。我们会发现只有右端点在它右边的会造成影响。而这个值就是这些区间最左的左端点。
codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e5100;
struct node{int l,r;
}a[N];
int n,m,ans,Min;
bool cMp(node x,node y)
{return x.ry.r;}
int main()
{scanf(%d%d,n,m);for(int i1;im;i)scanf(%d%d,a[i].l,a[i].r);sort(a1,a1m,cMp);Minn;for(int im;i1;i--){ansmax(ans,Min-a[i].r);Minmin(Min,a[i].l);}printf(%d,ans);
}T2:T2:T2:扫雷
题目大意
n∗mn*mn∗m的图有一些雷求每个位置旁边有多少雷
解题思路
暴力模拟不解释
codecodecode
#includecstdio
#includestring
#includeiostream
using namespace std;
int a[1002][1002],n,m;
int main()
{//freopen(mine.in,r,stdin);//freopen(mine.out,w,stdout);scanf(%d%d\n,n,m);string s;for (int x1;xn;x){getline(cin,s);for (int y0;ym;y){if (s[y]*){for (int ix-1;ix1;i)for (int jy-1;jy1;j){if (i0 j0 in jm a[i][j1]!23333)a[i][j1];}a[x][y1]23333;}}}for (int i1;in;i){for (int j1;jm;j)if (a[i][j]23333) printf(%c,*);else printf(%d,a[i][j]);printf(\n);}
}T3:T3:T3: 异或和
题目大意
nnn个数求出现次数为奇数的数异或和
解题思路
若出现次数为偶数两两异或抵消所以就是求所有数的异或和
codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int n,a,ans;
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a),ans^a ;printf(%d,ans);
}T4:T4:T4:解密
题目大意
加密方法是将字符串每个字符ccc变为(k1∗ck2)%26(k1*ck2)\%26(k1∗ck2)%26。给一串加密后的要求解密。
解题思路
暴力枚举解密后的然后匹配即可。
codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
ll k1,k2,big,a,n;
char s[1100];
int main()
{scanf(%lld%lld,k1,k2);scanf(%s,s1);nstrlen(s1);for(ll i1;in;i){big(s[i]Z);as[i]-(s[i]Z?A:a);for(ll j0;j25;j)if((j*k1k2)%26lla){printf(%c,j(big?A:a));break;}}
}T5:T5:T5:图的遍历
题目大意
一张无向图每次走两步求至少增加多少条边可以遍历完整张图
解题思路
考虑贪心我们先考虑现在的图联通我们可以将图分为偶点和奇点。偶点就是可以遍历到的奇点就是不能的我们发现若有奇点此时答案为1否则为0.
那若是分为若干个联通块呢我们会发现联通块之间无论如何连接并不会影响答案所以直接暴力连接即可。
codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e5100;
struct node{int to,next;
}a[N*2];
int n,m,ls[N],tot,ans,z,last;
bool v[N][2];
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs(int x,int k)
{if(v[x][k]) return;v[x][k]1;for(int ils[x];i;ia[i].next)dfs(a[i].to,k^1);
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}last1;dfs(1,1);for(int i2;in;i)if(!v[i][0]!v[i][1]){ans;dfs(i,1);addl(last,i);lasti;}memset(v,0,sizeof(v));dfs(1,1);for(int i1;in;i)if(!v[i][1]){ans;break;}printf(%d,ansz);
}T7:T7:T7:区间求和
题目大意
一个序列每次询问一个区间[l,r][l,r][l,r] ∑ilrai∗num(ai)\sum_{il}^r a_i*num(a_i)il∑rai∗num(ai) num(ai)num(a_i)num(ai)表示这个区间中aia_iai的数量
解题思路
显然的莫队不解释。
codecodecode
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
%:pragma GCC optimize(-fgcse)
%:pragma GCC optimize(-fgcse-lm)
%:pragma GCC optimize(-fipa-sra)
%:pragma GCC optimize(-ftree-pre)
%:pragma GCC optimize(-ftree-vrp)
%:pragma GCC optimize(-fpeephole2)
%:pragma GCC optimize(-ffast-math)
%:pragma GCC optimize(-fsched-spec)
%:pragma GCC optimize(unroll-loops)
%:pragma GCC optimize(-falign-jumps)
%:pragma GCC optimize(-falign-loops)
%:pragma GCC optimize(-falign-labels)
%:pragma GCC optimize(-fdevirtualize)
%:pragma GCC optimize(-fcaller-saves)
%:pragma GCC optimize(-fcrossjumping)
%:pragma GCC optimize(-fthread-jumps)
%:pragma GCC optimize(-funroll-loops)
%:pragma GCC optimize(-fwhole-program)
%:pragma GCC optimize(-freorder-blocks)
%:pragma GCC optimize(-fschedule-insns)
%:pragma GCC optimize(inline-functions)
%:pragma GCC optimize(-ftree-tail-merge)
%:pragma GCC optimize(-fschedule-insns2)
%:pragma GCC optimize(-fstrict-aliasing)
%:pragma GCC optimize(-fstrict-overflow)
%:pragma GCC optimize(-falign-functions)
%:pragma GCC optimize(-fcse-skip-blocks)
%:pragma GCC optimize(-fcse-follow-jumps)
%:pragma GCC optimize(-fsched-interblock)
%:pragma GCC optimize(-fpartial-inlining)
%:pragma GCC optimize(no-stack-protector)
%:pragma GCC optimize(-freorder-functions)
%:pragma GCC optimize(-findirect-inlining)
%:pragma GCC optimize(-fhoist-adjacent-loads)
%:pragma GCC optimize(-frerun-cse-after-loop)
%:pragma GCC optimize(inline-small-functions)
%:pragma GCC optimize(-finline-small-functions)
%:pragma GCC optimize(-ftree-switch-conversion)
%:pragma GCC optimize(-foptimize-sibling-calls)
%:pragma GCC optimize(-fexpensive-optimizations)
%:pragma GCC optimize(-funsafe-loop-optimizations)
%:pragma GCC optimize(inline-functions-called-once)
%:pragma GCC optimize(-fdelete-null-pointer-checks)
#includecstdio
#includecmath
#includealgorithm
#includecctype
#define ll long long
using namespace std;
const int N1e5100;
struct node{ll l,r,id,pos;
}a[N];
ll n,m,w[N],l,r,now,id[N],t;
ll cnt[N],ans[N];
bool operator (node x, node y) {return x.posy.pos||(x.posy.posx.ry.r);
}
inline ll read() {ll x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
void print(ll x){if (x9) print(x/10); putchar(x%1048); return;
}
void add(ll x)
{now(2*cnt[x]1)*x;cnt[x];}
void del(ll x)
{now-(2*cnt[x]-1)*x;cnt[x]--;}
int main()
{nread();mread();tsqrt(n);for(ll i1;in;i)w[i]read();for(ll i1;im;i)a[i].lread(),a[i].rread(),a[i].idi,a[i].pos(a[i].l-1)/t1;sort(a1,a1m);l1,r0;for(ll i1;im;i){while(la[i].l) add(w[--l]);while(ra[i].r) add(w[r]);while(la[i].l) del(w[l]);while(ra[i].r) del(w[r--]);ans[a[i].id]now;}for(ll i1;im;i)print(ans[i]),putchar(\n);
}T8:T8:T8:取球游戏
题目大意
ccc种颜色抽随机nnn个(每种颜色等概率)求最后是mmm种颜色个数为奇数的概率
解题思路
我们设fi,jf_{i,j}fi,j表示抽到第iii个颜色为jjj个的方案数有 fi,j∗jcgt;fi1,j−1f_{i,j}*\frac{j}{c}\ \ \ gt;\ \ \ f_{i1,j-1}fi,j∗cj fi1,j−1 fi,j∗c−jcgt;fi1,j1f_{i,j}*\frac{c-j}{c}\ \ \ gt;\ \ \ f_{i1,j1}fi,j∗cc−j fi1,j1
这个可以用矩阵乘法优化即可。
codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll Size111;
ll n,c,m;
double a[Size][Size],ans[Size][Size],C[Size][Size];
void mulself() {for(ll i0;ic;i)for(ll j0;jc;j)C[i][j]0;for(ll i0;ic;i)for(ll j0;jc;j)for(ll k0;kc;k)C[i][j]a[i][k]*a[k][j];for(ll i0;ic;i)for(ll j0;jc;j)a[i][j]C[i][j];
}
void mul(){for(ll i0;ic;i)for(ll j0;jc;j)C[i][j]0;for(ll i0;ic;i)for(ll j0;jc;j)for(ll k0;kc;k)C[i][j]a[i][k]*ans[k][j];for(ll i0;ic;i)for(ll j0;jc;j)ans[i][j]C[i][j];
}
void ksm(ll b) {while(b){if(b1) mul();mulself();b1;}
}
int main()
{scanf(%lld%lld%lld,c,n,m);a[0][1]1;a[c][c-1]1;for(ll i1;ic;i)a[i][i1](double)(c-i)/c,a[i][i-1](double)i/c;for(ll i0;ic;i)ans[i][i]1;ksm(n);printf(%.3lf,ans[0][m]);
}T9:T9:T9:坐电梯
题目大意
mmm个请求楼层优先走到最高层的求要多久才接到kkk楼
解题思路
在所有读入的数中求一个最大值hhh然后答案就是2h−1−k2h-1-k2h−1−k
codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int n,k,maxs,num;
int main()
{scanf(%d%d,n,k);maxsk;for(int i1;in;i){scanf(%d,num);maxsmax(maxs,num);}printf(%d,maxs-1maxs-k);
}T10:T10:T10:技术
题目大意
一序列中有的空缺了求有多少种填数方式使得这是一个单调不降序列
解题思路
我们发现若一段连续的空缺lll且这段空缺中可以填的数的个数为kkk那么这段空缺的方案数就是Ckl−1l−1C^{l-1}_{kl-1}Ckl−1l−1(插板法)。然后计算方案数即可。
codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll XJQ1e97,N2e6100;
ll num[N],n,ans1,last1000,z,inv[N];
ll C(ll n,ll m)
{if(nm) return 0;ll ans1;for(ll i1;im;i)ansans*((n-i1)%XJQ)%XJQ*inv[i]%XJQ;return ans;
}
int main()
{scanf(%lld,n);inv[1]1;for(ll i2;iN;i)inv[i]inv[XJQ%i]*(XJQ-XJQ/i)%XJQ;for(ll i1;in;i){scanf(%lld,num[i]);if(num[i]){(ans*C(last-num[i]i-z-1,i-z-1))%XJQ;lastnum[i];zi;}}(ans*C(last-1n-z,n-z))%XJQ;printf(%lld,ans);
}
