Codeforces Round #401 (Div. 2) (A~E)

落日映苍穹つ 2022-07-10 04:22 187阅读 0赞

[CF \#401][CF _401](链接)

A题：

枚举一下题意，然后找循环节就可以了。（不找规律会TLE的）

代码：

#include<bits/stdc++.h>
    using namespace std;
    int a[3]={0,1,2};
    
    int main()
    {
    	int n,x;
    	cin>>n>>x;
    	n=n%6;
    	for(int i=0;i<n;i++){
    		 if(i%2==0){
    		 	swap(a[0],a[1]);
    		 }
    		 else{
    		 	swap(a[1],a[2]);
    		 }
    	}
    	cout<<a[x]<<endl;
    	return 0;
    }

B题：

贪心，都sort一下，然后分别从前和后扫一遍就行了。

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    int main()
    {
    	int n,x;
    	cin>>n;
    	string s,ss;
    	cin>>s>>ss;
    	sort(s.begin(),s.end());
    	sort(ss.begin(),ss.end());
    	int j=n-1;
    	for(int i=n-1;i>=0;--i){
    		if(ss[j]>=s[i]) --j;
    	}
    	cout<<j+1<<endl;
    	j=0;
    	for(int i=0;i<n;i++){
    		if(ss[i]>s[j])j++;
    	}
    	cout<<j<<endl;
    	return 0;
    }

C题：

dp题。

设dp【i】【j】表示到达 i 行 j 列时的最大贡献。

所以转移方程为：if(a\[i\]\[j\]>=a\[i-1\]\[j\]) dp\[i\]\[j\]=dp\[i-1\]\[j\]+1;else dp\[i\]\[j\]=1.

代码：

#include<bits/stdc++.h>
    using namespace std;
    int ans[100010];
    //dp【i】【j】表示在i行j列时的最大贡献
    int main()
    {
    	int n,m;
    	int x;
    	cin>>n>>m;
    	int a[n+5][m+5];
    	int dp[n+5][m+5];
    	memset(a,0,sizeof(a));
    	memset(dp,0,sizeof(dp));
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>x;
    			a[i][j]=x;
    		}
    	}
    	for(int i=1;i<=m;i++)dp[1][i] = 1;
    	for(int i=2;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			if(a[i][j]>=a[i-1][j]) dp[i][j]=dp[i-1][j]+1;
    			else dp[i][j]=1;
    		}
    	}
    	memset(ans,0,sizeof(ans));
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			ans[i]=max(ans[i],dp[i][j]);
    		}
    		
    	}
    	int q;
    	cin>>q;
    	while(q--){
    		int x,y;
    		cin>>x>>y;
    		if(y-x+1 <= ans[y])puts("Yes");
    		else puts("No");
    	}
    	return 0;
    }

D题：

贪心。从最后一个字符串往前扫，如果前面的比后面的大，那就把前面的删了再重新从前面第一个字符串开始构造。

代码：

#include<bits/stdc++.h>
    using namespace std;
    string s[500005];
    int main()
    {
    	int n;
    	string ss;
    	cin>>n;
    	for(int i=0;i<n;i++){
    		cin>>s[i];
    	}
    	for(int i = n-1; i > 0 ; --i){
    		
    		if(s[i] < s[i-1]){ 
    			ss = s[i-1];
    			s[i-1] = "";
    			for(int j = 0; ss[j] <= s[i][j]; j++){
    				s[i-1] += ss[j];
    			}
    		}
    	}
    	for(int i=0;i<n;i++) cout<<s[i]<<endl;
    	return 0;
    }

E题：

典型的贪心。

把一堆空心圆堆起来。上面的外径比下面的内径大，上面的外径比下面的外径小。然后问你最大高度。

贪心。按外径把每组大到小排序。然后不断地贪心下一个就行了。貌似也能dp。

代码：

#include<bits/stdc++.h>
    using namespace std;
    vector<pair<pair<int,int>,int>>V;
    int main()
    {
    	int n;
    	cin>>n;
    	int a,b,h;
    	for(int i = 0; i < n; i++){
    		cin>>a>>b>>h;
    		V.push_back(make_pair(make_pair(b,a),h));
    	}
    	sort(V.rbegin(),V.rend());//按外径大到小 
    	/*
    	for(auto t : V){
    		cout<<t.first.second<<" ";
    		cout<<t.first.first<<" ";
    		cout<<t.second<<endl;
    	}
    	*/
    	long long ans=0;
    	priority_queue<pair<long long,int>>pq;
    	for(auto t : V)
    	{
    		int x = t.first.second;
    		int y = t.first.first;
    		int z = t.second;
    		while(!pq.empty() && pq.top().second >= y){
    			pq.pop();
    		}
    		long long res=0;
    		if(pq.empty()){
    			res = z;
    		}
    		else res = z + pq.top().first;
    		
    		ans = max(ans,res);
    		pq.push(make_pair(res,x));
    	}
    	cout<<ans<<endl;
    	return 0;
    }

[CF _401]: http://codeforces.com/contest/777