闵行建设机械网站,做网站一般把宽度做多少,南京小程序外包公司,常州网站建设哪家便宜通过答题情况的难度系数#xff1a;
签到#xff1a;A
简单#xff1a;BL
中等#xff1a;D
困难#xff1a;CM
极难#xff1a;KNO
A-和
算出n个数的和判断正负性即可#xff01;#xff01;#xff01;
发现很多同学的代码错误#xff1a;要么sum未赋初值
签到A
简单BL
中等D
困难CM
极难KNO
A-和
算出n个数的和判断正负性即可
发现很多同学的代码错误要么sum未赋初值要么数组大小定义太小导致数组溢出
#includebits/stdc.h
#define ll long long
#define pb push_back
#define endl \n
#define close ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N2e55;void solve(){int n;cinn;int sum0;while(n--){int x;cinx;sumx;}if(sum0) coutzeroendl;else if(sum0) coutpositiveendl;else coutnegativeendl;
}int main()
{close;int _1;while(_--){solve();}return 0;
}
B-积
直接计算n个数的积的话结果会导致爆long long判断积的正负性只需找到负数的个数如果出现了0结果即0否则如果出现负数的个数为偶数个结果即为正数否则即为负数
发现很多同学们的代码都直接算出n个数的积结果会导致爆long long和int故不能直接乘
#includebits/stdc.h
using namespace std;
int main(){int n,s1,x;cinn;while(n--){scanf(%d,x);if(x0) s*-1;if(!x) s*0;}puts(s0?positive:s?negative:zero);
}
C-马
直接DFS或者BFS即可
本来打算放这个基础搜索题目做个简单题但是发现很多同学不会搜索导致题目N过的人数也很少
BFS做法
#includebits/stdc.h
#define ll long long
#define pb push_back
#define endl \n
#define close ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N2e55;
int vis[55][55][55];
struct node{int x,y,z;
};void solve(){int n,m,h,t,stx,sty,stz;cinnmhstxstystzt;vectornoded(t);for(int i0;it;i){cind[i].xd[i].yd[i].z;}queuenodeq;q.push({stx,sty,stz});int ans0;while(!q.empty()){node uq.front();q.pop();if(vis[u.x][u.y][u.z]) continue;//coutu.x u.y u.zendl;vis[u.x][u.y][u.z]1;ans;for(int i0;it;i){int txu.xd[i].x,tyu.yd[i].y,tzu.zd[i].z;if((tx1txn)(ty1tym)(tz1tzh)){if(vis[tx][ty][tz]) continue;q.push({tx,ty,tz});}}}coutansendl;
}int main()
{close;int _1;//cin_;while(_--){solve();}return 0;
}
DFS做法
#includebits/stdc.h
using namespace std;
int a[31][3],ans,t,n,m,h;
bool f[51][51][51];
void dfs(int x,int y,int z){f[x][y][z]1,ans;for(int i1;it;i){int Xxa[i][0],Yya[i][1],Zza[i][2];if(X0XnY0Z0YmZh!f[X][Y][Z]) dfs(X,Y,Z);}
}
int main(){int x,y,z;cinnmhxyzt;for(int i1;it;i) cina[i][0]a[i][1]a[i][2];dfs(x,y,z),coutans;
}
D-数
由题意可知当n或m足够大的时候总有一个值在[1,10]这个区间上故可直接枚举大小更小的那个 集合作为二元有序对其中的一个数。例如当集合A中的3时集合B的大小为m(m3)要满足此二元有序对取集合m中大于3的数有m/3-1个小于等于3的数可直接循环枚举
发现一开始大部分同学都是直接O(n*m)暴力学校oj判题都是直接把整个程序跑完才判出TLE导致oj直接爆了一般的oj1s钟可以跑4e8次左右做题之前需先算出时间复杂度合不合适再考虑实现代码
#includebits/stdc.h
#define ll long long
#define pb push_back
#define endl \n
#define close ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N2e55;void solve(){ll n,m;cinnm;if(nm) swap(n,m);ll ans0;for(int i1;in;i){ansm/i-1;for(int j1;ji;j){if(i%j0) ans;}}coutansendl;
}int main()
{close;int _1;while(_--){solve();}return 0;
}
E-X限祖玛
在轮到玩家进行操作的时候肯定是只要能选上连续X个相同颜色的祖玛球最优故之间判断整个序列能操作的最大数maxmax偶数即后者赢否则前者赢
#include bits/stdc.husing namespace std;
const int N 1e5 10;
char a[N];int main() {int n, x;scanf(%d%d, n, x);scanf(%s, a 1);pairchar, int stk[N];int top 0;int cnt 0;for (int i 1; i n; ) {int j i;while (j n a[i] a[j]) j ;// [i, j - 1]int stklen 0;if (top stk[top].first a[i])stklen stk[top].second; int len j - i stklen;cnt len / x;stk[top] {a[i], len - len / x * x};if (top stk[top].first a[i]) {while (top stk[top].first a[i]) top --;}if (len % x ! 0)stk[top] {a[i], len % x}; i j;}if (cnt 1)puts(Fang is winner);elseputs(Liang is winner);
}
F-合成大魔棒
可发现所有树枝的价值小于等于1e9故合并的次数最大是1000次大于1000次最后合成得到的值为负数故不必考虑合成次数大于1000次的情况
在考虑x次合并的时候肯定是连续x1合并得到的最大值最优比如12345此时合并两次肯定是将后面连续3个数合并得到最大值12如果2和3合并4和5合并此时最大值9故无法保证此合并方案最优
#includebits/stdc.h
#define ll long long
using namespace std;
const int Max1e65;
int a[Max];
int pre[Max];
int ans0;
int main(){int n;cinn;for(int i1;in;i){cina[i];// scanf(%d,a[i]);pre[i]pre[i-1]a[i];}int maxa0;for(int i1;imin(1000,n);i){for(int j1;jn;j){int rji-1;if(rn) break;maxamax(maxa,pre[r]-pre[j-1]-(i-1)*(i-1)*(i-1));}}coutmaxaendl;
}
K-Syan的最大值 容易知道将全部数字进行与操作最优
这题过的人数很少出乎我们意料可能大部分同学没有接触过位运算学过计组之后可能会更清楚一些但是后面我们加上了样例解释还是很多同学不敢做其实第一位同学提交的代码思路完全正确只是数组开太小导致溢出不知为何放弃做这题了 一般看到评测结果运行错误大概率原因就是数组开小导致溢出
#include bits/stdc.husing namespace std;const int N1e55;
int a[N];
int main() {int n;cinn;int ans0;for(int i1;in;i){cina[i];ans|a[i];}coutansendl;
}
L-Syan的无限循环小数easy 如题意可知给出的a,b都在[1,5]这个区间可直接手动枚举知道1/32/34/35/3是无线循环小数
#include bits/stdc.husing namespace std;int main() {int a,b;cinab;if(a1b3) printf(YES\n);else if(a2b3) printf(YES\n);else if(a4b3) printf(YES\n);else if(a5b3) printf(YES\n);else printf(NO\n);
}
M-Syan的无限循环小数hard 这题不同于L给出的a,b都在[1,1000000000]这个区间不可直接手动枚举这时就需要知道这结论将分数化为最简分数后分母的全部因数除去1和其自身没有为2或5以外的数则该分数就不是无限循环小数否则为无限循环小数。
#include bits/stdc.husing namespace std;int main() {int a, b;cin a b;int g __gcd(a, b);a / g, b / g;if (a % b 0)puts(NO);else {while (b % 2 0)b / 2;while (b % 5 0)b / 5;puts(b 1 ? NO : YES);}
}
N-Syan的最大金币数 由题意可知玩家可以从起点无数次到达终点直到迷宫中可取的金币全部获得。从起点到达一个方格如若想到获得迷宫中的金币就必须再从此处到达终点走出迷宫例如样例 当走到31处时此时只能往41和32走但是32有障碍不能到达走到41也是死路故31处的金币无法获得
故只需判断从起点11往终点nm走从终点nm往起点11走如果这两个方向都能到达一个方格则此时的金币即可获得做两次BFS即可
#include bits/stdc.h
using namespace std;
#define sc(x) scanf(%d,x)
#define sl(x) scanf(%lld,x)
#define ll long long
#define pb push_back
const int Max1e65;
const int Mod998244353;
const int mod998244353;
bool vis[1005][1005];
struct node{int x,y;
};
int dir[2][2]{1,0,0,1};
bool flag[1005][1005];
int n;int m;
bool check(int x,int y){if(x1xny1yn) return true;return false;
}
void bfs(int start_x,int start_y){node start,next;queuenodeq;q.push({start_x,start_y});flag[start_x][start_y]true;while(!q.empty()){startq.front();q.pop();for(int i0;i2;i){next.xstart.xdir[i][0];next.ystart.ydir[i][1];if(check(next.x,next.y)!vis[next.x][next.y]!flag[next.x][next.y]){q.push(next);flag[next.x][next.y]true;}}}
}
bool flag1[1005][1005];
int dir1[2][2]{-1,0,0,-1};
void bfs1(int start_x,int start_y){node start,next;queuenodeq;q.push({start_x,start_y});flag1[start_x][start_y]true;while(!q.empty()){startq.front();q.pop();for(int i0;i2;i){next.xstart.xdir1[i][0];next.ystart.ydir1[i][1];if(check(next.x,next.y)!vis[next.x][next.y]!flag1[next.x][next.y]){q.push(next);flag1[next.x][next.y]true;}}}
}
int main(){cinnm;for(int i1;im;i){int x,y;cinxy;vis[x][y]true;}bfs(1,1);bfs1(n,n);int ans0;for(int i1;in;i){for(int j1;jn;j){if(i1j1) continue;if(flag[i][j]flag1[i][j]) ans;}}coutansendl;
}
O-Syan的三元组
这题提交的人也有很多直接O(n*n*n)直接暴力没有实现算明白时间复杂度
方法一 由D|a-b||b-c||a-c|可知当abc的时候距离最小其余情况 可知
L1|a-b| L1|b-c| L3|a-c|
D|a-b||b-c||a-c|L1L2L32L3
由D的表达式可知事实上决定D大小的关键时a和c的距离于是问题就可以简化为每次固定c找一个a使得L3|c-a|最小
#include bits/stdc.husing namespace std;const int N1e55;
int a[N],b[N],c[N];int main() {int n;cinn;for(int i1;in;i){cina[i];}for(int i1;in;i){cinb[i];}for(int i1;in;i){cinc[i];}sort(a1,a1n);sort(b1,b1n);sort(c1,c1n);int i1,j1,k1;long long ans1e18;while(injnkn){long long Dabs(a[i]-b[j])abs(b[j]-c[k])abs(a[i]-c[k]);ansmin(ans,D);if(a[i]b[j]a[i]c[k]) i;else if(b[j]a[i]b[j]c[k]) j;else k;}printf(%lld\n,ans);
}
方法二也可以固定中间b的值然后在ac数组中二分找到距离b最近的一个值
附上王逸鸣学长的代码
#includebits/stdc.h
#define ll long long
#define pb push_back
#define endl \n
#define close ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N2e55;void solve(){int n;cinn;setlls1,s2,s3;for(int i0;in;i){int x;cinx;s1.insert(x);}for(int i0;in;i){int x;cinx;s2.insert(x);}for(int i0;in;i){int x;cinx;s3.insert(x);}ll ans3e10;for(auto i:s1){auto js2.lower_bound(i),ks3.lower_bound(i);if(js2.end()||ks3.end()) continue;ansmin(ans,abs(i-*j)abs(i-*k)abs(*j-*k));}for(auto j:s2){auto is1.lower_bound(j),ks3.lower_bound(j);if(is1.end()||ks3.end()) continue;ansmin(ans,abs(*i-j)abs(*i-*k)abs(j-*k));}for(auto k:s3){auto js2.lower_bound(k),is1.lower_bound(k);if(js2.end()||is1.end()) continue;ansmin(ans,abs(*i-*j)abs(*i-k)abs(*j-k));}coutansendl;
}int main()
{close;int _1;while(_--){solve();}return 0;
}
P-Shiki的二元组
二分找第k个小的数check判断二分此时的mid前面有几个比其小的数
这题新生做之前可能还有很多同学没有接触二分
#include bits/stdc.h
using namespace std;
#define sc(x) scanf(%d,x)
#define sl(x) scanf(%lld,x)
#define ll long long
#define pb push_back
const int Max1e65;
const int Mod998244353;
ll a[Max],b[Max];
int main(){int n;sc(n);ll k;sl(k);for(int i1;in;i) sl(a[i]);for(int i1;in;i) sl(b[i]);sort(a1,a1n);sort(b1,b1n);ll l0,r1e18;ll x0;while(lr){ll mid(lr)/2;ll ans0;bool flagfalse;ll sum;for(int i1;in;i){// if(flag) break;if(a[i]*b[n]mid) ansn;else{int L1,Rn;while(LR){int Mid(LR)/2;if(a[i]*b[Mid]mid) RMid-1;else LMid1;}// coutmid L Rendl;ansR;}}if(ansk) lmid1;else rmid-1;}printf(%lld\n,l);
}
Q-被守护者的灵柩
直接判断t是否是s的子序列时间复杂度O(n*n)。循环t字符串找到t[1]第一次出现在s的位置然后依次找t[i]在t[i-1]出现在s的位置之后出现t[i]的第一个位置i0.
#includebits/stdc.h
#define ll long long
using namespace std;
const int Max1e65;
char a[Max],b[Max];
int main(){scanf(%s,a1);scanf(%s,b1);int lenstrlen(b1);int len_astrlen(a1);int j1;bool flagtrue;for(int i1;ilen;i){while(jlen_ab[i]!a[j]){j;}if(b[i]a[j]) j;else{flagfalse;break;}}if(flag) printf(yes\n);else printf(no\n);
}
T-命运尽头的垂泪者
模拟题按照题意模拟即可
#include bits/stdc.h
using namespace std;
#define sc(x) scanf(%d,x)
#define sl(x) scanf(%lld,x)
#define ll long long
#define pb push_back
const double esp1e-8;
const int Max1e65;
const int Mod998244353;
ll a[Max],b[Max];
queueintq;
int main(){int n;double h,m,k;cinnhmk;double Mm,Hh;double st_cao0;double cao0;for(int i1;in;i){cao-st_cao;string str;double cnt,dmg;cinstr;if(strPhysico) cindmg;else cincntdmg;if(strAnemo){//风m-0.5*cnt;m-0.2*M*dmg/H;}else if(strGeo){//岩m-0.5*cnt;m-0.2*M*dmg/H;}else if(strElectro||strPyro){//雷火if(strPyro) m-2*cnt;else m-cnt;m-0.2*M*dmg/H;int lenq.size();lenmin(len,2);m-0.2*6*k*len*M/H;while(!q.empty()) q.pop();}else if(strDendro){//草m-0.2*M*dmg/H;if(caoesp){caomax(cao,0.8*cnt);}else{cao0.8*cnt;st_cao1.6*cnt/(145*cnt);}}else if(strHydro){//水m-0.2*M*dmg/H;if(caoesp){cao-0.5*cnt;q.push(i);} }else if(strCryo){//冰}else if(strPhysico){//物理m-0.2*M*dmg/H;}}while(!q.empty()){if(n-q.front()6){m-0.2*M*4*k/H;;// h-4*k;}q.pop();}double summ*100.0/M;if(sumesp) printf(%.2lf%%\n,sum);else printf(win\n);
}
