Codeforces Round #579 (Div. 3)

图片说明

题意：
给出一个序列，问你是否能构成1-n的环或者n-1的环。
题解：
处理一下序列，取模就行了。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[205];
int main()
{
  int t,n;
  cin>>t;
  while(t--)
  {
      int flag1 = 0,flag2 = 0;
      cin>>n;
      for(int i=1;i<=n;i++){
          cin>>a[i];
          a[i] -= 1;
      }
      // 3 0 1 2
      // 3 0 1 2
      for(int i=1;i<n;i++){
          if((a[i]+1)%n != a[i+1]%n)
              flag1 = 1;
          if((a[i+1]+1)%n != a[i]%n)
              flag2 = 1;
      }
      if(!flag1||!flag2)
          cout<<"YES"<<endl;
      else
          cout<<"NO"<<endl;
  }

  return 0;
}

图片说明

题意：
给出你4*n个木棍，问你是否能组成n个面积相同的矩形。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[404],b[202];
int main()
{
  int t,n;
  cin>>t;
  while(t--)
  {
      set<int> s;
      cin>>n;
      int cnt = 0,flag = 0;
      for(int i=1;i<=4*n;i++){
          scanf("%d",&a[i]);
      }
      sort(a+1,a+1+4*n);
      for(int i=1;i<=4*n;i+=2){
          if(a[i] != a[i+1]){
              flag = 1;
          }else{
              b[++cnt] = a[i];
          }
      }
      if(flag){
          cout<<"NO"<<endl;
          continue;
      }
      for(int i=1;i<=n;i++)
      {
          int k = b[i]*b[2*n-i+1];
          s.insert(k);
      }
      if(s.size() == 1){
          cout<<"YES"<<endl;
      }else{
          cout<<"NO"<<endl;
      }

  }
  return 0;
}

图片说明
题意：
给出n个数，让你找出这些数的公因数的个数。
题解：
先算出所有数的最大公因数，然后照这个公因数的因子个数。
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[400005];
int main()
{
  int n;
  cin>>n;
  scanf("%lld",&a[1]);
  ll gcd = a[1];
  for(int i=2;i<=n;i++)
  {
      scanf("%lld",&a[i]);
      gcd = __gcd(gcd,a[i]);
  }
  ll ans = 0;
  for(ll i=1;i*i<=gcd;i++)
  {
      if(gcd%i == 0){
          ans++;
          if(i*i != gcd)
              ans++;
      }
  }
  cout<<ans<<endl;
  return 0;
}

图片说明

题意：
给出一个母串和一个子串且母串中存在子串的子序列，问你最多删除母串多少字符依然能让母串中存在子串的子序列。有俩个不同的难度，就是长度不同而已，这里直接写hard的做法。
题解：
最大分割情况只可能是两种，一种是最左端或者最右端删去一大段，另一种是中间任意两个字母间删去一大段

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 200005;
char s1[maxx],s2[maxx];
int pre[maxx],nex[maxx];
int main()
{
  scanf("%s%s",s1,s2);
  int l1 = strlen(s1),l2 = strlen(s2);
  int t = 0;
  for(int i=0;i<l1;i++){
      if(s1[i] == s2[t]){
          pre[t] = i;
          t++;
      }
      if(t >= l2)
          break;
  }
  t = l2-1;
  for(int i=l1-1;i>=0;i--){
      if(s1[i] == s2[t]){
          nex[t] = i;
          t--;
      }
      if(t < 0)
          break;
  }
  int ans = max(nex[0],l1 - pre[l2-1] - 1);
  for(int i=1;i<l2;i++){
      ans = max(ans,nex[i] - pre[i - 1]-1);
  }
  cout<<ans<<endl;
  return 0;
}

题意：
给出n个人的体重，每个人可以选择增加1，较少1，或者不变体重。
问你最后最多有多少人的体重不一样，注意，体重不能减小到0
题解：
必须要往一个方向填充贪心。
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 150010;
int a[maxx],flag[maxx];
int main()
{
  int n,ans = 0;
  cin>>n;
  for(int i=1;i<=n;i++){
      scanf("%d",&a[i]);
  }
  sort(a+1,a+1+n);
  flag[0] = 1;
  for(int i=1;i<=n;i++)
  {
      if(!flag[a[i] - 1]){
          flag[a[i] - 1] = 1;ans++;
      }
      else if(!flag[a[i]]){
          flag[a[i]] = 1;ans++;
      }
      else if(!flag[a[i] + 1]){
          flag[a[i]+1] = 1;ans++;
      }
  }
  cout<<ans<<endl;
  return 0;
}

题意：
给出n对数，每个数有俩个权值a和b，a代表学习这个技能的最小等级，b代表你学完这个技能后可以增加或者减少多的等级，问你能否学完所有的技能
题解：
优先队列+贪心
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
  int a,b;
  friend bool operator < (node p1,node p2){
      return p1.a>p2.a;
  }//小
};
struct node2{
  int a,b;
  friend bool operator < (node2 p1,node2 p2){
      if(p1.a + p1.b != p2.a + p2.b)
          return p1.a + p1.b < p2.a + p2.b;
      return p1.a<p2.a;
  }
};
priority_queue<node> q1;
priority_queue<node2> q2;
int main()
{
  int n,r,a,b;
  scanf("%d %d",&n,&r);
  for(int i=1;i<=n;i++){
      cin>>a>>b;
      if(b>=0)
          q1.push(node{a,b});
      else
          q2.push(node2{a,b});
  }
  while(!q1.empty())
  {
      node now = q1.top();
      q1.pop();
      if(now.a > r){
          cout<<"NO"<<endl;
          return 0;
      }
      r += now.b;
  }
  //cout<<r<<endl;
  while(!q2.empty())
  {
      node2 now = q2.top();
      q2.pop();
      if(now.a > r){
          cout<<"NO"<<endl;
          return 0;
      }
      r += now.b;
  }
  //cout<<r<<endl;
  if(r >= 0)
      cout<<"YES"<<endl;
  else
      cout<<"NO"<<endl;
  return 0;
}

加油！
图片说明