首页 > 其他分享 >2021CCPC(桂林)

2021CCPC(桂林)

时间:2022-11-03 11:13:29浏览次数:63  
标签:return int ll dis 2021CCPC 桂林 include define

A. A Hero Named Magnus

签到题 输出2x-1 注意用到unsigned long long

I. PTSD

签到题

G. Occupy the Cities

分析:

考虑从左到右依次考虑 pre表示当前1需要向前贡献多少 并且不断跟新pre

因为在有限的时间内 所有的1都尽可能的最大化 想到用二分时间mid

如果遇到pre>mid 这样一定不成立

如果遇到pre=mid 当前1一定要先先前扩展 再向后扩展 贡献为mid-1

如果遇到pre<mid 这样我可以第一次就向后扩展 贡献为mid

细节挺多的 调了好久

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
int ii,pre,edd,sum,T,n,mid,l,r,ans;
string s;
void solve();
bool ck(int x){
	ii=0;pre=0;edd=0; 
	while(ii<n){
		sum=0;
		while(s[ii]=='0'&&ii<n)ii++,sum++;
		if(ii==n){
			if(sum>edd)return false;
			return true;
		}
		pre=sum-edd;
		if(pre<0)pre=0;
		if(pre>x)return false;
		if(x>pre)
		edd=x;
		else edd=x-1;
		if(edd<0)edd=0;
		ii++;
		pre=0;
	}
		if(pre>0)return false;
		else return true;
}
int main(){
	cin>>T;
	while(T--)solve();
     return 0;
}
void solve(){
	cin>>n>>s;
	l=0,r=n;
	while(l<=r){
		mid=l+r>>1;
		if(ck(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d\n",ans);
}

E. Buy and Delete

分析: Bob最多删两次边 问题转化为求有向图的最小环

太菜了 有向图找环的问题困扰了我们好久

有向图找最小环

对每个点 i 进行dj最短路 先将i扩展的点放入队列中 再将dis[i]设为inf 最终dis[i]即为i点环的最小值

第一次遇到这样的做法 学到了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long lld;
const int N = 2005;
const int M = 5005;
const lld inf = 1e17;
int n, m;
lld dis[N], ans, minc = inf, c, w[M];
bool vis[N];
int nextt[M], to[M], head[N], cnt;
void add(int x, int y, lld z) {
	nextt[++cnt] = head[x]; w[cnt] = z;
	to[cnt] = y; head[x] = cnt;
}
priority_queue<pair<lld, int> > q;
void dijkstra() {
	while(!q.empty()) {
		int x = q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x] = true;
		for(int i = head[x]; i; i = nextt[i]) {
			int y = to[i];
			if(dis[y] > dis[x] + w[i]) {
				dis[y] = dis[x] + w[i];
				q.push(make_pair(-dis[y], y));
			}
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &c);
	for(int i = 1, x, y; i <= m; i++) {
		lld z;
		scanf("%d%d%lld", &x, &y, &z);
		add(x, y, z); minc = min(minc, z);
	}
	ans = inf;
	for(int x = 1; x <= n; x++) {
		for(int i = 1; i <= n; i++) dis[i] = inf;
		while(!q.empty()) q.pop();
		memset(vis, false, sizeof(vis));
		dis[x] = 0;
		for(int i = head[x]; i; i = nextt[i]) {
			int y = to[i];
			if(dis[y] > dis[x] + w[i]) {
				dis[y] = dis[x] + w[i];
				q.push(make_pair(-dis[y], y));
			}
		}
		dis[x] = inf;
		dijkstra();
		ans = min(ans, dis[x]);
	}
	if(ans == inf) {
		if(c >= minc) printf("1");
		else printf("0");
	} else {
		if(c >= ans) printf("2");
		else if(c >= minc) printf("1");
		else printf("0");
	}
	return 0;
}

D. Assumption is All You Need


题意:给出两个序列a和b,每次能够在a上交换一个逆序对,问能否构造一组序列将a变成b。

分析:这个题目不简单

发现考虑降序数组不太好 所以想到按照顺序贪心

考虑最大数n 如果 ida[n]>idb[n] 即需要将n换到前面去 发现这样是不可能成立的

对于ida[n]=idb[n] 就不需要再动他了

对于ida[n]<idb[n] 并不是一次性和目标位置交换 因为要尽可能大的数放前面 所以依次和大数交换

 #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repn(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=a;i>=n;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<long double,long double>
#define vl vector<ll>
#define vi vector<int>
#define x first
#define y second
#define eachit(x,y) for(auto x=y.begin();x!=y.end();x++)
#define each(x,y) for(auto& x:y)
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) (x).begin(), (x).end()
typedef unsigned long long int ull;
#define pb push_back
#define endl '\n'
ll gcd(ll a,ll b){if(b==0)return abs(a);else return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int mod = 998244353;
const ll INFLL=0x3f3f3f3f3f3f3f3fll;
const int INF=0x3f3f3f3f;
const double pi=acos(-1.0);
ll ksm(ll a,ll b)
{ll rec=1;while(b){if(b%2){rec*=a;rec%=mod;}ll tmp=a%mod;a=tmp*tmp;a%=mod;b>>=1;rec%=mod;}rec%=mod;return rec;}
ull fpow(ull a,ull b)
{ull rec=1;while(b){if(b%2){rec*=a;}ull tmp=a;a=tmp*tmp;b>>=1;}return rec;}
double dpow(double a,ll b)
{double rec=1;while(b){if(b%2){rec*=a;}double tmp=a;a=tmp*tmp;b>>=1;}return rec;}
int lowbit(int lowbitn){return lowbitn&(-lowbitn);}
ll lowbit(ll lowbitn){return lowbitn&(-lowbitn);}
const int N = 2050;
int a[N], b[N];
int ida[N], idb[N];
vector<pii> ans;
signed main()
{
    fastio
    int t;
    cin >> t;
    while(t --)
    {
    	ans.clear();
    	int n;
    	cin >> n;
    	repn(i, 1, n)
    	{
    		cin >> a[i];
    		ida[a[i]] = i;
    	}
    	repn(i, 1, n) 
    	{
    		cin >> b[i];
    		idb[b[i]] = i;
    	}
    	bool flag = 1;
    	per(i, n, 1)
    	{
    		if(ida[i] == idb[i]) continue;
    		if(ida[i] > idb[i]) 
    		{
    			//cout << i << endl;
    			flag = 0;
    			break;
    		}
			int now = ida[i], aim = idb[i];
			per(j, i - 1, 1)
			{
				if(ida[j] > now && ida[j] <= aim)
				{
					ida[i] = ida[j];
					swap(a[now], a[ida[j]]);
					swap(now, ida[j]);
					ans.pb({now, ida[j]});
				}
			}
    	}
    	repn(i, 1, n)
    	{
    		if(a[i] != b[i]) flag = 0;
    	}
    	if(!flag) cout << -1 << endl;
    	else
    	{
    		cout << ans.size() << endl;
    		each(it, ans) 
    		{
    			if(it.x > it.y)  swap(it.x, it.y);
    			cout << it.x << " " << it.y << endl;
    		}
    	}
    	
    }
    return 0;
}

标签:return,int,ll,dis,2021CCPC,桂林,include,define
From: https://www.cnblogs.com/wzxbeliever/p/16853766.html

相关文章

  • 2022CCPC(桂林)
    我的首站本来想着练练手拿铜牌血赚打铁不亏结果保底铜牌要是G题做出来应该可以冲击一下银牌https://codeforces.com/gym/104008A.Lily签到题:所有不在L旁的字符......
  • dijkstra 求最小环( CCPC桂林 - E. Buy and Delete )
    原文题意经过转化后,本质就是求最小环。有向图有以下三种实现方式,而无向图只能用第一种实现方式。实现方式1:删边求最短距离有向图实现方式2:回到起点构成环有向图实现......