F:
签到题,ifelse一下就行了。。。。我写复杂了。。。。。。。
#include<bits/stdc++.h> using namespace std; void solved(){ string s1,s2; cin>>s1>>s2; if(s1 == "elephant" && s2 == "tiger"){ cout<<"tiangou yiwusuoyou"<<endl;return ; }else if(s2 == "elephant" && s1 == "tiger"){ cout<<"tiangou txdy"<<endl;return ; } if(s1 == "tiger" && s2 == "cat"){ cout<<"tiangou yiwusuoyou"<<endl;return ; }else if(s2 == "tiger" && s1 == "cat"){ cout<<"tiangou txdy"<<endl;return ; } if(s1 == "cat" && s2 == "mouse"){ cout<<"tiangou yiwusuoyou"<<endl;return ; }else if(s2 == "cat" && s1 == "mouse"){ cout<<"tiangou txdy"<<endl;return ; } if(s1 == "mouse" && s2 == "elephant"){ cout<<"tiangou yiwusuoyou"<<endl;return ; }else if(s2 == "mouse" && s1 == "elephant"){ cout<<"tiangou txdy"<<endl;return ; } cout<<"tiangou yiwusuoyou"<<endl;return ; } int main(){ solved(); return 0; }
G:
签到题,贪心选择要画的时间最少的科目,排序一下,然后一个一个去选就行了。(要开ll才行)
代码
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; typedef long long int ll; ll a[maxn]; void solved(){ ll n,m;scanf("%lld%lld",&n,&m); for(ll i = 1; i <= n; i++)scanf("%lld",&a[i]); sort(a + 1,a + 1 + n); ll ans = 0; for(ll i = 1; i <= n; i++){ if(m >= a[i]){ m-=a[i]; ans++; }else break; } printf("%lld\n",ans); } int main(){ solved(); return 0; }
B:
问题可以简化为:给你一些数,满足这些数最大值与最小值差<=k,并长度最长。
为了方便处理,我们先排序,然后枚举每一个数的起始位置,然后二分出它最大值位置(满足差<=k),然后用他们的长度更新答案。
代码
#include<bits/stdc++.h> using namespace std; typedef long long int ll; const int maxn = 2e5 + 10; ll a[maxn],dis[maxn]; void solved(){ int t; for(scanf("%d",&t);t;t--){ ll n,k;cin>>n>>k; for(int i = 1; i <= n; i++)cin>>a[i]; sort(a + 1,a + 1 + n); int ans = 0; for(int i = 1; i <= n; i++){ int v = k + a[i]; int pos = lower_bound(a + 1,a + 1 + n,v) - a; if(a[pos] == v){ ans = max(ans,pos - i + 1); }else{ ans = max(ans,pos - i); } } cout<<ans<<endl; } } int main(){ solved(); return 0; }
H:
并查集的裸题了。。不过太久没写并查集导致很多细节没处理好。思路很简单,先将c=1的a,b并在同一个集合,然后检查c=0,如果发现a,b在同一个集合就会产生矛盾。cin超时要用scanf,由于每次读入两个点,所以maxn要开两倍,a,b<=1e9,所以还需要离散化一下,大概就是这些坑了。
代码
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 7; typedef long long int ll; struct node{ int a,b,c; node(){} node(int a,int b,int c):a(a),b(b),c(c){}; }ans[maxn]; int res[maxn << 1]; int f[maxn << 1]; int find(int x){ return f[x] == x? x : f[x] = find(f[x]); } void solved(){ int t; for(scanf("%d",&t);t;t--){ int n; scanf("%d",&n); int cnt = 0; for(int i = 1; i <= n * 2 ; i++)f[i] = i; for(int i = 1; i <= n; i++){ int x,y,z;scanf("%d%d%d",&x,&y,&z); res[++cnt] = x; res[++cnt] = y; ans[i] = {x,y,z}; } sort(res + 1,res + 1 + cnt); int len = unique(res + 1,res + 1 + cnt) - (res + 1); bool flag = true; for(int i = 1; i <= n; i++){ int u = ans[i].a; int v = ans[i].b; u = lower_bound(res + 1, res + 1 + len,u) - res; v = lower_bound(res + 1, res + 1 + len,v) - res; if(ans[i].c == 1){ int fa = find(u); int fb = find(v); if(fa != fb)f[fa] = fb; }else{ if(find(u) == find(v))flag = false; } } if(flag)cout<<"YES"<<endl; else cout<<"NO"<<endl; } } int main(){ solved(); return 0; }
D:
区间修改,区间求和,所以需要用到前缀和与差分,由于是二维的,所以前缀和与差分也需要二维的,可以先对所有区间修改差分一下,然后求一个和,得出每个数原来的值,再求一次前缀和实现O(1)区间和查询。
代码
#include<bits/stdc++.h> using namespace std; const int maxn = 3e3 + 10; typedef long long int ll; ll a[maxn][maxn]; void solved(){ int n,m,k,q; scanf("%d%d%d%d",&n,&m,&k,&q); while(k--){ ll x1,x2,y1,y2;scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2); a[x1][y1]++; a[x2 + 1][y2 + 1]++; a[x1][y2 + 1]--; a[x2 + 1][y1]--; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ a[i][j] += a[i][j - 1]; } } for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ a[i][j] += a[i - 1][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ a[i][j] += a[i - 1][j]; } } for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ a[i][j] += a[i][j - 1]; } } for(int i = 1; i <= q; i++){ ll x1,x2,y1,y2;scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2); cout<<a[x2][y2] + a[x1 - 1][y1 - 1] - a[x1 - 1][y2] - a[x2][y1 - 1]<<endl; } } int main(){ solved(); return 0; }
J题
sum1求aj的前缀和,sum2求aj^2的前缀和,将公式展开直接O(n)就可以做完了。
不过取模有亿点点麻烦,我是把所有能取的地方全部取了才过的,还是减法取模的时候要+mod才行,防止产生负数
代码
#include<bits/stdc++.h> using namespace std; const int maxn = 5e5 + 10; typedef long long int ll; ll mod = 1e9 + 7; ll a[maxn]; ll sum1[maxn],sum2[maxn]; void solved(){ int n;scanf("%d",&n); for(int i = 1; i <= n; i++){ scanf("%lld",&a[i]); sum1[i] = (sum1[i - 1] + a[i]) % mod; sum2[i] = (sum2[i - 1] + a[i] * a[i] % mod) %mod; } ll ans = 0; for(int i = 1; i <= n; i++){ ans += (((n - i) * a[i] % mod * a[i] % mod) %mod - (2 * a[i] % mod * (sum1[n] - sum1[i] + mod) %mod) %mod + (sum2[n] - sum2[i] + mod)%mod)%mod; } printf("%lld\n",ans%mod); } int main(){ solved(); return 0; }
C题
题意就是要你包围住这个联通块。
你可以想象一个大矩形,我们要把外面的包起来,里面的不要包,并且边界没有#,所以我们可以直接从起点(1,1)bfs,把那个矩形外围全部标记一下,矩形里面的不用管,然后遍历一下迷宫如果它是#我们就找他的四个方向,如果满足某个方向已经被标记过,我们我们可以把它改成*。
代码
#include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + 10; char s[maxn][maxn]; bool vis[maxn][maxn]; int dir[][2] = {{-1,0},{1,0},{0,-1},{0,1}}; int n,m; struct node{ int x,y; node(){} node(int a,int b):x(a),y(b){} }; void bfs(int x,int y){ queue<node>st; st.push(node(x,y)); while(!st.empty()){ node cur = st.front();st.pop(); for(int i = 0 ; i < 4; i++){ int fx = cur.x + dir[i][0]; int fy = cur.y + dir[i][1]; if(fx < 1 || fy < 1 || fx > n || fy > m)continue; if(s[fx][fy] != '#' && !vis[fx][fy]){ st.push(node(fx,fy)); vis[fx][fy] = true; } } } } void solved(){ scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf(" %c",&s[i][j]); bfs(1,1); //for(int i = 1; i <= n; i++) // for(int j = 1; j <= m; j++) // if(vis[i][j])cout<<i<<" "<<j<<endl; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(s[i][j] == '#'){ for(int k = 0; k < 4; k++){ int fx = i + dir[k][0]; int fy = j + dir[k][1]; if(vis[fx][fy] && s[fx][fy] == '.'){ s[fx][fy] = '*'; } } } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ printf("%c",s[i][j]); } cout<<endl; } } int main(){ solved(); return 0; }