热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【超好懂的比赛题解】CodeforcesRound#747(Div.2)

title:CodeforcesRound#747(Div.2)date:2021-10-9tags:ACM,练习记录author:Linno题目链接:https:c

title :Codeforces Round #747 (Div. 2)
date : 2021-10-9
tags : ACM,练习记录
author : Linno


在这里插入图片描述

题目链接 :https://codeforces.com/contest/1594

补题进度 :已补完

这次做得可谓是相当差了,A题想复杂、C题调一小时重写才过,E题十分钟写完没交上去。总之还是太菜了。

A-Consecutive Sum Riddle

题意

给一个n,求L和R,使得[L,R]中所有整数加起来等于n。

思路

对于正数,我们知道n=sum[n]-sum[n-1],我们要减去n前面那一坨,只需要取负数的同样位置即可,即L=-n+1,R=n。负数同理。

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn=2e5+7;
const int mod&#61;1e9&#43;7;int t,n,L,R;signed main(){cin>>t;while(t--){cin>>n;if(n>0){L&#61;-n&#43;1,R&#61;n;}else L&#61;-n&#43;1,R&#61;n;cout<}

B-Special Numbers

题意

给出n,k&#xff0c;求第k个【n的幂集子集】之和的大小。

思路

考虑二进制&#xff0c;第k大的数其实就是k&#xff0c;普及到其他进制&#xff0c;也不过是把k二进制拆分&#xff0c;k&#61;1010表示第10大的数是n3&#43;n1n^3&#43;n^1n3&#43;n1

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn&#61;2e5&#43;7;
const int mod&#61;1e9&#43;7;int fpow(int a,int p){int res&#61;1;while(p){if(p&1) res&#61;res*a%mod;a&#61;a*a%mod;p>>&#61;1;}return res;
}int t,n,k,ans,cnt;signed main(){cin>>t;while(t--){cin>>n>>k;ans&#61;0;cnt&#61;0;while(k){if(k&1){ans&#43;&#61;fpow(n,cnt);ans%&#61;mod;}k>>&#61;1;cnt&#43;&#43;;}cout<}

C-Make Them Equal

题意

求多少次操作可以使得n长的字符串全为ch&#xff0c;每次操作可选择[1,n]中的一个数x&#xff0c;所有除不尽x的位置全部变为ch。

思路

很考察细节。很容易想到最多两次操作就能完成&#xff0c;对于这种情况我们都可以取pos1&#61;n-1,pos2&#61;n&#xff1b;对于1次操作的情况&#xff0c;x所在的位置字符必为ch&#xff0c;那么前面的元素必除不尽&#xff0c;遍历后面的元素即可。对于0次操作&#xff0c;就是所有位置都为ch。

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn&#61;3e5&#43;7;
const int mod&#61;1e9&#43;7;int t,n,pos,pos2,vt[maxn];
char ch;
string str;signed main(){cin>>t;while(t--){cin>>n>>ch;cin>>str;int flag&#61;0,flag2&#61;0,cnt&#61;0;for(int i&#61;0;i}

D-The Number of Imposters

题意

给定n个点m条边&#xff0c;每条边u指定v为c&#xff0c;已知c为imposter的点必说真话&#xff0c;c为crewmate的点必说假话&#xff0c;求图中最多有多少个imposter。

思路

相当于黑白涂色了&#xff0c;边的性质为1则两端不同色&#xff0c;否则两端同色。

双向建边跑二分图&#xff0c;取每个联通分块中个数多的答案加起来。

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn&#61;2e5&#43;7;
const int maxm&#61;1e6&#43;7;struct E{int nxt,v,f;
}e[maxm];int head[maxn],cnt&#61;0,ans&#61;0;
int vis[maxn],num[3],flag;void addedge(int u,int v,int f){e[&#43;&#43;cnt]&#61;(E){head[u],v,f};head[u]&#61;cnt;
}void dfs(int x,int col){ vis[x]&#61;col;num[col]&#43;&#43;;for(int i&#61;head[x];i;i&#61;e[i].nxt){int to&#61;e[i].v,fang&#61;(col&#61;&#61;2)?1:2;if(e[i].f&#61;&#61;1){if(vis[to]){if(vis[to]!&#61;fang) flag&#61;1;continue;}else dfs(to,fang); }if(e[i].f&#61;&#61;2){if(vis[to]){if(vis[to]!&#61;col) flag&#61;1;continue;}else dfs(to,col);}}
}void init(){ans&#61;0;cnt&#61;0;memset(vis,0,sizeof(vis));memset(head,0,sizeof(head));}signed main(){int t,n,m,u,v;string str;cin>>t;while(t--){cin>>n>>m;init();for(int i&#61;1;i<&#61;m;i&#43;&#43;){cin>>u>>v;cin>>str;if(str&#61;&#61;"imposter") flag&#61;1;else flag&#61;2;addedge(u,v,flag);addedge(v,u,flag);}flag&#61;0;for(int i&#61;1;i<&#61;n;i&#43;&#43;){num[1]&#61;0,num[2]&#61;0;if(!vis[i]){dfs(i,1);ans&#43;&#61;max(num[1],num[2]);}}if(flag) cout<<-1<<"\n";else cout<}

E1-Rubik’s Cube Coloring (easy version)

题意

有n^2-1个节点&#xff0c;每个节点涂上魔方6种颜色中的一种&#xff0c;相邻点颜色必须在魔方中相邻&#xff08;有4种&#xff09;&#xff0c;求种方案数。

思路

第一个节点可以涂6种色&#xff0c;然后对于任意两个相邻的点都只能涂4种色&#xff0c;共2n−12^n-12n1个点&#xff0c;那么答案就是6∗42n−26*4^{2^n-2}642n2

注意对2用快速幂不要取模&#xff0c;不会爆long long。

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn&#61;2e5&#43;7;
const int mod&#61;1e9&#43;7;int fpow(int a,int p){int res&#61;1;while(p){if(p&1) res&#61;res*a%mod;a&#61;a*a%mod;p>>&#61;1;}return res;
}int k;signed main(){cin>>k;int tmp&#61;1;for(int i&#61;1;i<&#61;k;i&#43;&#43;) tmp<<&#61;1; int ans&#61;6*fpow(4,tmp-2);cout<}

E2-Rubik’s Cube Coloring (hard version)

题意

在上一题的基础上加多一个限定&#xff0c;就是我们固定住第i个节点的颜色&#xff0c;再求方案数。

思路

真正用到的点只有2000个&#xff0c;可以建立一棵虚树进行dp。

由于是完全二叉树&#xff0c;祖先的个数也只有lognlognlogn个&#xff0c;可以接受。

所有隐式节点或者说没被建立的节点&#xff0c;其值不受固定颜色点的干扰

转移时直接把两个子树乘起来。

代码

不是很会写&#xff0c;抄博客的。

#include
#define int long long
using namespace std;
typedef double db;
const int mod&#61;1e9&#43;7;
const db eps&#61;1e-10;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return xinline db Max(db x,db y){return x-y>eps?x:y;}
inline db Min(db x,db y){return x-yinline int Add(int x,int y,int M&#61;mod){return (x&#43;y)%M;}
inline int Mul(int x,int y,int M&#61;mod){return 1ll*x*y%M;}
inline int Dec(int x,int y,int M&#61;mod){return (x-y&#43;M)%M;}
inline int Abs(int x){return x<0?-x:x;}
inline int read(){ //快读 int s&#61;0,w&#61;1;char ch&#61;getchar();while(!isdigit(ch)){if(ch&#61;&#61;&#39;-&#39;)w&#61;-1;ch&#61;getchar();}while(isdigit(ch)){s&#61;s*10&#43;ch-&#39;0&#39;;ch&#61;getchar();}return s*w;
}
inline void write(int x){ //快速输出 if(x<0)putchar(&#39;-&#39;),x&#61;-x;if(x>9)write(x/10);putchar(x%10&#43;&#39;0&#39;);
}
const int N&#61;2e5&#43;10;
int k,n;
int F[61];
string s;
typedef long long ll;
mappa,col,lson,rson,f[4]; //实际上的点编号太大了&#xff0c;用map存
vectorNode;
inline int qpow(int x,int y){ //快速幂 int res&#61;1;while(y){if(y&1)res&#61;Mul(res,x);x&#61;Mul(x,x);y>>&#61;1;}return res;
}
inline int Getdep(int v){return log2(v)&#43;1;} //获取点的深度
void Treat(){for(auto v:Node){if(lson[v]||rson[v])continue;int Dep&#61;k-Getdep(v)&#43;1;if(col[v])f[col[v]][v]&#61;Mul(1,qpow(4,F[Dep]));else for(int i&#61;1;i<&#61;3;&#43;&#43;i)f[i][v]&#61;Mul(2,qpow(4,F[Dep]));}
}
void DP(ll x){if(!lson[x]&&!rson[x])return;if(lson[x])DP(lson[x]);if(rson[x])DP(rson[x]);ll L1&#61;f[1][lson[x]],L2&#61;f[2][lson[x]],L3&#61;f[3][lson[x]],R1&#61;f[1][rson[x]],R2&#61;f[2][rson[x]],R3&#61;f[3][rson[x]];if(!lson[x]){L1&#61;L2&#61;L3&#61;Mul(2,qpow(4,F[k-Getdep(x*2)&#43;1]));}if(!rson[x]){R1&#61;R2&#61;R3&#61;Mul(2,qpow(4,F[k-Getdep(x*2)&#43;1]));}if(!col[x]){f[1][x]&#61;Mul(2,Mul(Add(L2,L3),Add(R2,R3)));f[2][x]&#61;Mul(2,Mul(Add(L1,L3),Add(R1,R3)));f[3][x]&#61;Mul(2,Mul(Add(L2,L1),Add(R2,R1)));}else{if(col[x]&#61;&#61;1)f[1][x]&#61;Mul(Add(L2,L3),Add(R2,R3));if(col[x]&#61;&#61;2)f[2][x]&#61;Mul(Add(L1,L3),Add(R1,R3));if(col[x]&#61;&#61;3)f[3][x]&#61;Mul(Add(L2,L1),Add(R2,R1));}
}
signed main(){k&#61;read();F[1]&#61;0;for(int i&#61;2;i<&#61;60;&#43;&#43;i){F[i]&#61;Add(F[i-1],1,mod-1);F[i]&#61;Mul(F[i],2,mod-1);}n&#61;read();for(int i&#61;1;i<&#61;n;&#43;&#43;i){int pos&#61;read();cin>>s;if(s&#61;&#61;"orange"||s&#61;&#61;"red")col[pos]&#61;1;if(s&#61;&#61;"white"||s&#61;&#61;"yellow")col[pos]&#61;2;if(s&#61;&#61;"blue"||s&#61;&#61;"green")col[pos]&#61;3;while(pos){ //返回向上到父亲的一条链Node.emplace_back(pos);pa[pos]&#61;pos/2;if(pos%2&#61;&#61;0)lson[pos/2]&#61;pos;else rson[pos/2]&#61;pos;pos/&#61;2;}}sort(Node.begin(),Node.end()); //排序所有关键节点 ll root&#61;1;Treat();DP(root);int res&#61;Add(f[3][root],Add(f[1][root],f[2][root]));write(res);putchar(&#39;\n&#39;);return 0;
}

F-Ideal Farm

题意

如果每个盒子都有求并且存在一个区间[l,r]使得∑i&#61;lra[i]&#61;k,其中a[i]表示第i个盒子的球数\sum_{i&#61;l}^ra[i]&#61;k,其中a[i]表示第i个盒子的球数i&#61;lra[i]&#61;k,a[i]i&#xff0c;那么我们就说这个方案是合理的。每组数据给定球数s,盒子数n以及k&#xff0c;问是否无论怎么划分都是合理的。

思路

首先我们向每个盒子加一个球&#xff0c;那么剩下的球&#xff0c;每隔k个盒子就再放k个&#xff0c;这样可以保证前面的区间都不存在方案使之合理&#xff0c;如果到最后依然有球剩下&#xff0c;那么就说明可以构建出一种不合理的方案&#xff0c;否则无论怎样都是合理的。

注&#xff1a;k>s是不合理的&#xff0c;并且特判s&#61;&#61;k是合理的!

代码

#include
#define int long long
using namespace std;int t,s,n,k,flag,tim;signed main(){cin>>t;while(t--){cin>>s>>n>>k;flag&#61;0;if(s&#61;&#61;k){puts("YES");continue;}if(k>s) flag&#61;1;else{s-&#61;n; //每个pen先放一个tim&#61;n/k;s-&#61;tim*k;if(s>&#61;0) flag&#61;1;}if(flag) puts("NO");else puts("YES"); } return 0;
}


推荐阅读
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 本文深入探讨了 Java 中的 Serializable 接口,解释了其实现机制、用途及注意事项,帮助开发者更好地理解和使用序列化功能。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 本文介绍了如何在C#中启动一个应用程序,并通过枚举窗口来获取其主窗口句柄。当使用Process类启动程序时,我们通常只能获得进程的句柄,而主窗口句柄可能为0。因此,我们需要使用API函数和回调机制来准确获取主窗口句柄。 ... [详细]
  • 文件描述符、文件句柄与打开文件之间的关联解析
    本文详细探讨了文件描述符、文件句柄和打开文件之间的关系,通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
author-avatar
荆梦梦丶乐园
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有