Codeforces Round #835 (Div. 4)

比赛链接：Dashboard - Codeforces Round #835 (Div. 4) - Codeforces

A: 排序

题意：给定三个数，求第二大数

思路：排一遍序，输出第二个数即可

代码：

#include
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int a[N];
 
inline void solve(){
	for(int i=1;i<=3;i++) cin>>a[i];
	sort(a+1,a+1+3);
	cout<2]<<"\n"; 
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

B: 排序

 题意：找最大字符

思路：排序即可

代码：

#include
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int a[N];
 
inline void solve(){
	int n;string s;cin>>n>>s;
	sort(s.begin(),s.end());
	char aa=s[s.size()-1];
	int ans=aa-'a'+1;
	cout<"\n";
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

C:贪心

题意：给定长度为N的数组，找每个数与最大数的差值，如果本身就是最大数，则差值为最大数-次大数 

思路：排一次序。依次运算即可

代码：

#include
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int a[N],b[N];
 
inline void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
	sort(b+1,b+1+n);
	if(b[1]==b[n]){
		for(int i=1;i<=n;i++) cout<<"0 ";
		cout<<"\n";return;
	}
	for(int i=1;i<=n;i++){
		if(a[i]==b[n]) cout<<(a[i]-b[n-1])<<" ";
		else cout<<(a[i]-b[n])<<" ";
	}
	cout<<"\n";
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

D:思维+模拟

 这里直接说结论吧

结论：找到山谷后，后面的上升序列只能一直升，不能降

代码：

#include
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int a[N],d[N];
 
inline void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	bool ok=false;//表示是否为升序
	for(int i=2;i<=n;i++){
		if(a[i]==a[i-1]) continue;
		if(ok){
			if(a[i]-1]){
				cout<<"NO\n";return;
			}
		}
		if(a[i]>a[i-1]) ok=true;
	}
	cout<<"YES\n";
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

 E:前后缀

 题意：给定 01 串，求最多反转其中一个位置的前提下，最大的逆序对数

吐槽：一开始考虑贪心，直接搞TLE了。然后又O（N^2）求逆序对，也炸了。没有脑子捏。。。

思路：这里用前后缀进行优化

先算出初始的逆序对数量，接下来考虑每个点翻转对答案的影响。

如果是 0 变成 1 ，那么对答案的影响是减去后面的 1 的数量，加上前面 0 的数量。

如果是 1 变成 0 ，那么对答案的影响是减去后面 0 的数量，加上前面 1 的数量。

用前后缀分别维护出一个位置前面和后面 1 和 0 的数量即可。

代码：

#include
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int arr[N],p1[N],s1[N],p0[N],s0[N];
//p1：表示当前位置前面有多少个1
//p0：表示当前位置前面有多少个0
//s1：表示当前位置后面有多少个1
//s0：表示当前位置后面有多少个0
 
inline void solve(){
	int n;cin>>n;int sum=0;//sum记录逆序对数
	for(int i=1;i<=n;i++) cin>>arr[i];
	int a=0,b=0;//a表示1的个数，b表示0的个数
	for(int i=n;i>=1;i--){
		if(arr[i]==1){
			s1[i]=a;s0[i]=b;
			a++;sum+=b;
		}
		else{
			s1[i]=a;s0[i]=b;b++;
		}
	}
	a=0,b=0;
	for(int i=1;i<=n;i++){
		if(arr[i]==1){
			p1[i]=a;p0[i]=b;a++;
		}
		else{
			p1[i]=a;p0[i]=b;b++;
		}
	}
	int ans=sum;
	for(int i=1;i<=n;i++){//进行枚举判断
		if(arr[i]) ans=max(ans,sum+p1[i]-s0[i]);
		else ans=max(ans,sum-p1[i]+s0[i]);
	}
//ps：p0和s1数组没有用到捏...q.q
	cout<"\n";
}
 
signed main(){
	int T;cin>>T;
	while(T--) solve();
}

 F:二分+贪心

题意：有 n 个任务，每个任务做完会获得 ai 的奖励，任务做完会有 x 天的 cd ，必须在 x+1 天才能继续完成这个任务。给定参数 c,d ，请问在 d 天获得至少 c 的奖励的最大cd是多少。

思路：先考虑特判，先从大到小sort一遍。

如果不存在冷却时间的情况下，如果每天都选择最大的得分（maxx）,d*maxx

#include
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int a[N],n,c,d;
 
bool check(int mid){
	int sum=0;
	for(int i=1;i<=min(mid+1,n);i++){
		for(int j=i;j<=d;j+=mid+1){
			sum+=a[i];
			if(sum>=c) return true;
		}
	}
	return false;
}
 
inline void solve(){
    cin>>n>>c>>d;
	int maxx=0,sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];maxx=max(maxx,a[i]);
	}
	sort(a+1,a+1+n,greater<int>());
	for(int i=1;i<=min(d,n);i++) sum+=a[i];
	if(d*maxx"Impossible\n";
	else{
		if(sum>=c){
			cout<<"Infinity\n";return;
		}
		int L=0,R=2e5;
		while(L+1
			int mid=L+R>>1;
			if(check(mid)) L=mid;
			else R=mid;
		}
		cout<"\n";
    }
}
 
signed main(){
	int T;cin>>T;
	while(T--) solve();
}

#include
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
typedef pair<int,int>PII;
int n,a,b;
vectorve[N];
set<int>se;
bool ok;
 
void dfs1(int u, int fa, int sum){
    se.insert(sum);
    for(auto [x, y] : ve[u]){
        if(x == fa) continue;
        if(x != b)
        dfs1(x, u, sum ^ y);
    }
}
 
void dfs2(int u, int fa, int sum){
    for(auto [x, y] : ve[u]){
        if(x == fa) continue;
        if(se.count(sum ^ y)) ok = 1;
        dfs2(x, u, sum ^ y);
    }
}
 
void solve(){
    cin >> n >> a >> b;
    ok = false;se.clear();
    for(int i = 1; i <= n; i ++ ) ve[i].clear();
    for(int i = 1; i <= n - 1; i ++ ){
        int x, y, z;cin >> x >> y >> z;
        ve[x].push_back({y, z});
		ve[y].push_back({x, z});
    }     
    dfs1(a, 0, 0);dfs2(b, 0, 0);
    if(ok) cout << "YES\n";
    else cout << "NO\n";
}
 
signed main(){
	int T;cin>>T;
	while(T--) solve();
}