赞
踩
题意: 有n个台阶,其中有k个是坏的,坏的不能到达,每次只能爬一阶或者两阶,问爬到第n阶台阶有多少种方案,答案对1e9+7取模
题解: 经典斐波那契,当遇到坏的台阶时,坏的台阶方案数为0即可
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1000010,mod=1e9+7; ll a[N]; ll b[N]; int main() { ios::sync_with_stdio(false); int t; cin>>t; while(t--) { int n,x; cin>>n>>x; for(int i=1; i<=x; i++) { int x; cin>>x; b[x]=1; } a[0]=1; if(b[1]==1) a[1]=0; else a[1]=1; for(int i=2; i<=n; i++) if(b[i]==1) { a[i]=0; } else a[i]=(a[i-1]+a[i-2])%mod; cout<<a[n]<<"\n"; for(int i=1; i<=1e5; i++) b[i]=0; } }
题解: 先求出两点距离,在按照题上给的评级得出分数,如果分数为0,那么连击数也要清零,再用分数乘以连击数的加成即可
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1000010,mod=1e9+7; double x1[N],x2[N]; double y11[N],y2[N]; int main() { ios::sync_with_stdio(false); int n; ll sum=0; double r; cin>>n>>r; int com=0; for(int i=1; i<=n; i++) cin>>x1[i]>>y11[i]; for(int i=1; i<=n; i++) cin>>x2[i]>>y2[i]; for(int i=1; i<=n; i++) { double r1=sqrt((x1[i]-x2[i])*(x1[i]-x2[i])+(y11[i]-y2[i])*(y11[i]-y2[i])); double ans;//分数 if(r1<0.2*r) ans=300; else if(r1<0.5*r) ans=200; else if(r1<r) ans=100; else ans=0; if(ans==0) { com=0; continue; } else com++; double tmp=1; if(com>=400) tmp+=0.04; else if(com>=300) tmp+=0.03; else if(com>=200) tmp+=0.02; else if(com>=100) tmp+=0.01; sum+=ans*tmp; } cout<<sum; }
题解: 根据题目中的公式可以化简出:
可以证明出这个函数是单调递增,所以可以使用浮点数二分答案
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1000010,mod=1e9+7; ll a[N]; ll b[N]; int main() { ios::sync_with_stdio(false); int t; cin>>t; while(t--) { double n; cin>>n; double l=0,r=100000000000; for(int i=1; i<=1000; i++) { double mid=(l+r)/2; if(0.5*(pow(mid,1.5))+sin(mid)>n) r=mid; else l=mid; } printf("%.6lf\n",l); } }
**题解:**小签到题。可以先把字符串三个一组分组,然后利用map给分组的字符串赋值
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1000010,mod=1e9+7; ll a[N]; ll b[N]; int main() { ios::sync_with_stdio(false); int n; cin>>n; string s; cin>>s; map<string,char>ma; char ch='a'; for(int i=0; i<n*3; i+=3) { string s1; s1+=s[i]; s1+=s[i+1]; s1+=s[i+2]; if(!ma.count(s1)) { ma[s1]=ch; ch++; } cout<<ma[s1]; } }
题解: 因为题上的ch[i]<10,所以当选中矩阵的面积大于10时肯定会不合法,所以直接遍历行和列的值,当行乘以列大于10是直接continue,
枚举左上角的坐标,通过行和列的值找出左下角的坐标,遍历有左上角和右下角形成的整个矩形,然后判断不同的数是否等于矩形的面积。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=510,mod=1e9+7; int a[N][N]; int n,m; int ma[100]; int main() { ios::sync_with_stdio(false); scanf("%d%d",&n,&m); // cin>>n>>m; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&a[i][j]); // cin>>a[i][j]; int sum=0; for(int h=1; h<=10; h++) { for(int l=1; l<=10; l++) { if(l*h>10) continue; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { int x1=i+h-1; int y1=j+l-1; if(x1>n||y1>m) continue; int cnt=0; for(int i=0;i<=9;i++) ma[i]=0; for(int ii=i; ii<=x1; ii++) { for(int jj=j; jj<=y1; jj++){ if(ma[a[ii][jj]]) continue; ma[a[ii][jj]]++; cnt++; } } sum+=(cnt==(x1-i+1)*(y1-j+1)); } } } } cout<<sum; }
题解: 利用结构体排序,把小时,分钟全部转化成秒,按时间排序,时间相同,就按出现前后排序
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1000010,mod=1e9+7; int n,m; struct Node { string s; int x,id; } p[N]; bool cmp(Node a,Node b) { if(a.x==b.x) return a.id<b.id; return a.x<b.x; } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1; i<=n; i++) { string s; char ch; int h,m,ms; cin>>s>>h>>ch>>m>>ch>>ms; p[i].s=s; p[i].x=h*3600+m*60+ms; p[i].id=i; } sort(p+1,p+1+n,cmp); for(int i=1; i<=n; i++) cout<<p[i].s<<"\n"; }
题意: 给出一个由n个点和m条边的无向图,每次删除若干条边,然后求删边之后从1到n的最短路
题解: 容易发现这个题算法就是最短路 ,关键就是时间复杂度难处理,可以先跑一遍dijkstra,然后记录让节点i入队的节点u,即pre[i]=u,表示i的父节点u更新了i使节点i入队,然后从节点n往回搜,把往回搜的这条路径上的所有边标记,在删除的边中若没有被标记的边,说明从1到n的最短路上的所有边都没有被删,此时直接输出dis[n]即可,
但是若果有被标记的边,就要再跑一次dijkstar,然后输出结果。这道题说明数据全部随机产生,不会有硬卡数据的点,但是会有一个数据特别大,一般不降时间复杂度的写法会超时
代码:
# include "bits/stdc++.h" using namespace std; using ll = long long; const int N = 510; const int M = N * N * 2; struct Edge { int nxt, to, val; } edge[M]; int head[N], cnt; inline void add_Edge ( int from, int to, int val ) { edge[++cnt] = { head[from], to, val }; head[from] = cnt; } bool is_del[M]; int n, m, s; int vis[N], dis[N]; int pre[N]; struct node { int id, val; inline friend bool operator < ( node a, node b ) { return a.val > b.val; } }; bool in_short_edge[N][N]; inline void Dijkstra () { for ( int i = 1; i <= n; i ++ ) vis[i] = 0, dis[i] = 0x3f3f3f3f; priority_queue<node> heap; heap.push({1, 0}); dis[1] = 0; while ( !heap.empty() ) { node node_u = heap.top(); heap.pop(); int u = node_u.id, val = node_u.val; if ( vis[u] ) continue; vis[u] = true; for ( int i = head[u]; i; i = edge[i].nxt ) { if ( is_del[i] ) continue; int v = edge[i].to; if ( dis[v] > dis[u] + edge[i].val ) { dis[v] = dis[u] + edge[i].val; heap.push({v, dis[v]}); pre[v] = u; } } } } int u[M], v[M], w[M]; int main () { scanf("%d%d%d", &n, &m, &s); for ( int i = 1; i <= m; i ++ ) { scanf("%d%d%d", &u[i], &v[i], &w[i]); add_Edge(u[i], v[i], w[i]); add_Edge(v[i], u[i], w[i]); } Dijkstra(); int disn = dis[n]; for ( int cur = n; pre[cur]; cur = pre[cur] ) { in_short_edge[pre[cur]][cur] = true; in_short_edge[cur][pre[cur]] = true; } while ( s -- ) { int num; scanf("%d", &num); vector<int> del(num); bool need_again = false; for ( int &i : del ) { scanf("%d", &i); is_del[i * 2] = is_del[i * 2 - 1] = true; if ( in_short_edge[u[i]][v[i]] ) need_again = true; } if ( !need_again ) printf("%d\n", disn == 0x3f3f3f3f ? -1 : disn); else Dijkstra(), printf("%d\n", dis[n] == 0x3f3f3f3f ? -1 : dis[n]); for ( int i : del ) is_del[i * 2] = is_del[i * 2 - 1] = false; } }
题解: 因为答案最后对2取余,所以只需要考虑a[i]奇偶性,把每个a[i]记成0和1,因为1异或1等于0,0异或0等于0,所以只需要考虑1异或0的情况,题上说把每一对都异或,所以最后的公式就是(0的数量乘以1的数量)个1异或,若cnt0*cnt1为1答案就为1,否则为0。有一种特殊情况是数组中的数全部为1,没有0,这个时候1的数量为奇答案就是1,否则为0
代码:
#include<bits/stdc++.h> using namespace std; const int N=1000010; int a[N]; int main(){ ios::sync_with_stdio(false); int n; cin>>n; // for(int i=1;i<=n;i++) cin>>a[i]; long long cnt1=0,cnt0=0; for(int i=1;i<=n;i++){ int x; cin>>x; if(x%2) cnt1++; else cnt0++; } if(cnt1*cnt0%2||cnt0==0&&cnt1%2==1) cout<<"1"; else cout<<0; }
**题解:**如果a和b的最大公约数不是1,那么a和b就要有除1外的公约数,因为对a操作,b不变,可以分解b的所有质因子,计算a最少加多少次可以被b的质因子整除
代码:
#include <bits/stdc++.h> #define ll long long using namespace std; const ll mod = 1e9 + 7; const int maxn = 1e5 + 5; ll v1[2005], v2[2005]; ll sum1[2005], sum2[2005]; int main(){ ll t; cin>>t; while(t--){ ll n,m; cin>>n>>m; if(__gcd(n,m)!=1) { cout<<0<<"\n"; continue; } vector<ll>v,v1; for(int i=2;i<=m/i;i++){ if(m%i==0){ v.push_back(i); while(m%i==0) m/=i; } } if(m!=1) v.push_back(m); int len=v.size(); for(int i=0;i<len;i++) v1.push_back(v[i]-n%v[i]); sort(v1.begin(),v1.end()); cout<<v1[0]<<"\n"; } return 0; }
**题解:**要求删除对角线,那么可以把主对角线和副对角线分开写,
这里有个性质:对于主对角线上面所有的元素a[i][j],同一主对角线的 j-i 的值相同,对于所有副对角线上面的所有元素a[i][j],同一副对角线的 j+i 的值相同。考虑主对角线,把每条主对角线上的所有值相加
变成a[i]
然后求出a[i]的前缀和sum[i],根据假设删除的对角线是第i条线,那么矩阵两部分的值分别是sum[i-1]和sum[n+n-1]-sum[i]
同理,副对角线也是一样。
代码:
#include<bits/stdc++.h> using namespace std; const int N=1010; int sum[N*2],a[N*2]; int g[N][N]; int main(){ ios::sync_with_stdio(false); int n; scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&g[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i+j-1]+=g[i][j]; for(int i=1;i<=n+n-1;i++) sum[i]=sum[i-1]+a[i]; int res=0x3f3f3f3f; for(int i=1;i<=n+n-2;i++) res=min(res,abs(sum[i]-(sum[n+n-1]-sum[i+1]))); for(int i=1;i<=n+n;i++) a[i]=sum[i]=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[j-i+n]+=g[i][j]; for(int i=1;i<=n+n-1;i++) sum[i]=sum[i-1]+a[i]; // int res=0x3f3f3f3f; for(int i=1;i<=n+n-2;i++) res=min(res,abs(sum[i]-(sum[n+n-1]-sum[i+1]))); cout<<res; }
签到题。直接模拟。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1000010,mod=1e9+7; ll a[N]; ll b[N]; int main() { ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int a,b,c; cin>>a>>b>>c; if(a>=30&&b>=14&&c>=12) cout<<"Yes\n"; else if(a>=20&&b>=14&&c>=12) cout<<"ulii\n"; else cout<<"No\n"; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。