526互联

CF1825 div 2

发布时间 2023-05-08 23:10:37作者: 洛浔

A

结论题 删掉一个或者全相同。

// Problem: A. LuoTianyi and the Palindrome String
// Contest: Codeforces - Codeforces Round 872 (Div. 2)
// URL: https://codeforces.com/contest/1825/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

void work(){
	string s;
	cin>>s;
	// cout<<s<<endl;
	int n=s.length();
	s='_'+s;
	int fg=0;
	for(int i=1;i<=n;i++)
	if(s[i]!=s[1]) {fg=1;}
	cerr<<n<<endl;
	if(fg)cout<<n-1<<endl; 
	else cout<<-1<<endl;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		work();
	}
	
	return 0;
}

B

结论题，考虑左上角放极差

// Problem: A. LuoTianyi and the Palindrome String
// Contest: Codeforces - Codeforces Round 872 (Div. 2)
// URL: https://codeforces.com/contest/1825/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[20005];
void work(){
	int n,m;
	cin>>n>>m;
	
	int nn=n*m;
	for(int i=1;i<=nn;i++)cin>>a[i];
	sort(a+1,a+nn+1);
	int ans=(a[nn]-a[1])*(nn-1);
	
	ans-=(min(n,m)-1)*min(a[nn]-a[nn-1],a[2]-a[1]);
	cout<<ans<<endl;
}
signed main(){
		ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		work();
	}
	
	return 0;
}

C

考虑是从一个点开始然后左右延伸。然后枚举 贪心。

// Problem: C. LuoTianyi and the Show
// Contest: Codeforces - Codeforces Round 872 (Div. 2)
// URL: https://codeforces.com/contest/1825/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],n,m;
int cnt[N],c1,c2,num;
void work(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	c1=c2=0,num=0;;
	for(int i=1;i<=n;i++){
		if(a[i]==-1) c1++;
		else if(a[i]==-2) c2++;
		else {
			if(cnt[a[i]]==0) num++;
			cnt[a[i]]++;
		}
	}
	// cout<<c1<<" "<<c2<<" "<<num<<endl;
	int ans=max(c1,c2)+num;
	int ccc=0;
	for(int i=1;i<=m;i++){
		if(cnt[i]){
			ccc++;
			int tmp=min(i,ccc+c1)+min(m-i,num-ccc+c2);
			// cout<<min(i,ccc+c1)<<" "<<min(m-i-1,num-ccc+c2)<<endl;
			ans=max(ans,tmp);
		}
	}
	cout<<min(ans,m)<<endl;
	for(int i=1;i<=n;i++) if(a[i]>0)cnt[a[i]]=0;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		work();
	}
	
	return 0;
}

D1

操！
没取模。

// Problem: D1. LuoTianyi and the Floating Islands (Easy Version)
// Contest: Codeforces - Codeforces Round 872 (Div. 2)
// URL: https://codeforces.com/contest/1825/problem/D1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long N=4e5+5,mod=1e9+7;
long long n,k;
vector<long long> v[N];
long long siz[N],ans;

void dfs(long long u,long long fa){
	siz[u]=1;
	for(long long x:v[u]){
		if(x==fa) continue;
		dfs(x,u);
		siz[u]+=siz[x];
		ans+=(long long)siz[x]*(n-siz[x])%mod;
		ans%=mod;
	}
	
}
long long qp(long long a,long long b){
	long long ret=1;
	for(;b;b>>=1,a=a*a%mod) if(b&1) ret=ret*a%mod;
	return ret;
}
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	if(k==1||k==3){cout<<1<<endl;return 0;}
	for(long long i=1;i<n;i++){
		long long x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	// cerr<<ans<<endl;
	ans=(ans+n*(n-1)/2)%mod;
	printf("%lld\n",(long long)ans*qp(n*(n-1)/2%mod,mod-2)%mod);
	return 0;
}