搜索

Codeforces Round #829 (Div. 2)


发布时间: 2022-11-24 20:41:00    浏览次数:38 次

A. Technical Support

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
const ll N=2e5+10;
const ll inf=1e18;
const ll mod=9901;
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  ll t;cin>>t;
  while(t--){
	ll n;cin>>n;
	string s;cin>>s;
	ll ans=0;
	for(ll i=0;i<s.size();i++){
		if(s[i]=='Q') ans++;
		else if(ans>0) ans--;
	}
	if(ans) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
  }
}

B. Kevin and Permutation

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
const ll N=2e5+10;
const ll inf=1e18;
const ll mod=9901;
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  ll t;cin>>t;
  while(t--){
	ll n;cin>>n;
	if(n&1) cout<<n<<" ";
	for(ll i=n/2;i>=1;i--) cout<<i<<" "<<i+n/2<<" ";
	cout<<endl;
  }
}

C1. Make Nonzero Sum (easy version)

题解:因为只包含1和-1,每次都考虑a[i]和a[i+1],和就是a[i]-a[i+1],可以发现,如果这两个数相同的话和就是0,如果不同的话就应该把他们分别加上。

例如:一个序列1 1,直接选择[1,2]这个区间,和就是1-1=0,和为0,如果序列为1 -1,那么就分两次选择,[1,1]和[2,2],就是1+(-1)=0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
const ll N=1e6+5;
const ll inf=1e18;
const ll mod=9901;
ll a[N];
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  ll t;cin>>t;
  while(t--){
    ll n;cin>>n;
    for(ll i=1;i<=n;i++) cin>>a[i];
    vector<ll> ans;
    ans.push_back(0);
    for(ll i=2;i<=n;i++){
      if(i&1) continue;
      if(a[i]==a[i-1]) ans.push_back(i);
      else ans.push_back(i-1),ans.push_back(i);
    }
    if(n&1) cout<<"-1"<<endl;
    else{
      cout<<ans.size()-1<<endl;
      for(ll i=1;i<ans.size();i++){
        cout<<ans[i-1]+1<<" "<<ans[i]<<endl;
      }
    } 
  }
}

C2. Make Nonzero Sum (hard version)

题解:与前一题相同,只需要判断一下0的位置

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
const ll N=2e5+5;
const ll inf=1e18;
const ll mod=9901;
ll a[N];
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  ll t;cin>>t;
  while(t--){
    ll n;cin>>n;
    ll sum=0;
    for(ll i=1;i<=n;i++){
       cin>>a[i];
       if(a[i]) sum++;
    }
    vector<ll> ans;
    if(sum&1) cout<<"-1"<<endl;
    else {
      ll beg=0,end=0;
      ll p=0;
      for(ll i=1;i<=n;i++){
        if(a[i]){
          p++;
          if(p==1){
            if(a[i-1]==0){
            ans.push_back(i-1);
            }
            beg=i;
          }
          else if(p==2){
            end=i;
            if(((end-beg)%2&&a[end]==a[beg])||((end-beg)%2==0&&a[end]!=a[beg])){
              ans.push_back(end);
            }
            else {
              ans.push_back(beg);
              ans.push_back(end);
            }
            p=0;
          }
        }
      }
      if(a[1]==0){
        ans.insert(ans.begin(),0);
      }
      if(a[n]==0){
        ans.push_back(n);
      }
      cout<<ans.size()-1<<endl;
      for(ll i=1;i<ans.size();i++){
        cout<<ans[i-1]+1<<" "<<ans[i]<<endl;
      }
    }
  }
}

D. Factorial Divisibility

题解:判断最后a1!+a2!+...an!是否包含x!,判断是否有x!,如果存在a[i]>=x那么肯定还有x!,如果不存在,那么我们就要判断它的第一位的,就比如要得到4!就需要4*3!,就是3!+3!+3!+3!,需要四个3!,然后3!同理,需要三个2!一次类推,所以就可以从1开始往上不断累加阶乘,最后看能不能到达x!

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
const ll N=5e5+5;
const ll inf=1e18;
const ll mod=9901;
ll a[N],sum[N];
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  ll n,m;cin>>n>>m;
  for(ll i=1;i<=n;i++){
     cin>>a[i];
     sum[a[i]]++;//记录每一个数的个数
  }
  ll ans=0;
  bool flag=0;
  for(ll i=1;i<=m-1;i++){
    if(sum[i]%(i+1)){//如果这个i!可以往上累加变成(i+1)!
      flag=1;break;
    }
    sum[i+1]+=sum[i]/(i+1);
  }
  if(flag) cout<<"No"<<endl;
  else cout<<"Yes"<<endl;
}
免责声明 Codeforces Round #829 (Div. 2),资源类别:文本, 浏览次数:38 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 08:41:00。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/hhzp/p/16923213.html