• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

CF习题集一

开发技术 开发技术 3天前 11次浏览

CF习题集一

一、CF915E Physic++al Education Lessons

题目描述

(Alex)高中毕业了,他现在是大学新生。虽然他学习编程,但他还是要上体育课,这对他来说完全是一个意外。快要期末了,但是不幸的(Alex)的体育学分还是零蛋!

(Alex)可不希望被开除,他想知道到期末还有多少天的工作日,这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情:

从现在到学期结束还有 (n) 天(从 (1)(n) 编号),他们一开始都是工作日。接下来学校的工作人员会依次发出 (q) 个指令,每个指令可以用三个参数 (l,r,k) 描述:
如果 (k=1),那么从 (l)(r) (包含端点)的所有日子都变成非工作日。
如果 (k=2),那么从 (l)(r) (包含端点)的所有日子都变成工作日。
帮助(Alex)统计每个指令下发后,剩余的工作日天数。

输入格式:

第一行一个整数 (n),第二行一个整数 (q)((1le nle 10^9,;1le qle 3cdot 10^5)),分别是剩余的天数和指令的个数。

接下来 (q) 行,第 (i) 行有 (3) 个整数 (l_i,r_i,k_i)​,描述第 (i) 个指令((1le l_i,r_ile n,;1le kle 2))

输出格式:

输出 (q) 行,第 (i) 行表示第 (i) 个指令被下发后剩余的工作日天数。

输入输出样例

输入 #1

4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2

输出 #1

2
0
2
3
1
4

分析

这一道题只有区间赋值操作,因此我们用珂朵莉树随便搞搞就可以了

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
#define sit set<asd>::iterator
struct asd{
    int l,r;
    mutable int val;
    bool operator < (const asd& A)const{
        return l<A.l;
    }
    asd(int aa,int bb,int cc){
        l=aa,r=bb,val=cc;
    }
    asd(int aa){
        l=aa;
    }
};
set<asd> s;
sit Split(int wz){
    sit it=s.lower_bound(asd(wz));
    if(it!=s.end() && it->l==wz) return it;
    it--;
    int l=it->l,r=it->r,val=it->val;
    s.erase(it);
    s.insert(asd(l,wz-1,val));
    return s.insert(asd(wz,r,val)).first;
}
int sum;
void Assign(int l,int r,int val){
    sit it2=Split(r+1),it1=Split(l);
    for(sit it=it1;it!=it2;it++){
        sum-=it->val*(it->r-it->l+1);
    }
    s.erase(it1,it2);
    s.insert(asd(l,r,val));
    sum+=(r-l+1)*val;
}
int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    s.insert(asd(1,n,1));
    sum=n;
    while(q--){
        int aa,bb,cc;
        scanf("%d%d%d",&aa,&bb,&cc);
        if(cc==1){
            Assign(aa,bb,0);
        } else {
            Assign(aa,bb,1);
        }
        printf("%dn",sum);
    }
    return 0;
}

二、CF915C Permute Digits

题目描述

给出两个正整数(a),(b)。在十进制下重排(a),构造一个不超过(b)的最大数,不能有前导零。允许不去重排(a)

输入格式:

第一行一个数(a) ((1le ale 10^{18}))。第二行一个数(b)((1le ble 10^{18}))

数没有前导零,数据保证有解。

输出格式:

输出一个数,表示(a)重排后不超过(b)的最大数,不应该有前导零。

输出的数的长度应该与(a)相等,它应该是(a)的一个排列。

分析

这道题可以用贪心解决,分为两种情况

1、(a)的位数小于(b)的位数,此时我们把(a)的所有位从大到小排一下序即可

2、(a)的位数和(b)的位数相等,那么(a)的最高位一定小于等于(b)的最高位

此时又可以分成两种情况

第一种即(a)的最高位填的数字比(b)的最高位填的数字小

我们把剩下的从大到小排一下序即可

另一种就是(a)(b)最高位上的数字相等

我们可以选择一个满足条件的最大值填入(a)的第二位,对于其他位也是如此

这样看起来似乎没有什么问题,但是对于下面的这一组数据

15778899
98715689

如果我们用简单的贪心去匹配,那么(a)的前(5)位会分别被填上(98715)

匹配到第(6)位时,我们会发现此时没有合适的数字去匹配

因此,我们的贪心要能够支持回溯操作,即可持久化贪心

如果当前匹配不成功的话,那么回溯到上一状态继续匹配

时间复杂度(O(玄学))

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=25;
int a[maxn],cnt[maxn],ans[maxn],xn[maxn];
char s[maxn],s1[maxn];
signed main(){
	scanf("%s%s",s+1,s1+1);
	int len=strlen(s+1),len1=strlen(s1+1);
	for(int i=1;i<=len;i++) a[i]=s[i]-'0';
	if(len1>len){
		sort(a+1,a+1+len);
		for(int i=len;i>=1;i--) printf("%lld",a[i]);
		printf("n");
		return 0;
	}
	int qnd=0;
	for(int i=1;i<=len;i++){
		cnt[a[i]]++;
		xn[a[i]]++;
	}
	//处理出每一个数字在原序列中出现的个数
	bool bishangyigeda;
	if(cnt[s1[1]-'0']){
		cnt[s1[1]-'0']--;
		ans[1]=s1[1]-'0';
		int j=2;
		bishangyigeda=0;
		while(j<=len1){
			bool jud=0;
			if(bishangyigeda==0){
				for(int k=s1[j]-'0';k>=0;k--){
					if(cnt[k]){
						cnt[k]--;
						ans[j]=k;
						jud=1;
						if(k!=s1[j]-'0')bishangyigeda=1;
						break;
					}
				}
			} else {
				for(int k=9;k>=0;k--){
					if(cnt[k]){
						cnt[k]--;
						ans[j]=k;
						jud=1;
						break;
					}
				}
			}
			if(jud==0) qnd=1;
			int now=j;
			while(qnd==1 && j>=2){
				cnt[ans[j-1]]++;
				j--;
				for(int k=ans[j]-1;k>=0;k--){
					if(cnt[k]){
						cnt[k]--;
						ans[j]=k;
						jud=1;
						if(k!=s1[j]-'0')bishangyigeda=1;
						break;
					}
				}
				if(jud==1) qnd=0;
			}
			if(j==1 && qnd==1) break;
			if(jud==1) qnd=0;
			j++;
		}
	}
	//判断a和b的最高位是否相等
	if(qnd==0 && xn[s1[1]-'0']){
		for(int i=1;i<=len1;i++) printf("%lld",ans[i]);
		printf("n");
	} else {
		memset(ans,0,sizeof(ans));
		for(int i=s1[1]-'0'-1;i>=1;i--){
			if(xn[i]) {
				xn[i]--;
				ans[1]=i;
				break;
			}
		}
		int j=2;
		while(j<=len1){
			for(int k=9;k>=0;k--){
				if(xn[k]){
					xn[k]--;
					ans[j]=k;
					break;
				}
			}
			j++;
		}
		for(int i=1;i<=len1;i++) printf("%lld",ans[i]);
		printf("n");
	}
	return 0;
}


三、CF766D Mahmoud and a Dic++tionary

题目描述

给一些单词,它们可能是同义或者反义,给出一些关系定义,从前面的定义开始建立关系,如果有的关系定义和之前的冲突输出(NO),否则输出(YES)。然后查询(q)次单词(x)和单词(y)的关系。

分析

比较基本的扩展域并查集的题

对于一个点,我们把它拆成两个点,分别代表它本身和它的反义单词

如果原来的单词标号为(xx),那么反义单词标号为(xx+n)

在建立关系时,如果两个单词(aa)(bb)是同义单词,那么我们将(aa)(bb)(aa+n)(bb+n)并在一起

如果是反义单词,我们将(aa)(bb+n),(bb)(aa+n)并在一起

查询时同理

代码

#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
const int maxn=1e6+5;
int fa[maxn];
int zhao(int xx){
    if(fa[xx]==xx) return xx;
    return fa[xx]=zhao(fa[xx]);
}
void bing(int aa,int bb){
    fa[zhao(aa)]=zhao(bb);
}
int main(){
    for(int i=0;i<maxn;i++) fa[i]=i;
    int n,m,k;
    cin>>n>>m>>k;
    string s;
    for(int i=1;i<=n;i++){
        cin>>s;
        mp[s]=i;
    }
    int aa;
    string s1,s2;
    for(int i=1;i<=m;i++){
        cin>>aa>>s1>>s2;
        int xx=zhao(mp[s1]);
        int yy=zhao(mp[s2]);
        int zz=zhao(mp[s1]+n);
        int qq=zhao(mp[s2]+n);
        if(xx==yy){
            if(aa==1) printf("YESn");
            else printf("NOn");
        } else if(yy==zz){
            if(aa==2) printf("YESn");
            else printf("NOn");
        } else if(xx==qq){
            if(aa==2) printf("YESn");
            else printf("NOn");
        }else {
            if(aa==1){
                bing(mp[s1],mp[s2]);
                bing(mp[s1]+n,mp[s2]+n);
            } else {
                bing(mp[s1],mp[s2]+n);
                bing(mp[s2],mp[s1]+n);
            }
            printf("YESn");
        }
    }
    for(int i=1;i<=k;i++){
        cin>>s1>>s2;
        int xx=zhao(mp[s1]);
        int yy=zhao(mp[s2]);
        int zz=zhao(mp[s1]+n);
        int qq=zhao(mp[s2]+n);
        if(xx==yy || zz==qq) printf("1n");
        else if(yy==zz || xx==qq) printf("2n");
        else printf("3n");
    }
    return 0;
}

四、CF533B Work Group

题目描述

公司有(n)个人,(1)是总裁,每个人有一个直接上司。每一个人有一个权值,要求找一个集合,使集合中所有人权值之和最大。其中每一个人的下属(直接,间接)总数都必须是偶数。输出最大权值。

分析

树形(DP)

我们设(f[x][0][0])为以(x)为根的子树选择了偶数个节点,其中编号为(x)的节点不选所得到的最大权值

我们设(f[x][1][0])为以(x)为根的子树选择了偶数个节点,其中编号为(x)的节点选择所得到的最大权值

我们设(f[x][0][1])为以(x)为根的子树选择了奇数个节点,其中编号为(x)的节点不选所得到的最大权值

我们设(f[x][1][1])为以(x)为根的子树选择了奇数个节点,其中编号为(x)的节点选择所得到的最大权值

每次转移时,我们记录在(x)的儿子节点中选择奇数个节点的最大值(maxj),选择偶数个节点的最大值(maxo),最后更新(x)(f)值即可

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
ll f[maxn][2][2],a[maxn];
vector<ll> g[maxn];
void dfs(ll now){
    if(g[now].size()==0){
        f[now][0][0]=0;
        f[now][1][0]=a[now];
        f[now][0][1]=f[now][1][1]=-0x3f3f3f3f;
        return;
    }
    ll maxj=0,maxo=0;
    for(ll i=0;i<g[now].size();i++){
        ll u=g[now][i];
        dfs(u);
        ll aa=maxj,bb=maxo;
        if(aa!=0) maxj=max(aa+max(f[u][0][0],f[u][1][1]),bb+max(f[u][0][1],f[u][1][0]));
        else maxj+=(bb+max(f[u][0][1],f[u][1][0]));
        if(aa!=0) maxo=max(aa+max(f[u][0][1],f[u][1][0]),bb+max(f[u][0][0],f[u][1][1]));
        else maxo+=max(f[u][0][0],f[u][1][1]);
    }
    f[now][0][0]=maxo;
    f[now][1][0]=maxo+a[now];
    f[now][0][1]=maxj;
}
int main(){
    ll n;
    scanf("%lld",&n);
    ll rt;
    for(ll i=1;i<=n;i++){
        ll aa,bb;
        scanf("%lld%lld",&aa,&bb);
        if(aa==-1) rt=i;
        else g[aa].push_back(i);
        a[i]=bb;
    }                                                                               
    dfs(rt);
    printf("%lldn",max(max(f[rt][0][1],f[rt][0][0]),f[rt][1][0]));
    return 0;
}

程序员灯塔 , 版权所有
转载请注明原文链接:https://www.wangt.cc/2020/08/cf%e4%b9%a0%e9%a2%98%e9%9b%86%e4%b8%80/
喜欢 (0)