临夏州住房与建设局官方网站/旺道智能seo系统

通过答题情况的难度系数：

签到：A

简单：BL

中等：D

困难：CM

极难：KNO

A-和

算出n个数的和判断正负性即可！！！

发现很多同学的代码错误：要么sum未赋初值，要么数组大小定义太小导致数组溢出！！！

#include<bits/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 N=2e5+5;void solve(){int n;cin>>n;int sum=0;while(n--){int x;cin>>x;sum+=x;}if(sum==0) cout<<"zero"<<endl;else if(sum>0) cout<<"positive"<<endl;else cout<<"negative"<<endl;
}int main()
{close;int _=1;while(_--){solve();}return 0;
}

B-积

直接计算n个数的积的话，结果会导致爆long long，判断积的正负性只需找到负数的个数，如果出现了0，结果即0；否则如果出现负数的个数为偶数个，结果即为正数，否则即为负数！！

发现很多同学们的代码都直接算出n个数的积，结果会导致爆long long和int，故不能直接乘！

#include<bits/stdc++.h>
using namespace std;
int main(){int n,s=1,x;cin>>n;while(n--){scanf("%d",&x);if(x<0) s*=-1;if(!x) s*=0;}puts(s>0?"positive":s?"negative":"zero");
}

C-马

直接DFS或者BFS即可！！！

本来打算放这个基础搜索题目做个简单题，但是发现很多同学不会搜索，导致题目N过的人数也很少！！！

BFS做法：

#include<bits/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 N=2e5+5;
int vis[55][55][55];
struct node{int x,y,z;
};void solve(){int n,m,h,t,stx,sty,stz;cin>>n>>m>>h>>stx>>sty>>stz>>t;vector<node>d(t);for(int i=0;i<t;i++){cin>>d[i].x>>d[i].y>>d[i].z;}queue<node>q;q.push({stx,sty,stz});int ans=0;while(!q.empty()){node u=q.front();q.pop();if(vis[u.x][u.y][u.z]) continue;//cout<<u.x<<" "<<u.y<<" "<<u.z<<endl;vis[u.x][u.y][u.z]=1;ans++;for(int i=0;i<t;i++){int tx=u.x+d[i].x,ty=u.y+d[i].y,tz=u.z+d[i].z;if((tx>=1&&tx<=n)&&(ty>=1&&ty<=m)&&(tz>=1&&tz<=h)){if(vis[tx][ty][tz]) continue;q.push({tx,ty,tz});}}}cout<<ans<<endl;
}int main()
{close;int _=1;//cin>>_;while(_--){solve();}return 0;
}

DFS做法：

#include<bits/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 i=1;i<=t;i++){int X=x+a[i][0],Y=y+a[i][1],Z=z+a[i][2];if(X>0&&X<=n&&Y>0&&Z>0&&Y<=m&&Z<=h&&!f[X][Y][Z]) dfs(X,Y,Z);}
}
int main(){int x,y,z;cin>>n>>m>>h>>x>>y>>z>>t;for(int i=1;i<=t;i++) cin>>a[i][0]>>a[i][1]>>a[i][2];dfs(x,y,z),cout<<ans;
}

D-数 

由题意可知，当n或m足够大的时候，总有一个值在[1,10]这个区间上，故可直接枚举大小更小的那个 集合作为二元有序对其中的一个数。例如：当集合A中的3时，集合B的大小为m(m>3)，要满足此二元有序对，取集合m中大于3的数有m/3-1个，小于等于3的数可直接循环枚举！！！

发现一开始大部分同学都是直接O(n*m)暴力，学校oj判题都是直接把整个程序跑完，才判出TLE，导致oj直接爆了！！！一般的oj，1s钟可以跑4e8次左右，做题之前需先算出时间复杂度合不合适，再考虑实现代码！！！

#include<bits/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 N=2e5+5;void solve(){ll n,m;cin>>n>>m;if(n>m) swap(n,m);ll ans=0;for(int i=1;i<=n;i++){ans+=m/i-1;for(int j=1;j<=i;j++){if(i%j==0) ans++;}}cout<<ans<<endl;
}int main()
{close;int _=1;while(_--){solve();}return 0;
}

E-X限祖玛

在轮到玩家进行操作的时候，肯定是只要能选上连续X个相同颜色的祖玛球最优，故之间判断整个序列能操作的最大数max，max偶数即后者赢，否则前者赢！

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
char a[N];int main() {int n, x;scanf("%d%d", &n, &x);scanf("%s", a + 1);pair<char, 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次合并的时候，肯定是连续x+1合并得到的最大值最优，比如：1，2，3，4，5；此时合并两次，肯定是将后面连续3个数合并得到最大值12，如果2和3合并，4和5合并，此时最大值9，故无法保证此合并方案最优！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=1e6+5;
int a[Max];
int pre[Max];
int ans=0;
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];// scanf("%d",&a[i]);pre[i]=pre[i-1]+a[i];}int maxa=0;for(int i=1;i<=min(1000,n);i++){for(int j=1;j<=n;j++){int r=j+i-1;if(r>n) break;maxa=max(maxa,pre[r]-pre[j-1]-(i-1)*(i-1)*(i-1));}}cout<<maxa<<endl;
}

K-Syan的最大值

        容易知道将全部数字进行与操作最优！

这题过的人数很少，出乎我们意料，可能大部分同学没有接触过位运算，学过计组之后可能会更清楚一些，但是后面我们加上了样例解释，还是很多同学不敢做，其实第一位同学提交的代码思路完全正确，只是数组开太小导致溢出，不知为何放弃做这题了 ！一般看到评测结果运行错误，大概率原因就是数组开小导致溢出！

#include <bits/stdc++.h>using namespace std;const int N=1e5+5;
int a[N];
int main() {int n;cin>>n;int ans=0;for(int i=1;i<=n;i++){cin>>a[i];ans|=a[i];}cout<<ans<<endl;
}

L-Syan的无限循环小数（easy）

        如题意可知，给出的a,b都在[1,5]这个区间，可直接手动枚举知道1/3，2/3，4/3，5/3是无线循环小数！ 

#include <bits/stdc++.h>using namespace std;int main() {int a,b;cin>>a>>b;if(a==1&&b==3) printf("YES\n");else if(a==2&&b==3) printf("YES\n");else if(a==4&&b==3) printf("YES\n");else if(a==5&&b==3) printf("YES\n");else printf("NO\n");
}

M-Syan的无限循环小数（hard）

        这题不同于L，给出的a,b都在[1,1000000000]这个区间，不可直接手动枚举，这时就需要知道这结论：将分数化为最简分数后，分母的全部因数（除去1和其自身）没有为2或5以外的数，则该分数就不是无限循环小数；否则为无限循环小数。

#include <bits/stdc++.h>using 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的最大金币数

        由题意可知，玩家可以从起点无数次到达终点，直到迷宫中可取的金币全部获得。从起点到达一个方格，如若想到获得迷宫中的金币，就必须再从此处到达终点，走出迷宫，例如样例

 当走到（3，1）处时，此时只能往（4，1）和（3，2）走，但是（3，2）有障碍不能到达，走到（4，1）也是死路，故（3，1）处的金币无法获得！！！

故只需判断从起点（1，1）往终点（n，m）走，从终点（n，m）往起点（1，1）走，如果这两个方向都能到达一个方格，则此时的金币即可获得，做两次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 Max=1e6+5;
const int Mod=998244353;
const int mod=998244353;
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(x>=1&&x<=n&&y>=1&&y<=n) return true;return false;
}
void bfs(int start_x,int start_y){node start,next;queue<node>q;q.push({start_x,start_y});flag[start_x][start_y]=true;while(!q.empty()){start=q.front();q.pop();for(int i=0;i<2;i++){next.x=start.x+dir[i][0];next.y=start.y+dir[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;queue<node>q;q.push({start_x,start_y});flag1[start_x][start_y]=true;while(!q.empty()){start=q.front();q.pop();for(int i=0;i<2;i++){next.x=start.x+dir1[i][0];next.y=start.y+dir1[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(){cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;vis[x][y]=true;}bfs(1,1);bfs1(n,n);int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==1&&j==1) continue;if(flag[i][j]&&flag1[i][j]) ans++;}}cout<<ans<<endl;
}

O-Syan的三元组

这题提交的人也有很多直接O(n*n*n)直接暴力，没有实现算明白时间复杂度！！！

方法一： 由D=|a-b|+|b-c|+|a-c|可知，当a=b=c的时候，距离最小，其余情况：

 可知

L1=|a-b|；   L1=|b-c|；   L3=|a-c|；

D=|a-b|+|b-c|+|a-c|=L1+L2+L3=2L3；

由D的表达式可知，事实上决定D大小的关键时a和c的距离，于是问题就可以简化为每次固定c找一个a，使得L3=|c-a|最小；

#include <bits/stdc++.h>using namespace std;const int N=1e5+5;
int a[N],b[N],c[N];int main() {int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];}for(int i=1;i<=n;i++){cin>>c[i];}sort(a+1,a+1+n);sort(b+1,b+1+n);sort(c+1,c+1+n);int i=1,j=1,k=1;long long ans=1e18;while(i<=n&&j<=n&&k<=n){long long D=abs(a[i]-b[j])+abs(b[j]-c[k])+abs(a[i]-c[k]);ans=min(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的值，然后在a，c数组中二分找到距离b最近的一个值！！！

（附上王逸鸣学长的代码）

#include<bits/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 N=2e5+5;void solve(){int n;cin>>n;set<ll>s1,s2,s3;for(int i=0;i<n;i++){int x;cin>>x;s1.insert(x);}for(int i=0;i<n;i++){int x;cin>>x;s2.insert(x);}for(int i=0;i<n;i++){int x;cin>>x;s3.insert(x);}ll ans=3e10;for(auto i:s1){auto j=s2.lower_bound(i),k=s3.lower_bound(i);if(j==s2.end()||k==s3.end()) continue;ans=min(ans,abs(i-*j)+abs(i-*k)+abs(*j-*k));}for(auto j:s2){auto i=s1.lower_bound(j),k=s3.lower_bound(j);if(i==s1.end()||k==s3.end()) continue;ans=min(ans,abs(*i-j)+abs(*i-*k)+abs(j-*k));}for(auto k:s3){auto j=s2.lower_bound(k),i=s1.lower_bound(k);if(j==s2.end()||i==s1.end()) continue;ans=min(ans,abs(*i-*j)+abs(*i-k)+abs(*j-k));}cout<<ans<<endl;
}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 Max=1e6+5;
const int Mod=998244353;
ll a[Max],b[Max];
int main(){int n;sc(n);ll k;sl(k);for(int i=1;i<=n;i++) sl(a[i]);for(int i=1;i<=n;i++) sl(b[i]);sort(a+1,a+1+n);sort(b+1,b+1+n);ll l=0,r=1e18;ll x=0;while(l<=r){ll mid=(l+r)/2;ll ans=0;bool flag=false;ll sum;for(int i=1;i<=n;i++){// if(flag) break;if(a[i]*b[n]<=mid) ans+=n;else{int L=1,R=n;while(L<=R){int Mid=(L+R)/2;if(a[i]*b[Mid]>mid) R=Mid-1;else L=Mid+1;}// cout<<mid<<' '<<L<<' '<<R<<endl;ans+=R;}}if(ans<k) l=mid+1;else r=mid-1;}printf("%lld\n",l);
}

Q-被守护者的灵柩

直接判断t是否是s的子序列，时间复杂度O(n*n)。循环t字符串，找到t[1]第一次出现在s的位置，然后依次找t[i]（在t[i-1]出现在s的位置之后出现t[i]的第一个位置，i>0）.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=1e6+5;
char a[Max],b[Max];
int main(){scanf("%s",a+1);scanf("%s",b+1);int len=strlen(b+1);int len_a=strlen(a+1);int j=1;bool flag=true;for(int i=1;i<=len;i++){while(j<=len_a&&b[i]!=a[j]){j++;}if(b[i]==a[j]) j++;else{flag=false;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 esp=1e-8;
const int Max=1e6+5;
const int Mod=998244353;
ll a[Max],b[Max];
queue<int>q;
int main(){int n;double h,m,k;cin>>n>>h>>m>>k;double M=m,H=h;double st_cao=0;double cao=0;for(int i=1;i<=n;i++){cao-=st_cao;string str;double cnt,dmg;cin>>str;if(str=="Physico") cin>>dmg;else cin>>cnt>>dmg;if(str=="Anemo"){//风m-=0.5*cnt;m-=0.2*M*dmg/H;}else if(str=="Geo"){//岩m-=0.5*cnt;m-=0.2*M*dmg/H;}else if(str=="Electro"||str=="Pyro"){//雷火if(str=="Pyro") m-=2*cnt;else m-=cnt;m-=0.2*M*dmg/H;int len=q.size();len=min(len,2);m-=0.2*6*k*len*M/H;while(!q.empty()) q.pop();}else if(str=="Dendro"){//草m-=0.2*M*dmg/H;if(cao>esp){cao=max(cao,0.8*cnt);}else{cao=0.8*cnt;st_cao=1.6*cnt/(14+5*cnt);}}else if(str=="Hydro"){//水m-=0.2*M*dmg/H;if(cao>esp){cao-=0.5*cnt;q.push(i);} }else if(str=="Cryo"){//冰}else if(str=="Physico"){//物理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 sum=m*100.0/M;if(sum>esp) printf("%.2lf%%\n",sum);else printf("win\n");
}