当前位置：首页 > news >正文

Codeforces Round 908 (Div. 2)题解

news 2025/9/10 15:15:10

A. Secret Sport

题目分析:

B. Two Out of Three

题目分析:

C. Anonymous Informant

题目分析:

A. Secret Sport

题目分析:

A,B一共打n场比赛，输入一个字符串由'A'和‘B’组成代表A赢或者B赢（无平局），因为题目说明这个人记得一定打了n场比赛，所以也就是n场比赛结束，题目说明，一旦分出胜负，比赛当场结束，那么一整场比赛的结束一定是分出了胜者，所以一定是字符串的最后一个，也没有所谓的'?'(平局)的情况出现

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N =1e5+7;
signed main()
{IOS
use{int n;cin>>n;string a;cin>>a;cout<<a.back()<<endl;}
return 0;
}

B. Two Out of Three

题目分析:

给定一个数组a，让创造出一个等长数组并且满足题目条件：ai=aj时，那三条，不过一整个b数组里面只能出现三种之中的两种，如果出现三种或者一种结果是不对的。

对于a数组，必须有重复的数才行，否则连前提条件ai=aj都满足不了,也就是0种。

对于重复数：

出现两次的数，那么我们让第一个数为1，第二个数为2只能满足出现1种的情况，所以必须要有至少两组的出现两次的数例如样例3：1 1 2 2.
对于出现两次以上的数，比如出现了3次，我们较为想当然的让它们为1 ， 2 ，3，结果发现这样写三种全有，那么对于这种我们只能让它出现三种其中的一种，也就是与第一种情况相同，换句话说：对于出现两次的数，和出现两次以上的数是一种做法 .

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N =1e5+7;
signed main()
{IOS
use{int n;cin>>n;vct<int>a(n+1);int cnt[101]={};for(int i=1;i<=n;i++){cin>>a[i];cnt[a[i]]++;}int x2=0;for(int i=1;i<=100;i++){if(cnt[i]>=2)x2++;}if(x2<2)cout<<"-1"<<endl;else{vct<bool>st(101,1);int cntx=1;for(int i=1;i<=n;i++){if(cnt[a[i]]>=2&&st[a[i]]&&cntx&&cntx<3){cout<<cntx+1<<" ";st[a[i]]=0;cntx++;}else cout<<"1 ";}cout<<endl;}
}return 0;
}

C. Anonymous Informant

题目分析:

给一个数组b,有人说这是由一个数组a进行如下操作得到的:

取一个x满足 $a_x=x$
将a数组向左移x格

让判断真假。

对于第x位置的 $a_x$ 向左移动x格，就变成了末尾，也就是 $a_n$ ,那么既然b是由a数组得来的，我们可以逆推出：每次操作向右移动 $b_n$ 格，最终得到数组a，因为数组a不是确定的，所以我们需要判断在逆推回a数组的时候是否会出现不可行的情况，因为正推的条件是 $a_x=x$ ,故逆推的条件是 $b_n \le n$ ，如果不满足逆推条件也就是不可行情况，结果为假。

对于操作次数 $k,(1 \le k \le 10^9)$ ,故我们考虑去除多余重复的操作，也就是取 $min(n,k)$ 次操作即可.

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N =1e5+7;
signed main()
{IOS
use{int n,k;cin>>n>>k;vct<int>a(n+1);int mas=min(n,k);for(int i=1;i<=n;i++){cin>>a[i];}int x=n;bool isok=1;while(mas--){if(a[x]>n){isok=0;break;}x=(x+n-a[x])%n;}if(isok)cout<<"Yes"<<endl;else cout<<"No"<<endl;
}return 0;
}

查看全文

http://www.lryc.cn/news/223207.html