第二次周赛题解

简介: 第二次周赛题解

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;
}
蔡珏
+关注
目录
打赏
0
0
0
0
2
分享
相关文章
【力扣每日一题】1207. 独一无二的出现次数
【力扣每日一题】1207. 独一无二的出现次数
|
9月前
力扣370周赛 -- 第三题(树形DP)
力扣370周赛 -- 第三题(树形DP)
|
9月前
|
六六力扣刷题哈希表之快乐数
六六力扣刷题哈希表之快乐数
59 0
算法刷题第三天:双指针--2
右指针不断向右移动,每次右指针指向非零数,则将左右指针对应的数交换,同时左指针右移。
84 0
算法刷题第三天:双指针--2
【LeetCode每日一题】剑指 Offer 39. 数组中出现次数超过一半的数字(持续更新)
【LeetCode每日一题】剑指 Offer 39. 数组中出现次数超过一半的数字(持续更新)
118 0
【LeetCode每日一题】剑指 Offer 42. 连续子数组的最大和(持续更新)
【LeetCode每日一题】剑指 Offer 42. 连续子数组的最大和(持续更新)
89 0
【LeetCode每日一题】剑指 Offer 40. 最小的k个数(持续更新)
【LeetCode每日一题】剑指 Offer 40. 最小的k个数(持续更新)
86 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等