Pinely Round 1 (Div. 1 + Div. 2)

比赛链接：Dashboard - Pinely Round 1 (Div. 1 + Div. 2) - Codeforces

A：思维

题意：定义了一个序列，给定了三个整数n，a，b。问能否构造两个长度为n的序列，使得它们的最长前缀的长度为a，最长后缀为b。能构造则YES，否则NO

思路：认真读题你就会发现。a和b是有关系的。为什么？

仔细思考一下，要使得前缀长度为a，两个序列在a+1位置上的数就必须要不同，从而断开，使得前缀长度为a。后缀也同理。

那么，断开的条件是什么？才能使得构造成功呢？

结论：m>=2。为什么？

必须满足a+1为断点，b-1为断点才能构造成功。

当然，这里还有一个特判。

当n=a=b，那么就说明两个序列是相同的，一定可以构造成功 

代码：

#include
#define all(v) v.begin(),v.end()
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e3+10;
typedef pair<int,int>PII;
 
inline void solve(){
	int n,a,b;cin>>n>>a>>b;
	if(n==a&&n==b){
		cout<<"Yes\n";return;
	}
	if(n-(a+b)>=2) cout<<"Yes\n";
	else cout<<"No\n";
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

B:结论

题意：给定一个环形数组，每次可以删除一个数，删除后的位置会合并掉。如果合并后存在两个相同的数字相邻，那么其中一个数会被立刻消除。每次操作可以删除一个数，求最多消除几次可以使得数组为空。

结论：

数的种类>=3，ans=n

数的种类==2，ans=+1

数的种类==1，ans=1

代码：

#include
#define all(v) v.begin(),v.end()
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e3+10;
typedef pair<int,int>PII;
 
inline void solve(){
	int n;cin>>n;
	int cnt=0;//记录种类数
	map<int,int>mp;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		if(mp[x]==0) cnt++;
		mp[x]++;
	}
	if(n==1) cout<<"1\n";
	else if(cnt==2) cout<2+1<<"\n";
	else if(cnt>=3) cout<"\n";
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

C:构造

题意：给定一个 n∗n 的 01 矩阵，要求构造 n 个满足要求的集合 A1，A2，A3，...，An ，使得 bij=1 的时候，集合 Ai 是集合 Aj 的真子集。

思路：先扫一遍矩阵。当碰见=1的时候 ，我们就将Ai中的元素全部放进Aj中。在放的时候，会出现Ai中的元素被更新的情况，这个时候再扫一遍即可。

代码：

#include
#define all(v) v.begin(),v.end()
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e3+10;
typedef pair<int,int>PII;
char b[N][N];
 
inline void solve(){
	set<int>se[N];
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>b[i][j];
			se[i].insert(i);//给Ai一个初始值
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(b[i][j]=='1'){
				for(auto x:se[i]){
					se[j].insert(x);//满足条件的情况下：将Ai放入Aj中
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(b[i][j]=='1'){
				for(auto x:se[i]){
					se[j].insert(x);//放在A更新，再放入一次
				}
			}
		}
	}
	for(int i=1;i<=n;i++){//输出即可
		cout<size()<<" ";
		for(auto x:se[i]){
			cout<" ";
		}
		cout<<"\n";
	}
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}