CF习题集一
CF习题集一
一、CF915E Physical Education Lessons
题目描述
\(Alex\) 高中毕业了，他现在是大学新生。虽然他学习编程，但他还是要上体育课，这对他来说完全是一个意外。快要期末了，但是不幸的 \(Alex\) 的体育学分还是零蛋！
\(Alex\) 可不希望被开除，他想知道到期末还有多少天的工作日，这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情：
从现在到学期结束还有 \(n\) 天(从 \(1\) 到 \(n\) 编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出 \(q\) 个指令，每个指令可以用三个参数 \(l,r,k\) 描述：
如果 \(k=1\) ，那么从 \(l\) 到 \(r\) （包含端点）的所有日子都变成非工作日。
如果 \(k=2\) ，那么从 \(l\) 到 \(r\) （包含端点）的所有日子都变成工作日。
帮助
\(Alex\)
统计每个指令下发后，剩余的工作日天数。
输入格式：
第一行一个整数 \(n\) ，第二行一个整数 \(q\) \((1\le n\le 10^9,\;1\le q\le 3\cdot 10^5)\) ，分别是剩余的天数和指令的个数。
接下来 \(q\) 行，第 \(i\) 行有 \(3\) 个整数 \(l_i,r_i,k_i\) ，描述第 \(i\) 个指令 \((1\le l_i,r_i\le n,\;1\le k\le 2)\) 。
输出格式：
输出 \(q\) 行，第 \(i\) 行表示第 \(i\) 个指令被下发后剩余的工作日天数。
输入输出样例
输入 #1
输出 #1
分析
这一道题只有区间赋值操作，因此我们用珂朵莉树随便搞搞就可以了
代码
#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("%d\n",sum);
}
return 0;
}
二、CF915C Permute Digits
题目描述
给出两个正整数 \(a\) , \(b\) 。在十进制下重排 \(a\) ，构造一个不超过 \(b\) 的最大数，不能有前导零。允许不去重排 \(a\) 。
输入格式：
第一行一个数 \(a\) \((1\le a\le 10^{18})\) 。第二行一个数 \(b\) \((1\le b\le 10^{18})\)
数没有前导零，数据保证有解。
输出格式：
输出一个数，表示 \(a\) 重排后不超过 \(b\) 的最大数，不应该有前导零。
输出的数的长度应该与 \(a\) 相等，它应该是 \(a\) 的一个排列。
分析
这道题可以用贪心解决，分为两种情况
1、 \(a\) 的位数小于 \(b\) 的位数，此时我们把 \(a\) 的所有位从大到小排一下序即可
2、 \(a\) 的位数和 \(b\) 的位数相等，那么 \(a\) 的最高位一定小于等于 \(b\) 的最高位
此时又可以分成两种情况
第一种即 \(a\) 的最高位填的数字比 \(b\) 的最高位填的数字小
我们把剩下的从大到小排一下序即可
另一种就是 \(a\) 和 \(b\) 最高位上的数字相等
我们可以选择一个满足条件的最大值填入 \(a\) 的第二位，对于其他位也是如此
这样看起来似乎没有什么问题，但是对于下面的这一组数据
如果我们用简单的贪心去匹配，那么 \(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 Dictionary
题目描述
给一些单词，它们可能是同义或者反义，给出一些关系定义，从前面的定义开始建立关系，如果有的关系定义和之前的冲突输出 \(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("YES\n");
else printf("NO\n");
} else if(yy==zz){
if(aa==2) printf("YES\n");
else printf("NO\n");
} else if(xx==qq){
if(aa==2) printf("YES\n");
else printf("NO\n");
}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("YES\n");
}
}
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("1\n");
else if(yy==zz || xx==qq) printf("2\n");
else printf("3\n");
}
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("%lld\n",max(max(f[rt][0][1],f[rt][0][0]),f[rt][1][0]));
return 0;
}
![[图]微软骚操作：通过Outlook在Android长按菜单中嵌入Bing搜索](https://img1.tuicool.com/iq2Y3uY.jpg!web)