2021 CCPC桂林G E D【二分、区间贪心、有向最小环】

A I 签到题

略

G题二分+贪心

代码

#include
using namespace std;
#define int long long
#define N 1000006
#define inf 0x3f3f3f3f3f
int T,n,m;int va[N];string s;
int suml[N],sumr[N];int vis[N];
bool check(int mid)
{
	for(int i=1;i<=n;i++)vis[i]=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='0'){
			int minn=min(i-suml[i],sumr[i]-i)+1; //最近的1到自己的距离+1，1是选择一次的时间
			if(minn<=mid)continue;
			if(minn==mid+1){                    //最多能处理这些
				if(suml[i]>=1&&!vis[suml[i]]){  //尽量用左边的1，右边的留给别人，这样最贪心
					vis[suml[i]]=1;continue;   
                //如果刚好，vis先置为1，如果已经有了，那么就算了
				}
				if(sumr[i]<=n&&!vis[sumr[i]]){
					vis[sumr[i]]=1;continue;
				}
			}
			return false;
		}
	}
	return true;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--){
		cin>>n;cin>>s;s="!"+s;
		int maxnl=-inf,maxnr=inf;
		for(int i=1;i<=n;i++){
			if(s[i]=='0')suml[i]=maxnl; //maxnl是左边而来的1
			else maxnl=i;
		}
		for(int i=n;i>=1;i--){
			if(s[i]=='0')sumr[i]=maxnr; //maxnr是右边而来的1
			else maxnr=i;
		}
		int l=0,r=n;
		while(l
			int mid=(l+r)>>1;
			if(check(mid))r=mid;
			else l=mid+1;
		}
		cout<"\n";
	}
	return 0;
}
 

E. Buy and Delete（有向最小环）

Problem - E - Codeforces

题意：

G图有n个点，首先G图无边，Alice买了一些边放到G里。之后，Bob删边，Bob删子集SS，SS里面无环。商店里有m条边，Alice有c元。Alice要使Bob删掉的次数最大化，求Bob删的回数

思路：

买不起--0，无环--1，有环--2

如果一条边都买不起的话，输出0；不然直接先置为1；假设把商店里所有边都放到G图里，在G中求有向图最小环；

有向最小环的寻找方式：有向图求最小环【里面还有 有向最大环 有向判负环】

这里采用Dijkstra算法

代码：

#include
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
typedef pair<long long,int> pll;
vectormp[2005];int dis[2005][2005];bool vis[2005];
int ans=0;bool flag=0;int n,m,c;
void dijkstra(int u)
{
    for(int i=1;i<=n;i++) dis[u][i]=INF;
    memset(vis,0,sizeof vis);
    dis[u][u]=0;
    priority_queue,greater >heap;
    heap.push({0,u});
    while (heap.size()){
        pll t=heap.top();heap.pop();
        int ver=t.second;
        if (vis[ver]) continue;
        vis[ver]=true;
        for(auto k:mp[ver]){
            if(!vis[k.second]&&dis[u][k.second]>dis[u][ver]+k.first){
                dis[u][k.second]=dis[u][ver]+k.first;
                heap.push({dis[u][k.second],k.second});
            }
        }
    }
}
signed main()
{
    cin>>n>>m>>c;
    for(int i=1;i<=m;i++){
        int uu,vv,p;cin>>uu>>vv>>p;
        mp[uu].push_back({p,vv});
        if(c>=p){ans=1;}
    }
    if(ans==0){cout<<0;return 0;}
    int minn=INF;
    for(int i=1;i<=n;i++)dijkstra(i);
    for(int i=1;i<=n;i++){
       for(int j=0;jsize();j++){
            minn=min(minn,mp[i][j].first+dis[mp[i][j].second][i]);
       }
    }
    if(minn<=c)ans=2;
    cout<
    return 0;
}

D. Assumption is All You Need（贪心 暴力）

题意：

 对于A数组中每个逆序对，交换它们，输出交换策略

思路：

贪心+暴力。

参考：2021 CCPC 桂林站 ADEGIK 

如果该位上a[i]和b[i]上的一样，就没有换的必要了；

如果该位上a[i]要比b[i]的小，a[i]前面的已经有序，没有换的必要；由于只能逆序对交换元素，a[i]的后面再怎么换也只能换比a[i]更小的，无解，输出-1。

如果该位上a[i]要比b[i]的大，遍历a[i]后面的每一位元素a[j]，如果存在小于a[i]（符合交换条件）、大于等于b[i]（逼近b[i]），则进行交换；

在进行每一次交换后，a[i]的值势必会渐渐接近b[i]最后等于b[i]，而不断地交换也可以使得当前较大的元素最大限度地留在较前的位置（较早地被swap了而不是找到匹配元素再进行交换）。

注意：

记得取消同步 不然会超时 ios::sync_with_stdio(0);cin.tie(0);

代码：

#include
using namespace std;
int a[2030],b[2030];
int pos[2030];int n;
vectorint,int> >ans;
 
void solve(){
    ans.clear();
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        if(a[i]==b[i])continue;
        else if(a[i]-1<<'\n';return;}
        else if(a[i]>b[i]){
            for(int j=i+1;j<=n;j++){
                if(a[j]=b[i]){//满足逆序且逐渐逼近b[i]
                    swap(a[j],a[i]);
                   ans.push_back({i,j});
                   if(a[i]==b[i])break;
                }
            }
        }
    }
    cout<size()<<'\n';
    for(int i=0;isize();i++){
        cout<" "<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}