A-lpt的小屋
#include<bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) typedef pair<int, int> PII; #define ll long long #define endl "\n" #define pb push_back const int N = 1e4, INF = 0x3f3f3f3f; int t; double W, H, x1, x2, Y1, y2; double w2, h2; int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); cin >> t; while (t--) { cin >> W >> H; cin >> x1 >> Y1 >> x2 >> y2; cin >> w2 >> h2; ll w1 = x2 - x1, h1 = y2 - Y1; if (w1 + w2 <= W || h1 + h2 <= H) { double ans = 1e9; if (w1 + w2 <= W) { ans = min(ans, max((double)0,w2-(W - x2))); ans = min(ans,max((double) 0,w2-x1)); } if (h1 + h2 <= H) { ans = min(ans, max((double)0,h2 - (H - y2))); ans = min(ans, max((double)0,h2 - (Y1))); } printf("%.9lf\n",ans); } else cout <<-1 << endl; } return 0; }
B-因为突然懒得翻译了所以想让你们读读英语题面
为什么不翻译?why?因为翻译过来题目太简单,你们马上就做出来了我很没面子,所以让你们读读英语题面
#include<bits/stdc++.h> using namespace std; #define ll long long const int N=200; ll a[N]={0}; ll t[N]={0}; int main() { int k; cin>>k; ios::sync_with_stdio(); cin.tie(0); cout.tie(0); while(k--) { int n; cin>>n; memset(a,0,sizeof(a)); memset(t,0,sizeof(t)); for(int i=0;i<n;i++) { cin>>a[i]; t[a[i]]++; } ll maxid=0; for(int i=1;i<=100;i++) maxid=max(t[i],maxid); cout<<maxid<<endl; } return 0; }
C - yyj 的最爱
暴力写法
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { int q,d,n; cin>>q>>d; while(q--) { cin>>n; if(n>=d*10) { cout<<"YES"<<"\n"; }else { int res=1; while(n>=0) { if(n%10==d) res=0; n-=d; } if(res==0) cout<<"YES"<<"\n"; else cout<<"NO"<<endl; } } } return 0; }
dp写法
#include<bits/stdc++.h> using namespace std; const int maxn=207; int t,d,q; bool dp[maxn]; int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin>>t; while (t--){ memset(dp,0,sizeof(dp)); dp[0]=1; cin>>q>>d; int mx=d*10; for (int i=0;10*i+d<=mx;++i){ for (int j=0;10*i+d+j<=mx;++j){ dp[10*i+d+j]|=dp[j]; } } while (q--){ int u; cin>>u; if (u>=mx||dp[u]) cout<<"YES\n"; else cout<<"NO\n"; } } return 0; }
D-we are 伐木累
#include<bits/stdc++.h> using namespace std; const int INF=1e9+10,N=1e6+10;; #define ll long long ll a[N]; ll n,m; bool check(int x) { ll sum=0; for(int i=0;i<n;i++) { ll t=a[i]-x; if(t>=0) sum+=t; } return sum>=m; } int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; } sort(a,a+n); int l=0,r=INF; while(l<r) { int mid=l+r+1>>1; if(check(mid)) l=mid; else r=mid-1; } cout<<r<<endl; return 0; }
E - CJ的防AK题
我出的防AK题是吓唬你们的。。。实际上是最水的题,真正的签到题就是这个,随便一个筛法筛一遍就行了
#include<iostream> using namespace std; const int N=100005; bool f[N]; int prime[N],n; int cnt=0; void init() { for(int i=2;i<N;i++) { if(!f[i]) prime[cnt++]=i; for(int j=0;j<cnt&&i*prime[j]<N;j++) { f[i*prime[j]]=1; if(i%prime[j]==0) break; } } } int main() { init(); cin>>n; cout<<prime[n-1]<<endl; return 0; }
F-yyj的宝剑(贪心+高精度)
直接上代码(高精度不会的同学学一下,我博客里面有我常用的高精度模板):
#include <bits/stdc++.h> using namespace std; const int N = 1e4 + 1; int n; struct node { int l, r; bool operator<(const node &w)const { return l * r < w.l * w.r; } } a[N]; vector<int>mx(vector<int> &ans, vector<int> c) { if (c.size() > ans.size()) { return c; } else if (c.size() < ans.size()) { return ans; } else { for (int i = c.size() - 1; i >= 0; i--) { if (c[i] != ans[i]) { if (c[i] > ans[i]) return c; else return ans; } } return c; } } vector<int>mul(vector<int> &sum, int &b) { int t = 0; vector<int>C; for (int i = 0; i < sum.size() || t; i++) { if (i < sum.size()) t = t + sum[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } vector<int>div(vector<int> &sum, int &b) { int t = 0; vector<int>C; for (int i = sum.size() - 1; i >= 0; i--) { t = t * 10 + sum[i]; C.push_back(t / b); t %= b; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { cin >> n; vector<int>sum(1, 1); int res; int chu; cin >> res >> chu; for (int i = 1; i <= n; i++) { cin >> a[i].l >> a[i].r; } sort(a + 1, a + 1 + n); vector<int>ans(1, 0); sum = mul(sum, res); //高精度乘低精度 for (int i = 1; i <= n; i++) { ans = mx(ans, div(sum, a[i].r)); sum = mul(sum, a[i].l); } for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i]; cout << endl; }
G- 摸鱼王的旅游计划
(考察队列)
队列数组实现(平常我喜欢数组实现栈和队列,因为更快!)
#include <iostream> #include <queue> #include <string.h> using namespace std; const int N = 1e6 + 10; typedef long long ll; // 队列存储最长不同序列 int hh=0,tt=-1; long long q[N]; // 存储值 long long a[N]; // 标志值是否在队列中 bool f[N]; int main() { ll n; scanf("%lld", &n); ll ans = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } for (int i = 1; i <= n; i++) { while (hh<=tt&&f[a[i]] != 0) { f[q[hh]]=0; hh++; } q[++tt]=a[i]; f[a[i]] = 1; ans=max(ans,(ll)(tt-hh+1)); } printf("%lld\n", ans); }
队列STL版
#include <iostream> #include <queue> #include <string.h> using namespace std; const int NUM = 1e6 + 1; typedef long long ll; // 队列存储最长不同序列 queue<long long> q; // 存储值 long long a[NUM]; // 标志值是否在队列中 bool f[NUM]; int main() { ll n; scanf("%lld", &n); ll ans = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } for (int i = 1; i <= n; i++) { if (f[a[i]] == 0) { q.push(a[i]); f[a[i]] = 1; } else { while (f[a[i]] != 0) { f[q.front()] = 0; q.pop(); } q.push(a[i]); f[a[i]] = 1; } if (q.size() > ans) { ans = q.size(); } } printf("%lld\n", ans); }
摸鱼王邓学长的解法:双指针
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int f[N]; int n; int a[N]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } int l = 0, ans = 0; for (int i = 0; i < n;) { if (f[a[i]] == 0) { f[a[i]]++; i++; } else { f[a[l]]--; l++; } ans = max( i - l, ans); } cout << ans << endl; return 0; }
H- 采花大盗:
(考察dfs或者bfs的水题,我这里只写了dfs的代码)
#include<bits/stdc++.h> using namespace std; const int N=25; bool st[N][N]; int n,m; int sx,sy; int ans=0; char s[N][N]; int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; void dfs(int x,int y) { for(int i=0;i<4;i++) { int a=dx[i]+x,b=dy[i]+y; if(!st[a][b]&&s[a][b]=='.'&&a>=1&&a<=m&&b>=1&&b<=n) { st[a][b]=1; dfs(a,b); ans++; } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { cin>>s[i][j]; if(s[i][j]=='@') { sx=i; sy=j; } } st[sx][sy]=1; ans=1; dfs(sx,sy); cout<<ans<<endl; }